Detail publikace

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

DVOŘÁK, V.

Originální název

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

Anglický název

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

Jazyk

en

Originální abstrakt

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. 

Anglický abstrakt

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. 

Dokumenty

BibTex


@inproceedings{BUT91454,
  author="Václav {Dvořák}",
  title="On the Complexity and Optimization of Branching Programs for Decision Diagram Machines",
  annote="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. ",
  address="Faculty of Electrical Engineering and Communication BUT",
  booktitle="Programmable Devices and Embedded Systems  PDeS 2012",
  chapter="91454",
  edition="NEUVEDEN",
  howpublished="online",
  institution="Faculty of Electrical Engineering and Communication BUT",
  number="11",
  year="2012",
  month="may",
  pages="84--89",
  publisher="Faculty of Electrical Engineering and Communication BUT",
  type="conference paper"
}