Быстродействующий метод размещения элементов СБИС с учетом загрузки коммутационных слоев тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Марченко, Михаил Александрович

• Марченко, Михаил Александрович
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Марченко, Михаил Александрович

Введение

Глава 1. Современные проблемы автоматизации проектирования топологии СБИС

1.1. Технологические тенденции и конструкторские требования

1.2. Основные этапы решения задачи размещения

1.3. Критерии качества и тестовые примеры

1.4. Аналитические методы

1.5. Дихотомические алгоритмы

1.6. Комбинированные алгоритмы

1.7. Результаты сравнения на ISPD

1.8. Методы легализации, детального размещения и ЕСО

1.9. Эффективность алгоритмов размещения в зависимости от схемы и библиотеки 49 Выводы

Глава 2. Методы оптимизации размещения

2.1. Модель графа перестановок

2.2. Алгоритм оптимизации размещения элементов

Глава 3. Оценка трассируемости с использованием вероятностного анализа

3.1. Постановка задачи

3.2. Оценка перегрузок

3.3. Запреты на трассировку

3.4. Оптимизация трассируемости 97 Выводы

Глава 4. Метод оценки деревьев Штейнера, адаптирующийся к критериям трассировки

4.1. Постановка задачи

4.2. Похожие деревья

4.3. Нахождение взаимнооднозначного соответствия между вершинами

4.4. Алгоритм построение дерева Штейнера.

Выводы

Глава 5. Программная реализация алгоритмов

5.1 Структура данных для алгоритмов оптимизации

5.2 Оценка трассируемости

5.3 Реализация общего оптимизационного алгоритма

5.4 Оптимизация трассируемости

5.5 Легализация элементов СБИС 135 5.6. ЕСО размещение 139 Выводы

Введение диссертации (часть автореферата) на тему «Быстродействующий метод размещения элементов СБИС с учетом загрузки коммутационных слоев»

Актуальность работы.

Прогресс в развитии нанотехнологий, а именно, дальнейшее уменьшение технологических размеров транзисторов и проводников привел к уменьшению удельного веса задержки в транзисторе в общей задержке по цепи более чем на три порядка. Эта тенденция отразилась на эволюции алгоритмов размещения элементов СБИС, которые активно развивались в последнее время. Задача размещения элементов СБИС существенно усложнилась также за счет увеличения размерности задачи до нескольких миллионов элементов и ужесточения технологических требований. В совокупности это привело к необходимости проведения дополнительной оптимизации после глобального и детального размещения элементов Критериями оптимизации могут быть трассируемость, рабочая частота, выделение тепла, потребление питания и другие. В совокупности этот этап носит название этапа инженерных изменений (ЕСО) В настоящее время на этапе ЕСО применяются различные эвристические методы, в том числе интерактивные процедуры Отсутствие общей методологии проведения ЕСО - оптимизации делает этот этап одним из критических. Задача разработки ЕСО - методологии является крайне актуальной.

Цель диссертационной работы состоит в разработке ЕСО маршрута, который позволит объединить в одном ЕСО процессе как автоматические, так и интерактивные методы оптимизации размещения и стандартные ЕСО операции, а также в разработке эффективных методов и алгоритмов оптимизации размещения элементов СБИС по различным критериям. Для достижения данной цели в диссертационной работе решаются следующие задачи:

- разработка математической модели графа перестановок;

- разработка общего эффективного алгоритма оптимизации размещения элементов СБИС;

- разработка алгоритмов оценки и оптимизации трассируемости, разработка метода построения деревьев Штейнера, основанного на знаниях, для быстрой точной оценки топологии цепи;

- разработка алгоритма ЕСО размещения (размещение и легализация элементов, добавленных для достижения заданных технологических параметров)

Научная новизна результатов, представленных в данной диссертационной работе, заключается в следующем:

- предложен метод, объединяющий в одном ЕСО процессе как автоматические, так и интерактивные алгоритмы оптимизации размещения и стандартные ЕСО операции, который, в отличие от известных, позволяет восстанавливать легальность размещения после внесения изменений без проведения полного переразмещения элементов.

