Application-specific topology generation algorithms for network-on-chip design

Tosun S., Ar Y., Ozdemir S.

IET COMPUTERS AND DIGITAL TECHNIQUES, vol.6, no.5, pp.318-333, 2012 (SCI-Expanded) identifier identifier


Network-on-chip (NoC) is an alternative approach to traditional communication methods for system-on-chip architectures. Irregular topologies are preferable for the application specific NoC designs as they offer huge optimisation space in contrast to their regular counterparts. Generating an application-specific topology as part of the synthesis flow of a NoC architecture is a challenging problem as there may be several topology alternatives, each of which may be superior to the others based on the different objective criteria. In this study, the authors tackle at this problem and propose a heuristic and a genetic algorithm-based methods. The heuristic method, called TopGen, is a two-phase application-specific topology generation algorithm aiming to minimise the energy consumption of the system. TopGen first decomposes the given application into clusters based on the communication traffic. It then maps the clusters onto the routers and connects them in such a way that the communication cost of the network is minimised. The second algorithm, called GA-based topology generation algorithm-based topology generation algorithm (GATGA), is based on a genetic algorithm, which initially creates a set of solutions and uses genetic operators to reproduce new topologies from them. The authors compared our algorithms with existing methods through several multimedia benchmarks and custom generated graphs. TopGen and GATGA obtained better results than previous methods with negligible area and link length overheads.