Содержание к диссертации
Введение
Глава 1. Современное состояние вопроса интеллектуализации систем автоматизации проектирования
1.1 Задачи САПР с точки зрения интеллектуализации 9
1.2 Математический аппарат САПР (обзор) .19
1.3 Постановка задачи исследований 28
Выводы по первой главе 30
Глава 2. Формализация базовых задач автоматизации проектирования и методика их реиения
2.1 Формализация обьектов автоматизации проектирования аппаратом теории графов 31
2.2 Единая методика решения базовых задач 43
2.3 Модифицированный алгоритм решения базовых задач (на примере распознавания изоморфизма графов) 49
2.4 Аппаратно-программные средства решения базовых задач (на примере распознавания изоморфизма графов).. ..63
Выводы по второй главе 71
Глава 3. Инструментальные средства и принципа интеллектуализации систем автоматизации проектирования
3.1 Инструментальные средства интеллектуализации системы 72
3.2 Модульний принцип построения программных средств интеллектуализации системы 79
3.3 Структура и принцип функционирования Функционально-ориентированного процессора .87
3.4 Оценка эффективности аппаратных и программных.средств интеллектуализации системы 101
Выводы по третьей главе ...114
Глава 4. Практическая реализация средств интеллектуализации системы автоматизации проектирования
4.1 Реализация аппаратно-программных средств интеллектуализации системы 115
4.2 Диагностический контроль топологии БИС и СБИС... 122
4.3 Использование средств интеллектуализации системы при проектировании технологических процессов в легкой промыи-ленности. 142
Выводы по четвертой главе 152
Заключение 153
Список использованной литературы. 154
Прилошения 162
- Модифицированный алгоритм решения базовых задач (на примере распознавания изоморфизма графов)
- Модульний принцип построения программных средств интеллектуализации системы
- Оценка эффективности аппаратных и программных.средств интеллектуализации системы
- Использование средств интеллектуализации системы при проектировании технологических процессов в легкой промыи-ленности.
Введение к работе
Современный уровень развития вычислительной техники-представляет разработчикам в области автоматизации проектирования весьма широкие возмозшости, главным образом в направлении интеллектуализации САПР. Это связано с разработкой принципиально новой теоретической основы, а такке математического и информационного обеспечения в совершенствовании технических средств. В автоматизации проектирования существуют стандартные наборы решений разнообразных задач, которые в практическом использовании в определенной степени удовлетворяют поставленным требованиям. Для более адекватного отображения результатов проектирования заданию, требуется система, имитирующая деятельность человека-конструктора.
Интеллектуальные САПР не могут формировать новые идеи, Ни Ц ТО ЙН \ЩШ опираясь на знания, базовые алгоритмы реые-ния проектируемых объектов, технологий изготовления изделий, алфавит компилятора и параметры элементов систем позволяют проводить направленный поиск решений.
В работе [891 описана концепция развития автоматизации проектирования на машинах пятого поколения, где обязательный условием является содержание в системе программного обеспечения следующих компонентов:
і. Интеллектуальная система обеспечения системотехнических исследований (ИСОСИ);
2. Интеллектуальная сервисная система (ИСС),, для обеспечения работы пользователя в целом с системой проектирования и сохранения высокой надежности ее функционирования.
ИСОСИ обеспечивает проектировщика интеллектуальными средствами, для помощи в проведении системотехнических исследований и состоит в основном из:
- интеллектуальной системы программирования, системы
проектирования, баз знаний:
- интеллектуальной системи проектирования сверхболышх
интегральных схем.
ИСС включает средства совместимости с программами балами данных других машин, справочник средства пользователя h наконец средства автоматического контроля и восстановления. Что касается конфигурации аппаратной системы, то она долань . обеспечивать интеллектуальное общение человека в качестве средств ввода-вывода текстов, речи, графики, изобранений и т. х.
Ц 8 л ь диссертации. Разработка аппаратно-программных методов создания интеллектуальной системи автоматизации проектирования, формализация знаний, данных и процесса проектирования обьектов сложной структуры.
В диссертации исследуются и разрабатываются следующие задачи:
анализ существующих методов, алгоритмов и систем автоматизации проектирования,
методйяагические основы интеллектуальной системы автоматизации проектирования,
математический аппарат, базирующийся на методах теории графов,
способы и методы решения задач теории графов на основе единого входного языка,
аппаратная и программная реализация решения задач теории графов,
разработка инструментальных средств формализации описания обьектов.
Методы исследования. Разработанные модели и методы создания интеллектуальной системы автоматизации проектирования базируются на методах теории графов, теории принятия решений, теории формальных систем, искусственного интеллекта и системного анализа.
На у ч н а я н о в и з н а. Основными научными результатами работы являются разработка методшкичш создания интеллектуальной САПР на основе единой методики решения.задач теории графов и единого входного языка описания обьектов различных предметных областей. Принципиальный вклад в развитии интеллектуализации систем автоматизации проектирования состоит в следующем:
Разработана методгаютическая основа интеллектуальных систем автоматизации проектирования, базирующаяся на методах теории графов и принятия решений. Особенностью такой методе#е«т является комплексный подход в решении проблем проектирования обьектов сложной структуры.
Предложена единая методика решения задач теории графов, основанная на методе разбиения вершин графа на уровни. Единая методика позволяет существенно сократить количество комбинаторных операций возникающих б процессе проектирования.
Создан единый входной язык и способ представления графовой информации в формальной квадратичной форме, основан-
Ч^'Л^^1-4'' -»?7%41«^WfeS^%r*was ст-г**?'-'---'"'-***^'*^—**"!'" *«>—' — <—-
uuti на методах и аппарат* теории rpaij.ub и обеспоиизакций формализацию задач проектирования.
Предлоаена универсальная структура комбинированной записи с постоянной и переменной чагтями для обработки знант"! я данных различных предметных областей, обеспечения достоверности и оперативности доступа к графовой информации.
Разработан <:пособ аппаратно-программной реализации процесса проектирования объектов слияний структуры, основанный на методе разбиения вершин графа на уровни.
Предложен способ взаимодействия между аппаратной реализацией и программным обеспечением базовой машины в процессе проектирования, обеспечивающий высокую производительность за счет распараллеливания вычислений.
Разработаны инструментальные ..ридотва, обеспечивающие связь пользователя с интеллектуальной системой проектирования и формализацию задач различных предметных областей.
Практическая ценность работы.
Разработанные в диссертации научные, теоретические и практические положения, методы и средство могут использоваться при проектировании обьектов сложной структуры в различных предметных областях.
Реализация результатов работы.Основные результаты диссертации пилучены при выполнении научно-исследовательской работы в лаборатории "ВТ и САПР" Института Кибернетики с ВЦ Академии наук Республики Узбекистан; для ре-сения проблемы диагностического контроля топологии БИС и .СБИС d радиоэлектронной промышленности. Инструментальные средства и программное обеспечение системы одобрены Художественно-тех--ническими Советами Акционерного обьединения "ШОБУВЬ", Saw-билского производственного торгово-ывейного обьединения "СУДУ" и приняты на опытную эксплуатацию. Внедрение результатов работы подтверждено соответствующими актами.
А п р о б а ц и я р а б и т и. Основные положения диссертационной работы докладывались и обсуждались на следующих, конференциях и' семинарах: "Проблемы вычислительной математики и автоматизации научных исследований" (Алма-Ата,1908), IX Республиканская межвузовская научная конференция по математике и механике (Алма-Ата,1389), Международная научно-техническая конференция "Теория и методы создания интеллектуальных САПР в машиностроении и приборе,.-,грг.ении" (Минск,.1332), IV Всесоюзная конференция "Методы и средства обработки сложной графической информации" (Нижний Новгород,1331), Региональная
научно-методическая конференция вуяйь Прлла и Сибири (Челябинск, 1389 ). III Международная научно техническая конференция "Интеллектуальные САПР" f Таганрог,!ПЗ;м и др.
П у б л vi к а ц и и. По теме диссертации опубликованы 6 научных статей и тезисов дсікг,лдпь на Международных, всесоюзних и Республиканских конференциях.
Структура побьем работы.
Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 150 страниц текста, 55 рисунков,.4 таблицы, 10 листингов программ и списка литературы из 107 наименований.
В первой главе даются анализ существующих методов, алгоритмов и систем автоматизации проектирования с точки зрения интеллектуализации и методов?ичої'киг неновы реализации проблем проектирования с тачки зрения интеллектуализации и математический аппарат, базирующийся на методах теории графог:, которые позволяют решить трудпоф.-.рмллизугмые задачи различных этапов проектирования. Зто достигается за счет комплексного подхода к процессу проектирования.
Во второй главе показывается необходимость комплексного подхода к проблемам проектирования, требующих разработки совершенных методов и способов ревения задач теории графов. Аппаратная реализация метода разбиения вершин графа на уровни позволит повысить производительность интеллектуальной системы автоматизации проектирования ь целом. Единая методика решения задач теории графов обеспечит конструктивную настраиваемость задач проектирования и высокую информационную связь мевду ними.
В третьей главе опж^ваатся средства содания интеллектуальных систем автоматизации проектирования. Инструментальные средства обеспечивают наиболее удобный диалог пользователя с системой и Формализацию задач проектирования. Модульный принцип построения программного обеспечения и аппаратная реализация процедур комбинаторного характера позволяют составлять оптимальный маршрут решения задач проектирования и повысить быстродействие системы в целом.
В главе//приводится способ взаимодействия аппаратной реализации и программного обеспечения базовой машины, обеспечивающей распараллеливание вычислений за счет разделения задач на аппаратное и программное выполнение, а также возможность использования ИСнПР при проектировании обьектов слонной структуры различных предметных областей.
В заключении приводятся основные результаты получении* в диссертации и соответствующие постановке задачи.
і"
Современное состояние вопроса интеллектуализации j;:j;. автоматизации проектироиания.
В данной глав»; произойди ту а анализ суцествуюцпх методов, алгоритмов и систем"" автоматизации проектирования с точки зрения интеллектуализации я раг.г.кг.триваются вопроси сьязанн:;{ с математическим аппаратом chlt^m г.і-оектиривания. Системы аь-томатизации проектирования основанные на методах теории графов являются одним из наиболее перспективных и удобных способов представления трудпиформилизуемых объекте: проектирования-. Для повышения эффективности решения таких задач, возникает необходимость использования аппаратно-программной поддержки.
1.1. Задачи Г.пііР с точки ^".'Ни* интеллектуализации.
В настоящее время СуЩсСгьуч-т множество систем автоыа тизированного проектирования (САПР) наиболее актуальные с. точки зрения интеллектуализации некоторых задач. Ннокесты. работ посвящено проблеме создания адаптируемых базовых компонент-лингвистического, информационного обеспечений, интеллектуальных средств и САПР с интегрированными ресурсами. {; [13,82,88] приводится подход к созданию средств лингвистического взаимодействия, основанный на понятии единого лингвистического процессора и обеспечиоакщпй достижение большой гибкости и простоты в описании проблемно-ориентированных языки;. САПР; облегчение процесса включения в среду комплексной СПП? новых подсистем и пакетов прикладних программ (ППП); боле о эффективное информационное обеспечение процесса трансляции. 3 основу системы заложен аппарат теории мнокеств, который обеспечит наличие в поставе системного программного обеспечения комплексной САПР средства автоматизации программировать лингвистической среды, адаптируемого к различным проблемно-ориентированным языкам. Для интеллектуальной поддерхкп процессов проектирования и управления, разработана систем.-: КОНЦЕПТ описанная б C25J. Система включает интегрирован;;^' базу данных и знаний, средства логического анализа, вывода, объяснений и мояет рассматриваться как оболочка для экспертных САПР. Достоинством системы КОНЦЕПТ является автонатичс;-
ж
-» * ——"
І ї\ , і І,
леми касающиеся схемотехники и топологии. Учитывая, что интеллектуальная деятельность человека наиболее наглядно проявляется на верхнем уровне, авторами приводятся этапн проектирования на данном уровне:
выбор алгоритма эвристическим путем; ,
согласование алгоритма с заданием эвристическими методами;
синтез архитектуры.
При этом, если полученная архитектура не полностью отражает требования задания, то уровень проекта определяется знаниями и опытом проектировщика. Таким образом, интеллектуальная САПР - система, которая имитирует деятельность конструктора, управляет алгоритмами и знаниями конкретной предметной области, модифицирует их согласно заданию, производит оптимизацию при синтезе проектируемых схем. С ростом сложности и интеграции схем возрастает число знаний'и понятий, которыми необходимо манипулировать ъ процессе проектирования, что приводит к необходимости соответствующих лингвистических средств общения пользователей с интеллектуальными САПР. В [39] для этих целей предлагают лингвистический процессор, обеспечивающий взаимодействие пользователя с системой на ограниченном fформализованном) естественном языке при наличии двухстороннего диалога. Исходя из атого можно определить воз-косности лингвистического процессор.-»:
обучение пользователя и видачо справочной информации;
систематическое пополнение пользователем знаний системы 0 ПреДМеТНОЙ ОбЛаСТИ, а . ТаК ЖЄ ИХ КОррЄКТИрОВКа.
диалоговый режим при проектировании на ограниченном языке;
представление результатов проектирования в виде документов.
Особое место в [391 отвидиая алфавиту компилятора, предназначенный для описания алгоритмов реализуемой схемы к помощью набора функций. Если каждая Функция компилятора называется буквой, тоМ типов букв при проектировании будет иметь А/С разновидностей, отличающихся параметрами. Поэтому моцность алфавита компилятора:
Р^. Ус (из
вариационные возможности представляются б виде:
Далее авторани дается сущность генерации алгоритмов, кновным принципом при генерации алгоритмов интеллектуальных САПР является модификация базового алгоритма стриктурно от исходного. Множество вариантов <;х^н и алгоритмов полученных при генерации интеллектуальными САПР называются областью возможных решений (ОВР) и отражают поррнктнисть знаний, заполненных в САПР. Все решения отличав"''* друг от друга либо па-раметрально, либо архитектурно или содернаниен различных {ркциональных отдельных компонент. Авторами предлагается три зтапа оптимизации решений при синтезе алгоритмов:
Поиск подобласти возможных ремений соответствующих заданию;
Поиск требуемого решения путем генерации серии алгоритмов от базового;
Компиляция букв алфавит а злементов.
На рис. 1.1. показан ОВР при синтезе некоторого алгоритма, где (1-5) - подобласти отображающие возможные решения при различных математических методах. Подобласти описываются граничными параметрами типа:
Si/*u,} , Si „і Тс *u.'n > 71 sntrrj ( 1. 3 )
На первом этапе, если требования представлены нера-иенстваки -W и Т^ То/ , то проверив с помощью
~>i>Uti ^ So/^S/vQX И fmin^ 7fV^ І лак (1.4)
mosho утверждать, что речение удовлетворяет заданию при выполнении этого неравенства. В противном случае, необходимо произвести корректировку заданим.
Второй этап характеризуется поиском реыения в подобласти, где находятся искомые точки А и В, указанных в задании,
Н. третьем этапе производится компиляция букв алфавита элементе; А и выбор соответствующих Функций или алгоритмов.
ЇГ-зстно Г601, что в основу принципа работы действующих САП? положены следующие stohn проектирования: Функцио-
Smax
SW
4)
ГМХ
Sf/ЛІ
глип
S win
_і..
~\5мкх f-
Рис і.і Способ оптимизации ОВР при .синтезе алгоритма
*
ЗАДАНИЕ
ФУНКЦИОНАЛЬНОЕ ПРОЕКТИРОВАНИЕ
-^
АЛГОРИТМИ- . ЧЕСКОЕ ПРОЕКТИРОВАНИЕ
-^
КОНСТРУКТОРСКОЕ ПРОЕКТИРОВАНИЕ
-^
ТЕХНОЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕ
ПРОИЗВОДСТВО
Рис. 1.2 Вертикальные уровни проектирования изделий в САПР
ЗАДАНИЕ
ФУНКЦИОНАЛЬНОЕ ПРОЕКТИРОВАНИЕ
АЛГОРИТМИЧЕСКОЕ ПРОЕКТИРОВАНИЕ
-5>-
КОНСТРУКТОР-СКОЕ ПРОЕКТИРОВАНИЕ
ТЕХНОЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕ
ПРОИЗВОДСТВО
ПРОВЕРКА И КОРРЕКТИРОВКА ПАРАМЕТРОВ
Рис. 1.3 Проектирование изделий на верхнем уровне
клльное", алгоритмической, конструкторское и технологическое (см. рис.і.2). В гбяэи с этик ъ р.-.поте [321 предлагается производить проверку корректности ?лдлниз- но верхнем уровне, т.е. на Функциональном, алгоритмическом и конструкторском (см.рис.1.3),
Следовательно, с точки чрения интеллектуализации проверка корректности требований задания ь определенной степени заключается в решении задач оптимизации при синтезе, а также в генерации исходных алгоритмов. Известии, что с переходом на более высокие уровни, число ОВР возрастает и качественно детализируется. Вместе с тем, проверка корректности задания на конечных уровнях, например при технологическом проектировании требует больших вычислительных и материальных затрат. Поэтому предлагается для повышения ст*п*ни интеллектуализации проектирующих систем, производить проверку корректности задания на алгоритмическом и конструкторском этапе (рис 1.4).
На конструкторском этапе проектирования все задачи условно мохно разделить на три группы:
синтеза конструкции;
контроля полученных конструктивных решений;
оформления и выдачи конструкторской документации»!. Многие задачи синтеза конструкций включают в себя
проблемы метрического и топологического характера. К задачам топологического характера относятся определение планарности схем и построение кратчайших связывающих деревьев. В качестве проблем метрического характера можно рассматривать задачи выделения сильносвязанннх злементпв и нахождение отдельных компонентов связности модели. Для контроля правильности синтезированных конструктивов и компоновки, на основе типизации используются топологические задачи установления изоморфизма и изоморфного вложения графов. Известно, что большинство задач конструкторского этапа проектирования, реализуются на основе большого разнообразия методов и алгоритмов, не связанных между с о fi п л общностью математических процедур и операций [58]. Все алг ;н!тмы и методы относятся к классу комбинаторных и в основної производят комбинаторны^ вычисления на дискретных структурах [74]. В основу таких алгоритмов заложены.процедуры операции полного или сокращенного перебора, поиска, сочетаний и перестановок.
Поэтому проблеме интеллектуализации конструкторского
%'
-vjp-"
ЗАДАНИЕ
ФУНКЦИОНАЛЬНОЕ ПРОЕКТИРОВАНИЕ
->
АЛГОРИТМИЧЕСКОЕ ПРОЕКТИРОВАНИЕ
КОНСТРУКТОРСКОЕ ПРОЕКТИРОВАНИЕ
ТЕХНОЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕ
ПРОИЗВОДСТВО
ПРОВЕРКА И КОРРЕКТИРОВКА ПАРАМЕТРОВ ЗАДАНИЯ
L
Рис. 1.4. Проектирование- изделий на венх уровнях.
ст..
»:.іпа про9ктированио долино удйлдтьса большой внимание, каи
включительно трудоемкому б связи с большой размерностью за-
'. і їч и сложностью размещения элементов. 1« основу реиения мно-
п конструкторских задач положены методы теории графов. ; В настоящее время разроботанк эффективные методы, сис-; ?*иы, принципы размещения и трассировки, программное обеспе-j *гние для проектирования топологии БИС и СБИС различных типов |. : учетом схемотехнических и технологических ограничений,, вы-: ';з5отаны критерии оптимизации топологического проекта І. И2.16,18,43.551.
Одним из сложных моментов данного этапа является про-: !.;гсс проверки топологии путем восстановления электрической ; аеыы по чертежам Фотошаблонов. Математический аппарат, бази-I р^вдийся на методе теории графов позволяет формализовать за-f : дїчи этапа, создавать формальные процедури, методы и алгорит-\ « для решения в'ыые указанных проблем. Полояительные I результаты при виборе эффективных алгоритмов конструирования ; f интеллектуальных САПР дадут широкое использование принципов J параллельного программирования графовых задач [37,58).
Однако для реализации таких алгоритмов требуется соот-! ?.етствующие или современные технические средства сверхвысокого быстродействия. Тем самым возникает еще проблема создания ; специальных средств аппаратной поддермки для интеллектуальных ;; САПР. Это объясняется использованием-на конструкторском этапе : всевозможных операций над матрицами, списками и фреймами. Г Кроме того, граф представляемый в виде матрицы является одним { из наиболее удобных способов задания математических моделей j электронных схем.
I Таким образом, при интеллектуальном проектировании ! кикроэлектронных вычислительных структур основной задачей | звяется решение- оптимизационных задач выбора наилучшего вари-!' лнта структуры и выявление универсальной модели структуры | МП.-
\- Вместе с тем, аналогичные проблемы существуют не толь-
| ко при проектировании изделий в радиоэлектронной промышлен-\ ности, но и при проектировании изделий и технологических про-! цессов в различных отраслях легкой промышленности, | мавиностроения, а также при реиении задач синтеза программного го и информационного обеспечения модульных систем обработки \ данных [1,2,3,17,68.86]. В качестве базового математического
аппарата, описывающей взаимосвязь оснпвнкх структурних элементов проектирования используется аппарат теории графов. Множество вериин графа при этом изоморфно операциям, переходам- и приемам , а множество дуг - отношениям, отражающим временную упорядоченность частей процесса.
Поэтому, обобщая вышеописанный анализ, нохно сделать вывод, что в качестве универсальной модели структуры необходимо использовать графовую модель, а для решения оптимизационных задач - методы теории графов. В связи с этим, ниже описываются задачи теории графов и их практическое применение;на различных этапах проектирования в интеллектуальных САПР.
1.2. Математический аппарат САПР (обзор).
Анализ приведенных ь п.!.!. M'-ї..чі-ь, слгорит.чиь и -:;\-: :?»автоматизации проектирования 11 о к. і '^.'ь а к т, что ь oohiji/j ,::; :-;лояены комбинаторны^ проік-дури, ьнїі /іняюь^ие операции ГшИС-«1, сочетаний и перестановок, Для эффективной реализации ука-ишшх операций необходима максимальная Формализация не толь-до поставленной задачи, но и используемых при этом методов и алгоритмов. Кроме того, обьект проектирования представляя со-*зй сложную систему, с позиций комплексного подхода, состоит -4i отдельных частей связанных различными отношениями и обладает целостным характером функционирования.
Наиболее удобным методом представления и оПраОотки знаний и данных о конкретном ооьькте является метод теории графов [143. Математический аппарат базирующейся на методах теории графов признан не только эффективным аппаратом Формализации задач проектирование, Н'- и как яэик для описания ра.<-
ЛііЧНЯХ ПРОЦЕССОВ И ОчЬ^г, г«".в .
Существует клас»; задач теории графов, основанный на етоде разбиения графов на уровни. Алгоритмы- этих задач является базовыми на многих этапах проектирования и могут быть приложены для решения комбинаторных задач различных предмет-пух областей.
Рассмотрим сущность и метод решения задач этого класса.
Под изоморфизмом графов понимается отноиенне', когда *езду вершинами, ребрами, дугами и питлями двух графов имеет-сз взаимнооднозначное соответствие. Данная проблема относится к сложным алгоритмическим проблемам. Алгоритм распознавания изоморфизма заключается в полном переборе всех вариантов соответствия вераил и сьязеп.
Практически, задача применяется на всех этапах проектирования.САПР,, на. конструкторском этапе ее применение наиболее наглядно и актуально,
В результате проектирования топологии БИС и СБИС могут возникнуть ошибки, связанные с перестановкой соединений, потерей и:прокладкой лишних связей. В конечном счете проектируемая схема не может выдавать требуемые выходные параметры, хотя количество связей и вершин соответствуют заданному. Поэтому необходимо сравнить топологию схемы с исходной электрической принципиальной схемой,
Лри проектировании технологических процессов в легкой
промышленности и маииностроонии задача примэняэтся для проверки результатов технического проекта корректности технического задания [97,103].
Фактически, задача сводится к сравнений двух производных графов и один граф может быть получен из другого путем перенумерации вершин. [34,611. В настоящее время известно более 40 методов и алгоритмов распознавания изоморфизма, а так же.аппаратная реализация одного из' эффективных алгоритмов 171.
Одной из актуальных задач теории графов является задача декомпозиции графов. Существует большое количество методов и алгоритмов декомпозиции. С точки зрения точности решений их условно разделяют на эвристические и детерминированные. Детерминированные методы являются наиболее трудоемкими по способу реализации, но тем не- менее дают точные результаты. С помощью эвристических методов мовно получить линь одно лекальное решение, хотя легкореализуемы. Для решения этой проблемы создаются рандомизированные алгоритмы, основанные ка случайном поиске, что позволяет находить серию локальных решений с приближенными результатами.
Практически, задача декомпозиции используется для компоновки электронных схем в блоки по определенным заранее критериям [68,751. В основном, различие алгоритмов декомпозиции графов заключается в -способах лтбпро вершин графа в соответствующие подмноаества.
В зависимости от способа отбора вершины все алгоритмы делятся на последовательный, паралл*льно-последовательные и итерационные. Известны следующие спосибн отбора вершин:
из невнбранного мнойест*а ькршин выбирается такмя вершина , которая максимальным числом ребер связана с вершинами формируемого подграфа;
выбирается вершина, связанная минимальным числом р*-бер с вершинами Формируемого подграфа;
выбирается вершина, связанная максиальным числом ребер с вершинами формируемого подграфа и минимальным числом ребер с вершинами, ене не распределенных ни в какой подграф.
Задачи-декомпозиции имеют следующий- набор основных критериев:
а) число внешних соединений меаду подграфами;
б) число подграфов;
в) число типов подграфов;
Г) ЧИСЛО ВерИИН В ППДГрйфг'.
Первнй критерий определяется Функционалом ьнеиних связей:
где ^-jm^'/V=7 - заданое разбиение графа на подграфы,
- число внешних ребер, соединяющих графы
he И hi.
Второй критерий характеризуется числом подграфов в разбиении. Поэтому, если ^--/"/tjyw - разбиение графа на подграфы, то A/fTD-M , где т - число графов б разбиении.
Третий критерий определяет иднптипность графа, т.е. наядой вершине графа присвоен один тип конечного набора.
Очевидно, что задача декомпозиции графов относится к числу многокритериальных. Поз тану метод реаения таких задач заключается в выборе начального множества вершин исходного графа. Далее к каждой из веріїин последовательно^ присоединяются другие вершины для образования подграфов искомого разбиения. Способ разбиения и требования при отборе вершины описаны выше. Практически, задача используется для компоновки базовых элементов при конструкторском проектировании БИС и СБИС. При проектировании технологических процессов в легкой промышленности и машиностроении задача используется для разбиения обобщенного графа на подграфы " цепью построения графа технологического процесса конкретного изделие [36,100,10?.].
Суть задачи построения минимального связывающего дерева и минимальной гамильтоновой цепи состоит в следувідем: задано множество вершин хсХ графа I.-
Первый метод основан на многократном использовании двух теорем 172]:
Когда вершина минимального дерева непосредственно связана по крайней мере с одной и- близайаих соседних вершин.
Каадая цепь н минимальном дереве связана по крайней мере с одной из соседних цепей кратчайшими ребрами.
Второй метод обеспечивает последовательный выбор кратчайшего ребра, не образующего цикла с ранее выбранными ребрами минимального дерева С81J. Для этого строится полный граф и составляется список ребер в порядке возрастания из длины.
9'>
Третий метод основывается теоремой, которая утверждает, что граф, образованный из полного графа, устранением всех возможных циклов путем удаления в каждом из них по одному ребру наибольшей длины, есть минимальное дерево [641.
Согласно этого метода, сначало нумеруются ребра в порядке возрастания длин так, что длина dj не превышает длины djl, если j
Выше описанные методы дают приемлемые результаты только в том случае, если в каждой вершине мояет сходится неограниченное число робер. При схождении в вершине не более двух ребер, задача соединения элементов оказывается эквивалентной задаче коммивояжера и для получения оптимальных решений в случае большого количества вершин требуется весьма'значительный объем вычислений.
Практически, задача построения минимального связываю-іего дерева решает проблему трассировки соединений на площади кристалла. Основные трудности при трассировке соединений обусловлены отсутствием эффективности алгоритмов, учитывающих особенности проектирования топологии, что приводит к получению проводников слоишкх конфигурлций и увеличению числа пересечений соединений.
Кроме того, задача является оптимизационной, так как производится перебор всех варииантоБ проведения соединения. Для таких целей используют эвристические методы построения алгоритмов трассировки соединений. В качестве критерий трассировки соединений могут быть минимизация суммарной длины соединений цепей, числа-пересечений на площади кристалла. При проектировании технологических процессов в легкой промышленности и машиностроении задача используется для устронения избыточных связей между вершинами графа технологического процесса изделия, полученной из обобщенного базового графа 199,103,1053.'
В [5R] предлагается один из методов нахождения путей в графах-и перечисления-путей. Pro мойно использовать не только для неориентированных графов, но и в общем случае, для смешанных мультиграфов Г8П.
Задача ставится следующим образом. Пусть -йнициальный неориентированный граф с начальным множеством А'. Необходимо найти Rl(A) и его мощность//^,)/, т.е. число воз-'
?л
аоаннх путей в/7 .
Решение этой задачи разбивается на четыр-- зтапа. Сначала гр_аф_^=
Опишем все этап» решения поставленной зад.-чи.
Первый этап заключается в преобразовании графа_с кратными ребрами'и петлями (рис 1.5) в обыкновенный граф L*(Xti/y/i>.
Пусть ХссХ - произвольная вершина граф.-.Z, ,Xf- другая
верізина такая, что в графе L существует &-кратк;;> ребер, сое
диняющих зти вершины. :.
k - кратным расцеплением графа ^ в точке Xj называется Граф С -
где $gfij) - J -й .экземпляр вершины X) .
Если А,--.,&.- все кратные ребра, связизлэцие x
Полным расщеплением Ь называется граф, полчченный последовательным расщеплением графа в вершинах, имеющих кратные ребра. Граф, полученный в результате полного расщепления, будет конечным, обыкновенным;. обозначим его /.-<Х,ц//>%
На втором этапе применяют к полученному графу операцию разметки (разбиения по уровням4., описанную выше. Вершиш; последнего уровня будут называться конечными. Для построенного пути графам обязательно будут неповторяющиеся вериины.
Мноаество конечных вериин последнего уровня обозначим
как В, тогда задача нахождения всех путей, начинающихся в^ и кончающихся в 6 , состоит в построении множества Р*6?,в)\
Заметим, что если Fr-Хг - число элементов на уровне г, то для каждой вершиниХсХг ее связность не превышает числа Fr„i+Pr + Fr-+i , так как все вершины, смежные данной, распадаются на три класса: лежащие на предыдущем уровне, на данном уровне и на следующем уровне; при ьтом надо ичесть, что граф Z г обыкновенный, следовательно клмдля пара вершин инцидентна не более чем одному ребру.
Предлоиенный метод и алгоритмы можно применять для заданных фиксированных начальных и конечных вершин при проектировании БИС и СБИС на конструкторском этапе. При проектировании технологических процессов в легкой промышленности и машиностроения задача используется для нахождения оптимальних путей в графе технологического процесса изделия с целью «онпактного размещения смежных операций [103,105].
Суть задачи изоморфного влохения графов состоит в следующем: если имеется граф L=
Как задача распознавания изоморфизма графов, данная проблема имеет комбинаторный характер и поэтому в [51,65,763 сделаны попытки сократить перебор при ее решении. В [563 приводится следующий наиболее эффективный метод.
Заданы два графа I. и С с перенумерованными в.ериинани, где соответственно /?- AV,/#-/K/. Для решения задачи необходимо, чтобы IXl^lY/jiW^n . Множество векторов степеней вершин
графа L представляется в виде S(X)-< St(xl). St(x2), ,
St(x-)>.. а для графа G - S(Y')=
Необходимо получить матрицу соответствия S^~ i^ij} следующим образом.
У~СЛ s-t (*)> Si (*)
Вершина хі при влоаении может соответствовать.лииь таким вершинам у], для которых/Чу =1. Каждая строка матрицы соответствий задает множество тех вершин графа G, которые могут соответствовать вершине графа.L, определяющей данную строку. Согласно метода последовательно строятся частичные соответс-
твия между вершинами и ребрами, после чего проверяются на условие изоморфности с помощью матриц инциденций. Частичные соответствия определены на подграфах графа L, которые образуют расширяющуюся последовательность, заканчивающуюся графом L.
В целях повышения эффективности алгоритма вершины rpa-fa упорядочиваются по числу возможных соответствий. Для этого создается упорядоченный по возрастанию вектор:
Первый подграф графа G состоит из единственной вериини с минимальным весом Ifo Затем, каждому подграфу очередного этапа, строится список частичных .изоморфизмов (вложений), т.е. присоединяют новую еще не рассмотренную вершину графа-L. Для этой вершини формируется множество допустимых вершин гра-$а L. Каждая такая вершина порождает расширение соответствия. 3 случае изоморфности этого расширенного соответствия, он г* заносится в список изоморфных плояений данного подграфа.
Процесс продолжается дп тех пор, пока не получится список соответствий всего графа L. Если этот список пуст, то L не имеет изоморфного вложения б граф G.
Практически, задача изоморфного вложения графов используется в покрытии структуры определенным количеством су— цествуютих типовых микросхем и проблема ставится следующим образом: Структура S описывается графом U
Таким образом, анализ актуальных задач используемых в САПР, а так же большинство существующих работ, базирующихся на аппарате теории графов показывает, что важное место при проектировании, занимает формализация основных сведений об объекте, этапов и задач. Кроме того Формализация должна да-
z?
зать четкое представление об исходной информации, типах математических моделей, используемых в проектировании, а так »е представлять основные алгоритмические методы и. процедуры ре-вения задач. В работе [34] приводится язык отвечающий требованиям формализации - язык теории графов. Здесь ке.дается ме-годюагрическая основа создания интеллектуальных САПР„ описываемая языком и аппаратом теории графов. Для эффективного .решения класса задач г. наилучшим качеством и минимальное ?ремя целесообразно создание аппаратно-программной поддераки ориентированной на общие процедуры. Как видно из описания указанных задач наиболее общей процедурой при их реиении- является процедура разбиения графа на уровни. Аппаратная реализация процедуры позволит повысить быстродействие системы проектирования в целом, т.к. разбиение во всех задачах используется для сокращения времени перебора.
1.3. Постановка задачи исследований.
І ;': Приведенный »ыие анализ Пнка'знвает, что в настояце^
V. .' время в области автоматизации проектирования наиболее акту-
\\ гг. альной становится научно-техническая проблема создания интел-
гг ) лектуальных комплексних САПР с интегрированными ресурсами,
t і которая обусловливает включение в состав основных средств ин-
| ,ч те.ллектуальное обеспечение. Необходимость такого.обеспечения Щ^ ;,, " возникла в-связи с повышением-сложностью; проектируемых изделий и точностью их верификации.
В настоящее время делаются попытки; создания, .такой, сис
темы проектирования, которая имитировала бы деятельность
конструктора-разработчика. Поэтому, создаваемая интеллекту
альная система долана обладать возможностью:тесной интеграции
аппаратных и программных средств, гибкой программной перест
ройки процессов Проектирования, быструю адаптация в.-различных
предметных областях за счет единого входного языками.проект
ных процедур, а.такае производить интеллектуальное-сопровон-
дение процессов проектирования. у :.;:.- .:.
Как показывает анализ работ , такими возыокностямн долана обладать и интеллектуальная САПР . При. этом, основини математическим аппаратом для реализации указанных возможностей являются методы теории графов, так как они легко формализуют задачи проектирования любого зтапа и создают формальные методы и алгоритмы.
Известно, что задачи различных этапов проектирования
|,'ї ; при создании интеллектуальных САПР практически, не связана
т\ ]t меяду собой общностью.математических процедур и операций, рь-
S? ", \ ализуются большим разнообразием методов и алгоритмов конбина-
(: "~j \ торно-логического характера. Применение единого входного язы-
). h і/ ка с одной стороны позволяет осуществлять параметрическую
?$ еЛ'-w настройку на различные форматы данных , ас другой стороны
И Щг' ".приводят к увеличению обьема хранимых данных, что замедляет
у '&''/' поиск необходимой информации.
;; ) Jl ,. Сложившуюся проблему мояно эффективно реыить введенной jlIі в состав технических средств интеллектуальных САПР высокопроизводительных специализированных устройств.
Однако, интеллектуализация процессов проектирования предусматривает расширение области возмойных реиении и соответственно получение различных вариантов параметров объект.). Поэтому возникает проблема отбора оптимального варианта :: контроля функционирования обьекта после каадого зтапа проек-
-^»^^.я*«чтаг№,р^,г.~!»-»«>'^».%^,м|С«'Г*^
тирования, которая основана на решении задачи, распознавания изоморфизма графов.
В связи с указанными выше проблемами в данной работе предлагается решение следующих задач:
Анализ существующих методов, алгоритмов и систем автоматизации проектирования с точки зрения интел -лектуализации.
Обоснование и выбор единого входного языка описания объекта и разработка единой методики решения задач теории графов.
Разработка аппаратно-программного метода решения задач теории графов.
Аппаратная реализация процедуры разбиения вершин графа на уровни и выбор способа взаимодействия с базовой машиной.
5.Разработка инструментальных средств создания интеллектуальной системы автоматизации проектирования.
6. Разработка методов реализации интеллектуальной системы автоматизации проектирования в различных отраслях промышленности.
Выводы по первой главе:
В результате анализа <.ущт тьующих методов, алгоритмов и СнПР с точки зрения интеллектуализации, обоснована необходимость разработки методологической основы решения задач теории графов и создания системы проектирования, имитирующей деятельность человека.
Выбран математический аппарат, базирующийся на методах и аппарате теории графов, позволяющий описывать сломные обьекты проектирования, создавать формальные методы и алгоритмы, повышающие степень интеллектуализации задач проектирования.
Для эффективной реализации проблем комбинаторно-логического характера, предложен аппаратно-программный метод создания интеллектуальной системы автоматизации проектирования.
На основе предложенной методологии решения проблем проектирования, сформулирована постановка задачи разработки интеллектуальной САПР.
Модифицированный алгоритм решения базовых задач (на примере распознавания изоморфизма графов)
Конструкторские задачи являются труднореиаеными и характеризуется применением эвристических методов реііеїшя. Поэтому для значительного увеличения эффективности, совреыешшс-СйПР долгны обладать принципиально новини функциональными возмоаностяыи, такими, как наличие интеллектуального интерфейса с пользователем, управления едиными и больииыи базами данных и знаний. Кроме того, интеллектуальные СйПР долины представлять собой технические системы, состоящие из больного числа специализированных, функционально-ориентированных и проблемно-ориентированных аппаратных средств. Цель ориентации состоит в том, чтобы добиться решения поставленных задач определенного круга, с наилучшим качеством за минимальное время. Проблемная и функциональная ориентация предполагает аппаратную реализацию алгоритма решения задачи, позволявши добиться максимального быстродействия.
Анализируя работу алгоритма распознавания изоморфизма графов приведенного в п.2.3 мокно отметить, что этап разбиения вершин графа по уровням является наиболее трудоемкой по времени выполнения, имеет комбинаторные процедуры и операции, число повторений которых намного превышает числа вершш исследуемого графа.Так, на приведенном алгоритме (рис.2.12) произвольный граф имеющий І5 вершин, при разбиении по уровням представляется в виде массива SMEG размерностью пропорциональной числу смежных вершин. Поэтому для нахождения элемента очередного уровня, необходимо просмотреть весь массив.
Для аппаратной реализации таких комбинаторных процедур в САПР, ваанейшим является вопрос построения электронных моделей графов (ЗМГ). ЗМГ обладают более широкими функциональным : возможностями: - расширяет класс решаемых графовых задач, - позволяют автоматизировать ввод-вывод данных, - позволяют оперативно изменять структуру задачи, - упрощают агрегатирование спецпроцессов с универсаль- ними ЗВМ и другими устройствами. В [7,3,10,58] приводятся несколько способов аппаратной реализации задачи определения изоморфизма графов. Нужно отметить, что повиаая производительность САПР в целом - эти способы создают некоторые затруднения в целесообразности их использования: 1, Любая, полная аппаратная реализация кого-либо алго ритма требует значительных затрат на проектирование и производство оборудования. 2. Устройство, ориентированное на работу конкретного алгоритма не может быть использовано для решения оп ределенного класса задач на графах. Зти две проблемы являются одним из основных в повышении эффективности САПР РЗА и СБИС, поэтому в работе предлагается способ повышения степени интеллектуализации САПР за счет использования оптимальной аппаратной поддержки, реализующей комбинаторную процедуру разбиения верщин графа по уровням. Особенностью процедуры разбиения является то, что перестановка элементов производится на большие расстояния. Алгоритм работы процедуры основан на методе сортировки с помощью разделения. Допустим, задан массив в произвольной последовательности и имеется начальная вершина графа L, представленная в Формальной квадратичной форме, каждый элемент SMEG имеет вид С2.І0). Индекс массива I производит просмотр элементов с начала, 3 соответственно с конца. Тогда работа алгоритма сортировки основывается на следующих шагах: 1. Производим проверку условия Xo=SMEG[I].BEG слева г. е. с начала массива. Если, данное условие выполняется, то SHEGU1.BEG считается вершиной уровня-. R, т.е. выбираем следующий 1-й элемент и переходим к началу шага. 2. Производим проверку условия Xo=SMEG[J].BEG справа, т.е. с конца массива. В случае выполнения; условия, SMEGtOT.BEG считается вершиной уровня R, т.е. производим перестановку местами элементов с индексами I и 3, а затем осуществляем дальнейшую проверку условия 2. 3. Производим проверку условия равенства I и 3. Выполнение данного условия, свидетельствует просмотру всего массива и формированию вершин и связей уровня R. Если условие не выполняется, то возвращаемся к шагу 2. Таким образом, суть комбинаторной процедуры сводится к сортировке элементов массива определенной размерности, т.е. члены массива для которых значения конца связи равно значению начала связи следующего уровня переносятся на начало массива. Далее для отличия, элементы массива будем обозначать следующим образом: в программах через SMEG, в аппаратной поддеряке через EQ. По описанным BUtse шагам на рис.2.1 4 приводится блок-схема алгоритма сортировки, т.е. процедуры-разбиения вершин и связей графа по уровня.
Алгоритм в основном состоит из трех основных частей А, В и С. В первой части А элементы массива EQ.BEG, начиная с I-того, проверяются на соответствие или равенству X. Как только это условие нарушается происходит переход ко второй части В, где производится проверка на неравенство X с конца, начиная с J -го элемента. При невыполнении этого условия производится проверка l =j, которая говорит о том, что перебраны не все элементы массива. В случае ее правильности производится перестановка элементов списка массива (часть С). При выполнении конечной проверки алгоритм или заканчивает работу, или выполняется заново. Таким образом, все элементы массива группируются согласно условиям сортировки.
Несмотря на свою кажущуюся простоту, оптимизация времени работы, данного алгоритма имеет большое значение, так как процедура разбиения вершин графа по уровням является часто встречающейся при решении графовых задач данного класса. Кроме того, как видно на рис.2.12 данный алгоритм входит в тело общего цикла программного обеспечения и тем самым задача принимает экспоненциональннй характер,
Поэтому наиболее кардинальным решением задачи оптимизации времени выполнения данного алгоритма является изготовление специального аппаратного блока.
Как, известно [36], работа большинства современных вычислительных машин, заключается в последовательном выполнении операций. Так, процессор долаен сначало считать из оперативной памяти код команды, затем операнды, необходимые для выполнения этой команды, далее произвести преобразования и снова считать код команды, которая долмна указать, что надо делать с этими преобразованными данными, считать операнды необходимые для данной команды и так далее. На все эти действия тратится время. Для аппаратного решения характерно то, что оно ориентировано на конкретную задачу, которую выполнит быстро и точно. Такой подход приводит к потере универсальности, но в результате дает колосальний выигрыш во времени, за счет того, что многие операции при аппаратном решении выполняются одновременно. Так, в нашем случае при выполнении программы по выше указанному алгоритму, в части А требуется не менее сотни машинных команд на один цикл. Аппаратная реализация данного алгоритма - не более двух тактов.
Модульний принцип построения программных средств интеллектуализации системы
Блок логики состоит из следующих регистров: - регистров EQfil .BEG и EQCJ1.BEG содержащих текущие значения соответствующих массивов, - регистров X, содержащего значение сортирующей верси-ны графа. - регистров I и 3, содержащие соответствующие значения переменных, - регистра ММ, содержащего значение размерности массива, - регистра Р, содержащей число равное количеству элементов массива соответствующих X. Такие имеются схемы сравнения данных и постоянное запоминающее устройство, в котором находится вся логика данного устройства. Схема работы блока логики- приведена на рис.2.16. Рассмотрим кратко работу данного блока. После связи с ЗВМ начинается работа всего устройства (одновременно с записью X происходит обнуление регистра Р и занесение значения ИМ в регистр Л. Из ОЗУ происходит занесение текущих значений массивов EQ.BEG. Затем сравниваются все параметры между собой. В зависимости от их комбинации ПЗУ вырабатывает следующие сигналы, которые выполняют следующие функции: Перестановка - производит перестановку значений элементов массива; Конец - показывает конец работы блока. Таким образом, предложенный метод аппаратно-программной реализации процедуры разбиения вершин графа на уровни позволяет существенно повысить производительность системы на некотором классе задач. Такие устройства называют Функционально-ориентированными процессорами, работа которых в составе технических средств САПР организуется таким образом, что помимо увеличения производительности за счет функциональной специализации оборудования, дополнительное увеличение быстродействия можно получить заменив программное решение задачи процессом электронного моделирования и обеспечения одновременного выполнения операций на различных функциональных устройствах . 1. В результате анализа способов представления графовой информации обоснован и предложен единый входной язык решения задач теории графов, основанный на Формальной квадратичной форме представления графов и структуре комбинированной записи с постоянной и переменной частями, для обработки, хранения знаний и данных об объектах различных предметных областей. 2. На основе единого входного языка, разработана единая методика решения задач теории графов, позволяющая составлять маршруты проектирования, параметрическую настройку на различные форматы данных и т.д. 3. Для апробации единой методики решения задач теории графов и единого входного языка, в качестве примера рассмотрен модифицированный алгоритм распознавания изоморфизма графов, использующий метод разбиения вершин графа на уровни. 4. Проблемы комбинаторно-логического характера в задачах теории графов, решаются с п Мои;ьй разработанного спецпроцессора, реализукщет разбиение вершин графа на уровни и аппаратно-программного метод/,. Интеллектуализация систем автоматизации проектирование" БО многом зависит от степени формализации задач, которые имеют комбинаторный характер и от принятия реиении ъ конкретні,-;-. условиях. В число таких задач мояно отнести задачи проектирования средств вычислительной техники и технологических процессов различных отраслей, например легкой промышленности. Создание интеллектуальных систем в основном зависит от разработки инструментальных средств. Универсальность инструментальных средств определяет уровень интеллектуализации системы. Предполагается метод создания инструментальных средств с аппаратными и программными обеспечениями, которые базируэт ся на единой методике решения задач теории храфов , ;. 3.1. Инструментальные средства интеллектуализации системы. С расширением круга пользователей различных областей интеллектуальной системы, возникают проблемы их взаимодействия. Средства, обеспечивающие связь пользователей с системой будем называть инструментальным. Инструментальные средства интеллектуальной системы ус ; ловно мохно разделить на два уровня (см.рис.3.1). Проектиро . вание изделий или технологического процесса, в основном базируется на .идее сочетания инженерной интуиции, возможностей .. системой и способов человеко-машинного взаимодействия. Поэтому, инструментальные средства первого уровня, характеризуют :; большим разнообразием средств Формализации обьектов различных предметных областей, г. помочь» которых пользователь Формирует задание. К инструментальным средствам второго уровня относятся средства, обеспечивающие непосредственно процесс проектирования, т.е. запросы аппаратно-программного комплекса, которые являются универсальными для определенных задач проектирования. Одним из основных средств обеспечения взаимодействия пользователя с системой на всех уровнях являются командный диалог и диалог типа "вопрос-ответ". При построении структури ; программного обеспечения максимально учтены интерактивные принципы, при которых: - интеллектуальная система "проявляет инициативу" и ведет пользователя к решению его задачи; - для более опытного пользователя система оказывает помощь и действует только по его запросу. Далее в п. 4.2 рассмотрим пример расчитанный на опытного пользователя и поэтому диалог обеспечивает только подсказку на его запросы. Кроме интерактивного режима взаимодействия пользователя с, интеллектуальной системой к инструментальным средствам относятся средства отладки программного обеспечения (компиляторы), средства ввода-вывода, средсва помощи типа "HELP", редакторы базы знаний. При создании интеллектуальной системы эти средства используются в сочетании или по отдельности на различных уровнях.
На уровне формализации производится настройка система на конкретную предметную область и формируется техническое задание для проектирования (рис. 3.1.).
В блоке 1 описываются характеристики конкретной предметной области и редактирования базы знаний. В большинстве случаев в качестве редактора знаний используется стандартные текстовые редакторы типа LEXICON, CHIHRITER или NORTON утилиты. После модификаций правил данных в предметной;области производится синтаксический контроль и проверка по качественному содержанию. Поэтому данный блок называется блоком формирова-( ния базы предметных знаний. В блоке 2 производится анализ выбранных проектировщи-: ком характеристик, выбор критериев для синтеза системы, выде-. ление среди них наиболее значимых и идентификация полей . переменной части структуры комбинированной записи типа выражения 2.10. в п. 2.1.
Оценка эффективности аппаратных и программных.средств интеллектуализации системы
Дополнительно вырабатывается с выхода элемента 2-И-НЕ DD33 сигнал R.EQ.BEG, записывающий содержимое текущего члена массива Eq.begfі 1 или Eq.begtj], Б регистр DD32. Этот сигнал вырабатывается из комбинации сигналов R.EQCJ] и R.EftCI]. Также для синхронизации записи в ОЗУ блока сортировки из комбинации сигналов Н.Е0.Ш и H.EQC3] вырабатывается сигнал WRITE (выход элемента DD54), поступающий на ОЗУ . ...
Работа блока сортировки происходит в два такта . После поступления разрешающего значения сигнала H0RK через некоторое время, равное времени перезарядки конденсатора С2 (см. рис.3.6.), начинает работать задающий генератор, выполненный на микросхеме DD35. Когда напряжение на выходе генератора равно,0,, то разрешаются операции с ОЗУ блока сортировки (считывание и запись 1-такт), когда і то операции сравнения и переключения счетчиков по заднему фронту импульсов -3, +1 и +Р (2-такт), Данное разделение чтения и анализа позволяет исключить временные перекосы из-за иеодновременности срабатывания схемы сравнения. Исключение составляет импульс -3 во время выполнения программы перестановки данных в ОЗУ,, но при этом не выполняются операции сравнения.
В начальный момент времени на адресные шины ОЗУ через мультиплексор на микросхемах DD38, DD39 поступает адрес 10 со счетчика I. В первом такте на выходе DO ПЗУ DD34 вырабатывается сигнал R.EQfll записывающий данные с ОЗУ в регистре 1DD10 (см. рис. 3,4.). Одновременно вырабатывается сигнал R. E.g.beg, производящий запись в регистр DD32. Схема сравнения DD30, DD31 и DD53 сравнивает значение числа X с выхода регистра DD4 (см. рис.3.5.) с текущим значением массива Eq.beg [{] с выхода DD32 и в случае равенства устанавливает на выходе триггера DD53 сигнал EQ.DEG-X в единицу. Во втором такте устанавливаются +1 и +Р, прибавляющие 1 к их содержимым. В случае неравенства Eq.begtn и X на выходе DD53 устанавливается в 0 и во втором такте не вырабатывается ни каких импульсов и в следующем такте вырабатывается сигнал R.EQC33, который производит во-первых, переключение триггера DD40 в. резни 3, при этом мультиплексор переключается для работы со счетчиком J (т.е. на адресной ыине ОЗУ выставляется адрес 3, а ПЗУ переходит в режим работы с адресами 3), во-вторых, запись ОЗУ в регистр 1DD11- и запись текущего значения EQ.begfJl в регистр DD32. В случае неравенства члена массива Eq.begh 3 числу X на выходе схемы сравнения 0 и во втором такте вырабатывается сигнал -3, по заднему Фронту которого происходит вы-.читание і из содержимого счетчика 3, в случае равенства во втором такте не возникают ни какие сигналы, а в следующем такте вырабатывается сигнал CHANGE, производящий установку триггера DD41 в режим перестановки. Сигнал подтверждения АСК. СН поступает на вход ПЗУ, сбрасывает сигнал CHANGE и запускает программу обработки перестановок.
Так как в начальный момент работы режима перестановки на адресной шине установлен адрес J, в регистре 1DD10 (см. рис.3.4.)- значение Eq.begtiJ, то надо занести это значение в ОЗУ, потом переключиться на адрес I и записать в ОЗУ содержимое регистра 1DD11.и. выйти из режима перестановки. Поэтому в первом такте программа перестановки, зааитая в ПЗУ, вырабатывает сигнал Н.ЕРЛП и через элемент 2-ИЛИ-НЕ DD54 сигнал WRITE, активизирующий микросхемы ОЗУ 1DD8, 1DD9 через элемент 2-ИЛИ-ЯЕ 1ВВ? в реши записи. Лри этом под действием сигнала H.EQfl] регистр 1DD10 выставляет свое содержимое на шину данных ОЗУ. То есть происходит запись Б ОЗУ. По заднему фронту импульса и".ЕОГИ происходит сброс триггера DD40 и переключение мультиплексора адреса DD38, DD39 для работы со счетчиком I, т.е. на адресной шине ОЗУ устанавливается текущий адрес I. В следующем такте вырабатывается сигнал W.EQfJ], который производит аналогично запись регистра 1DD11 в ОЗУ. Во время этого такта вырабатывается сигнал -3, вычитающий і из содерхимого счетчика 3. По заднему фронти импульса И.ЕЦШ происходит переключение триггера DD41 и окончание программы перестановки. Видно, что перестановка происходит во всех ОЗУ одновременно и тем самым достигается выигран во времени. Программа сортировки продолжает работу дальше.
Если во время работы программы содержимое счетчика I становится больше содержимого счетчика 3, то схема совпадения DD45, DD46 вырабатывает сигнал.1 3, который через микросхемы DD19, DD18, DD17 поступает на триггер DD21 и сбрасывает его. Сигнал WORK устанавливается в единицу и блок сортировки заканчивает свою работу. Таким образом, описанные блоки, Функционируя вместе с программным обеспечением, представляют собой спецпроцессор. На рис. 3.8. приводится место данного спецпроцессора в процессе проектирования СБИС.
Поэтому из оценки эффективности спецпроцессора, приведенного в п.3.4,- описания в п.2.4 и выые, можно сделать выводы: - устройство является мощным средством повышения на несколько порядков производительности САПР ; - высокая производительность достигается за счет использования режима разделения задачи между спецпроцессором и базовой машиной; - повышение эффективности работы спецпроцессора зависит от качественного взаимодействия его с программным обеспечением базовой машины и САПР в целом. преямуцсстьа интелл .-ктуальннл СЯПР изделий PSA связаны -с возможностью моделирование функционирования СБИС и реальных рабочих условиях без изготовления кристалла. С по-моцью моделирования обычно наблюдают за поведением проектируемых систем до. создания, если точно заданы параметри компонентов и межсоединений. Большинство разработчиков интегральных схем пользуются только средствами ввода принципиальных схем в связи со сложностью ряда средств проектирования, особенно.при моделировании неисправностей. Лля конструкторов работа с программой моделирования требует формирования обширной библиотеки моделей интегральных схем. Поэтому одним из путей избежания сложности создания базы моделей СЯПР является использование последовательной автоматизации проектирования; сначала отрабатывают и совершенствуют процесс схемного ввода, затем переходят к освоению средств моделирования.
Существенное увеличение скорости моделирования, позволяющее резко повысить сложность эффективно разрабатываемых схем, может быть достигнуто применением специализированных вычислительных средств.
При работе со спецпроцессорами моделирования в обцем случае появляются дополнительные по отноыенкю к программному моделированию временные затраты, связанные с преобразованной примитивов модели, перекодировкой исходных данных во входном Формате спецпроцессора и пересылкой Б спецпроцессор полученных загрузочных файлов. Диаграмма распределения общего времени моделирования при программном и аппаратном подходах приведена на рис. 3.8.
При нерациональном использовании аппаратного моделирования временные затраты ухидиавт эффективность спецпроцессоров, тем самым увеличивают общее время моделирования. Поэтому в интеллектуальных САПР параллельно применяются аппаратное и программное моделирования.
Наиболее эффективным является подход, в результате которого МОЕНО сократить дополнительные временные затраты при аппаратном моделировании на Формирование загрузочного файла и ее загрузку. Основным путем решения этой проблемы является .максимальная интеграция спецпроцессоров, точнее функционально -ориентированных процессоров с программным обеспечением системы или базовой маыины.
Использование средств интеллектуализации системы при проектировании технологических процессов в легкой промыи-ленности.
. Текст программы на языке ассемблер приводится в приложении. Принципы функционирования ООП во время обмена информации подробно описаны в п.3.3. Поэтому рассмотрим поведение ЦП при взаимодействии с аппаратной частью задачи. На .рис.4.3 приводится алгоритм работы центрального процессора при обмене с ФОП.
Последовательно, выполняя команды основной программы разбиения графа по уровням и встретив, команду обращения к процедуре SORT, центральный процессор формирует список запросов готовности ФОП к сеансу обмена. Если ФОП не готов к обмену данными, то ЦП находится Б режиме ожидания. При поступлении сигнала в порт ввода-вывода ПОИ) с ФОП, ЦП производит подготовку массива EQ и параметров Р,Х и I к обмену и передает управление ПДП. Пока происходит передача данных с помощью ПДП, ЦП находится в режиме ожидания,, т.к. ПДП занимает системную- вину для "непосредственного обмена иформацей между ОЗУ БМ и ОЗУ ФОП, После окончания обмена и освобождения системной иинц КПДП, начинается распараллельливание вычислительного процесса. ФОП производит операции сравнения и перестановки в массиве EQ, а ЦП - выборку элементов EQ.EN=X во вновь полученном массиве, для Формирования следующего решения. Окончив выборку, ЦП проверяет; что число переставленных элементов массива не достигло общего числа элементов массива. Если условие не выполняется, то работа алгоритма повторяется. В случае выполнения условия, ЦП продолжает выполнять основную программу решения задачи распозиавония изоморфизма графов.
Таким образом, описанный способ аппаратно-программной реализации задачи, характеризуется не только распараллеливанием вычислений, но и присущей для интеллектуальных САПР возможностью эффективного взаимодействия ПК и ФОП. В частности [63],подчеркивается, что решение задач посредством аппаратно-программного обеспечения и при эффективном их взаимодействии осуществляется в 2.....І0, а для некоторых задач в 20 раз быстрее, чем с помощью программного обеспечения. Поэтому, аппаратно-программная реализация интеллектуальной системы НОЙЄТ широко использоваться при проектировании средств вычислительной техники, технологических процессов и изделий различных отраслей промышленности. В процессе создания САПР СБИС разработаны и предлоаенк [513 новые средства математического, информационного и технического обеспечения, поддерккваюцие технологию процесса разработки СБИС. В настоящее время усилия разработчиков САШ4 сосредоточены преодоление "барьера размерности" возникаицн:: задач, особенно на этапах разработки топологии и изготовления Фотошаблонов- СБИС. Для СБИС, содержащих десятки миллионов транзисторов [56] размерность задач возрастает на порядок и более. Одним из этапов автоматизации проектирования и изготовления СБИС является синтез топологии и разработка оотоиаб-лонов. К синтезу топологии относятся такие задачи экспоненциального характера, как кодирование топологии, ее контроль и редактирование. На рисунке 4.4 приводится блок-схема синтеза топологии. Допустим, электрическая схема проектируемого устройства представлена в виде графа ь= Х,1Ь,где . Х=СХ/ -,ХС ,...,Хп)-ынояество вершин, U={U/,U ,...;Un}-MHoiecT3o ребер графа (рис. 4.9) и граф топологической схемы G= Y,U , где У= {Y/.Yj,.... Уп)-мнокество вершин. U=(U/,UA иш)-мнонество ребер графа. Тогда, этап синтеза топологии можно представить как задачу поиска отображения: На выполнение отображения (4.5) с учетом несовершенства технологического оборудования и математических моделей, применяемых при разработке, накладываются конструкторские и технологические ограничения. К первым относятся ограничении типа: множество наборов для реализации элементов областей; множество наборов для зазоров между этими областями; мнонест-во наборов допустимых границ этих областей; мнозество набороь перестановок элементов х Х. Ко вторым относятся ограничения гарантирующие корректность проведения операций изготовления проектируемого изделия: допустимые размеры областей,углы нед-ду линиями, допустимые расстояния и т.д. Отклонение от кокс-трукторско-технологических ограничений приводит к несоответствию топологии СБИС принципиальной электрической схеме, точнее ошибке в топологии проектируемого устройства. Для выявления такого рода ошибок используется задача диагностического контроля проекта СБИС Г12,16,41,43,46,49,56,57,70]. Диагностический контроль топологии СБИС условно можно разделить на следующие этапы:. 1. проверка расположения области вскрытий относительно . слоя металлизации; 2. формирование списка соединений вскрытий по анализу топологии схемы; 3. распознавание компонентов сложной структуры; 4. проверка соответствия топологии электрической схемы. Для эффективного решения этих задач, необходимо при держиваться следующих условий: -каждое вскрытие должно покрываться некоторой областью металлизации; -каждой области металлизации должна соответствовать определенная цепь вскрытий, покрытых.этой областью; - каждое вскрытие должно покрываться областью меттали зации в соответствии с принципиальной электрической схемой. Невыполнение одного из указанных условий приводит к несоответствию топологии СБИС электрической схеме и может быть обнаружена наличием следующих причин: - вскрытие не покрывается ни одной областью металлизации; - вскрытие частично покрывается областью металлизации; - вскрытие не содержится в соответствующей ему области металлизации; - соединения между некоторыми вскрытиями отсутствуют; - обрыв в области металлизации и др. В Г46,57Т предлагаются методы и алгоритмы поиска указанных ошибок и приводится блок-схема диагностического контроля топологии БИС на рис.4.6. По заданной электрической схеме устройства проектируется ее топология, т.е. производится компоновка, размещение элементов и трассировка межзлементных связей. Причем проектируемая топология представляется в форме послойных чертежей геометрии схемы, т.е. в интеллектуальных САПР данная форма характеризуется как алфавит компилятора и таблиц координат условных точек контуров.
