Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail publikace
DVOŘÁK, V.
Originální název
On the Complexity and Optimization of Branching Programs for Decision Diagram Machines
Typ
článek ve sborníku mimo WoS a Scopus
Jazyk
angličtina
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.
Klíčová slova
Boolean functions, Multi-Terminal Binary Decision Diagrams (MTBDDs), branching programs, MTBDD complexity, Decision Diagram Machines (DDMs)
Autoři
Rok RIV
2012
Vydáno
23. 5. 2012
Nakladatel
Faculty of Electrical Engineering and Communication BUT
Místo
Brno
ISBN
978-3-902823-21-2
Kniha
Programmable Devices and Embedded Systems PDeS 2012
ISSN
1474-6670
Periodikum
Programmable devices and systems
Ročník
Číslo
11
Stát
Spojené království Velké Británie a Severního Irska
Strany od
84
Strany do
89
Strany počet
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" }