автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Проектирование топологии СБИС методом иерархической декомпозиции в среде распределенных вычислений

Введение.

1. Обзор и анализ методов повышения производительности САПР.

1.1. Темпы роста размерности задач проектирования СБИС.

1.2. Аппаратные ускорители решения задач проектирования.

1.3. Параллельные вычисления как метод повьппения производительности.

1.4. Системы распределенных вычислений.

1.5. Проблемы выбора конфигурации кластерной системы.

Выводы.

2. Проектирование параллельных алгоритмов.

2.1. Декомпозиция задач.

2.2. Организация взаимодействия задач.

2.3. Укрупнение зернистости задач.

2.4. Отображение множества задач на множество процессоров.

2.5. Иерархическая декомпозиция как унифицированный метод организации параллельного процесса решения.

Выводы.

3. Параллельное решение задачи глобальной трассировки СБИС.

3.1. Линейчатые топологии.

3.2. Существующие алгоритмы глобальной трассировки.

3.3. Модель глобальной трассировки.

3.4. Стратегии максимального и минимального определения границ.

3.5. Параллельный алгоритм и его вычислительная сложность.

3.6. Программная реализация и результаты тестирования.

Выводы.

4. Совместное решение задач размещения и глобальной трассировки.

4.1. Существующие алгоритмы размещения ячеек и глобальной трассировки.

4.2. Параллельный алгоритм размещения и глобальной трассировки.

4.3. Параллелизм и вьршслительная сложность алгоритма.

4.4. Программная реализация и результаты тестирования.

Выводы.

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

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

В настоящее время все большее распространение получает такой вид параллельной обработки, как системы распределенных вычислений (кластеры), которые характеризуются доступностью, высокой масштабируемостью, одним из лучших соотношений ценаЛпроизводительность и представляют собой совокупность стандартных процессорных блоков (например, ПК), объединенных средой передачи данных (например, локальная сеть).

Организация параллельных вычислительных процессов в распределенных вычислительных средах, связанных с проблемно-ориентированной обработкой данных (в частности при автоматизированном проектировании изделий микроэлектронной техники), требует создания специальных методов и программных средств распараллеливания обработки проектной информации. Данная необходимость продиктована:

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

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

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

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

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

Цель работы и задачи исследования

Цель работы заключается в разработке эффективного метода организации параллельного вычислительного процесса в СРВ путем декомпозиции исходной задачи на автономно решаемые подзадачи на примере проектирования топологии СБИС.

Для достижения указанной цели были поставлены и решены следуюш,ие задачи:

- анализ суш;ествуюш;их методов повышения производительности САПР с целью обоснования перспективности выбранного направления исследований;

- разработка эффективного метода построения параллельных алгоритмов, функционирующих в СРВ для задач автоматизированного проектирования топологии СБИС;

- разработка иерархического метода декомпозиции для задач синтеза топологии СБИС и его интеграция с выработанным подходом к организации параллельного вычислительного процесса;

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

- создание программного обеспечения прототипа САПР СБИС на основе выработанных концепций организации параллельной обработки для задач проектирования топологии СБИС в СРВ.

Основные методы исследования

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

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

- унифицированный метод организации параллельного вычислительного процесса в СРВ на основе иерархической декомпозиции объекта проектирования, применительно к решению задач проектирования топологии СБИС;

- параллельный алгоритм глобальной трассировки топологии СБИС на основе иерархической декомпозиции, функционирующий в СРВ, и отличающийся высокими показателями масштабируемости (эффективности процесса решения для задач различной размерности), сокращения времени счета и постоянством качества решения при изменении числа процессоров СРВ;

- параллельный алгоритм совместного решения задач глобальной трассировки и размещения ячеек СБИС, использующий в качестве базового метод иерархической декомпозиции, предназначенный для функционирования в СРВ, и отличающийся высокими показателями масштабируемости, сокращения времени счета и постоянным качеством решения при различном числе процессоров СРВ;

