Browsing by Author "Ke, JY"

Now showing 1 - 2 of 2

An approach to checking link conflicts in the mapping of uniform dependence algorithms into lower dimensional processor arrays
(1999-07-01)
Ke, JY
;
Tsay, JC
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose an enumeration method to check link conflicts in the mapping of n-dimensional uniform dependence algorithms with arbitrary convex index sets into k-dimensianal processor arrays. Previous methods on checking the link conflicts had to examine either the whole index set or the I/O spaces whose size are O(N-2n) or O(Nn-1), respectively, where hr is the problem size of the n-dimensional uniform dependence algorithm. In our approach, checking the link conflicts is done by enumerating integer solutions of a mixed integer linear program. In order to enumerate integer solutions efficiently, a representation of the integer solutions is devised so that the size of the space enumerated is O((2N)(n-k)). Thus, our approach to checking link conflicts has better performance than previous methods, especially for larger k. For the special case k = n - 2, we show that link conflicts can he checked by solving two linear programs in one variable.
Finding space-optimal linear array for uniform dependence algorithms with arbitrary convex index sets
(1998-12-01)
Ke, JY
;
Tsay, JC
;
資訊工程學系
;
Department of Computer Science
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.