Mapping parallel programs onto hypercube computers to minimize link-contention degree

Leung Chan Kwok, Hong Shen

研究成果: Paper同行評審

摘要

Mapping parallel programs onto multiprocessor computers is one of the most significant research topics in parallel processing. A program can be partitioned into communicating tasks. The allocation of the communicating tasks to processors is called process-to-processor mapping (mapping). Communicating tasks should be allocated in a way to balance the computation load and to minimize the communication load. Link-contention degree increases the communication cost due to communication congestion caused by multiple communicating processes sharing the same communication link, therefore should be minimized. This paper proposes a new mapping algorithm for hypercube computers which aims at minimizing the link-contention degree at every processor to below a certain (preset) level. For mapping an arbitrary task graph onto a hypercube computer, the algorithm has a worst-case time complexity O(n 4+p 6). Our algorithm has been implemented in C++ programming language and its performance is evaluated through extensive testing.

原文English
頁面44-52
頁數9
出版狀態Published - 1996
對外發佈
事件Proceedings of the 1996 IEEE 2nd International Conference on Algorithms & Architectures for Parallel Processing, ICA 3PP - Singapore, Singapore
持續時間: 11 6月 199613 6月 1996

Conference

ConferenceProceedings of the 1996 IEEE 2nd International Conference on Algorithms & Architectures for Parallel Processing, ICA 3PP
城市Singapore, Singapore
期間11/06/9613/06/96

指紋

深入研究「Mapping parallel programs onto hypercube computers to minimize link-contention degree」主題。共同形成了獨特的指紋。

引用此