Mapping Non-trivial Network Topologies Onto Chips

Adopting high-degree topologies is a promising way to reduce end-to-end latency in a network-on-chip (NoC). However, some high-degree topologies are not used in practice due to their complex layout on a chip. In this work we explore the way to systematically obtain the quasi-optimal mapping of those topologies onto a chip by modelizing the mapping problem as a quadratic assignment problem. Results show that the Robust Tabu Search algorithm achieves the mappings with the shortest link length for most topologies of up to 512 cores. The link length is reduced by up to 51% when compared to naive baseline method. We also tackle even larger topologies by means of clustering, and a promising results are obtained to apply those algorithms for topologies of 2,048 or more cores with a modest penalty on the link length.