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

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

Аюпов Андрей Борисович

Исследование и разработка методов размещения стандартных ячеек с явной оптимизацией задержек и трассируемости нанометровых СБИС

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

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

Москва-2008

003451528

Работа выполнена в ЗАО «Интел А/О»

Научный руководитель: доктор технических наук, доцент А.М. Марченко

Официальные оппоненты: доктор технических наук, профессор Г.Г. Казеннов

кандидат технических наук, И.А. Сырцов

Ведущая организация: ГУЛ НПЦ «ЭЛВИС»

Защита состоится 19 ноября 2008 года в И час. 00 мин. на заседании совета Д 002.078.01 по защите докторских и кандидатских диссертаций в Учреждении Российской академии наук Институте проблем проектирования в микроэлектронике РАН (ИППМ РАН) по адресу: 124681, г.Москва, ул. Советская, д.З.

С диссертацией можно ознакомиться в библиотеке ИППМ РАН, с авторефератом диссертации - на сайте ИППМ РАН www.IPPM.ru.

Автореферат разослан 18 октября 2008 г.

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

кандидат технических наук

совета Д 002.078.01,

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность работы

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

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

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

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

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

• разработка методов оптимизации трассируемости в процессе размещения стандартных ячеек,

• разработка методов оптимизации быстродействия схемы в процессе размещения стандартных ячеек,

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

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

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

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

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

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

Реализация.

На базе предложенных алгоритмов разработан комплекс программ для оптимизации производительности и трассируемости схемы на этапах глобального и детального размещения в программном продукте "Synergy". Разработанные программы внедрены в ЗАО "Интел" для проектирования сложных схем, которые имеют жесткие ограничения на быстродействие или проблемы с трассируем остью.

Практическая значимость работы.

Использование разработанных методов и реализованных программ при проектировании реальных компонент высокопроизводительных микропроцессоров внутри компатга «Интел» показали значительное улучшения таких параметров схем, как быстродействие и трассируемость, в сравнении с существующими промышленными пакетами проектирования СБИС. Основные теоретические результаты используются в учебных процессах в МФТИ и МГУ им. М.В.Ломоносова.

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

• Great Lakes Symposium on VLSI (Orlando, USA, 2008г., 1 доклад)

• East-West Design and Test Workshop (г. Сочи, 2006 г., 1 доклад)

• International Workshop on Logic and Synthesis (Anaheim, USA, 2004r., 1 доклад)

• Всероссийская научно-техническая конференция "Проблемы разработки перспективных микро- и наноэлектронных систем" (Москва, 2008г., 1 доклад)

• Международная конференция AIS/CAD '08 (пос. Дивноморское, Краснодарский край, 2008г., 1 доклад)

Публикации. Результаты диссертации отражены в 7 публикациях.

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность темы, сформулирована цель работы, показана научная новизна и практическая значимость полученных результатов, раскрыта структура диссертации.

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

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

становится невозможно развести все необходимые соединения между элементами по коммутационным слоям.

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

Типичный маршрут разработки ИС включает этапы системного, функционального, логического и топологического проектирования. На системном этапе формулируются требования к функциональным характеристикам, разрабатываются алгоритмы, реализуемые в ИС и структурные схемы. Алгоритмы обычно представляют собой код на языке проектирования аппаратуры (HDL - Hardware Description Language) и выражают поведенческий аспект проектируемого изделия. Основными HDL языками в современных САПР являются VHDL и Verilog. Поведенческие описания представляют собой исходное задание на функциональное и логическое проектирование. Этап функционально-логического проектирования поддерживаются в САПР подсистемами синтеза и моделироваия. Одной из наиболее ответственных и трудно формализуемых проектных процедур является блочный синтез, в процессе которого выполняется распределение операций алгоритма по временным тактам и по функциональным блокам аппаратуры. Тем самым определяются структура схемы на уровне регистровых передач (RTL - Register Transfer Level), типы блоков (комбинационные или последовательностные), реализуются распараллеливание и конвейеризация вычислений. Полученное RTL -описание на языке HDL далее поступает на этап логического синтеза, где логические выражения в схеме минимизируются и отображаются в вентильную структуру, построенную на элементах из стандартной

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

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

Простой и в то же время эффективной оценкой длины проводника является полупериметр охватывающего цепь прямоугольника (half rectangular perimeter - HRPM). Известно, что для двух- и трех- контактных цепей полупериметр охватывающего прямоугольника совпадает с длиной минимального дерева Штейнера, которое используется во многих алгоритмах трассировки. Поэтому сумма полупериметров охватывающих прямоугольников по всем цепям является наиболее распространенной целевой функцией в алгоритмах размещения. Это также связано с тем, что суммарная длина проводников коррелирует со многими параметрами схемы: производительностью, потребляемой мощностью и качеством трассировки.

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

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

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

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

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

Cosí = а, ■ СI + а2 - С2 + и3 ■ СЗ + а , ■ С4 + а5 ■ С'5 минимум, (1) включающей в себя следующие компоненты:

