標題: Optimal processor mapping for linear-complement communication on hypercubes
作者: Hou, Y
Wang, CM
Ku, CY
Hsu, LH
資訊工程學系
Department of Computer Science
關鍵字: hypercubes;linear-complement communication;channel contention;processor mapping;wormhole routing
公開日期: 1-五月-2001
摘要: In this paper, we address the problem of minimizing channel contention of linear-complement communication on wormhole-routed hypercubes. Our research reveals that, for traditional routing algorithms, the degree of channel contention of a linear-complement communication can be quite large. To solve this problem, we propose an alternative approach, which applies processor reordering mapping at compile time. in this compiler approach, processors are logically reordered according to the given communication(s) so that the new communication(s) can be efficiently realized on the hypercube network. It is proved that, for any linear-complement communication, there exists a reordering mapping such that the new communication has minimum channel contention. An O(n(3)) algorithm is proposed to find such a mapping for an n-dimensional hypercube. An algorithm based on dynamic programming is also proposed to find an optimal reordering mapping for a set of linear-complement communications. Several computer simulations have been conducted and the results clearly show the advantage of the proposed approach.
URI: http://dx.doi.org/10.1109/71.926171
http://hdl.handle.net/11536/29701
ISSN: 1045-9219
DOI: 10.1109/71.926171
期刊: IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
Volume: 12
Issue: 5
起始頁: 514
結束頁: 527
顯示於類別:期刊論文


文件中的檔案:

  1. 000168690400006.pdf