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
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.