基于调和距离量子多目标进化算法的NoC测试规划优化

南京大学学报(自然科学版) ›› 2017, Vol. 53 ›› Issue (1): 173–.

基于调和距离量子多目标进化算法的NoC测试规划优化

胡　聪1，2，李　智1，3*，周　甜2，屈瑾瑾2，许川佩2

出版日期:2017-01-19 发布日期:2017-01-19
作者简介:1.西安电子科技大学机电工程学院，西安，710071；2.桂林电子科技大学电子工程与自动化学院，桂林，541004；3．桂林航天工业学院，桂林，541004
基金资助:
基金项目：国家自然科学基金(61561012，21662018)，广西自然科学基金(2014GXNSFAA118370，2014GXNSFAA118393)，广西自动检测技术与仪器重点实验室(YQ16106) 收稿日期：2016－09－26 *通讯联系人，Email：mataaedu@outlook.com

Test scheduling optimization for networkonchip using harmonic distance quantuminspired evolutionary algorithm

Hu Cong1，2，Li Zhi1，3*，Zhou Tian2，Qu Jinjin2，Xu Chuanpei2

Online:2017-01-19 Published:2017-01-19
About author:1.School of MechanoElectronic Engineering，Xidian University，Xi’an，710071，China； 2．School of Electronic Engineering and Automation，Guilin University of Electronic Technology，Guilin，541004，China； 3．Guilin University of Aerospace Technology，Guilin，541004，China

摘要/Abstract

摘要： 如何实现测试时间和测试功耗协同优化是目前片上网络(NetworkonChip，NoC)测试中亟待解决的问题．提出一种基于调和距离量子多目标进化算法(Harmonic distance quantuminspired multiobjective evolutionary algorithm，HQMEA)的NoC测试规划优化方法．采用重用NoC作为测试存取机制(Test access mechanism，TAM)的并行测试方法，对NoC中的内核进行测试，节省测试资源，提高测试效率．提出的算法在量子多目标进化算法(Quantuminspired multiobjective evolutionary algorithm，QMEA)的基础上，采用多进制概率角编码替代二进制概率幅编码，更好的适应NoC测试规划问题；采用调和距离替代拥挤距离(Crowding distance)能更好的衡量拥挤程度；采用混沌策略动态更新旋转角，能很好地兼顾了算法的探索和发掘能力．在ITC’02 test benchmarks测试集上进行对比实验，结果表明相比量子多目标进化算法，提出的算法不仅提升了算法的收敛性，而且保证了Pareto解集良好的分布性．

Abstract: Networkonchip(NoC)is an emerging communication paradigm for the nextgeneration complex corebased system chips.The cooptimization of test time and test power consumption is currently an emergency problem to be solved for networkonchip testing.In this paper，we propose a harmonic distance quantuminspired multiobjective evolutionary algorithm(HQMEA)for NoC test scheduling optimization.The reuse of onchip network as test access mechanism(TAM)in NoC relies on the reuse of existing resources without introducing new overhead，it can affords a costefficient solution to the NoCbased system testing.Therefore，for the sake of saving testing resources and improving the test efficiency，we adopt the parallel test method of the NoC reuse to test the Intellectual Property(IP)cores of the NoC.On the basis of the quantuminspired multiobjective evolutionary algorithm(QMEA)，the proposed algorithm adoptS multinary probability angle coding as an alternative to probability amplitude binary coding，which is suitable for the NoC test scheduling problem；Then，the proposed algorithm uses the harmonic distance as a represent of crowded distance to better measure crowded degree；In addition，the proposed algorithm adopts the strategy of chaos dynamically updating rotation angle to improve the balance between exploration and exploitation of the algorithm.The comparative experiments are conducted on the ITC’02 test benchmarks.The results show that compared with quantum multiobjective evolutionary algorithms，the proposed algorithm not only improves the convergence of the algorithm，but also ensures a better distribution on the Pareto front.It confirms the superiority of the proposed algorithm in solving multiobjective optimization problems.

胡　聪1，2，李　智1，3*，周　甜2，屈瑾瑾2，许川佩2. 基于调和距离量子多目标进化算法的NoC测试规划优化[J]. 南京大学学报(自然科学版), 2017, 53(1): 173–.

Hu Cong1，2，Li Zhi1，3*，Zhou Tian2，Qu Jinjin2，Xu Chuanpei2 . Test scheduling optimization for networkonchip using harmonic distance quantuminspired evolutionary algorithm[J]. Journal of Nanjing University(Natural Sciences), 2017, 53(1): 173–.

参考文献

