On the Complexity and Optimization of Branching Programs for Decision Diagram Machines
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F12%3APU98162" target="_blank" >RIV/00216305:26230/12:PU98162 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On the Complexity and Optimization of Branching Programs for Decision Diagram Machines
Popis výsledku v původním jazyce
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 thesebounds 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 itsexecution 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.
Název v anglickém jazyce
On the Complexity and Optimization of Branching Programs for Decision Diagram Machines
Popis výsledku anglicky
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 thesebounds 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 itsexecution 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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GAP103%2F10%2F1517" target="_blank" >GAP103/10/1517: Natural computing na nekonvenčních platformách</a><br>
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2012
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Programmable Devices and Embedded Systems PDeS 2012
ISBN
978-3-902823-21-2
ISSN
—
e-ISSN
—
Počet stran výsledku
6
Strana od-do
84-89
Název nakladatele
Faculty of Electrical Engineering and Communication BUT
Místo vydání
Brno
Místo konání akce
Brno
Datum konání akce
23. 5. 2012
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—