標題: DESIGN OF SPACE-OPTIMAL REGULAR ARRAYS FOR ALGORITHMS WITH LINEAR SCHEDULES
作者: TSAY, JC
CHANG, PY
交大名義發表
工學院
National Chiao Tung University
College of Engineering
關鍵字: ALGORITHM MAPPING;DATA DEPENDENCY;LINEAR SCHEDULE;MATRIX MULTIPLICATION;OPTIMIZING COMPILER;SPACE-OPTIMAL;SYSTOLIC ARRAY
公開日期: 1-五月-1995
摘要: The problem of designing space-optimal 2D regular arrays for N x N x N cubical mesh algorithms with linear schedule ai + bj + ck, 1 less than or equal to a less than or equal to b less than or equal to c, and N = nc, is studied. Three novel nonlinear processor allocation methods, each of which works by combining a partitioning technique (gcd-partition) with different nonlinear processor allocation procedures (traces), are proposed to handle different cases, In cases where a + b less than or equal to c, which are dealt with by the first processor allocation method, space-optimal designs can always be obtained in which the number of processing elements is equal to N-2/c. For other cases where a + b > c and either a = b and b = c, two other optimal processor allocation methods are proposed. Besides, the closed form expressions for the optimal number of processing elements are derived for these cases.
URI: http://dx.doi.org/10.1109/12.381953
http://hdl.handle.net/11536/1958
ISSN: 0018-9340
DOI: 10.1109/12.381953
期刊: IEEE TRANSACTIONS ON COMPUTERS
Volume: 44
Issue: 5
起始頁: 683
結束頁: 694
顯示於類別:期刊論文


文件中的檔案:

  1. A1995QX27100007.pdf