- разработана модель графа перестановок, которая в отличие от известных, учитывает изменение длины цепей, позволяет точно определять стоимость каждой перестановки, что дает возможность улучшить качество и скорость оптимизации;

- предложен алгоритм оценки деревьев Штейнера, основанный на знаниях. Отличительной особенностью этого алгоритма является то, что он строит деревья Штейнера по заданному образцу, тем самым могут быть использованы любые неформальные критерии и учтены сложные ограничения. Кроме того, алгоритм является универсальным и может быть адаптирован под любую конкретную задачу через создание специализированной библиотеки образцов;

- разработан алгоритм оптимизации и оценки трассируемости, его отличительной особенностью является то, что он не производит полного переразмещения элементов, сохраняет легальность и не нарушает других характеристик размещения;

- разработан быстродействующий алгоритм оптимизации размещения элементов по длине цепей. Предложенный алгоритм не производит переразмещения элементов, сохраняет глобальную структуру размещения и легальность.

Реализация.

На базе предложенных алгоритмов разработан комплекс программ оптимизации размещения, оценки трассируемости и ЕСО размещения по различным критериям. Программы оценки трассируемости, оптимизации размещения по длине цепей и трассируемости, легализации используются в модуле размещения программного продукта "Go Placement". Программа ЕСО размещения реализована в виде отдельной подсистемы и предназначена для корректировки размещения согласно списку технологических нарушений. Разработанные программы внедрены в ЗАО "Гамбит" и использовались в ИППМ РАН.

Практическая значимость работы.

Алгоритмы и подходы, предложенные в данной работе, реализованы в виде программы оптимизации размещения элементов, которая используются при проектировании СБИС. Алгоритмы оценки и оптимизации трассируемости используются при проектировании СБИС с высокой утилизацией и сложными технологическими ограничениями. Реализация алгоритма ЕСО размещения является неотъемлемой частью процесса ЕСО, широко используемого при проектировании специализированных СБИС (время прохождения сигнала, минимизация потребления электроэнергии) в настоящее время. С использованием данных программ было произведено проектирование ряда СБИС для ведущих мировых производителей микропроцессоров.

Апробация основных теоретических и практических результатов работы проводилась на конференциях:

• Международная научно-техническая конференция «Интеллектуальные САПР» (г. Геленджик, 2002-2005 г., 4 доклада)

• 8 Международный семинар «Дискретная математика и ее приложения» (МГУ, 2004 г., 1 доклад)

Публикации. Результаты диссертации отражены в 7 публикациях.

Структура и объем диссертационной работы. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы. Работа содержит 156 страниц и акты о внедрении.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Марченко, Михаил Александрович

Выводы

1. Программный пакет "Go Placement" представляет собой платформу для реализации различных алгоритмов размещения и оптимизации элементов СБИС;

2. Представленные в этой главе реализации алгоритмов работают в составе общей системы и общего потока проектирования СБИС;

3. Результаты тестирования на реальных примерах показали эффективность работы реализованных алгоритмов;

4. Среди направлений дальнейшей работы по реализации можно выделить повышение операционной эффективности программных модулей, улучшение каналов интеграции и взаимодействия между различными подсистемами.

Заключение.

Настоящая диссертационная работа посвящена исследованию проблем размещения элементов СБИС при соблюдении современных технологических ограничений, а именно, алгоритмов легализации и ЕСО размещения с учетом загрузки коммутационных слоев.

1. Предложен ЕСО маршрут, который, в отличие от традиционного подхода, позволил объединить в одном ЕСО процессе как автоматические методы оптимизации размещения так и интерактивные ЕСО операции над логической схемой.

2. Разработан и исследован алгоритм оптимизации легального размещения, который, в отличие от известных, основан на специализированной модели «графа перестановок» и обладает следующими преимуществами:

• для определения изменения целевой функции при применении перестановки не нужно производить ее явное вычисление (это в точности вес цикла в графе);

• существует возможность выхода из локальных минимумов за счет использования ребер с отрицательным весом;

• используется статистическая информация обо всех возможных перемещениях, такая как сумма длин всех ребер графа, максимальный и минимальный вес ребра и другие; в известных алгоритмах решение принимается, исходя только из локальных данных, таких как выигрыш при перестановке;

