A design framework and genetic algorithm for digital design optimisation on FPGAs

by Savage, Matthew James

Abstract (Summary)
Design tools of ever increasing power are required to keep pace with technological improvements in chip production. Chip capacities continually increase meaning that designs previously unfeasible become feasible. These designs are typically more complex and larger than their predecessors. Usually, the time available to a designer does not increase at the same rate. A designer is therefore tasked with a greater work load and a very limited amount of time. Design tools and automation are therefore necessary to compensate for this situation. The limiting characteristics of a design tool are its ease of use, the range of systems it can be applied to, and the quality of results obtained. Should a design tool lack in any of these three areas it will be of limited benefit. This work addresses only the quality of results obtained. While the other two are essential, they are unlikely to be relevant to a design tool if that tool is not adopted because the results were of insufficient quality. A design framework is proposed for the digital design of systems on FPGAs. This framework sets out the processes for producing a system specification of the design problem encountered, and then gives a procedure for processing that specification to produce a set of pareto-optimal designs in VHDL to implement the specification. The actual mapping of a specification to a VHDL design, is held in a mapping string that allows optimisation to be separated from other stages in the design framework. A new genetic algorithm, the Adaptive Speciation Genetic Algorithm (ASGA), is proposed featuring a customised selection, crossover, and mutation operator. This algorithm is assessed against other genetic algorithms from the literature on a knapsack problem and three digital design case studies. These case studies were the design of a parameter estimation circuit for a Self-Tuning Regulator (STR), the design of a Sum-of-Absolute- Difference (SAD) function for video motion detection problems, and the design of a five state Extended Kalman Filter (EKF). Results indicated that ASGA had good performance in all these problems. Through tests against other genetic algorithms, it was found the ASGA’s selection operator was inferior in some cases to that of the Pareto Envelope Selection Algorithm (PESA) by 3 Corne et al. By incorporating the selection operator of PESA performance improvements could be gained in the EKF problem.
Bibliographical Information:

Advisor:Professor Zoran Salcic; Associate Professor Grant Covic; Dr George Coghill

School:The University of Auckland / Te Whare Wananga o Tamaki Makaurau

School Location:New Zealand

Source Type:Master's Thesis

Keywords:genetic algorithm digital design fpga fields of research 280000 information computing and communication sciences 280200 artificial intelligence signal image processing 280212 neural networks algorithms fuzzy logic 290000 engineering technology 290900 electrical electronic 290902 integrated circuits


Date of Publication:01/01/2009

© 2009 All Rights Reserved.