Congestion- and energy-aware run-time mapping for tile-based network-on-chip architecture

The mapping of application tasks to processing elements (PE) connected by a network-on-chip (NoC) has a significant impact on the overall performance and power consumption of the applications. In this work, a novel dynamic task mapping algorithm is proposed to reduce the overall latency and power consumption of a given set of applications. Applications are modeled by task graphs. Each task graph represents a application and is composed of several tasks. A task is mapped as close to its parent task as possible, based on a candidate spiral search (CSS) method for candidate PEs. The CSS starts to search an empty PE for mapping the requested task with the Manhattan distance between the requested task and its parent task is equal to one. If there is not any candidate available, the Manhattan distance is increased by one until an empty PE is found. Further, the aggregate communication load (ACL) of each candidate PE is also monitored. A task is primarily mapped to a candidate PE which is in the candidate set found by CSS with the minimal ACL. The proposed Rotating Mapping Algorithm (RMA) thus employs CSS to reduce communication latency and ACL to achieve load balancing, which implies lower power consumption. Experiments demonstrate the feasibility and benefits of the proposed method compared with some state-of-the-art task mapping techniques. The Proposed algorithm at most reduces 42.73% in the total energy consumption and 29.32% in the global average delay.