An approach to checking link conflicts in the mapping of uniform dependence algorithms into lower dimensional processor arrays

檔案

日期

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.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

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

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/31261