автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Исследование и разработка параллельных алгоритмов трассировки БИС

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ОД

- 1 5: К ГШ

На правах рукописи

Ховансков Сергей Андреевич

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

Специальность 05.13.12 - системы автоматизации проектирования

Автореферат диссертации на соискание ученой степени кандидата технических наук

Таганрог - 1998г.

Работа выполнена в Таганрогском государственном радиотехническом университете

Научный руководитель - доктор технических наук,

профессор Калашников В.А.

Официальные оппоненты:

д.т.н., профессор Чернышев Юрий Олегович

к.т.н., доцент Лебедев Борис Константинович

Ведущая организация: Научно-исследовательский институт связи (г.Таганрог)

Защита состоится "_"_ 1998г. в_ часов на

заседании диссертационного совета Д063.13.02 по защите диссертации при Таганрогском государственном радиотехническом университете по адресу: 347928, г.Таганрог, пер. Некрасовский, 44, ауд. Д - 406.

С диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан "_"_199_г.

Ученый секретарь диссертационного совета, кандидат технических наук, доцент

А.Н. Целых

Актуальность работы. Проектирование БИС - сложный, занимающий много времени процесс; сроки разработки

электронного устройства,_____содержащего БИС в качестве

компонентов, могут превышать период, в течение которого изделие пользуется спросом и затраты на проектирование могут не окупиться до того, как прибор устареет. Учитывая эти обстоятельства, разработка СБИС должна осуществляться в кратчайшие сроки, с наименьшими затратами; устройства, выполненные по этим проектам, должны обладать заданными функциональными свойствами и отвечать поставленным требованиям. Проектирование БИС высокой степени интеграции требует создания эффективных систем автоматизированного проектирования (САПР) для организации сквозного цикла проектирования БИС за приемлемое с точки зрения пользователя время.

Удовлетворить в полной мере этим требованиям могут только вычислительные системы, имеющие структуру отличную от классической. К такого рода системам относятся параллельные вычислительные системы. Ясно, что использование этих систем в комплексе технических средств (КТС) САПР должно расширить возможности системы. При этом, положительный эффект при решении задач автоматизированного проектирования БИС на КТС, в состав которых входят параллельные вычислительные системы (ПВС), может быть достигнут, в основном, за счет их распараллеливания.

Цель работы и задачи исследования. Целью диссертационной работы является исследование и разработка отдельных компонент этапа проектирования БИС - построение связывающих деревьев, расслоение, синтез топологии; разработка алгоритмического и прикладного программного обеспечений систем

автоматизированного проектирования на базе параллельных вычислительных систем, в основу построения которых положены созданные или создающиеся высокопроизводительные многопроцессорные вычислительные комплексы.

Для достижения поставленной цели были решены следующие задачи:

исследование существующих алгоритмов построения связывающих деревьев, для оценки ускорения их выполнения на ПВС, на основе выделения в них максимальных параллельных процессов;

разработка нового алгоритма параллельного построения ортогональных связывающих деревьев и оценка ускорения его

выполнения на ПВС;

- исследование существующих алгоритмов распределения фрагментов цепей по слоям для оценки ускорения их выполнения на ПВС на основе выделения в них максимальных параллельных процессов;

- разработка алгоритма определения клик графа для выполнения на ПВС и оценка эффективности его выполнения;

- исследование существующих алгоритмов трассировки соединений для оценки ускорения их выполнения на ПВС на основе выделения в них максимальных параллельных процессов;

- разработка нового алгоритма параллельной трассировки соединений и оценка ускорения его выполнения на ПВС;

- разработка организации вычислительного процесса и синтез базового набора макроопераций, необходимых для реализации задачи параллельной трассировки на ПВС;

- разработка аппаратно-программного комплекса, для работы САПР СБИС, на основе разработанных алгоритмов и многопроцессорной вычислительной системы со структурно процедурной организацией вычислений (МВС СПРВ), в качестве аппаратного ускорителя выполнения задач САПР;

- исследование параметров вычислительного процесса при реализации задачи параллельной трассировки на МВС СПРВ: ускорение, доли накладного времени, коэффициента использования оборудования и коэффициента качества программирования.

Методика исследований базируется на теории множеств, теории графов, теории оптимизации, теории алгоритмов, теории вычислительных систем и принципах параллельной обработки информации с учетом специфики алгоритмов и процессов, порождаемых при решении задач САПР.

Научная новизна диссертационной работы заключается в следующем:

разработан новый алгоритм параллельного построения ортогональных связывающих деревьев;

- разработаны новые алгоритмы для узловых процессоров процессорного поля ПВС, позволяющие организовать процесс одновременного построения всех ортогональных связывающих деревьев, получена оценка ускорения выполнения построения ортогонального связывающего дерева на ПВС;

- разработаны алгоритмы для узловых процессоров, позволяющие организовать эффективный процесс выделения клик графа на ПВС, процессоры которой соединены по полному графу, получена оценка ускорения выполнения выделения на ПВС;

-разработаны алгоритмы для узловых процессоров, позволяющие

организовать процесс одновременного построения всех трасс на ПВС, процессорное поле которой имеет структуру типа "решетки", получена оценка ускорения выполнения алгоритма на ПВС;----------------------

