MicroGP

MicroGP QR Code µGP (MicroGP) is a versatile optimizer able to outperform both human experts and conventional heuristics in finding the optimal solution of hard problems. Given a task, it first fosters a set of random solutions, then iteratively refines and enhance them. Its heuristic algorithm uses the result of the evaluations, together with other internal information, to efficiently explore the search space, and eventually to produce the optimal solution. µGP has been devised in 2002, and subsequently developed thanks to the effort of several people.

µGP original application was the creation of assembly-language programs for testing different microprocessors, hence the Greek letter µ (micro) in its name. Afterward, it has been used on a wider range of problems, such as: creation of test programs for pre- and post-silicon validation; design of bayesian networks; creation of mathematical functions represented as trees; integer and combinatorial< optimization; real-value parameter optimization; and even creation of corewar warriors.

µGP is an evolutionary algorithm, hence the acronym GP (genetic programming) in its name. A population of different solutions is considered in each step of the search process, and new individuals are generated through mechanisms that ape both sexual and asexual reproduction. New solutions inherit distinctive traits from existing ones, and may coalesce the good characteristics of different parents. Better solutions have a greater chance to reproduce and to succeed in the simulated struggle for existence.

The current implementation is version 3, also known as µGP3, ugp3 (due to typographic limitations) and MicroGP++ (being written in C++). It can be redistributed and modified under the terms of the GNU General Public License. Please, refer to http://ugp3.sourceforge.net/ for download links and additional documentation.

 

Related papers and other material

  1. Artificial evolution in computer aided design: from the optimization of parameters to the creation of assembly programs
    G. Squillero
    Computing, Special Issue on Bio-inspired Computing, Volume 93, Numbers 2-4, 103-120
  2. Automatic generation of software-based functional failing test for speed debug and on-silicon timing verification
    E. Sanchez, G. Squillero, A. Tonda
    MTV11: International Workshop on Microprocessor Test and Verification
  3. Post-Silicon Failing-Test Generation through Evolutionary Computation
    E. Sanchez, G. Squillero, A. Tonda
    19th IFIP/IEEE International Conference on Very Large Scale Integration (VLSI-SoC)
  4. Post-Silicon Functional Failing-Test Generation through Evolutionary Computation
    E. Sanchez, G. Squillero, A. Tonda
    ETS2005: IEEE European Test Symposium, 2005
  5. Evolutionary Optimization: the µGP toolkit
    E. Sanchez, M. Schillaci, G. Squillero
    Hardcover, ISBN 978-0-387-09425-0 / 1st Edition., 2011, XIII, 178 p.
  6. Microprocessor Software-Based Self-Testing.
    M. Psarakis, D. Gizopoulos, E. Sanchez, M. Sonza Reorda
    IEEE Design & Test of Computers, May/June 2010, pp. 4-18
  7. A hardware accelerated framework for the generation of design validation programs for SMT processors
    D. Ravotto, E. Sanchez, M. Sonza Reorda
    IEEE Design and Diagnostic of Electronic Circuits and Systems, Vienna, April 2010, pp. 289-292
  8. Automatic Detection of Software Defects: an Industrial Experience
    S. Gandini, D. Ravotto, W. Ruzzarin, E. Sanchez, G. Squillero, A. Tonda
    GECCO 2009: Proceedings of the 2009 GECCO conference on Genetic and evolutionary computation, Montreal, Quebec (Canada), pp: 1921-1922
  9. EA-Based Test and Verification of Microprocessors
    G. Squillero
    GECCO 2008: Proceedings of the 2008 GECCO conference companion on Genetic and evolutionary computation, Atlanta, GA (USA)
    Tutorial
  10. A novel methodology for diversity preservation in evolutionary algorithms
    G. Squillero, A. Tonda
    GECCO 2008: Proceedings of the 2008 GECCO conference companion on Genetic and evolutionary computation, Atlanta, GA (USA)
  11. An Evolutionary Methodology for Test Generation for Peripheral Cores Via Dynamic FSM Extraction
    D. Ravotto, E. Sanchez, M. Schillaci, G. Squillero
    4th European Workshop on Bio-Inspired Heuristics for Design Automation (EvoHOT2008), March 26-28, 2008, Napoli, Italy, pp. 214-223
  12. Methodologies for Test Program Generation Exploiting Simulation Feedback
    G. Squillero
    Technion - Israel Institute of Technology, Haifa, Israel
    Tutorial
  13. 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.
  14. Coupling EA and High-level Metrics for the Automatic Generation of Test Blocks for Peripheral Cores
    L.Bolzani, E. Sanchez, M. Schillaci, G. Squillero
    GECCO2007: Genetic and Evolutionary Computation Conference, London, UK, July 7-11, 2007, pp. 1912-1919
  15. 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. 179 - 184
  16. 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
  17. 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
  18. Anatomy of an extensible evolutionary tool
    E. Sanchez, M. Schillaci, G. Squillero
    GSICE2: II Giornata di Studio Italiana sul Calcolo Evoluzionistico, 2006
  19. 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
  20. 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
  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. 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)
  23. MicroGP - An Evolutionary Assembly Program Generator
    G. Squillero
    Genetic Programming and Evolvable Machines, vol. 6, no. 3, 2005, pp. 247-263
  24. 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
  25. 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
  26. 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
  27. 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
  28. 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
  29. 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
  30. 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
  31. 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
  32. 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
  33. 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
  34. 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
  35. 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
  36. 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
  37. 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
  38. 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
  39. 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
  40. 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
  41. 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

Contact information

Giovanni Squillero
Politecnico di Torino
Dipartimento di Automatica e Informatica
Corso Duca degli Abruzzi 24
I-10129 Torino
ITALY
Tel: +39-011564.7186
Fax: +39-011564.7099
E-mail: giovanni . squilleroat polito.it
Personal web page: http://www.cad.polito.it/staff/squillero/
Politecnico info page: http://www.dauin.polito.it/en/personale/scheda/(matricola)/003584