Compiling array references with affine functions for data-parallel programs

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > journal & Dissertation > Item 987654321/29171

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/29171

Title:	Compiling array references with affine functions for data-parallel programs
Authors:	Wei,WH;Shih,KP;Sheu,JP
Contributors:	資訊工程研究所
Keywords:	COMMUNICATION
Date:	1998
Issue Date:	2010-06-29 20:15:26 (UTC+8)
Publisher:	中央大學
Abstract:	An important research topic is parallelizing of compilers to generate local memory access sequences and communication sets while compiling a data-parallel language into an SPMD (Single Program Multiple Data) program. In this paper, we present a scheme to efficiently enumerate local memory access sequences and to evaluate communication sets. We use a class table to store information that is extracted from array sections and data distribution patterns. Given array references and data distributions, we can utilize the class table to generate communication sets in closed forms. Furthermore, we derive the algorithms for sending and receiving necessary data between processors. An algorithm for generating the class table is presented, and the time complexity of this algorithm is O(s), where s is the array section stride. The technique of generating communication sets for one index variable has been implemented on a DEC Alpha 3000 workstation. The experimental results confirm the advantage of our scheme, especially when the array section stride is larger than the block size. Finally, we adapt our approach to handle array references with multiple index variables. The time complexity for constructing the whole class table is O(s(2)).
Relation:	JOURNAL OF INFORMATION SCIENCE AND ENGINEERING
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] journal & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	503	View/Open

社群 sharing

Loading...