American Institute of Mathematical Sciences

Advanced
April  2014, 10(2): 383-396. doi: 10.3934/jimo.2014.10.383

Optimizing system-on-chip verifications with multi-objective genetic evolutionary algorithms

Adriel Cheng 1, and  Cheng-Chew Lim 1,

1. 

School of Electrical and Electronic Engineering, The University of Adelaide, Adelaide, 5005, Australia, Australia

Received  October 2012 Revised  July 2013 Published  October 2013

Verification of semiconductor chip designs is commonly driven by single goal orientated measures. With increasing design complexities, this approach is no longer effective. We enhance the effectiveness of coverage driven design verifications by applying multi-objective optimization techniques. The technique is based on genetic evolutionary algorithms. Difficulties with conflicting test objectives and selection of tests to achieve multiple verification goals in the genetic evolutionary framework are also addressed.
Keywords: genetic evolutionary algorithms, Multi-objective optimization, system-on-chip verification, coverage driven verification., Pareto optimization.
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C3.
Citation: Adriel Cheng, Cheng-Chew Lim. Optimizing system-on-chip verifications with multi-objective genetic evolutionary algorithms. Journal of Industrial & Management Optimization, 2014, 10 (2) : 383-396. doi: 10.3934/jimo.2014.10.383
References:
[1]

T. Bao and B. Mordukhovich, Refined necessary conditions in multi-objective optimization with applications to microeconomic modeling, Discrete Contin. Dyn. Syst., 31 (2011), 1069-1096. doi: 10.3934/dcds.2011.31.1069.  Google Scholar

[2]

J. Bergeron, Writing Testbenches using SystemVerilog, $1^{st}$ edition, Springer Science + Business Media, New York, 1994. Google Scholar

[3]

H. Bonnel and N. S. Pham, Non-smooth optimization over the (weakly or properly) Pareto set of a linear-quadratic multi-objective control problem: Explicit optimality conditions, J. Ind. Manag. Optim., 7 (2011), 789-809. doi: 10.3934/jimo.2011.7.789.  Google Scholar

[4]

A. Cheng and C. C. Lim, Markov modeling and parameterization of genetic evolutionary test generation, J. Global Optim., 51 (2011), 743-751. doi: 10.1007/s10898-011-9682-5.  Google Scholar

[5]

A. Cheng, C.-C. Lim, Y. Sun, H. He, Z. Zhou and T. Lei, Using genetic evolutionary software application testing to verify a DSP SoC, in 4th IEEE Int. Workshop on Electronic Design, Test & Applications, IEEE Computer Society, Hong Kong, 2008, 20-25. doi: 10.1109/DELTA.2008.31.  Google Scholar

[6]

