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

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 ⁴+p ⁶). Our algorithm has been implemented in C++ programming language and its performance is evaluated through extensive testing.