С1* - суммарная длина проводников, посчитанная по дереву Штейнера, С2 -штрафная функция для удаления перекрытий между ячейками, СЗ -штрафная функция для оценки трассируемости, С4- функция оценки быстродействия схемы, С5 - штрафная функция для полного удаления перекрытий между ячейками и расстановки ячеек в ряды.

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

Рисунок I. Эволюция штейнеровского дерева: а.

Незначительное перемещение ячеек и штейнеровских точек,

б. Значительное перемещение ячеек и штейнеровских точек,

в. Обновленное дерево

В данной главе предложена модификация штрафной функции перекрытий между ячейками из алгоритма АР1асе (Кап!^ 2004) - С2*, которая позволяет эффективно размещать ячейки в условиях невысокой плотности. Известная ранее функция из алгоритма АР1асе распределяет

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

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

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

С3 = £ к

(

тах

V. V i

\

Ж)

где RDh , Ьк) и RDV {si, bk) - вклад сегмента цепи ,v( в плотность трассировки над клеткой Ък по вертикальному и горизонтальному направлениям. Caph(bk) и Capv(bk)- горизонтальная и вертикальная пропускная способность клетки Ьк соответственно.

Для вычисления загрузки клетки двухконтактной цепью si используется известная вероятностная оценка (Yang 2001): l(s)

RDis,) =--'-, где l(s,)- относительная длина цепи s,,

bbox _area{si)

выраженная в количестве клеток, которые она занимает, и bbox_area{Sj) -количество клеток, попадающих в охватывающий сегмент sl прямоугольник.

Обозначив за (лг,,,^,) и (лг12, _у, 2) координаты терминалов сегмента , а за » и А - ширину и высоту клетки регулярной решетки соответственно, в диссертационной работе определяются оценки для загрузки клеток, которые попадают под охватываемый сегмент прямоугольник для горизонтальных и вертикальных направлений раздельно:

~ х, 11

Щ, ,Ьк) = ,Ьк). --

w

X; 1 X,

W

-+1

У ¡а-У ¡л

h

+ 1

RDv(si,bi) = SAB(si,b

|У«.2 ~ >Vil h

Xj 9 Xj

w

-+1

У1.1-УЧ h

+ 1

где

1, охватывающий сегмент s: SAB(Sj,bk)= прямоугольник покрывает bk (2)

О, иначе

Из определения функции (2) следует ее разрывность, и для задачи оптимизации требуется ее непрерывность и сглаживание. Используя координаты терминалов сегмента s( и координаты (х,, у,) центра клетки Ьк, функция SAB была определена следующим образом:

SAB(x:1, уц, ха, д 2, х„у,) = Сот{Хц, 2, ) • Coin(yiX, yL2, у,)

где

(1, если min(x, ,,xi2)<x, < шах(дг,,,xia)

(3)

О, иначе

С целью приближения функции (3) непрерывной функцией, было введено следующее выражение для функции Coin :

Coin(x) ,, X/ 2, X,) =

\x, -A)| Jx, ~(xM +A)| А

|дс, ~(xi2 -A)| |jc, ~(xi 2 +A)|

Параметр А используется для контроля над точностью приближения. Рис.2, иллюстрирует графики функций /(х,) = Со/я(0.1,0.2,xt) с параметром А = 0.02 , вычисленных по формуле (3). формуле (4) и формуле (4) со следующей сглаженной функцией абсолютного значения, введенного в диссертационной работе:

( (хХ) (

abs(jc) = 77 ■ log 1 + ехр — +?;Tog 1 + ехр

/ "Л х

V Ч J

Рисунок 2. График функции Coin.

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

межсоединений. Также для входов комбинационной части схемы (входы схемы и выходы элементов памяти) заданы действительные, а для выходов (входы элементов памяти и выходы схемы) требуемые значения времени прибытия сигналов. Задача временного анализа - определить, удовлетворяет ли логическая и топологическая реализации схемы заданным временным ограничением (ограничениям на производительность). Для этого для каждого выхода комбинационной части схемы е Е оценивается резерв (запас) времени slackfe). Величина резерва времени может быть вычислена в любой точке прохождения сигнала в схеме, как разница между требуемым RT (required time) и действительным AT (arrival time) временами прибытия сигнала, посчитанными в этой точке. Значения AT в схеме вычисляются путем их распространения от входов комбинационной части схемы к их выходам, накапливая задержки в элементах и проводниках. Отрицательное значение резерва времени показывает величину запаздывания сигнала по отношению к ограничению на производительность схемы.

Для оптимизации быстродействия схемы в задаче размещения функция С4 определена следующим образом:

С4 = £ тЫО,-s/асЦе,)), (5)

е,е Е

где

Е - множество выходов комбинационных путей в схеме (выходы схемы и входные терминалы элементов памяти).

slack{e,) - функция резерва времени, как функция от размещения ячеек в выходе .

Все функции в маршруте вычисления резерва времени slack(ei) являются функциями, зависящими от координат хе X , так как выражаются через длины межсоединений. Основной идеей предложенного метода является использование функциональных зависимостей временных

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

Для прошвольной функции 0(а, И) от двух аргументов а и

