Efficient Address Generation for Affine Subscripts in Data-Parallel Programs
學年 89
學期 1
出版（發表）日期 2000-09-01
作品名稱 Efficient Address Generation for Affine Subscripts in Data-Parallel Programs
作品名稱（其他語言）
著者 Shih, Kuei-ping; 石貴平; Sheu, Jang-ping; Chang, Chih-yung
單位 淡江大學資訊工程學系
出版者
著錄名稱、卷期、頁數 The Journal of Supercomputing 17(2), pp.205-227
摘要 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).
關鍵字 address generation;affine subscripts;data distribution;distributed-memory;multicomputers;data-parallel languages;multiple induction variables (MIVs);single program multiple data (SPMD)
語言 en
ISSN
期刊性質 國內
收錄於
產學合作
通訊作者
審稿制度 否
國別 TWN
公開徵稿
出版型式 ,電子版
相關連結

機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/59898 )

機構典藏連結