EDA中高层次综合算法及两种时序综合理论比较研究
|
摘要
IC(Integrated Circuit)技术飞速发展，目前己处于GSI阶段，正向SOC(System On a Chip)发展，IC的应用范围极广。关于IC的设计、测试、模拟、仿真已形成实用化的集成工具，如VHDL语言。但是，在IC的发展过程中遇到了很多理论与技术问题。本文正是从理论研究角度入手，结合计算复杂性理论，对EDA中的两个重要环节，高层次综合和逻辑综合中的时序处理，做了深入研究，给出了两个理论结果和两个算法。
正如文中所指出的那样，绝大多数组合与时序优化问题，实际上都是NP-完全问题，因而试图给出现实可行的一劳永逸的通用算法在目前是办不到的。所以，大多数研究者均是从自身的角度出发，研究各种各样的启发式算法，然而算法效果如何，针对EDA中各个环节目前尚无人提出统一标准来做判断分析。
本文在继承前人工作的基础上，将最基本也是最重要的图灵机模型及其依据于此的计算复杂性理论的若干重要概念与思想引入到EDA中的高层次综合和逻辑综合环节中。文中在讨论了P与NP问题、近似算法性能指标等概念的基础上，对高层次综合中的问题，将其归结为基本组合问题，并进行了描述。针对高层次综合中部分有代表性的问题，指出其近似求解的无限逼近最优性。
本文对高层次综合中的互连单元分配算法进行了研究，对互连单元分配进行了论述。在着重分析数据通路连接图的表示模型的基础上，对数据通路连接图的标准型给出了一系列定义，然后提出了IU-Allocation算法。利用该算法对线性预测系统的自相关数字电路进行了实验，并对算法的时间复杂性做了分析。
本文介绍了演化计算的概念及应用。提出了一种基于演化程序的数据通路综合算法。该算法将演化程序与已知的启发式算法相结合，可对较大的设计空间进行智能化搜索。同时，以减少硬件资源成本和缩短总的执行时间为目标，讨论了应用该方法对典型的微分方程电路实施调度、分配和数据通路综合的整体优化过程，并做了仿真实验，证明可以有效地提高高层次综合设
哈尔滨工程大学博士学位论文
计的质量。
对时序逻辑综合领域的两种重要理论，布尔过程论与时变布尔函数，在
定时特性方面进行了重点比较。这两种理论均是在考虑布尔变量的同时，将
时间特性加入其中，以期系统地处理逻辑与时序问题。其重要的不同点是，
布尔过程借助实数的运算，而时变布尔函数依然采用布尔运算。研究了布尔
过程在计算通路敏化时的计算复杂性，指出按其算法进行通路敏化求解是指
数时间算法。
最后本文对逻辑综合领域的最新进展进行了综述，介绍了OBDD的来
源、发展，以及目前的状态。论述了确切BDD算法、启发式BDD算法、快
速BDD最小化、使用无关集的启发式BDD最小化等相关概念和算法。
关键词:高层次综合算法;布尔过程论;时变布尔函数;顺序二叉判决图
With the development of science and technology, IC(integrated circuit) is striding for the SOC(System on a chip)stage, and it is in GSI stage now. Tools for test, emulation and simulation, such as VHDL language, have been developed for the design of IC. However, there are still many problems of theory and technology unresolved in this process. Based on this consideration, this paper investigates two important parts of EDA-high level synthesis and logic synthesis, by combining computational complexity theory. Two conclusions and two algorithms are given in this paper.Just as this paper points out, most problems about combination and sequential optimization are in fact NP-complete, so, it's impossible to find a general algorithm to solve all the problem presently. So, many researchers present heuristic algorithms to solve the problems, but no one provides a framework to find a heuristic framework to systematically analyze these algorithms.By inheriting from works done by others, we introduce Turing machine model, which is of most importance to the computational complexity theory, high level synthesis and logic synthesis. We also discuss such concepts as P and NP, approximate algorithm performance, and ascribe problems of high-level synthesis to combinational problem. For typical problems in high-level synthesis, we point out its maximum optimum.Further, we study the algorithm of interconnect unit in high level synthesis, and formulate the allocation of interconnect unit in this paper. By basing on analyzing the model of data path connection diagram, we provide a sequence of definition about data path niter-connect diagram, and then present an IU-Allocation algorithm. By utilizing this algorithm, we did an experiment about autocorrelation data circuit of linear forecast system and analyzed the tune complexity of the algorithm.Also, we introduce the concept and application of data path synthesis, and
present an data path synthesis algorithm based on evolutionary computation. By combining extant heuristic algorithm and evolutionary algorithm, it can intelligently search relative bigger space. At the same time, this paper discusses how to reduce hardware resources and compress execution time when we use these algorithms to schedule or allocate classical differential equation and optimize data paths. The simulation experiments imply that it can effectively improve the quality of high-level synthesis.We also focus on the comparison of two important theories-Boolean process and TBF. Both theories are developed from Boolean function in order to systematically deal with logic and tuning problems. The most important difference between the two theories is that Boolean process still use Boolean domain while TBF still adopt the old system except that it introduced the time variable. Also this paper studies the complexity of Boolean process in dealing with path sensitization and find that the tune complexity is exponential.At last, we give a survey of logic synthesis and an overview about the source and development of OBDD, and also introduce the status quo of OBDD minimization.Further, we formulated exact OBDD minimization in algorithms, heuristic OBDD minimization algorithms, fast OBDD minimization algorithms OBDD minimization using don't care sets and related concepts.
正如文中所指出的那样，绝大多数组合与时序优化问题，实际上都是NP-完全问题，因而试图给出现实可行的一劳永逸的通用算法在目前是办不到的。所以，大多数研究者均是从自身的角度出发，研究各种各样的启发式算法，然而算法效果如何，针对EDA中各个环节目前尚无人提出统一标准来做判断分析。
本文在继承前人工作的基础上，将最基本也是最重要的图灵机模型及其依据于此的计算复杂性理论的若干重要概念与思想引入到EDA中的高层次综合和逻辑综合环节中。文中在讨论了P与NP问题、近似算法性能指标等概念的基础上，对高层次综合中的问题，将其归结为基本组合问题，并进行了描述。针对高层次综合中部分有代表性的问题，指出其近似求解的无限逼近最优性。
本文对高层次综合中的互连单元分配算法进行了研究，对互连单元分配进行了论述。在着重分析数据通路连接图的表示模型的基础上，对数据通路连接图的标准型给出了一系列定义，然后提出了IU-Allocation算法。利用该算法对线性预测系统的自相关数字电路进行了实验，并对算法的时间复杂性做了分析。
本文介绍了演化计算的概念及应用。提出了一种基于演化程序的数据通路综合算法。该算法将演化程序与已知的启发式算法相结合，可对较大的设计空间进行智能化搜索。同时，以减少硬件资源成本和缩短总的执行时间为目标，讨论了应用该方法对典型的微分方程电路实施调度、分配和数据通路综合的整体优化过程，并做了仿真实验，证明可以有效地提高高层次综合设
哈尔滨工程大学博士学位论文
计的质量。
对时序逻辑综合领域的两种重要理论，布尔过程论与时变布尔函数，在
定时特性方面进行了重点比较。这两种理论均是在考虑布尔变量的同时，将
时间特性加入其中，以期系统地处理逻辑与时序问题。其重要的不同点是，
布尔过程借助实数的运算，而时变布尔函数依然采用布尔运算。研究了布尔
过程在计算通路敏化时的计算复杂性，指出按其算法进行通路敏化求解是指
数时间算法。
最后本文对逻辑综合领域的最新进展进行了综述，介绍了OBDD的来
源、发展，以及目前的状态。论述了确切BDD算法、启发式BDD算法、快
速BDD最小化、使用无关集的启发式BDD最小化等相关概念和算法。
关键词:高层次综合算法;布尔过程论;时变布尔函数;顺序二叉判决图
With the development of science and technology, IC(integrated circuit) is striding for the SOC(System on a chip)stage, and it is in GSI stage now. Tools for test, emulation and simulation, such as VHDL language, have been developed for the design of IC. However, there are still many problems of theory and technology unresolved in this process. Based on this consideration, this paper investigates two important parts of EDA-high level synthesis and logic synthesis, by combining computational complexity theory. Two conclusions and two algorithms are given in this paper.Just as this paper points out, most problems about combination and sequential optimization are in fact NP-complete, so, it's impossible to find a general algorithm to solve all the problem presently. So, many researchers present heuristic algorithms to solve the problems, but no one provides a framework to find a heuristic framework to systematically analyze these algorithms.By inheriting from works done by others, we introduce Turing machine model, which is of most importance to the computational complexity theory, high level synthesis and logic synthesis. We also discuss such concepts as P and NP, approximate algorithm performance, and ascribe problems of high-level synthesis to combinational problem. For typical problems in high-level synthesis, we point out its maximum optimum.Further, we study the algorithm of interconnect unit in high level synthesis, and formulate the allocation of interconnect unit in this paper. By basing on analyzing the model of data path connection diagram, we provide a sequence of definition about data path niter-connect diagram, and then present an IU-Allocation algorithm. By utilizing this algorithm, we did an experiment about autocorrelation data circuit of linear forecast system and analyzed the tune complexity of the algorithm.Also, we introduce the concept and application of data path synthesis, and
present an data path synthesis algorithm based on evolutionary computation. By combining extant heuristic algorithm and evolutionary algorithm, it can intelligently search relative bigger space. At the same time, this paper discusses how to reduce hardware resources and compress execution time when we use these algorithms to schedule or allocate classical differential equation and optimize data paths. The simulation experiments imply that it can effectively improve the quality of high-level synthesis.We also focus on the comparison of two important theories-Boolean process and TBF. Both theories are developed from Boolean function in order to systematically deal with logic and tuning problems. The most important difference between the two theories is that Boolean process still use Boolean domain while TBF still adopt the old system except that it introduced the time variable. Also this paper studies the complexity of Boolean process in dealing with path sensitization and find that the tune complexity is exponential.At last, we give a survey of logic synthesis and an overview about the source and development of OBDD, and also introduce the status quo of OBDD minimization.Further, we formulated exact OBDD minimization in algorithms, heuristic OBDD minimization algorithms, fast OBDD minimization algorithms OBDD minimization using don't care sets and related concepts.
引文
[1] Pogge H B. The next chip challenge: effective methods for viablemixed technology SoCs. In Proc 39th DAC, 2002:84-87P
[2] Bergamaschi R A, Lee W R. Designing system-on-chip using cores. In Proc37th DAC, 2000:420-425P
[3] 徐善峰，初秀琴，李玉山．21世纪微电子芯片设计技术发展方向．微电子学，2001，31(5)：313-316页
[4] Harry V. Deep-Submicron CMOS Ics. Boston:Kluwer Academic Publisher, 2001:11-36P
[5] Chandrakasan Aet al. Design of high-performance microprocessor circuits. New York: IEEE Press, 2000:20-65P
[6] MacMillen D, Butts Met al. An industrial view of electronic design automation. IEEE Trans CAD, 2000,9(12):1428-1448P
[7] 彭宇行，陈福接，李思昆．高速IC设计技术．计算机辅助设计与图形学报，1996，8(6)：439-445页
[8] 洪先龙，刘伟平，边计年．超大规模集成电路计算机辅助设计技术．北京：国防工业出版社，1998
[9] A. Ghosh, s. Devadas, and A.R. Newton. Heuristic Minimization of Boolean Relations using Testing Techniques. In Proceedings of the international Conference on Computer Design, September 1990
[10] M. Damiani, J. Yang, and G. DeMicheli. Optimization of Combinational Logic Circuits Based on Compatible Gates. In Proceedings of the 30th Design Automation Conference, pages 631-636, June 1993
[11] G.D. Hachtel, R.M. Jacoby, k. Keutzer, and C.R. Morrison. On the relationship between area optimization and multifault testability of multilevel logic. IEEE/ACM International Conference on Computer Aided Design,' 89, Nov.,1989
[12] R. Brayton, G. Hachtel, C. McMullen, and A. Sangiovanni-Vincentelli. Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, 1984
[13] Larry Augustin. An algebra of waveforms. IFIP International Workshop on Applied Formal Methods for Correct VLSI Design, pages 159-168. Nov.,1989
[116] Rolf Drechsler, Nicole Drechsler, Wolfgang Gunther. Fast Exact Minimization of BDD' s. IEEE Transactions On Computer-Aided Design Of Integrated Circuits And Systems.1993,19(3), 384-389
[117] Steven J Friedman , Kenneth J Supowit . Finding the Optimal Variab-le Ordering for Binary Decision Diagrams. IEEE Transactions On Computers. 1990, 39(5):710-713
[118] N Ishiura, H Sawada, S Yajima. Minimization of binary decision diagrams based on exchange of variables. Computer-Aided Design. 1991:472-475
[119] S W Jeong, T-S Kim, F Somenzi. An efficient method for optimal BDD ordering computation. VLSI and CAD. 1993
[120] R E Bryant . Graph-based algorithms for Boolean function manipulation . IEEE Trans Comput. 1991, 40:205-213
[121] Thomas R Shiple, Robert K Brayton. Heuristic Minimization of BDDs Using Don' t Cares. Annual ACM IEEE Design Automation Conference. 1994:225-231 and Allocation Method Followed by an Interconnect Optimization Algorithm. In: Proc. Of the 27th DAC. 1990.77-83P
[31] Wakabayashi K , Tanaka H . Global Scheduling Independent of Control Dependencies Based on Condition Vectors. In: Proc. of the 29th DAC. 1992.112-115P
[32] Rim M, Jain R, Leone R D. Optimal Allocation and Binding in High-Level Synthesis. In: Proc. Of the 29th DAC. 1992.120-123P
[33] McFarland M C, Parker A C, Camposano R. The High-level Synthesis of Digital Systems. Proceedings of the IEEE,1990,76 (2): 301-318P
[34] Devadas S, Newton A R. Algorithms for Hardware Allocation in Data Path Synthesis. IEEE Trans, on CAD, 1989,8(7):768~781P
[35] Su M, Xue H X, Hong X L A Global Scheduling Algorithm for CDFC with Nested Conditional Branches. In: Proc. Of the 3rd International CAD/Graphics. 1993. 526-530P
[36] Su M, Xue H X, Hong X L. Diffusion Based Scheduling Algorithm for High-Level Synthesis. In: Proc. of the 2nd CAD/Graphics. 1991. 497-502P
[37] P. G. Paulin, J. P. Knight, Force-Directed Scheduling for the Behavioral Synthesis of ASIC' s, IEEE Trans on CAD, Vol8, No. 6, June, 1989, pp. 661-679P
[38] M . C . McFarland et al., The High-level Synthesis of Digital Systems, Proc. of IEEE Vol. 78, No. 2, Feb, 1990, pp. 301-318P
[39] 李淳，刘明页等，迭代的调度分配改进策略，计算机辅助设计图形学学报，1996, 8 (3): 222-226 页。
[40] Bhattacharya S, Dey s et al. Performance analysis and op-timization of schedules for conditional and loop-intensive specifitions. Proc. 31st Design Automation Conf., 1994,491-496P
[41] Satyanarayana J H, Nowrouzian B. FLIGHT: a novel approach to the high-level synthesis of digital-serial digital filters. Proc. Midwest Symp. On Circuits and Systems, 1994, vol.1, 335-338P
[42] Martin R S , Knight J P . PASSOS . a different approach for assignme-nt and scheduling for power, area and speed optimization in high-level synthesis. Proc. Midwest Symp. OnCircuits and Systems, 1994, vol. 1, 339-342P
[43] Amellal S, Kaminska B. Functional synthesis of digital systems with TASS. IEEEE trans, on CAD, 1994,13(5):537-552P
[44] Amellal S, Kaminska B. Scheduling algorithm in datapath synthesis using the tabu search technique. Proc. 30th Design Automation Conf., Europe, Event in ASIC Design, 1993,398-402P
[4
[45] Nourani M, Papachristou C et al. A neural network based algorithm for the scheduling problem in high-level synthesis. Design Automation Conf.,Europe, 1992,341-346P
[46] Wang C Y, Parhi K K. High-level DSP synthesis using concurrent transformations, scheduling, and allocation. IEEE trans. On CAD, 1995,14,14(3):274-295P
[47] Joon S Y, Chong M K. Reducing cross-coupling among interconnect wires in Deep Submicron datapath design. Proc. 36th Design Automation Conf.,1999:485-490P
[48] Potkonjak M, Rabaey J. Optimizing resource utilization using transformation. IEEE trans, on CAD, 1994,13(3):277-292P
[49] 苏明，元彦宏，薛宏熙，洪先龙．基于浓度扩散的调度算法．计算机学报，1993，16(4)：257-264页
[50] Dhodhi M K et al. Datapath synthesis using a problem-space genetic algorithm. IEEE Trans. on CAD, 1995,14(8):934-943P
[51] Ahmad I, Dhodhi M K et al. Integrated scheduling, allocation and module selection for design-space exploration in high-level synthesis. IEEE Proc, Comput. Digit. Tech.,1995,142(1):65-71P
[52] Dhodhi M K, Ahmad Iet al. High-level synthesis of datapaths for easy testability, IEEE Proc. Circuits, Devices and Systems, 1995, Aug, 202-219P
[53] 苏明，薛宏熙，洪先龙．强时间约束条件下的调度优化算法．计算机辅设计与图形学学报，1993年第1期：13-17页
[54] Ly T A, Mowchenko J T. Applying simulated evolution to high-level synthesis IEEE trans, on CAD, 1993,12(3):389-409P
[55] Paulin P G, Knight J P et al. HAL:A multi-paradigm approach to automatic datapath synthesis. Proc. 23rd Design Automation Conf.,1986,263-270P
[56] Paulin P G, Kight J P. Force-directed scheduling for the behavioral synthesis of ASICs. IEEE trans, on CAD, 1989,8(6):661-679P
[57] Paulin P G, Knight J P. Algorithms for high-level synthesis. IEEE Design & Test of Computers, 1989,6(6):18-31P
[58] Peng Z, Kuchcinski K. Automated transformation of algorithms into Register-transfer Ievel implementations. IEEE trans, on CAD, 1994,13(2):150-166P
[59] Chao L F, Paugh A Let al. Rotation scheduleing:a loop pipelineing algorithm . Proc 30st Design Automation Conf, 1993, 566-572P
[60] Luche L E, Parhi K K. Generalized ILP scheduling and allocation for high-level DSP synthesis
[61] Evehing H, Honeth S. Optimization and resynthesis of complex datapaths. Proc 32nd Design Automation Conf, 1995,14(3):274-295P
[62] Jon C C, Lam Y Y H. Using time zones for datapath allocation in high-level synthesis of digital systems. Int. J. Electronics, 1995 ,79(5):627-640P
[63] Paulin P G, Knight J Pet aI. HAL:A multi-paradigm approach to automatic datapath synthesis. Proc. 23rd Design Automation Conf.,1986,263-270P
[64] 何中礼，庄镇泉．一种数字电路高层次综合器DLS．电子学报，1994，22(11)：49-54页
[65] Jiang Y M. Performance-driven interconnection optimization for microarchitecture synthesis. IEEE trans on CAD ,1994 ,13(2): 137-149P
[66] Minjoong Rim, Rajiv Jain and Renato De Leone. Optimal Allocation and Binding in High-Level Synthesis. In Proc. ACM/IEEE 29th DAC, 1992: 120-123P
[67] Catheherine H Gebotys. Optimal Scheduling and Allocation of Embeded VLSI Chips. In Proc. ACM/IEEE Trans VLSI, Vol, 1, No. 3, Sept. 1993 ,233-243P
[68] 刘明业，张东晓，叶梅龙，李雁．专用集成电路高级综合理论．北京：北京理工大学出版社1998
[69] 傅清祥，王晓东．算法与数据结构．北京：电子工业出版社1998
[70] 张力昂可计算性与计算复杂性导引．北京：北京大学出版社1996
[71] Michael R. Garey, David S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W.H. Freeman and Company. 1979
[72] Marin D. Davis, Elaine J. Weyuker, Computability, Compleity, and Languages, Fundamentals of Theoretical Computer Science, Academic Press, Inc. 1983
[73] TSENG C J, SIEWIOREK D P. Automated Synthesis of Data Paths in Digital Systems. IEEE Trans. on CAD, 1986,5(3):379-393P
[74] J.G. Augustson and J. Minker. An analysis of some graph theoretical cluster techniques. J. ACM. 1970,17(4):571-588P
[75] C. Bron and J. Kerbosch. Finding all cliques of an undirected graph-Algorithm 457. Commun. ACM. 1973,16(9):575-577P
[76] G.D. Mulligan and D.G. Corneil. Corrections to Bierstone' s Algorithm for Geneating Cliques. J. ACM 1972,19(2):244-247P
[77] M.C. Paull and S.H. Unger. Minimizing the number of states in Incompletely specified sequential functions. IRE Trans. Electronic Computers. 1959, vol. EC-8,356-367P
[78] S. Tsukiyama, M. Ide, H. Ariyoshi, I. Shirakawa. A new algorithm for generating all the maximal independent sets. SIAM J. Computing .1977, vol. 6 505-517P
[79] CONG J, PAN D Z. Interconnect estimation and planning for deep submicron designs[A].Tech Rep 980035[R].UCLS CS Dept, 1998:507-510P
[80] LAGNESE E, THOMAS D. Architectural partitioning for system level synthesis of integrated circuits[J]. IEEE Trans on CAD, 1991,10(7):847-860P
[81] 刘泽坚，陆宏达．用复杂数学系统测试的整体功能模型[J]．计算机辅助设计与图形学学报，1999，11(6)：542—546页
[82] Rechenberg, I. Evolutions strategie:Optimierung technischer System nach Prinzipen cler biologischen Evolution. Frommann-Holzboog Verlag, Stuttgart, 1973.
[83] Schwefel, H.-P., Numerical Optimization for Computer Models, John Wiley ,Chichester ,UK. 1981
[84] Fogel, L.J., Owens, A.J., and Walsh, M.j., Artificial Intelligence Through Simulated Evolution, John Wiley, Chichester, UK. 1996
[85] Holland, J.H., Adaptation in Natural and Artificial Systems , University of Michigan Press, Ann Arbor, 1975.
[86] Z．米凯利维茨著．周家趄译．演化程序—遗传算法和数据编码的结合．北京：科学出版社，2000
[87] 潘正君，康立山，陈毓屏著．演化计算．北京：清华大学出版社，广西：广西科学技述出版社，1998
[88] 谢涛，陈火旺，康立山，计算机学报，2003(8)：997-1003页
[89] Pareto V. Cours D' Economie Politique, volume Ⅰ and Ⅱ. F. Rouge, Lausanne, 1896
[90] Chipperfield A J, Fleming P J. Gas turbine engine controller desigh using multiobjective genetic algorithms. In:Proceedings of the 1st IEE/IEEE International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications, University of Sheffield, UK, 1995. 214-219P
[91] Fonseca C M , Fleming P J . Multiobjective optimization and multiple constrains handling with evolutionary algorithms-part I :A unified formulation, and part IIapplication example. IEEE Transactions on Systems, Man & Cybernetics-Part A: Systems and Humans, 1998,28 (1):26-47P
[92] Jones B R, Crossley W A, Lyrintzis A S. Aerodynamic and aeroacoustic optimization of airfoils via a parallel genetic algorithm. In : Proceedings of the 7th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, St. Louis, Mo, 1998.AIAA-98-4811
[93] 王志华,邓仰东。数字集成系统的结构化设计与高层次综合。北京：清华大学出版社，2001
[94] Subramaniam G, Ken R. Datapath Synthesis Using Genetic Algorithm . Computers and Electrical Engineer-ing, 26(2000):337-349P
[95] Ahmad I, Dhodhi M K et al. Integrated scheduling, allocation and module selection for design-space exploration in high-level synthesis. IEEE Proc, Comput. Digit. Tech., 1995, 142(1):65-71P
[96] Dhodhi M K, Ahmad I et al. High-level synthesis of datapaths for easy testability, IEEE Proc. Circuits, Devices and Systems, 1995, Aug, 209-219P
[97] When N, Held M et al.A novel scheduling/allocation approach for datapath synthesis based on genetic paradigms. North-Holland: Elsevier Science Publishiers B. V, 1991 [98] J.H.Holland, Adaptation in Natural and Artificial Systems. Ann Arbor, MI: University of Michigan, 1975
[99] Michalewicz Z . Genitic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, Berlin, 1992
[100] P. McGeer and R. Brayton. Provably correct critical paths. The Proceedings of the Decennial Caltech VLSI Conference, 1989
[101] W. Lam, R. Brayton, and A. Sangiovanni-Vincentelli. Circuit delay models and their exact computation using timed Boolean functions. IEEE/ACM Design Automation Conference' 93,1993
[102] H .C.CHEN and D.H. Du. Path sensitization in critical path problem. 1990 ACM Workshop on Timing Issues in the Specification and Synthesis of Digital Systems, 1990
[103] Devadas S , Keutzer K , Malik S . Computation of floating mode delay in combinational circuits: theory and algorithms. IEEE Trans CAD, 1993,12(12) :1913-1931P
[104] Lin C J, Reddy S M, On delay testing in logic circuits. IEEE Trans CAD, 1987,6(6): 694-703P
[105] Bhattacharya D, Agraval P, Agrawal C D. Test generation for p- ath delay faults using binary decision diagrams. IEEE Trans computers, 1945, 44(3):434-447P
[106] P. McGeer and R.Brayton. Provably correct critical paths. The Proceedings of the Decennial Caltech VLSI Conference, 1989
[107] 2000, 12 (4): 308-311
[108] S B Akers. Binary decision diagrams. IEEE Trans Comput . 1978, C-27: 509-516
[109] Randal E, Bryant. Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transactions On Computers , 1986 , C35(8) : 677-691
[110] Rolf Drechsler, Wolfgang Gunther , Fabio Somenzi. Using Lower ounds During Dynamic BDD Minimization. IEEE Transactions On Computer-Aided Design Of Intergrated Circuits And Systems. 2001, 20(1) : 51-57
[111] Wolfgang Gunther, Rolf Drechsler. Minimization of free BDDs. VLSI journal. 2002:41-59
[112] Beate Bollig, Ingo Wegener. Improving the Variable Ordering of OBDDs Is NP-Complete. IEEE Transactions On Computers . 1996, 45(9):993-1002
[113] Masahiro Fujita, Hisanori Fujisawa, Yusuke Matsunaga. Variable Ordering Algorithms Ffor Ordered Binary Decision Diagrams and Their Evaluation. IEEE Transactions On Computer-Aided Design Of Integrated Circuits And Systems. 1993,12(1):6-12
[114] Rudiger Ebendt, Wolfgang Gunther, Rolf Drechsler. An Improved Branch Bound Algorithm for Exact BDD Minimization. IEEE Transactions On Computer-Aided Design Of Integrated Circuits And systems. 2003, 22(12):1657-1663
[115] Shipra Panda , Fabio Somenzi . Who Are the Variables in Your Neighborhood. Proceedings of the 1995 International Conference on Computer-Aided Design. 1995:74-77
[116] Rolf Drechsler, Nicole Drechsler, Wolfgang Gunther. Fast Exact Minimization of BDD' s. IEEE Transactions On Computer-Aided Design Of Integrated Circuits And Systems.1993,19(3), 384-389
[117] Steven J Friedman , Kenneth J Supowit . Finding the Optimal Variab-le Ordering for Binary Decision Diagrams. IEEE Transactions On Computers. 1990, 39(5):710-713
[118] N Ishiura, H Sawada, S Yajima. Minimization of binary decision diagrams based on exchange of variables. Computer-Aided Design. 1991:472-475
[119] S W Jeong, T-S Kim, F Somenzi. An efficient method for optimal BDD ordering computation. VLSI and CAD. 1993
[120] R E Bryant . Graph-based algorithms for Boolean function manipulation . IEEE Trans Comput. 1991, 40:205-213
[121] Thomas R Shiple, Robert K Brayton. Heuristic Minimization of BDDs Using Don' t Cares. Annual ACM IEEE Design Automation Conference. 1994:225-231
[2] Bergamaschi R A, Lee W R. Designing system-on-chip using cores. In Proc37th DAC, 2000:420-425P
[3] 徐善峰，初秀琴，李玉山．21世纪微电子芯片设计技术发展方向．微电子学，2001，31(5)：313-316页
[4] Harry V. Deep-Submicron CMOS Ics. Boston:Kluwer Academic Publisher, 2001:11-36P
[5] Chandrakasan Aet al. Design of high-performance microprocessor circuits. New York: IEEE Press, 2000:20-65P
[6] MacMillen D, Butts Met al. An industrial view of electronic design automation. IEEE Trans CAD, 2000,9(12):1428-1448P
[7] 彭宇行，陈福接，李思昆．高速IC设计技术．计算机辅助设计与图形学报，1996，8(6)：439-445页
[8] 洪先龙，刘伟平，边计年．超大规模集成电路计算机辅助设计技术．北京：国防工业出版社，1998
[9] A. Ghosh, s. Devadas, and A.R. Newton. Heuristic Minimization of Boolean Relations using Testing Techniques. In Proceedings of the international Conference on Computer Design, September 1990
[10] M. Damiani, J. Yang, and G. DeMicheli. Optimization of Combinational Logic Circuits Based on Compatible Gates. In Proceedings of the 30th Design Automation Conference, pages 631-636, June 1993
[11] G.D. Hachtel, R.M. Jacoby, k. Keutzer, and C.R. Morrison. On the relationship between area optimization and multifault testability of multilevel logic. IEEE/ACM International Conference on Computer Aided Design,' 89, Nov.,1989
[12] R. Brayton, G. Hachtel, C. McMullen, and A. Sangiovanni-Vincentelli. Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, 1984
[13] Larry Augustin. An algebra of waveforms. IFIP International Workshop on Applied Formal Methods for Correct VLSI Design, pages 159-168. Nov.,1989
[116] Rolf Drechsler, Nicole Drechsler, Wolfgang Gunther. Fast Exact Minimization of BDD' s. IEEE Transactions On Computer-Aided Design Of Integrated Circuits And Systems.1993,19(3), 384-389
[117] Steven J Friedman , Kenneth J Supowit . Finding the Optimal Variab-le Ordering for Binary Decision Diagrams. IEEE Transactions On Computers. 1990, 39(5):710-713
[118] N Ishiura, H Sawada, S Yajima. Minimization of binary decision diagrams based on exchange of variables. Computer-Aided Design. 1991:472-475
[119] S W Jeong, T-S Kim, F Somenzi. An efficient method for optimal BDD ordering computation. VLSI and CAD. 1993
[120] R E Bryant . Graph-based algorithms for Boolean function manipulation . IEEE Trans Comput. 1991, 40:205-213
[121] Thomas R Shiple, Robert K Brayton. Heuristic Minimization of BDDs Using Don' t Cares. Annual ACM IEEE Design Automation Conference. 1994:225-231 and Allocation Method Followed by an Interconnect Optimization Algorithm. In: Proc. Of the 27th DAC. 1990.77-83P
[31] Wakabayashi K , Tanaka H . Global Scheduling Independent of Control Dependencies Based on Condition Vectors. In: Proc. of the 29th DAC. 1992.112-115P
[32] Rim M, Jain R, Leone R D. Optimal Allocation and Binding in High-Level Synthesis. In: Proc. Of the 29th DAC. 1992.120-123P
[33] McFarland M C, Parker A C, Camposano R. The High-level Synthesis of Digital Systems. Proceedings of the IEEE,1990,76 (2): 301-318P
[34] Devadas S, Newton A R. Algorithms for Hardware Allocation in Data Path Synthesis. IEEE Trans, on CAD, 1989,8(7):768~781P
[35] Su M, Xue H X, Hong X L A Global Scheduling Algorithm for CDFC with Nested Conditional Branches. In: Proc. Of the 3rd International CAD/Graphics. 1993. 526-530P
[36] Su M, Xue H X, Hong X L. Diffusion Based Scheduling Algorithm for High-Level Synthesis. In: Proc. of the 2nd CAD/Graphics. 1991. 497-502P
[37] P. G. Paulin, J. P. Knight, Force-Directed Scheduling for the Behavioral Synthesis of ASIC' s, IEEE Trans on CAD, Vol8, No. 6, June, 1989, pp. 661-679P
[38] M . C . McFarland et al., The High-level Synthesis of Digital Systems, Proc. of IEEE Vol. 78, No. 2, Feb, 1990, pp. 301-318P
[39] 李淳，刘明页等，迭代的调度分配改进策略，计算机辅助设计图形学学报，1996, 8 (3): 222-226 页。
[40] Bhattacharya S, Dey s et al. Performance analysis and op-timization of schedules for conditional and loop-intensive specifitions. Proc. 31st Design Automation Conf., 1994,491-496P
[41] Satyanarayana J H, Nowrouzian B. FLIGHT: a novel approach to the high-level synthesis of digital-serial digital filters. Proc. Midwest Symp. On Circuits and Systems, 1994, vol.1, 335-338P
[42] Martin R S , Knight J P . PASSOS . a different approach for assignme-nt and scheduling for power, area and speed optimization in high-level synthesis. Proc. Midwest Symp. OnCircuits and Systems, 1994, vol. 1, 339-342P
[43] Amellal S, Kaminska B. Functional synthesis of digital systems with TASS. IEEEE trans, on CAD, 1994,13(5):537-552P
[44] Amellal S, Kaminska B. Scheduling algorithm in datapath synthesis using the tabu search technique. Proc. 30th Design Automation Conf., Europe, Event in ASIC Design, 1993,398-402P
[4
[45] Nourani M, Papachristou C et al. A neural network based algorithm for the scheduling problem in high-level synthesis. Design Automation Conf.,Europe, 1992,341-346P
[46] Wang C Y, Parhi K K. High-level DSP synthesis using concurrent transformations, scheduling, and allocation. IEEE trans. On CAD, 1995,14,14(3):274-295P
[47] Joon S Y, Chong M K. Reducing cross-coupling among interconnect wires in Deep Submicron datapath design. Proc. 36th Design Automation Conf.,1999:485-490P
[48] Potkonjak M, Rabaey J. Optimizing resource utilization using transformation. IEEE trans, on CAD, 1994,13(3):277-292P
[49] 苏明，元彦宏，薛宏熙，洪先龙．基于浓度扩散的调度算法．计算机学报，1993，16(4)：257-264页
[50] Dhodhi M K et al. Datapath synthesis using a problem-space genetic algorithm. IEEE Trans. on CAD, 1995,14(8):934-943P
[51] Ahmad I, Dhodhi M K et al. Integrated scheduling, allocation and module selection for design-space exploration in high-level synthesis. IEEE Proc, Comput. Digit. Tech.,1995,142(1):65-71P
[52] Dhodhi M K, Ahmad Iet al. High-level synthesis of datapaths for easy testability, IEEE Proc. Circuits, Devices and Systems, 1995, Aug, 202-219P
[53] 苏明，薛宏熙，洪先龙．强时间约束条件下的调度优化算法．计算机辅设计与图形学学报，1993年第1期：13-17页
[54] Ly T A, Mowchenko J T. Applying simulated evolution to high-level synthesis IEEE trans, on CAD, 1993,12(3):389-409P
[55] Paulin P G, Knight J P et al. HAL:A multi-paradigm approach to automatic datapath synthesis. Proc. 23rd Design Automation Conf.,1986,263-270P
[56] Paulin P G, Kight J P. Force-directed scheduling for the behavioral synthesis of ASICs. IEEE trans, on CAD, 1989,8(6):661-679P
[57] Paulin P G, Knight J P. Algorithms for high-level synthesis. IEEE Design & Test of Computers, 1989,6(6):18-31P
[58] Peng Z, Kuchcinski K. Automated transformation of algorithms into Register-transfer Ievel implementations. IEEE trans, on CAD, 1994,13(2):150-166P
[59] Chao L F, Paugh A Let al. Rotation scheduleing:a loop pipelineing algorithm . Proc 30st Design Automation Conf, 1993, 566-572P
[60] Luche L E, Parhi K K. Generalized ILP scheduling and allocation for high-level DSP synthesis
[61] Evehing H, Honeth S. Optimization and resynthesis of complex datapaths. Proc 32nd Design Automation Conf, 1995,14(3):274-295P
[62] Jon C C, Lam Y Y H. Using time zones for datapath allocation in high-level synthesis of digital systems. Int. J. Electronics, 1995 ,79(5):627-640P
[63] Paulin P G, Knight J Pet aI. HAL:A multi-paradigm approach to automatic datapath synthesis. Proc. 23rd Design Automation Conf.,1986,263-270P
[64] 何中礼，庄镇泉．一种数字电路高层次综合器DLS．电子学报，1994，22(11)：49-54页
[65] Jiang Y M. Performance-driven interconnection optimization for microarchitecture synthesis. IEEE trans on CAD ,1994 ,13(2): 137-149P
[66] Minjoong Rim, Rajiv Jain and Renato De Leone. Optimal Allocation and Binding in High-Level Synthesis. In Proc. ACM/IEEE 29th DAC, 1992: 120-123P
[67] Catheherine H Gebotys. Optimal Scheduling and Allocation of Embeded VLSI Chips. In Proc. ACM/IEEE Trans VLSI, Vol, 1, No. 3, Sept. 1993 ,233-243P
[68] 刘明业，张东晓，叶梅龙，李雁．专用集成电路高级综合理论．北京：北京理工大学出版社1998
[69] 傅清祥，王晓东．算法与数据结构．北京：电子工业出版社1998
[70] 张力昂可计算性与计算复杂性导引．北京：北京大学出版社1996
[71] Michael R. Garey, David S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W.H. Freeman and Company. 1979
[72] Marin D. Davis, Elaine J. Weyuker, Computability, Compleity, and Languages, Fundamentals of Theoretical Computer Science, Academic Press, Inc. 1983
[73] TSENG C J, SIEWIOREK D P. Automated Synthesis of Data Paths in Digital Systems. IEEE Trans. on CAD, 1986,5(3):379-393P
[74] J.G. Augustson and J. Minker. An analysis of some graph theoretical cluster techniques. J. ACM. 1970,17(4):571-588P
[75] C. Bron and J. Kerbosch. Finding all cliques of an undirected graph-Algorithm 457. Commun. ACM. 1973,16(9):575-577P
[76] G.D. Mulligan and D.G. Corneil. Corrections to Bierstone' s Algorithm for Geneating Cliques. J. ACM 1972,19(2):244-247P
[77] M.C. Paull and S.H. Unger. Minimizing the number of states in Incompletely specified sequential functions. IRE Trans. Electronic Computers. 1959, vol. EC-8,356-367P
[78] S. Tsukiyama, M. Ide, H. Ariyoshi, I. Shirakawa. A new algorithm for generating all the maximal independent sets. SIAM J. Computing .1977, vol. 6 505-517P
[79] CONG J, PAN D Z. Interconnect estimation and planning for deep submicron designs[A].Tech Rep 980035[R].UCLS CS Dept, 1998:507-510P
[80] LAGNESE E, THOMAS D. Architectural partitioning for system level synthesis of integrated circuits[J]. IEEE Trans on CAD, 1991,10(7):847-860P
[81] 刘泽坚，陆宏达．用复杂数学系统测试的整体功能模型[J]．计算机辅助设计与图形学学报，1999，11(6)：542—546页
[82] Rechenberg, I. Evolutions strategie:Optimierung technischer System nach Prinzipen cler biologischen Evolution. Frommann-Holzboog Verlag, Stuttgart, 1973.
[83] Schwefel, H.-P., Numerical Optimization for Computer Models, John Wiley ,Chichester ,UK. 1981
[84] Fogel, L.J., Owens, A.J., and Walsh, M.j., Artificial Intelligence Through Simulated Evolution, John Wiley, Chichester, UK. 1996
[85] Holland, J.H., Adaptation in Natural and Artificial Systems , University of Michigan Press, Ann Arbor, 1975.
[86] Z．米凯利维茨著．周家趄译．演化程序—遗传算法和数据编码的结合．北京：科学出版社，2000
[87] 潘正君，康立山，陈毓屏著．演化计算．北京：清华大学出版社，广西：广西科学技述出版社，1998
[88] 谢涛，陈火旺，康立山，计算机学报，2003(8)：997-1003页
[89] Pareto V. Cours D' Economie Politique, volume Ⅰ and Ⅱ. F. Rouge, Lausanne, 1896
[90] Chipperfield A J, Fleming P J. Gas turbine engine controller desigh using multiobjective genetic algorithms. In:Proceedings of the 1st IEE/IEEE International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications, University of Sheffield, UK, 1995. 214-219P
[91] Fonseca C M , Fleming P J . Multiobjective optimization and multiple constrains handling with evolutionary algorithms-part I :A unified formulation, and part IIapplication example. IEEE Transactions on Systems, Man & Cybernetics-Part A: Systems and Humans, 1998,28 (1):26-47P
[92] Jones B R, Crossley W A, Lyrintzis A S. Aerodynamic and aeroacoustic optimization of airfoils via a parallel genetic algorithm. In : Proceedings of the 7th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, St. Louis, Mo, 1998.AIAA-98-4811
[93] 王志华,邓仰东。数字集成系统的结构化设计与高层次综合。北京：清华大学出版社，2001
[94] Subramaniam G, Ken R. Datapath Synthesis Using Genetic Algorithm . Computers and Electrical Engineer-ing, 26(2000):337-349P
[95] Ahmad I, Dhodhi M K et al. Integrated scheduling, allocation and module selection for design-space exploration in high-level synthesis. IEEE Proc, Comput. Digit. Tech., 1995, 142(1):65-71P
[96] Dhodhi M K, Ahmad I et al. High-level synthesis of datapaths for easy testability, IEEE Proc. Circuits, Devices and Systems, 1995, Aug, 209-219P
[97] When N, Held M et al.A novel scheduling/allocation approach for datapath synthesis based on genetic paradigms. North-Holland: Elsevier Science Publishiers B. V, 1991 [98] J.H.Holland, Adaptation in Natural and Artificial Systems. Ann Arbor, MI: University of Michigan, 1975
[99] Michalewicz Z . Genitic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, Berlin, 1992
[100] P. McGeer and R. Brayton. Provably correct critical paths. The Proceedings of the Decennial Caltech VLSI Conference, 1989
[101] W. Lam, R. Brayton, and A. Sangiovanni-Vincentelli. Circuit delay models and their exact computation using timed Boolean functions. IEEE/ACM Design Automation Conference' 93,1993
[102] H .C.CHEN and D.H. Du. Path sensitization in critical path problem. 1990 ACM Workshop on Timing Issues in the Specification and Synthesis of Digital Systems, 1990
[103] Devadas S , Keutzer K , Malik S . Computation of floating mode delay in combinational circuits: theory and algorithms. IEEE Trans CAD, 1993,12(12) :1913-1931P
[104] Lin C J, Reddy S M, On delay testing in logic circuits. IEEE Trans CAD, 1987,6(6): 694-703P
[105] Bhattacharya D, Agraval P, Agrawal C D. Test generation for p- ath delay faults using binary decision diagrams. IEEE Trans computers, 1945, 44(3):434-447P
[106] P. McGeer and R.Brayton. Provably correct critical paths. The Proceedings of the Decennial Caltech VLSI Conference, 1989
[107] 2000, 12 (4): 308-311
[108] S B Akers. Binary decision diagrams. IEEE Trans Comput . 1978, C-27: 509-516
[109] Randal E, Bryant. Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transactions On Computers , 1986 , C35(8) : 677-691
[110] Rolf Drechsler, Wolfgang Gunther , Fabio Somenzi. Using Lower ounds During Dynamic BDD Minimization. IEEE Transactions On Computer-Aided Design Of Intergrated Circuits And Systems. 2001, 20(1) : 51-57
[111] Wolfgang Gunther, Rolf Drechsler. Minimization of free BDDs. VLSI journal. 2002:41-59
[112] Beate Bollig, Ingo Wegener. Improving the Variable Ordering of OBDDs Is NP-Complete. IEEE Transactions On Computers . 1996, 45(9):993-1002
[113] Masahiro Fujita, Hisanori Fujisawa, Yusuke Matsunaga. Variable Ordering Algorithms Ffor Ordered Binary Decision Diagrams and Their Evaluation. IEEE Transactions On Computer-Aided Design Of Integrated Circuits And Systems. 1993,12(1):6-12
[114] Rudiger Ebendt, Wolfgang Gunther, Rolf Drechsler. An Improved Branch Bound Algorithm for Exact BDD Minimization. IEEE Transactions On Computer-Aided Design Of Integrated Circuits And systems. 2003, 22(12):1657-1663
[115] Shipra Panda , Fabio Somenzi . Who Are the Variables in Your Neighborhood. Proceedings of the 1995 International Conference on Computer-Aided Design. 1995:74-77
[116] Rolf Drechsler, Nicole Drechsler, Wolfgang Gunther. Fast Exact Minimization of BDD' s. IEEE Transactions On Computer-Aided Design Of Integrated Circuits And Systems.1993,19(3), 384-389
[117] Steven J Friedman , Kenneth J Supowit . Finding the Optimal Variab-le Ordering for Binary Decision Diagrams. IEEE Transactions On Computers. 1990, 39(5):710-713
[118] N Ishiura, H Sawada, S Yajima. Minimization of binary decision diagrams based on exchange of variables. Computer-Aided Design. 1991:472-475
[119] S W Jeong, T-S Kim, F Somenzi. An efficient method for optimal BDD ordering computation. VLSI and CAD. 1993
[120] R E Bryant . Graph-based algorithms for Boolean function manipulation . IEEE Trans Comput. 1991, 40:205-213
[121] Thomas R Shiple, Robert K Brayton. Heuristic Minimization of BDDs Using Don' t Cares. Annual ACM IEEE Design Automation Conference. 1994:225-231