Диссертация на тему "Разработка и исследование композитных алгоритмов компоновки блоков ЭВА", скачать бесплатно автореферат по специальности 05.13.12 - Системы автоматизации проектирования (по отраслям)

Содержание
ВВЕДЕНИЕ

1. АНАЛИЗ И СОСТОЯНИЕ ПРОБЛЕМЫ КОМПОНОВКИ БЛОКОВ ЭВА

1.1 Коммутационные модели блоков ЭВА

1.2 Постановка задачи компоновки

1.3 Анализ существующих алгоритмов разбиения графов и гиперграфов на части

1.4 Выводы

2. РАЗРАБОТКА ПОИСКОВЫХ МЕТОДОВ КОМПОНОВКИ БЛОКОВ ЭВА.

2.1 Использование экспертных систем при построении

моделей компоновки блоков.

2.2 Разработка архитектуры, стратегии и принципов компоновки блоков

2.3 Построение модифицированных генетических операторов.
2.4 Выводы.
3. РАЗРАБОТКА КОМПОЗИТНЫХ АЛГОРИТМОВ КОМПОНОВКИ БЛОКОВ ЭВА
3.1. Разработка алгоритмов компоновки на основе
раскраски графов.
3.2. Построение параллельнопоследовательных алгоритмов компоновки на основе определение независимых и доминирующих
подмножеств
3.3. Разработка композитного алгоритма компоновки на основе сжатия и построения паросочетаний графа
3.4. Выводы
4. АНАЛИЗ ЭКСПЕРИМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ РАЗРАБОТАННЫХ АЛГОРИТМОВ.
4.1. Краткие сведения об инструментальной среде компоновки
блоков ЭВА.
4.2. Цель и средства экспериментальных исследований
4.3. Результаты экспериментальных исследований.
4.4. Выводы
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Компоновкой коммутационной схемы на конструктивно законченные части называется процесс распределения элементов низшего конструктивного уровня в высший в соответствии с заданными критериями. Такими критериями могут быть: число конструктивно законченных блоков, длина задержки сигнала, число соединений между конструктивными блоками, количество связей внутри блоков, функциональная полнота блоков. Наиболее распространенным критерием компоновки является число внешних связей. Оптимизация этого критерия обеспечивает упрощение конструкции, повышение надежности и т. В связи с этим разработка, анализ и исследование методов компоновки коммутационных схем проводится на основе оптимизации критерия числа внешних связей [6-, -,]. Задачи конструкторского проектирования принадлежат к классу комбинаторных оптимизационных задач. Реализация этих задач на ЭВМ зависит от выбираемой формальной математической модели коммутационной схемы. Различные математические модели с различной точностью описывают одни и те же параметры устройства при решении каждой конкретной задачи конструкторского проектирования. В этой связи на различных этапах конструкторского проектирования, в зависимости от конкретных оптимизируемых критериев, используются различные коммутационные модели. Оптимизационные задачи конструкторского проектирования, как правило, формулируют на основе теории графов, гиперграфов и их матричных и списковых эквивалентов [6-, -,]. В этой связи задача компоновки блоков в конструктивно законченные части сводится к задаче разбиения графа или гиперграфа на части. Рассмотрим математическую модель коммутационной схемы М1. Она представляется неориентированным графом в = (X, и), здесь компоненты схемы представляются вершинами Т = {, , . К = {к^ к2,. В графе в каждая цепь а представлена своим полным подграфом, включающим все вершины, инцидентные данной цепи, а вес ту ребра (1, ]) е и зависит от числа связей между компонентами схемы и]. Например, на рис. ЭВА. Здесь 1-5 блоки; еге5 цепи (внешние связи); Кь к2 - внешние контакты цепей схемы. Блоком Ф будем называть совокупность компонентов 1,2,. С. Тогда математической моделью блока Ф является совокупность математических моделей компонентов 1,2,. Б блока, модели пространства Ъ и алгоритма Т отображения компонентов и соединений в пространство Ъ, т. Ф=(1,2,. Б; Ъ С; Т). Тогда коммутационная схема Б задается в общем случае набором непересекающихся деревьев, соединяющих компоненты 1,2,. Пространство Ъ может быть либо абстрактным математическим, либо метрическим пространством []. В задачах компоновки обычно рассматривается абстрактное математическое пространство. Алгоритм Т задает отображение компонентов 1,2,. На рис. Здесь каждая цепь ере5 представлена полным подграфом. Например, вершины графа 1,2 и 5 соединены ребрами е и образуют цикл (1 е! Вершины 2,3 соединены ребром е2 и образуют путь (2 е2 3). Вместо индекса е1 можно ставить значение веса ребра. Кроме того, два ребра, соединяющие одни и те же вершины, могут быть представлены одним ребром с общим весом. Например, между вершинами 4 и 3 вместо двух ребер е5, ез можно провести одно ребро с весом е5 У е3. Такое представление коммутационной схемы может привести к искажениям при решении задачи компоновки, т. Данную модификацию модели будем считать жесткой и приближенной. Она используется на этапе предварительного разбиения графов. Разновидностью модели М1 является представление коммутационной схемы ее графом, в котором с целью устранения полных подграфов цепей переходят к представлению цепей ак (к = 1,2,. Б) их деревьями Тк (к = 1,2, . О). Сложность задачи в данном случае заключается в обосновании объективного критерия выбора совокупности деревьев, а также алгоритмических трудностях, связанных с определением набора этих деревьев. Даже для сравнительно небольших коммутационных схем число Р огромно и исключает возможность построения модели путем прямого перебора (при наличии критерия выбора). В работе [] предлагается из множества 0 конфигураций деревьев выбирать те, которые в совокупности дают граф с минимальным суммарным числом ребер. На рис. Рис. Рис. Рис. Граф схемы (рис.

Название работы	Автор	Дата защиты
Разработка и исследование распределенных Web-ориентированных архитектур САПР	Адамов, Абзетдин Загирович	2003
Модели и методы анализа проектных решений цифровой электронной техники на основе сетей Петри	Веселов, Алексей Аркадьевич	2006
Разработка подсистемы САПР тестопригодного проектирования СБИС и МЭА	Рыбаков, Василий Владимирович	1998

Электронная библиотека диссертаций

Разработка и исследование композитных алгоритмов компоновки блоков ЭВА