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

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

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.
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.  doi: 10.3934/dcds.2011.31.1069.  Google Scholar

[2]

J. Bergeron, Writing Testbenches using SystemVerilog,, $1^{st}$ edition, (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.  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.  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, (2008), 20.  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), (2005), 79.  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.  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.   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, (1996), 991.  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, (2003), 286.   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, (1993), 416.   Google Scholar

[12]

D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning,, Addison-Wesley, (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, (1994), 82.  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, (1992), 291.   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.  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, (2001), 793.  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.  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), (2006), 19.  doi: 10.1109/HLDVT.2006.319996.  Google Scholar

[19]

E. Sanchez, M. Schillaci and G. Squillero, Evolutionary Optimization: The GP Toolkit,, $1^{st}$ edition, (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, (2007), 83.  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.  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, (1996), 517.  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, (2001), 82.  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, (1993), 41.   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, (1999), 257.  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.  doi: 10.3934/dcds.2011.31.1069.  Google Scholar

[2]

J. Bergeron, Writing Testbenches using SystemVerilog,, $1^{st}$ edition, (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.  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.  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, (2008), 20.  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), (2005), 79.  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.  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.   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, (1996), 991.  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, (2003), 286.   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, (1993), 416.   Google Scholar

[12]

D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning,, Addison-Wesley, (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, (1994), 82.  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, (1992), 291.   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.  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, (2001), 793.  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.  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), (2006), 19.  doi: 10.1109/HLDVT.2006.319996.  Google Scholar

[19]

E. Sanchez, M. Schillaci and G. Squillero, Evolutionary Optimization: The GP Toolkit,, $1^{st}$ edition, (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, (2007), 83.  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.  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, (1996), 517.  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, (2001), 82.  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, (1993), 41.   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, (1999), 257.  doi: 10.1109/4235.797969.  Google Scholar

[26]

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

[1]

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

[2]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[3]

Dmitry Treschev. A locally integrable multi-dimensional billiard system. Discrete & Continuous Dynamical Systems - A, 2017, 37 (10) : 5271-5284. doi: 10.3934/dcds.2017228

[4]

Xu Zhang, Xiang Li. Modeling and identification of dynamical system with Genetic Regulation in batch fermentation of glycerol. Numerical Algebra, Control & Optimization, 2015, 5 (4) : 393-403. doi: 10.3934/naco.2015.5.393

[5]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[6]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[7]

Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021008

[8]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028

[9]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023

[10]

Cicely K. Macnamara, Mark A. J. Chaplain. Spatio-temporal models of synthetic genetic oscillators. Mathematical Biosciences & Engineering, 2017, 14 (1) : 249-262. doi: 10.3934/mbe.2017016

[11]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006

[12]

Habib Ammari, Josselin Garnier, Vincent Jugnon. Detection, reconstruction, and characterization algorithms from noisy data in multistatic wave imaging. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 389-417. doi: 10.3934/dcdss.2015.8.389

[13]

Xianming Liu, Guangyue Han. A Wong-Zakai approximation of stochastic differential equations driven by a general semimartingale. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2499-2508. doi: 10.3934/dcdsb.2020192

[14]

Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213

[15]

Xiaohu Wang, Dingshi Li, Jun Shen. Wong-Zakai approximations and attractors for stochastic wave equations driven by additive noise. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2829-2855. doi: 10.3934/dcdsb.2020207

[16]

M. Grasselli, V. Pata. Asymptotic behavior of a parabolic-hyperbolic system. Communications on Pure & Applied Analysis, 2004, 3 (4) : 849-881. doi: 10.3934/cpaa.2004.3.849

[17]

Elena Bonetti, Pierluigi Colli, Gianni Gilardi. Singular limit of an integrodifferential system related to the entropy balance. Discrete & Continuous Dynamical Systems - B, 2014, 19 (7) : 1935-1953. doi: 10.3934/dcdsb.2014.19.1935

[18]

Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203

[19]

Dugan Nina, Ademir Fernando Pazoto, Lionel Rosier. Controllability of a 1-D tank containing a fluid modeled by a Boussinesq system. Evolution Equations & Control Theory, 2013, 2 (2) : 379-402. doi: 10.3934/eect.2013.2.379

[20]

Yanqin Fang, Jihui Zhang. Multiplicity of solutions for the nonlinear Schrödinger-Maxwell system. Communications on Pure & Applied Analysis, 2011, 10 (4) : 1267-1279. doi: 10.3934/cpaa.2011.10.1267

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]