• предусмотрена возможность перераспределения незанятого места на кристалле и устранения трассировочных перегрузок;

• алгоритм учитывает специфику задачи и, как следствие, имеет меньшую сложность, что делает возможным его применение на задачах большой размерности.

3. Разработан алгоритм оптимизации размещения по равномерности загрузки кристалла, который, в отличие от известных алгоритмов:

• работает инкрементально,

• позволяет контролировать соблюдение разнообразных критериев в процессе оптимизации трассируемости, что дает возможность улучшить сходимость алгоритма и сохранить глобальную структуру размещения.

4. Разработан алгоритм построения и оценки деревьев Штейнера, который, в отличие от известных алгоритмов:

• адаптируется к заданным критериям трассировки,

• позволяет получать более точную оценку длины по сравнению с полупериметром,

• дает возможность применять различные стратегии трассировки на разных участках схемы.

Областью применения алгоритма являются цепи с небольшим числом контактов, что типично при проектировании СБИС.

5. Указанный подход может быть применен к задаче классификации графов, т.к. введенная метрика между множествами точек в метрическом пространстве распространяется также и на взвешенные графы (при условии выполнения неравенства треугольника для весов ребер).

6 Представленные в диссертации алгоритмы были реализованы и используются в составе программного пакета системы проектирования СБИС для проектирования СБИС по технологии 90нм.

7. Результаты тестирования на реальных примерах показали эффективность работы реализованных алгоритмов.

Список литературы диссертационного исследования кандидат технических наук Марченко, Михаил Александрович, 2006 год

1. http://www.itrs.net/Common/20051TRS/lnteiconnect2005 pdf

2. N. Viswanathan and С. С -N. Chu. Fastplace: Efficient analytical placement using cell hifting, iterative local refinement and a hybrid net model. IEEE Trans. Computer-Aided Design, to appear, 2005.

3. Goto. An efficient algorithm for the two-dimensional placement problem in electrical circuit layout. IEEE Trans, on Circuits and Systems, Vol. CAS-28(1):12-18, 1981.

4. A. E. Caldwell, A. B. Kahng, I. L. Markov, "Can Recursive Bisection Alone Produce Routable Placements?" DAC'OO, p. 477.

5. A. E. Caldwell, A. B. Kahng, I. L. Markov, "Optimal Partitioners and End-case Placers for Standard-cell Layout," IEEE Trans. On CAD 19(11), pp. 1304-1314, 2000.

6. A. E. Caldwell, A. B. Kahng, I. L. Markov, "Design and Implementation of Move-Based Heuristics for VLSI Hypergraph Partitioning," ACM J. on Experimental Algorithms, vol. 5,2000.

7. A. E. Caldwell, A. B. Kahng, I. L. Markov, "Improved Algorithms for Hypergraph Bipartitioning," ASPDAC 2000, pp. 661-666.

8. N. Selvakkumaran and G. Karypis, "THETO: A Fast and High-Quality Partitioning Driven Global Placer," Technical Report 03-046,2003, University of Minnesota.

9. K. W. Morton and D. F. Mayers. Numerical Solution of Partial Differential Equations. Cambridge University Press, 1994.

10. J. Cong and J. Shinnerl, editors. Multilevel Optimization in VLSICAD. Kluwer, Boston, 2003.

11. G. Karypis. Multilevel hypergraph partitioning. In Multilevel Optimization in VLSICAD, chapter 3. Kluwer Academic Publishers, Boston, 2003.

12. T. Chan, J. Cong, and K. Sze. Multilevel generalized force-directed method for circuit placement. In Proc. Int'l Symp. on Phys. Design, 2005.

13. A. Kahng and Q. Wang. Implementation and extensibility of an analytic placer. In Proc. Int'l Symp. on Phys. Design, pages 18-25, 2004.

14. K. Arrow, L. Huriwicz, and H.Uzawa. Studies in Nonlinear Programming. Stanford University Press, Stanford, CA, 1958.

15. J.Cong, M.Romesis, and J.Shinnerl. Fast floorplanning by look-ahead enabled recursive bipartitioning. In Asia South Pacific Design Automation Conf. 2005.