получены оценки ускорения выполнения на ПВС ряда существующих. алгоритмов: построения ортогональных связывающих деревьев, разнесения связей по слоям, прокладки трасс, на основе исследования вариантов их вычислительных процессов;

- разработаны принципы организации вычислительного процесса и синтезирован базовый набор макроопераций для выполнения параллельной трассировки на МВС СПРВ.

Практическая ценность работы. На основе теоретических исследований предложена методика, позволяющая производить оценки эффективности выполнения алгоритмов проектирования на ПВС. Создан ряд алгоритмов этапа трассировки. На их основе разработаны алгоритмы для узловых процессоров процессорного поля ПВС, позволяющие организовать вычислительные процессы: одновременного построения всех связей деревьев, разнесения фрагментов цепей по слоям с минимальными временными затратами, прокладки одновременно всех трасс на коммутационном поле БИС. Адаптация алгоритма параллельной трассировки в условиях МВС СПРВ позволила выявить закономерности и ограничения, налагаемые на алгоритмы при проектировании на многопроцессорных системах.

Апробация основных результатов диссертационной работы докладывались и обсуждались на:

- всероссийской XXXIX научно-технической конференции, ТРТУ, г.Таганрог, 1993г.;

- всероссийской научно-технической конференции "Актуальные проблемы твердотельной электроники и микроэлектроники", г. Таганрог, 1994г.;

- всероссийской научно-технической конференции "Интеллектуальные САПР-96", г. Геленджик, 1997г.;

научно-технических и научно-методических конференциях профессорско-преподовательского состава, аспирантов и сотрудников Таганрогского государственного радиотехнического университета в 1986-1997 г.

Публикации. Материалы, содержащие основные научные результаты, опубликованы в 10 печатных работах, кроме того, во ВНТИЦ зарегистрировано 5 отчетов по хоздоговорным и научно -исследовательским работам в области автоматизации и

проектирования РЭА и БИС, выполненных при непосредственном участии автора.

Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка литературы и приложения. Работа содержит 190 стр. машинописного текста, включая 37 стр. рисунков и таблиц, список литературы из 90 наименований, 3 стр. актов об использовании.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертационной работы, определены пути решения задачи уменьшения времени проектирования СБИС поставлена цель работы, дано общее описание выполненной работы.

Первый раздел посвящен одной из задач трассировки -разработке алгоритма построения связывающих деревьев на ПВС. Производится анализ способности распараллеливания на ПВС следующих алгоритмов построения связывающих деревьев: определения Гамильтонова пути в графе, на основе построения кратчайшего дерева Прима, построения минимального ортогонального связывающего дерева Штейнера, на основе волнового алгоритма. В результате анализа выделены максимальные по объему независимые вычислительные процессы, получены оценки ускорений выполнения этих алгоритмов на ПВС. Из анализа сделан вывод, что оценка степени параллелизма алгоритмов и время его выполнения на ПВС зависит от максимального количества вычислительных процессов, которые возможно выполнять одновременно. Наименьшее время выполнения имеют алгоритмы, при реализации которых на ПВС возможно одно- временное построение всех связей.

Разработан алгоритм параллельного построения ортогональных связывающих деревьев.

Алгоритм ориентирован на матричную МВС, процессорное поле (ПП) которой имеет структуру типа "решетки", образованную узловыми процессорами (УП) и связями между ними. Дискретному рабочему полю ставятся в соответствие УП ПП P(J,j), которым присваиваются координаты дискретов и их состояния S,j. Построение ортогональных связывающих деревьев на модели дискретного рабочего поля заключается в присвоении метки совокупности УП. Из пары соединяемых контактов один

выбирается в качестве "источника" к +, второй - в качестве "цели" к *, соответствующие им УП помечаются аналогично. Работа алгоритма состоит в передаче метки из "источника" по направлению к "цели". Поиск направления передачи задается последовательностью приоритетных направлений.

Алгоритм работы всех УП един и состоит из 4-х этапов.

На первом этапе производится обмен информацией между соседними процессорами, содержащей сведения об их состояниях.

На втором этапе производится анализ информации, полученной на первом этапе, с целью принятия решения о выборе соседнего процессора для передачи ему метки, проверка окончания процесса построения связи, разрешения тупиковых и конфликтных ситуаций (Алгоритм 1).

На третьем этапе осуществляется обмен информацией по направлениям, выбранным на основе принятых решений.

На четвертом этапе происходит изменение состояний процессоров в соответствии с полученной информацией на предыдущем этапе.

Разработан алгоритм обмена информацией между процессорами (этапы 1 и 3), позволяющий передавать информацию для процесса построения всего за 8 машинных тактов обмена. В результате обмена, в каждом УП, находится информация о состояниях четырех соседних с ним. Приведем общий алгоритм процессора P(i,j) для построения связи / (этап 2):

п.1 .Если количество шагов, отработанных алгоритмом, больше единицы, то переход к п.4 , в противном случае переход к п.2 .

п.2 .Если не менее трех процессоров, входящих во множество M,j, имеют состояния равные единице и S,=0, то состояние P(i,j) изменить на £/,,=1. В противном случае переход к п.З

п.З .Если содержится контакт е К+, то определить вариант последовательности приоритетных направлений распространения связи /. Переход к п.4 .

п.4 .Если S,j =0, то переход к п.5 , в противном случае к п.7.

