Compucology.net

by Craig Webster and Harshy Wanigasekara-Mohotti

When it comes to the highest performance custom computer chips humans remain the best designers around. But the exponential increase in complexity of each new generation of chip means that this may not be the case for much longer. Genetic algorithms are powerful design tools which mimic the processes of evolution and may offer an important new approach for solving a number of imminent problems of chip design.

Component density

As components shrink in size and more complicated chip composition techniques are used, such as an increased numbers of layers, the problem of arriving at an optimal circuit layout becomes proportionately more difficult. The best chip design will use a component layout which will allow it to hold as many components as technologically possible. Partly to achieve this and partly to allow the chip to operate at high speeds, the length of circuits connecting individual chip components must be as short as possible – since long connecting circuits slow signals within the chip. This kind of optimisation problem is one which is very familiar to mathematics where it is called the Travelling Salesman Problem. Substituting cities and travelling distances for chip components and connecting circuits, the Travelling Salesman Problem (TSP) is stated in deceptively simple terms: what is the shortest route allowing each of a number of cities on a map to be visited only once, thus saving the travelling salesman fuel and travelling time? The most intuitive way of finding the optimally shortest route is to add up the distances between cities for every possible visiting order. However, as the number of cities increases the number of possible visiting orders explodes. The time it would take to solve the problem by this initially intuitive method therefore rapidly becomes unreasonably long. For large TSPs the time required can often be longer than the lifetime of the programmer and with the addition of just a few more cities can require longer than the lifetime of the universe! The problem is complicated further in chip design since the cities are not fixed and can be moved around. Currently a number of rules of thumb exist for solving this problem, but it is unclear how long these methods will remain effective with the increasing component density of new generation chips. A few years from now integrated circuits the size of your fingernail will routinely contain one billion transistors, and require a design as complex as a road map of the entire planet.

The bit rot problem

An additional difficulty which must be faced in the next few years of chip design is the problem of background radiation corrupting the bits stored in individual transistors as these components get progressively smaller. Up until recently background radiation was not a problem for the functional integrity of transistors, but a critical threshold is now being approached where normal environmental radiation has a significant chance of delivering enough energy to change the state of individual transistors. This effect has been called hardware bit rot and can cause anything from corrupted data to software crashes. Aircraft and other high altitude technology are at considerably higher risk of experiencing bit rot since normal background radiation is higher at higher altitudes. A proposed solution to this problem is to store every bit of information on a chip on two transistors rather than one, effectively giving each transistor a backup of its contents should bit rot occur. While this doubling up of transistors may solve the bit rot problem it means that at most only half of the transistors on a chip will be doing any actual work. Ideally a less wasteful parity checking scheme may be possible, but this further complicates the overall design of the chip.

Genetic algorithm design

Genetic Algorithms (GAs) are powerful general purpose design tools which mimic the process of natural selection by setting up a population of artificial “organisms” and allowing them to evolve based on selection pressures defined by the user. To produce a chip design with components arranged in an optimal manner using GAs we would create a population of chip patterns which initially had randomly arranged components. Each in turn would then be scored according to the number of components accommodated and the total length of connecting circuits. Individual chip patterns with the most components and the shortest circuits would get the highest score. The variation inherent in the initially random population of patterns would ensure that some designs scored better than others. These scores would then become the fitness measures of the individual chip designs and would dictate the proportional make-up of the next generation. The most fit designs would be disproportionately represented in the next generation, while those poorer scorers would be under-represented or drop out of the population altogether.

A process where features of the design of individual chips are swapped between pairs ranked in order of fitness-scores is then typically used. This produces a composite design from each pair and is the artificial version of sexual reproduction. Each pair of chip designs can be considered the parents of each composite child. This is an effective method of mixing design features to produce composite children some of which will score better than their parents. Intermittently, small random variations in selected chip features are also typically used during reproduction; this adds noise to the process and by doing so helps increase the efficiency of convergence on an optimal chip design. This is the artificial version of genetic mutation. The next generation of chip designs is then scored on component density and circuit length and the process repeated. After a large number of generations this test-and-reproduce cycle will move the overall population of chip designs in the direction of the optimally designed chip as only the highest scoring designs in each generation will survive in to the next. Eventually a chip design will be created which gains a very good score and this design can then be used for chip manufacture in the conventional manner.

GAs are not limited to solving layout optimisation problems. By incorporating other selection pressures into the artificial evolutionary process other design problems can be solved. For example, the bit rot problem could be tackled by simulating the kind of bit corruption caused by radiation in the population of chip designs during the scoring phase. Chips would get extra points for continuing to perform well despite this abuse. Eventually a robust design would be expected to evolve which was resistant to certain types of bit rot.

One of the most attractive advantages of using GAs as design tools is their ability to find solutions to problems in a way completely free of preconceptions about what is possible and what is not. This is something that human designers find very difficult. This ability of GAs was highlighted in 1997 by Adrian Thompson, a researcher at the University of Sussex (1,2), who used GAs to design a specialised chip capable of a difficult signal discrimination task. The resulting circuit was three times more efficient than even he thought possible, requiring only 32 of the 100 logic gates assigned to the task. A chip designed by a human, says Thompson, would have required 10 to 100 times as many logic elements to be successful.

The relatively recent availability of cheap, fast computing power has made GA methods more accessible than ever before. Their usefulness and efficiency for solving hard design and optimisation tasks is only beginning to be fully realised. The increasingly difficult problems faced by chip designers has resulted in electronics being one of the first engineering fields to adopt GA methods, albeit currently only at the high-end research level. Their use is bound to become more widespread in electronics as well as many other fields where hard design problems exist.

Harshy Wanigasekara-Mohotti is a software engineer at C-Cube Microsystems, California.

References
1. Taubes G. Evolving a conscious machine. Discover 1998; 19(6): 72-79.
2. Davidson C. Creatures from primordial silicon. New Scientist 1997; 156(2108): 30-34.