Performance-driven assignment and mapping for reliable networks-on-chips

Qian-qi LE; Guo-wu YANG; William N. N. HUNG; Xiao-yu SONG; Fu-you FAN

doi:10.1631/jzus.C1400055

Your Location：

Home >

Browse articles >

Performance-driven assignment and mapping for reliable networks-on-chips

Computer & Automation | Updated：2022-05-19

- Performance-driven assignment and mapping for reliable networks-on-chips
- 性能驱动的可靠片上网络分配和映射
- Frontiers of Information Technology & Electronic Engineering Vol. 15, Issue 11, Pages: 1009-1020(2014)
- Affiliations：
  
  1.School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China
  2.Department of Information and Computing Science, Chengdu University of Technology, Chengdu 610059, China
  3.Synopsys Inc., Mountain View, CA 94040, USA
  4.Department of Electronic and Computer Engineering, Portland State University, Portland, OR 97207-0751, USA)
- Author bio：
  
  [ "Qian-qi LE, E-mail: leqqi777@163.com" ]
- Funds：
- DOI：10.1631/jzus.C1400055
  CLC： TP202;TN402
- Received：19 February 2014，
  
  Revised：2014-10-22，
  
  Published：2014-11
- Accepted：
Scan QR Code
Qian-qi LE, Guo-wu YANG, William N. N. HUNG, et al. Performance-driven assignment and mapping for reliable networks-on-chips[J]. Frontiers of Information Technology & Electronic Engineering, 2014, 15(11): 1009-1020.
DOI：

Qian-qi LE, Guo-wu YANG, William N. N. HUNG, et al. Performance-driven assignment and mapping for reliable networks-on-chips[J]. Frontiers of Information Technology & Electronic Engineering, 2014, 15(11): 1009-1020. DOI： 10.1631/jzus.C1400055.

摘要

研究目的

以提高片上网络性能和可靠性为目标，提出片上网络设计中分配和映射这两个重要步骤的优化算法，提出自适应容错路由算法。

创新要点

根据片上网络分配和映射的需求和约束条件，设计了自适应容错路由算法以提高系统可靠性。分别设计了PSOGA、PSOSA和SS三个多目标优化算法，既能满足片上网络分配和映射的需求，又改善了传统智能算法易陷入局部最优的缺点，获得了更多高性能分配和映射方案。

研究方法

首先，根据片上网络分配和映射的需求，分别提出了性能和可靠性的多目标评价模型。接着，设计了自适应的容错路由算法兼顾了系统可靠性和性能。然后，根据片上网络分配和映射的特征，设计了PSOGA和PSOSA算法，融合粒子群、遗传算法和模拟退火算法等传统智能算法的优点，设计了多目标SS算法，实现了基于小种群的多目标优化。最后，将提出的算法用于E3S的典型测试用例，并且通过NIRGAM进行仿真。

重要结论

实验结果显示，本文算法获得的分配和映射方案在质量和数量上均优于传统智能算法。

Abstract

Network-on-chip (NoC) communication architectures present promising solutions for scalable communication requests in large system-on-chip (SoC) designs. Intellectual property (IP) core assignment and mapping are two key steps in NoC design

significantly affecting the quality of NoC systems. Both are NP-hard problems

so it is necessary to apply intelligent algorithms. In this paper

we propose improved intelligent algorithms for NoC assignment and mapping to overcome the drawbacks of traditional intelligent algorithms. The aim of our proposed algorithms is to minimize power consumption

time

area

and load balance. This work involves multiple conflicting objectives

so we combine multiple objective optimization with intelligent algorithms. In addition

we design a fault-tolerant routing algorithm and take account of reliability using comprehensive performance indices. The proposed algorithms were implemented on embedded system synthesis benchmarks suite (E3S). Experimental results show the improved algorithms achieve good performance in NoC designs

with high reliability.

关键词

Keywords

references

