Performance-Aware Hybrid Algorithm for Mapping IPs onto Mesh-Based Network on Chip

Guang SUN  Shijun LIN  Depeng JIN  Yong LI  Li SU  Yuanyuan ZHANG  Lieguang ZENG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E94-D   No.5   pp.1000-1007
Publication Date: 2011/05/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E94.D.1000
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer System
Keyword: 
mapping algorithm,  network on chip,  energy consumption,  latency,  bandwidth,  

Full Text: PDF>>
Buy this Article




Summary: 
Network on Chip (NoC) is proposed as a new intra-chip communication infrastructure. In current NoC design, one related problem is mapping IP cores onto NoC architectures. In this paper, we propose a performance-aware hybrid algorithm (PHA) for mesh-based NoC to optimize performance indexes such as latency, energy consumption and maximal link bandwidth. The PHA is a hybrid algorithm, which integrates the advantages of Greedy Algorithm, Genetic Algorithm and Simulated Annealing Algorithm. In the PHA, there are three features. First, it generates a fine initial population efficiently in a greedy swap way. Second, effective global parallel search is implemented by genetic operations such as crossover and mutation, which are implemented with adaptive probabilities according to the diversity of population. Third, probabilistic acceptance of a worse solution using simulated annealing method greatly improves the performance of local search. Compared with several previous mapping algorithms such as MOGA and TGA, simulation results show that our algorithm enhances the performance by 30.7%, 23.1% and 25.2% in energy consumption, latency and maximal link bandwidth respectively. Moreover, simulation results demonstrate that our PHA approach has the highest convergence speed among the three algorithms. These results show that our proposed mapping algorithm is more effective and efficient.