- набор критериев выбора аппаратных компонентов и архитектуры СРВ для достижения необходимых технико-экономических характеристик вычислительной системы.

Практическая значимость. Разработанные компоненты математического, программного, лингвистического и информационного обеспечения интегрированы в прототип САПР СБИС, функционирующей в СРВ. Программно реализованы параллельные алгоритмы глобальной трассировки и совместного решения задач глобальной трассировки и размещения ячеек СБИС.

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

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

Апробацияработы. Основные положения и результаты диссертационной работы докладывались и обсуждались на Всероссийском совещании-семинаре «Высокие технологии в региональной информатике» (г. Воронеж, 1998 г.). Международной научно-технической конференции «Актуальные проблемы анализа и обеспечения надежности и качества приборов, устройств и систем» (г. Пенза, 1998 г.). Шестом Международном семинаре «Распределенная обработка информации (РОИ-98)» (г. Новосибирск, 1998 г.), II межрегиональной научно - методической конференции «Новые информационные технологии обучения в региональной инфраструктуре» (г. Пенза, 1999 г.), XIV Международной научно-технической конференции «Интеллектуальные САПР-99» (г. Геленджик, 1999 г.). Международной научно-технической конференции «Информационные технологии и системы в образовании, науке, бизнесе» (г. Пенза, 1999 г.). Шестой всероссийской Межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика '99» (г. Москва, 1999 г.). Международной научно-методической конференции «Телемати-ка-2000» (г. Санкт-Петербург, 2000 г.), Международной конференции «Информационные системы и технологии (ИСТ-2000)» (г. Новосибирск, 2000 г.), всероссийской конференции «Теоретические и прикладные вопросы современных информационных технологий» (г. Улан-Удэ, 2000 г.).

Публикации. По теме диссертационной работы опубликовано 12 печатных работ.

Структура и объем работы. Диссертация состоит из введения, четырех глав с выводами, заключения и списка литературы, включающего 137 наименований. Работа изложена на 166 страницах машинописного текста, содержит 59 рисунков и 14 таблиц.

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

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

2. Предложено в качестве способа повышения производительности САПР СБИС использовать среду распределенных вычислений, позволяющую ускорять решение задач проектирования за счет их параллельной обработки.

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

4. Предложен метод иерархической декомпозиции не только как средство снижения размерности задачи, но и как средство распараллеливания процесса ее решения.

5. Предложен параллельный алгоритм глобальной трассировки топологии СБИС, использующий метод иерархической декомпозиции, и позволяющий ускорить процесс решения данной задачи приблизительно в 0,6хР раз (Р -число процессоров распределенной среды).

6. Предложен параллельный алгоритм совместного решения задач глобальной трассировки и размещения ячеек СБИС на основе метода иерархической декомпозиции, имеющий высокие показатели качества решения и снижения времени счета.

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

-1668. Предложены критерии выбора аппаратных компонентов и архитектуры среды распределенных вычислений по определенному набору параметров. 9. На основе предложенных методов и алгоритмов разработаны и реализованы подсистемы глобальной трассировки соединений и размещения ячеек СБИС, функционирующие в среде распределенных вычислений.

Заключение

1. Информационный сайт поддержки разработчиков систем на основе продукции фирмы Intel®, http://developer.intel.com/

2. Flynn М. Some Computer Organizations and Their Effectiveness // IEEE Trans. Computers. 1966. V.21. N 9. P.948-960

3. Higbie L. C. Supercomputer architecture // Computer. 1973. V.6. N 12. P.48-56.

4. Handler W. On classification schemes for computer systems in the post Von Neumann era // Lecture Notes in Computer Science. 1975.

5. Thurber K. J. Large Scale Computer Architecture / Hayden Book Company, Rochelle Park, New Jersey, 1976.

6. Skiilicom D. A Taxonomy for Computer Architectures // Computer. 1988. V.21. Nll.P.46-57.