можно построить оператор 0(f,g) = h на функциях f(x),g(x), где Л(х)-0(/~(x),g(x)). Например, для задержки в проводе как функции от длины сегмента (segment _length ) и емкости сегмента (segment _/oat/): Segment _ Delay(segment __ length, segment _ load) = = r ■ segment _ length ■ segment __ load

можно построить соответствующий оператор на функциях segmentjfength и segment loacl от вектора х е X:

Segment_Delay( segment_length,segment_load ) = f, где f(x) = r- segment_length(x) ■ segment_Ioad(\).

Из формулы вычисления производной сложной функции:

(V0)(f,g) = 0,/Vf + 0gVg^ (6)

следует, что для вычисления значения и вектора градиента оператора 0(f,g) в точке хе X необходимы только значения и вектор градиента функций /(х) и g(x) в точке х, и нет необходимости знать символическую форму этих функций. Имея это в виду, было предложено использовать вспомогательную структуру данных PFunc, которая будет описывать произвольную функцию в заданной точке хе X через ее значение и вектор градиента.

Пусть Ff является объектом типа PFunc и /- функция, которая описана с помощью F, в заданной точке х. Тогда Ff это кортеж,

состоящий из значения функции /(х) и всех частных производных -—(х) в

дхк

точке х. Введем следующее обозначение для Рг:

(

КП

Эх,' Эх2' ' дхп

Рассмотрим пример вычисления значения и градиента функции задержки проводника, соединяющего две ячейки, по упрощенной формуле с1 = К-С , где Я и С - паразитные сопротивление и емкость проводника. Рассматривая для простоты одномерную оптимизацию, введем координаты ячеек и х2 ■ Пусть в традиционном маршруте временного анализа следуют такие вычисления: длина проводника / = х2 -х,, затем паразитные сопротивление Я = г • I и емкость С = с -1, а затем задержка с1 = Я-С , где г и с погонные сопротивление и емкость металлического слоя проводника. В диссертационной работе предлагается использовать в расширенном алгоритме временного анализа не значения этих функций, а РРипс -представления соответствующих функций. Для этого для независимых переменных данного примера х1 и х2 вводятся их РРипс -представления -

^ = (Х|,[1,0]), = (х2,[0,1]) согласно определению РРипс. Тогда вместо вычисления длины проводника 1 = х2-х1, вычисляется РРипс -представление для функции длины как разность двух РРипс -представлений: Р) = РХг - , а паразитные емкости и сопротивления как произведение

РРипс -представление длины сегмента на константу: РК-г-Р1 и Рс - с ■ !•). И наконец задержка с! = Я- С представлена как Р^ = РК ■ Рс. В данном примере были использованы такие операции, как «разность» двух РРипс, «произведение» двух РРипс и «произведение» РРипс и константы. В

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

Таким образом, было предложено расширить традиционный алгоритм временного анализа таким образом, чтобы использовать новое представление РРипс функций вместо их значений, используемых в алгоритме. Тогда, такие характеристики, как паразитные емкости и сопротивления проводников, их задержки, задержки ячеек, действительное и требуемое время прибытия сигнала и их разница (Б1аск(е,)) вычисляются в предложенном алгоритме временного анализа рекурсивно по формуле (6) как функции независимых переменных задачи размещения. Далее, РРипс -представление, а значит значение и вектор градиента, вычисляется для функции С4 согласно определению (5).

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

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

¡^Глобальное размещение ] ячеек_\

Аналитическая легализация рззмеьценйя

Удаление перекрытой !

между ячейками

РД1

Расстановка ячеек в ряды I

Дискретная легализация | размещения 1

Легальное размещение ^

ячеек

Рисунок 3. Блок-схема предложенного алгоритма легализации

размещения

Для этого предлагается ввести в целевую функцию аналитического алгоритма размещения функцию для полного удаления перекрытий между ячейками и расстановки ячеек в ряды. Такая штрафная функция С5 представлена следующей суммой:

С5 = С50 + С5Д

где С50 - функция, штрафующая перекрытия между ячейками, С5Р -функция, штрафующая размещение ячеек вне стандартных рядов.

Ячейка <■■

Рнсунок 4. Обозначения для геометрии ячейки

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

прямоугольной стандартной ячейки ск . Пусть ы'к, Ик - это ширина и высота ячейки соответственно. Тогда верхний правый угол ячейки задается координатами хк, ук, где x¡ =хк +\\>к и у"к = ук +Ьк. Прямоугольная форма стандартной ячейки может быть задана через две проекции^ = [хЛ.,х"к] и =[->^->'¡1 на оси ОХ, ОУ соответственно. Сначала определим длину пересечения двух отрезков вхк =[хк,х*к] и л* = [х„,,х*,]. Обозначим через ¡еп(зк,.ч*п) функцию от двух переменных хк.хт, которая определяет длину перекрытия двух отрезков Далее определены три вспомогательные

функции /о(х;^), /г/(х;^) и ¿ф^,^):

|х — х<, если х, < х < х1

О, иначе 19

hi(x;sl) = \ (8)

О, иначе

