This work centers on the application of Genetic Algorithms (GA) to the high-level synthesis of VLSI (Very Large Scale Integration - a term used to describe complex microchips) devices. Synthesis is the process of converting a high-level algorithm or process description into a microchip implemented on silicon. Basically a synthesis tool takes the initial idea and turns it into a practical silicon chip. This is an extremely complex process that requires many different levels of design. At each level of the design factors affecting area - speed - power - delay - cost, etc have to be considered. Each factor impacts on the others, for example a high speed implementation may require a large area, affecting cost, reliability, etc. The designer must 'trade-off' these factors against each other to achieve an optimum solution that satisfies the initial design criteria.
The work specifically targets minimising the power consumption of VLSI devices. Power consumption, which directly affects device heat, is becoming a major factor in VLSI design. We all have heatsinks and fans within our PCs, this cooling equipment increases the cost of the processing devices. Even small price differences have a large effect on competitiveness in the silicon chip market. Excessive heating of a device will reduce its operating lifetime and cause the device to fail. Another influence on low power requirements is the current boom in the portable computing market. These systems operate off a battery with a fixed operating time. If the power consumption of these portable computers can be reduced the operating lifetime can be increased without modifying the battery size. In conclusion, low power is a very desirable criteria for VLSI devices. Unfortunately it is also a difficult criteria to achieve. The complexity of VLSI synthesis has already been mentioned. The techniques used for high level power reduction further complicate the synthesis problem, the problem becomes intractable. An intractable problem, simply, is a problem for which no algorithm can be developed to quickly find the best solution. These problems require a search of all the possible solutions, comparing the solutions to determine which is the best. Such a process is very time consuming and impractical for most problems, therefore an efficient search algorithm is required, enter the Genetic Algorithm.
The Genetic Algorithm is a search and optimisation tool modeled on the biological process of natural selection. If we consider biology, we can consider the problem as 'living on planet earth'. The population of solutions is the wide array of species on planet earth. Most people would say that evolution, natural selection has produced humans as the 'best' solution to this problem. Of course, we could just be an intermediate solution on the way to the best solution. Our genetic makeup has been created over generations of reproduction (combination of parents genetic material) and mutation (random changing of our genetic codes). These processes give rise to new solutions that have different characteristics to other solutions. Some method is required to gauge the quality of solutions, a 'fitness' function. The fitness of each solution is a score indicating how well that solution performs under the 'living on planet earth' criteria. For example, our opposable thumb enables us to grab objects and use them. Animals without such a feature would have a lower fitness. Higher fitness solutions have a greater chance of reproducing (natural selection), therefore better solutions will breed a greater number of even better solutions. This is an extremely simple look at the Genetic Algorithm process.
A software Genetic Algorithm consists of a population of solutions to a particular problem. A fitness function is used to score each individual. Using probability functions those with the highest fitness have the highest chance of reproducing, producing children for the next population of solutions, the next generation. The GA process terminates when a solution matching all the problem criteria has been found.
Why use the GA for low power synthesis? The GA has been used in different areas of VLSI synthesis with encouraging results. The complexity of the low power synthesis problem makes it ideal for an efficient search algorithm like the GA.
The research involves the development of software to implement a synthesis tool capable of producing low power implementations of Digital Signal Processing (DSP) algorithms. These algorithms are widely used in telecommunications, speech processing, CD manufacture, games machines, etc. The core of the software consists of a Genetic Algorithm applying known power minimisation techniques to a population of candidate DSP solutions. The software has been developed in Microsoft's Visual C++ on a PC running Windows 95. It has been designed to be portable to other systems such as UNIX. The research involves analysis of low-power design techniques for VLSI systems, development of CAD tools for high-level synthesis and integration of artificial intelligence techniques with advanced engineering design methodologies.
Publications
Work to date and results have been reported in the following publications :
The results demonstrate that the GA can modify high-level DSP algorithms to produce low power versions. This research was towards my PhD, which was completed in October 1998. The research was funded by a studentship from the EPSRC and performed within the Circuits and Systems Group at Cardiff University Of Wales.
Please e-mail me with any comments or suggestions - [email protected]