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

Adriel Cheng; Cheng-Chew Lim

doi:10.3934/jimo.2014.10.383

Article Contents

2014, Volume 10, Issue 2: 383-396. Doi: 10.3934/jimo.2014.10.383

This issue Previous Article Fractional order optimal control problems with free terminal time Next Article A ladder method for linear semi-infinite programming

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

Received: September 30, 2012

Revised: June 30, 2013

Published: March 2014

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Related Papers

Cited by

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.
[2]	J. Bergeron, Writing Testbenches using SystemVerilog, $1^{st}$ edition, Springer Science + Business Media, New York, 1994.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[12]	D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Massachusetts, 1989.
[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.
[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.
[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.
[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.
[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.
[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.
[19]	E. Sanchez, M. Schillaci and G. Squillero, Evolutionary Optimization: The GP Toolkit, $1^{st}$ edition, Springer Science + Business Media, New York, 2011.
[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.
[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.
[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.
[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.
[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.
[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.
[26]	Nios II Hardware Development Tutorial,, Development manual of Altera Inc., (2005).