[Previous | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] |

Finding Space-Optimal Linear Array for

Uniform Dependence Algorithms with Arbitrary

Convex Index Sets

**Jenn-Yang Ke and Jong-Chuang Tsay**

National Chiao Tung University

Hsinchu, Taiwan 300, R.O.C.

The mapping of an *n*-dimensional uniform dependence algorithm onto a linear processor array can be considered as a linear transformation problem. However, to find a linear space-optimal transformation is difficult because the conditions for checking a correct mapping and the space cost function do not have closed-form expressions, especially when the index set *J* of an *n*-dimensional algorithm is of an arbitrary bounded convex index set. In this paper, we propose an enumeration method to find a space-optimal PE allocation vector for mapping an *n*-dimensional uniform dependence algorithm with an arbitrary bounded convex index set onto a linear processor array, assuming that a linear schedule is given a priori.

Keywords: uniform dependence algorithms, linear schedule, allocation vector, norm, space optimal

Retrieve PDF document (**199812_03.pdf** : 128,535 bytes)

Received October 4, 1996; accepted May 3, 1997.

Communicated by Jang-Ping Sheu.
^{*} This research was supported in part by the National Science Council of the Republic of China under Grant No. NSC86-2213-E-009-017.