Configurable decoders with application in fast partial reconfiguration of FPGAs

A decoder is a hardware module that expands an x-bit input into an n-bit output, where x << n. It can be viewed as producing a set S of subsets of an n-element set Zn. If this set S can be altered by the user, the decoder is said to be configurable. We propose a class of configurable decoders (called "mapping-unit" based decoders or simply MU-decoders) that facilitate efficient selection of elements in an FPGA (in general, in any chip). Conventional solutions for this selection use either (a) a fixed (non-reconfigurable) decoder that lacks the flexibility to generate many subsets quickly, or (b) a large look-up table (LUT) which is flexible, but too expensive. The proposed class of MU-decoders have much of the flexibility of the large-LUT solution (also called a LUT decoder here) at the cost of the fixed decoder solution. Specifically, we show that for any fixed gate cost, the a MU-decoder can produce any set of subsets that the LUT decoder can; in addition, the MU-decoder can exploit any available structure in the application at hand to produce many more subsets than the LUT decoder. We illustrate this ability in the context of totally ordered sets of subsets