Energy-Efficient Mapping for 3D NoC Using Logistic Function Based Adaptive Genetic Algorithms

WANG Jiawen; LI Li; WANG Zhongfeng; ZHANG Rong; ZHANG Yuang

Article Contents

Article Navigation > Chinese Journal of Electronics > 2014 > 23(2): 254-262

WANG Jiawen, LI Li, WANG Zhongfeng, et al., “Energy-Efficient Mapping for 3D NoC Using Logistic Function Based Adaptive Genetic Algorithms,” Chinese Journal of Electronics, vol. 23, no. 2, pp. 254-262, 2014,

Citation:

WANG Jiawen, LI Li, WANG Zhongfeng, et al., “Energy-Efficient Mapping for 3D NoC Using Logistic Function Based Adaptive Genetic Algorithms,” Chinese Journal of Electronics, vol. 23, no. 2, pp. 254-262, 2014,

Citation:

PDF( 985 KB)

Energy-Efficient Mapping for 3D NoC Using Logistic Function Based Adaptive Genetic Algorithms

Institute of VLSI Design, LAPEM, Nanjing University, Nanjing 210093, China

Funds: This work is supported in part by the National Nature Science Foundation of China (No.61176024, No.61006018), Research Fund for the Doctoral Program of Higher Education of China (No.20120091110029), A Project Funded by the Priority academic program development (PAPD) of Jiangsu Higher Education Institutions.

Received Date: 2012-01-01
Rev Recd Date: 2013-05-01
Publish Date: 2014-04-05

Abstract

Abstract

The problem of mapping application tasks is one of key issues in 3D Network on chip (3D NoC) design. A novel Logistic function based adaptive genetic algorithm (LFAGA) is proposed for energy-aware mapping of homogeneous 3D NoC. We formulate the mapping problem and show the Standard genetic algorithm (SGA). The LFAGA is presented in detail with the goal of obtaining higher convergence speed while preventing the premature convergence. Experimental results indicate that the proposed LFAGA is more efficient than previously proposed Chaos-genetic mapping algorithm (CGMAP). In the experiments, a randomly generated task graph of size 27 is mapped to a 3D NoC of size 3×3×3, the convergence speed of LFAGA is 2.55 times faster than CGMAP in the best condition. When the task size increases to 64 and the 3D NoC size extends to 4×4×4, LFAGA is 2.31 times faster compared to CGMAP. For the NoC sizes in the range from 3×3×2 to 4×4×4, solutions obtained by the LFAGA are consistently better than the CGMAP. For example, in the experiment of size 4×4×4, the improvement of final result reaches 30.0% in term of energy consumption. For a real application of size 3×4×2, 18.6% of energy saving can be achieved and the convergence speed is 1.58 times faster than that of the CGMAP.
- Energy-awaremapping,
- 3D NoC,
- Logisitc function,
- Adaptive genetic algorithm,
- Convergence speed

FullText(HTML)

References(26)

References

L. Benini and G. De Micheli, "Networks on chips: A new SoC paradigm", IEEE Computer, Vol.35, No.1, pp.70-78, 2002.

GE Fen and WU Ning, "Genetic algorithm based mapping and routing approach for network on chip architectures", Chinese Journal of Electronics, Vol.19, No.1, pp.91-96, 2010.

A.W. Topol, et al., "Three-dimensional integrated circuits", IBM J. Research and Development, Vol.50, No.4/5, 2006.

B. S. Feero and P. P. Pande, "Networks-on-chip in a threedimensional environment: A performance evaluation", IEEE Transactions on Computers, Vol.58, No.1, pp.32-45, 2009.

Radu Marculescu, Umit Y.Ogras, Li-Shiuan Peh, et al., "Outstanding reasearch problems in NoC design: System, microarchitecture, and circuit perspectives", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol.28, No.1, pp.3-21, 2009.

E. Carvalho, C. Marcon, N. Calazans, et al., "Evaluation of static and dynamic task mapping algorithms in NoC-based MPSoCs, system-on-chip", International Symposium on SOC, Tampere, Finland, pp.87-90, 2009.

Ewerson Luiz de Souza Carvalho, Ney Laert Vilar Calazans and Fernando Gehm Moraes, "Dynamic task mapping for MPSoCs", Design & Test of Computers, IEEE, Vol.27, No.5, pp.26-35, 2010.

