автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Исследование и разработка задач размещения разнотипных элементов при автоматизированном проектировании узлов ЭВМ

ВВЕДЕНИЕ

Глава I. ОБЗОР ЗАДАЧ И МЕТОДОВ РАЗМЕЩЕНИЯ РАЗНОГАБА

РИТНЫХ ЭЛЕМЕНТОВ

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

1.2. Алгоритмы , использующие методы оптимального раскроя материалов

Методы плотного размещения

Размещение с использованием аналитических и дискретной моделей элементов

1.3. Анализ задачи и известных алгоритмов

Глава 2. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ С УЧЕТОМ ТРЕБОВАНИЙ ТРАССИРОВКИ

2.1. Модели схемы и печатной платы.

2.2. Точная формальная постановка. Алгоритмы преобразования графов, представляющих схемы и платы.'.

2.3. Оптимальное представление ортографа упрошен ной клеточной моделью.

Глава 3. ОПТИМАЛЬНЫЕ ПРЕОБРАЗОВАНИЯ ГИПЕРГРАФА СХЕМЫ В

РЕАЛИЗУЮЩЕМ ОРТОГРАФЕ

3.1. Задача оптимального свертывания гиперграфа , представляющего схему

3.2. Размещение вершин нормализованного гиперграфа в ортографе

3.3. Приближенный алгоритм размещения.

Глава 4. РЕАЛИЗАЦИЯ И ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ

РАЗРАБОТАННЫХ МОДЕЛЕЙ И АЛГОРИТМОВ.

4.1. Организация системы автоматизированного проектирования

4.2. Подсистема программ размещения элементов . 118 4.3. Экспериментальное иссяедрвание разработанных алгоритмов и программ

4.4. Результаты внедрения разработанных моделей и алгоритмов.I.

Поставленные ХХУТ съездом КПСС задачи резкого повышения эффективности и качества труда во всех отраслях народного хозяйства СССР определили основные направления научных исследований и опытно-конструкторских разработок; Одним из важнейших средств решения поставленных задач является повсеместное применение средств вычислительной техники и различной цифровой аппаратуры. В 1981-1985 гг. в СССР производство приборов, средств автоматизации и вычислительной техники значительно увеличится.

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

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

