Author: Chen Y.S. Wang S.D. Wang C.M.
Publisher: Academic Press
ISSN: 0743-7315
Source: Journal of Parallel and Distributed Computing, Vol.35, Iss.2, 1996-06, pp. : 123-132
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Abstract
In this paper, an approach to tiling nested loops for maximizing parallelism is proposed. The proposed method aims at aggregating independent computations of a loop nest into rectangular blocks and maximizing the block sizes for maximizing parallelism. At first, all the independent computations that can be executed in the first time unit are identified. These computations are called the initially independent computations. Then it is shown that all of them can be collected as a union of rectangular blocks. So, based on these, the entire iteration space of the loops is partitioned into rectangular blocks for maximizing parallelism. The proposed method is formulated as systematic procedures which can easily be implemented in a parallelizing compiler. It is shown that when the wavefront transformation is combined with the proposed method, the loops can always be tiled so that the tile size is greater than one. In comparison with previous work on tiling, the proposed method is shown to have several advantages as summarized in the conclusions of this paper.
Related content
Communication-Minimal Tiling of Uniform Dependence Loops
By Xue J.
Journal of Parallel and Distributed Computing, Vol. 42, Iss. 1, 1997-04 ,pp. :
Optimizing Nested Loops Using Local CPS Conversion
By Reppy J.
LISP and Symbolic Computation, Vol. 15, Iss. 2-3, 2002-09 ,pp. :