п.5 .Получена информация о связи /, если да, то переход к п.6 , в

противном случае к п. 13 .

п.6 .Выбор направления дальнейшего построения связи I, переход к п. 11 .

п.7 .Если Sij =1, то переход к п. 13, нет к п.8.

п.8 .Если получена информация о связи /, то переход к п.9 , в противном случае к п. 10 .

п.9 .Анализ координат источников и целей взаимодействующих связей и принятие решения, перейти к п. 11 .

п. 10 . Получена информация о запрещении построения связи / , перейти к п.11 .

п.11 . Сформировать информацию для третьего этапа, п. 12 . Выбрать номер такта Т0 для нужного направления приема или передачи, переход к п. 13 . п. 13 . Конец работы алгоритма.

К основному алгоритму разработан алгоритм принятия решений, позволяющий разрешать конфликтные ситуации (п. 10), и алгоритм взаимодействия связей друг с другом (п.9). Для более равномерного распределения связей по полю введен критерий минимума пересечений разных цепей.

Все узловые процессоры работают по единому алгоритму и независимо друг от друга. Это позволяет выполнить одновременное построение всех связей. Время построения на МВС всех связывающих деревьев определяется временем построения самой длинной связи на дискретном рабочем поле.

Произведена оценка ускорения выполнения разработанного алгоритма на МВС в зависимости от количества строящихся связей. Выражение для оценки ускорения будет иметь вид:

где щ - трудоёмкость построения связи на один дискрет с помощью

щ,и2 - трудоёмкость внутрипроцессорных операций и межпроцессорного обмена соответственно;

т 1 ,Х2 - время выполнения на МВС внутрипроцессорных операций и межпроцессорного обмена соответственно

- время выполнения обмена состоянием дискретов для ОВС; ^р - площадь кристалла; У - число элементов.

^*1ёУ*0.3*У*(ы0Т0 +4

ОВС;

Оценка выполнялась для БИС с увеличением V до

3000 при размерах кристалла 7*7мм и 5*5мм. При увеличенииГ ускорение возрастает по закону 0(У'/21о§7), а от размеров поля имеет линейную зависимость:

Во втором разделе рассматривается следующая важная задача трассировки - распределение фрагментов цепей по слоям, известной в теории графов как задача раскраски графа пересечений. Проведен анализ выполнения на ПВС алгоритмов разнесения фрагментов цепей по слоям. Исследована возможность их решения на ПВС. Выделены максимальные по объему независимые вычислительные процессы, получены оценки ускорений выполнения этих алгоритмов на ПВС. На основе анализа сделан вывод, что наиболее эффективно на ПВС решается вычислительная часть алгоритмов.

Предложен алгоритм распределения фрагментов цепей по коммутационным слоям БИС. В основу предлагаемого алгоритма положен алгоритм определения семейств клик графа, позволяющий выделять независимые множества графа без петель кратных ребер.

Алгоритм представляет собой следующий итерационный процесс. На каждой итерации определяется новая подстановка вершин исходного графа й на основе генерации п случайных чисел в диапазоне от 1 до п, модифицируется матрица смежности А = \а,)\ , задающая граф О, и осуществляется выделение

семейства клик, покрывающих все ребра графа С, с использованием алгоритма выделения независимых множеств графа. Изменение порядка следования вершин в модифицированной матрице смежности позволяет на каждой итерации доопределять новые клики графа. Для хранения информации о выделенных кликах графа в качестве структуры данных используется двоичное дерево, что позволяет исключить проверку повторности выделения одних и тех же клик графа.

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

Выполняемый на МВС алгоритм состоит из 3-х решающих

блоков.

Блок 1 состоит из одного УП и предназначен для генерации случайных чисел.

УП блока 2 предназначены для хранения матрицы

смежности А по с1 столбцов в каждом УП, поиска очередного непомеченного элемента матрицы А, выполнения логического умножения строк матрицы А и пометки ее элементов, вошедших в

выделенные клики. Блок 2 состоит из # = ^ УП.

Блок 3 предназначен для хранения информации о выделенных кликах графа, совмещения операций записи информации о клике и проверки повторности выделения одних и тех же полных подграфов. В каждом УП блока 3 хранится информация об к поддеревьях двоичного дерева О, корневыми вершинами которых являются вершины списка вершин самого верхнего уровня дерева

I). Таким образом блок 3 состоит из УП.

Все ПП МВС разделено для одновременного выполнения 3-х блоков алгоритма.

Проведено исследование зависимости эффективности выполнения алгоритма на МВС от количества УП, числа ребер графа, количества столбцов матрицы смежности, хранящихся в одном УП при различных значениях числа вершин графа.

Получено выражение для оценки эффективности / :

р-2-т-

