Title :
A Comparison of Architectures for Various Decision Diagram Machines
Author :
Nakahara, Hiroki ; Sasao, Tsutomu ; Matsuura, Munehiro
Author_Institution :
Kyushu Inst. of Technol., Iizuka, Japan
Abstract :
This paper compares 6 decision diagram machines (DDMs) with respect to area-time complexity, throughput, and compatibility to the existing memory. First, 6 types of decision diagrams (DDs): BDD, MDD, QRBDD, QRMDD, heterogeneous MDD (HMDD), and QRHMDD are introduced. Second, corresponding DDMs are developed. Third, memory sizes and average path length (APL) for these DDs are compared. As for area-time complexity, the QDDM is the best; as for throughput, the QRQDDM is the best; and as for compatibility to the existing memory, the HMDDM is the best.
Keywords :
Binary decision diagrams; Boolean functions; Data structures; Distributed decision making; Industrial control; Input variables; Logic functions; Microprocessors; Process control; Throughput; BDD; Branching Machine; Heterogeneous MDD; Homogeneous MDD; MDD; QDD; QRBDD; QRMDD;
Conference_Titel :
Multiple-Valued Logic (ISMVL), 2010 40th IEEE International Symposium on
Conference_Location :
Barcelona, Spain
Print_ISBN :
978-1-4244-6752-5
DOI :
10.1109/ISMVL.2010.50
