Reordering binary decision diagrams for circuit design

摘要

One embodiment accesses a binary decision diagram (BDD) representing a function having n variables, where n ‰¥ 2, wherein the BDD comprises n layers corresponding to the n variables, respectively; and reorders the n variables of the BDD by iteratively and alternating reordering k consecutive layers, where 1 k ‰¤ n , until a size of the BDD has reached a desired threshold, wherein each iteration comprises: selects k consecutive layers from the n layers, wherein the k consecutive layers selected during a current iteration differ from the k consecutive layers selected during a previous iteration immediately preceding the current iteration; determines a locally optimum variable order of the k consecutive layers; and reorders the k consecutive layers according to the locally optimum variable order of the k consecutive layers.