Разработка и исследование методов логического синтеза быстродействующих цифровых КМОП БИС
Диссертация
Особенно остро вопрос быстродействия стоит для схем функций арифметического блока. Критической для таких схем является задержка схемы переноса, структура которой почти полностью определяет быстродействие арифметического блока. Некоторые из исследований в области синтеза схем переноса имеют чисто теоретическое значение: рассматривается синтез асимптотически оптимальных схем. Реальные схемы… Читать ещё >
Список литературы
- Вартанян С.М. Новое доказательство минимальности контактной схемы, реализующей линейную функцию // Методы дискретного анализа в изучении реализаций логических функций. Вып.41. Новосибирск. — 1984.
- Исаева Т. Ю. Корнилов А.И., Алгоритм декомпозиции логических функций, ориентированный на синтез быстродействующих цифровых устройств. // Информационные технологии. Вып. 4. — С. 26 -30 — 2001.
- Кармазинский А.Н. Синтез принципиальных схем элементов на МДП-транзисторах. -М.: Радио и связь. 1983.
- Корнилов А.И. и др. Устройство переноса // Свидетельство об изобретении СССР № 1 608 648, G 06 F 7/50. 1988.
- Корнилов А.И. Проектирование быстродействующих арифметических устройств в универсальном логическом базисе // Техника средств связи. Сер. Микроэлектронная аппаратура,-Вып. 1−2 (12−13). М.: С. 41−47. — 1990.
- Корнилов А.И. Универсальная ячейка базового кристалла и метод синтеза схем // Техника средств связи. Сер. Микроэлектронная аппаратура Вып. 1−2 (6−7). — С. 64−67. — 1985.
- Корнилов А.И. Устройство переноса // Свидетельство об изобретении СССР № 1 402 145, G 06 F 7/50. 1986.
- Корнилов А.И., Коренева Т. Ю. Синтез КМОП схем с ограниченной глубиной // Тезисы докладов конференции молодых специалистов. Часть II ЦООНТИ «ЭКОС». — 1986.
- Логическое проектирование БИС/В.А. Мищенко, А. И. Аспидов, В. В. Витер и др.- Под ред. В. А. Мищенко. М.: Радио и связь. — 1984.
- Лупанов О.Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики. Вып. .10. -М.: Физматгиз, 1963. С.63−97.
- Лупанов О.Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. Вып. 3. М.: Физматгиз, 1960. — С.61−80.
- Лупанов О.Б. Об одном подходе к синтезу управляющих систем принципе локального кодирования // Проблемы кибернетики. Вып. 14. — М.: Физматгиз, 1965. -С.31−110.
- Немудров В.Г., Корнилов А. И., Исаева Т. Ю. Синтез схем на основе КМОП базовых кристаллов // Автоматизация проектирования в радиоэлектронике и вычислительной технике: Материалы семинара М. — 1987.
- Немудров В.Г., Корнилов А. И., Коренева Т. Ю. Синтез электрических схем цифровых устройств на КМОП БК // Техника средств связи. Сер. Микроэлектронная аппаратура- 1985, вып. 1−2 (6−7).
- Нигматуллин Р.Г. Сложность булевых функций. М., «Наука». — 1988.
- Окольнишникова Е.А. Нижние оценки сложности реализации характеристических функций двоичных кодов бинарными программами // Методы дискретного анализа в синтезе реализаций булевых функций. Сб. научных трудов, вып.51, Новосибирск. -1991.-С. 61−83.
- Окольнишникова Е.А. О сравнении сложностей бинарных k-программ // Дискретный анализ и исследование операций 1995. — Т.2, № 4. — С. 54−73.
- Поваров Г. Н. Метод синтеза вычислительных и управляющих контактных схем // Автоматика и телемеханика. 1957. — Т. 18, № 2. — С. 145−162.
- Редькин Н.П. О минимальной реализации двоичного сумматора // Проблемы кибернетики. Вып. 38. М.: Наука. — 1981. — С. 181−216.
- Редькин Н.П. О реализации монотонных булевых функций контактными схемами // Проблемы кибернетики. Вып. 35. М.: Наука. — 1979. — С. 87−110.
- Сапоженко А. А.- Ложкин С.А. Методы логического проектирования и оценки сложности схем на дополняющих МОП транзисторах. Микроэлектроника, АН СССР, т. 12, вып. 1 1983.-С. 42−47.
- Сапоженко А.А.- Ложкин С.А. Метод каскадов для КМОП схем. Техника средств связи, Сер. Микроэлектронная аппаратура, вып. 1−2 (6−7). 1985. — С. 84−90.
- Храпченко В.М. О сложности реализации симметрических функций формулами // Матем. заметки. 1972.-Т. 11, № 1. — С.109−120.
- Шагурин И.И. Основы формального схемотехнического синтеза цифровых микросхем на биполярных транзисторах // Микроэлектроника, т.8, вып.2, 1979. -С.114−130.
- Яблонский С. В. Функциональные построения в k-значной логике // Труды МИ АН СССР. Т.51. -М.: Изд-во АН СССР, 1958.
- Akers, S. В. Binary Decision Diagrams // IEEE Trans. Comput., Vol. C-27, No. 6, p. 509 516. 1978.
- Ashar, P.- Cheong, M. Efficient Breadth-First Manipulation of Binary Decision Diagrams // Proc. oflCCAD. 1994.
- Bahar, R.I. et al. Algebraic Decision Diagrams and Their Applications II Bahar, R.I.- Frohm, E.A.- Gaona, C.M.- Hachtel, G.D.- Macii, E.- Pardo, A.- Somenzi, F. Proc. of Int. Conf. On Computer-Aided Design. — 1993.
- Berman, C.L. Ordered Binary Decision Diagrams and Circuit Structure // Proc. of ICCDVS9, pp. 392−395. 1989.
- Bern, J.- Meinel, C.- Slobodova, A. Global Rebuilding of OBDD’s Tunneling Memory Requirement Maxima // Proc. of the 32nd DAC, pp. 408−413. — 1995.
- Bollig, В.- Lobbing, M.- Wegener, I. Simulated Annealing to Improve Variable Orderings for OBDDs // Proc. of IFIP Workshop on Logic and Architectural Synthesis, Grenoble. -1994.
- Bollig, В.- Savicky, P.- Wegener, I. On the Improvement of Variable Orderings for OBDDs // Proc. of Int. Workshop on Computer-Aided Design & Test, Dagstuhl. 1995.
- Brace, K. S.- Rudell, R. L.- Bryant, R. E. Efficient Implementation of a BDD Package // Proc. of the 27th DAC, pp. 40−45. 1990.
- Bryant, R. E. Bit-Level Analysis of an SRT Divider Circuit // Proc. of the 33rd DAC. -1996.
- Bryant, R. E. Graph-Based Algorithms // IEEE Trans. Comput., Vol. C-35, No. 8, pp. 677−691.- 1986.
- Bryant, R. E. Symbolic Boolean Manipulation with Ordered Binary-Decision Diagrams // ACM Computing Surveys, Vol. 24, No 3. 1992.
- Burgun, L. et al. Multilevel Logic Optimization of Very High Complexity Circuits // Burgun, L.- Dictus, N.- Greiner, A.- Prado Lopes, E.- Sarwary, C. ACM. — 1994.
- Butler, R. M. et al. Heuristics to Compute Variable Orderings for Efficient Manipulation of Ordered Binary Decision Diagrams // Butler, R. M.- Ross, D. E.- Kapur, R.- Mercer, M. R. -Proc. of the 28th DAC. 1991.
- Chang, S. С.- Marek-Sadowska, M.- Hwang Т. T. Technology Mapping for TLU FPGA’s Based on Decomposition of Binary Decision Diagrams // IEEE Trans, on Computer Aided Design of Integrated Circuits and Systems, Vol. 15 No 10. 1996.
- Chen, C. -S.- Hwang, Т. -Т.- Lin, C. L. Low-Power FPGA Design A Re-Engineering Approach // Proc. of the 34th DAC. — 1997.
- Chen, C.-S. et al. Combining Technology Mapping and Placement for Delay-Minimization in FPGA Design. // Chen, C.-S.- Tsay, Yu-W.: Hwang, T.-T.- Lin, C. L. IEEE Trans, on CAD of Integrated Circuits and Systems, Vol. 14, No 9. — 1995.
- Clarke, E.M. et al. Spectral Transforms for Large Boolean Functions with Application for Technology Mapping // Clarke, E.M.- McMillan, K.L.- Zhao, X.- Fujita, M.- Yang, J. Proc. of the 30th DAC. — 1993.
- Devadas, S.- Malik, S. A Survey of Optimization Techniques Targeting Low Power VLSI Circuits. // Proc. of the 32nd DAC, 1995.
- Drechsler, R.- Drechsler, N.- Gunther, W. Fast Exact Minimization of BDDs // Proc. of the 35th DAC.- 1998.
- Drechsler, R.- Horeth, S. Manipulation of *BMDs // Proc. ofthe 35th DAC. 1998.
- Fortas, A.- et al. Mapping Techniques for QuickLogic FPGA // Fortas, A.- Bouzouzou, H.- Crastes, M.- Roane, R.- Saucier, G. Proc. of SASIMT1995, pp. 184−190. — 1995.
- Friedman, S. J.- Supowit, K. J. Finding the Optimal Variable Ordering for Binary Decision Diagrams // Proc. ofthe 24th DAC. 1987.
- Friedman, S. J.- Supowit, K. J. Finding the Optimal Variable Ordering for Binary Decision Diagrams // IEEE Trans. Comput., Vol. C-39, No 5, pp. 710−713. 1990.
- Fujita, M.- Chen, К. C. Network Resynthesis for Delay Minimization. // Proc. of SASIMI-92, pp. 26−35.- 1992.
- Fujita, M.- Fujisawa, H.- Kawato, N. Evaluation and Improvements of Boolean Comparison Method Based on Binary Decision Diagrams // Proc. of ICCAD. 1988.
- Fukui, M- Newton, A. R. Optimum Module Generation for Semi-Custom Design. Proc. ofAPCCAS'92. 1992.
- Galans, N. et al. Advanced Ordering Manipulation Techniques for Binary Decision Diagrams // Galans, N.- Zhang, Q.- Jacobi, R.- Yernaux, В.- Trullemans, A. -M. Proc. of the European Conf. on Design Automation EDAC'92. — 1992.
- Gavrilov, S. et al. Library-Less Synthesis for Static CMOS Combinational Logic Circuits // Gavrilov, S.- Glebov, A.- Pulella, S.- Moore, S. C.- Dharchoudhury, A.- Panda, R.- Vijayan, G.- Blaauw, D. T. Proc. ofICCAD'97. — 1997.
- Gavrilov, S.- Glebov, A. BDD-based Circuit Level Structural Optimization for Digital CMOS. // Proc. of MALOPD'99 Workshop Moscow, Russia, September 12−13. — 1999.
- Glebov, A.- Blaauw, D.- Jones, L. Transistor Reordering for Low-Power CMOS Gates Using SP-BDD Representation // Proc. of Int. Symp. on Low Power Design, p. 161. 1995.
- Hinsberger, U.- Kolla, R. Boolean Matching for Large Libraries // Proc. of the 35th DAC. 1998.
- Hong, Y. et al. Safe BDD Minimization Using Don’t Cares // Hong, Y.- Beerel, P. A.- Burch, J.R.- McMillan, K.L. Proc. of the 34th DAC. — 1997.
- Horeth, S. Compilation of Optimized OBDD-Algorithms // EURO-DAC'96 with EURO-VHDL'96.-1996.
- Horeth, S.- Drechsler, R. Dynamic Minimization of Word-Level Decision Diagrams // Proc. of DATE'98. 1998.
- Iman, S.- Pedram, M. Pose: Power Optimization and Synthesis Environment // Proc. of DAC'96. 1996.
- Isaeva T. Y. Switch-Level BDD Based Synthesis Algorithm // Proc. of MALOPD'99 Workshop Moscow, Russia, September 12−13. — 1999.
- Ishiura, N. Synthesis of Multi-Level Logic Circuits from Binary Decision Diagrams // Proc. of SASIMI-92, pp. 74−83. 1992.
- Ishiura, N.- Sawada, H.- Yajima, S. Minimization of Binary Decision Diagrams Based on Exchanges of Variables // Proc. of ICC AD. 1991.
- Ishiura, N.- Yajima, S. A Class of Logic Functions Expressible by Polynomial-Size Binary Decision Diagrams // Proc. of SASIM1−90. 1990.
- Jacobi, R.P.- Trullemans, A.-M. ROBDD-based Logic Decomposition Techniques // Proc. of IFIP Workshop on Logic and Architecture Synthesis, Institut National Polytechnique de Grenoble, France, December 19−20. 1994.
- Jain, J. et al. Indexed BDDs: Algorithmic Advances in Techniques to Represent and Verify Boolean Functions // Jain, J.- Bitner, J.- Abadir, M.S.- Abraham, J.A.- Fussell, D.S. IEEE Trans. On Computers, Vol. 46, No. 11. 1997.
- Jeong, S. -W. et al. Variable Ordering for Binary Decision Diagrams // Jeong, S. -W.- Plessier, В.- Hachtel, G. D.- Somenzi, F. Proc. of the European Conf. on Design Automation EDAC'92. 1992.
- Kebschull, U.- Schubert, E.- Rosenstiel, W. Multilevel Logic Synthesis Based on Functional Decision Diagrams // Proc. of European Design Conf., pp. 43−47. 1992.
- Kornilov A. I., Isaeva T. Y. BDD Based Decomposition for Depth Reduction // IV International Design Automation Workshop «Russian Workshop'94»: Abstracts of Papers Submitted to Russian Workshop'94 Moscow, Russia, June 28−29. — 1994.
- Kornilov A. I., Isaeva T. Y. Circuit Depth Optimisation by BDD Based Function Decomposition // Logic and Architecture Synthesis: State-of-the-art and novel approaches -Chapman&Hall, edited by G. Saucier and A. Mignotte. 1995.
- Kornilov A. I., Isaeva T. Y. Circuit Depth Optimization by BDD Based Function Decomposition // Proc. of IFIP Workshop on Logic and Architecture Synthesis, Institut National Polytechnique de Grenoble France, December 19−20. — 1994.
- Kornilov A. I., Isaeva T. Y., Syngaevsky V. A. Carry Circuit Depth Optimisation by BDD Based Decomposition // Proc. of PATMOS'97 Workshop Louvain-la Neuve, Belgium, September 8−10.- 1997.
- Kukimoto, Y.- Fujita, M.- Brayton, R. K. A Redesign Technique for Combination Circuits Based on Gate Reconnections // Proc. of ICCAD. 1994.
- Lai, Yung-Te- Pedram, M.- Pan, R. OBDD-Based Function Decomposition: Algorithms and Implementation // IEEE Trans, on Computer Aided Design of Integrated Circuits and Systems, Vol. 15 No 8.- 1996.
- Lai, Yung-Te- Pedram, M.- Vrudhula, S. BDD Based Decomposition of Logic Functions with Application to FPGA Synthesis // Proc. of the 30th DAC. 1993.
- Laurent, В.- Saucier, G. Performance/Power Tradeoffs in ASIC Multipliers. // Proc. of PATMOS'97 Workshop. 1997.
- Lavagno, L. et al. Timed Shannon Circuits: A Power-Efficient Design Style and Synthesis Tool // Lavagno, L.- McGeer, P. C.- Saldanha, A.- Sangiovanni-Vincentelli, A. L. Proc. of the 32nd DAC.- 1995.
- Lee, C. Y. Representation of Switching Circuits by Binary-Decision Programs // Bell Syst. Tech. J., Vol. 38, pp. 985−999. 1959.
- Lin, В.- Newton, A. R. Implicit Manipulation of Equivalence Classes Using Binary Decision Diagrams // Proc. of the European Conf. on Design Automation EDAC'92. 1992.
- Malik, S. et al. Logic Verification Using Binary Decision Diagrams in a Logic Synthesis Environment // Malik, S.- Wang, A. R.- Brayton, R. K.- Sangiovanni-Vincentelli, A. Proc. of the ICCAD. — 1988.
- Manne, S.- Grunwald, D.- Somenzi, F. Remembrance of Things Past: Locality and Memory in BDDs // Proc. of the 34th DAC, p. 196−201. 1997.
- Meinel, C.- Somenzi, F.- Theobald, T. Linear Sifting of Decision Diagrams // Proc. of the 34th DAC. 1997.
- Meinel, C.- Theobald, T. Ordered Binary Decision Diagrams and Their Significance in Computer-Aided Design of VLSI Circuits a Survey // Electronic Colloquium on Computational Complexity, report No. 39. — 1998.
- Minato, S. Calculating of Unate Cube Set Algebra Using Zero Suppressed BDDs.
- Minato, S. Fast Generation oflrredundant Sum-of-Products Forms from Binary Decision Diagrams // Proc. of SASIMI-92, pp. 64−73. 1992.
- Minato, S. Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems // Proc. of the 30th DAC.- 1993.
- Minato, S.- Ishiura, N.- Yajima, S. Shared Binary Decision Diagram with Attributed Edges for Efficient Boolean Functions Manipulation // Proc. of the 27th DAC. 1990.
- Moller, D.- Molitor, P.- Drechsler, R. Symmetry Based Variable Ordering for ROBDDs // Proc. of IFIP Workshop on Logic and Architecture Synthesis, Institut National Polytechnique de Grenoble, France, December 19−20. 1994.
- Moret, В. M. Decision Trees and Diagrams // Association on Computing Mash., Comput. Surv., Vol. 14, pp. 593−623. 1982.
- Motorola H4C Series Design Reference Guide, p. 7−165.
- Murgai, R et al. Logic Synthesis for Programmable Gate Arrays // Murgai, R.- Nishizaki, N.- Shenoy, N.- Brayton, R.K.- Sangiovanni-Vincentelli, A. Proc. of the 27th DAC. — 1990.
- Murgai, R.- Brayton, R.K.- Sangiovanni-Vincentelli, A. Optimum Functional Decomposition Using Encoding. // Proc. of the 31st DAC. 1994.
- Narayan, A. et al. Partitioned ROBDDs // Narayan, A.- Jain, J.- Fujita, M.- Sangiovanni-Vincentelli, A. -Proc. ofICCAD'96. 1996.
- Panda, S.- Somenzi, F.- Plessier, B. F. Symmetry Detection and Dynamic Variable Ordering of Decision Diagrams // Proc. of ICCAD. 1994.
- Poirot, F.- Roane, R.- Tarroux, G. Boolean Optimization Using Implicit Techniques // Proc. of IWLAS. 1994.
- Rajgopal, S.- Tyagr, A. Dynamic Distance Based BDD Ordering // Proc. of SASIMI-92, pp. 54−63. 1992.
- Riera, J. et al. From BDDs to CMOS Complex Gates // Riera, J.- Ribas, L.- Velasco, A. J.- Carrabina, J. Proc. of IWLAS. — 1996.
- Riera, J. et al. Switch-Level Technology Mapping and Modeling // Riera, J.- Velasco, A. J.- Ribas, L.- Carrabina, J. Proc. of PATMOS'97 Workshop. — 1997.
- Rudell, R. Dynamic Variable Ordering for Ordered Binary Decision Diagrams // Proc. of the Int. Conf. on Computer Aided Design, pp. 42−47. 1993.
- Rudell, R. Tutorial: Design of a Logic Synthesis System // Proc. of the 33rd DAC. 1996.
- Sauerhoff, M.- Wegener, I. On the Complexity of Minimizing the OBDD Size for Incompletely Specified Functions // IEEE Transactions of Computer Aided Design of Integrated Circuits and Systems. Vol. 15, No. 11, p. 1435−1437. — 1996.
- Sawada, H.- et al. Logic Synthesis Method for Look-Up Table Applications Using Functional Decomposition and Support Minimization // Sawada, H.- Suyama, Т.- Yukishita, M.- Nagoya, A. Proc. of SASIMT95, pp. 161−168. — 1995.
- Scholl, C. et al. Minimizing ROBDD Sizes of Incompletely Specified Boolean Functions by Exploiting Strong Symmetries // Scholl, C.- Melchior, S.- Hotz, G.- Molitor, P. Proc. Of EDAC'97
- Scholl, C. Multi-Output Functional Decomposition with Exploitation of Don’t Cares. DATE'98, 1998.
- Singh, K. J.- Wang, A. R.- Brayton, R. K.- Sangiovanni-Vincentelli, A. Timing Optimization of Combinational Logic. // Proc. of ICCAD. 1988.
- Somenzi, F. CUDD: CU Decision Diagram Package, ftp://vlsi.colorado.edu/pub/
- Stanion, Т.- Sechen, C. A Method for Finding Good Ashenhurst Decomposition and Its Application to FPGA Synthesis // Proc. of the 32nd DAC, pp. 60−64. 1995.119
- Stanion, Т.- Sechen, С. Boolean Division and Factorization Using Binary Decision Diagrams // Proc. of IEEE Asia-Pacific Conference on Circuits and Systems (APCCAS'92), pp. 190−195.- 1992.
- Tachibana M. Heuristic Algorithms for FBDD node Minimization with Application to Pass-Transistor Logic and DCVS Synthesis // SASIMI-96, pp. 96−101. 1996.
- Trullemans-Anckaert, A.-M. et al. A Multi-Target Design Approach for Power Critical VLSI Systems / A.-M. Trullemans-Anckaert, R. Ferreira, G. Saucier, T. Isaeva // Proc. of SASIMI-2000. -2000.
- Tsai, M. H., Hwang, Т. Т.- Lin, Y. L. Technology Mapping for Field Programmable Gate Arrays Using Binary Decision Diagrams // Proc. of SASIMI-92, pp. 84−92. 1992.
- Weinmann, U.- Rosenstiel, W. Network Flow Based Clustering and Partitioning for FPGAs // IFIP Workshop on Logic and Architectural Synthesis. 1994.
- Yang, C.- Singhal, V.- Ciesielski, M. BDD Decomposition for Efficient Logic Synthesis // Proc. of ICCD'99, pp. 626−631. 1999.
- Yang, S. et al. Space- and Time- Efficient BDD Construction via Working Set Control // Yang, S.- Chen, Y.-A.- Bryant, R.E.- O’Hallaron, D.R. Proc. of ASP-DAC'98, pp. 433−446. — 1998.
- Ye, Y.- Roy, K. A Graph-Based Synthesis Algorithm for AND/XOR Networks // Proc. of the 34th DAC. 1997.
- Zhong, P. et al. Using Reconfigurable Computing Techniques to Accelerate Problems in the CAD Domain: A Case Study with Boolean Satisfiability // Zhong, P.- Ashar, P- Malik, S.- Martonosi, M. Proc. of the 35th DAC. — 1998.
- Zhou, H.- Wong, D.F. Exact Gate Decomposition for Low-Power Technology Mapping. // Proc. of the 34th DAC. 1997.120