Research: MicroGP

Description

The μGP is composed of three clearly separated blocks: an evolutionary core, an instruction library and an external evaluator. The evolutionary core cultivates a population of individuals. It uses auto-adaptation mechanisms, dynamic operator probabilities, dynamic operator strength, and variable population size. The instruction library is used to map individuals to valid assembly language programs. It contains a highly concise description of the assembly syntax or more complex, parametric fragments of code. Finally, the external evaluator simulates the assembly program, providing the necessary feedback to the evolutionary core.

Our earliest attempt to evolve test programs was presented in [date01]. The approach relied on a library of sharp fragments of code, called macros. The optimal sequence of macros was heuristically determined, and then a genetic algorithm optimized their parameters. The approach is quite effective, but hardly scalable. An Intel i8051, a very simple microprocessor, required 213 macros; and the macro list was carefully compiled by an experienced engineer in two working days.

The embryonic idea of the μGP was presented in [cec02]. The paper described a GP-like framework for generating assembly language program with simple instructions tightly connected with a directed acyclic graph. It implemented a straightforward (μ+λ) evolution, with no recombination, nor other enhancements. Remarkably, the overall structure resembled the linear graph GP, developed independently, and concurrently. Shortly after, the naïve approach was used in [ats02] for validating a microprocessor design, and provided effective results with moderate effort by human experts.

Afterwards, the μGP was slightly improved, adding recombination and auto-adaptation. At the same time, the evaluation procedure was expanded and the correlation with hardware strengthened. The enhanced methodology was used on different problems and the results of [date01] were easily outperformed. Paraphrasing Samuel, the μGP was eventually able to do what was needed to be done, without being told exactly how to do it ("Some Studies in Machine Learning Using the Game of Checkers", IBM Journal of Research and Development, 1959). This is true at least in the very specialized context of microprocessor validation.

In 2003, the whole μGP was rewritten from scratch. The latest prototype is in (almost) ANSI C and consists of about 6,500 lines on 29 files. It has the ability to exploit single instructions, complex macros, or their combination. Individual representation has been completely disconnected from assembly specification. The number of different nodes has been reduced, and their expressiveness increased. The directed acyclic graph representation has been transformed to handle generic directed cyclic graphs. A new abstraction level has been added, enabling support for subroutines and software interrupts.

The methodology has been successfully exploited for design validation and test against three different processors (see papers for details):

• Intel i8051 is an 8-bit microprocessor originally designed in the 80’s. Despite its relatively old age, the i8051 is one of the most popular microcontrollers in use today [ats02] [date03] [ices03].

• DLX/pII is a 5-stage pipelined version of the academic DLX microprocessor designed by Patterson and Hennessy [sac03].

• LEON P1754 is the commercial name of a synthesizable VHDL model of the 32-bit SPARC-V8 microprocessor [no published results, yet].

• PLASMA is a tiny microcontroller (almost) compatible with MIPS I™ [no published results, yet].

With respect to design validation it was used to induce test programs able to achieve very high statement coverage against RT-level descriptions of the i8051, the DLX/pII and the LEON.

With respect to test, the μGP approach was used to induce a test program able to attain high stuck-at fault coverage against a gate-level description of the i8051. Moreover, it was exploited to induce a test program attaining a very high gate-level toggle activity on a gate-level model of the DLX/pII.

Table summarizes the attained results on the three microprocessors in term of: gate-level statement coverage (SC%); gate-level toggle activity (TA%); and gate-level stuck-at fault coverage (FC%). Rows labeled "μGP" report figures attained by a trhe μGP; rows labeled "RND" show results attainable by a random or pseudo-random methodology; rows labeled "ALT" report results achieved by an alternative approach.

	SC [%]	TA [%]	FC [%]
i8051	μGP	99.7		90.77
	RND	95.0		85.19
	ALT	99.1		62.93
DLX/pII	μGP	94.59	87.51
	RND	78.87	19.59
	ALT	80.59	32.59

The table is reported to provide a qualitative summary, the exact meaning of both figures and captions depends on the goal and on the microprocessor targeted.

Acknowledgements

Papers

