An approach to checking link conflicts in the mapping of uniform dependence algorithms into lower dimensional processor arrays
Jenn-Yang Ke, Jong-Chuang Tsay · IEEE Transactions on Computers · 1999
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-dimensional 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/sup 2n/) or O(N/sup n-1/), respectively, where N 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)/sup 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 be checked by solving two linear programs in one variable.