| Abstract: | An efficient heuristic algorithm for variable ordering of OBDDs, the WDHA (Weight and Distance based Heuristic Algorithm), is presented. The algorithm is based on the heuristics implied in the circuit structure graph. To scale the heuristics, pi -weight , node -weight , average -weight and pi -distance in the circuit structure graph are defined. As any of the heuristics is not a panacea for all circuits, several sub algorithms are proposed to cope with various cases. One is a direct method that uses pi -weight and pi -distance . The others are based on the depth first search (DFS) traversal of the circuit structure graph, with each focusing on one of the heuristics. An adaptive order selection strategy is adopted in WDHA. Experimental results show that WDHA is efficient in terms of BDD size and run time, and the dynamic OBDD variable ordering is more attractive if combined with WDHA. |