7. Dasgupta S. A Hierarchical Taxonomic System for Computer // 1990. V.23. N 3. P.64-74.

8. Feng T. Some Characteristics of Assotiative Parallel Processing // Proc. 1972 Sagamore Computing Conf. 1972. P.5-16.

9. Shore J.E. Second Thoughts on Parallel Processing // Comput. Elect. Eng. N 1. P.95-109.

10. Хокни P., Джессхоуп К. Параллельные ЭВМ. Архитектура, программирование и алгоритмы. М.: Радио и связь. 1986. 392 С.

11. Носкпеу R. Parallel Computers: Architecture and Performance // Proc. of Int. Conf. Parallel Computing'85. 1986. P.33-69.

12. Hockney R. Classification and Evaluation of Parallel Computer Systems // Lecture Notes in Computer Science. 1987. N 295. P. 13-25.

13. Hwang K., Briggs F. A. Computer Architecture and Parallel Processing. 1984. P.32-40.

14. Snyder L. A Taxonomy of Synchronous Parallel Machines. University Park. Penn. 1988. P.281-289.-16815. Johnson E. E.Completing an MIMD Multiprocessor Taxonomy // Computer Architecture News. 1988. V. 16. N 2. P.44-48.

15. Basu A. Parallel Processing Systems: a Nomenclature based on their Characteristics // Proc. lEEE(UK). N 134. 1987. P.143-147.

16. Krishnamurthy E.V. Parallel Processing Principles and Practice. Addison-Wesley Pub. Company. 1989. P.208-246.

17. Duncan R. A survey of parallel computer architectures // Computer. V.23. N 2. 1990. P.5-16.

18. Бэбб P., Мак-Гроу Дж. и др. Программирование на параллельных вычислительных системах. М.: Мир. 1991. 376 С.

19. Головкин Б.А. Параллельные вычислительные системы. М.: Наука. 1980. 520 С.

20. Высокоскоростные вычисления. Архитектура, производительность, прикладные алгоритмы и программы Супер-ЭВМ /Под ред. Ковалика Я.- М.: Радио и связь. 1988. 432 С.

21. Валях Е. Последовательно-параллельные вычисления. М.: Мир. 1985. 456 С.

22. Супер ЭВМ. Аппаратная и программная организация. /Под ред. Фернбаха С- М.: Радио и связь. 1991. 320 С.

23. N. Wirth. Program development by stepwise refinement. Com. ACM, 14(4):221-227,1971.

24. M. Ben-Ari. Principles of Concurrent and Distributed Programming. Prentice-Hall, 1990.

25. S. Akl. The Design and Analysis of Parallel Algorithms. Prentice-Hall, 1989.

26. Gibbons and W. Rytter. Efficient Parallel Algorithms. Cambridge University Press, 1990.

27. G. Fox et al. Solving Problems on Concurrent Processors. Prentice-Hall, 1988.

28. G. Fox, R. Williams, and P. Messina. Parallel Computing Works! Morgan Kaufman, 1994.

29. V. Kumar and V. Rao. Parallel depth-first search, part II: Analysis. Intl J. of Parallel Programming, 16(6):479-499, 1987.

30. N. Carriero and D. Gelemter. How to Write Parallel Programs. MIT Press, 1990.

31. M, Berger and S. Bokhari. A partitioning strategy for nonuniform problems on multiprocessors. IEEE Trans. Computs., C-36(5):570-580, 1987.

32. H. Simon. Partitioning of imstructured problems for parallel processing. Computing Systems in Engineering, 2(2/3):135-148, 1991,

33. C. L. Seitz. Multicomputers. In C,A,R, Hoare, editor. Developments in Concurrency and Communication, Addison-Wesley, 1991.

34. R. Williams. Performance of dynamic load balancing algorithms for unstructured mesh calculations. Concurrency: Practice and Experience, 3(5):457-481, 1991.

