Efficient local memory sequence generation for data parallel programs using permutations

• Published in: Journal of systems architecture 2001-06, Vol.47 (6), p.505-515
• Main Authors: Huang, Tsung-Chuan, Shiu, Liang-Cheng, Huang, Jui-Hsiang
• Format: Article
• Language: English
• Subjects: Applied sciences; Block compression/decompression; Block-cyclic distribution; Computer science; control theory; systems; Data compression; Data-parallel programming; Distributed shared memory; Exact sciences and technology; Integer programming; Local memory access sequence; Memory and file management (including protection and security); Memory organisation. Data processing; Parallel processing; Permutation; Software; Studies; Systems design
• ISSN: 1383-7621; 1873-6165
• DOI: 10.1016/S1383-7621(01)00012-1

Generating local memory access sequence is a critical issue in distributed-memory implementations of data-parallel languages. In this paper, for arrays distributed block-cyclically on multiple processors, we introduce a novel approach to the local memory access sequence generation using the theory of permutation. By compressing the active elements in a block into an integer, called compress number, and exploiting the fact that there is a repeating pattern in the access sequence, we obtain the global block cycle. Then, we show that the local block cycle can be efficiently enumerated as closed forms using the permutation of global block cycle. After decompressing the compress number in the local block cycle, the local block patterns are restored and the local memory access sequence can be quickly generated. Unlike other works, our approach incurs no run-time overhead.