Evolutionary Design for Novel Technologies

Adrian Thompson

Top-down design defers detailed implementation considerations to as late as possible in the design process. This abstraction helps large and complex systems to be designed. However, details of the target medium must be taken into account at some stage. This typically happens in the painstaking design of a library of simple `standard cells', that closely exploit the properties of the particular medium, allowing a relatively easy technology mapping from an abstract design to an implemented system.

Evolutionary algorithms seem well suited to the design of standard cells. The cells are simple, so within the reach of contemporary evolutionary methods. Experiments have shown that if evolution is allowed to manipulate a circuit at a fine level of detail, and without prejudicial constraints, then it can produce circuits exploiting the physical medium in sophisticated and subtle ways that would be hard for a human designer to derive [1,2]. It should also be possible to integrate non-behavioural requirements such as size, power-consumption, or fault-tolerance, into the goals of the evolutionary process [1].

The ability of evolution to find forms and processes well-tailored to the medium, and to produce designs that might be counter-intuitive, surprising, or educational, could help find design-styles (or cell libraries) for novel technologies. As exotic media based on quantum physics or biochemistry are proposed, it is not immediately clear how best they could be used. Here I present a simple study: the evolution of a NOR-gate in a meso/nano-scale medium based on few/single-electron effects in tunnel junctions [3].

A single design issue is isolated to be addressed: resulting from their unavoidably high resistance, tunnel junctions cannot simply be connected together by wires as in normal semiconductor VLSI [4]. Ideally, all components would only interact with their spatial neighbours, so that no wires would be needed; this is a major design challenge, and has prompted proposals for cellular-automata-like architectures. In this experiment, there is a two-dimensional array of nodes, with components between them. The components can be a tunnel junction, a capacitance, none, or a `virtual wire'. A virtual wire connecting two nodes actually amalgamates them into one: the final circuit could be constructed without wires by deforming the regular 2-D array to push the necessary components together. This results in a circuit not needing wires, but not as constrained in architecture as a regular 2-D array.

In other respects, the experiment was unrealistic. Fitness evaluations were in a simulation [5] at 0K, neglecting co-tunnelling. A possibly inappropriate I/O signal representation, power-supply arrangement, and modelling of input coupling and output load was used, and no pure resistances were provided. The result from a GA (population 30, natural problem representation, real-valued encoding, 2529 generations) does work as a NOR gate (Figs 1,2) within this model, displays a$\pm$10% tolerance on resistances and capacitances, and has the desired locality property.

This experiment is very preliminary, but illustrates one way that evolutionary design techniques may help novel technologies to become viable.

Figure: The evolved NOR gate. All junction resistances are 100k$\Omega$, all capacitances were under evolutionary control.

Figure 2: Performance over an evolutionary evaluation. The inputs are shown dashed and dotted, the output solid. Output is from SIMON - Simulation of Nano Structures - Christoph Wasshuber

 
 

1999-03-02