An Entry for THE 5th ANNUAL (2008) ?HUMIES? AWARDS FOR HUMAN-COMPETITIVE RESULTS PRODUCED BY GENETIC AND EVOLUTIONARY COMPUTATION HELD AT THE GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE 2008 (1) the complete title of paper published in the open literature describing the work that the author claims describes a human-competitive result: Evolution of Synthetic RTL Benchmark Circuits with Predefined Testability (2) the name, complete physical mailing address, e-mail address, and phone number of EACH author: Tomas Pecenka, ON Semiconductor, Bozeny Nemcove 1720, 756 61, Roznov pod Radhostem, Czech Republic, e-mail: tomas.pecenka@onsemi.com, +420 571667117 Lukas Sekanina, Faculty of Information Technology, Brno University of Technology, Bozetechova 2, 612 66 Brno, Czech Republic, e-mail: sekanina@fit.vutbr.cz, phone: +420541141215 Zdenek Kotasek, Faculty of Information Technology, Brno University of Technology, Bozetechova 2, 612 66 Brno, Czech Republic, e-mail: kotasek@fit.vutbr.cz, phone: +420541141223 (3) the name of the corresponding author: Lukas Sekanina (4) the abstract of the paper: This paper 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 circuits that have ever been designed by means of evolutionary algorithms. This paper also investigates suitable parameters of the evolutionary algorithm for this problem and explores the limits in the complexity of evolved circuits. (5) a list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria (see above) that the author claims that the work satisfies: D, G (6) a statement stating why the result satisfies the criteria that the contestant claims: This result is in the area of diagnostics and testing of digital circuits. Simultaneously with the growing complexity of digital circuits, we can observe the growing complexity of CAD tools that are utilized to produce and verify these circuits. The evaluation and comparison of different algorithms and methodologies utilized in these CAD tools is one of the most difficult tasks CAD users are faced with. Over the years, there have been many attempts to create and use benchmark circuits for evaluation and comparison of these algorithms and methodologies. In the testing community, the following benchmark circuits are currently used: ISCAS85, ISCAS89, ITC99 and ITC02. The problem of existing benchmark circuits is that their complexity is too low. This problem might be overcome by the utilization of synthetic benchmark circuits. Synthetic benchmarks are usually created by an automated procedure and constrained to have a specific set of desirable characteristics (such as the size, topology, testability and function). In particular, a variable testability and a sufficient structural complexity of benchmark circuits are crucial features for testing modern CAD test tools. Unfortunately, no approach has been proposed so far for the design of synthetic benchmark circuits that are both testable (i.e. the testability can be defined by user) and complex. We used evolutionary algorithm to develop synthetic RTL (Register Transfer Level) benchmark circuits with required structure, complexity and testability. The benchmark circuits are used to verify the effectiveness of algorithms and methodologies which aim at increasing testability parameters of digital circuits and compare different methodologies for design and test of digital circuits. As an important aspect of our approach, we see the fact that benchmark circuits with different levels of testability can be evolved -- based on user requirements in terms of circuit structure, complexity and testability. We also proposed a methodology allowing to evaluate the quality of benchmark circuits using a standard approaches such as fault coverage measure. The result which we are submitting as an entry to the Humies 2008 competition, is the set of evolved benchmark circuits with predefined complexity and testability properties. This set of benchmark circuits can reveal potential bugs in CAD diagnostics testability validation tools much easier and faster that any other benchmark set proposed so far. It is important to say that we did not evolve circuits with required function; evolved circuits have the predefined testability properties in terms of their structural parameters. As the testability can be estimated in the polynomial time, it is possible to evaluate thousands of very complex candidate circuits in reasonable time. Thus, it is possible to evolve large benchmark circuits containing thousands of components (i.e. millions of gates after synthesis). Surprisingly, the complexity limit is not determined by ourevolutionary algorithm. There was no reason to evolve more comprehensive benchmarks because the commercial design tools we routinely use for the circuit design were not able to synthesize such large circuits. To summarize: D: The result (the set of benchmark circuits) was accepted as a new solution for design of synthetic benchmark circuits by one of prominent journals in the field of design and test of digital circuits and independently of the fact that it was mechanically created. G: Engineers have proposed various benchmark circuits in the area of digital circuits testing for many years. The main problem in their design is the need for simultaneous high complexity and controlled testability. Proposed benchmark circuits are the most complex circuits with a known level of testability. Hence the result solves a problem of indisputable difficulty in its field. (7) a full citation of the paper (that is, author names; publication date; name of journal, conference, technical report, thesis, book, or book chapter; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable): Pecenka, T., Sekanina, L., Kotasek, Z.: Evolution of Synthetic RTL Benchmark Circuits with Predefined Testability. ACM Transactions on Design Automation of Electronic Systems. 2008. ISSN 1084-4309, (accepted on January 27th, 2008), in press (8) a statement either that ?any prize money, if any, is to be divided equally among the co-authors? OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors: Any prize money, if any, should be divided equally among the co-authors. (9) a statement stating why the judges should consider the entry as ?best? in comparison to other entries that may also be ?human-competitive.? (a) The result is practically useful. (b) The result was accepted in the field of testing digital circuits in which an extremely high competition can be observed. The community of circuit designers and test oriented researchers has existed for more than 50 years. Many well-performing approaches have been proposed for this particular problem. Many commercial companies have worked in this area. It can be stated that the community is conservative and pragmatic with respect to completely new approaches and methodologies. (c) The result strongly benefits from the use of the evolutionary approach: As benchmark circuits are designed by means of the evolutionary algorithm, they can contain constructions which do not usually appear in the circuits designed by classical design techniques that are based on the principles of decomposition and minimization. Thus, the use of evolved benchmark circuits in the process of evaluating new software tools can reveal problems that remain hidden when conventional benchmark circuits are used. (d) We evolved the largest objects (i.e. circuits containing more than 1.2M gates after synthesis) that have probably been evolved ever.