Learning Systems Group

[back]

Learning in Hardware
Alexander Nicholson, Arrigo Benedetti, Yaser Abu-Mostafa, Pietro Perona

Abstract. We investigate the use of learning and adaptation for digital hardware design. We use reconfigurable hardware devices and discrete optimization methods to learn circuits from a set of examples. We have shown that this approach works well for the design of small arithmetic circuits and that significant performance improvements may be achieved by moving away from a strictly evolvable (genetic algorithms) approach.

Motivation. For real time signal processing and pattern recognition tasks, a software solution is often not fast enough. Reconfigurable hardware devices allow us to implement complex algorithms in hardware at low cost and on a small production scale. Leading FPGAs now comprise millions of gate equivalents, affording great computational power, but design of complex nonlinear or continuous mathematical circuitry is impractical. Evolvable hardware approaches attempt to facilitate design by automating parts of the process. We look at a more general hardware learning paradigm, applying general learning algorithms to the task of FPGA configuration for simple combinational circuit design and pattern recognition problems.

Research. We use the Xilinx 6200 Reconfigurable Processing Unit for experimentation with learning hardware. The Xilinx 6200 RPU has a public architecture, can be reconfigured in-circuit, and can be partially reconfigured. These make it singularly suitable for evolvable hardware applications. We look at the task of hardware design as a learning problem - we begin with a data set representing the problem we want to solve and look to extract a solution from it. Using input/output pairs, we attempt to find a good hardware configuration by exploring configuration space (within some constraints).

Figure 1

Using the Reactive Tabu Search (RTS) for optimization, we have shown that our hardware learning approach is able to learn arithmetic circuits that have low (<2%) error and use the hardware efficiently. We find circuits that perform the task well, yet do not obey conventional design constraints. Figure 1 illustrates one such circuit, learned to implement a 2-bit multiplier.

We compared RTS to a genetic algorithm (GA) for exploring circuit configurations. Using a 2-bit adder as the target, we found that RTS greatly outperformed the GA for similar CPU times. On a trial of 25 runs (each with 5500 seconds of execution time), the best GA performance was an error of 16%, whereas the RTS was able to find a perfect circuit, and averaged about 1.7% error.

We have done preliminary investigations of the scalability of this approach. As we add more resources, more correct circuits are implementable in the allocated chip area. However, the task of searching configuration space grows exponentially in the size of the circuit. Figure 2 illustrates this trade-off in one dimension.

Figure 2

Current results are primarily for small arithmetic circuits, but the advantages of learning hardware are for larger circuits and tasks which require complex or ill-defined computations (e.g. pattern recognition). Future work will apply this approach to small learning problems, and higher level approaches (functional level adaptation and hierarchical methods) to larger circuit design. For practicality, we will also investigate application of learning hardware to latest generation devices.

References/Publications

Evolution and Learning for Digital Circuit Design. Nicholson, A. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 519-524, San Francisco, 2000. Morgan Kaufmann Publishers.