Title :
Partitioning and retiming of multi-dimensional systems
Author :
Passos, Nelson ; Sha, Edwin Hsing-Mean ; Bass, Steven C.
Author_Institution :
Dept. of Comput. Sci. & Eng., Notre Dame Univ., IN, USA
fDate :
30 May-2 Jun 1994
Abstract :
The use of massive parallelism in solving Partial Differential Equations (PDEs) has been studied for a long time. Fettweis and Nitache (1991) introduced a new method of transforming a PDE problem in a set of computational nodes represented by wave digital filters working in a multidimensional environment. Those computational nodes may not be mapped one-to-one to processor elements. After the nodes are partitioned into blocks, this paper introduces the concept of transforming such blocks to multidimensional data flow graphs, and an algorithm to obtain a final execution schedule with an optimal performance by using multidimensional retiming. The method is applicable to any uniformly represented data dependence graph and the Fettweis and Nitache method was chosen as an interesting example of its application
Keywords :
data flow graphs; mathematics computing; multidimensional systems; parallel algorithms; partial differential equations; scheduling; timing; wave digital filters; computational nodes; execution schedule; massive parallelism; multi-dimensional systems; multidimensional data flow graphs; multidimensional environment; partial differential equations; partitioning; retiming; uniformly represented data dependence graph; wave digital filters; Computational modeling; Computer science; Digital filters; Equations; Multidimensional systems; Parallel processing; Partitioning algorithms; Processor scheduling; Scheduling algorithm; Timing;
Conference_Titel :
Circuits and Systems, 1994. ISCAS '94., 1994 IEEE International Symposium on
Conference_Location :
London
Print_ISBN :
0-7803-1915-X
DOI :
10.1109/ISCAS.1994.409238
