摘要
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月 1996 → 13 6月 1996 |
Conference
Conference | Proceedings of the 1996 IEEE 2nd International Conference on Algorithms & Architectures for Parallel Processing, ICA 3PP |
---|---|
城市 | Singapore, Singapore |
期間 | 11/06/96 → 13/06/96 |