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

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

На правах рукописи УДК 681.3:621.3.049

ТРУНОВ ИГОРЬ ЛЕОНИДОВИЧ

ЗДАНИЕ «ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ САПР НА БАЗЕ МВС-, (ЭТАП РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ)

Специальности

04.13.- Системы автоматизации проектирования О'.;.13..'5 - Применение вычислительной техники, математического моделирования и математических ч.'/тодов в научных исследованиях

АВТОРЕФЕРАТ .•.(ссертации на соискание ученой степени кандидата технических наук

Таганрог - 1996

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

Научный руководитель .доктор технических наук, профессор Калашников В.й. Официальные оппоненты: доктор технических наук, профессор Глушань В.М кандидат технических наук Сураенко И.Ф.

Ведущая организация: ИНСТИТУТ ПРОБЛЕМ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ РАН, г. Ярославль

. Защита-диссертации состоится "___"_______________199__г.

в_____ часов на заседании специализированного совета

Д 063.13.02 при Таганрогской государственном радиотехническом университете по адресу: .347915, Г.Таганрог, Некр.:" ор■ кий. 44. ауд. Д - 400.

С диссертацией кояно ознакомиться в библиотеке университета.

автореферат разослан "

Нченый секретарь спеииализированнг--

совета Д 063. 02 к.т.н.. доцент :

й.Н. Целых

йктчальность работы. Проектирование СБИС - это сложный, занимающий много времени прсцесс; сроки разработки электронного устойгтва, содержащего СБИС в качестве компонентов, могут превышать период, в течение которого изделие пользует-г.я спросом. Затраты на проектирование возможно, не окупятся до того, как прибор устареет, йчитывая эти обстоятельства, разработка СБИС должна осуществляться в кратчайвие сроки, с наимеььвими затратами; устройства выполненные по этим проектам. должны обладать заданными функциональными свойствами и отвечать поставленным требованиям. Одним из путей достижения этоЛ цели являет'ся автоматизация процесса проектирования, начиная с высиего уровня представления требований к системе и кончая уровнем физического'представления с помощьв фото-

V

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

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

Положительный эффект при режекик задач автоматизирован-

1 ^ - *

ного проектирования,БИС на-КТС., в е<гстав. кЬторых входят МВС,

ц

мо*ет бить достигнут, в основном, за счет их распараллеливания.

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

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

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

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

- моделирование разработанных алгоритмов на эмуляторе МАЗУ-МЙП.>

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

Научная новизна. Научная новизна полученных в работе результатов замечается в сдедуввзм:

- разработан алгоритм'разаевения элементов с использова-

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

- исследована зависимость меяду временам решения задачи и чменьиением суммарной длины соединений при различном выборе

;> - последовательности Фибоначчи:

- разработаны приьципы организации вычислительного про-, ■лесса решения задачи размещения элементов на многопроцессорной • шлеме;

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

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

Реализация работы. Теоретические и практические результаты. полученные'в диссертации, использовались в госбюдвет-них и хоздоговорных научйо7исследовательских работах, выполняемых согласно планам работ секции радиоэлектроники и приборостроения. Программы САПР Минвуза РСФСР, а такие по

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

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

- мевреспубликанском семинаре "Интеллектуальные САПР СБИС", г. Ереван. 1988 г.:

- меадународной научно-технической конференции студентов, мо лодых ученых и специалистов "Молодые ученые в. решении комплексной программы научно-технического прогресса стран-членов СЭВ", г.Киев, 1989 г.;

- всесоюзной конференции "Теория и практика построения интеллектуальных" интегрированных САПР РЗА и БИС", г. Москва,

1989 г.:

-всесоазном научно-техническом ссминаре "Созцание интеллектуальных СЙПР СБИС и электронных средств",-г. Гелендеик. 1990г.:

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

1990 г.:

- иеареспубликанской иколе-семинаре "Опит разработки и применения приборно-технологических САПР", г^ Львое, 1991 г.:

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

Публикации по теме диссертационной работы. Материалы, садереавие основные научные результаты, опубликованы в ?

?

печатных работах, кроне того вг ВНТИЦ зарегистрировано 9 отчетов по хоздоговорным и научно-исследовательским работах в области автоматизации и проектирования РЗй и БИС, выполненных при непосредственном- участии автора.

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

•И? стр. машинописного текста, содержит Ц стр. рисунков и таблиц, списка литературы, включающего наименования, и прилокения.

Краткое содержание работа.

Во введении отражены актуальность темы, цель и научная-

#

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

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

ё

d! sai и. таким образом, представляй е® ¡в ваше Ь"

Задача разнекмшя сбодося тавдь ь втаВралйнжш зада* нуге графа! схеин £-iX.Bí з явердаитвда сетад тазаи •згдо.ш- . чтооч берлина инолества I разместились б же дзлшх ® £®<ог№7-ствии с еябраншга критерием разяещегла.

СОДОДяирдех ээтоновяА штоцазиктнай ашгарятя с исаодьэо ааннеи крит^ргя хинимдка сдамарнвгс Еардя-шиа гараюшэес&а расстоЯ«ай. >

jüa опенки степени ддобства В -ой ш азида зды вержкны

графа Gr взедеи понатне "йарраения r^pitasreoraac радогпюяА. *

Lj - £ (tLj - flßsi^j ■ í dl.j >$ij {4}

' где íj. - яар35гнЕ£ гарявьичеськх ¡рдсстшаий юз 3 -чай aepiiras:

сtij ~ расстсание мевдд ssaaiut i i i гра®з I¿r r. %ij - число кратных peSíp шеадд ВЕркиваяи Xim Xj ~ - гармваичеавк гасстшншя ваюш в^ршма-аин

Xi и % .

* ~ Хдтъ* алгоритма з£штчает£я в 'сяедэшаг-«- Чзвесгао. чта -£Л5 уневьззана суммарной juman сведхнеяяа злжвегаа связанны с щздгам идхно размещать как гешш йшяж таг к даггд.. йиеаяъный шарааят. когда р-згстсшние шезду хшлзакакки р^рзинайя равип 1. Но практически это йессзрцшгмви:.

С цаяьи шгаямизацня расстояния щредаг&етса шстгакить ь соответствие жоничестед стьеЯ «вкдд ыщшршв ti¿ ш®-киторое число из паслежоватальнохтв f ilj*" мгещ!-

вдва oïjaszai

la

0 il as..- ■• п.

Ш 'ЯЙН0 ÍÍ«W

/ад - иазвве« гсцшонически н рагстапнинм.. Id алгцрит»гд здр-я«ш. скязакшв связяии, дюжни гакядтпюя щщг от д/гц-а аа ¡расгавянии ms йвль'эем.. $<¿jj .. ;йз .'инпввгтжл sïîpjffa r¡paipa. [рвоншнгенйппо 3 свтке ¡выйчр-аетея »кротка Щ t аавскмаямпш í$ ® щрЕшав'ВДИзта ъе ¡паркстзнттвка <с дгруглй э*длшнпй с даямв ашпшзяции тумщршти вдрзэнниа игармлни-

ЧИЖИЖ ¡рэсста.яккй. РаШШЩЯ!» ИРПЦЮГЙРВ ЕКбНра КГЛРОЙ ЕВ!Щ>-гкны даа ПЕгрьраэ^р-зжкя жврвин ¡прадш.. ЩрэдцяаБИИ,. чт> щпн-.. !нзгй граф ¡шдоитрдет ¡яеютицщз систгва материальных -точек.. йусть тов точки Xj£ Ж< закреплены., а ушЖ щвтется mu ивкшгадяящ звищд„ Тягда ¡известно. »что жинщд» гуикарняй ayirefffi расстояний от ¿¡ да тг -тнек Щ ашвЕТГ агеигв„ тгвч-

ш ¡t/ шиедЕна s t жтаданитаии ¡центра тгзииггтя

'( St , ikt й ^гсокатртааеипй Тзвкм ш'бразпн., ъхвтгтгя

тгешр яолвввжв дай версияя у-е Ж > гагтщгае вгбнппгчит дав-«яв-Есае в аякгжв ¡щш делткких.. ¡кпгща ¡все ашггалшыв шегряины

зэднишега. и яши® j/ л тячк2ии x¿ с x .шь-иъ

дейгштатг ша !гц>1тягеш1я„ тгртгоряягжа "ьная «fcy « Щ йотдашзха цслевтгй ?1якя тфщшгавтся ¡как

m m

zij m

jf* л*

¡nm« Sjtj - мсокрзгината - .«и

В общем случае подученная то".ка 1'5с не принимает (^.начисленного значение. Перестаэляя выбрашш вершины, вновь

т

вычисляем суммй&яое нарушение гармонических расстояний •

Процесс продолжается до тех пор, пока I не будет равна О иди за определенное количество итераций не получено умень-вьнйе суммарного"нарувения гармонических расстояний. Приведем описание алгоритма. п.1. Сформировать первоначальное размещение, п.2. Выбрать рлд Фибоначчи, исходя из характеристики схемы (максимального'количества связей мехду вершинами).

п.З. Вычислить нарушение гармонических расстояний по каждой вервине и суммарное нарушение гармоничесних расстояний по формуле 1.

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

п.5. Вычислить силовой вектор и целевую точку для этой вермин» по формуле 2.

п.б. Осуществить перестановку вершин и сделать вычисления по п.З.

п.7.* Имеется какое-нкбддь уменьшение суммарного нарушения гармонических расстояний ?

Если да, сохранить новое размещение м перейти к п.4 Если нет. перейти к п.8. п.8. Сохранить старое размещение и перейти к следующей вервине с меньшим нарувением гармонических расстояний.

и

п.9. Все ли вершины просмотрены ?

Если да, перейти я п.10 .

Если нет, перейти к п.5 .

п.10. Конец

В третьей подразделе обработаны эксперемектальные результаты, в частности, исследована и проанализирована зависимость менду временем решений задачи и выбором р-последовательности Фибоначчи.

Во втором разделе освещаются вопроса связанные с реализацией задачи раэмчцения элементов на накрококпьвтере. С этой цельз в первом подразделе описывается назначение и некоторые особенности вычислительного процесса макрокомпьютера., В частности описан состав макрокомпьатера включающего в себя: суперпроцессор. общую память, системный интерфейс. Выделен основной- принцип функционирования какрокомпьатера, предпологающий право пользователя на "доконструирования" требуемой архитектуры с помощью представляемых технических и программных срэдств. Рассмотрены способы организации вычисления и методы исиараллелквания задач. Из элементной базы для построения «акрокомпьлтера рассмотрен макропроцессор (Ш) - процессор-¡аа секция с программируемой структурой, реализующая базовые ¡аборы крупных математических операций (накрооперации (ЙЙОП)) структурными методами. Обьяснены некоторые особенности прик- ! ,ладного программирования макрокпмпьвтера:

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

2) последовательность кадров определяет процедуру (за-

а

дачу> выполняемую иакрокомпьютерои.

Во втором подразделе описана организация паралельного вычислительного процесса. Вычислительный процесс разбит на 5 кадров. Первый кадр содернит: МАОП J9 - для вычисления массива истиных расстояний мевду элементами, МАОП KMR - для вычисления гармонических расстояний меяду элементами, МАОП N& - для вычисления массива нарушений гармонических расстояний. МАОП РАКШ - параллельный максимум., МАОП MAXSTR -- максимум потока для определения-максимального элемента массива нарушений гармонических расстояний. МАОП PARSUM - параллельное вычисление сумм«._МА9П Sl'MMA - последовательное • вычисление суммы, для вычисления суммарного нарушения гармонических расстояний. Во втором кадре с помощью МАОП PR (.произведение двух чисел), PARSUM. SUMMA. СТТ (параллельное деление двух чисел на третье) вычисляются координаты цс левей точки для вершины с максимальным нарушением гармонич^г-ких расстояний. ,Ь третьем к$дре,по вычисленным координатам целевой точки находится номёр в'ершины замени. Для этого в кадре выделены две МАОП NZ и PARDIS, В МАОП NZ идет непосредственное сравнение координат целевой точки с массивом исходного располо»ения элементов, а МАОП PARDJS представляюаая \ ' * ■ ! собой пирамиду дизьюнкторов выделяет номер замены элемента.

В четвертом кадре с помощью МАОП ELS по найденным номерам

■для перестановки вершин производится ,выделение строк и столо-

t j 1 цов матрицы SVZ. В пятом кадре производится'обмен ctpoK и

столбцов матрицы.! Причел MAOtl ZEST производит обмен столб-

i' ,

цов матрицы, а МАОП ZS производит обмен строк.

В третьем подразделе привздены характеристики вычислительного процесса. В соответствии с граф-схемами МйОП были определены сложность (количество элементарных процессоров (31!)) и операционные задержки каждой МйОП. В соответствии со структурными схемами кадров были определены сложность ( VI) ,. операционные задераки, количество (м-) и глубина каналов памяти по записи-считываниа и время <Тр однократного выполнения каждого кадра, для размещения N элементов.

7< -'¿оыУт + 50¿орт * гвл

Тг = к - '-4

тз - Р.ОМ//П * 6... ,,, i в2

■= ЮЛ'У,7? * п , Общее время выголнения одной нтеиЗ"^»*

Тит = I Я ^еоиУгп » Ш/м + 6?

ревения задачи, прошедаьП 9 чтераций Ьр'.-мй т, учитывает сычихление условия окончания итеррацион-",ого процесса. Опытным путем была определена зависимость количества итераций ог размерности задачи 9 * ¿'<^>.7 откуда

минимальное время ревения задачи (без учета операционных задержек)

to

Эффективность

7lt„„ l0Nll№ (¡¡СogjrtfcO/v'/M t фф)

e=-

Коэф<ри«иекг использования оборудования имеет вид

I TlVL кия -——-------

>. _

max V'Z U

v»i

~2280A3~i И2ГА}' + ьшг^+ыои/м ¿isihrnLo^m t > ЬЛ2

б третьем разделе организация вычислительного процесса конкретизирована исходя из вычислительного ресурса эмулятора ЦОД МАГ?., имеющего всего 1С ЭП и 6 НР.5У. Из-за ограниченности ,ресурса задачи размещения была развита на 9 кадров, «asaufi из которых-, кроме первого, содержит одну MP.OFi. Для каждой MQGfl приведены: .программа-, таблицы расположения дар-

\ .. т

mix в М(Ш, вр^мейная диаграмма выполнения.

.В заключении приведены основные результаты диссертационной paCioTuA

6Л1рилоеении приведены распечатки файлов программ модели

Ч * ' ' ' ( v '

рования и файлов результатов моделирования,-пример работы эму

ляторл MiWH-MfiR .и .а^ы ^использовании результатов диссерта-

цио'ниой работы,. ' ч

' Основные реэульт?т1? работы. ^ -

1разработан алс-огитй размещения элементов. £ использо-* " / «• ' ' '

ванием последовательностей Фибоначчи, позволяющий использовать его в качестве предварительного размещения. Предлояено в качестве гармонического закона связываввего два понятия: расстояние иеаду элементами и количество связей меадд ними, использовать р - последовательность Фибоначчи и на основании этого введено понятие гармонического расстояния кеяду элементами.

2. Впервые исследована зависимость меядд временем реиения задачи и забором р - последовательностей Фибоначчи, такие дан вероятностный прогноз уменьшения суммарной длины соединений при ограниченной лимите врекенЯ при различных выборах

р - последовательностей.

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

4. Синтезирован базойый набор макроопераций для реализации алгоритма размещения элементов с использойанием последовательностей Фибоначчи, учитывающей специфику'эмулдт МйЗУ -МАП. структурно-процедурную организаций паралельных вычислений и управление синхронизации потопами Тайных.

. 5. Рассч'йг^ЙН теоретические характеристики вычислительного процесса, такие как время резания задачи, эффективность и коэффициент использования .оборудования для реализации задачи размещения на накрокоШлтере.

Разработзч-пакет прикладных программ на мавинннх языках программирования процедур.и заданий для моделирования эа-.чйелй.-\1ьчсо процесса. Пакет апробирован на эмуляторе МйЗН-

1в

Осноьлые полояения диссертационной работы излояены в следующих пуоли.чл':,>•-::<;

!. йисяк В.Ь.. Трунов И./!.. Лях А.В. О реализации параллелизма в алгоритмах размг щсия фрагментов топологии БИС. -- Сеп. ь ВИНИТИ N '570-Ввя. 1С .

Тр'г'Н'Ч- И.г. Об одном подходе к задаче размещения.// ИнIеллектуэльче:р САПР СБИС: тея.д-л..«:, - Ер»>р*н 1-988 г.. Ч.2Ч.

IрумоЕ- И.Л. Алгоритм рпомещения элчменток С использование« последив<лтельностей Фи'^наччи: тез. докл. мекдунар. н. т. !.ПН4\ - Киев. 1989 г.. с 144.

4. Трутн- И.Л. Об одном решении задлчи ¡'замещения на гц-перЗР-й с прмгрзммируемой архитектура.// >.'-¡здание интеллектуальных САПР СБИС и ЭС: "ез. докл. - Геленшш.. 1990 г..• .5^

.5. Калашников В.А.. Тииенко В.А.. Трунив И.Л. принцип: реализации алгоритмов разм^Щ'-ния на многопроцессорных &ычк': -лительных '*!■ нмЫх. Л' '„'яыт разработки и применения приборно-технологиче. ки>- САПР: тез. цока. - Львов. 1991 г.. с.33.

а. Разр-!0<7гк-1 и исследев-ание архитектуры, принципов построение и .,'л!.к1?нтнйй"1^1зы высокопроизводительного суперпроце'.--сора для решем.чя зад"ач САПР СБИС. »Отчет о НИР.» / НИИ «ВС пр.' ТРТИ. -Ы ГР "1.9.10 054183 - Таганрог. 1991 г.. с.31-32.

?. Супер ЭВМ с программируемой архитектурой и нейрокомпьютеры. (Отчет о НИР Г/НИИ «ВС при ГШ. N ГР 01. 090036910 - Таганрог. 1991 г,, кн. 3.. с.7в»Ш.

Личный вклад автора в работах написанных в соавторстве: /1/ - основные принципы распараллеливания алгоритмов: /5/ - стратегия реализации алгоритмов размещения на многс процессорных вычислительных системах.