Исследование и разработка параллельных алгоритмов трассировки БИС

• Автор: Ховансков, Сергей Андреевич
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Таганрог
• Количество страниц: 194 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
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Л.. СТРУКТУРА И ОБЩИЕ ПРИНЦИПЫ РАБОТЫ МВС
4.2. ОРГАНИЗАЦИЯ ПАРАЛЛЕЛЬНОГО ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА И
СИНТЕЗ БАЗОВОГО НАБОРА МАКРООПЕРАЦИЙ ЗАДАЧИ ТРАССИРОВКИ
4.3. ОЦЕНКА ХАРАКТЕРИСТИК ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА ТРАССИРОВКИ
4.4. АППАРАТНО - ПРОГРАММНЫЙ КОМПЛЕКС ДЛЯ САПР СБИС
4.5 ВЫВОДЫ
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

ВВЕДЕНИЕ
С момента появления первой простейшей электронно вычислительной аппаратуры (ЭВА) прошло немало времени. Использование и внедрение ЭВА стало одним из показателей научно-технического прогресса. Прогресс требует своевременного повышения быстродействия, качества, эффективности применяемых ЭВА, что ведет к постоянному ее усложнению. Препятствием повышения качества ЭВА и сокращением сроков ее создания, в свое время, стали несоответствия между возрастающей сложностью микроминиатюризации ЭВА и устаревшими методами и средствами ее конструирования [1-31]. Для разрешения этого несоответствия в 70-х - начале 80-х годов была разработана и внедрена новая технология проектирования, связанная с использованием и применением систем автоматизированного проектирования (САПР) [1-3,5-21,24-54].
Автоматизация процесса проектирования ЭВА и разработка САПР позволили не только сократить сроки создания аппаратуры и облегчить условия труда, но и повысить качество производимой продукции. Это стало возможным потому, что при производстве изделий для управления станками, автоматами и поточными линиями используется информация, разработанная с помощью САПР и записанная на ЭВМ. Благодаря этому время проектирования сократилось, а ЭВА усложнялась и наметилась тенденция к очередному увеличению сроков разработки изделий, даже с использованием САПР. В тоже время стала заметна тенденция к уменьшению средних сроков эксплуатации ЭВА, которая связана с ускорением прогресса в микроэлектронике и, соответственно с быстрым моральным старением эксплуатируемой

P(ltJ)eM .Множество D соседних дискретов для d(xry) составит :
Р З'Р
D ={й(х+1,у), d(x,y+1), d(x-Uy), d(x,y-1 )}.

Таким образом, между элементами М и D существует взаимо-
tj ху
однозначное соответствие.
1.2.2. ОСНОВНЫЕ ЭТАПЫ АЛГОРИТМА ПОСТРОЕНИЯ СВЯЗЫВАЮЩИХ ДЕРЕВЬЕВ
НА МВС
Построение ортогональных связывающих деревьев на модели дискретного рабочего поля заключается в присвоении метки совокупности УН (рисЛ.10,1.II) [74,77,78].
Обозначим А - множество всех цепей А=(А1,А2,,Аг
Все контакты цепи разбиваются на пары таким образом, чтобы при соединении этих пар контактов связями образовывалось дерево, включающее в себя все контакты.
Определим количество связываемых пар контактов S в множестве