Partitioning and Retiming of Multi-Dimensional Systems

The use of massive parallelism on solving Partial Differential Equations has been studied for a long time. Alfred Fettweis has 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 multi-dimensional data flow graphs, and an algorithm to obtain a final execution schedule with an optimal performance by using multi-dimensional retiming. The method is applicable to any uniformly represented data dependence graph and the Fettweis method was chosen as an interesting example of its application