Enhanced genetic algorithms and their application in retargetable code generation

dc.contributor.advisorWilson, Thomas
dc.contributor.advisorHayward, Gordon
dc.contributor.authorGrewal, Gary William
dc.degree.departmentSchool of Engineeringen_US
dc.degree.grantorUniversity of Guelphen_US
dc.degree.nameDoctor of Philosophyen_US
dc.description.abstractThis 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.en_US
dc.publisherUniversity of Guelphen_US
dc.rights.licenseAll items in the Atrium are protected by copyright with all rights reserved unless otherwise indicated.
dc.subjectgenetic algorithmsen_US
dc.subjectenhanced genetic algorithmen_US
dc.subjectcode generationen_US
dc.subjectembedded systemen_US
dc.subjectdigital-signal processorsen_US
dc.titleEnhanced genetic algorithms and their application in retargetable code generationen_US


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
13.24 MB
Adobe Portable Document Format