Result Details

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

DVOŘÁK, V. On the Complexity and Optimization of Branching Programs for Decision Diagram Machines. Programmable Devices and Embedded Systems PDeS 2012. Programmable devices and systems. Brno: Faculty of Electrical Engineering and Communication BUT, 2012. no. 11, p. 84-89. ISBN: 978-3-902823-21-2. ISSN: 1474-6670.
Type
conference paper
Language
English
Authors
Dvořák Václav, prof. Ing., DrSc., DCSY (FIT)
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)

Published
2012
Pages
84–89
Journal
Programmable devices and systems, vol. 2012, no. 11, ISSN 1474-6670
Proceedings
Programmable Devices and Embedded Systems PDeS 2012
Conference
11th IFAC/IEEE International Conference on Programmable Devices and Embedded Systems
ISBN
978-3-902823-21-2
Publisher
Faculty of Electrical Engineering and Communication BUT
Place
Brno
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"
}
Projects
Natural Computing on Unconventional Platforms, GACR, Standardní projekty, GAP103/10/1517, start: 2010-01-01, end: 2013-12-31, running
Security-Oriented Research in Information Technology, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, start: 2007-01-01, end: 2013-12-31, running
Research groups
Supercomputing Technologies Research Group SC@FIT (RG SC@FIT)
Departments
Department of Computer Systems (DCSY)
Back to top