標題: An approach to checking link conflicts in the mapping of uniform dependence algorithms into lower dimensional processor arrays
作者: Ke, JY
Tsay, JC
資訊工程學系
Department of Computer Science
關鍵字: uniform dependence algorithms;lower dimensional arrays;space-time mapping;link conflict;mixed integer linear programming;Hermite normal form;Smith normal form
公開日期: 1-Jul-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-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.
URI: http://dx.doi.org/10.1109/12.780880
http://hdl.handle.net/11536/31261
ISSN: 0018-9340
DOI: 10.1109/12.780880
期刊: IEEE TRANSACTIONS ON COMPUTERS
Volume: 48
Issue: 7
起始頁: 732
結束頁: 737
Appears in Collections:Articles


Files in This Item:

  1. 000081670400006.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.