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
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.
Technical Reports may be found in the CSE departmental report archives.
219 631-8803 (Office)
219 631-9260 (FAX)
esha@bach.helios.nd.edu or
Revised - May 13, 1995.