Mandelli, Marcelo, Ost, Luciano and Carara, Everton, et al., "Energy-aware dynamic task mapping for NoC-based MPSoCs", IEEE International Symposium on Circuits and Systems, Rio De Janeiro, Brazil, pp.1676-1679, 2011.

J. Hu and R. Marculescu, "Energy-aware mapping for tilebased NOC architectures under performance constraints", Asia South Pacific Design Automic Conference, Kitakyushu, Japan, pp.233-239, 2003.

Srinivasan Murali and Giovanni De Micheli, "Bandwidthconstrained mapping of cores onto NoC architectures", Design, Automation and Test in Europe Conference and Exhibition Volume II, Paris, France, Vol.2, pp.896-901, 2004.

A. Hansson, K. Goossens, and A. Radulescu, "A unified approach to mapping and routing on a network-on-chip for both best-effort and guaranteed service traffic", Hindawi VLSI Design, Vol.2007, 2007.

C.A.M. Marcon, E.I. Moreno, N.L.V. Calazans, and F.G. Moraes, "Comparison of network-on-chip mapping algorithms targeting low energy consumption", Computers & Digital Techniques, IET, Vol.2, No.6, pp.471-482, 2008.

Tang Lei, Shashi Kumar, "A two-step genetic algorithm for mapping task graphs to a network on chip architecture", Euromicro Symposium on Digital Systems Design, Warsaw, Poland, pp.180, 2003.

Fahime Moein-darbari, Ahmad Khademzade and Golnar Gharooni-fard, "CGMAP: A new approach to Network-on-chip mapping problem", IEICE Electronics Express, Vol.6, No.1, pp.27-34, 2009.

F.Ge andW.Ning, "Genetic algorithm based mapping and routing approach for Network on chip architectures", Chinese Journal of Electronics, Vol.19, No.1, pp.91-96, 2010.

G. Ascia, V. Catania, and M. Palesi, "Multi-objective mapping for meshbased NoC architectures", 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, Stockholm, Sweden, pp.182-187, 2004.

Wenbiao Zhou, Yan Zhang and Zhigang Mao, "Pareto based Multi-objective mapping IP cores onto NoC architectures", IEEE Asia Pacific Conference on Circuits and Systems, Singapore, pp.331-334, 2006.

A.A. Morgan, H. Elmiligi, M.W. El-Kharashi, and F. Gebali, "Multi-objective optimization of NoC standard architectures using genetic algorithms", IEEE International Symposium on Signal Processing and Information Technology, Luxor, Egypt, pp.85-90, 2010.

C. Addo-Quaye, "Thermal-aware mapping and placement for 3-D NoC designs", IEEE International SOC Conference, Herndon, USA, pp.25-28, 2005.

K. Skadron, T. Abdelzaher, and M. Stan, "Control-theoretic techniques and Thermal-RC modeling for accurate and localized dynamic thermal management", Eighth International Symposium on High-Performance Computer Architecture, Cambridge, USA, pp.17-28, 2002.

T. T. Ye, L. Benini, and G. De Micheli, "Analysis of power consumption on switch fabrics in network routers", Design Automation Conference, Paris, France, pp.524-529, 2002.

M. Srinivas and L.M. Patnaik, "Adaptive probabilities of crossover and mutation in genetic algorithms", IEEE Transactions on Systems, Man and Cybernetics, Vol.24, No.4, pp.656-667, 1994.

Wein-Tsung Shen, Chih-Hao Chao, Yu-Kuang Lien and An-Yeu (Andy) Wu, "A new binomial mapping and optimization algorithm for reduced-complexity mesh-based on-Chip network", First International Symposium on Networks-on-Chip, Princeton, USA, pp.317-322, 2007.

J.J. Grefenstette, "Optimization of control parameters for genetic algorithms", IEEE Transactions on Systems, Man and Cybernetics, Vol.16, No.1, pp.122-128, 1986.

Keith Vallerio, Task graphs for free (TGFF v3.0), 2008, Available: http://ziyang.eecs.umich.edu/～dickrp/tgff/.

Khalid Latif, Arir-Mohammad Rahmani and Tiberiu Seceleanu, et al., "Power-and Performance-aware IP mapping for NoCbased MPSoC platforms", 17th IEEE International Conference on Electronics, Circuits, and Systems, Athens, Greece, pp.758-761, 2010.

Relative Articles

Supplements(0)

Cited By

Proportional views