1. Efficient Machine-Code Test-Program Induction
   F. Corno, G. Cumani, M. Sonza Reorda, G. Squillero
   CEC2002: Congress on Evolutionary Computation, Honolulu, Hawaii (USA), pp. 1486-1491
2. Evolutionary Test Program Induction for Microprocessor Design Verification
   F. Corno, G. Cumani, M. Sonza Reorda, G. Squillero
   ATS2002: IEEE Asian Test Symposium, Guam (USA), November 2002, pp. 368-373
3. Fully Automatic Test Program Generation for Microprocessor Cores
   F. Corno, G. Cumani, M. Sonza Reorda, G. Squillero
   DATE2003: Design, Automation and Test in Europe, Munich, Germany, March 3-7, 2003, pp. 1006-1011
4. Automatic Test Program Generation for Pipelined Processors
   F. Corno, M. Sonza Reorda, G. Squillero
   SAC2003: The Eighteenth Annual ACM Symposium on Applied Computing, Melbourne, Florida (USA), March 9-12, 2003, pp. 736-740
5. Exploiting Auto-Adaptive µGP for Highly Effective Test Programs Generation
   F. Corno, G. Squillero
   ICES2003: The 5th International Conference on Evolvable Systems: From Biology to Hardware, Trondheim (Norway), March 17-20, 2003, pp. 262-273
6. An Enhanced Framework for Microprocessor Test-Program Generation
   F. Corno, G. Squillero
   EUROGP2003: 6th European Conference on Genetic Programming, Essex (UK), April 14-16, 2003, pp. 307-315
7. Code Generation for Functional Validation of Pipelined Microprocessors
   F. Corno, G. Squillero, M. Sonza Reorda
   ETW03: 8th IEEE European Test Workshop (Formal Proceedings), The Netherlands, May 25��28, 2003, pp. 113-118
8. Exploiting Co-Evolution and a Modified Island Model to Climb the Core War Hill
   F. Corno, E. Sanchez, G. Squillero
   CEC03: 2003 IEEE Congress on Evolutionary Computation, Canberra, Australia, 8th - 12th December 2003, pp. 2222-2229
9. Exploiting HW Acceleration for Classifying Complex Test Program Generation Problems
   E. Sanchez, G. Squillero, M. Violante
   of Evolutionary Computing: EvoWorkshops 2004 proceedings, Coimbra (Portugal), April 5-7 2004, pp. 230-239
10. Automatic Test Program Generation - a Case Study
    F. Corno, E. Sanchez, M. Sonza Reorda, G. Squillero
    IEEE Design & Test, Special issue on Functional Verification and Testbench Generation, Volume: 21, Issue 2, March-April 2004, pp. 102-109
11. On The Evolution of Corewar Warriors
    F. Corno, E. Sanchez, G. Squillero
    CEC2004, Congress on Evolutionary Computation, Portland (Oregon), June 20-23, 2004, pp. 2365-2371
12. A Local Analysis of the Genotype-Fitness Mapping in Hardware Optimization Problems
    E. Sanchez, G. Squillero, M. Violante
    CEC2004, Congress on Evolutionary Computation, Portland (Oregon), June 20-23, 2004, pp. 871-878
13. Code Generation for Functional Validation of Pipelined Microprocessors
    F. Corno, E. Sanchez, M. Sonza Reorda, G. Squillero
    Journal of Electronic Testing: Theory and Applications, Vol 20(3), June 2004, pp. 269-278
14. Automatic Test Programs Generation Driven by Internal Performance Counters
    W. Lindsay , E. Sanchez, M. Sonza Reorda, G. Squillero
    MTV'04: 5th International Workshop on Microprocessor Test and Verification, pp. 8-13
15. Coupling Different Methodologies to Validate Obsolete Microprocessors
    L. Anghel, E. Sanchez, M. Sonza Reorda, G. Squillero, R. Velazco
    DFT'04: The 19th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems
16. Automatic Verification of RT-Level Microprocessor Cores Using Behavioral Specifications: a Case Study
    L. Anghel, E. Sanchez, M. Sonza Reorda, G. Squillero, R. Velazco
    XIX Conference on Design of Circuits and Integrated Systems, Bordeaux, France, November 24-26, 2004
