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

Volume

4

fYear

1994

fDate

30 May-2 Jun 1994

Firstpage

227

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1994. ISCAS '94., 1994 IEEE International Symposium on

Conference_Location

London

Print_ISBN

0-7803-1915-X

Type

conf

DOI

10.1109/ISCAS.1994.409238

Filename

409238