16. C.E. Radke. A justification of, and an improvements on, a useful rule for predicting circuit-to-pin ratios. In Proc. Design Automation Conf, pages 257-267, 1969.

17. D. Hill US patent 6,370,673: Method and system fro high speed detailed placements of cells within integrated circuit design, 2002.

18. A. B. Kahng and Q. Wang, "Implementation and Extensibility of Analytic Placer", Proc. Int. Symp. Physical Design, 2004, pp. 18-25.

19. A. B. Kahng and X. Xu, "Accurate Pseudo-Constructive Wirelength and Congestion Estimation", Proc. ACMInt Worbhop on System-Level Interconnect Prediction, April 2003, pp. 61-68.

20. W. Naylor et al., "Non-linear Optimization Systems and Method for Wire Length and Delay Optimization for an Automatic Electric Circuit Placer", US Patent 6301693, 0ct.2001.

21. B.Hu and M.Marek-Sadovska, "Multilevel Fixed-Points-Additions based Placement", to Appear on IEEE Trans. On CAD.

22. N.Viswanathan and C.C.-N Chu, "FastPlace:Efficient Analytical Placement using Cell Shifting, Iterative Local Refinement and Hybrid Net Model", Proc. Intl. Symp. On Physical Design, 2004.

23. K.Doll, F.M.Johannes, and K.J.Antreich. Iterative placement improvement by network flow methods. IEEE Trans. On CAD of Circuit and Systems, 13(10): 11891200, 1994.

24. T. F. Chan et al., "mPL6: A Robust Multilevel Mixed-Size Placement Engine". ISPD '05:227-229, 2005.

25. NuCAD. "IBM-PLACE benchmark", http://www.ece.nwu.edu/nucad/ibm-place.html.

26. M.А. Марченко "Оценка и оптимизация трассируемости", Информационные технологии, т 3, 2004.

27. Taraneh Taghavi, Xiaojian Yang, Bo-Kyung Choi "Dragon2005: large-scale mixed-size placement tool", ISPD '05,2005, p.245-247

28. Gi-Joon Nam "The ISPD'05 placement contest and benchmark suite", ISPD '05,2005, p.216-219

29. Patrick Hung, Michael J. Flynn "Stochastic congestion model for VLSI systems" Technical Report No. CSL-TR-97-737 October 1997

30. Jinan Lou, Shankar Krishnamoorthy, Henry S. Sheng "Estimating routing congestion using probabilistic analysis" ISPD 2001.

31. C.K. Cheng and E.S. Kuh. "Module placement based on resistive network optimization "IEEE Transactions onComputer aided design, 3(3):218-225, 1984.

32. R. S. Tsay, E.S. Kuh, and C. P. Hsu "PROUD: a sea-of-gates placement algorithms". IEEE Design and test of computers, 44-56, 1988.

33. M. A. Breuer "A Class of min-cut placement algorithms". In Design Automation Conference, 284-290. IEEE/ACM, 1977

34. M. A. Breuer. "Min-cut placement". J. Design Automation Fault-Tolerant Computing, l(4):343-382, 1977

35. U. Lauther. "A min-cut placement algorithm for general cell assemblies based an graph representation", In Desogn Automation Conference, pages 1-10. IEEE/ACM, 1979.

36. A. E. Dunlop and B. W. Kernigan. "A procedure for placement of standard cell VLSI circuits". IEEE Transactions on Computer Aided Design, 4(l):92-98, 1985

37. A. Srinivasan, K. Chaudhary, and E. S. Kuh. "RITUAL: A performance-driven placement algorthm". IEEE Transactions on Circuits and Systems 2: Analog and Digital Processing, 39(11):825-840, 1992.

38. D. Stroobandt and J. Van Campenhout. "Accurate interconnection length estimations for predictions early in the design cycle". VLSI Design, Special Issue on Physical Design in Deep Submicron, 10(1): 1-20, 1999

39. P. R. Suaris and G. Kedem. "Quadrisection: A new approach to standard cell layout". In International Conference on Computer-Aided Design, pages 474-477. IEEE/ACM, 1987

