Efficient Address Generation for Affine Subscripts in Data-Parallel Programs

doi:10.1023/A:1008190606079

淡江大學機構典藏 > 工學院 > 資訊工程學系暨研究所 > 期刊論文 > Item 987654321/59898

請使用永久網址來引用或連結此文件: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/59898

題名:	Efficient Address Generation for Affine Subscripts in Data-Parallel Programs
作者:	Shih, Kuei-ping;石貴平;Sheu, Jang-ping;Chang, Chih-yung
貢獻者:	淡江大學資訊工程學系
關鍵詞:	address generation;affine subscripts;data distribution;distributed-memory;multicomputers;data-parallel languages;multiple induction variables (MIVs);single program multiple data (SPMD)
日期:	2000-09-01
上傳時間:	2011-10-05 22:25:05 (UTC+8)
摘要:	Address generation for compiling programs, written in HPF, to executable SPMD code is an important and necessary phase in a parallelizing compiler. This paper presents an efficient compilation technique to generate the local memory access sequences for block-cyclically distributed array references with affine subscripts in data-parallel programs. For the memory accesses of an array reference with affine subscript within a two-nested loop, there exist repetitive patterns both at the outer and inner loops. We use tables to record the memory accesses of repetitive patterns. According to these tables, a new start-computation algorithm is proposed to compute the starting elements on a processor for each outer loop iteration. The complexities of the table constructions are O(k+s2), where k is the distribution block size and s2 is the access stride for the inner loop. After tables are constructed, generating each starting element for each outer loop iteration can run in O(1) time. Moreover, we also show that the repetitive iterations for outer loop are Pk/gcd(Pk, s1), where P is the number of processors and s1 is the access stride for the outer loop. Therefore, the total complexity to generate the local memory access sequences for a block-cyclically distributed array with affine subscript in a two-nested loop is O(Pk/gcd(Pk, s1)+k+s2).
關聯:	The Journal of Supercomputing 17(2), pp.205-227
DOI:	10.1023/A:1008190606079
顯示於類別:	[資訊工程學系暨研究所] 期刊論文

文件中的檔案:

沒有與此文件相關的檔案.

在機構典藏中所有的資料項目都受到原著作權保護.

TAIR相關文章

資料載入中.....