T. Bjerregaard , , , S. Mahadevan . . A survey of research and practices of network-on-chip . . ACM Comput. Surv. , , 2006 . . 38 ( ( 1 ): ): 1.1 - - 1.51 . . DOI: 10.1145/1132952.1132953 http://doi.org/10.1145/1132952.1132953 . .

A.L. Cheng , , , Y. Pan , , , X.L. Yan , , , 等 . . A general communication performance evaluation model based on routing path decomposition . . J. Zhejiang Univ.-Sci. C (Comput. & Electron.) , , 2011 . . 12 ( ( 7 ): ): 561 - - 573 . . DOI: 10.1631/jzus.C1000281 http://doi.org/10.1631/jzus.C1000281 . .

M.V.C. da Silva , , , N. Nedjah , , , L.M. Mourelle . . Power- aware multi-objective evolutionary optimisation for application mapping on network-on-chip platforms . . Int. J. Electron. , , 2010 . . 97 ( ( 10 ): ): 1163 - - 1179 . . DOI: 10.1080/00207217.2010.512105 http://doi.org/10.1080/00207217.2010.512105 . .

R. Das , , , S. Eachempati , , , A.K. Mishra , , , 等 . . Design and evaluation of a hierarchical on-chip interconnect for next-generation CMPs . . Proc. IEEE 15th Int. Symp. on High Performance Computer Architecture , , 2009 . . p.175 - - 186 . . DOI: 10.1109/HPCA.2009.4798252 http://doi.org/10.1109/HPCA.2009.4798252 . .

J. Hu , , , R. Marculescu . . Energy-aware mapping for tile- based NoC architectures under performance constraints . . Proc. Asia and South Pacific Design Automation Conf. , , 2003 . . p.233 - - 239 . . DOI: 10.1109/ASPDAC.2003.1195022 http://doi.org/10.1109/ASPDAC.2003.1195022 . .

W.N.N. Hung , , , X. Song . . BDD variable ordering by scatter search . . Proc. Int. Conf. on Computer Design , , 2001 . . p.368 - - 373 . . DOI: 10.1109/ICCD.2001.955053 http://doi.org/10.1109/ICCD.2001.955053 . .

R.K. Jena , , , G.K. Sharma . . A multi-objective evolutionary algorithm based optimization model for network-on-chip synthesis . . Proc. 4th Int. Conf. on Information Technology , , 2007 . . p.977 - - 982 . . DOI: 10.1109/ITNG.2007.10 http://doi.org/10.1109/ITNG.2007.10 . .

W. Liu , , , Z. Gu , , , J. Xu , , , 等 . . Satisfiability modulo graph theory for task mapping and scheduling on multiprocessor systems . . IEEE Trans. Parall. Distr. Syst. , , 2011 . . 22 ( ( 8 ): ): 1382 - - 1389 . . DOI: 10.1109/TPDS.2010.204 http://doi.org/10.1109/TPDS.2010.204 . .

R. Marculescu , , , U.Y. Ogras , , , L.S. Peh , , , 等 . . Outstanding research problems in NoC design: system, microarchitecture, and circuit perspectives . . IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. , , 2009 . . 28 ( ( 1 ): ): 3 - - 21 . . DOI: 10.1109/TCAD.2008.2010691 http://doi.org/10.1109/TCAD.2008.2010691 . .

E. Masehian , , , D. Sedighizadeh . . Multi-objective robot motion planning using a particle swarm optimization model . . J. Zhejiang Univ.-Sci. C (Comput. & Electron.) , , 2010 . . 11 ( ( 8 ): ): 607 - - 619 . . DOI: 10.1631/jzus.C0910525 http://doi.org/10.1631/jzus.C0910525 . .

N. Muralimanohar , , , R. Balasubramonian , , , N. Jouppi . . Optimizing NUCA organizations and wiring alternatives for large caches with CACTI 6.0 . . Proc. 40th Annual IEEE/ACM Int. Symp. on Microarchitecture , , 2007 . . p.3 - - 14 . . DOI: 10.1109/MICRO.2007.33 http://doi.org/10.1109/MICRO.2007.33 . .