1,еслихт <хк ихк <хт be{sl,sl) = \ (9)

[О, иначе

Используя функции (7), (8) и (9) были описаны шесть возможных вариантов расположения двух отрезков sxk,sxm относительно друг друга и

предложено выражение для функции len(sxk,sxm), которое обобщает эти варианты (10). Описан метод сглаживания выражения (10).

len(sxk,sxn) =---х

с2-be(sxk,sxm)-be(sxm,sxk))

x{[hi(xn-sxk)+lo(x'myk)-(xk -xk)be(sxm,sxk)]+ (10)

+ [hi(xk; sxm)+lo(xk; sxm) - (x*m - xm) be(sxk ,.v,lj]} Подобным образом вычисляется длина перекрытия двух отрезков - проекций ячейки на ось OY. Далее, оценивается площадь перекрытия двух ячеек следующей функцией:

area{ck,cm) = lenx(sxk,sxm) leny(syk,sym) Тогда функция С50 будет приближена следующим выражением: С5о= Y,{area(ck,cm)}

all pairs {ск,ст}

Для размещения ячеек в дискретные ряды была выбрана периодическая функция синуса. Выражение для функции С5,; имеет следующий вид:

cecells ^

Г /„ ,. ЛЛ

, . Ък 2ку 1 + sin — +-—

V I 2 acrh

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

г/г - высота ряда.

В пятой главе раскрыта структура реализации на языке С++ разработанных алгоритмов. Была построена иерархия классов для создания интегрированной системы для аналитического размещения, объединяющей в себе пакет оптимизации ТАО и пакет для определения целевой функций для оптимизации.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

Результаты тестирования предложенных методов оптимизации показывают эффективность решения поставленных задач для промышленных схем размерностью до 25 тысяч элементов, спроектированных на технологии 45нм:

а. Трассируемость улучшена на 16% в среднем в сравнении с

размещением с традиционным критерием оптимизации - суммарной длиной межсоединений.

б. Быстродействие схемы увеличено на 14% в среднем в сравнении с

промышленным маршрутом топологического проектирования, используемого в Интел.

в. Деградация параметров промышленных схем во время традиционной

легализации сокращена с 7.6% до 0.7% для суммарной длины проводников, с 19% до 2% для трассируемости и с 68% до 14% для временных параметров в среднем.

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

1. Аюпов А.Б. Легализация размещения как задача нелинейной оптимизации // III Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем - 2008»: сб. научн. тр. / под общ. ред. А.Л. Стемпковского". -М.: ИППМ РАН, 2008. - С. 126-131.

2. Аюпов А.Б., Крагинский Л.М. Оптимизация быстродействия СБИС в аналитическом алгоритме размещения стандартных ячеек // Труды конференции AISWCAD-2008.-2008.-Т. 1.-С. 151-158.

3. Аюпов А.Б., Марченко A.M. 2008. Метод оптимизации трассируемости в аналитическом алгоритме размещения // Информационные технологии. -2008. - Вып. 2. - С. 12-17.

4. Ayupov A., Kishinevsky М. and Marchenko A. Separating retiming from the initial states // Proceedings of the 2005 International Workshop on Logic ad Synthesis.-2005.-P. 65-72.

5. Ayupov A., Marchenko A. and Tiourin V. An analytical approach to placement legalization // Proceedings of the 2008 ACM Great Lakes Symposium on VLSI. -2008. - P. 167-170.

6. Ayupov A., Marchenko A. Congestion-driven analytical placement // Proceedings of the 2006 East-West Design and Test International Workshop. -2006.-P. 143-148.

7. Ayupov A., Kraginskiy L. A novel timing-driven optimization using smooth timing model // Proceedings of the East-West Design & Test Symposium. -2008.-P. 137-140.

Введение.

Глава 1. Современные проблемы автоматизации проектирования топологии СБИС

1.1 Технологические тенденции и конструкторские требования.

1.2 Основные этапы решения задачи размещения.

1.3 Методы глобального размещения.

1.3.1. Конструктивные методы размещения.

1.3.2. Итеративные методы размещения.

1.3.3. Алгоритмы размещения с конкурса ISPD-2005.

1.4 Результаты сравнения на ISPD-2005.

1.5 Критерии качества в алгоритмах размещения.

1.6 Методы легализации размещения.

Выводы.

Глава 2. Общая постановка задачи.

2.1 Постановка задачи.

2.2 Сглаживание базовых функций.

2.3 Штейнеровская модель цепи и длина трасс.

2.4 Особенности в условиях пониженной плотности размещения.

Выводы.

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

3.1 Метод оптимизации трассируемости в алгоритме размещения.

3.2 Метод оптимизации быстродействия в алгоритме размещения.

Выводы.

Глава 4. Аналитический подход к легализации размещения.

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

4.2 Алгоритм легализации размещения ячеек.

Выводы.

Глава 5. Программная реализация алгоритма размещения и экспериментальные результаты.

5.1 Программная реализация алгоритма оптимизации размещения.

5.2 Результаты тестирования оптимизации трассируемости в аналитическом алгоритме размещения.

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

5.4 Методы ускорения аналитической легализации размещения и результаты тестирования.

5.5 Метод динамического изменения весов в целевой функции.

Выводы.

Актуальность работы.

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

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

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

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

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

• разработка методов оптимизации трассируемости в процессе размещения стандартных ячеек,

• разработка методов оптимизации быстродействия схемы в процессе размещения стандартных ячеек,

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

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

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

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

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

Реализация.

На базе предложенных алгоритмов разработан комплекс программ для оптимизации производительности и трассируемости схемы на этапах глобального и детального размещения в программном продукте "Synergy". Разработанные программы внедрены в ЗАО "Интел" для проектирования сложных схем, которые имеют жесткие ограничения на быстродействие или проблемы с трассируемостью.

Практическая значимость работы.

Использование разработанных методов и реализованных программ при проектировании реальных компонент высокопроизводительных микропроцессоров внутри компании «Интел» показали значительное улучшения таких параметров схем, как быстродействие и трассируемость, в сравнении с существующими промышленными пакетами проектирования СБИС. Основные теоретические результаты используются в учебных процессах в МФТИ и МГУ им. М.В.Ломоносова.

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

• Great Lakes Symposium on VLSI (Orlando, USA, 2008г., 1 доклад)

• East-West Design and Test Workshop (г. Сочи, 2006 г., 1 доклад)

• International Workshop on Logic and Synthesis (Anaheim, USA, 2004г., 1 доклад)

• Всероссийская научно-техническая конференция "Проблемы разработки перспективных микро- и наноэлектронных систем" (Москва, 2008г., 1 доклад)

• Международная конференция AIS/CAD '08 (пос. Дивноморское, Краснодарский край, 2008г., 1 доклад)

Публикации. Результаты диссертации отражены в 7 публикациях.

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

Выводы

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

2. Представлены результаты оптимизации трассируемости в аналитическом алгоритме размещения в сравнении с алгоритмом, оптимизирующим суммарную длину проводников. Проведен сравнительный анализ, который показал, что предложенная оптимизация позволяет улучшить трассируемость на 16% в среднем по сравнению с традиционным маршрутом для набора схем LGSynth и промышленных схем, спроектированных на технологии 45нм.

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

4. Описан метод ускорения алгоритма аналитической легализации размещения, позволяющий сократить вычислительную сложность с квадратичной до линейной. Предложенный метод легализации в сравнении с традиционной легализацией размещения показал на промышленных схемах, спроектированных на технологии 45нм, следующие результаты: a. Деградация параметров схемы во время традиционной легализации сокращена с 7.6% до 0.7% для суммарной длины проводников, с 19% до 2% для трассируемоети и с 68% до 14% для временных параметров. b. Оптимизации суммарной длины проводников во время аналитической легализации размещения позволяет получить улучшение по этой метрике на 6%.

Заключение

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

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

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

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

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

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

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

Результаты тестирования предложенных методов оптимизации показывают эффективность решения поставленных задач для промышленных схем размерностью до 25 тысяч элементов, спроектированных на технологии 45нм: а. Трассируемость улучшена на 16% в среднем в сравнении с размещением с традиционным критерием оптимизации - суммарной длиной межсоединений. б. Быстродействие схемы увеличено на 14% в среднем в сравнении с промышленным маршрутом топологического проектирования, используемого в Интел. в. Деградация параметров промышленных схем во время традиционной легализации сокращена с 7.6% до 0.7% для суммарной длины проводников, с 19% до 2% для трассируемости и с 68% до 14% для временных параметров в среднем.

1. http://www.itrs.net/Links/2005ITRS/Home2005.htm2. http://www.itrs.net/Links/2007ITRS/Home2007.htm

2. Sai-Halasz G. А. 1995. Performance trends in high-end processors. Proceedings of IEEE. Volume 83. Issue 1. pp. 20-36.

3. Sylvester D., Keutzer K. 2000. A global wiring paradigm for deep submicron design. IEEE Computer-Aided Design of Integrated Circuits and Systems. Volume 19. Issue 2. pp. 242-252

4. Норенков И.П. «Средства автоматизации проектирования в электронике» (обзор), http://rk6.bmstu.ru/electronicbook/develop/ecad/init.htm

5. Donath W. 1980. Complexity theory and design automation. In Proceedings of the 17th Design Automation Conference, pp. 412-419.

6. Fukunaga K., Yamada S., Stone H., and Kasai T. 1983. Placement of circuit modules using a graph space approach. In Proceedings of the 20th Design Automation Conference. 465-473.

7. Hanan M., and Kurtzberg J. M. 1972a. Placement techniques. In Design Automation of Digital Systems, 1, M A. Breuer, Ed. Prentice Hall, Englewood Cliffs, N. J., Chap. 5, pp. 213-282

8. Kambe Т., Chiba Т., Kimura S., Inufushi T, Okuda N., and Nishioka, I. 1982. A placement algorithm for poly cell LSI and its evaluation. In Proceedings of the 19th Design Automation Conference. PP 655-662

9. Kang S. 1983. Linear ordering and application to placement. In Proceedings of the 20th Design Automation Conference, pp. 457-464.

10. Kozawa T , Terai H., Ishii Т., Hayase M., Miura С., Ogawa Y, Kishida K., Yamada N., and Ohno Y. 1983. Automatic placement algorithms for high packing density VLSI. In Proceedings of the 20th of the Design Automation Conference, pp. 175-181

11. Magnuson W. G. 1977. A comparison of constructive placement algorithms. IEEE Region 6 Conf, Rec. 28-32.

12. Persky G., Deutsch D. N., and Schweikert D. J., 1976. LTX: A system for the directed automatic design of LSI circuits. In Proceedings of the 13 th Design Automation Conference, pp. 399-407.

13. Palczewski, 1984. Performance of algorithms for initial placement. In Proceedings of the 21st Design Automation Conference, pp. 399-404

14. Kernighan B. W., Andlin S. 1970. An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49, 2, 291-308.

15. Fiduccia С. M., and Mattheyses, R. M. 1982. A linear-time heuristic for improving network partitions. In Proceedings of the 19th Design Automation Conference, pp. 175-181.

16. Johannes F. M., Just К. M., and Antreich K. J. 1983. On the force placement of logic arrays. In Proceedings of the 6th European Conference on Circuit Theory and Design, pp. 203-206.

17. Quinn N. R. 1975. The placement problem as viewed from the physics of classical mechanics. In Proceedings of the 12th Design Automation Conference, pp. 173-178.

18. Quinn N. R., and Breuer M. A. 1979. A force directed component placement procedure for printed circuit boards. IEEE Trans. Circuits Syst. CAS-26, 377-388.

19. Chyan D., and Breuer M. A. 1983. A placement algorithm for array processors. In Proceedings of the 20th Design Automation Conference, pp. 182-188.

20. Eisenmann H., and Johannes F.M. 1998. Generic global placement and floorplanning. In Proceedings of the Design Automation Conference. pp269-274.

21. Goto S., and Kuh E. S. 1976. An approach to the two-dimensional placement problem in circuit layout. IEEE Trans. Circuits Syst. CAS-25, 4, 208-214.

22. Kirkpatrick S., Gelatt С D , and Vecchi M P. 1983. Optimization by simulated annealing. Science 220.4598 (May), 671-680.

23. Sechen C. 1986. The Timber Wolf 3.2 Standard Cell Placement and Global Routing Program. User's Guide for Version 3.2, Release 2

24. Sechen C. 1988. VLSI Placement and Global Routing Using Simulated Annealing. Kluwer, В. V., Deventer, The Netherlands

25. Sun W.-J., Sechen C. 1993. Efficient and effective placement for very large circuits. In Proceedings of the 1993 IEEE/ACM international conference on computer-aided design, pp. 170-177

26. Wang M., Yang X., Sarrafzadeh M. 2000. DRAGON2000: Standard-cell placement tool for large industry circuits. In Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, pp. 260-263

27. ISPD 2005: http://www.sigda.org/ispd2005/contest.htm

28. Taghavi Т., Yang X., Choi B.K. 2005. Dragon2005: large-scale mixed-size placement tool. Proceedings of the 2005 international symposium on Physical design, pp. 245-247

29. Viswanathan N., Pan M., Chu C. FastPlace: an analytical placer for mixed-mode designs. Proceedings of the 2005 international symposium on Physical design, pp. 221-223

30. Ни В., Zeng Y., Marek-Sadowska M. mFAR: fixed-points-addition-based VLSI placement algorithm. Proceedings of the 2005 international symposium on Physical design. 239-241

31. Roy J., Papa D., Adya S., Chan H., Ng A., Lu J., Markov I. 2005. Capo: robust and scalable open-source min-cut floorplacer. Proceedings of the 2005 international symposium on Physical design. 224 226

32. Agnihotri A., Ono S., Madden P. 2005. Recursive bisection placement: fengshui 5.0 implementation details Proceedings of the 2005 international symposium on Physical design 230 232

33. Chen Т., Hsu Т., Jiang Z., Chang Y. NTUplace: a ratio partitioning based placement algorithm for large-scale mixed-size designs Proceedings of the 2005 international symposium on Physical design 236-238

34. Takahashi K., Nakajima K., Terai M. and Sato K. 1995. Min-Cut Placement With Global Objective Functions for Large Scale Sea of Gates Arrays", IEEE Transactions on Computer-Aided Design, pp. 434-446

35. Caldwell A., Kahng A., Markov I. 2000. Design and Implementation of Move-Based Heuristics for VLSI Hypergraph Partitioning. ACM on Experimental Algorithms, vol. 5.

36. Caldwell A, Kahng A., Markov I. 2000. Improved Algorithms for Hypergraph Bipartitioning. ASPDAC 2000. pp. 661-666

37. Kahng A., Reda S., Wang Q. 2005. APlace: a general analytic placement framework. Proceedings of the 2005 international symposium on Physical design. 233 -235

38. Chan Т., Cong J., Romesis M., Shinnerl J., Sze K., Xie M. 2005. mPL6: a robust multilevel mixed-size placement engine Proceedings of the 2005 international symposium on Physical design. 227 229

39. Murty K., YuF.-T. 1999. Linear Complementarity, Linear and Nonlinear Programming. Internet Edition.http://ioe.engin.umich.edu/people/fac/books/murtv/linear complementarity webbooи

40. W. Naylor et al. 2001. Non-Linear Optimization System and Method for Wire Length and Delay Optimization for an Automatic Electric Circuit Placer. US Patent 6301693

41. Ruehli A., Wolff Sr. P., Goetzel G. 1977. Analytical power timing optimization techniques for digital systems. In Proc. of the 14th ACM/IEEE Design Automation Conference, pp. 142-146

42. Sapatnekar S. S. and Kang S. M. 1993. Design Automation for Timing-Driven Layout Synthesis. Kluwer Academic Publishers, Boston, MA.

43. Nam G.-J., Alpert C., Villarrubia P., Winter В., Yildiz M. 2005. The ISPD2005 placement contest and benchmark suite. Proceedings of the 2005 international symposium on Physical design, pp. 216 220

44. Kahng A. and Wang Q. 2004. Implementation and Extensibility of an Analytical Placer. Proceedings of the 2004 international symposium on Physical design, pp. 18-25

45. Viswanathan N., Chu C. 2005. FastPlace: Efficient Analytical Placement using Cell Shifting, Iterative Local Refinement, and a Hybrid Model. IEEE transaction on CAD of integrated circuits and system. Vol. 24. No. 5. pp. 722-733.

46. Chan Т., Cong J., Sze K. 2005. Multilevel Generalized Force-directed Method for Circuit Placement. Proceedings of 2005 International Symposium on Physical Design, pp. 185-192.

47. Adya S., Yildiz M., Markov I. et. al. 2003. Benchmarking For Large-scale Placement and Beyond. Proceedings of 2003 International Symposium on Physical Design, pp. 95-103

48. Chen T.-C., Jiang Z.-W, Hsu T.-C., Chen H.-C., and Chang Y.-W. 2006. A High-Quality Mixed-Size Analytical Placer considering Preplaced Blocks and Density Constraints. Proceedings of 2006 ICCAD. pp. 187-192.

49. Hou W, Yu H, Hong X., Cai Y., Wu W., Gu J.and Kao W. H. 2001. A new congestion-driven placement algorithm based on cell inflation. Proc. of Asia South Pacific Design Automation Conference, pp.605-608

50. Yang X., Kastner R.and Sarrafzadeh M. 2001. Congestion reduction during placement based on integer programming. Proc. Int. Conf. on Computer-Aided Design, pp.573-576.

51. Breuer U.and Rohe A. 2002. An effective congestion-driven placement framework. Proc. Intl. Symp. on Physical Design, pp.6-11.

52. Parakh P.N., Brown R.B.and Sakallah K.A. 1998. Congestion driven quadratic placement. Design Automation Conference, pp.275-278.

53. Liu Q., Marek-Sadowska M. A. 2005. Congestion-driven Placement Framework with Local Congestion Prediction. Proceedings of the 2005 Great Lakes Symposium on VLSI, pp.488-493.

54. Sham C., Young E. 2005. Congestion prediction in early stages. Proceedings of SLIP'05.

55. Rajagopal К., Cao Т., Shaked Т., Parasuram Y., Halpin B. 2003. Timing Driven Force Directed Placement with Physical Net Constraints. Proc. of Int. Symp. on Physical Design, pp. 60-66.

56. Yang X., Choi B.K., Sarrafzadeh M. 2002. Timing Driven Placement using Design Hierarchy Guided Constraint Generation. Proc. of Int. Conf. on Computer Aided Design, pp. 177-180.

57. Marek-Sadowska M., Lin S.P. 1989. Timing-Driven Placement. Proc. of Int. Conf. on Computer Aided Design, pp. 94-97

58. Ou S.L., Pedram M. 1990. Timing-driven Placement Based on Partitioning with Dynamic Cut-net Control. Proc. of IEEE Design Automation Conference.

59. Ren H., Pan D.Z., Kung D.S. 2004. Sensitivity Guided Net Weighting for Placement Driven Synthesis. Proc. of Int. Symp. on Physical Design, pp. 10-16.

60. Srinivasan A., Chaudhary K., Kuh E. S. 1991. RITUAL: Performance driven placement algorithm for small cell ICs. Proc. of Int. Conf. on Computer Aided Design, pp. 48-51

61. Kong T. 2002. A novel net weighting algorithm for timing-driven placement. Proc. of Int. Conf. on Computer Aided Design, pp. 172-176

62. Baldick R., Kahng A.B., Kennings A., Markov I.L. 2001. Efficient Optimization by Modifying the Objective Function: Applications to Timing-Driven VLSI Layout. IEEE Trans, on Circuits and Systems I: Fundamental Theory and Applications, v. 48, no. 8

63. Donath W.E., Norman R.J., Agrawal B.K., Hello S.E., Han S.Y., Kurtzberg J.M., Lowy P., McMillan R.I. 1990. Timing Driven Placement Using Complete Path Delays. Proc. of IEEE Design Automation Conference, pp. 84-89

64. Chowdhary A., Rajagopal K., Venkatesan S., Cao Т., Tiourin V., Parasuram Y., Halpin B. 2005. How accurately can we model timing in a placement engine? Proc. of IEEE Design Automation Conference, pp. 801-806

65. Shahookar K., Mazumder P. 1991. VLSI Cell Placement Techniques. ACM Computing Surveys, v. 23, no. 2.

66. Sarrafzadeh M. and Wang M. 1997. NRG: Global and detailed placement. In Proc. Int. Conf. Comput. Aided Des. pp. 532-537.

67. Hill D. 2002. Method and system for high speed detailed placement of cells within an integrated circuit design. U.S. Patent 6 370 673, Apr. 9, 2002.

68. Ren H., Pan D. Z., Alpert C. J., and Villarrubia P. 2005. Diffusion-based placement migration. In Proc. Des. Autom. Conf. pp. 515-520.

69. Agnihotri A., Yildiz M. C., Khatkhate A., Mathur A., Ono S., and Madden P. H. 2003. Fractional cut: Improved recursive bisection placement. In Proc. Int. Conf. Comput. Aided Design, pp. 307-310.

70. Luo Т., Ren H., Alpert C. J., and Pan D. 2005. Computational geometry based placement migration. In Proc. Int. Conf. Comput. Aided Des. pp. 41-47.

71. Vygen J. 1997. Algorithms for large-scale flat placement. In Proc. Des. Autom. Conf. pp. 746-751.

72. Vygen J. 1998. Algorithms for detailed placement of standard cells. In Proceedings of the conference on Design, automation and test in Europe, pp. 321 324.

73. Brenner U., Pauli A., and Vygen J. 2004. Almost optimum placement legalization by minimum cost flow and dynamic programming. In Proc. Int. Symp. Phys. Des. pp. 2-9.

74. Brenner U. and Vygen J. 2004. Legalizing a placement with minimum total movement. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 23, no. 12.pp. 1597-1613

75. Sentovich E.M., Singh K.J., Lavagno L.et al. 1992.SIS : A system for sequential circuit synthesis. Technical report UCB/ERL M92/41, University of California at Berkeley

76. Kashyap C.V., Alpert C.J., Liu F., Devgan A. 2003. Closed Form Expressions for Extending Step Delay and Slew Metrics to Ramp Inputs. Proc. of Int. Symp. on Physical Design, pp. 24-31

77. Ratzlaf C.L., Pullela S., Pillage L.T. 1992. Modelling the RC-Interconnect Effects in a Hierarchical Timing Analyzer. Proc. of IEEE Custom Integrated Circuits Conference, pp. 15.6.1-15.6.4.

78. Benson S.J., Mclnnes L.C., More J., Sarich J. TAO User Manual. http://www.mcs.anl.gov/tao82.LGSynth suitehttp://vlsicad.eecs.umich.edU/BK/Slots/cache/www.cbl.ncsu.edu/CBLDocs/lgs93.h tml

79. MVSIS: Logic Synthesis and Verification. http://embedded.eecs.berkeley.edu/Respep/Research/mvsis/

80. Kahng A., Mantik S and Markov I. 2002 MinMax Placement For LargeScale Timing Optimization. Proceedings of ISPD'02. pp. 143-148.

81. Kennings A. A. and Markov I. L., 2002. Smoothening Max-terms and Analytical Minimization of Half-Perimeter Wirelength. VLSI Design 14(3), pp. 229-237.

82. Kennings A. A. and Markov I. L., 2000. Analytical minimization of half-perimeter wirelength. Proceedings of the ASP-DAC 2000. Asia and South Pacific, pp. 179184.

83. Аюпов А.Б., Крагинский J1.M. Оптимизация быстродействия СБИС в аналитическом алгоритме размещения стандартных ячеек // Труды конференции AIS'08/CAD-2008.-2008. -Т. 1.-С. 151-158.

84. Аюпов А.Б., Марченко A.M. 2008. Метод оптимизации трассируемости в аналитическом алгоритме размещения // Информационные технологии. — 2008.-Вып. 2.-С. 12-17.

85. Ayupov A., Kishinevsky М. and Marchenko A. Separating retiming from the initial states // Proceedings of the 2005 International Workshop on Logic ad Synthesis. -2005. P. 65-72.

86. Ayupov A., Marchenko A. and Tiourin V. An analytical approach to placement legalization // Proceedings of the 2008 ACM Great Lakes Symposium on VLSI. -2008.-P. 167-170.

87. Ayupov A., Marchenko A. Congestion-driven analytical placement // Proceedings of the 2006 East-West Design and Test International Workshop. 2006. - P. 143148.

88. Ayupov A., Kraginskiy L. A novel timing-driven optimization using smooth timing model // Proceedings of the East-West Design & Test Symposium. 2008. - P. 137140.1. Утверждаю»

89. Заместитель декана Факультета Радиотехники и Кибернетики

90. Технического Института (ГУ)