Модели и алгоритмы автоматизированной декомпозиции схем ЭВМ

• Автор: Попов, Алексей Юрьевич
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 176 с. : ил

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ.

1. ОПРЕДЕЛЕНИЕ ОБЪЕКТА ИССЛЕДОВАНИЯ И ПОСТАНОВКА ЗАДАЧИ

1.1. Анализ задачи разрезания и выбор математических моделей.

1.2. Формальная постановка задачи разрезания

1.3. Задача выбора структур данных для реализации алгоритмов декомпозиции схем

1.4. Анализ методов решения задачи разрезания.

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

2.1. Анализ структур данных и операций над ними.

2.2. Исследование операций над линейными структурами данных.

2.3. Исследование операций над древовидными и сетевыми структурами

2.4. Классификация базовых структур данных и матрица сложностей базовых операций.
2.5. Формальная постановка и методика решения задачи выбора структур данных.
2.6. Локальнооптимальный алгоритм выбора структур данных.
2.7. Выбор структур данных для последовательного алгоритма разрезания гиперграфа.
3. АЛГОРИТМЫ ДЕКОМПОЗИЦИИ СХЕМ ПО МЕТОДУ ДВОИЧНОЙ СВЕРТКИ.
3.1. Математическая модель процесса композиции и особенности алгоритмов
свертки.
3.2. Алгоритмы свертки без учета связности.
3.3. Алгоритмы свертки с учетом связности
3.4. Сравнительный анализ полученных результатов
3.5. Выбор структур данных
4. АЛГОРИТМ ДИХОТОМИЧЕСКОГО РАЗРЕЗАНИЯ ГИПЕРГРАФА ПО МЕТОДУ ВЕТВЕЙ И ГРАНИЦ
4.1. Математическая модель процесса дихотомического разрезания
гиперграфа по методу ветвей и границ.
4.2. Доказательство применимости метода ветвей и границ для декомпозиции
4.3. Схемы реализации метода ветвей и границ
4.4. Способы формирования дерева решений
4.5. Способы кодирования вершин дерева решений и оценка сверху их
емкостной сложности
4.6. Кодирование огибающей цепи.
4.7. Алгоритм дихотомического разрезания гиперграфа по методу ветвей и
границ.
4.8. Выбор структур данных и определение вычислительной сложности
алгоритма
5. ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ.
5.1. Система автоматизированной декомпозиции схем
5.2. Экспериментальное исследование вычислительной сложности алгоритмов двоичной свертки
5.3. Исследование возможности применения алгоритма дихотомического разрезания гиперграфа по методу ветвей и границ и двоичной свертки для декомпозиции схем.
5.4. Экспериментальные исследования качественных характеристик алгоритмов
ЗАКЛЮЧЕНИЕ..
СПИСОК ЛИТЕРАТУРЫ


Разрезание является задачей структурно синтеза, исходными данными для которой служит схема электрическая функциональная, отображающая состав и параметры связи функционально закончсных узлов схемы без указания их компановочных параметров. При автоматизированном решении данной задачи должен выполнятся формальный переход от исходной модели к модели результата. Следовательно, для ее автоматизации необходимо определить данные модели и формальные методы их преобразования. В качестве модели исходного описания объектов структурного синтеза широко испольуется такая математическая абстракция как граф [3,,,,,,,]. Она позволяет отобразить в модели всю необходимую информацию о схеме [,]: связность элементов схемы с точностью до вывода с учетом направления распространения сигнала и фактора неизвестности соединений в пределах одной цепи, порядок расположения выводов, возможность прокладки соединений между выводами и под элементами, метрические параметры элементов. Для различных подзадач схемно-топологического проектирования часть информации несущественна, что позволяет в каждом случае выбрать наиболее компактную модель. В [] описана процедура синтеза графовой модели объекта и доказательства ее правильности. Для различных подзадач таковой могут являться: неориентированный или ориентированный мультиграф, гиперграф или ультраграф [,,,,]. Качество решения задачи компоновки сильно влияет на результаты схемно-топологического проектирования. При постановке данной задачи в виде компоновки схем в конструктивно унифицированные модули, т. Ог~? Рис. В [,] моделью схемы является неориентированный мультиграф (Рис. Каждая цепь, связывающая элементы схемы, представляется полным подграфом на соответствующих вершинах графа. Т.к. Для адекватного представления схемы с точки зрения точности определения связности ее частей необходимо отобразить в математической модели отношения, соответствующие принадле лености элемента цепи. Адекватная модель схемы должна отображать тройку {Э,Ц,Пр}, где Э -множество элементов схемы, Ц - множество цепей, Пр - отношение принадлежности элемента цепи. Подобная модель представления схемы -гиперграф {Х,и,Г} (Рис. Х={х1,. Г - отношение инцидентности множеств X и и: ГХ={ГхД=1,. Ги={ГиД=1,. Отношение инцидентности (Г) обладает свойством симметричности - информация о направлении распространения сигнала не существенна. Таким образом, адекватной и наименее избыточной моделью схемы при решении задачи разрезания является гиперграф. Для построения модели схемы в виде гиперграфа необходимо провести преобразование вида {Э,Ц,Пр}<->{Х,и,Г}: множество элементов схемы ставится во взаимнооднозначное соответствие вершинам гиперграфа (Э<->Х), множество цепей ставится во взаимно-однозначное соответствие ребрам гиперграфа (Ц<->и), а принадлежность элементов цепи задается отношением инцидентности (Пр<->Г). Гц: щ -> Ги,= Xj для '^=. Х] с: X. Такте образом, схему можно считать полностью заданной, если мы имеем множества : X, и, а также Гх* для всех х*еХ , или Пи для всех цеи. Схема считается заданной, если мы знаем множество вершин X, множество ребер и, а также, для каждого х* - Гх]у или для каждого ц - Ги^ По известным Х,и, ГХ{ можно определить Гщ9 ГГх*, а также по известным Х,и, Гиу мы можем получить Гх*, ГГх1. X | - количество вершин (элементов в схеме). А - среднее количество вершин (элементов), содержащихся в ребре (цепи). Параметр р может принимать значение от 1 до (п-1) и характеризует "связность" в схеме, т. С учетом (1. А, из которых базовыми и привычными для конструктора являются параметры п,р,ш. Нетрудно показать, что для реальных схем А<5, при получении оценок вычислительной сложности можно считать р=р. Таким образом из основных характеристик схемы будем использовать параметры п,дш. В соответствие с функционально-узловым подходом к проектированию, ЭВМ состоит из блоков разной степени сложности, образующих многоуровневую иерархическую структуру, которую представляют в виде дерева функционального вхождения []. Конструктивно деление ЭВМ также имеет иерархическую древовидную структуру, которая, однако, может отличаться от функциональной. Размеры конструктивных модулей могут быть заранее известны. Показатели п,ш,ри А связаны следующей формулой: шА = пр. Р = [? ГГх,].