ACHIEVING FULL PARALLELISM USING MULTIDIMENSIONAL RETIMING

Most scientific and Digital Signal Processing (DSP) applications are r ecursive or iterative. Transformation techniques are usually applied t o gel optimal execution rates in parallel and/or pipeline systems. The retiming technique is a common and valuable transformation tool in on e-dimensional problems, When loops are represented by data flow graphs (DFGs). In this paper, uniform nested loops are modeled as multidimen sional data flow graphs (MDFGs). Full parallelism of the loop body, i. e., all nodes in the MDFG executed in parallel, substantially decrease s the overall computation time. it is well known that, for one-dimensi onal DFGs, retiming can not always achieve full parallelism, ether exi sting optimization techniques or nested loops also can not always achi eve full parallelism. This paper shows an important and counter-intuit ive result, which proves that we can always obtain full-parallelism fo r MDFGs with more than one dimension. This result is obtained by trans forming the MDFG into a new structure. The restructuring process is ba sed on a multidimensional retiming technique. The theory and two algor ithms to obtain full parallelism are presented in this paper. Examples of optimization of nested loops and digital signal processing designs are shown to demonstrate the effectiveness of the algorithms.