Motivation and framework for using genetic algorithms for microcode compaction

ABSTRACT

Genetic algorithms are a robust adaptive optimization technique based on a biological paradigm. They perform efficient search on poorly-defined spaces by maintaining an ordered pool of strings that represent regions in the search space. New strings are produced from existing strings using the genetic-based operators of recombination and mutation. Combining these operators with natural selection results in the efficient use of hyperplane information found in the problem to guide the search. The searches are not greatly influenced by local optima or non-continuous functions. Genetic algorithms have been successfully used in problems such as the traveling salesperson and scheduling job shops. Microcode compaction can be modeled as these same types of problems, which motivates the application of genetic algorithms in this domain.

REFERENCES

• All86: Vicki Hurst Allan, A critical analysis of the global optimization problem for horizontal microcode (phase-coupled, compaction, code motion, compilation), 1986
• BDM+88: S.J. Beaty, M.R. Duda, R.A. Mueller, P.H. Sweany, and J Varghese. "Optimization issues for a retargetable microcode compiler". MicroArch, 3(1):5-15, December 1988.
• Boo87: L. Booker. "Improving search in genetic algorithms". In Lawrence Davis, editor, Genetic Algorithms and Simulated Annealing, pages 61-73. Morgan Kaufmann, 1987.
• CS89: Gary A. Cleveland , Stephen F. Smith, Using genetic algorithms to schedule flow shop releases, Proceedings of the third international conference on Genetic algorithms, p.160-169, December 1989, George Mason University, United States
• DeJ86: K. DeJong. An Analysis of Reproduction and Crossover in a Binary - coded Genetic Algorithm. PhD thesis, University of Michagan, Ann Arbor, 1986.
• Fis81: J.A. Fisher. "Trace scheduling: A technique for global microcode compaction". IEEE Transactions on Computers, C- 30(7):478-490, July 1981.
• Gol89: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• HMS87: Michael A. Howland , Robert A. Mueller , Philip H. Sweany, Trace scheduling optimization in a retargetable microcode compiler, Proceedings of the 20th annual workshop on Microprogramming, p.106-114, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255325]
• Hol75: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• LDSM80: David Landskov , Scott Davidson , Bruce Shriver , Patrick W. Mallett, Local Microcode Compaction Techniques, ACM Computing Surveys (CSUR), v.12 n.3, p.261-294, Sept. 1980 [doi>10.1145/356819.356822]
• Nic85: Alexandru Nicolau, Percolation Scheduling: A Parallel Compilation Technique, Cornell University, Ithaca, NY, 1985
• Rob79: E.L. Robertson. "Microcode Bit Optimization is NP-complete". IEEE Transactions on Computers, C-28(4):316-319, April 1979.
• Sys90: Gilbert Syswerda. "Schedule optimization using genetic algorithms". In L. Davis, editor, The Genetic Algorithms Handbook. 1990.
• Veg82: Steven Roger Vegdahl, Local code generation and compaction in optimizing microcode compilers, 1982
• WSF89: Darrell Whitley , Timothy Starkweather , D'Ann Fuquay, Scheduling problems and traveling salesman: the genetic edge recombination, Proceedings of the third international conference on Genetic algorithms, p.133-140, December 1989, George Mason University, United States
• WSS90: D. Whitley, T. Starkweather, and D. Shaner. "The traveling saleman and sequence scheduling quality solution using genetic edge recombination". In L. Davis, editor, The Genetic Algorithms Handbook, 1990.