Full metadata record
DC FieldValueLanguage
dc.contributor.authorKe, JYen_US
dc.contributor.authorTsay, JCen_US
dc.date.accessioned2014-12-08T15:46:26Z-
dc.date.available2014-12-08T15:46:26Z-
dc.date.issued1999-07-01en_US
dc.identifier.issn0018-9340en_US
dc.identifier.urihttp://dx.doi.org/10.1109/12.780880en_US
dc.identifier.urihttp://hdl.handle.net/11536/31261-
dc.description.abstractIn 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.en_US
dc.language.isoen_USen_US
dc.subjectuniform dependence algorithmsen_US
dc.subjectlower dimensional arraysen_US
dc.subjectspace-time mappingen_US
dc.subjectlink conflicten_US
dc.subjectmixed integer linear programmingen_US
dc.subjectHermite normal formen_US
dc.subjectSmith normal formen_US
dc.titleAn approach to checking link conflicts in the mapping of uniform dependence algorithms into lower dimensional processor arraysen_US
dc.typeArticleen_US
dc.identifier.doi10.1109/12.780880en_US
dc.identifier.journalIEEE TRANSACTIONS ON COMPUTERSen_US
dc.citation.volume48en_US
dc.citation.issue7en_US
dc.citation.spage732en_US
dc.citation.epage737en_US
dc.contributor.department資訊工程學系zh_TW
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.identifier.wosnumberWOS:000081670400006-
dc.citation.woscount0-
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.