CoNA: Dynamic Application Mapping for Congestion Reduction in Many-Core Systems

Abstract—Increasing the number of processors in a single chip toward network-based many-core systems requires a run-time task allocation algorithm. We propose an efficient mapping algorithm that assigns communicating tasks of incoming applications onto resources of a many-core system utilizing Network-on-Chip paradigm. In our contiguous neighborhood allocation (CoNA) algorithm, we target at the reduction of both internal and external congestion due to detrimental impact of congestion on the network performance. We approach the goal by keeping the mapped region contiguous and placing the communicating tasks in a close neighborhood. A completely synthesizable simulation environment where none of the system objects are assumed to be ideal is provided. Experiments show at least 40 % gain in different mapping cost functions, as well as 16 % reduction in average network latency compared to existing algorithms. Keywords-Network-on-Chip; MPSoC; run-time; dynamic; task mapping; processor allocation; congestion; contiguous; latency; performance I