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 grap...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.展开更多
A short-time scaling criterion of variable ordering of OBDDs is proposed. By this criterion it is easy and fast to determine which one is better when several. variable orders are given, especially when they differ 10%...A short-time scaling criterion of variable ordering of OBDDs is proposed. By this criterion it is easy and fast to determine which one is better when several. variable orders are given, especially when they differ 10% or more in resulted BDD size from each other. An adaptive variable order selection method, based on the short-time scaling criterion, is also presented. The experimental results show that this method is efficient and it makes the heuristic variable ordering methods more practical.展开更多
基金the National Natural Science Foundationof China! ( No.69873 0 2 6)the Post-doctoral ScienceFoundation of China
文摘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.
文摘A short-time scaling criterion of variable ordering of OBDDs is proposed. By this criterion it is easy and fast to determine which one is better when several. variable orders are given, especially when they differ 10% or more in resulted BDD size from each other. An adaptive variable order selection method, based on the short-time scaling criterion, is also presented. The experimental results show that this method is efficient and it makes the heuristic variable ordering methods more practical.
