Designing Lower-Dimensional Regular Arrays for Algorithms with Uniform Dependencies
✍ Scribed by Jong-Chuang Tsay; Pen-Yuang Chang
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 360 KB
- Volume
- 33
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
In this paper, we will propose a polynomial-time method to design m-dimensional regular arrays for n (n Ն 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.