40. D. Huang and A. B. Kahng. "Partitioning-based standard-cell global placement with exact objective". In International Symposium on Physical Design, pages 18-25. ACM, 1997.

41. K. Shahookar and P. Mazumber. "VLSI Cell Placement Techniques". ACM Computing Surveys, 23(2): 143-220, 1991

42. С. Sechen. VLSI placement and global routing using simulated annealing. Kluwer, B. V., Deventer, The Netherlands, 1988.

43. C. Sechen. The TimberWolf3.2 standard cell placement and global routing program: user's guide for version 5/2, release 2. 1986

44. C. Sechen and A. Sangiovanni-Vincentelli. "TimberWolO.2: a new standard cell placement and global routing package". In Design Automation Conference, pages 432-439. IEEE/ACM, 1986.

45. L. Nagel. "SPICE2, A computer program to simulate semiconductor circuits", Univ. California, Berkley, CA, TR ERL-M520, 1995.

46. C. J. Alpert, A. Devgan, and C. Kashyap, "A two moment delay metric for performance optimization", in Proc Int. Symp. Physical Design, 2000, pages 69-74.

47. L. T. Pillage and R. A. Rohrer, "Asymptotic waveform evaluation for timing analysis", IEEE Trans. Computer-Aided Design, vol. 13, pp. 1526-1535, 1994.

48. C. L. Ratzlaff, N. Gopal, and L. T. Pillage, "RICE: Rapid interconnect circuit evaluator", in Proc. IEEE/ACM Design Automation Conf, 1991, pp. 555-560.

49. B. Tutiani, F. Dartu, and L. Pileggi, "Explicit RC-circuit delay approximation based on the first three moments of the impulse response", in Proc. IEEE/ACM Design Automation Conf, 1996, pp. 611-616.

50. A. B. Kahng and S. Muddu, "Two-pole analysis of interconnection trees", in Proc. IEEE Multi-Chip Module Conf, 1995, pp. 105-110.

51. W. C. Elmore, "The transient response of damped linear network with particular regard to wideband amplifiers", J Appl. Phys.,\ol 19, pp.55-63, 1948

52. L. T. Pileggi, "Timing metrics for physical design of deep submicron technologies", in Proc. Int Symp Physical Design, 1998, pp 28-33

53. J. Rubinstein, P. Penfield Jr., and M. A. Horowitz, "Signal delay in RC tree networks", IEEE Trans Computer Aided Design, vol. CAD-2, pp. 202-211, 1983.

54. R. Gupta, B. Tutuianu, and L. T. Pileggi, "The Elmore delay as a bound for RC trees with generalized input signals", IEEE Trans. Computer Aided Design, vol. 16, pp. 95104,1997.

55. J. Cong, L. He, C.-K. Koh, and P.H. Madden, "Performance optimization of VLSI interconnect layout", Integr. VLSI J., vol 21, pp. 1-94, 1996.

56. C.-K. Cheng, J. Lillis, S. Lin, and N. Chang, Interconnect Analysis and Synthesis. New York: Willey, 2000.

57. A. B. Kahng and S. Muddu, "Accurate analytical delay models for VLSI interconnects", Univ. California, Los Angeles, CA, UCLA CS Dept. TR-950034, 1995

58. A. B. Kahng and S. Muddu, "An analytical delay model for RLC interconnects", IEEE Trans. Computer-Aided Design, vol. 16, pp. 1507-1514, 1997.

59. B. Krauter, R. Gupta, J. Willis, and L. T. Pileggi, "Transmission line synthesis", in Proc. IEEE/ACM Design Automation Conference, 1995, pp. 358-363.

60. R. Kay and L. Pileggi, "PRIMO: Probability interpretation of moments for delay calculation", in Proc. IEEE/ACM Design Automation Conference, 1998, pp. 463-468.

61. L. O. Chua, Desoer, and Kuh, Linear and Non-linear Circuits. New york: McGraw-Hill, 1987.

62. M.Pedram and N.Bhat, "Layout Driven Technology Mapping", In Design Automation Conference, pp.99-105, 1991.

63. M.Pedram and N.Bhat, "Layout Driven Logic Restructure/Decomposition", Proc of Int. Conf. on Computer-Aided Design, pp. 134-137, 1991.

