Remembrance Of Things Past: Locality And Memory In BDDs
S. Manne, D. Grunwald, Fabio Somenzi · 2005
Binary Decision Diagrams #BDDs# are e#cientatmanipulating large sets in a compact manner. BDDs, however, are inef- #cientatutilizing thememory hierarchyofthe computer. Recentwork addresses this problem bymanipulating the BDDs in breath-#rst manner #BFS#. BFS processing is quitesuccessful atreducingthenumber of page faults when the BDDs do not #t in theavailable physical memory.When paging does not take place, it is much less clear which paradigm leads tothebetter performance. In this paper, we perform a detailed analysis of BFS and DFS packages usingsimulation and direct performance monitoringofthememory hierarchy. Weshowthatthere is very little di#erence in TLB and cache miss rates for DFS and BFS paradigms. We also showthat di#erences in execution timebetween carefully tuned BFS and DFS implementations are primarily a function of the lossless computed table used in BFS implementations, and not a function of memory locality.Furthermore, we present implementation changes tothetheCudd ...