Вопросы разработки алгоритмического и программного обеспечения, предназначенного для решения одного класса задач конструкторского проектирования цифровой аппаратуры

• Автор: Тимофеева, Надежда Константиновна
• Шифр специальности: 01.01.10
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Киев
• Количество страниц: 121 c. : ил

Глава I. Обзор основных задач конструкторского проектирования ЭВМ

§ I. Некоторые оптимизационные задачи комбинаторного типа, возникающие на этапе конструкторского

проектирования и методы их решения

§ 2. Основные подходы, применяемые при решении оптимизационных задач проектирования
§ 3. Формальная постановка задачи компоновки, размещения, трассировки и распределения инвариантных выводов

Глава II, Математические модели и алгоритмы решения задач

проектирования узлов ЗВМ

.§ I. Компоновка базовых элементов в модули

§ 2. Размещение компонентов на монтажном поле

§ 3. Распределение внешних выводов узлов ЗВМ

Глава III. Формирование графической информации при проектировании печатных плат

§ I. Принципы подготовки управляющих программ для
автоматизации изготовления узлов ЗВМ
§ 2. Математическая модель'и алгоритм решения
одной задачи типа задачи коммивояжера
Глава IV. Система автоматизированного проектирования цифровой аппаратуры ДИСИО
§ I. Назначение и структура системы
§ 2. Принципы функционирования системы ДИСИО
§ 3. Входной язык системы ДИСИО

Заключение
Литература
Приложение
Широкое внедрение во многие сферы человеческой деятельности различных средств вычислительной техники потребовало ускоренных разработок вычислительных машин и систем, сложность которых непрерывно возрастает. Проектирование.ЭВМ, во время которого перерабатываются огромные массивы информации, немыслимо без автоматизации разработок ЭВМ.
Согласно [I] , проектирование ЭВМ разделяют на этапы: системное проектирование, проектирование математического обеспечения, логическое, конструкторское проектирование, проектирование электронных схем.
В настоящее время в разных организациях реализованы и используются ряд систем и подсистем автоматизированного проектирования (САПР), имеющие различное целевое назначение (см. например [1-27]). Большой вклад в развитие автоматизации конструкторского проектирования внесли различные коллективы под руководством Абрайтиса Л.Б., Глушкова В.М., Ландау И.Я., Майорова С,А., Матюхина Н.Я.,
Пескова М.И., Петренко А.И., Рябова Г.Г., Рябова Л.П., Селютина В.А. и ряца других советских ученых,
В диссертационной работе рассматриваются вопросы, связанные с автоматизацией конструкторского проектирования узлов ЭВМ. На конструкторском этапе проектирования узлов ЭВМ предполагается автоматизация решения следующих задач:
обработка входной информации для выбранной САПР и преобразование ее во внутренний формат данных;
решение комбинаторных задач оптимизации, возникающих на этом этапе, таких как:

задачи X — 0 ), / - вычисляемый на каждом шаге решения задачи
вес, который соответствует весу Ц$(£;) некоторой установочной пози-
/> Г
ции из набора позиций = 4/г 1 и находится в пределах
йь пгах (где)
В нашем случае выбор оптимального решения производим по критериям (2,6)-(2.7). Для их построения используем оценки (2.8)—(2.11). Разбиение множества X на блоки производим алгоритмом, предложенным автором в работе ^100 ]
На основании решения задачи (2.6)—(2.7), (2.12)—(2.15) формируем задачу размещения следующего типа: найти такое размещение полученных блоков У/ У& в указанных позициях
для которого достигался бы

тсгъ£ (2.17-)
еде. ас ё=
где множество всевозможных перестановок чисел ВпФ,4...,пЪ
5? = {сО=(с$1 сО иРт)и^«£■,а$е.бт (^
и каждая перестановка сд — (^/к ) ^ 52 определяет вариант решения задачи размещения по следующему правилу: блок разбиения , помещается в позицию 4^- > а позиции
>'"* (дуг, , если } остаются свободными; В(^) -
оценка длины соединений, принадлежащих е -и цепи электрической схемы при варианте размещения , ^- число всех электрических цепей схемы.
Для решения задачи размещения блоков разбиения с равным весом можно использовать алгоритм метода вектора спада [49]
метод выбран в связи с тем, что он позволяет получить локальный экстремум задачи за приемлемое время работы