Mapping Non-trivial Network Topologies Onto Chips
- 1 September 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 73-78
Abstract
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.Keywords
This publication has 20 references indexed in Scilit:
- Quadratic Assignment Problem2009
- A survey for the quadratic assignment problemEuropean Journal of Operational Research, 2007
- Microarchitecture of a High-Radix Router2005
- Communication and task scheduling of application-specific networks-on-chipIEE Proceedings - Computers and Digital Techniques, 2005
- Trends toward on-chip networked microsystemsInternational Journal of High Performance Computing and Networking, 2005
- A methodology for designing efficient on-chip interconnects on well-behaved communication patterns2003
- Route packets, net wires2001
- Algorithm 769ACM Transactions on Mathematical Software, 1997
- Robust taboo search for the quadratic assignment problemParallel Computing, 1991
- P-Complete Approximation ProblemsJournal of the ACM, 1976