35. S. Barnard and H. Simon. Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurrency: Practice and Experience, 6(2):101-117, 1994.

36. S. Bokhari. On the mapping problem. IEEE Trans. Computs,, C-30(3):207-214, 1981,

37. F, C, H, Lin and R, M. Keller. The gradient model load balancing method. IEEE Trans. Software Eng., SE-13(l):32-38, 1987.

38. Tantawi and D. Towsley. Optimal load balancing in distributed computer systems. J. ACM, 32(2):445-465, 1985.

39. G. Cybenko. Dynamic load balancing for distributed memory multiprocessors. J. Parallel and Distributed Computing, 7:279-301,1989.

40. K. W. Lee and C. Sechen. A new global router for row-based layout. // Proc. Int. Conf Computer-Aided Design, pp. 180-183, Nov. 1988.

41. J. Cong and B. Preas. A new algorithm for standard cell global routing. // Proc. Int. Conf Computer-Aided Design, pp. 176-179, Nov. 1988.

42. G. Meixner and U. Lauther. A new global router based on a flow model and linear assignment. // Proc. Int. Conf Computer-Aided Design, pp. 44-47, Nov. 1990.

43. R. Nair, A simple yet effective technique for global wiring. // IEEE Trans. Computer-Aided Design, vol. CAD-6, no. 2, pp. 165-172, Mar. 1987.

44. D. Hechtman and J. J. Lewandowski, A flux directed approach to a wire routing problem. // IEEE VLSI Tech. Bull., vol. 4, no. 3/4, pp. 124-138, Sept./Dec. 1989.

45. M. Burstein and R. Pelavin, Hierarchical wire routing. // IEEE Trans. Computer-Aided Design, vol. CAD-2, no. 4, pp. 223-234, Oct. 1983.

46. M. Marek-Sadowska, Global router for gate array. // Proc. Int. Conf Computer Design, pp. 332-337, Oct. 1984.

47. W. K. Luk, D. T. Tang, and C. K. Wong, Hierarchical global wiring for custom chip design. // Proc. 23rd Design Automat. Conf, pp. 481-489, June 1986.

48. B. M. Курейчик. Генетические алгоритмы. / Монография, ТРТУ, Таганрог, 1998 г. 241 с.

49. Б. К. Лебедев. Глобальная трассировка на основе генетической эволюции. // Перспективные информационные технологии и интеллектуальные системы. №5, С. 77-91, ТРТУ, Таганрог, 2000 г.

50. О. Б. Лебедев. Генетический алгоритм глобальной трассировки. // Перспективные информационные технологии и интеллектуальные системы. №2, С. 66-76, ТРТУ, Таганрог, 2000 г.

51. R. Nair, S. J. Hong, S. Liles, and R. Villani, Global wiring on a wire routing machine. // Proc. 19th Design Automat. Conf, pp. 224-231, June 1982.

52. Y. Won and S. Sahni, Maze routing on a hypercube multiprocessor computer. // Proc. Int. Conf Parallel Process., pp. 630-637, Aug. 1987.

53. Jonathan Rose, LocusRoute: A parallel global router for standard cells. // Proc. 25th Design Automat. Conf, pp. 189-195, June 1988.-17159. P. С. Гарфинкель, Г. Л. Немхаузер, Целочисленное программирование. М: Мир, 1982, pp. 154-165.

54. Автоматизация проектирования БИС. В 6 кн.: Практ. пособие. Кн. 6. Г. Г. Казеннов, Е. В. Сердобинцев. Проектирование топологии матричных БИС/Под ред. Г. Г. Казеннова. М.: Высшая школа, 1990.

55. Бершадский А. М. Применение графов и гиперграфов для автоматизации РЭА и ЭВА. Саратов: Изд-во Саратов, ун-та, 1983. - 120 с.

56. М. А. Breuer, Min-cut placement. // J. Design Automat. Fault Tol. Сотр., vol. 1, pp. 343-382, Oct. 1977.