17. Automatic Test Program Generation for Verifyng Microprocessors
    F. Corno, E. Sanchez, M. Sonza Reorda, G. Squillero
    IEEE Potentials, Vol 24, Issue 1, Feb-Mar 2005, pp. 34-37
18. Automatic Completion and Refinement of Verification Sets for Microprocessor Cores
    E. Sanchez, G. Squillero, M. Sonza Reorda
    Lecture Notes in Computer Science, Vol 3449, "Applications on Evolutionary Computing: EvoWorkkshops 2005", Lausanne (CH), March 2005, pp. 205-214
19. MicroGP - An Evolutionary Assembly Program Generator
    G. Squillero
    Genetic Programming and Evolvable Machines, vol. 6, no. 3, 2005, pp. 247-263
20. Evolving Assembly Programs: How Games Help Microprocessor Validation
    F. Corno, E. Sanchez, G. Squillero
    IEEE Transactions on Evolutionary Computation, Special Issue on Evolutionary Computation and Games, Dec. 2005, vol. 9, pp. 695-706
    SILVER MEDAL at the Human-Competitive Awards 2005 (HUMIES)
21. New Evolutionary Techniques for Test-Program Generation for Complex Microprocessor Cores
    E. Sanchez, M. Schillaci, M. Sonza Reorda, G. Squillero, L. Sterpone, M. Violante
    GECCO05: Genetic and Evolutionary Computation Conference, Washington, DC, USA, June 25-29 2005, pp. 2193-2194
22. Automatic Generation of Test Sets for SBST of Microprocessor IP Cores
    E. Sanchez, M. Sonza Reorda, G. Squillero, M. Violante
    SBCCI 2005, 18th IEEE Symposium on Integrated Circuits and Systems Design, pp. 74-79
23. An Effective Technique for Minimizing the Cost of Processor Software-Based Diagnosis in SoCs
    P. Bernardi, E. Sanchez, M. Schillaci, G. Squillero, M. Sonza Reorda
    IEEE DATE2006: Design, Automation and Test in Europe, 2006, pp. 412-417
    BEST PAPER AWARD at IEEE DATE 2006
24. An Automated Methodology for Cogeneration of Test Blocks for Peripheral Cores
    L. Bolzani, E. Sanchez, M. Schillaci, M. Sonza Reorda, G. Squillero
    IOLTS2007: IEEE International On-Line Testing Symposium, 2007, pp. 265-270
25. On the Automatic Generation of Test Programs for Path-Delay Faults in Microprocessor Cores
    P. Bernardi, M. Grosso, E. Sanchez, M. Sonza Reorda
    ETS2007: 12th IEEE European Test Symposium, Freiburg, Germany, 2007, pp. 159 - 164
26. Evolutionary Techniques Applied to Hardware Optimization Problems: Test and Verification of Advanced Processors
    E. Sanchez, G. Squillero
    [chapter in] Studies on Computational Intelligence, Vol 66, Advances in Evolutionary Computing for System Design, edited by Lakhmi C. Jain, Vasile Palade and Dipti Srinivasan, Springer publisher, 2007, ISBN 978-3-540-72376-9, pp. 83-106.
27. Test Program Generation From High-level Microprocessor Descriptions
    E. Sanchez, M. Sonza Reorda, G. Squillero
    [chapter in] Test and validation of hardware/software systems starting from system-level descriptions, Edited by M. Sonza Reorda, M. Violante, Z. Peng, Springer publisher, 2005, 179 p, ISBN: 1-85233-899-7, pp. 83-106
28. An Evolutionary Methodology for Test Generation for Peripheral Cores Via Dynamic FSM Extraction
    D. Ravotto, E. Sanchez, M. Schillaci, and G. Squillero
    4th European Workshop on Bio-Inspired Heuristics for Design Automation (EvoHOT2008), March 26-28, 2008, Napoli, Italy, pp. 214-223

Download Information

• ugp-2.7.0-beta.tar.gz (the source code on 3-march-2004)
• MicroGP-1003.pdf (an outdated introduction)

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

Related topics

• Genetic Algorithms

Researchers

Contact information

© Copyright Politecnico di Torino webmaster@www.cad.polito.it (/research/microgp.html - 11-Nov-2007)