Detail publikace

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

DVOŘÁK, V. O složitosti a optimalizaci větvících programů pro stroje DDM. Programmable Devices and Embedded Systems PDeS 2012. Programmable devices and systems. Brno: Faculty of Electrical Engineering and Communication BUT, 2012. s. 84-89. ISBN: 978-3-902823-21-2. ISSN: 1474-6670.
Název česky
O složitosti a optimalizaci větvících programů pro stroje DDM
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Dvořák Václav, prof. Ing., DrSc.
Klíčová slova

Boolean functions, Multi-Terminal Binary Decision Diagrams (MTBDDs), branching programs, MTBDD complexity, Decision Diagram Machines (DDMs)

Abstrakt

Decision Diagram Machines (DDMs) jsou speciální procesory, které vyhodnocují rozhodovací diagramy. V článku jsou zaprvé odvozeny horní meze ceny multi-terminálových binárních rozhodovacích diagramů (MTBDDs) pro řídké logické funkce s více výstupy. Na základě těchto mezí můžeme odhadnout velikost programů s větvením běžících na různých DDMs. Zadruhé je provedena optimalizace heterogenních programů s větvením, ve které se hledá časo-orostorový kompromis mezi velikostí paměti potřebné pro program s větvením a dobou jeho zpracování. Jako případová studie jsou nalezeny optimální architektury programů s větvením pro množinu testovacích úloh. Kromě DDMs múže být stejná technika použita také pro mikrokontroléry s podporou více-místného větvení, na nichž běží  vestavěné firmware s častými logickými výpočty. 

Rok
2012
Strany
84–89
Časopis
Programmable devices and systems, roč. 2012, č. 11, ISSN 1474-6670
Sborník
Programmable Devices and Embedded Systems PDeS 2012
ISBN
978-3-902823-21-2
Vydavatel
Faculty of Electrical Engineering and Communication BUT
Místo
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"
}
Nahoru