Publication Details
On Lookup Table Cascade-Based Realizations of Arbiters
Dvořák Václav, prof. Ing., DrSc.
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.
@inproceedings{BUT30723,
author="Petr {Mikušek} and Václav {Dvořák}",
title="On Lookup Table Cascade-Based Realizations of Arbiters",
booktitle="4th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science",
year="2008",
pages="261--261",
publisher="Masaryk University",
address="Znojmo",
isbn="978-80-7355-082-0",
url="https://www.fit.vut.cz/research/publication/8806/"
}