Conference paperMIKUŠEK Petr and DVOŘÁK Václav. On Lookup Table CascadeBased Realizations of Arbiters. In: 4th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Znojmo: Masaryk University, 2008, pp. 261261. ISBN 9788073550820.  Publication language:  english 

Original title:  On Lookup Table CascadeBased Realizations of Arbiters 

Title (cs):  Realizace arbitrů pomocí LUT kaskád 

Pages:  261261 

Proceedings:  4th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science 

Conference:  MEMICS'08  4th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science 

Place:  Znojmo, CZ 

Year:  2008 

ISBN:  9788073550820 

Publisher:  Masaryk University 

Files:  

 Keywords 

LUT cascades, MultiTerminal BDDs, iterative disjunctive decomposition, arbiter circuits 
Annotation 

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 onedimensional cascade of lookup tables (LUT cells) is such a regular structure.
LUTs are in fact multipleinput, multipleoutput 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 sub100nm LSI technology. Sequential processing of LUT cascades by means of microengines with multiway branching can improve firmware performance a great deal.
In this presentation we will present a new algorithm of iterative decomposition for multipleoutput Boolean functions with an embedded heuristics to order variables. The algorithm produces a cascade of lookup tables that implements the given function and simultaneously a suboptimal MultiTerminal Binary Decision Diagram (MTBDD). Its main contribution is that the bottomup 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 nontraditional synthesis of large combinational and sequential circuits. On the other hand, suboptimal MTBBDs can serve as prototypes for efficient firmware implementation, especially when a microprogrammed controller that firmware runs on supports multiway 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. 
BibTeX: 

@INPROCEEDINGS{
author = {Petr Miku{\v{s}}ek and V{\'{a}}clav Dvo{\v{r}}{\'{a}}k},
title = {On Lookup Table CascadeBased Realizations of Arbiters},
pages = {261261},
booktitle = {4th Doctoral Workshop on Mathematical and Engineering
Methods in Computer Science},
year = {2008},
location = {Znojmo, CZ},
publisher = {Masaryk University},
ISBN = {9788073550820},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=8806}
} 
