Genetic Algorithms and Instruction Scheduling

Many difficulties are encountered when developing an instruction scheduler to produce efficacious code for multiple architectures. Heuristic-based methods were found to produce disappointing results; indeed the goals of validity and length compete. This lead to the introduction of another method to search the solution space of valid schedules: genetic algorithms. Their application to this domain proved fruitful. 1 Introduction This paper discusses some of the breadth of the work reported in depth in [Bea91]. Parts of the verbiage are common. It also extends the information contained in [BWJ90] Instruction scheduling involves choosing, from the large solution set of possible concurrent instructions, one packing that hopefully reduces both the execution time and the space of the program. The solution space may be viewed as an incomplete n-dimensional hypercube, where n is the number of operations to be performed. Each operation can be executed at a variety of locations in the code, and ..