Помощь в написании студенческих работ
Антистрессовый сервис

Исследование и разработка задач размещения разнотипных элементов при автоматизированном проектировании узлов ЭВМ

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

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

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

Содержание

  • Глава 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 г.

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

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

ЗАКЛЮЧЕНИЕ

.

Показать весь текст

Список литературы

  1. Применение вычислительных машин для проектирования цифровых устройств. Сб. статей под ред. Н.я.Матюхина. «Сов. радио», 1968.
  2. М.Е., Штейн Б. Е. Методы машинного проектирования цифровой аппаратуры. М., «Сов.радио», 1973 г.
  3. П. и др. Автоматизация проектирования вычислительных систем с использованием логических схем на твердом теле.
  4. В кн. Кибернетический сборник. Новая серия. Вып. I, М., &bdquo-Мир", 1965.
  5. И.Я. Применение ЦВМ для проектирования ЦВМ. М., &bdquo-Энергия", 1974.
  6. О.Н. Единая система автоматизации проектирования ЭВМ. М., «Сов.радио», 1976.
  7. В.А. Машинное конструирование электронных устройств. М. «Сов.радио», 1977.
  8. Л.Б., Шейнаускас Р. И., Жилевичус В. А. Автоматизация проектирования ЭВМ. М., «Сов.радио», 1978.
  9. А.Й., Тетельбаум А. Я. Формальное конструирование электронно-вычислительной аппаратуры. М., «Сов.радио», 1979.
  10. Теория и методы автоматизации проектирования вычислительных систем, сб. под ред. Брейера М., пер. с англ., изд. «Мир», М., 1977.
  11. Автоматизация проектирования вычислительных систем: Языки моделирования и базы данных. Сб. статей под ред. Брейера М., пер. с англ., изд. &bdquo-Мир", М., 1979.
  12. М.Е. Об ортогональных графах и оптимальных соединениях схем. Изв. АН СССР,"Техническая кибернетика",$ 2,1970 г.
  13. Д.И., Масютин Г. Г., Явич A.A., Пресну -хин В.В. Грдфические средства автоматизации проектирования РЭА. М., «Сов.радио», 1980.
  14. Е.П., Кот В.И. Размещение модулей произвольной геометрической формы на платах с печатным монтажом. &bdquo-Труды НИИ УаГ, 1970, № 2.
  15. ЕЛ., Кот В.И., Ландау И. Я., Сомкин В. М. Автоматизация проектирования печатных блоков с модулями произвольной формы". М., &bdquo-Машиностроение", 1979.
  16. Й.К., Рубляускас Д. В. Итерационный алгоритм размещения разногабаритных элементов. В кн. Выч. техника, т.5 Каунас, 1974.
  17. В.Б., Рябов Л. П. Алгоритм размещения модулей различных габаритов на печатной плате, ж. &bdquo-Обмен опытом в радиопромышленности", 1977, JB 2.
  18. .А. Универсальность САПР. Проблемы и решения, ж. &bdquo-Приборы и системы управления", 1979, № I.
  19. Л.А., Кузьмин Б. А., Эйдес A.A. Алгоритм размещения радиоэлементов разной формы. Ж. &bdquo-Приборы и системы управления", 1979, № 2.
  20. И.К. Алгоритм размещения разногабаритных элементов в кратные позиции. К. &bdquo-УС и М", 1979,. № 4, стр. 120−123.
  21. Ю.Г. Размещение геометрических объектов. «Науко-ва думка», Киев, 1975.
  22. Н.И. и др. Оптимизация тепловых режимов элементов РЭА посредством их рационального размещения. Материалы • конференции: &bdquo-Автоматизир. техн. проектирование цифровых устройств" (июнь 1976 г.), т.8, Выч. техн., Каунас, 1976, стр. 69−72.
  23. Petrik S.K. A Direct Detormination 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. М.Е. Об оптимальном размещении компонент. -&bdquo-Изв. АН СССР. Техническая кибернетика", 1971, й 4, стр.133−141.
  26. Л.Б., Шейнаускас Р. И., Жилевичус В. А. Система автоматизации проектирования радиоэлектронной и вычислительной аппаратуры &bdquo-Каунас-2″, -&bdquo-Управляющие системы и машины", № 2, 1979, стр. 95−98.
  27. В.М. и др. Об автоматизации проектирования вычислительных машин. &bdquo-Кибернетика", 1967, № 5, стр.2−14.
  28. С.А. Алгоритмические методы проектирования цифровых систем. Изв. ВУЗов СССР, &bdquo-Приборостроение", 1980, т. ХП, J6 3, стр. 89−96.
  29. Е.И., Матюхин Н. Е. &bdquo-Автоматизированная система проектирования цифровых автоматов АСП-1″, &bdquo-Обмен опытом в радиопромышленности", 1972, J? 4, стр. 4−8.
  30. А.Н., Берштейн Л. С., Курейчик В. М. Применение графов для проектирования дискретных устройств. М., &bdquo-Наука", 1974.
  31. .А., 1^щин O.K. и др. Общие принципы организации проектирования в КАСПИ-М., ИТМ и ВТ АН СССР, 1975.
  32. М.И. Опыт разработки и внедрения системы автоматизации проектирования. &bdquo-Обмен опытом в радиопромышленности", 197I, № 7, стр. 20−23.
  33. Г. В. и др. Архитектура системы автоматизированного проектирования РЭА. &bdquo-Обмен опытом в радиопромышленности", 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.II. Метод размещения элементов с нефиксированными связями. «„Труды МИЭМ“, ч. I, 1971, вып. 16, стр. 114−139.
  48. Селютин В.А., УлыбинБ.Н. О приближенных методах решения задачи размещения. В кн. „“ Вычислительная техника», т. I, КПИ, Каунас, 1970, стр. 269−274.
  49. .Д. Алгоритм размещения модулей на плате.- «Обмен опытом в радиопромышленности», 1972, вып.4, стр.31−33.
  50. А.Н., Берштейн Л. С., Семенкин В. В. Решение задачи размещения элементов схем с помощью гиперграфов. «„Методы расчета и автоматизации проектирования устройств микроэлектронных ЦВМ“, Ж АН УССР, Киев, стр.38−53, 1973.
  51. Т.В. О задаче размещения разногабаритных элементов цифро-аналоговых и аналоговых радиоэлектронных узлов „Сборник трудов под редакцией Матова В.И. &bdquo-Авиационные вычислительные управляющие системы“, издательство МАИ, 1981.
  52. Т.В. К задаче размещения разногабаритных элементов, УСиМ, & I, 1982.
  53. Т.В. К задаче оптимального разбиения платы при размещении разногабаритных компонентов „“ Вопросы радиоэлектроники», серия электронная вычислительная техника, вып.6, 1981.
  54. Т.В. Об одной задаче оптимизации при размещении разнотипных:компонентов, ««Известия АН СССР. Техническая кибернетика», №.б, 1981.
  55. Т.В. Об оптимизационных задачах на специальных графах в алгоритмах размещения компонентов ЭЕМ, ««Вопросы радиоэлектроники», серия &bdquo-Общие вопросы радиоэлектроники», 1983 '-вып. 5,
Заполнить форму текущей работой

Сессия? Спокойно!