Detail publikace

On Lookup Table Cascade-Based Realizations of Arbiters

Originální název

On Lookup Table Cascade-Based Realizations of Arbiters

Anglický název

On Lookup Table Cascade-Based Realizations of Arbiters

Jazyk

en

Originální abstrakt

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.

Anglický abstrakt

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.

BibTex


@inproceedings{BUT30723,
  author="Petr {Mikušek} and Václav {Dvořák}",
  title="On Lookup Table Cascade-Based Realizations of Arbiters",
  annote="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.",
  address="Masaryk University",
  booktitle="4th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science",
  chapter="30723",
  edition="NEUVEDEN",
  howpublished="print",
  institution="Masaryk University",
  year="2008",
  month="october",
  pages="261--261",
  publisher="Masaryk University",
  type="conference paper"
}