Для сокращения сроков и повышения качества разработок широкое применение нашли системы автоматизированного проектирования (САПР) [1-1<3 . Большое значение приобрели задачи автоматизации проектирования при разработке цифровой аппаратуры для летательных аппаратов, систем управления воздушным движением (УВД) и других аналогичных систем. Эффективность САПР в значительной степени определяется качеством решения взаимосвязанных задач оптимизации, к которым в первую очередь относятся задачи размещения разнотипных элементов на платах ячеек и трассировки печатных соединении*

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

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

Состояние вопроса. В известных работах Е.П; Герасименко, В.И.Кота, И.Я.Ландау, Л.Б.Абрайтиса, И.К.Матицкаса, Д.В.Рубля -ускаса, В.Б.Аргемова, Л.П.Рябова, Л.А.Рычкова, Б.А. Кузьмина, А.А.Эйдеса, Ю.Г.Стояна, Н.И.йшя [13-211 и др. рассматриваются варианты задачи размещения разногабаритных элементов и соответствующие алгоритмы их решения, использующие идеи и методы оптимального раскроя материалов. Общими недостатками этих методов являются слабый учет связности, отсутствие точных постановок задач и невысокое качество размещения при значительной плотности соединений.

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

- разработка соответствующих математических моделей и алгоритмов;

- разработка реализующих эти алгоритмы программ и включение их в САПР;

- экспериментальное исследование моделей и алгоритмов с целью определения их оптимальных параметров и характеристик.

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

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

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

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

- 8ы(?р4н математический аппарат для решения основных оптимизационных задач, решаемых при размещении;

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

- разработаны высокоэффективные приближенные алгоритмы размещения;

- разработаны метод и подсистема экспериментального исследования алгоритмов оптимизации непосредственно в процессе проектирования ячеек. Практическая значимость. Разработанные в диссертации алгоритмы запрограммированы на ЕС ЭШ и в составе подсистемы размещения включены в САПР, используемую для проектирования цифровых и цифро-аналоговых ячеек. Полученное с помощью указанных алгоритмов размещение позволяет автоматически трассировать 95-98$ соедир нений при плотности последних до 2 контактов на I см платы (при шаге проводников 1,25 мм).

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

Реализация в промышленности. САПР, включающая разработанные в диссертации алгоритмы, внедрена на ряде научно-исследовательских и опытно-конструкторских организаций различных ведомств. Внедрение в Московском НИИ Приборостроения, -■ Тбилисском НИИ Систем Автоматизации НПО пЭлва" и предприятиях п/я A-7I56, Р-6380 дало заметный экономический эффект (более 200 тыс. руб.).

Реализация в учебном процессе. Научный результаты диссертации используются в учебном процессе в Львовском ордена Ленина Политехническом институте им. Ленинского комсомола.

Структура и объем работы. Диссертация состоит из введения,

Основные результаты диссертационной работы докладывались:

- на аспирантских семинарах МАИ им. Серго Орджоникидзе;

- на кафедре вычислительной техники МАИ;

- на семинарах кафедры вычислительной техники МИЭМ;

- на республиканском совещании иАвтоматизация конструирования устройств и узлов радиоэлектронной и электронно-вычислительной аппаратуры", г. Каунас, 1980 г.

Разработанные в диссертации алгоритмы использованы в ОКР „Автомат-1", пАврора-5" (МНИИП, г.Москва).

По материалам диссертации автором написано 5 научных трудов, опубликованных во всесоюзных и ведомственных научных журналах и научно-технических сборниках [54-58].

ЗАКЛЮЧЕНИЕ

1. Применение вычислительных машин для проектирования цифровых устройств. Сб. статей под ред. Н.я.Матюхина. «Сов. радио", 1968.

2. Штейн М.Е., Штейн Б.Е. Методы машинного проектирования цифровой аппаратуры. М., «Сов.радио", 1973 г.

3. Кейс П. и др. Автоматизация проектирования вычислительных систем с использованием логических схем на твердом теле.

4. В кн. Кибернетический сборник. Новая серия. Вып. I, М., „Мир", 1965.

5. Ландау И.Я. Применение ЦВМ для проектирования ЦВМ. М., „Энергия", 1974.

6. Юрин О.Н. Единая система автоматизации проектирования ЭВМ. М., „Сов.радио", 1976.

7. Селютин В.А. Машинное конструирование электронных устройств. М. „Сов.радио", 1977.

8. Абрайтис Л.Б., Шейнаускас Р.И., Жилевичус В.А. Автоматизация проектирования ЭВМ. М., „Сов.радио", 1978.

9. Петренко А.Й., Тетельбаум А.Я. Формальное конструирование электронно-вычислительной аппаратуры. М., „Сов.радио", 1979.

10. Теория и методы автоматизации проектирования вычислительных систем, сб. под ред. Брейера М., пер. с англ., изд. «Мир", М., 1977.

11. Автоматизация проектирования вычислительных систем: Языки моделирования и базы данных. Сб. статей под ред. Брейера М., пер. с англ., изд. „Мир", М., 1979.

12. Штейн М.Е. Об ортогональных графах и оптимальных соединениях схем. Изв.АН СССР,„Техническая кибернетика",$ 2,1970г.

13. Томашевский Д.И., Масютин Г.Г., Явич A.A., Пресну -хин В.В. Грдфические средства автоматизации проектирования РЭА. М., „Сов.радио", 1980.

14. Герасименко Е.П., Кот В.И. Размещение модулей произвольной геометрической формы на платах с печатным монтажом. „Труды НИИ УаГ, 1970, № 2.

15. Гёрасименко ЕЛ., Кот В.И., Ландау И.Я.,Сомкин В.М. Автоматизация проектирования печатных блоков с модулями произвольной формы". М., „Машиностроение", 1979.

16. Матицкас Й.К., Рубляускас Д.В. Итерационный алгоритм размещения разногабаритных элементов. В кн. Выч. техника, т.5 Каунас, 1974.

17. Артемов В.Б., Рябов Л.П. Алгоритм размещения модулей различных габаритов на печатной плате, ж. „Обмен опытом в радиопромышленности", 1977, JB 2.

18. Кузьмин Б.А. Универсальность САПР. Проблемы и решения, ж. „Приборы и системы управления", 1979, № I.

19. Рычков Л.А., Кузьмин Б.А., Эйдес A.A. Алгоритм размещения радиоэлементов разной формы. Ж. „Приборы и системы управления", 1979, № 2.

20. Матицкас И.К. Алгоритм размещения разногабаритных элементов в кратные позиции. К. „УС и М", 1979,. № 4, стр. 120-123.

21. Стоян Ю.Г. Размещение геометрических объектов. „Науко-ва думка", Киев, 1975.

22. Гиль Н.И. и др. Оптимизация тепловых режимов элементов РЭА посредством их рационального размещения. Материалы • конференции: „Автоматизир. техн. проектирование цифровых устройств" (июнь 1976 г.), т.8, Выч. техн., Каунас, 1976, стр. 69-72.

23. Petrik S.K. A Direct Detörmination of the Redundant Forms of a Boolean Funktion from the Set of Prim Implikants, AFCRC-TR-56-110 Air Force Cambridge Research Center, Cambridge, Massachusets, April 195&*

24. Штейн M.E., Медведев A.C. К задаче размещения компонент. УСиМ, 1974, В 2, стр. 77-80.

25. Штейн М.Е. Об оптимальном размещении компонент. -„Изв. АН СССР. Техническая кибернетика", 1971, й 4, стр.133-141.

26. Абрайтис Л.Б., Шейнаускас Р.И., Жилевичус В.А. Система автоматизации проектирования радиоэлектронной и вычислительной аппаратуры „Каунас-2", -„Управляющие системы и машины", № 2, 1979, стр. 95-98.

27. Глушков В.М. и др. Об автоматизации проектирования вычислительных машин. „Кибернетика", 1967, № 5, стр.2-14.

28. Майоров С.А. Алгоритмические методы проектирования цифровых систем. Изв. ВУЗов СССР, „Приборостроение", 1980, т. ХП, J6 3, стр. 89-96.

29. Гурвжч Е.И., Матюхин Н.Е. „Автоматизированная система проектирования цифровых автоматов АСП-1", „Обмен опытом в радиопромышленности", 1972, J? 4, стр. 4-8.

30. Мелихов А.Н., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств. М., „Наука", 1974.

31. Бабаян Б.А., 1^щин O.K. и др. Общие принципы организации проектирования в КАСПИ-М., ИТМ и ВТ АН СССР, 1975.

32. Песков М.И. Опыт разработки и внедрения системы автоматизации проектирования. „Обмен опытом в радиопромышленности", 197I, № 7, стр. 20-23.

33. Орловский Г.В. и др. Архитектура системы автоматизированного проектирования РЭА. „Обмен опытом в радиопромышленности", 1975, JS 6, стр. 11-14.

34. Морозов К.К., Одиноков В.Г. Использование ЭЦШ при конструировании некоторых узлов РЭА. М., «Сов.радио", 1972.35. %рапетян дл. Автоматизация оптимального конструирования ЭВМ. М.,».Сов. радио", 1973.

35. Петросян А.В. Теоретико-алгоритмические задачи и применение. «Вопросы проектирования и моделирования сложных систем", ИК АН УССР, Киев, 1975, стр. 3-23.

36. Berge С., Graphes el hypergrafes, Paris, Dunod, 1970.

37. Крыкановский Ю.М. Компоновка конструкторских элементов цифровых устройств. В кн. «Применение ВМ для проектирования ЦУ, под ред. Н.Я.Матюхина, М., «Сов.Радио", 1968, стр. 153-164.

38. Базилевич Р.П., Ткаченко С.П. Решение задачи разбиения методом параллельного свертывания. В кн. «Вычислительная техника", т.УП, КПИ, Каунас, 1975, стр. 295-298.

39. Крапчин А.И., Покровский Д.Н., Малышков Е.Н. Компоновка и размещение модулей при автоматизированном проектировании радиоэлектронной аппаратуры. «Автоматика и вычислительная техника", 1969, № 5, стр. 7-II.

40. Помазанов В.М. К задаче о размещении ячеек в панели.- В кн. «Применение Ш для проектирования ЦУ", под ред. Н.Я.Матюхина, М., «Сов.радио", 1968.42. shafer О.В. Seducing wiring lengths.- „Elekfcrotechnolodgy",

41. Oct. 1962, v.70, N 4, p. 92-9543. Garside R.G., Nichoison B.S. Permutation procedure for the backboard wiring problem.- „Proc. IEEE", 1968, v. 115,n1,p.27.

42. Loberman H., Weinberger A. Formal procedures fop connecting terminals with a minimum total wire length.- ltJ. of the association for computing ,achinery", Oct. 1957» v.14, Ш 4.

43. Houghton I. A system for the placement of circuit modules. • „Internat, conf. comput. aided design". Sauthampton,1969, London, IEEE, 1969, p. 82-88.1.wler E.L. The quadratic assignment problem. „Management science", 196$, v.9, N 4, p. 586-599.

44. Gilmore P.C. Optimal and suboptimal algorithms forthe quadratic assignment problem.- J. Soc.Indastr. Appl. Math", 1962, TS 2, 10.

45. Mamelak J.S. The placement of computer logic modules.-„J.ASsoc. Oomput. Machinery", 1966, 15, IT 4, p.615-629.

46. Бабаян Б.А., Пронин Ю.А. Размещение компонентов связной системы методом ветвей и границ. ИТМ и ВТ АН СССР, М., 1971.

47. Розанов В.А., Юрин 0.ÏÏ. Метод размещения элементов с нефиксированными связями. »»Труды МИЭМ", ч. I, 1971, вып. 16, стр. 114-139.

48. Селютин В.А.,УлыбинБ.Н. О приближенных методах решения задачи размещения. В кн. »» Вычислительная техника",т.I, КПИ, Каунас, 1970, стр. 269-274.

49. Гинзбург Б.Д. Алгоритм размещения модулей на плате.- «Обмен опытом в радиопромышленности", 1972, вып.4, стр.31-33.

50. Мелихов А.Н., Берштейн Л.С., Семенкин В.В. Решение задачи размещения элементов схем с помощью гиперграфов. »»Методы расчета и автоматизации проектирования устройств микроэлектронных ЦВМ", Ж АН УССР, Киев, стр.38-53, 1973.

51. Кобзева Т.В. О задаче размещения разногабаритных элементов цифро-аналоговых и аналоговых радиоэлектронных узлов «Сборник трудов под редакцией Матова В.И. „Авиационные вычислительные управляющие системы", издательство МАИ, 1981.

52. Кобзева Т.В. К задаче размещения разногабаритных элементов, УСиМ, & I, 1982.

53. Кобзева Т.В. К задаче оптимального разбиения платы при размещении разногабаритных компонентов »» Вопросы радиоэлектроники", серия электронная вычислительная техника,вып.6, 1981.

54. Кобзева Т.В. Об одной задаче оптимизации при размещении разнотипных:компонентов, »»Известия АН СССР. Техническая кибернетика", №.б, 1981.

55. Кобзева Т.В. Об оптимизационных задачах на специальных графах в алгоритмах размещения компонентов ЭЕМ, »»Вопросы радиоэлектроники", серия „Общие вопросы радиоэлектроники", 1983 '-вып. 5,