標題: Designing lower-dimensional regular arrays for algorithms with uniform dependencies
作者: Tsay, JC
Chang, PY
交大名義發表
工學院
National Chiao Tung University
College of Engineering
公開日期: 25-二月-1996
摘要: In this paper, we will propose a polynomial-time method to design m-dimensional regular arrays for n (n greater than or equal to m + 1) dimensional algorithms with uniform dependencies, regular algorithms. The proposed method has two steps: the first one is to transform an independently partitioned regular algorithm to a new one, which has an identity dependence matrix. We call this step identity transformation, which is an affine one. In the second step, we propose a spacetime mapping in a fixed form to map the new regular algorithm to a lower-dimensional regular array. Thus, an affine spacetime mapping is constructed by combining the identity transformation and the fixed form's spacetime mapping together. With the proposed affine spacetime mapping, the original regular algorithm can be mapped to a lower-dimensional regular array in polynomial time, which depends only on the number of dimensions of the regular algorithm. Meanwhile, the designed regular array is asymptotically optimal in time and space. (C) 1996 Academic Press, Inc.
URI: http://dx.doi.org/10.1006/jpdc.1996.0021
http://hdl.handle.net/11536/1444
ISSN: 0743-7315
DOI: 10.1006/jpdc.1996.0021
期刊: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
Volume: 33
Issue: 1
起始頁: 24
結束頁: 32
顯示於類別:期刊論文


文件中的檔案:

  1. A1996UB20800003.pdf