Efficient local memory sequence generation for data parallel programs using permutations

TFIR > Department of Electrical Engineering > journal > Item 987654321/675

Please use this identifier to cite or link to this item: http://163.15.40.127/ir/handle/987654321/675

Title:	Efficient local memory sequence generation for data parallel programs using permutations
Authors:	Huang, Tsung-Chuan;許良政;Shiu, Liang-Cheng;Huang, Jui-Hsiang;(東方工商專科學校電機工程科)
Contributors:	東方工商專科學校電機工程科
Keywords:	Block-cyclic distribution;Local memory access sequence;Data-parallel programming;Block compression/decompression;Permutation
Date:	2001-06
Issue Date:	2010-01-11 11:54:08 (UTC+8)
Abstract:	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.
Relation:	Journal of Systems Architecture, Volume 47, Issue 6, June 2001, Pages 505-515
Appears in Collections:	[Department of Electrical Engineering] journal

Files in This Item:

There are no files associated with this item.