山东大学学报(工学版) ›› 2015, Vol. 45 ›› Issue (2): 43-48.doi: 10.6040/j.issn.1672-3961.1.2014.011
伍欢, 钟发荣, 莫毓昌, 潘竹生, 曾令国
WU Huan, ZHONG Farong, MO Yuchang, PAN Zhusheng, ZENG Lingguo
摘要： 为探究启发式边排序策略性能和网络结构特征的相关性,并建立网络结构特征依赖的边排序策略选择方法,基于4种常用的规则网络对BFS(breadth-first search) 和POS (priority ordering search)两种策略的性能展开研究。通过试验分析比较了4种网络下BFS和POS两种策略的BDD (binary decision diagram)尺度与总体运行时间等性能数据。研究结果表明:在规则网络结构中,不同的排序策略适用于不同的网络结构。在Torus和Square网络中BFS策略优于POS策略;在De Bruijn和Nearest-neighbor网络中POS策略普遍优于BFS策略。该结论为特定网络选取最优或次优启发式边排序策略提供了依据。
中图分类号:
| [1] SHELDON B AKERS. Binary decision diagrams[J]. IEEE Transactions on Computers, 1978, C-27(6):509-516. [2] RANDAL E BRYANT. Symbolic boolean manipulation with ordered binary-decision diagrams[J]. ACM Computing Surveys, 1992, 24(3):293-318. [3] RANDAL E BRYANT. Graph-based algorithms for boolean function manipulation[J]. IEEE Transactions on Computers, 1986, C-35(8):677-691. [4] SIELING D, WEGEBER I. Reduction of OBDDs in linear time[J]. Information Processing Letters, 1993, 48(3):139-144. [5] GAREY M R, JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness[M]. San Francisco, USA: WH Freeman & Company, 1979:45-65. [6] BOLLIG B, WEGENER I. Improving the variable ordering of OBDDs is NP-complete[J]. IEEE Transactions on Computers, 1996, 45(9):993-1002. [7] STEVEN J FRIEDMAN, KENNETH J SUPOWIT. Finding the optimal variable ordering for binary decision diagrams[J]. IEEE Transactions on Computers, 1990, 39(5):710-713. [8] BUTLER K M, ROSS D E, KAPUR R, et al. Heuristics to compute variable orderings for efficient manipulation of ordered binary decision diagrams[C]//Proceedings of the 28th ACM/IEEE Design Automation Conference. San Francisco, USA: ACM, 1991: 417-420. [9] FUJITA M, FUJISAWA H, KAWATO N. Evaluation and improvements of boolean comparison method based on binary decision diagrams[C]//IEEE International Conference on Computer-Aided Design. Santa Clara, USA: IEEE, 1988:2-5. [10] FUJITA M, MATSUNAGA Y, KAKUDA T. On variable ordering of binary decision diagrams for the application of multi-level logic synthesis[C]//Proceedings of the Conference on European Design Automation. Amsterdam, Holland: IEEE, 1991:50-54. [11] MERCER M R, KAPUR R, ROSS D E. Functional approaches to generating orderings for efficient symbolic representation[C]//Proceedings of the 29th ACM/IEEE Design Automation Conference. Anaheim, USA: IEEE, 1992:624-627. [12] BOUISSOU M. An ordering heuristic for building binary decision diagrams from fault-trees[C]//Reliability and Maintainability Symposium, Proceedings of the International Symposium on Product Quality and Integrity. Las Vegas, USA: IEEE, 1996:208-214. [13] BOUISSOU M, BRUYERE F, RAUZY A. BDD based fault-tree processing: a comparison of variable ordering heuristics[C]//Proceedings of European Safety and Reliability Association Conference. Lisboa, Portuguesa: Elsevier, 1997. [14] GARY HARDY, CORINNE LUCET, NIKOLAOS LIMNIOS. Computing all-terminal reliability of stochastic networks with binary decision diagrams[C]//Proceedings of the 11th International Symposium on Applied Stochastic Models and Data Analysis. Brest, France: ASMDA, 2005:1468-1474. [15] GARY HARDY, CORINNE LUCET, NIKOLAOS LIMNIOS. K-terminal network reliability measures with binary decision diagrams[J]. IEEE Transactions on Reliability, 2007, 56(3):506-515. [16] FU MIN YEH, SY YEN KUO. OBDD-based network reliability calculation[J]. Electronics Letters, 1997, 33(9):759-760. [17] SY YEN KUO, SHYUE KUNG LU, FU MIN YEH. Determining terminal-pair network reliability based on edge expansion diagrams using OBDD[J]. IEEE Transactions on Reliability, 1999, 48(3):234-246. [18] FU MIN YEH, SHYUE KUNG LU, SY YEN KUO. OBDD-based evaluation of k-terminal network reliability[J]. IEEE Transactions on Reliability, 2002, 51(4):443-451. [19] 潘竹生, 莫毓昌, 赵建民. 优先级边排序策略及其性能分析[J]. 计算机科学, 2014, 41(8):81-84. PAN Zhusheng, MO Yuchang, ZHAO Jianmin. Priority edge ordering strategy and performance analysis[J]. Computer Science, 2014, 41(8):81-84. [20] ADIGA N R, BLUMRICH M A, CHEN D, et al. Blue Gene/L torus interconnection network[J]. IBM Journal of Research and Development, 2005, 49(2/3):265-276. [21] BARRENRTXEA G, BEFERULL LOZANO B, VETTERLI M. Lattice networks: capacity limits, optimal routing, and queueing behavior[J]. IEEE/ACM Transactions on Networking, 2006, 14(3):492-505. [22] SRIDHAR M A, RAGHAVENDRA C S. Fault-tolerant networks based on the de bruijn graph[J]. IEEE Transactions on Computers, 1991, 40(10):1167-1174. |
| [1] | 刘玉振,徐承强 . 多晶体材料三维微结构有限元分析的后处理[J]. 山东大学学报(工学版), 2008, 38(2): 13-17 . |
|
||