64. T.Kutzschebauch and L.Stok, "Congestion Aware Layout Driven Logic Synthesis", Proc. of Int. Conf. on Computer-Aided Design, pp.216-223, 2001.

65. P.Kudva, A.Sullivan and W. Dougherty, "Metrics for Structural Logic Synthesis", Proc. of Int. Conf on Computer-Aided Design, pp. 551-556, 2002.

66. Q. Liu and M. Marek-Sadowska, "A Study ofNetlist Structure and Placement Efficiency" In Int. Symp. On Phys. Design, pp. 198-203, 2004.

67. A.E.Caldwell, A.B.Kahng and I.L.Markov, "Can Recursive Bisection alone Produce Routable Placements", Design Automation Conference, pp.260-263, 2000.

68. T. F. Chan, J. Cong, J. Shinnerl and K. Sze, "An Enhanced Multilevel Algorithm for Circuit Placement", Proc. of Int. Conf on Computer-Aided Design, pp. 299-306, November 2003.

69. В Hu and M.Marek-Sadowska, "Fine-granularity Clustering for Large-scale Placement Problems", In Proc. Intl Symp. on Physical Design, pp.67-74, Apr 2003.

70. Tom Chen and Alkan Cengiz "Measuring Routing Congestion for Multi-Layer Global Routing" GLSVLSI2000.

71. Chin-liang Eric Cheng "RISA: Accurate and Efficient Placement Routability Modeling", 1994.

72. M. Burnstaein and S.J. Hong "Hierarchical VLSI Layout: Simultaneous Placement and Wiring of Gate Arrays" in VLSI, pp. 45-60,1983

73. S. Mayrhofer and U. Lauther, "Congestion-Driven Placement using a new multi-partitioning heuristic", IEEE International Conf. on CAD, pp. 332-335, 1990.

74. R.-S. Tsay, and S.C. Chang, "Early Wirability Checking and 2-D Congestion Driven Circuit Placement", IEEE International Conf. on ASIC, 1992.

75. Bryan Preas & Michael Lorenzetti, "Physical Design Automation of VLSI Systems", pp. 96-97, 1988.

76. W.-J. Sun & C. Sechen, "Efficient and effective placement for very large circuits", IEEE International Conference on CAD, pp. 170-177, 1993.

77. J. Soukup, "Circuit Layout", Proc of the IEEE, Vol. 69, No. 10, Oct. 1981

78. P.G. Karger and M. Malek "Formulation of components placement as a constrained optimization problem", Proceedings of the ICCAD, p. 814-819, 1984

79. C-L. E. Cheng, "RISA: Accurate and Efficient Placement Routability Modeling", Procedengs of International Conference an Computer Aided Design, pp. 690-695, 1994

80. M. Wang and M. Sarrafzadeh, "On the behavior of congestion minimization during placement", International symposium on physical design, pp. 145-150, 1999

81. S. Mayrhoferand U. Lauther, "Congestion-Driven Placement Using a New Multi-partitioning Heuristic", Proceedings of International Conference on Computer Aided Design, pp.332-335, 1990

82. P.N. Parakh, R.B. Brown and K.A. Sakallah, "Congestion Driven Quadratic Placement", Proceedings of 35th Design Automation Conference, pp. 275-278, 1998

83. R.S. Tsay, S.C. Chang and J. Thorvaldson, "Early Wireability Checking and 2-D Congestion Driven Circuit Placement", Proceedings of Fifth Annual IEEE International ASIC Conference and Exhibit, pp. 50-53, 1992

84. M. Wang and M. Sarrafzadeh, "Modeling and Minimization of Routing Congestion", Proceedings of Asian-Pacific Design Automation Conference, pp. 185-190,2000

85. Patrick Hung, Michael J. Flynn "Stochastic congestion model for VLSI systems" Technical Report No. CSL-TR-97-737, 1997

86. М.А. Марченко "Метод оптимизации легального размещения СБИС по длине цепей и равномерности загрузки кристалла", «Высокопроизводительные вычислительные системы» ИМВС РАН №2, 2004

87. L. Maliniak, "1С Tool Creates a Floorplan from HDL Code", Electronic Design, 1996

