skip to main content
research-article

Evolution of synthetic RTL benchmark circuits with predefined testability

Published: 25 July 2008 Publication History

Abstract

This article presents a new real-world application of evolutionary computing in the area of digital-circuits testing. A method is described which enables to evolve large synthetic RTL benchmark circuits with a predefined structure and testability. Using the proposed method, a new collection of synthetic benchmark circuits was developed. These benchmark circuits will be useful in a validation process of novel algorithms and tools in the area of digital-circuits testing. Evolved benchmark circuits currently represent the most complex benchmark circuits with a known level of testability. Furthermore, these circuits are the largest that have ever been designed by means of evolutionary algorithms. This work also investigates suitable parameters of the evolutionary algorithm for this problem and explores the limits in the complexity of evolved circuits.

References

[1]
Bhatia, S. and Jha, N. 1994. Genesis: A behavioral synthesis system for hierarchical testability. In Proceedings of the European Design and Test Conference, Paris. IEEE Computer Society, 272--276.
[2]
Brglez, F., Bryan, D., and Kozminski, K. 1989. Combinational profiles of sequential benchmark circuits. In Proceedings of the International Symposium on Circuits and Systems (ISCAS), Portland, OR. IEEE Computer Society, 1924--1934.
[3]
Brglez, F. and Fujiwara, H. 1985. A neutral netlist of 10 combinational benchmark circuits and a target simulator in Fortran. In Proceedings of the International Symposium on Circuits and Systems (ISCAS), Kyoto, Japan. IEEE Computer Society, 695--698.
[4]
Chen, C.-H., Wu, C., and Saab, D. G. 1991. Accessibility analysis on data flow graph: An approach to design for testability. In Proceedings of the IEEE International Conference on Computer Design: VLSI in Computer and Processors. IEEE Computer Society, 463--466.
[5]
Corno, F., Cumani, G., Reorda, M. S., and Squillero, G. 2002. Efficient machine-code test-program induction. In Proceedings of the Congress on Evolutionary Computation (CEC), Honolulu, Hawaii. IEEE, 1486--1491.
[6]
Corno, F., Reorda, M. S., and Squillero, G. 2000a. High-Level observability for effective high-level ATPG. In Proceedings of the 18th IEEE VLSI Test Symposium (VTS). IEEE Computer Society, Washington, DC, 411--416.
[7]
Corno, F., Reorda, M. S., and Squillero, G. 2000b. RT-Level ITC'99 benchmarks and first ATPG results. IEEE Des. Test 17, 3, 44--53.
[8]
Darnauer, J. and Dai, W. W.-M. 1996. A method for generating random circuits and its application to routability measurement. In Proceedings of the ACM 4th International Symposium on Field-Programmable Gate Arrays (FPGA). ACM Press, New York, 66--72.
[9]
Fernandes, J. M., Santos, M. B., Oliveira, A. L., and Teixeira, J. C. 2004. A probabilistic method for the computation of testability of RTL constructs. In Proceedings of the Conference on Design Automation and Test in Europe (DATE). IEEE Computer Society, Washington, DC, 176--181.
[10]
Flottes, M. L., Pires, R., and Rouzeyre, B. 1997. Analyzing testability from behavioral to RT level. In Proceedings of the European Conference on Design and Test (EDTC). IEEE Computer Society, Washington, DC, 158--164.
[11]
Garvie, M. and Thompson, A. 2003. Evolution of combinatonial and sequential on-line self-diagnosing hardware. In Proceedings of the 5th NASA/DoD Workshop on Evolvable Hardware (EH), Chicago, IL. IEEE Computer Society, 177--183.
[12]
Gloster, C. 1993. ISCAS'89 addendum benchmark set. In ACM/SIGDA Benchmarks Electron. Newslett. ACM Press.
[13]
Harlow, J. 2000. Overview of popular benchmark sets. IEEE Des. Test Comput. 17, 3, 15--17.
[14]
Hellebrand, S. and Wunderlich, H.-J. 1994. Synthesis of self-testable controllers. In Proceedings of the European Design and Test Conference. IEEE Computer Society Press, 580--585.
[15]
Higuchi, T., Niwa, T., Tanaka, T., Iba, H., de Garis, H., and Furuya, T. 1993. Evolving hardware with genetic learning: A first step towards building a Darwin machine. In Proceedings of the 2nd International Conference on Simulated Adaptive Behaviour. MIT Press, 417--424.
[16]
Hutton, M. D., Rose, J., and Corneil, D. G. 2002. Automatic generation of synthetic sequential benchmark circuits. IEEE Trans. Comput. Aided Design Integr. Circ. Syst. 21, 8, 928--940.
[17]
Iwama, K., Hino, K., Kurokawa, H., and Sawada, S. 1997. Random benchmark circuits with controlled attributes. In Proceedings of the European Design and Test Conference. IEEE Computer Society, Washington, DC, 90--97.
[18]
Kundarewich, P. and Rose, J. 2004. Synthetic circuit generation using clustering and iteration. IEEE Trans. Comput. Aided Des. 23, 6, 869--887.
[19]
Lohn, J. D., Larchev, G. V., and DeMara, R. F. 2003. A genetic representation for evolutionary fault recovery in Virtex FPGAs. In Proceedings of the 5th International Conference on Evolvable Systems: From Biology to Hardware (ICES), Trondheim, Norway. Springer, 47--56.
[20]
Marinissen, E. J., Iyengar, V., and Chakrabarty, K. 2002. A set of benchmarks for modular testing of SoCs. In Proceedings of the IEEE International Test Conference (ITC), Baltimore, MD. IEEE Computer Society Press, 519--528.
[21]
Mazumder, P. and Rudnick, E. 1998. Genetic Algorithms for VLSI Design and Test Automation. Prentice-Hall.
[22]
Miller, J., Job, D., and Vassilev, V. 2000. Principles in the evolutionary design of digital circuits—Part I. Genetic Program. Evolv. Mach. 1, 1, 8--35.
[23]
Miller, J. F. and Thomson, P. 1998. Aspects of digital evolution: Geometry and learning. In Proceedings of the 2nd International Conference on Evolvable Systems: From Biology to Hardware (ICES). Lecture Notes in Computer Science, vol. 1478, Springer, 25--35.
[24]
Pecenka, T. 2006. Brno university of technology: Fittest_bench06 benchmarks and cirgen page. http://www.fit.vutbr.cz/~pecenka/cirgen.
[25]
Pecenka, T., Kotasek, Z., and Sekanina, L. 2006. FITTest_BENCH06: A new set of benchmark circuits reflecting testability properties. In Proceedings of the IEEE Design and Diagnostics of Electronic Circuits and Systems Workshop. IEEE Computer Society, 285--289.
[26]
Pecenka, T., Kotasek, Z., Sekanina, L., and Strnadel, J. 2005. Automatic discovery of RTL benchmark circuits with predefined testability properties. In Proceedings of the NASA/DoD Conference on Evolvable Hardware, Los Alamitos, CA. IEEE Computer Society, 51--58.
[27]
Pecenka, T., Strnadel, J., Kotasek, Z., and Sekanina, L. 2006. Testability estimation based on controllability and observability parameters. In Proceedings of the 9th EUROMICRO Conference on Digital System Design (DSD). IEEE Computer Society, 504--514.
[28]
Pistorius, J., Legai, E., and Minoux, M. 1999. Generation of very large circuits to benchmark the partitioning of FPGA. In Proceedings of the International Symposium on Physical Design (ISPD). ACM Press, New York, 67--73.
[29]
Sekanina, L. 2004. Evolvable Components: From Theory to Hardware Implementations. Natural Computing Series, Springer.
[30]
Sekanina, L. and Ruzicka, R. 2003. Easily testable image operators: The class of circuits where evolution beats engineers. In Proceedings of the NASA/DoD Conference on Evolvable Hardware, Chicago, IL. IEEE Computer Society, 135--144.
[31]
Strnadel, J. 2004. Testability analysis and improvements of register-transfer level digital circuits. Ph.D. thesis, Brno University of Technology.
[32]
Stroobandt, D., Verplaetse, P., and Van Campenhout, J. 2000. Generating synthetic benchmark circuits for evaluating CAD tools. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 19, 9, 1011--1022.
[33]
Thompson, A. 1998. Hardware Evolution: Automatic Design of Electronic Circuits in Reconfigurable Hardware by Artificial Evolution. Distinguished Dissertation Series, Springer.
[34]
URL-ITC99. 1999. ITC'99 benchmarks web site. http://www.cad.polito.it/tools/itc99.html.
[35]
Verplaetse, P., Stroobandt, D., and Van Campenhout, J. 2002. Synthetic benchmark circuits for timing-driven physical design applications. In Proceedings of the International Conference on VLSI, Los Vegas, NV. H. Arabnia, ed. CSREA Press, 31--37.
[36]
Zhang, K., DeMara, R. F., and Sharma, C. A. 2005. Consensus-Based evaluation for fault isolation and on-line evolutionary regeneration. In Proceedings of the 6th International Conference on Evolvable Systems: From Biology to Hardware (ICES), Lecture Notes in Computer Science, vol. 3637. Springer, 12--24.

