Partitioning and retiming of multi-dimensional systems
Nelson Luiz Passos, Edwin H.‐M. Sha, S. C. Bass · 2002
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.>