Title :
Exploiting isomorphism for compaction and faster simulation of binary decision diagrams
Author :
Chauhan, Pankaj ; Dasgupta, Pallab ; Chakrabarti, P.P.
Author_Institution :
Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., Kharagpur, India
Abstract :
We present two techniques for compaction of ROBDDs. The first technique extracts isomorphic subtrees from a characteristic function ROBDD (cfBDD), replaces them by multi-output nodes, and stores the extracted subtrees as MTBDDs. The second technique searches pre-defined topological structures (signatures) within the cfBDD and replaces them by multi-output nodes. While both approaches are able to extract isomporphic subtrees in the cfBDD, the signature scanning approach gives a significantly better compression and reduces the simulation time as compared to cfBDD simulation, which shows that is possible to compress BDDs and yet simulate them faster
Keywords :
binary decision diagrams; high level synthesis; logic partitioning; logic simulation; ISCAS benchmark circuits; binary decision diagrams; characteristic function ROBDD; compaction; faster simulation; functional logic simulation; isomorphic subtrees; isomorphism; level scanning; multi-output nodes; pre-defined topological structures; signature scanning approach; simulation time; Binary decision diagrams; Boolean functions; Circuit simulation; Compaction; Computational modeling; Data structures; Discrete event simulation; Logic circuits; Space technology; Topology;
Conference_Titel :
VLSI Design, 1999. Proceedings. Twelfth International Conference On
Conference_Location :
Goa
Print_ISBN :
0-7695-0013-7
DOI :
10.1109/ICVD.1999.745173