U.Y. Orgas , , , J. Hu , , , R. Marculescu . . Key research problems in NoC design: a holistic perspective . . Proc. 3rd IEEE/ACM/IFIP Int. Conf. on Hardware/Software Codesign and System Synthesis , , 2005 . . p.69 - - 74 . . DOI: 10.1145/1084834.1084856 http://doi.org/10.1145/1084834.1084856 . .

A.R.M. Rao , , , N. Arvind . . A scatter search algorithm for stacking sequence optimisation of laminate composites . . Compos. Struct. , , 2005 . . 70 ( ( 4 ): ): 383 - - 402 . . DOI: 10.1016/j.compstruct.2004.09.031 http://doi.org/10.1016/j.compstruct.2004.09.031 . .

F. Refan , , , H. Alemzadeh , , , S. Safari , , , 等 . . Reliability in application specific mesh-based NoC architectures . . Proc. 14th IEEE Int. On-line Testing Symp. , , 2008 . . p.207 - - 212 . . DOI: 10.1109/IOLTS.2008.53 http://doi.org/10.1109/IOLTS.2008.53 . .

P.C. Saxena , , , S. Gupta , , , J. Rai . . A delay optimal coterie on the k-dimensional folded Petersen graph . . J. Parall. Distr. Comput. , , 2003 . . 63 ( ( 11 ): ): 1026 - - 1035 . . DOI: 10.1016/S0743-7315(03)00116-3 http://doi.org/10.1016/S0743-7315(03)00116-3 . .

M.J. Sepulveda , , , M. Strum , , , W.J. Chau . . A multi-objective adaptive immune algorithm for NoC mapping . . Proc. 17th IFIP Int. Conf. on Very Large Scale Integration , , 2011 . . p.193 - - 196 . . DOI: 10.1109/VLSISOC.2009.6041354 http://doi.org/10.1109/VLSISOC.2009.6041354 . .

L. Tang , , , S. Kumar . . A two-step genetic algorithm for mapping task graphs to a network on chip architecture . . Euromicro Symp. on Digital System Design , , 2003 . . p.180 - - 187 . . DOI: 10.1109/DSD.2003.1231923 http://doi.org/10.1109/DSD.2003.1231923 . .

J. Wang , , , Y. Jiao , , , X. Song , , , 等 . . Optimal training sequences for indoor wireless optical communications . . J. Opt. , , 2012a . . 14 ( ( 1 ): ): 015401.1 - - 015401.5 . . DOI: 10.1088/2040-8978/14/1/015401 http://doi.org/10.1088/2040-8978/14/1/015401 . .

J. Wang , , , X. Xie , , , Y. Jiao , , , 等 . . Optimal odd-periodic complementary sequences for diffuse wireless optical communications . . Opt. Eng. , , 2012b . . 51 ( ( 9 ): ): 095002.1 - - 095002.6 . . DOI: 10.1117/1.OE.51.9.095002 http://doi.org/10.1117/1.OE.51.9.095002 . .

Q. Yu , , , P. Ampadu . . A flexible parallel simulator for networks-on-chip with error control . . IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. , , 2010 . . 29 ( ( 1 ): ): 103 - - 116 . . DOI: 10.1109/TCAD.2009.2034353 http://doi.org/10.1109/TCAD.2009.2034353 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

A spaceborne advanced storage system for remote sensing microsatellites

A reliable and energy-efficient storage system with erasure coding cache

Areliable power management scheme for consistent hashing based distributed key value storage systems#

Related Author

Shilei TU

Huiquan WANG

Yue HUANG

Zhonghe JIN

Ji-guang WAN

Da-ping LI

Xiao-yang QU

Chao YIN

Related Institution

Micro-Satellite Research Center, Zhejiang University

Key Laboratory of Micro-Nano Satellite Research

Wuhan National Laboratory for Optoelectronics, Department of Computer Science and Technology, Huazhong University of Science and Technology

Wuhan National Laboratory for Optoelectronics

Department of Computer Science and Technology, Huazhong University of Science and Technology

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