Communication-Cost-Aware Task-to-Core Mapping for 2D Concentrated-Mesh NoC-Based Neural Network Accelerators

Abstract

Task placement strongly affects the on-chip communication overhead of Network-on-Chip (NoC)-based deep-neural network (DNN) accelerators. This work addresses task-to-core mapping on two-dimensional (2D) Concentrated Mesh (CMesh) NoCs with the explicit objective of minimizing communication cost, defined as the traffic-weighted number of inter-router hops. We formulate the problem as a quadratic assignment problem (QAP) over a weighted communication task graph and the core-to-core hop-distance matrix of the target CMesh. We first establish an exact reference by encoding the QAP as a binary mixed-integer quadratic program (MIQP). We then propose two scalable alternatives: (i) a constructive heuristic that forms router-sized, communication-dense task islands, assigns the islands to routers through a reduced QAP, and refines the mapping by local search; and (ii) an Iterated Tabu Search (ITS) that combines randomized tabu tenure, aspiration, incumbent-based perturbation, and parallel independent chains. Across 14 digital signal processing and neural network benchmarks, ITS obtains the same results as MIQP on 13 instances and is only 1.6% above the certified optimum for the remaining instance. Among the 12 instances for which the MIQP solution proves optimality, ITS reaches the optimum on 11; on the two instances that reach the eight-hour limit, ITS matches the best MIQP solution incumbent. The constructive heuristic produces mappings in 0.008-2.561 ms and matches the best objective of the MIQP solution on five of seven neural network workloads. These results show that the proposed methods can obtain high-quality CMesh mappings at a design-time cost substantially lower than exact mathematical optimization.