Enhanced genetic algorithms and their application in retargetable code generation
This thesis connects two areas of research: genetic algorithms and code generation for embedded systems, primarily digital-signal processors. The first part of the thesis deals with enhancements that transform the canonical genetic algorithm into an effective mechanism for handling certain types of constraint-satisfaction problems. The enhanced genetic algorithm (EGA) works especially well when constraints are highly interrelated, and it allows efficient handling of larger problems than can be handled by other techniques. Specifically, the EGA promotes the mutation operator into a primary tool for directly attacking the cause of unsatisfied constraints. While this causes rapid convergence to a feasible region of the solution space, a new type of elitism maintains diversity in the population. This allows a variety of different feasible solutions to be generated. The first part of the thesis explains the enhancements and illustrates their effects on two classical problem: graph coloring; and integrated scheduling, module allocation, and binding in VLSI design. The second part of the thesis examines the use of EGAs in an important application area: code generation for parallel, highly encoded instruction sets, primarily DSPs. This problem has tightly interconnected subproblems that are each extremely complex and that interact in very subtle ways. A code generation methodology has been developed that uses the EGA as the basis for many, if not most, of the required optimizations. The thesis not only exhibits the use of EGAs in a large, highly constrained, realistic problem; it also examines a variety of strategies for using the EGA on a number of structurally different subproblems in code generation. The use of EGAs as the basis of optimization has enabled construction of a retargetable compiler, a code generator that applies the same methodology and algorithms to produce good quality code for a number of different processors.