Minimum dependence distance tiling of nested loops with non-uniform dependences

@inproceedings{Punyamurtula94, abstract = {We address the problem of partitioning nested loops with non-uniform (irregular) dependence vectors. Although many methods exist for nested loop partitioning, most of these perform poorly when parallelizing nested loops with irregular dependencies. We apply the results of classical convex theory and principles of linear programming to iteration spaces and show the correspondence between minimum dependence distance computation and iteration space tiling. The cross-iteration dependencies are analyzed by forming an Integer Dependence Convex Hull (IDCH). A simple way to compute minimum dependence distances from the dependence distance vectors of the extreme points of the IDCH is presented. Using these minimum dependence distances the iteration space can be tiled. Iterations in a tile can be executed in parallel and the tiles can be executed with proper synchronization. We demonstrate that our technique gives much better speedup and extracts more parallelism than the existing techniques}, author = {Punyamurtula, S. and Chaudhary, V. }, booktitle = {Parallel and Distributed Processing, 1994. Proceedings. Sixth IEEE Symposium on}, citeulike-article-id = {2758506}, doi = {10.1109/SPDP.1994.346179}, journal = {Parallel and Distributed Processing, 1994. Proceedings. Sixth IEEE Symposium on}, pages = {74--81}, posted-at = {2008-05-05 19:03:43}, priority = {2}, title = {Minimum dependence distance tiling of nested loops with non-uniform dependences}, url = {http://dx.doi.org/10.1109/SPDP.1994.346179}, year = {1994} }

TY - CONF ID - Punyamurtula94 L3 - citeulike-article-id:2758506 TI - Minimum dependence distance tiling of nested loops with non-uniform dependences T2 - Parallel and Distributed Processing, 1994. Proceedings. Sixth IEEE Symposium on JF - Parallel and Distributed Processing, 1994. Proceedings. Sixth IEEE Symposium on SP - 74 EP - 81 N2 - We address the problem of partitioning nested loops with non-uniform (irregular) dependence vectors. Although many methods exist for nested loop partitioning, most of these perform poorly when parallelizing nested loops with irregular dependencies. We apply the results of classical convex theory and principles of linear programming to iteration spaces and show the correspondence between minimum dependence distance computation and iteration space tiling. The cross-iteration dependencies are analyzed by forming an Integer Dependence Convex Hull (IDCH). A simple way to compute minimum dependence distances from the dependence distance vectors of the extreme points of the IDCH is presented. Using these minimum dependence distances the iteration space can be tiled. Iterations in a tile can be executed in parallel and the tiles can be executed with proper synchronization. We demonstrate that our technique gives much better speedup and extracts more parallelism than the existing techniques AU - Punyamurtula, S AU - Chaudhary, V PY - 1994/// UR - http://dx.doi.org/10.1109/SPDP.1994.346179 ER -