On Lookup Table Cascade-Based Realizations of Arbiters

LUT cascades, Multi-Terminal BDDs, iterative disjunctive decomposition, arbiter circuits

Design of digital systems with a degree of regularity in physical placement of subsystems and in their interconnection has always been a much desired goal and is even more so at present. A regular logic has advantages which make it more attractive: short development time, better utilization of chip area, easy testability and easy modifications all end up in a lower cost. A one-dimensional cascade of look-up tables (LUT cells) is such a regular structure. LUTs are in fact multiple-input, multiple-output universal logic blocks. LUTs in block RAMs may provide support for reconfigurable architectures, asynchronous cascades or clocked pipelines; speed is competitive with other FPGA designs, layout and wiring are very easy. The LUT cascade is a promising reconfigurable logic device for future sub-100nm LSI technology. Sequential processing of LUT cascades by means of micro-engines with multi-way branching can improve firmware performance a great deal. In this presentation we will present a new algorithm of iterative decomposition for multiple-output Boolean functions with an embedded heuristics to order variables. The algorithm produces a cascade of look-up tables that implements the given function and simultaneously a sub-optimal Multi-Terminal Binary Decision Diagram (MTBDD). Its main contribution is that the bottom-up synthesis of MTBDD/LUT cascade does not require knowledge of optimum ordering of variables, because the order of variables is generated concurrently. The LUT cascade can be used for pipelined processing on FPGAs with BRAMs or at a non-traditional synthesis of large combinational and sequential circuits. On the other hand, suboptimal MTBBDs can serve as prototypes for efficient firmware implementation, especially when a micro-programmed controller that firmware runs on supports multi-way branching. A novel technique is illustrated on practical examples of three types of arbiters. It may be quite useful as a more flexible alternative implementation of digital systems with increased testability and improved manufacturability. The presentation will be based on a paper we have presented recently at DSD 2008.