88. C. S. Chen, Y. W. Tsay, T. Hwang, A. Wu, and Y. L. Lin, "Combining Technology Mapping and Placement for Delay Minimization in FPGA Designs", IEEE transactions on Computer Aided Design of Integrate Circuits and Systems, pages 1076-1084, 1995

89. R. Dudzinski, "RTL Floorplanning Set to Drive Synthesis", EE Times, page 52,1995

90. T. Okamoto, and J. Cong, "Buffer Steiner Tree Construction with Wire Sizing for Interconnection Layout Optimization", Proc. Design Automation Conference, pp. 740-745, 1996

91. C.C.N. Chu and D.F. Wong, "A New Approach to Simultaneous Buffer Insertion and Wire Sizing", Proc. International Conference on Computer Aided Design, pp.614-622,1997

92. J. Lillis, and C.K.Cheng, "Timing Optimization for Multi-Source Nets: Characterization and Optimal Repeater Insertion", Proc. Design Automation Conference, pp. 214-219, 1997

93. J. Cong, C.K. Koh, and K.-S. Leung, "Simultaneous Buffer and Wire Sizing for Performance and Power Optimization", Proc. Int. Symp. On Low Power Electronics and Design, pp. 271-276, 1996

94. Coudert, R. Haddad, and S. Manne, "New Algorithms for Gate Sizing: A Comparative Study", Proc. Design Automation Conference, pp. 734-739, 1996

95. L.A. Entrena, E. Olias, and J. Uceda, "Timing Optimization by Redundancy Addition and Removal", Proc. Physical Design Workshop, pp. 13-20, 1996

96. Y.M. Jiang, A. Kristic, K.T. Cheng, and M. Marek-Sadowska, "Post-Layout Logic Restructuring for performance Optimization", Proc. Design Automation Conference, pp. 662-665, 1997

97. Марченко M.A. "Метод оптимизации легального размещения СБИС по длине цепей и равномерности загрузки кристалла", Труды Конференции «Интеллектуальные системы и Интеллектуальные САПР», с.75-76, 2003

98. Марченко М.А. "Модель графа перестановок для оптимизации размещения элементов СБИС", Материалы 8 Международного семинара «Дискретная математика и ее приложения», с.285-288, 2004

99. В. М. Щемеленин "Автоматизация топологического проектирования БИС" Москва 2001

100. Xiaojian Yang, Bo-Kyung Choi, Majid Sarrafzadeh "Routability Driven Space Allocation for Fixed-Die Standard-Cell Placement", ISPD 2002.

101. Quinn, Breuer "A forced directed component placement procedure for printed circuit boards", Transactions on Circuits and Systems 1979102. www ggtcorp com103. www.boost.org

102. Naveed Sherwani "Algorithms for VLSI physical design automation."

103. Thomas Lengauer "Combinatorial Algorithms for Integrated Circuit Layout."106. Орэ "Теория графов".

104. Ф. Харари, Э. Палмер "Перечисление графов".

105. Andrew В. Kahng, Gabriel Robins "On optimal interconnection for VLSI" Kluwer 1995.

106. M.A. Марченко «Метод построения деревьев Штейнера, основанный на знаниях» Труды Международных научно-технических конференций «Интеллектуальные системы (IEEE AIS'02)» и «Интеллектуальные САПР CAD-2002», 2002

107. М.А. Марченко «Алгоритм ЕСО размещения с оптимизацией методом перестановок и вставок» IEEE AIS'04 CAD-2004 с.62-65, Физматлит 2004

108. Утверждаю» Генершщыйдиректор ЗАО «Гамбит»

109. Т.А.Илуридзе 04 июля 2005 г.1. Акт о внедрении

110. Внедрены в эксплуатацию в ЗАО «Гамбит» в 2002 2004 годах.123298, Москва, 3-я Хорошевская ул, 11

111. Third Khoroshevskaya St, Moscow 123298, Russia

112. Tel [phone] Fax [phone] E-mail info@gambit com ru1. УТВЕРЖДАЮ

113. Заведующий Сектором автоматизации логического проектирования ИППМ РАН, д.т.н.1. A.JI. Глебов