Date: Tuesday, 26-Nov-96 00:09:46 GMT Server: NCSA/1.3 MIME-version: 1.0 Content-type: text/html Last-modified: Wednesday, 20-Sep-95 22:45:59 GMT Content-length: 2987 NSF CAREER Project [ U_N_I_V_E_R_S_I_T_Y___o_f___N_O_T_R_E___D_A_M_E ]

Principal Investigator: Dr. Edwin Sha

NSF CAREER Award (1995 - 1998)

Grant Number: MIP-9501006

Title: High-Level Design Methodologies for Time-Optimal and Memory-Optimal Systems

Abstract:

Since most time and memory critical parts of scientific computing applications are usually concentrated in nested loops, this research focuses on optimization algorithms for synthesis of those multi-level loops. The loop nests are modeled as Multi-dimensional Data-Flow Graphs (MDFG), and algorithms taking advantage of the multi-dimensionality are designed. Computation of a nested loop can be visualized as the repeated executions of the iteration body in a multi-dimensional iteration space. By considering the iteration space and the iteration body simultaneously, the proposed transformation and optimization techniques will be able to optimize throughput and memory requirement at the behavior level. The proposed project will develop polynomial-time algorithms on various graph models rather than using traditional integer linear programming approaches. Research topics of this project include:

1. Graph transformation and optimization techniques using the concept of multi-dimensional interleaving and retiming to obtain optimal throughput with the minimal increase of memory requirement.

2. Data scheduling techniques to minimize the size of the first-level memory (on-chip memory) for a given time constraint, and techniques to maximize data utilization for a given size of on-chip memory.

3. Design automation for Hardware/Multi-Software, HMS, (special hardware with multiple processors) co-design.

4. Development of synthesis tools for multi-dimensional applications.

Graduate Students

Technical Reports may be found in the CSE departmental report archives.


Dr. Edwin Sha
Department of Computer Science and Engineering
University of Notre Dame,
Notre Dame, IN 46556, USA.

219 631-8803 (Office)
219 631-9260 (FAX)

esha@bach.helios.nd.edu or
hms@cse.nd.edu

Revised - May 13, 1995.