57. M. Hanan and J. M. Kurtzberg, Placement techniques. // in Design Automation of Digital Systems: Theory and Techniques. M. A. Breuer, Ed., Prentice-Hall, 1972, pp. 213-282.

58. Sechen, VLSI Placement and Global Routing using Simulated Annealing. Boston: Kluwer Academic Publishers, 1988.

59. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by simulated annealing. // Science, vol. 220, pp. 671-680, May 1983.

60. R. M. Kling and P. Banerjee, ESP: Placement by simulated evolution. // IEEE Trans. Computer-Aided Design, vol. CAD- 8, no. 2, pp. 245-256, Mar. 1989.

61. R. M. Kling, Optimization by simulated evolution and its application to cell placement. //Tech. Rep. no. CRHC-90-7, Coordinated Science Laboratory, Univ. of Illinois, Urbana, IL, Aug. 1990.

62. P. Banerjee, M. H. Jones, and J. S. Sargent, Parallel simulated annealing algorithms for standard cell placement on hypercube multiprocessors. // IEEE Trans. Parallel and Dist. Syst, vol. 1, no. 1, pp. 91-106, Jan. 1990.

63. J. Sargent and P. Banerjee, A parallel row-based algorithm for standard cell placement with integrated error control. // Proc. 26th Design Automat. Conf, pp. 590-593, June 1989.

64. P. Ravikumar and S. Sastry, Parallel placement on hypercube architecture. // Proc. Int. Conf Parallel Process., Vol. Ill, pp. 97-101, 1989.

65. Hill. Casotto, F. Romeo, and A. Sangiovanni-Vincentelli, A parallel simulated annealing algorithm for the placement of macro-cells. // Proc. Int. Conf. Computer-Aided Design, pp. 30-33, Nov. 1986.

66. S. A. Kravitz and R. A. Rutenbar, Placement by simulated annealing on a multiprocessor. // IEEE Trans. Computer-Aided Design, vol. CAD-6, no 4, pp. 534549, June 1981.

67. Casotto and A. Sangiovanni-Vincentelli, Placement of standard cells using simulated annealing on the Connection Machine. // Proc. Int. Conf. Computer- Aided Design, pp. 350-353, 1981.

68. C. P. Wong and R. D. Fiebrich. Simulated annealing-based circuit placement algorithm on The Connection Machine System. // Proc. Int. Conf. Computer Design, pp. 18-82, 1981.

69. J. S. Rose, D. R. Blythe, W. M. Snelgrove, and Z. G. Vranesic. Fast, high quality VLSI placement on a MIMD multiprocessor. // Proc, Int. Conf. Computer-Aided Design, pp. 42-45, Nov. 1986.

70. K. Ueda, T. Komatsubara, and T. Hosaka. A parallel processing approach for logic module placement. // IEEE Trans. Computer-Aided Design, vol. CAD-2, no.l,pp. 39-41, Jan. 1983.

71. R. M. Kling and P. Baneijee. Concurrent ESP: A placement algorithm for execution on distributed processors, // Proc, Int, Conf, Computer-Aided Design, pp. 354-351, 1981.

72. A. Szepieniec, Integrated placement/routing in sliced layouts. // Proc. Design Automat. Conf., pp. 300-301, 1986.

73. Shragowitz, J. Lee, and S, Sahni, Placer-router for sea-of-gates design style. // Proc. Int. Conf. Computer Design, pp. 330-335, 1981.

74. P. R. Suaris and G. Kedem, A quadrisection-based combined place and route scheme for standard cells. // IEEE Trans. Computer-Aided Design, vol. 8, no. 3, pp. 234-244, Mar. 1989.

75. R. J. Brouwer, PARAGRAPH: (PARallel Algorithm for Global Routing and Placement Hierarchically). // Proc. 27th Design Automat. Conf, pp. 653-658, June 1990.

