Efficient local memory sequence generation for data parallel programs using permutations

Generating local memory access sequence is a critical issue in distributed- memory implementations of data-parallel languages. In this paper, for array s distributed block-cyclically on multiple processors, we introduce a novel approach to the local memory access sequence generation using the theory o f permutation. By compressing the active elements in a block into an intege r, called compress number, and exploiting the fact that there is a repeatin g pattern in the access sequence, we obtain the global block cycle, Then, w e show that the local block cycle can be efficiently enumerated as closed f orms using the permutation of global block cycle. After decompressing the c ompress number in the local block cycle, the local block patterns are resto red and the local memory access sequence can be quickly generated. Unlike o ther works, our approach incurs no run-time overhead. (C) 2001 Elsevier Sci ence B.V. All rights reserved.