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.