Conference paper

DVOŘÁK Václav. On the Complexity and Optimization of Branching Programs for Decision Diagram Machines. In: Programmable Devices and Embedded Systems PDeS 2012. Brno: Faculty of Electrical Engineering and Communication BUT, 2012, pp. 84-89. ISBN 978-3-902823-21-2. ISSN 1474-6670.
Publication language:english
Original title:On the Complexity and Optimization of Branching Programs for Decision Diagram Machines
Title (cs):O složitosti a optimalizaci větvících programů pro stroje DDM
Pages:84-89
Proceedings: Programmable Devices and Embedded Systems PDeS 2012
Conference:11th IFAC/IEEE International Conference on Programmable Devices and Embedded Systems
Place:Brno, CZ
Year:2012
ISBN:978-3-902823-21-2
Journal:IFAC-PapersOnLine, Vol. 2012, No. 11, Laxenburg, AT
ISSN:1474-6670
Publisher:Faculty of Electrical Engineering and Communication BUT
Keywords
Boolean functions, Multi-Terminal Binary Decision Diagrams (MTBDDs), branching programs, MTBDD complexity, Decision Diagram Machines (DDMs)
Annotation
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. 
BibTeX:
@INPROCEEDINGS{
   author = {V{\'{a}}clav Dvo{\v{r}}{\'{a}}k},
   title = {On the Complexity and Optimization of Branching Programs for
	Decision Diagram Machines},
   pages = {84--89},
   booktitle = { Programmable Devices and Embedded Systems  PDeS 2012},
   journal = {IFAC-PapersOnLine},
   volume = {2012},
   number = {11},
   year = {2012},
   location = {Brno, CZ},
   publisher = {Faculty of Electrical Engineering and Communication BUT},
   ISBN = {978-3-902823-21-2},
   ISSN = {1474-6670},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9828}
}

Your IPv4 address: 54.159.145.68
Switch to IPv6 connection

DNSSEC [dnssec]