Publication detail

Design of Arbiters and Allocators Based on Multi-Terminal BDDs

DVOŘÁK, V. MIKUŠEK, P.

Original Title

Design of Arbiters and Allocators Based on Multi-Terminal BDDs

English Title

Design of Arbiters and Allocators Based on Multi-Terminal BDDs

Type

journal article - other

Language

en

Original Abstract

Assigning one (more) shared resource(s) to several requesters is a function of arbiters (allocators). This class of decision-making modules can be implemented in a number of ways, from hardware to firmware to software. The paper presents a new computer-aided technique that can produce representations of arbiters/allocators in a form of a Multi-Terminal Binary Decision Diagram (MTBDD) with close to minimum cost and width. This diagram can then serve as a prototype for a cascade of multiple-output look-up tables (LUTs) that implements the given function, or for efficient firmware implementation. The technique makes use of iterative decomposition of integer functions of Boolean variables and a variable-ordering heuristic to order variables. The LUT cascades lead directly to the pipelined design, simplify wiring and testing and can compete with the traditional FPGA design in performance and with PLA design in chip area.

English abstract

Assigning one (more) shared resource(s) to several requesters is a function of arbiters (allocators). This class of decision-making modules can be implemented in a number of ways, from hardware to firmware to software. The paper presents a new computer-aided technique that can produce representations of arbiters/allocators in a form of a Multi-Terminal Binary Decision Diagram (MTBDD) with close to minimum cost and width. This diagram can then serve as a prototype for a cascade of multiple-output look-up tables (LUTs) that implements the given function, or for efficient firmware implementation. The technique makes use of iterative decomposition of integer functions of Boolean variables and a variable-ordering heuristic to order variables. The LUT cascades lead directly to the pipelined design, simplify wiring and testing and can compete with the traditional FPGA design in performance and with PLA design in chip area.

Keywords

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

RIV year

2010

Released

28.07.2010

Publisher

NEUVEDEN

Location

NEUVEDEN

Pages from

1826

Pages to

1852

Pages count

27

URL

Documents

BibTex


@article{BUT50516,
  author="Václav {Dvořák} and Petr {Mikušek}",
  title="Design of Arbiters and Allocators Based on Multi-Terminal BDDs",
  annote="Assigning one (more) shared resource(s) to several requesters is a function of
arbiters (allocators). This class of decision-making modules can be implemented
in a number of ways, from hardware to firmware to software. The paper presents
a new computer-aided technique that can produce representations of
arbiters/allocators in a form of a Multi-Terminal Binary Decision Diagram (MTBDD)
with close to minimum cost and width. This diagram can then serve as a prototype
for a cascade of multiple-output look-up tables (LUTs) that implements the given
function, or for efficient firmware implementation. The technique makes use of
iterative decomposition of integer functions of Boolean variables and
a variable-ordering heuristic to order variables. The LUT cascades lead directly
to the pipelined design, simplify wiring and testing and can compete with the
traditional FPGA design in performance and with PLA design in chip area.",
  address="NEUVEDEN",
  chapter="50516",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  journal="Journal of Universal Computer Science",
  number="14",
  volume="16",
  year="2010",
  month="july",
  pages="1826--1852",
  publisher="NEUVEDEN",
  type="journal article - other"
}