Nl. Passos et Ehm. Sha, ACHIEVING FULL PARALLELISM USING MULTIDIMENSIONAL RETIMING, IEEE transactions on parallel and distributed systems, 7(11), 1996, pp. 1150-1163
Citations number
33
Categorie Soggetti
System Science","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
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.