^ 72-т-[1 + (ср-1)-0.02

(1+2-р)

+

к-р

, ч ( /Л \ 72 • т • [ 1 + (ф -1) ■ 0.02] 1 ь

где п - количество вершин графа V - объем памяти ОП УП Ъ - максимальная мощность клики графа О Р - количество итераций т - число ребер графа С

освещаются в четвертом разделе. Описывается назначение и некоторые Алгоритм, выполняемый на МВС, освобождает решение от таких недостатков как временные затраты, одновариантность: Он позволяет значительно сократить время решения задачи, тем самым дает возможность увеличить число итераций за приемлемое время и улучшить результат задачи. В конечном счете это влияет на процесс следующего этапа синтеза трасс, позволяет увеличить общее число разведенных трасс с наименьшим числом пересечений в слое.

Исследования подтверждают эффективность алгоритма определения семейства клик графа на ПВС и показывают, что разработанный алгоритм создает все необходимые условия для эффективной работы процесса трассировки.

В третьем разделе рассмотрена следующая задача трассировки - прокладка трасс на дискретном рабочем поле.

Приведен анализ синтеза трасс на рабочем поле: волнового, лучевого и канального алгоритмов трассировки. В них выделены максимальные по объему и независимые вычислительные процессы, выполняемые одновременно, дана оценка ускорения их выполнения на ПВС. На основе анализа сделан вывод, что наиболее эффективна трассировка на ПВС алгоритмами, время выполнения которых равно времени построения самой длинной трассы.

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

Выполнена оценка ускорения работы алгоритма при реализации на МВС, показывающая, что с увеличением количества элементов на кристалле до 1 ООО ускорение возрастает до 4000 раз. Ускорение оценивалось по сравнению с выполнением алгоритма на ОВС. Произведено сравнение времени выполнения трассировки разработанным алгоритмом, на МВС с количеством процессоров до 1000, и близким к нему лучевым, на ОВС. В результате сравнения сделан вывод, что выигрыш по времени появляется на МВС с количеством процессоров > 25.

Вопросы, связанные с реализацией задачи трассировки на

МВС со структурно-процедурной реализацией вычислений (СПРВ), особенности вычислительного процесса на МВС СПРВ. В частности описана логическая структура МВС СПРВ, которая содержит каналы распределенной памяти (РП), элементарные процессоры (ЭП) и коммутационную систему (КС). В МВС СПРВ элементарные процессоры соответствуют операциям в вершинах графа вычислительного алгоритма. Множество связей между вершинами реализуется пространственной коммутационной системой, а множество информационных потоков поддерживается множеством каналов распределенной оперативной памяти. Программа представляется последовательностью структурно реализуемых фрагментов вычислительного процесса.

Выделен основной принцип функционирования МВС СПРВ, предполагающий право пользователя на "доконструирования" требуемой архитектуры с помощью представляемых технических и программных средств. Рассмотрены способы организации вычислений и методы распараллеливания задач. Объяснены некоторые особенности прикладного программирования МВС СПРВ:

1) совокупность макроопераций, выполняемых в фиксированный момент времени называется кадром;

2) последовательность кадров определяет процедуру (задачу) выполняемую МВС СПРВ.

Приведено описание организации параллельного вычислительного процесса. Разработаны и приведены 10 макроопераций, объединенных в 4 кадра, реализующих процесс параллельной трассировки на МВС СПРВ. Для каждой макрооперации составлена ее граф-схема. Рассчитаны характеристики вычислительного процесса. В соответствии с граф схемами макроопераций были определены сложность (количество ЭП) и операционные задержки каждой макрооперации. В соответствии со структурными схемами кадров были определены операционные задержки, количество и глубина каналов памяти по записи-считыванию. Время однократного выполнения всех кадров для задачи трассировки на МВС:

I 10 ^^Т у ^

тс„ = Д„ах • -- + 4/^1 + 13к2 + 4/^3 + 13к4 +10/„

V М-г )

где ЫТ - число трасс;

г - разрядность операнда (время прохождения операнда); М - степень распараллеливания;

V - степень заполнения памяти координатами концов трасс; 13к\,13к2,13кт,,13кй, - задержки конвейера кадров к\,к2,кз и к4 соответственно; /„ - накладное время.

Время выполнения задачи на одном процессоре составит Т] = ИТ-1С-1540 . Средняя длина трассы составляет

С = Используя приведенные формулы параметры

выполнения трассировки на МВС СПРВ составит:

Т\ 5

Ускорение: & = — Эффективность: Е = —

Тс N

Доля накладного времени: 0 = -

Тсп

где Нс„ - накладное время для организации вычислительного процесса на МВС вычисляется по формуле Нсп = 2 • С • 1102 Коэффициент использования оборудования:

