Most scientific and DSP applications are recursive or iterative. Transformation techniques are usually applied to get optimal execution rates in parallel and/or pipeline systems. Loop nests are usually the most time and memory consuming parts, and are commonly found in scientific applications, such as image processing, DSP (including multi-dimensional DSP), computational fluid dynamics, geophysical data analysis, and computer vision. We model uniform loop nests by multi-dimensional (MD) data-flow graphs (MDFG). Several transformation techniques have been developed, such as MD retiming, MD rotation, Push-up scheduling.
MD retiming technique is able to transform any MDFG into a fully parallel one. Full parallelism of the loop body, i.e., all nodes in the MDFG executed in parallel, substantially decreases the overall computation time. It is well known that, for one-dimensional DFGs, retiming can not always achieve full parallelism. Other existing optimization techniques for nested loops also can not always achieve full parallelism. We show an important and counter-intuitive result, which proves that we can always obtain full-parallelism for MDFGs with more than one dimension. This transformation is done in polynomial time. We obtained the best-known results in terms of execution length, memory requirement and computation complexity.
When resource constraint is imposed, two techniques are developed, MD Rotation and Push-Up Scheduling. The push-up scheduling algorithm is able to achieve the shortest possible schedule length in polynomial time. This shows an interesting and important result which proves that the problem of scheduling multi-dimensional systems is not NP-hard as in the one-dimensional case.
Five journal papers have been published related to this category.