Publication detail

On the Complexity and Optimization of Branching Programs for Decision Diagram Machines

DVOŘÁK, V.

Original Title

On the Complexity and Optimization of Branching Programs for Decision Diagram Machines

Type

article in a collection out of WoS and Scopus

Language

English

Original Abstract

Decision Diagram Machines (DDMs) are special purpose processors that evaluate decision diagrams. First, this paper derives upper bounds on the cost of multi-terminal binary decision diagrams (MTBDDs) for sparse multiple-output logic functions. From these bounds we can estimate the size of branching programs running on various DDMs. Second, optimization of heterogeneous branching programs is undertaken that makes a space-time trade-off between the amount of memory required for a branching program and its execution time. As a case study, optimal architectures of branching programs are found for a set of benchmark tasks. Beside DDMs, the technique can also be used for micro-controllers with a   support for multi-way branching running logic-intensive embedded firmware. 

Keywords

Boolean functions, Multi-Terminal Binary Decision Diagrams (MTBDDs), branching programs, MTBDD complexity, Decision Diagram Machines (DDMs)

Authors

DVOŘÁK, V.

RIV year

2012

Released

23. 5. 2012

Publisher

Faculty of Electrical Engineering and Communication BUT

Location

Brno

ISBN

978-3-902823-21-2

Book

Programmable Devices and Embedded Systems PDeS 2012

ISBN

1474-6670

Periodical

Programmable devices and systems

Year of study

2012

Number

11

State

United Kingdom of Great Britain and Northern Ireland

Pages from

84

Pages to

89

Pages count

6

BibTex

@inproceedings{BUT91454,
  author="Václav {Dvořák}",
  title="On the Complexity and Optimization of Branching Programs for Decision Diagram Machines",
  booktitle="Programmable Devices and Embedded Systems  PDeS 2012",
  year="2012",
  journal="Programmable devices and systems",
  volume="2012",
  number="11",
  pages="84--89",
  publisher="Faculty of Electrical Engineering and Communication BUT",
  address="Brno",
  isbn="978-3-902823-21-2",
  issn="1474-6670"
}