76. P. R. Suaris and G. Kedem, An algorithm for quadrisection and its application to standard cell placement. // IEEE Trans. Circuits Syst., vol. 35, no. 3, pp. 294-303, Mar. 1988.

77. M. Fiduccia and R. M. Mattheyses, A linear-time heuristic for improving network partitions.//Proc. 19th Design Automat. Conf, pp. 175-181, 1982.

78. Бодрягин В. И., Зайцева Ж. Н., Мазанько Н, С, Автонастройка монтажного поля базового кристалла матричной БИС в системе автоматизированного проектирования//Вопросы радиоэлектроники. Сер. ЭВТ. Вып. 10,1982, С. 37-42.

79. Зайцева Ж. Н., Бодрягин В. И., Фомин К. Г. Нисходягцая технология проектирования адаптируемой САПР на базе типовых алгоритмических решений // Вопросы радиоэлектроники. Сер. ЭВТ. 1981, Вып. 6, С. 3.

80. Зайцева Ж. Н., Алферова М. Ф. Метод параллельной трассировки на платах любого конструкторского уровня // Вопросы радиоэлектроники. 1979, Вып. 6, С. 51-57.

81. Бершадский А. М., Курилов Л. С, Селиверстов М. Н. Балансировка нагрузки в кластерных системах. // Телематика-2000 Международная научно-методическая конференция. 29 мая -1 июня 2000 г., г. Санкт-Петербург, С. 124-125.

82. Селиверстов М.Н. Распределенный алгоритм генерации топологии СБИС. // Международная научно-техническая конференция "Интеллектуальные САПР". Таганрог: ТРТУ, 2000 - №2, С. 362 - 363.

83. Бершадский А. М., Курилов Л. С, Селиверстов М. Н. "Применение кластерных технологий в САПР" "Информационные технологии", 2001, №9. -С. 2-6.

84. Автоматизация проектирования больших и сверхбольших интегральных схем/А. И. Петренко, В. М. Курейчик, А. Я. Тетельбаум и др. // Зарубежная радиоэлектроника. 1981, № 6. С. 47-66.

85. Баталов Б. В., Норенков И. П. Система автоматизированного проектирования сверхБИС // Микроэлектроника. 1980, № 9. С. 401-412.

86. Автоматизация проектирования вычислительных структур / А. В. Каляев, А. Н. Мелихов, В. М. Курейчик, В. Ф. Гузик, В. А. Калашников. — Ростов н/Д: Изд-во Ростовского ун-та, 1983. 224 с.

87. Батищев Д. И. Поисковые методы оптимального проектирования. М.: Сов. радио, 1975.-216 с.

88. Морозов К. К., Одиноков В. Г., Курейчик В. М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры. М.: Радио и связь, 1983.-280 с.

89. Норенков И. П. Введение в автоматизированное проектирование технических устройств и систем. М.: Высшая школа, 1980. - 309 с.

90. Yoshizawa К. Automatic Layout Algorithms for Master Slice LSI // Proc. ISCAS. 1979. - P. 470-473.

91. Goto S. An Automatic Layout Design System for Master Slice LSI Chip // Proc. ISCAS. 1982. - P. 631-635.

92. Базилевич P. П. Алгоритмические методы гибкой трассировки межсоединений. Киев: Институт Кибернетики АН УССР, 1979. - 52 с.

93. Хонг С. Ю., Наир Р. Трассировочные машины новый инструмент для физического проектирования СБИС // ТИИЭР. - 1983, Т. 71, № 1. - С. 70-80.

94. Nair R. Global Wiring on a Wire Routing Machine // Proc. 19th DAC. 1982, P. 224-231.

95. Breuer M., Shamsa K. A Hardware Router // J. Digital Systems. 1981, Vol. 4, N4.-P. 393-408.

96. Тетельбаум A. Я. Иерархический подход к проектированию сверхбольших интегральных схем // Электронная техника. Сер. 10, Микроэлектронные устройства. 1981, Вып. 6(30). С. 29-32.

