Total views : 450

A Loop Splitting Method of Irregular and Flow Dependence Loops

Affiliations

  • Division of Information and Communication Engineering, Baekseok University, Korea, Republic of

Abstract


A lot of work has been done in parallelizing nested loops with uniform dependences, from dependence analysis to loop transformation. Loops with non-uniform dependences are not so uncommon in the real world. This paper proposes an efficient method of splitting and transforming nested loops with irregular and flow dependences for maximizing parallelism. Our approach is based on the Convex Hull theory that has adequate information to handle irregular dependences, and also based on minimum dependence distance tiling methods. We will first show how to find the incrementing minimum dependence distance. Next, we will propose how to tile the iteration space efficiently according to the incrementing minimum dependence distance. Finally, we will show how to achieve more parallelism by loop interchanging and how to transform it into parallel loops. Comparison with some other methods shows more parallelism than other existing methods.

Keywords

Flow Dependence, Irregular Dependence, Loop Transformation, Parallelizing Compiler

Full Text:

 |  (PDF views: 212)

References


  • Banerjee U. Loop Transformations for Restructuring Compilers: The Foundations. Norwell, Massachusetts: Kluwer Academic Publishers; 1993.
  • Cho CK, Shim JC, Lee MH. A loop transformation for maximizing parallelism from single loops with non-uniform dependences. Proceedings of High Performance Computing Asia ‘97; 1997. p. 696–9.
  • Cho CK, Lee MH. A loop parallization method for nested loops with non-uniform dependences. Proceedings of the International Conference on Parallel and Distributed Systems; 1997; p. 314–21.
  • Ju J, Chaudhary V. Unique sets oriented partitioning of nested loops with non-uniform dependences. Proceedings of International Conference on Parallel Processing; 1996.p. 45–52.
  • Punyamurtula S, Chaudhary V. Minimum dependence distance tiling of nested loops with non-uniform dependences. Proceedings of Symposium on Parallel and Distributed Processing; 1994. p. 74–81.
  • Punyamurtula S, Chaudhary V, Ju J, Roy S. Compile time partitioning of nested loop iteration spaces withnon-uniform dependences. Journal of Parallel Algorithms and Applications. 1996.
  • Tzen T, Ni L. Dependence uniformization: A loop parallelization technique. IEEE Transactions on Parallel and Distributed Systems. 1993; 4(5):547–58.
  • Zaafrani AA, Ito MR. Parallel region execution of loops with irregular dependences. Proceedings of the International Conference on Parallel Processing;1994. p. 11–9.

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.