An approach to checking link conflicts in the mapping of uniform dependence algorithms into lower dimensional processor arrays
檔案
- 000081670400006.pdf (253.7 KB, Adobe PDF)
日期
1999-07-01
類型
系所
期刊名稱
IEEE TRANSACTIONS ON COMPUTERS
卷期與頁次
第 48 卷第 7 期,頁 732–737
ISSN
0018-9340
語言
英文
摘要
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.
關鍵詞
uniform dependence algorithmslower dimensional arraysspace-time mappinglink conflictmixed integer linear programmingHermite normal formSmith normal form所屬典藏
期刊論文引用此條目
Ke, J., & Tsay, J. (1999). An approach to checking link conflicts in the mapping of uniform dependence algorithms into lower dimensional processor arrays. IEEE TRANSACTIONS ON COMPUTERS, 48(7), 732–737. https://doi.org/10.1109/12.780880
引用文字依 APA 第 7 版格式自動產生,使用前請再核對。
分享
永久網址:https://ir.lib.nycu.edu.tw/handle/11536/31261