Cited By

View all
  • (2024)Synthetic Benchmark for Data-Driven Pre-Si Analogue Circuit VerificationElectronics10.3390/electronics1313260013:13(2600)Online publication date: 2-Jul-2024
  • (2022)Graph-based genetic programmingProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533657(958-982)Online publication date: 9-Jul-2022
  • (2022)Scalable Synthetic Circuit Generation using Geometry Embedding for CAD Tool Assessment2022 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS48785.2022.9937638(3239-3243)Online publication date: 28-May-2022
  • Show More Cited By

Index Terms

  1. Evolution of synthetic RTL benchmark circuits with predefined testability

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Transactions on Design Automation of Electronic Systems
      ACM Transactions on Design Automation of Electronic Systems  Volume 13, Issue 3
      July 2008
      370 pages
      ISSN:1084-4309
      EISSN:1557-7309
      DOI:10.1145/1367045
      Issue’s Table of Contents
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Journal Family

      Publication History

      Published: 25 July 2008
      Accepted: 01 January 2008
      Revised: 01 January 2008
      Received: 01 May 2007
      Published in TODAES Volume 13, Issue 3

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. Benchmark circuit
      2. evolvable hardware
      3. testability analysis

      Qualifiers

      • Research-article
      • Research
      • Refereed

      Funding Sources

      • Grant Agency of the Czech Republic

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)8
      • Downloads (Last 6 weeks)1
      Reflects downloads up to 15 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)Synthetic Benchmark for Data-Driven Pre-Si Analogue Circuit VerificationElectronics10.3390/electronics1313260013:13(2600)Online publication date: 2-Jul-2024
      • (2022)Graph-based genetic programmingProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533657(958-982)Online publication date: 9-Jul-2022
      • (2022)Scalable Synthetic Circuit Generation using Geometry Embedding for CAD Tool Assessment2022 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS48785.2022.9937638(3239-3243)Online publication date: 28-May-2022
      • (2018)Generating Synthetic MVL Benchmarks from Random MDDs Under Restrictions2018 IEEE 48th International Symposium on Multiple-Valued Logic (ISMVL)10.1109/ISMVL.2018.00037(168-173)Online publication date: May-2018
      • (2017)Evolvable Hardware Challenges: Past, Present and the Path to a Promising FutureInspired by Nature10.1007/978-3-319-67997-6_1(3-37)Online publication date: 27-Oct-2017
      • (2015)Generating synthetic benchmark circuits for accelerated life testing of field programmable gate arrays using genetic algorithm and particle swarm optimizationApplied Soft Computing10.1016/j.asoc.2014.11.00227:C(179-190)Online publication date: 1-Feb-2015
      • (2012)Evolvable HardwareHandbook of Natural Computing10.1007/978-3-540-92910-9_50(1657-1705)Online publication date: 2012
      • (2011)Evolution of digital circuitsProceedings of the 13th annual conference companion on Genetic and evolutionary computation10.1145/2001858.2002140(1343-1360)Online publication date: 12-Jul-2011
      • (2011)Challenges of evolvable hardware: past, present and the path to a promising futureGenetic Programming and Evolvable Machines10.1007/s10710-011-9141-612:3(183-215)Online publication date: 1-Sep-2011
      • (2011)Formal verification of candidate solutions for post-synthesis evolutionary optimization in evolvable hardwareGenetic Programming and Evolvable Machines10.1007/s10710-011-9132-712:3(305-327)Online publication date: 1-Sep-2011
      • Show More Cited By

      View Options

      Login options

      Full Access

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media