2-е-(if -AM+ 4 -12 M + t* -8 M + /4 • 9M Тс ■ N

где t, - время выполнения i-го кадра,

N, - число процессоров, задействованных при реализации i-ro кадра.

Выполнено сравнение времени трассировки на МВС СПРВ разработанным алгоритмом и волновым. Выигрыш по времени: при

трассировке на кристалле 5*5 мм и количеством элементов 2*104, разработанным алгоритмом, составляет при количестве процессоров 400 - 750 раз и при увеличении количества процессоров повышается. Предложен вычислительный комплекс для выполнения САПР БИС, на основе ПЭВМ IBM PC, использующий МВС СПРВ в качестве ускорителя решения задач САПР.

ЗАКЛЮЧЕНИЕ.

- на основе анализа классических алгоритмов исследована организация процессов решения алгоритмов на ПВС и в них выделены максимальные по объему параллельные вычислительные процессы и произведена оценка ускорения их работы;

- впервые разработаны алгоритмы для узловых процессоров матричной МВС позволяющие организовать процесс параллельного построения ортогональных связывающих деревьев с равномерным распределением связей по рабочему полю и максимально использующий достоинства ПВС, уменьшать суммарную длину связей, разрешать конфликтные и тупиковые ситуации, учитывать расположения других цепей;

- впервые предложена организация вычислительного процесса на МВС алгоритма расслоения, путем определения клик графа. Алгоритм позволяет выделять независимые множества графа без петель и кратных ребер;

- впервые разработаны алгоритмы для узловых процессоров матричной МВС, позволяющие организовать процесс одновременной трассировки всех соединений на МВС;

- произведены оценки ускорения выполнения разработанных алгоритмов на МВС при разном количестве соединяемых элементов и различных характеристиках узловых процессоров;

- разработаны принципы организации вычислительного процесса решения задачи трассировки соединений на многопроцессорной вычислительной системе СПРВ;

- синтезирован базовый набор макроопераций для реализации алгоритма трассировки соединений, учитывающий структурно-процедурную организацию параллельных вычислений и управление синхронизации потоками данных;

- рассчитаны теоретические характеристики вычислительного процесса, такие как время решения задачи, эффективность и коэффициент использования оборудования для реализации задачи трассировки соединений на МВС СПРВ;

- предложен, на основе программ, реализующих разработанные алгоритмы и существующего комплекса ПЭВМ типа IBM PC, и МВС СПРВ, аппаратно-программный комплекс для выполнения САПР СБИС, использующий МВС СПРВ в качестве ускорителя решения задач САПР СБИС.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ.

1.Ховансков С.А., Калашников В.А. Базовые кристаллы. Перспективы автоматизации проектирования. В кн. Автоматизация проектирования электронной аппаратуры. Таганрог ТРТИ, 1983, вып.2.

2.Создать систему конструкторского проектирования заказных БИС

на основе ЕС ЭВМ и исследовать возможность ее реализации на МВС(промежуточный) Отчет о НИР, ЖР 0189.0012823 инв. 029.10019109, г.Таганрог, 1990,------------------------------------------------------------

3.Ховансков СЛ., Литвиненко В.А. Оценка эффективности определения клик графа на многопроцессорной вычислительной системе Депонировано в ВИНИТИ 26.12.90 Ы6451-В90.

4.Ховансков С.А., Литвиненко В.А.., Калашников В.А. Алгоритм трассировки на многопроцессорной вычислительной системе Депонировано в ВИНИТИ 19.04.91 г., N1684-В91.

5.Ховансков С. А Применение МВС многопроцессорной вычислительной системы для решения задач САПР Материалы XXXIX НТК ТРТУ, Таганрог, 1993г,

6.Ховансков С.А., Литвиненко В.А.., Калашников В.А. Использование многопроцессорной вычислительной системы для решения задачи трассировки. Ведомств, тематический сборник "Интеллектуальные САПР". Вып.4 ТРТУ, Таганрог, 1994г.,

7.Ховансков С.А., Литвиненко В.А. Алгоритм определения клик графа на МВС Тезисы докладов все российской НТК "Актуальные проблемы твердотельной электроники и микроэлектроники Таганрог, 1994г (26-29.06),

8.Ховансков С.А., Калашников В.А. Моделирование работы алгоритма параллельной трассировки на МВС Ведомств, тематический сборник "Интеллектуальные САПР".Вып.5. ТРТУ, Таганрог, 1995 г.

9.Ховансков С.А. Параллельный алгоритм построения ортогонального связывающего дерева на многопроцессорной вы числительной системе Депонировано в ВИНИТИ 10.12.96г., N3605-В96.

Ю.Ховансков С. А. Распараллеливание алгоритмов построения связывающего дерева для решения на многопроцессорной вычислительной системе Известия ТРТУ N3 Материалы Всероссийской конференции "Интеллектуальные САПР-96", ТРТУ, Таганрог, 1997

П.Ховансков С.А., Калашников В.А., Трунов И.Л Параллельный алгоритм размещения на многопроцессорной вычислительной системе Известия ТРТУ N3 Тематический выпуск "Интеллектуальные САПР-96",ТРТУ, Таганрог, 1997г 12. Разработка и исследование новых методов автоматизированного проектирования электронной аппаратуры на БИС с использованием интегральных критериев качества. Отчет о НИР, N гос. рг. 01.960.005/75 - ТРТУ, 1996г.

Личный вклад автора в работах, написанных в соавторстве:

[1] - разработка методов трассировки;

[2] - разработка принципов использования МВС для этапа трассировки;

[3] - разработка метода расслоения на МВС;

[4] - разработка алгоритмов параллельной трассировки;

[6] - выбор структуры МВС для параллельной трассировки

[7] - разработка алгоритма определения клик графа для МВС,

[8] - разработка алгоритмов параллельной трассировки для реализации на ПЭВМ;

[11] - разработка метода оценки алгоритма размещения на МВС;

[12] - разработка методов оценки существующих алгоритмов трассировки для peaJ

Соискатель:

Ховансков С.А.



сР

МИНИСТЕРСТВО ВЫСШЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

РОССИЙСКОЙ ФЕДЕРАЦИИ ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

На правах рукописи

ХОВАНСКОВ СЕРГЕИ АНДРЕЕВИЧ

и* Ь

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

ТРАССИРОВКИ БИС

Iо. Пг

Специальность 05.13.12 - Сис-темы автоматизации проектирования

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель

д.т.н., профессор Калашников В.А.

Таганрог - 1998

СОДЕРЖАНИЕ

ВВЕДЕНИЕ.........................................................4

1. РАЗРАБОТКА АЛГОРИТМА ПОСТРОЕНИЯ ОРТОГОНАЛЬНЫХ СВЯЗЫВАЮЩИХ ДЕРЕВЬЕВ НА МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ (МВС)____20

1.1 АНАЛИЗ АЛГОРИТМОВ ПОСТРОЕНИЯ СВЯЗЫВАЮЩИХ ДЕРЕВЬЕВ И ОЦЕНКА ИХ УСКОРЕНИЯ НА МВС...........................................20

1.2 АЛГОРИТМ ПАРАЛЛЕЛЬНОГО ПОСТРОЕНИЯ СВЯЗЫВАЮЩИХ ДЕРЕВЬЕВ.....33

1.3 ОЦЕНКА УСКОРЕНИЯ ВЫПОЛНЕНИЯ РАЗРАБОТАННОГО АЛГОРИТМА ПОСТРОЕНИЯ ДЕРЕВЬЕВ НА МВС....................................70

1.4 ВЫВОДЫ.....................................................78

2. РАЗРАБОТКА И ОЦЕНКА ЭФФЕКТИВНОСТИ АЛГОРИТМА ВЫДЕЛЕНИЯ МНОЖЕСТВ НЕПЕРЕСЕКАЮЩИХСЯ ЦЕПЕЙ НА МВС...........____.........80

2.1 АНАЛИЗ АЛГОРИТМОВ ВЫДЕЛЕНИЯ МНОЖЕСТВ НЕПЕРЕСЕКАЮЩИХСЯ

ЦЕПЕЙ И ОЦЕНКА ИХ УСКОРЕНИЯ НА МВС............................80

2.2 АЛГОРИТМ РАСПРЕДЕЛЕНИЯ ЦЕПЕЙ ПО СЛОЯМ НА МВС ..............91

2.3. ОЦЕНКА ЭФФЕКТИВНОСТИ ВЫДЕЛЕНИЯ КЛИК ГРАФА НА МВС.....____103

2.4. ВЫВОДЫ...................................................116

3. РАЗРАБОТКА АЛГОРИТМА ПАРАЛЛЕЛЬНОЙ ТРАССИРОВКИ СОЕДИНЕНИЙ

НА МВС.......................................................117

3.1 АНАЛИЗ АЛГОРИТМОВ ТРАССИРОВКИ.,СОЕДИНЕНИЙ И ОЦЕНКА ИХ УСКОРЕНИЯ НА МВС................;............................117

3.2 ПАРАЛЛЕЛЬНАЯ ТРАССИРОВКА СОЕДИНЕНИЙ НА ОСНОВЕ АЛГОРИТМА ПОСТРОЕНИЯ СВЯЗЫВАЮЩИХ ДЕРЕВЬЕВ НА МВС.......................126

3.3. МОДЕЛИРОВАНИЕ РАБОТЫ АЛГОРИТМА ПАРАЛЛЕЛЬНОЙ ТРАССИРОВКИ

ДЛЯ МВС НА ПЕРСОНАЛЬНОМ КОМПЬЮТЕРЕ.............................134

3.4 ВЫВОДЫ....................................................138

4.РЕАЛИЗАЦИЯ АЛГОРИТМА ПАРАЛЛЕЛЬНОЙ ТРАССИРОВКИ НА МВС СО СТРУКТУРНО-ПРОЦЕДУРНОЙ РЕАЛИЗАЦИЕЙ ВЫЧИСЛЕНИЙ................140

4.1. СТРУКТУРА И ОБЩИЕ ПРИНЦИПЫ РАБОТЫ МВС....................140

4.2. ОРГАНИЗАЦИЯ ПАРАЛЛЕЛЬНОГО ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА И

СИНТЕЗ БАЗОВОГО НАБОРА МАКРООПЕРАЦИЙ ЗАДАЧИ ТРАССИРОВКИ......144

4.3. ОЦЕНКА ХАРАКТЕРИСТИК ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА ТРАССИРОВКИ..................................................158

4.4. АППАРАТНО - ПРОГРАММНЫЙ КОМПЛЕКС ДЛЯ САПР СБИС...........174

4.5 ВЫВОДЫ.....................................................178

ЗАКЛЮЧЕНИЕ.....................................................180

ЛИТЕРАТУРА.....................................................182

ВВЕДЕНИЕ

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

Автоматизация процесса проектирования ЭВА и разработка САПР позволили не только сократить сроки создания аппаратуры и облегчить условия труда, но и повысить качество производимой продукций. Это стало возможным потому, что при производстве изделий для управления станками, автоматами и поточными линиями используется информация, разработанная с помощью САПР и записанная на ЭВМ. Благодаря этому время проектирования сократилось, а ЭВА усложнялась и наметилась тенденция к очередному увеличению сроков разработки изделий, даже с использованием САПР. В тоже время стала заметна тенденция к уменьшению средних сроков эксплуатации ЭВА, которая связана с ускорением прогресса в микроэлектронике и, соответственно с быстрым моральным старением эксплуатируемой

аппаратуры [3,8,13,14,16-18,22,23,28,30,31,36,37,40-42,49,52,5460]. При таких противоречивых тенденциях возникло положение, при котором выпускаемые изделия ЭВА становятся с самого начала производства морально устаревшими.

В связи с этим, основная трудность при разработке ВМС, которая, очевидно, будет усиливаться по мере роста степени интеграции в будущем, заключается в том, что традиционные методы автоматизированного проектирования и используемые для этого средства вычислительной техники не позволяют эффективно и качественно проектировать объекты такой высокой сложности.

Решение этой проблемы может идти четырьмя путями [3,8,22,23, 30,31,36,40,41,52,561. Один из них состоит в разработке эффективных численных методов решения уравнений, в применении иерархического ряда различных по сложности моделей, в использовании адаптивных алгоритмов и т.д., то есть, в совершенствовании программных средств САПР. Этот путь к настоящему времени практически исчерпал себя.

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

программирование при создании новых САПР.

В силу принципиального различия в математической постановке задач разных этапов премирования оказывается достаточно сложным создание сквозной САПР СБИС на базе одного общего специализированного вычислителя. Поэтому к настоящему времени наибольшие успехи получены в создании процессоров-акселераторов для логического и физического моделирования, но начинают появляться спецпроцессоры и для других этапов, в частности, для топологического проектирования СБИС [3,8,16,28,30,37,563.

Третий путь - использование быстродействующих аппаратных средств для ускорения процесса проектирования. Этот путь очень дорог, и в любом случае его эффективность уменьшается по мере увеличения системы вследствие задержек в передаче сигналов.

Четвертый путь - применение параллелизма для решения задач САПР СБИС. Параллелизм все более широко используется как средство, позволяющее повышать производительность вычислительных систем, не прибегая к повышению быстродействия их компонентов [8,28,30,37].

Реализация параллелизма стала возможна с созданием многопроцессорных вычислительных систем (МВС). МВС вычислительная система, базирующаяся на принципах параллельной обработки информации. Многопроцессорные вычислительные структуры с программируемой архитектурой отличаются способностью аппаратно адаптироваться к характеру вычислительных процессов и обеспечивать высокий уровень распараллеливания вычислений, соответственно, сверхвысокую производительность [9,28,30,55].

В системах автоматизированного р ттйктр^нной

аппаратуры в качестве базовых алгоритмов используются различные алгоритмы решения задач на графах. Однако применение этих

алгоритмов ограничивается их комбинаторной сложностью. Одним из наиболее эффективных путей сокращения временных затрат на их выполнение является использование многопроцессорных вычислительных систем (МВС). Сокращение времени решения задач проектирования дает возможность повышать качество проектирования увеличением числа циклов итерации, использованием более точных, но трудоемких методов решения [5,7-10,15-54].

Существует множество разработок МВС. Они отличаются друг от друга структурой, объемом и организацией памяти, разновидностями набора выполняемых команд, коммутациями, разрядностью обрабатываемой информации, типами операций и др. [9,28,30,55,61-68]. По сути, МВС является алгоритмическим операционным устройством [61,65,66,681. Алгоритмические операционные устройства по своему назначению можно разделить на три группы.

К первой группе относят устройства суммирования, вычитания, умножения, деления, называемые устройствами вычислительных операций, и устройства, реализующие операции логической алгебры.

Вторую группу составляют устройства вычисления одноместных функций X, 1/Х, е, log X, тригонометрических функций и т.д.

Третья группа предназначена для вычисления специальных многоместных функций, таких как свертка, БПФ и др.

На рис. I изображена классификация устройств по структурной, аппаратной сложности и по.принципу организации потоков данных.

Матричные устройства можно разделить на 4 класса [9,28,30,55, 61-68]. К первому относят комбинационные схемы (итеративные сети). Если комбинационную матрицу совместить с матрицей триггеров, то, добавив необходимые соединения, получим второй и третий классы устройств - систолические и ассоциативные матрицы [28,30,62,65].

Четвертый класс - это ассоциативно-систолическая матрица, способная, в зависимости от настройки по коду операции, выполнять операции конвейерной арифметики и ассоциативного поиска.

Специальные функции со сложностью О (И) и более реализуются на комбинационных и систолических матрицах с шогоразрядными ячейками, а также неоднородных одно- и многотрактовых операционных устройствах.

Для создания наиболее технологичных современных микроэлектронных алгоритмических операционных устройств требуются специфические изменения в структуре самого устройства. Одним из основных необходимых изменений в его структуре является такая организация, при которой оно строилось бы на основе небольшого числа типов элементов. Необходимость обеспечения высокой живучести и надежности требует построения алгоритмических операционных устройств из структурно - однородных блоков. Из приведенных выше структур МВС видно, что наиболее многочисленным семейством являются матричные МВС. Процессорное поле составляют матрицы БИС с идентичными элементами, их структурная сложность незначительна, поэтому матрицы БИС с одноразрядными идентичными элементами экономичны в проектировании и изготовлении. Они получают все большее распространение [30,55,61-64,66-681.

Выполнение любого алгоритма может быть разбито на отдельные процессы, это могут быть микрооперации, операции, команды, блоки и т.д., а с точки зрения последовательности выполнения процессов, любой алгоритм можно представить как параллельный, ярусный и параллельно-ярусный. Параллелизм решения задач реализуется на МВС, когда алгоритм решения является параллельным и для МВС создана специальная параллельная программа, предназначенная достичь цели,

заданной алгоритмом задачи и обеспечить эффективную параллельную обработку информации [42,55,61-64,69-713. От эффективности параллельной обработки информации зависит время решения задач на МВС [63,64,703.

Существует два основных метода использования параллелизма -параллелизм структуры (структурный параллелизм) и параллелизм процессов [42,55,61,63,69-713. Различие этих видов параллелизма заключается в том, что структурный параллелизм определяется на уровне одной операции и что эти операции выполняются так, как если бы они выполнялись одновременно над каждым элементом структуры данных и параллелизм процессов определяется на уровне более крупных совокупностей операций. Синхронизация между параллельными потоками команд выполняется с помощью генератора. Эти методы весьма сходны и для многих алгоритмов могут быть применены с одинаковой эффективностью [55,63,70,713. Однако считается, что динамическое создание и уничтожение процессов, обеспечивая большую гибкость программирования, требует большей избыточности для реализации параллелизма и для повышения эффективности необходимо уменьшение глубины детализации [55,61-64,69,703, т.е. параллельный алгоритм должен строиться из возможно более крупных, но редко взаимодействующих блоков. Из этого следует, что наиболее эффективен второй метод распараллеливания - параллелизм процессов.

Следовательно, для эффективного применения многопроцессорной вычислительной системы в качестве ускорителя выполнения задач САПР, необходимо, чтобы алгоритмы решения задач были основаны на однообразных процедурах и состояли из возможно более крупных, но редко взаимодействующих блоков команд.

Автоматизированное проектирование СБИС охватывает широкий

спектр вопросов, включающий представление исходной электрической схемы в виде математических моделей, размещение элементов библиотечных наборов на рабочем поле, проектирование коммутационных связей между ними и в проводящих слоях, контроль топологии, фотошаблонов и т.д.

Целью диссертационной работы является разработка и исследование алгоритмов параллельной трассировки - построение связывающих деревьев, расслоение, синтез топологии - предназначенных для реализации на МВС, позволяющих значительно сократить время и повысить качество проектирования топологии СБИС, произвести оценку его эффективности.

Реализация поставленной цели потребовала решения следующих задач:

- исследование существующих алгоритмов построения связывающих деревьев, для оценки ускорения их выполнения на МВС, на основе выделения в них максимальных параллельных процессов;

разработка нового алгоритма параллельного построения ортогональных связывающих деревьев и оценка ускорения его выполнения на МВС;

- исследование существующих алгоритмов распределения фрагментов цепей по слоям для оценки ускорения их выполнения на МВС на основе выделения в них максимальных параллельных процессов;

- разработка алгоритма определения клик графа для выполнения на МВС и оценка эффективности его выполнения;

- исследование существующих алгоритмов трассировки соединений для оценки ускорения их выполнения на МВС на основе выделения в них максимальных параллельных процессов;

- разработка нового алгоритма параллельной трассировки соединений и оценка ускорения его выполнения на МВС;

- разработка организации вычислительного процесса и синтез базового набора макроопераций необходимых для реализации задачи параллельной трассировки на МВС;

- разработка аппаратно-программного комплекса, для работы САПР

СБИС, на основе разработанных алгоритмов и МВС со структурно процедурной организацией вычислений, в качестве аппаратного ускорителя выполнения задач САПР;

- исследование ускорения, доли накладного времени, коэффициента использования оборудования и коэффициента качества программирования при реализации задачи параллельной трассировки на МВС СПРВ.

Методика исследований базируется на теории множеств, теории графов, теории оптимизации, теории алгоритмов, теории вычислительных систем и принципах параллельной обработки информации с учетом специфики алгоритмов и процессов, порождаемых при решении задач САПР.

Научная новизна работы заключается в следующем:

- разработан алгоритм обмена между процессорами решающего поля, имеющего структуру типа решетки, позволяющий за минимальное время выполнить обмен информацией всего поля процессоров;

- разработан новый алгоритм параллельного построения ортогональных связывающих деревьев;

разработаны принципиально новые алгоритмы для узловых процессоров процессорного поля МВС, позволяющие организовать процесс одновременного построения всех ортогональных связывающих деревьев, получена оценка ускорения выполнения построения ортогонального связывающего дерева на МВС;

- разработаны алгоритмы для узловых процессоров, позволяющие организовать эффективный процесс выделения клик графа на МВС, процессоры которой соединены по полному графу, получена оценка ускорения выполнения выделения на МВС;

- разработаны алгоритмы для узловых процессоров, позволяющие

организовать процесс одновременного построения всех трасс на МВС, процессорное поле которой имеет структуру типа "решетки", получена оценка ускорения выполнения алгоритма на МВС;

- получены оценки ускорения выполнения на МВС ряда существующих алгоритмов: построения ортогональных связывающих деревьев, разнесения связей по слоям, прокладки трасс, на основе исследования вариантов их вычислительных процессов;

- разработаны принципы организации вычислительного процесса и синтезирован базовый набор макроопераций для выполнения параллельной трассировки на МВС СПРВ.

Практическая ценность работы

На основе теоретических исследований предложена методика, позволяющая производить оценки эффективности выполнения алгоритмов проектирования на МВС. Соз