Разработка и исследование алгоритмов компоновки конструктивных узлов цифровой вычислительной аппаратуры.

• Автор: Егоров, А. Г.
• Шифр специальности: 05.00.00
• Научная степень: Кандидатская
• Год защиты: 1975
• Место защиты: Рязань
• Количество страниц: 212 с.

1. Модели и критерии, используемые при решении задач компоновки конструктивных узлов

1.1. Влияние интегральных схем на компоновку конструктивных узлов

1.2. О критериях компоновки конструктивных узлов

1.3. Обзор методов решения задачи компоновки

1.4. Выбор моделей и критериев оптимизации

Выводы

2. Покрытие функционально-логических схем несвязными модулями из заданного набора

2.1. Постановка задачи

2.2. Точный метод решения задачи покрытия

2.3. Определение минимального числа интегральных модулей

2.4. Приближенные способы покрытия

Выводы
3. Методы формирования набора типовых элементов
замены для нерегулярных схем
3.1. 0 .двух подходах к задаче формирования
типовых элементов замены
3.2. Приближенные алгоритмы компоновки
3.3. Разбиение схемы на типовые элементы замены
с введением избыточных элементов

3.4. Алгоритм разбиения схем из однофункциональных элементов с введением избыточности
Выводы
4. Методы компоновки регулярных схем
4.1. Выбор оптимальной совокупности функциональных узлов
4.2. Компоновка схем по обобщенному критерию. . . .125 Выводы
5. Программная реализация алгоритмов компоновки
и результаты их исследования
5.1. Способ представления информация о схеме
5.2. Основные положения программы покрытия
5.3. Программа компоновки нерегулярных схем
5.4. Программная реализация метода динамического программирования
5.5. Программа выбора оптимальной совокупности функциональных узлов
Выводы
Заключение
Литература
Приложения

Одной из особенностей современного этапа научно-технической революции является повсеместное внедрение средств вычислительной техники и , особенно, цифровых электронно-вычислительных машин (ЦВМ). Наряду с постоянным расширением круга задач, решаемых с помощью ЦВМ, непрерывно возрастает и их сложность, что приводит к необходимости создания все более мощных и надежных вычислительных комплексов в.кратчайшие сроки. Последние достижения микроэлектроники, позволяющие осуществить целый ряд сложных технических проектов, вместе с тем ставят достаточно много проблем, решение которых весьма затруднительно без широкого использования автоматизированных систем проектирования (АСП), охватывающих различные этапы разработки и изготовления ЦВМ и , в частности, наиболее трудоемкий этап технического проектирования. Применение АСП позволяет сократить сроки и стоимость проектирования, увеличить производительность труда, уменьшить затраты, связанные с исправлением неизбежно возникающих в процессе проектирования ошибок^ в некоторых случаях улучшить качество создаваемой аппаратуры.
До настоящего времени наибольшее внимание в рамках АСП уделялось двум задачам технического проектирования - размещению элементов, относящихся к младшим уровням конструктивной иерархии в

элементах старших уровней, и трассировке соединений между конструктивными элементами [32, 42 , 64] . Однако , с переходом к интегральным схемам (Ж) на одно из первых мест по важности решения выдвинулась задача компоновки, под которой понимается определение компонентов конструктивных узлов каждого уровня иерархии. Особенно остро эта задача стоит при проектировании таких конструктив,
ределяицему типы вершин 1/^е V подграфа & ^ .В обозначениях (2.2.3) + (2.2.5) область решения рассматриваемой задачи согласно (2.1.1) и требования однозначности покрытия определяется как
Таким образом задача разбиения множества вершин V гипергра-фа на подмножества ^' формулируется как задача
отыскания матрицы = II 11 , минимизирующей функционал
(2.2.2) и удовлетворяющей ограничениям (2.2.6), (2.2.V). Данная задача является существенно нелинейной задачей математического программирования, для которой в настоящее время не известны какие-либо точные алгоритмы решения, отличные от полного перебора. Тем не менее, принципиально возможно получение точного решения методом динамического программирования, посредством сведения её к модели многоэтапного процесса оптимизации [25,26}
2.2.2, При выводе основных соотношений рассматриваемого метода предположим, что каждый модуль набора содержит однотипные элементы, а каждой вершине гиперграфа поставлен в соответствие один и тот же признак, то есть

(2.2.6)
(2.2.7)