Введение к работе
Актуальность темы. В связи с ростом размерностей задач лроеэтирования, возникают слределэнные трудности, обусловленные, во-мнсгом, несоответствием возможностей САП? (методов, алгоритмов, программных и аппаратных средств} требованиям автоматизированного проектирования Указанное несоответствие вызвано тем, что при средних темпах роста сложности объектов проектирования, составлящих более двух порядков за десятилетие, темпы роста быстродействия процессоров общего назначения, реализужщих прикладные программы проектирования составляют за тот же период величину около одного порядка. Это положение усугубляется тем, что временная сложность основных алгоритмов проектирования составляет о(п2) и более. "Ецэ одной проблемой, обусловленной ростом сложности проектируемых изделии, является трудность обеспечения высокой степени интерантивности проектирования. Очевидно, что обеспечение, режима реального времени постоянно усложняется и требует дополнительных усилии. Наряду с повышением производительности САПР явно прослеживается тенденция к снижении нормализованной" плотности' компоновки, проектируемых СБИС. Для преодоления вышеуказанных, проблем предложен ряд подходов, одним из которых является "разработка и использование в составе . технического обеспечения САПР специализированных аппаратных средств, непосредственно реализущих, либо поддерживающих алгоритмы проектирования. При этом относительно остальных, указанный подход реализует максимально возможнее повышение производительности, при росте или сохранении качества, и по различным оценкам и. тестовым- данным., обеспечивается ускорение выполнения алгоритмов проектирования до нескольких порядков. Систематически возникающей в .процессе проектирования является процедура размещения. При этом качество и трудоемкость выполнения процедуры размещения во-многом определяют и результирующие качественные показатели объекта проектирования в целом. Поскольку проблема размещения в обдам случав 'является ЯР-трудной, то на практике она решается, как прззила, с помощью различных авриептсеских алгоритмов,, требующих обычно, полиномиального времени. Однако такие алгоритмы, обесточивающие наибоаэе качественные результаты, при больших размерностях
трэбуют значительного времени. В связи с.этим актуалкшм является
разработка : алгоритмов размещения и аппаратных средств САПР,
непосредственно - реализующих, либо поддерживающих данные
алгоритмы. . -
Цель диссертации. Цэлью диссертационной . работы является анализ, разработка и исследование алгоритмов и аппаратных средств САПР, позволяющих повысить эффективность решения проблемы размещэния.
Для достижения поставленной це-ти были решены следующие основные задачи:
разработка и исследование стратегий и алгоритмов размещения и соответствующих аппаратных моделей;
анализ и классификация специализированных аппаратных средств для поддержки процедуры размещения по типу ' архитектуры,-реализуемым алгоритмам и функциональным возможностям;
выявление основных требований, предъявляемых к разработка специализированных аппаратных - средств для поддержки алгоритмов разменрния, и выработка рекомендаций по их удовлетворению;
разработка и исследование альтернативных вариантов структур быстродействующих устройств для оценки размещения и процассоров р<лзм8щения с расширенными функциональными возможностями;
- разработка альтернативных блоков подсчета критериев и
генерации новых решений на основе формирователей перестановок,
размещений и сочетаний;
Методы исследования. Поставленные задачи решаются на основе элементов теории множеств, графов и гидарграфов, теории алгоритмов, а также вычислительных систем и структур.
Научная новизна работы и основных положений, выносимых на защиту, заключается в следующем:
- на основе анализа и классификации проектов ускорителей
размещения сформулированы основные требования, предъявляемые к
разработке аппаратных средств для поддержки алгоритмов
размещения; '
- в * рамках иерархического подхода- обосновано применэниэ
стратегии размещения, ориентированной на аппаратную поддержку; -
- разработан и исследован, адаптивный алгоритм ограниченной
последовательности и его < аппаратная модель, на оснсве
экспериментальных исслздрвании предложены рекомендации ш выбору
ero параметров (исходное длины поаявдоватвльности в коэффициента модофикацки дайны), обесгочивавсдах наибольшую эффективность;
- предложены способы обработки и разработаны соответствуювди структуры быстродейству юцих устройств (с производительностью до одного порядка выше относительно аналогов) для оценки размещения и аппаратных ускордавлен размещения с расширенными Функциональными возможностями, альтернативных блоков - генерации новых решении и подсчета критериев.
Практическая ценность результатов работы. Практическая ценность работы состоит в том, чта использование разработанных алгоритмов и включение разработанных аппаратных средств в состав технического обеспечения САПР, позволяет существенно ускорить (до 10 раз относительно аналогов) реализацию процедуры размещения, обеспечить жизнеспособность более трудоемких, во . и более качественных .'алгоритмов проектирования, повысить степень интерактивности процесса проектирования, и, таким образом, повысить качество и снизить трудоемкость и стоимость проектирования. Разработанный алгоритм и результаты его исследования могут быть самостоятельно использованы в качестве а,"ешнтов математического обеспечения САПР, а соответстзувдив программы - кагі . инструментальное средство экспериментального исследования различных алгоритмов размещения.
Реализация результатов работы. Основные научные и практические результаты, подученные в диссертации, использованы в 3-х хоздоговорных (х/д NN 13420, .13117, 13119) и госбюджетной работе R13155, выполнявшихся в соответствии с Постановлением N570/137 ' "Создать новые и развить действующие системы автоматизированного проектирования (САПР) и автоматизированные системы научных исследовании (АСНИ) в народном хозяйстве'*, утвержденном ГКНТ АН СССР от 10.11.85., координационным планом работ по комплексной научно- технической программе Минвуза' РСФСР "Системы 'автоматизированного проектирования", утвержденном приказом Минвуза N31 от 25.02.86. Результаты диссертации внедрены а Институте проблем вычислительной техники (ИШТ) РАН (г.Ярославль), где они были использованы при разработке высокоэффективных программно- аппаратных 'средств САПР. Изготовлены и протестированы макеты ряда узлов предлошяЕЫХ устройств (универсальный формирователь пврэстановок, блох
-6-'
введения подстановки, блок оцьнки ш критерию суммарвог длины цвдай), создана программная подсистема для экспериментального исследования комбинаторных алгоритмов размвпрния. Кроме тоге, отдельные научные и практические результаты диссертации Использованы в учебном прогресе на кафэдрэ САПР ГРГУ при чтении лекции и в цикле лабораторных работ по курсу "Автоматизация проектирования ЭВА", при проведении дипломного проектирования.
Апробация работы. Основные положения работы докладывались и
обсуждались на: . '. _
- международной '. конференции и школе . молодых ученых и специалистов "САПР-82. Новые информационныо технологии в науке, образовании и бизнесе" (г.Гурзуф, 1893г.);
-Всероссийских научно-технических конференциях с участием, зарубежных представителей "Интеллектуальные САПР" (г.Геленджик, 1982г. и 1993г.>.
Публикации. Основные результаты диссертации отражены в 5 печатных работах в центральной тачати, сборниках научных трудов и трудах конференций, а также 3 авторских свидетельствах и положительном решении по заявке на патент.
Структура и объем диссертации.. Диссертация . состоит из введения; трех глав, заключения, списка сокращений, использовании в .тексте, списка литературы и приложения. Работа содержит 199 стр., включая 36 рис., 11 табл., список литературы из 100 наименований, 50стр. приложение и актов об использовании.
