Pareto optimal mapping for tile-based network-on-chip under reliability constraints

Abstract

Mapping for network-on-chip (NoC) is one of the key steps of NoC design. To improve the performance and reliability of NoC architectures, we present a comprehensive optimization algorithm with multiple objectives. We propose to find the Pareto optimal solutions, rather than a single solution usually obtained through scalarization, e.g. weighting the objective functions. In order to meet the NoC mapping requests and strengthen the capability of searching solutions, the standard particle swarm optimization (PSO) algorithm is improved and a fault-tolerant routing is proposed. These methods help to solve the tradeoff between high performance and system reliability. We present a mathematical analysis of the convergence of the improved algorithms, and prove sufficient conditions of convergence. The improved algorithms are implemented on the Embedded Systems Synthesis Benchmarks Suite (E3S). Experimental results show our algorithms achieve high performance and reliability compared with the standard PSO.

Keywords:

• optimization algorithm
• network-on-chip
• mapping
• particle swarm optimization
• reliability

2010 AMS Subject Classifications::

• 68W20
• 68W35
• 68T20
• 68W40

Acknowledgements

We are grateful to the National Natural Science Foundation of China (grant number 60973016, 61272175), the National Basic Research Program of China 973 Program (grant number 2010CB328004), the Youth Backbone Teacher Foundation of Chengdu University of Technology (grant number JXGG201305) and the Bagui scholarship project for their continuous supports.