Circuit Enumeration
People
Tim Todman, Haohuan Fu, Oskar Mencer. Affiliates: Wayne Luk.
Brief Introduction
This project tries to exploit parallelism in reconfigurable hardware and other technologies for efficient enumeration of the solution space of demanding problems.
Brute force enumeration is a complete departure from current practice of hand-designed arithmetic units and logic minimisation tools, if successful, the research will enable design automation of optimal hardware designs for arithmetic and other applications, as well as yielding theoretical insights about analytical properties of such designs.
We address the problem of identifying minimal circuits for a function by improving the upper and lower bounds of resources it can use.
We find the lower bound using global generation: in principle, generating every possible configuration of a device. In pratice, we use local symmetries to give the effect of exhaustive generation at reduced cost, using Field-Programmable Gate Array devices (FPGAs) for high-speed emulation of configurations and connections of look-up tables (LUTs).
We find the upper bound using logic decomposition, applying local generation on the components of the decomposition.
In the case we are lucky, global generation will uncover the minimum possible implementation. Otherwise, we get an improved measure of the bounds within which the optimal design must lie, as well as a locally optimized implementation.
Such tighter bounds can be used to evaluate the quality of heuristic solutions to the same problem, perhaps similar to the Shannon limit in information theory.
We break circuit generation into four steps, shown as the figure below. Steps 1 to 4 can run in software. We also implement step 4 in parallel hardware on FPGAs, relying on two key FPGA properties: (a) LUTs: FPGAs implement high-speed table look-up. (b) Massive parallelism: many instances of our designs run in parallel.
This project is funded by UK Engineering and Physical Sciences Research Council (grant number EP/C509625/1).
