Speaker:Yijia Huang

RexBDDs: Rule Edges with Complement Swap for Binary Decision Diagrams

Binary decision diagrams (BDDs) are widely applied in various applications. Previously, CESRBDD was introduced to show the efficiency in the storage and computation against the alternatives by applying edge-specified reductions and input complement edges. This creative component extends the idea and presents RexBDDs, highly compact and reduced ordered-BDDs by eliminating nodes with duplicates and reduction patterns: redundancy, low-t, high-t, exist-low-t, exist-high-t, all-low-t, all-high-t. RexBDDs also incorporate input swap flags (never store both nodes p and q such that the 0-child of p is the same as the 1-child of q and the 1-child of p is the same as the 0-child of q) and output complement flags (never store both nodes p and q such that the function encoded by p is the complement of the function encoded by q). Compared with the regular BDDs, RexBDDs only request additional 12 bits of space for each node in the application but can potentially reduce the total number of stored nodes by 75%. Moreover, we also provide two universal reduction algorithms (push-up/push-down) to transform various types of BDDs proposed in the previous studies into the reduced RexBDDs.

Committee: Andrew Miner, Gianfranco Ciardo, and Wei Le

Join on Zoom: https://iastate.zoom.us/j/94785256053 Or, go to https://iastate.zoom.us/join and enter meeting ID: 947 8525 6053