next up previous
Next: Calculating Blocked Decompositions Up: Blocked Decompositions Previous: Blocked Decompositions

Blocked Decomposition Model

Our decomposition model is easily extended to incorporate the concept of tiling. In general, tiling creates two sets of loops: the inner loops iterate within the block and the outer loops iterate across the blocks. The inner loops are allocated to the same processor, while the outer loops are distributed across the processors. In this way, we achieve locality within the block, and parallelism across the blocks.

Mathematically we have represented the computation that is allocated to the same processor as a vector space . Focusing now on the loops within an inner block, the iterations that are allocated to same processor also form a vector space, . The vector space is called the localized vector space in [37], where is used to represent tile iterations that have cache locality. In our model the localized vector space contains all dimensions of the iteration space that are local to a processor, be they completely local or blocked. Thus . Any dimension of the iteration space that is in is blocked. Only the iterations within a finite block are allocated to the same processor, not the entire dimension. The blocks themselves are then distributed across the processors.

Similarly, we define a vector space to characterize the array dimensions within a block that are allocated to the same processor. The relationship between the data partition and space is .

In the ADI example, the blocked computation partitions are and . Similarly, the blocked data partition is and .

Our algorithm finds the computation and data partitions and ; these spaces correspond to those dimensions that must be entirely mapped onto the same processor. If blocking is desired, the algorithm also finds and ; the iterations in , and the data in are distributed, but must be blocked.



next up previous
Next: Calculating Blocked Decompositions Up: Blocked Decompositions Previous: Blocked Decompositions



Jennifer-Ann M. Anderson
Fri Apr 7 14:39:58 PDT 1995