Evolutionary Synthesis of VLSI Circuits with Fault Complementing

摘要

The synthesis of VLSI circuits provides a challenging problem for CAD designers. This is due the continuous increase in the complexity of such circuits and the discontinuous nature of the search space associated with their synthesis. This complexity is further increased when CAD tools are required to provide designs under a number of criteria. For example, synthesis for power as well as area and speed constraints. Genetic Algorithms (GAs) have been successfully used for the synthesis of VLSI circuits under multiple design constraints . One problem with most search techniques including genetic algorithms is being trapped in local minima, which significantly delays the search process. Authors in the literature have proposed a number of techniques for overcoming this problem. These mainly suggest the modification of genetic operators and/or the adoption of specialised selection strategies. However, experience shows that a genetic algorithm performs best when problem specific techniques are incorporated within their operators. Examples are [6] and [7]. Experience shows mat most GA based synthesis systems reach a circuit, which is 80-90% correct within the first 10% of the total GA runtime. The rest of the time is spent in identifying the portion of the circuit responsible for the remaining 20-10%. This leads to a significant increase in the synthesis time. In this paper the authors report on a technique for overcoming this delay, hence enabling a GA to reach a solution within a relatively short time, when compared to conventional GA based approaches to the synthesis problem. The technique is based on identifying a group of individuals, which dominate the population of the GA at an early stage. This is followed by a process of identifying input sequences which lead to a faulty output state and complementing these via a process which involves the use of XOR gates. These designs are fed back to the population of the GA, which carries on with the evolution process. During this process the GA utilises additional optimisation functions mainly for reducing area and operation time inflected at the fault complementing stage.