Abstract
This paper describes μGP, an evolutionary approach for generating assembly programs tuned for a specific microprocessor. The approach is based on three clearly separated blocks: an evolutionary core, an instruction library and an external evaluator. The evolutionary core conducts adaptive population-based search. The instruction library is used to map individuals to valid assembly language programs. The external evaluator simulates the assembly program, providing the necessary feedback to the evolutionary core. μGP has some distinctive features that allow its use in specific contexts. This paper focuses on one such context: test program generation for design validation of microprocessors. Reported results show μGP being used to validate a complex 5-stage pipelined microprocessor. Its induced test programs outperform an exhaustive functional test and an instruction randomizer, showing that engineers are able to automatically obtain high-quality test programs.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
R. M. Friedberg, “A learning machine: Part I,” IBM Journal of Research and Development, vol. 2, no. 1, pp. 2–13, 1958.
R. M. Friedberg, B. Dunham, and J. H. North, “A learning machine: Part II,” IBM Journal Research and Development, vol. 3, pp. 183–191, 1959.
J. R. Koza, “Genetic programming,” in Encyclopedia of Computer Science and Technology, A. Kent and J. Williams (Eds.), Marcel Dekker Publisher: New York, NY, USA, vol. 39, 1998, pp. 29–43, ISBN 0-8247-2292-2.
J. R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT-Press: Cambridge, MA, USA, 1992, ISBN 0-262-11170-5.
J. R. Koza, Genetic Programming II: Automatic Discovery of Reusable Programs, MIT-Press: Cambridge, MA, USA, 1994, ISBN 0-262-11189-6.
A. Fukunaga, A. Stechert, and D. Mutz, “A genome compiler for high performance genetic programming,” in Genetic Programming 1998: Proceedings of the 3rd Annual Conference, J. R. Koza, W. Banzhaf, K. Chellapilla, K. Deb, M. Dorigo, D. B. Fogel, M. H. Garzon, D. E. Goldberg, H. Iba, and R. L. Riolo (Eds.), Morgan Kaufmann Publishers: San Francisco, CA, USA, 1998, pp. 86–94.
S. Handley, “On the use of a directed acyclic graph to represent a population of computer programs,” in Proceedings of the 1994 IEEE World Congress on Computational Intelligence, IEEE: New York, NY, USA, 1994, pp 154–159.
R. Poli, “Evolution of graph-like programs with parallel distributed genetic programming,” Genetic Algorithms: Proceedings of the 7th International Conference, Thomas Back (Ed.), Morgan Kaufmann: San Francisco, CA, USA, 1997, pp. 346–353.
P. Nordin, “A compiling genetic programming system that directly manipulates the machine code,” in Advances in Genetic Programming, K. Kinnear (Ed.), MIT-Press: Cambridge, MA, USA, 1994, pp. 311–331.
P. Nordin and W. Banzhaf, “Evolving turing-complete programs for a register machine with self-modifying code,” in Genetic Algorithms: Proceedings of the 6th International Conference, L. Eshelman (Ed.), Morgan Kaufmann: San Francisco, CA, USA, 1995, pp. 318–327.
P. Nordin, W. Banzhaf, and F. Frantone, “Efficient evolution of machine code for CISC architectures using blocks and homologous crossover,” in Advances in Genetic Programming III, L. Spector (Ed.), MIT-Press: Cambridge, MA, USA, 1999, pp. 275–299.
E. Lukschandl, H. Borgvall, L. Nohle, M. Nordahl, and P. Nordin, “Evolving routing algorithms with the JBGP-system,” in Evolutionary Image Analysis, Signal Processing and Telecommunications: First European Workshop, EvoIASP'99 and EuroEcTel'99, R. Poli, H.-M. Voigt, S. Cagnoni, D. Corne, G. D. Smith, and T. C. Fogarty (Eds.), Springer-Verlag: Berlin, DE, 1999, pp. 193–202.
F. Corno, M. Sonza Reorda, G. Squillero, and M. Violante, “On the test of microprocessor IP Cores,” in IEEE Design, Automation & Test in Europe Conference, W. Nebel and A. Jerraya (Eds.), IEEE Computer Society: Los Alamitos, CA, USA, 2001, pp. 209–213.
F. Corno, G. Cumani, M. Sonza Reorda and G. Squillero, “Efficient machine-code test-program induction,” in Congress on Evolutionary Computation, D. B. Fogel, M. A. El-Sharkawi, X. Yao, G. Greenwood, H. Iba, P. Marrow, and M. Shackleton (Eds.), IEEE: Piscataway, NJ, USA, 2002, pp. 1486–1491.
W. Kantschik and W. Banzhaf, “Linear-Graph GP: A New GP Structure,” in Genetic Programming: 5th European Conference, J. A. Foster, E. Lutton, J. Miller, C. Ryan, and A. G. B. Tettamanzi (Eds.), Springer-Verlag: Berlin, DE, 2002, pp. 83–92.
F. Corno, G. Cumani, M. Sonza Reorda, and G. Squillero, “Evolutionary test program induction for microprocessor design verification,” in 11th Asian Test Symposium, IEEE Computer Society: Los Alamitos, CA, USA, 2002, pp. 368–373.
F. Corno, G. Cumani, M. Sonza Reorda, and G. Squillero, “Exploiting auto-adaptive μGP for highly effective test programs generation,” in 5th International Conference on Evolvable Systems: From Biology to Hardware (ICES2003), A. M. Tyrrell, P. C. Haddow, and J. Torresen (Eds.), Springer-Verlag: Berlin, DE, 2003, pp. 262–273.
F. Corno, G. Cumani, M. Sonza Reorda, and G. Squillero, “Automatic test program generation for pipelined processors,” in SAC03: 18th ACM Symposium on Applied Computing, H. Iwashita, S. Kowatari, T. Nakata, and F. Hirose (Eds.), ACM: New York, NY, USA, 2003, pp. 736–740.
F. Corno, G. Cumani, M. Sonza Reorda, and G. Squillero, “Fully Automatic Test Program Generation for Microprocessor Cores,” in DATE: IEEE Design, Automation & Test in Europe, N. Wehn and D. Verkest (Eds.), IEEE Computer Society: Los Alamitos, CA, USA, 2003, pp. 1006–1011.
A. L. Samuel, “Some studies in machine learning using the game of checkers,” IBM Journal of Research and Development, vol. 3, no. 3, pp. 210–229, 1959. Also available as: A. L. Samuel, “Some studies in machine learning using the game of checkers,” in Computers and Thought, E. A. Feigenbaum, and J. Feldman (Eds.), MIT Press: Cambridge, MA, USA, 1995, pp. 71–105.
G. Cabodi, S. Nocco, and S. Quer, “Improving SAT-based bounded model checking by means of BDDb-based approximate traversals,” in IEEE Design, Automation & Test in Europe Conference, N. Wehn and D. Verkest (Eds.), IEEE Computer Society: Los Alamitos, CA, USA, 2003, pp. 898–903.
H. H. Kwak, I. H. Moon, J. H. Kukula, and T. R. Shiple, “Combinational equivalence checking through function transformation,” in International Conference on Computer Aided Design, IEEE: Piscataway, NJ, USA, 2002, pp. 526–533.
J. Harrison, “Formal verification at Intel,” in IEEE Symposium on Logic in Computer Science, IEEE Computer Society: Los Alamitos, CA, USA, 2003, pp. 45–54.
B. Bentley, “Validating the Intel Pentium 4 microprocessor,” in Design Automation Conference, ACM: New York, NY, USA, 2001, pp. 244–248.
P. Mishra, H. Tomiyama, N. Dutt, and A. Nicolau, “Automatic verification of in-order execution in microprocessors with fragmented pipelines and multicycle functional units,” in DATE: IEEE Design, Automation & Test in Europe, C. D. Kloos and J. da-Franca (Eds.), IEEE Computer Society: Los Alamitos, CA, USA, 2002, pp. 36–43.
N. Utamaphethai, R. D. Blanton, and J. P. Shen, “Superscalar processor validation at the microarchitecture level,” in 12th IEEE International Conference on VLSI Design, IEEE Computer Society: Los Alamitos, CA, USA, 1999, pp. 300–305.
A. Chandra, V. Iyengar, D. Jameson, R. Jawalker, I. Nair, B. Rosen, M. Mullen, J. Yoor, R. Armoni, D. Geist, and Y. Wolfstal, “AVPGEN—a test generator for architecture verification,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, IEEE: New York, NY, USA, vol. 3, no. 2, 1995, pp. 188–200.
A. Aharon, A. Ba-David, B. Dorfman, E. Gofman, M. Leibowitz, and V. Schwartzburd, “Verification of the IBM RISC System/6000 by dynamic biased pseudo-random test program generator,” IBM Systems Journal, vol. 30, no. 4, pp. 527–538, 1991.
D. A. Patterson and J. L. Hennessy, Computer Architecture—A Quantitative Approach, 2nd edition, Morgan Kaufmann: CA, USA, 1996, ISBN 1-55860-329-8.
P. M. Sailer, and P. M. Sler, DLX Instruction Set Architecture Handbook, Morgan Kaufmann: CA, USA, 1996, ISBN 1-55860-371-9.
D. Van Campenhout, T. N. Mudge, and J. P. Hayes, “High-level test generation for design verification of pipelined microprocessors,” in Design Automation Conference, IEEE: Piscataway, NJ, USA, 1999, pp. 185–188.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by: Una-May O'Reilly
Rights and permissions
About this article
Cite this article
Squillero, G. MicroGP—An Evolutionary Assembly Program Generator. Genet Program Evolvable Mach 6, 247–263 (2005). https://doi.org/10.1007/s10710-005-2985-x
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10710-005-2985-x