97. Базилевич Р. П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств. Львов: Вища школа, 1981.- 168 с.

98. Ниссен К. Методология и средства иерархического проектирования СБИС // ТИИЭР, 1983, Т. 72, № 1. С. 81-94.

99. Батищев Д. И. Задачи и методы векторной оптимизации. Горький: Изд-во Горьк. ун-та, 1979. - 92 с.

100. Батищев Д. И., Львович Я. Е., Фролов В. Н. Оптимизация В САПР. Воронеж, ВГТУ. 1997.

101. Батищев Д. И. Генетические алгоритмы решения экстремальных задач / Под ред. Львовича Я. Е.: Учеб. пособие. Воронеж, 1995.

102. Абрайтис Л. Б. Автоматизация проектирования топологии цифровых интегральных схем. М.: Радио и связь, 1985.

103. Автоматизация проектирования больших интегральных схем. Петренко А. И., Сыпчук П. П., Тетельбаум А. Я., Иванников А. Д., Саватьев В. А. Киев: Вища школа. 1983.

104. Дж. Д. Ульман Вычислительные аспекты СБИС. М.: Радио и связь, 1990

105. Широ Г. Э. Методы трассировки печатных плат и КМОП БИС // Электронная техника. Сер. 10, Микроэлектронные устройства. 1978, Вып. 2(8). -С. 3-11.

106. Уланов А. П. Автоматизация разработки программ контроля матричных БИС // Теоретические и прикладные вопросы разработки и эксплуатации

107. САПР РЭА. (Тезисы докл. Всесоюзной конф.) М.: МАИ, 1986. - С. 101102.

108. Петренко А. И. Основы автоматизации проектирования. Киев: Техника, 1982.-295 с.

109. В. Н. Лошаков, Г. Э. Широ, Л. Б. Осипов, Г. Н. Брусникин. Системы машинного проектирования топологий изделий электронной техники // Электронная техника. Сер. 10. Микроэлектронные устройства. 1977, Вып. 6. -С. 73-81.

110. Лошаков В. Н. Параллельная трассировка соединений проводниками второго порядка // Электронная техника. Сер. 11. Комплексная микроминиатюризация радиоэлектронных устройств и систем. 1975, Вып. 4. - С. 5265.

111. Лошаков В. Н. Алгоритм размещения линеек контактных площадок // Электронная техника. Сер. 11. Комплексная микроминиатюризация радиоэлектронных устройств и систем. 1975, Вып. 4. - С. 67-74.

112. Лошаков В. Н. Метод сокращения операций в алгоритме параллельной трассировки соединений и некоторые оценки // Электронная техника. Сер. 11. Комплексная микроминиатюризация радиоэлектронных устройств и систем. 1976, Вып. 1. С. 51-58.

113. Теория и методы автоматизации проектирования вычислительных систем / Под ред. М. Брейера. М.: Мир, 1977. - С. 221-223.

114. Методы разбиения / К. К. Морозов, А. Н. Мелихов, Л. С. Берштейн и др.; Под ред. К. К. Морозова. М.: Сов. радио, 1978. - 136 с.

115. Юдин Д. Б., Гольдштейн Е. Г. Задачи и методы линейного программирования. -М.: Сов. радио, 1961.

116. Файзулаев Б. П., Павлычев В. А., Драбкин В. А. Оценка средней длины связей в логических цепях ЭВМ // Вопросы радиоэлектроники. Сер. ЭВТ. 1982, Вып. 16.-С. 95-99.

117. Селютин В. А. Автоматизированное проектирование топологии БИС. М.: Радио и связь 1983. - 112 с.

118. Абрайтис Л. Б., Блонскис И. С. Автоматизированный метод синтеза топологии интегральных схем. В кн.: Вычислительная техника. - Каунас, 1979, т. 12, С. 124-128.

119. АхоА., Хопкроф Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536 с.- 179