A. Cheng, A. Parashkevov and C.-C. Lim, A software test program generator for verifying system-on-chips, in 10th IEEE Int. High Level Design Validation and Test Workshop (HLDVT'05), Napa Valley, CA, 2005, 79-86. doi: 10.1109/HLDVT.2005.1568818.  Google Scholar

[7]

C. A. C. Coello, A comprehensive survey of evolutionary-based multiobjective optimization techniques, Journal of Knowledge and Information Systems, 1 (1999), 269-308. doi: 10.1007/BF03325101.  Google Scholar

[8]

F. Corno, E. Sanchez, M. S. Reorda and G. Squillero, Code generation for functional validation of pipelined microprocessors, Journal of Electronic Testing: Theory and Applications, 20 (2004), 269-278. Google Scholar

[9]

F. Corno, P. Prinetto, M. Rebaudengo and M. S. Reorda, GATTO: A genetic algorithm for automatic test pattern generation for large synchronous sequential circuits, in IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, Vol. 15, IEEE Council on Electronic Design Automation, 1996, 991-1000. doi: 10.1109/43.511578.  Google Scholar

[10]

S. Fine and A. Ziv, Coverage directed test generation for functional verification using Bayesian networks, in Proc. 40th Design Automation Conference, New Orleans, LA, 2003, 286-291. Google Scholar

[11]

C. M. Fonseca and P. J. Flemming, Genetic algorithms for multi-objective optimization: Formulation, discussion, and generalization, in 5th Int. Conf. on Genetic Algorithms, Morgan Kaufmann, 1993, 416-423. Google Scholar

[12]

D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Massachusetts, 1989. Google Scholar

[13]

J. Horn, N. Nafpliotis and D. E. Goldberg, A Niched Pareto genetic algorithm for multiobjective optimization, in Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Computation, Orlando, FL, 1994, 82-87. doi: 10.1109/ICEC.1994.350037.  Google Scholar

[14]

W. Jakob, M. Gorges-Schleuter and C. Blume, Application of genetic algorithms to task planning and learning, in Parallel Problem Solving from Nature, 2nd Workshop, Lecture Notes in Computer Science, 1992, 291-300. Google Scholar

[15]

T.-F. Liang and H.-W. Cheng, Multi-objective aggregate production planning decisions using two-phase fuzzy goal programming method, J. Ind. Manag. Optim., 7 (2011), 365-383. doi: 10.3934/jimo.2011.7.365.  Google Scholar

[16]

G. Nativ, S. Mittermaier, S. Ur and A. Ziv, Cost evaluation of coverage directed test generation for the IBM mainframe, in Proceedings of the 2001 IEEE International Test Conference, Baltimore, MD, 2001, 793-802. doi: 10.1109/TEST.2001.966701.  Google Scholar

[17]

T. Ray and R. Sarker, EA for solving combined machine layout and job assignment problems, J. Ind. Manag. Optim., 4 (2008), 631-646. doi: 10.3934/jimo.2008.4.631.  Google Scholar

[18]

A. Samarah, A. Habibi, S. Tahar and N. Kharma, Automated coverage directed test generation using a cell-based genetic algorithm, in IEEE Int. High Level Design Validation and Test Workshop (HLDVT'06), Monterey, CA, 2006, 19-26. doi: 10.1109/HLDVT.2006.319996.  Google Scholar

[19]

E. Sanchez, M. Schillaci and G. Squillero, Evolutionary Optimization: The GP Toolkit, $1^{st}$ edition, Springer Science + Business Media, New York, 2011. Google Scholar

[20]

E. Sanchez and G. Squillero, Evolutionary techniques applied to hardware optimization problems: Test and verification of advanced processors, in Advances in Evolutionary Computing for System Design (eds. L. C. Jain, V. Palade and D. Srinivasan), Studies in Computational Intelligence, 66, Springer, Berlin-Heidelberg, 2007, 83-106. doi: 10.1007/978-3-540-72377-6_13.  Google Scholar

[21]

N. Srinivas and K. Deb, Multiobjective optimization using nondominated sorting in genetic algorithms, Evolutionary Computation, 2 (1994), 221-248. doi: 10.1162/evco.1994.2.3.221.  Google Scholar

[22]

H. Tamaki, H. Kita and S. Kobayashi, Multi-objective optimization by genetic algorithms: A review, in Proc. IEEE Int. Conference on Evolutionary Computation, Nagoya, Japan, 1996, 517-522. doi: 10.1109/ICEC.1996.542653.  Google Scholar

[23]

S. Tasiran, F. Fallah, D. G. Chineery, S. J. Weber and K. Keutzer, A functional validation technique: Biased-random simulation guided by observability-based coverage, in IEEE Int. Conference on Computer Design, Austin, TX, 2001, 82-88. doi: 10.1109/ICCD.2001.955007.  Google Scholar

[24]

P. B. Wilson and M. D. Macleod, Low implementation cost IIR digital filter design using genetic algorithms, in IEE/IEEE Workshop on Natural Algorithms in Signal Processing, Chelmsford, Essex, (1993), 41-48. Google Scholar

[25]

E. Zitzler and L. Thiele, Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach, in IEEE Trans. on Evolutionary Computation, Vol. 3, IEEE Computational Intelligence Society, 1999, 257-271. doi: 10.1109/4235.797969.  Google Scholar

[26]

, Nios II Hardware Development Tutorial,, Development manual of Altera Inc., (2005).   Google Scholar

show all references

References:
[1]

T. Bao and B. Mordukhovich, Refined necessary conditions in multi-objective optimization with applications to microeconomic modeling, Discrete Contin. Dyn. Syst., 31 (2011), 1069-1096. doi: 10.3934/dcds.2011.31.1069.  Google Scholar

[2]

J. Bergeron, Writing Testbenches using SystemVerilog, $1^{st}$ edition, Springer Science + Business Media, New York, 1994. Google Scholar

[3]

H. Bonnel and N. S. Pham, Non-smooth optimization over the (weakly or properly) Pareto set of a linear-quadratic multi-objective control problem: Explicit optimality conditions, J. Ind. Manag. Optim., 7 (2011), 789-809. doi: 10.3934/jimo.2011.7.789.  Google Scholar

[4]

A. Cheng and C. C. Lim, Markov modeling and parameterization of genetic evolutionary test generation, J. Global Optim., 51 (2011), 743-751. doi: 10.1007/s10898-011-9682-5.  Google Scholar

[5]

A. Cheng, C.-C. Lim, Y. Sun, H. He, Z. Zhou and T. Lei, Using genetic evolutionary software application testing to verify a DSP SoC, in 4th IEEE Int. Workshop on Electronic Design, Test & Applications, IEEE Computer Society, Hong Kong, 2008, 20-25. doi: 10.1109/DELTA.2008.31.  Google Scholar

[6]

A. Cheng, A. Parashkevov and C.-C. Lim, A software test program generator for verifying system-on-chips, in 10th IEEE Int. High Level Design Validation and Test Workshop (HLDVT'05), Napa Valley, CA, 2005, 79-86. doi: 10.1109/HLDVT.2005.1568818.  Google Scholar

[7]

C. A. C. Coello, A comprehensive survey of evolutionary-based multiobjective optimization techniques, Journal of Knowledge and Information Systems, 1 (1999), 269-308. doi: 10.1007/BF03325101.  Google Scholar

[8]

F. Corno, E. Sanchez, M. S. Reorda and G. Squillero, Code generation for functional validation of pipelined microprocessors, Journal of Electronic Testing: Theory and Applications, 20 (2004), 269-278. Google Scholar

[9]

F. Corno, P. Prinetto, M. Rebaudengo and M. S. Reorda, GATTO: A genetic algorithm for automatic test pattern generation for large synchronous sequential circuits, in IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, Vol. 15, IEEE Council on Electronic Design Automation, 1996, 991-1000. doi: 10.1109/43.511578.  Google Scholar

[10]

S. Fine and A. Ziv, Coverage directed test generation for functional verification using Bayesian networks, in Proc. 40th Design Automation Conference, New Orleans, LA, 2003, 286-291. Google Scholar

[11]

C. M. Fonseca and P. J. Flemming, Genetic algorithms for multi-objective optimization: Formulation, discussion, and generalization, in 5th Int. Conf. on Genetic Algorithms, Morgan Kaufmann, 1993, 416-423. Google Scholar

[12]

D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Massachusetts, 1989. Google Scholar

[13]

J. Horn, N. Nafpliotis and D. E. Goldberg, A Niched Pareto genetic algorithm for multiobjective optimization, in Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Computation, Orlando, FL, 1994, 82-87. doi: 10.1109/ICEC.1994.350037.  Google Scholar

[14]

W. Jakob, M. Gorges-Schleuter and C. Blume, Application of genetic algorithms to task planning and learning, in Parallel Problem Solving from Nature, 2nd Workshop, Lecture Notes in Computer Science, 1992, 291-300. Google Scholar

[15]

T.-F. Liang and H.-W. Cheng, Multi-objective aggregate production planning decisions using two-phase fuzzy goal programming method, J. Ind. Manag. Optim., 7 (2011), 365-383. doi: 10.3934/jimo.2011.7.365.  Google Scholar

[16]

G. Nativ, S. Mittermaier, S. Ur and A. Ziv, Cost evaluation of coverage directed test generation for the IBM mainframe, in Proceedings of the 2001 IEEE International Test Conference, Baltimore, MD, 2001, 793-802. doi: 10.1109/TEST.2001.966701.  Google Scholar

[17]

T. Ray and R. Sarker, EA for solving combined machine layout and job assignment problems, J. Ind. Manag. Optim., 4 (2008), 631-646. doi: 10.3934/jimo.2008.4.631.  Google Scholar

[18]

A. Samarah, A. Habibi, S. Tahar and N. Kharma, Automated coverage directed test generation using a cell-based genetic algorithm, in IEEE Int. High Level Design Validation and Test Workshop (HLDVT'06), Monterey, CA, 2006, 19-26. doi: 10.1109/HLDVT.2006.319996.  Google Scholar

[19]

E. Sanchez, M. Schillaci and G. Squillero, Evolutionary Optimization: The GP Toolkit, $1^{st}$ edition, Springer Science + Business Media, New York, 2011. Google Scholar

[20]

E. Sanchez and G. Squillero, Evolutionary techniques applied to hardware optimization problems: Test and verification of advanced processors, in Advances in Evolutionary Computing for System Design (eds. L. C. Jain, V. Palade and D. Srinivasan), Studies in Computational Intelligence, 66, Springer, Berlin-Heidelberg, 2007, 83-106. doi: 10.1007/978-3-540-72377-6_13.  Google Scholar

[21]

N. Srinivas and K. Deb, Multiobjective optimization using nondominated sorting in genetic algorithms, Evolutionary Computation, 2 (1994), 221-248. doi: 10.1162/evco.1994.2.3.221.  Google Scholar

[22]

H. Tamaki, H. Kita and S. Kobayashi, Multi-objective optimization by genetic algorithms: A review, in Proc. IEEE Int. Conference on Evolutionary Computation, Nagoya, Japan, 1996, 517-522. doi: 10.1109/ICEC.1996.542653.  Google Scholar

[23]

S. Tasiran, F. Fallah, D. G. Chineery, S. J. Weber and K. Keutzer, A functional validation technique: Biased-random simulation guided by observability-based coverage, in IEEE Int. Conference on Computer Design, Austin, TX, 2001, 82-88. doi: 10.1109/ICCD.2001.955007.  Google Scholar

[24]

P. B. Wilson and M. D. Macleod, Low implementation cost IIR digital filter design using genetic algorithms, in IEE/IEEE Workshop on Natural Algorithms in Signal Processing, Chelmsford, Essex, (1993), 41-48. Google Scholar

[25]

E. Zitzler and L. Thiele, Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach, in IEEE Trans. on Evolutionary Computation, Vol. 3, IEEE Computational Intelligence Society, 1999, 257-271. doi: 10.1109/4235.797969.  Google Scholar

[26]

, Nios II Hardware Development Tutorial,, Development manual of Altera Inc., (2005).   Google Scholar

[1]

Henri Bonnel, Ngoc Sang Pham. Nonsmooth optimization over the (weakly or properly) Pareto set of a linear-quadratic multi-objective control problem: Explicit optimality conditions. Journal of Industrial & Management Optimization, 2011, 7 (4) : 789-809. doi: 10.3934/jimo.2011.7.789
[2]

Shoufeng Ji, Jinhuan Tang, Minghe Sun, Rongjuan Luo. Multi-objective optimization for a combined location-routing-inventory system considering carbon-capped differences. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021051
[3]

Danthai Thongphiew, Vira Chankong, Fang-Fang Yin, Q. Jackie Wu. An on-line adaptive radiation therapy system for intensity modulated radiation therapy: An application of multi-objective optimization. Journal of Industrial & Management Optimization, 2008, 4 (3) : 453-475. doi: 10.3934/jimo.2008.4.453
[4]

Yuan-mei Xia, Xin-min Yang, Ke-quan Zhao. A combined scalarization method for multi-objective optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2669-2683. doi: 10.3934/jimo.2020088
[5]

Xia Zhao, Jianping Dou. Bi-objective integrated supply chain design with transportation choices: A multi-objective particle swarm optimization. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1263-1288. doi: 10.3934/jimo.2018095
[6]

Han Yang, Jia Yue, Nan-jing Huang. Multi-objective robust cross-market mixed portfolio optimization under hierarchical risk integration. Journal of Industrial & Management Optimization, 2020, 16 (2) : 759-775. doi: 10.3934/jimo.2018177
[7]

Qiang Long, Xue Wu, Changzhi Wu. Non-dominated sorting methods for multi-objective optimization: Review and numerical comparison. Journal of Industrial & Management Optimization, 2021, 17 (2) : 1001-1023. doi: 10.3934/jimo.2020009
[8]

Min Zhang, Gang Li. Multi-objective optimization algorithm based on improved particle swarm in cloud computing environment. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1413-1426. doi: 10.3934/dcdss.2019097
[9]

Liwei Zhang, Jihong Zhang, Yule Zhang. Second-order optimality conditions for cone constrained multi-objective optimization. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1041-1054. doi: 10.3934/jimo.2017089
[10]

Yu Chen, Yonggang Li, Bei Sun, Chunhua Yang, Hongqiu Zhu. Multi-objective chance-constrained blending optimization of zinc smelter under stochastic uncertainty. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021169
[11]

Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021037
[12]

Jiao-Yan Li, Xiao Hu, Zhong Wan. An integrated bi-objective optimization model and improved genetic algorithm for vehicle routing problems with temporal and spatial constraints. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1203-1220. doi: 10.3934/jimo.2018200
[13]

Lin Jiang, Song Wang. Robust multi-period and multi-objective portfolio selection. Journal of Industrial & Management Optimization, 2021, 17 (2) : 695-709. doi: 10.3934/jimo.2019130
[14]

Jian Xiong, Zhongbao Zhou, Ke Tian, Tianjun Liao, Jianmai Shi. A multi-objective approach for weapon selection and planning problems in dynamic environments. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1189-1211. doi: 10.3934/jimo.2016068
[15]

Dušan M. Stipanović, Claire J. Tomlin, George Leitmann. A note on monotone approximations of minimum and maximum functions and multi-objective problems. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 487-493. doi: 10.3934/naco.2011.1.487
[16]

Hamed Fazlollahtabar, Mohammad Saidi-Mehrabad. Optimizing multi-objective decision making having qualitative evaluation. Journal of Industrial & Management Optimization, 2015, 11 (3) : 747-762. doi: 10.3934/jimo.2015.11.747
[17]

Peter Giesl, Najla Mohammed. Verification estimates for the construction of Lyapunov functions using meshfree collocation. Discrete & Continuous Dynamical Systems - B, 2019, 24 (9) : 4955-4981. doi: 10.3934/dcdsb.2019040
[18]

Jinyuan Zhang, Aimin Zhou, Guixu Zhang, Hu Zhang. A clustering based mate selection for evolutionary optimization. Big Data & Information Analytics, 2017, 2 (1) : 77-85. doi: 10.3934/bdia.2017010
[19]

Dmitri E. Kvasov, Yaroslav D. Sergeyev. Univariate geometric Lipschitz global optimization algorithms. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 69-90. doi: 10.3934/naco.2012.2.69
[20]

Yang Chen, Xiaoguang Xu, Yong Wang. Wireless sensor network energy efficient coverage method based on intelligent optimization algorithm. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 887-900. doi: 10.3934/dcdss.2019059

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (96)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences