JISE


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


Journal of Information Science and Engineering, Vol. 14 No. 4, pp. 743-763


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

  Retrieve PDF document (JISE_199804_03.pdf)