[1]　Benini L，De Micheli G．Networks on chips：A new SoC paradigm.Computer，2002，35(1)：70－78. [2] Cota E，Kreutz M，Zeferino C A，et al.The impact of NoC reuse on the testing of corebased systems.In：21st IEEE VLSI Test Symposium.Los Alamitos，USA：IEEE Press，2003，128－133. [3] Nolen J M，Mahapatra R．A TDM test scheduling method for networkonchip systems.In：6th International Workshop on Microprocessor Test and Verification.Los Alamitos，USA：IEEE Press，2005，90－95 [4] Liu C，Iyengar V，Shi J，et al.Poweraware test scheduling in networkonchip using variablerate onchip clocking.In：23rd IEEE VLSI Test Symposium.Los Alamitos，USA：IEEE Press，2005，349－354. [5] Xiang D，Zhang Y．Costeffective poweraware core testing in NoCs based on a new unicastbased multicast scheme.IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems，2011，30(1)：135－147. [6] Richter M，Chakrabarty K．Optimization of test PinCount，test scheduling，and test access for NoCbased multicore SoCs.IEEE Transactions on Computers，2014，63(3)：691－702. [7] Hu C，Li Z，Xu C，et al.Test scheduling for networkonchip using XYDirection connected subgraph partition and multiple test clocks.Journal of Electronic Testing：Theory and Applications，2016，32(1)：31－42. [8] 李　丽，张宇昂，傅玉祥等．三维众核片上处理器存储架构研究．南京大学学报(自然科学)，2014，50(3)：330－335.(Li L，Zhang Y A，Fu Y X ，et al.The study of memory architectures for 3D chip multiprocessors.Journal of Nanjing University(Natural Sciences)，2014，50(3)：330－335.) [9] Marinissen E J，Iyengar V，Chakrabarty K．A set of benchmarks for modular testing of SOCs.In：International Test Conference.New York，USA：IEEE Press，2002. [10] 公茂果，焦李成，杨咚咚等．进化多目标优化算法研究．软件学报，2009，20(2)：271－289.(Gong M G，Jiao L C，Yang D D，et al.Research on evolutionary multiobjective optimization algorithms.Journal of Software，2009，20(2)：271－289.) [11] Martí L，García J，Berlanga A，et al.A stopping criterion for multiobjective optimization evolutionary algorithms.Information Sciences.2016，367－368：700－718. [12] 宋晓峰，亢金龙，王　宏．进化算法的发展与应用．现代电子技术，2006(20)：66－68.(Song X F，Kang J L，Wang H．Development and applications of evolution arithmetic.Modern Electronics Technique，2006(20)：66－68.) [13] 杨　蕴，朱　琳，林　锦等．考虑地面沉降约束的地下水模拟优化管理模型．南京大学学报(自然科学)，2016，52(3)：470－478.(Yang Y，Zhu L，Lin J，et al.Simulation optimization modeling for groundwater management considering land subsidence.Journal of Nanjing University(Natural Sciences)，2016，52(3)：470－478.) [14] KukHyun H，JongHwan K．Quantuminspired evolutionary algorithm for a class of combinatorial optimization.IEEE Transactions on Evolutionary Computation，2002，6(6)：580－593. [15] Kim Y，Kim J H，Han K H．Quantuminspired multiobjective evolutionary algorithm for multiobjective 0/1 knapsack problems.In：IEEE Congress on Evolutionary Computation.New York，USA：IEEE Press，2006，2586－2591. [16] 申抒含，金炜东．多进制概率角复合位编码量子进化算法．模式识别与人工智能，2005，18(6)：657－663.(Shen S H，Jin W D．Multinary compound states of probability angle coded quantuminspired evolutionary algorithm.Pattern Recognition and Artificial Intelligence，2005，18(6)：657－663.) [17] 毕晓君，王艳娇．约束多目标人工蜂群算法．吉林大学学报(工学版)，2013，43(2)：397－403.(Bi X J，Wang Y J．Constraint multiobjective evolutionary algorithm based on artificial bee colony algorithm.Journal of Jilin University University(Engineering and Technology Edition)，2013，43(2)：397－403.) [18] Javidi M，Hosseinpourfard R．Chaos genetic algorithm instead genetic algorithm.International Arab Journal of Information Technology，2015，12(2)：163－168. [19] Petrovic＇ M，Mitic＇ M，Vukovic＇ N，et al.Chaotic particle swarm optimization algorithm for flexible process planning.The International Journal of Advanced Manufacturing Technology，2016，85(9－12)：2535－2555. [20] Zhang J，Lin S，Qiu W．A modified chaotic differential evolution algorithm for shortterm optimal hydrothermal scheduling.International Journal of Electrical Power & Energy Systems，2015，65：159－168. [21] Rezaee J A．A chaoticbased big bangbig crunch algorithm for solving global optimisation problems.Neural Computing and Applications，2014，25(6)：1329－1335. [22] Gandomi A H，Yang X．Chaotic bat algorithm.Journal of Computational Science，2014，5(2)：224－232. [23] He D，He C，Jiang L G，et al.Chaotic characteristics of a onedimensional iterative map with infinite collapses.IEEE Transactions on Circuits and SystemsI：Fundamental Theory and Applications，2001，48(7)：900－906. [24] Pouget J，Larsson E，Peng Z．SOC test time minimization under multiple constraints.In：12th Asian Test Symposium.Los Alamitos，USA：IEEE Press，2003，312－317. [25] Zitzler E，Deb K，Thiele L．Comparison of multiobjective evolutionary algorithms：Empirical results.Evolutionary Computation，2000，8(2)：173－195. [26] Zitzler E．Evolutionary algorithms for multiobjective optimization：Methods and applications.Ph.D.Dissertation.Zurich，Switzerland：Swiss Federal Institute of Technology，1999.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed