Алгоритмы оптимизации сетей с переменными сечениями дуг и их применение тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

АКАДЕМИЯ 11ЛУТС БЕЛАРУСИ о; ■ ' ИНСТИТУТ МАТЕМАТИКИ

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

РУДЕНКО Анатолий Григорьевич

АЛГОРИТМЫ ОПГШЛ0АДИИ СЕТЕП С ПЕРЕМЕНИМ! СЕЧЕНИЯМИ ДУГ И ИХ ПРИМЕНЕНИЕ

Специальность 01.01.09 - математическая шнЗернэтшш

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

Минск - 1992

Работа выполнена в лаборатории математических проблем автоматизации проектирования Института математики All Беларуси.

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

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

Официальные оппонента - доктор {изико-математичиских наук, профессор

ПЕРЕПЕЛИЦА Виталий Афанасьевич

- кандидат физико-математических наук, доцент КОЗМЁВ Михаил Михайлович

Ведущая организация - Институт кибернетики им. В.М. Глушкова

Академии наук Украины (г.Киев).

Защита состоится "6 " марта 193В года в ° часов на заседании специализированного соаета К 006.19.01 в Институте математики АН Беларуси по адресу: 220073, г.Минск, ул.Сурганова 11, Институт математики АН Беларуси.

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

Автореферат разослан "Ь." 1992 года.

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

А.И.АстровскЕй

эскиза топологии заказных БИС/СБИС.

Публикации и апробация. Основные результаты диссертации опубликованы в работах г 1-41 и докладывались: нз республиканском семинррэ "Машинные метода проектирования электронно-вычислительной аппаратуры" (Каунас, 1988 г.); на всесаюзной школе "Актуальные проблемы создания интеллектуальных САПР РЭА и СБИС" (Крымская область, 196Э г.); на международной школе "Новыэ информационные технологии в проектировании" (Крымская область, 1991 г.).

СОДЕИШШЕ РАБОТЫ

Во введении обосновывается актуальность исследования, даётся обзор шещихся результатов по теме диссертации и приводится краткая аннотация всех е9 параграфов.

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

Математическая модель для задачи оптимизации pg-cöth, отражающая основное технологические требования и фжичаские ограничения, впервые была представлена Ф.Брейнинсм в работе 2>. В основе всех рассмотренных математических моделей лежит постановка задачи (задача 45), представленная в работе 3> и зэключащаяся в следующем:

Пусть задано корневое дерево тг-сег,уэ. Каждому ребру атого дерева приписашо множество w. допустимых ширин и величина 1. (длина ребра). Проблема оптимизации'шкч питания и ■земли состоит в том, чтобы 'определить ширину *._« w.,i-rrtf

ы

каждого ребра таким образом, чтобы величина Е принимала

i « 1 11

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

Dranin Г.H. The Analysis and Design of Power Distribution Wets on LSI Chips // Trans, on circuits and systems. — 1Q80. -Vol. 33. - P.785-700.

" Chowdhury S., Breuer M. The Construction of Minimal Area Power and Ground Nets for VLSI Circuits /.' Proc. 22nd DA Conf. - 108S. - P. 704-707.

превышать заданных величин u., j« l : ) ^ piii ^ s и.,

tе Potblг , j J

где i.- значение тока в i-ом сегменте (заметам, что в соответствии с законом Кирхгофа i.» ) ' iгде soniiJ-

j С Sonti]

множество сыновей вершиш ¿), Pathti,ji - путь из i-ой вершины дерева в j-ую, - множество листьев дерева т., р-удельная проводимость слоя, в котором реализована pg-сэть. Множество допустимых щрин w. задаётся неравенством w.2:c., и кроме этого трббуэтся целочисленность ширин w..

В первом параграфа диссертации предложены две математаческие модели для задачи расчета сечений сымэнтов pG-сети, являющиеся модификацией ошсашой выше модели:

ЗАДАЧА (ОД) ОРДИНАРНОГО РАСЧЕТА ЦЕЛОЧИСЛЕННЫХ СЕЧЕНИИ СЕГМЕНТОВ р-СЕТИ

-> min

(СЦ)

) 1 . W. ->

* ■ 1 V

V «V г

) ' рх. 1 . у». ¿U .. J« L ,

' ■ ^ V V V J ' г*

i € Palblг, j )

w e «.={«.> cJN, . i«V

k l тл= 1 p

гдэ ш -ое допустимое значениэ оириш сечения 1-о2. дуги, ег, л,- количество допустимых значений ширины сечения

ДЛЯ дуги е.« Ер , В1 - г/ножбстзо натуральных чисел.

Постановка задачи ОН, адекватна реальной ситуации, в которой ток существует во всем■дерева т^ одновременно, то ьсть вся интегральная схема является "открытой". Ко на практике более распространенным является случай, когда в каждый момент времени "открыта" только часть схемы, то есть ток одновременно существует только в некотором поддереве т* дерева тг. Корень поддерева т* находится в корне дерева тг. а листья поддерева т* являются некоторым годаножеством листьев дэрева т^:

-S-

Кроме того, полагаем, что ьг- ь*и ь".

Обозначим через:

I* - ток. проходящий через вершину в случае,

когда "открытым" является поддерево тк , к-Г7м ; хк - падении напрязвния на сегменте р-сети,

соответствующем ,)-ой дуге дерева т^, в случае,

когда "открытым" является поддерево тк, к=1,м ; ик - максимально допустимое падение напряжения на цепи

ОТ КОрПЯ г ДО ЛИСТа j, .И Ьк, к-1,м. Представим соотношение, описывепцее взаимосвязи меэду шириной сегмента и падением напряжения нг: атом сегменте прл "открытом" поддереве тк:

хк-р1.1к^. 1еУ . к-ГТМ.

» ' 1 »_ I г * '

Введем дополнительно обозначения:

и. «»Си и ...и ),

ж.-СГ I ...I >, 4 Л Л 1

, 2

с »р1 а.,

> 1

— ,12 К.

X.=Сх х. . .х.>, J ) 1 )

1 сЬ , г

где aj«Цk-í7H|I>0^f,

X -{х -Сх1 х*.. .хМ) |р1г1к 1к*0>,

1 > ) з J 1 J J JJJJ ,

— — 1 2 М

ГЛВ . Р'х7.если 17^0

* ГДв дС х 3■< ' '

' и , если 1м-о.

С учётом приведённых выше обозначений и замены переменных задача ОЦ перепишется следущим образом:'

ЗАДАЧА (ЩВ) МУЛЬТИВАРИАНТНОГО РАСЧЕТА ЦЕЛОЧИСЛЕННЫХ СЕЧЕНШ Р-СЕТИ В ВЕКТОРНОЙ ФОРМЕ:

(ЩВ)

Г .с.Г.'дСх.) -> вйп

х.< и л ш

) « Га! М г.т!

гас I.

Л*. .

Г

где •<■• -отношение покомпонентного сравнения векторов,

- скалярное произведение векторов. Исследованию этой задачи посвящена основная ■часть диссертационной работы.

Второй параграф посвящЭн анализу сложности задача ОЦ.

Теорема-

Задача определения целочисленных свчоний шин питания и земли СБИС является нр-трудной.

Задача ЩВ также мр-трудна, так как задача 00 является оВ частным случаем (к«а). В данном случае ьгр--трудность задачи (не з сильном с!уйслэ ) не исключает построение алгоритмов ой точного решения с псевдополиаомиальннм временем работы.

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

В третьем параграфе выводится соотношения динамического программирования для задачи МЦВ.

Каждому вектору у« к" сопоставим множество веру.

Элемента(.и этого множества являются такие наборы »

Г

которые удовлетворяет неравенствам: • Е * < йт-у, те ь .

^ €Ра1М г.т)

Далее, введьм в рассмотрение функционал к" -Ж:

Г Су)- и 1Н Т2 сТ.'вСхЭ

Г 1.. 1 . Г- г ; ^ 1 *

•{X > бб С уЭ } 1 -

При атом, если о с >Ь =о, положим »«>.

Поскольку значение г^сф является в точности значением целевой функции зада1'и МЦВ в точке минимума, то функционал гг будем называть определяющим 'функционалом задачи МЦВ для вершины г.

Для максимального поддерева т. дерева тг с корнем в вершине 1 определяющий функционал задачи ЩВ для вершины 1 будет иметь вид:

F.Cy> _ MIN ZZcT¡*gCx D .

И

Теорема 2

tx V €Ö. <уЭ j €V

* jJ«V. i ' ;

Определяющий функционал задача МЦВ удовлетворяет соотношению динамического ■ программирования:

F Су)- min > Сс .Г. • дСх .Э +F .Сy+vi .33.

Алгоритмы, основанные на уравнении динамического программирования, во многом зависят от способа представления функции, участвующей в указанном соотношении. В <¡§4-0 изло:::огъ; алгоритмы, основанные на различных представлениях функции.

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

R»C а _Ь 3 хСа ,Ь )х. . . хСа ,Ь 3 . а «= [ -<о,-*оо] .bet —оо.+col . i =1 «М. I* • г' г м м i • ' i * * *

Систему гиперпрямоугольников

t

A-{R-Ca\bJ3xCaJ,bJ3x. . . xCaJ ,bJ3y Я j i t 2* г ы* м j = i

будем называть ь -разбиением гиперпрямоугольника ^»ca^bSxCa^b^x. ..хСа",ь®э, если выполняется свойства:

í 2' 2 и' N

1. R° -и R. )-« 1

г' RiO дая всех .............t^

Г í a', bJl ,

3. Ca! ,bJ3 "-j 1 1

1 1 Ъ-г.ьх

еСЛИ aJ-a°

еСЛИ aVa. .

Функции t>i R°-> к будем называть н-Функцией. если существуют ь-разбиение я. области R° и отображения t : я-> вг тате, что дая произвольного 5-еz .... з* r° фс£3-ícr3, где zc R^«*.

Пусть я-{й.>)т1 и я»^}. ь-разбиения гиперпрямоуголь-шка Введем в рассмотрение множество

КСЛ,ЭЬ-<С1,.Р Ц<И1............^¿.¿ф^ау

и некоторую биекш б!Ксл,ЗЬ-> <1 ,г,... где 1л=|ксл,ЗЬ то есть функция & ставит в соответствие поре индексов из множества к натуральное число.

Лею,. Для произвольных ь-разбионкй я и гаперпрямоуголь-

ника система множеств ксЯ,ЗЬ>

является ь-разбиением е°-

Нед н-фуккциями рассматривался следующие поточечные операции:

1) сложение функций

ч>: к°-> и -> в? - н-функцин, а ч>гкм -> к,., - результирующая функция;

2) минимум двух функций

н-функцяи, а V* к" -> результирукцая функция;

3) параллельный перенос функции на вектор с« к" ч>:Я°-> 33 - ч-фуккЦИЯ, а -> фСхз-ТрСг+с^ - результирующая функция. Пусть ©ск°>- класс всех н- функций, определенных на

К И vîsR0 -> R >pCz5 4mlri{ipCz>, 'pCzi)-

множестве r Теорема 3.

Класс замкнут относительно операций

сложения, минимума конечного числа функций и параллельного переноса функции.

Определяющий функционал г. является н-функцивй для любого 1 <з/.

Для вычисления функции динамического программирования в §4 используются представленные в работе *' алгоритмы.

Следствие.

4>Edelsbrunn»r H. A New Approach to Rectangle Intersections. Part II /V Int. J. Comput. Math. - 1083.- Vol. 13.- P.221-22Q.

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

ОССЬ тах иЭМ D IV I Нм~2 1одМ~аСЬ тах и1)),

. . J 1 г ' =* J

i . J 1 » i

где ь- наименьшее общее кратное {>»*|k-i,iy,

D»m»x л.

J

J

Если l- длкна входа задачи МЦВ, ped- полином от длины входа, с- константа не зависящая от размера входа, то имеет мэсто

Теорема 4- Класс задач МЦВ, удовлетворяющий условиям: CU b<pCL3 Cil) М<с

является полиномиально разрешимым.

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

Пусть У -{у}* —МНОЖ9СТВО векторов У «Су*,у2,..,ум)« к".

tp р Р=1 г р р р р

Определим функцию fi* такую, что выполняется следующее свойство:

f Су ) S fCy Э, если у Sy И У ,У «V .

р m ' р гл р п if

Функцию 4>sRM -> будем называть р-фушшией. если VZ€ шм ipC5)-_mln_fCy), где BCz)--(yeY |y>2,z«í ¡RM}.

У €В <3 » ^

Функцию f назовем опорной; функцией, а множество v^ -опорным множеством функции ч>.

Точку pesaR1 назовем максимальным элементом (или кратко максимумом) множества s, если не существует такого, что

p*q И Qip-

Рассмотрим следующие операции над р-функциями: сложение функций; минимум двух функций; параллельный перенос функции на вектор с« rm.

Теорема 5. [| Класс р-функций замкнут относительно операций сложения, минимума конечного числа функций и | параллельного переноса функции.

Следствие. Я Определящий.функционал г. является р-функцией для любого

В приведённом в § 5 алгоритме Б точного решения задачи МЦВ, основанном на описанном представлении, для вычисления функции динамического программирования используется алгоритм определения максимальных относительно частичного порядка элементов множества точек м-мерного пространства, описанный в работе

Оценка сложности алгоритма Б следующая:

. ОССЬ шах и1)гм о |У | Мы"г 1оз""гСЬ щах и1ЭЭ.

I. } ' ' 1 < 1 '

Несмотря на то, что оценка времени работы алгоритма А, приведённого в 54, несколько лучше, алгоритм Б на практике обладает рядом преимуществ (например, в алгоримэ Б значительно меньше объектов с одинаковыми весами, так как не происходит дробление объектов), которые позволяет использовать в зависимости от индивидуальной задачи МЦВ наряду с алгоритмом А алгоритм Б. •

Анализ оценок алгоритмов А и Б показывает, что они могут быть неприемлемыми для решения некоторых индиввдуальных задач (в частности, когда число заданных на входа поддеревьев достаточно велико) из-за больших временных затрат.

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

ОСрИ О |У|>.

Переменная р обратно пропорциональна величине шага решетки.

Препарата Ф., Шеймос М. Вычислительная геометрия: введение. ЙГгМир. - 1989. - 478с.

Поэтому шаг разбиения необходимо выбирать исходя из параметров задачи МЦВ, учитывая то, что хотя увеличение шага уменьшает временные затраты, но при. этом уменьшает точность решения задачи.

На практике возникает необходимость быстрого приближённого (оценочного) решения задачи МЦВ. Такое решение может быть построено из осново решения задачи ОЦ или 0.

ЗАДАЧА (0) ОРДИНАРНОГО РАСЧЕТА СЕЧЕКИИ СЕГМЕНТОЗ р-СЕТИ:

(0)

.УН. -> ш! п

"Гст 1 • V

1« РЩЫ г, 1)

« К . ,

V 4- * Г

где мноявсгво действительных положительных чисел.

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

Пусть <\"<Сг-~ множество отрезков, составляющих, честь рс-сбти, соединяющую 1-й функциональный элемент с соответствующей выходной " площадкой, где множество отрезков в , у^з, ч»1,г - координаты на

плоскости начальной и конечной точек З-го отрезка для 1-го Функционального элемента.

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

Эскизом топологии р-сети называется такое множество что-для всвх.1« выполняются соотношения:

а> <;-<>+*'

б> <ГЯ**

в)

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

.1™«*, ^ ^справедливо следующее:

1> 2)

где а - расстояние в принятой метрике. Через т(6) обозначим тожество всех Реализаций топологии о. Кроме этого введем - множество сечений всех

г

сегментов дерева т^.

Так как мы полагаем, что реализация топологии т^е т (с) не фиксирована (будем писать: ^стэ ,естг:>, Раъык.ист^), то вместо задачи 0 можно рассматривать аналогичную ей задачу расчета сечоний сегментов р-сети, в которой переменными являются не только но и т :

* г

ЗАДАЧА. (ОНТ) ОРДИНАРНОГО РАСЧЕТА СЕЧЕНШ СЕГМЕНТОВ Р-СЕТИ С НЕФИКСИРОВАННОЙ ГОПОЛОГИЕП:

(ОНТ)

•FCW.T Э- У

F *—

1 w -> min

/»1.1./V. < u., J« L СТ

^ I I I J г г *

i epathi г , j i < T r > W. € R , T «-(G),

'. <eV СТ Э,

г г 1

реализацией топологии g называется дерево

T°«r(G) таКОв, ЧТО PatMr,i] f) Pathtr, jJ«0 при l*J VI, J e

Теорема g

Максимальное дерево т<гг (g) и множество w»<G4.... ft^ где Я- ) ! (ДД./и., i «Pathl г, J i , J «= L достэ-

1 kepatbcr,ji 1 J . r

вляот оптимальное решение задаче ОНТ.

Из Теоремы 6 следует, что для задачи 0, удовлетворяющей условию:

Условие 1; V J?k-const Lr

мохет быть найдено точное решение за линейное от размера входа время.

В работе в> предложен линейный алгоритм решения задачи 0. Однако область применения этого алгоритма ограничена приведенным ниже условием.,

УСЛ0ВИ6 2: uk-const Vke L^.

Алгоритма, представленные в 57, основывагтся на приведении обдай задачи 0 либо к Условию 1, либо к Условию 2.

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

1. Азарйнок A.C., Нлебансвич Д.М., Крикун B.C., Метельский H.H., Наумович П.А., Руденко А.Г., Соболевский П.И., Степанец В.Я. Автоматизация проектирования СБИС. Метод иерархической генерации эскиза топологического чертежа на основе бгЗлиотеки фиксированных разногабаритных блоков. -ггн., 1988. - 36с. - (Препринт АН БССР. Ин-т математики; № ■ 16(32С)}.

2. АзарВнок A.C., Рудонко А.Г., Степанец В.Я. Два метода расчЗта шин питания к земли БИС/СБИС // Бесц1 АК БССР. Сер. <51з.-мат. навук. - 1980. - J6 5. - С,93-100.

3. Рудекко А.Г. 0 точном целочисленном рошении задачи оптимизации сечений сегментов вин питания и земли БИС/СБИС // Весц! Ali БССР. Сер. ф1з.-цаг. ноаук. - 1990. - R 3. ■• С.103-103.. "

4. Руденко А-Г. Математические' модели и методы решения задачи расчета сечений шин питания БИОСБКС. - !.ui., 1391. -4G с.

- (Препринт / АН БССР. йн-т математики; JBj3(Vß5)).

Chowdhury S., Breuer M. An OCn) Algorithm for Width Determination of Power .'Ground Routers for VLSI Circuits ✓✓Integration Letter. - 1986. - N 4. - P. 345-353.