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

Journal of Inforamtion Science and Engineering, Vol.14 No.4, pp.743-763 (December 1998)
Finding Space-Optimal Linear Array for
Uniform Dependence Algorithms with Arbitrary
Convex Index Sets*

Jenn-Yang Ke and Jong-Chuang Tsay
Department of Computer Science and Information engineering
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

Full Text () 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.