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

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

Марченко Михаил Александрович

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

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

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

Москва - 2006

Работа выполнена в Институте проблем проектирования в микроэлектронике Российской академии наук (ИППМ РАН)

Научный руководитель: доктор технических наук, профессор Г.Э. Широ

Защита состоится 18 декабря 2006 года в Ючас.ООмин. на заседании диссертационного совета Д 002.078,01 в Институте проблем проектирования в микроэлектронике Российской академии наук по адресу: 124681, г. Москва, ул. Советская, д. 3.

С диссертацией можно ознакомиться в библиотеке ИППМ РАН. Автореферат разослан 17 ноября 2006 г.

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

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

В.М. Курейчик

кандидат технических наук C.B. Гаврилов

Ведущая организация:

Московский государственный институт электронной техники (технический университет)

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

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

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

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

разработка математической модели графа перестановок; разработка общего , эффективного алгоритма оптимизации

размещения элементов СБИС;

3 .

разработка алгоритмов оценки и оптимизации трассируем ости, разработка метода построения деревьев Штейнера, основанного на знаниях, для быстрой точной оценки топологии цепи; - ; разработка алгоритма ECO размещения {размещение и легализация элементов, добавленных для достижения заданных технологических параметров).

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

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

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

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

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

На базе предложенных алгоритмов разработан комплекс программ оптимизации размещения, оценки трасснруемости и ECO размещения по различным критериям. Программы оценки трасснруемости, оптимизации размещения по длине цепей и трасснруемости, легализации используются в модул ^размещения программного продукта "Go Placement". Программа ECO размещения реализована в виде отдельной подсистемы и предназначена для корректировки размещения согласно списку технологических нарушений. Разработанные программы внедрены в ЗАО "Гамбит".

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

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

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

• Международная научно-техническая ' конференция «Интеллектуальные САПР» (г. Геленджик, 2002-2005 г., 4 доклада).

5 "

• 8 Международный семинар «Дискретная математика и ее

приложения» (МГУ, 2004 г., 1 доклад).

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

Структура н объем работы

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

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

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

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

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

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

Подобные тенденции отразились на эволюции алгоритмов

размещения элементов СБИС, которые активно развивались в последнее

время. Их можно разбить на три главных типа: аналитические,

дихотомические (итерационные) и комбинированные. Для тестирования

алгоритмов были разработаны новые тестовые примеры, которые

отражают современные тенденции в размещении элементов СБИС:

6

■ более 1 миллиона размещаемых элементов;

■ наличие макроблоков;

■ наличие элементов ввода-вывода и необходимость их размещения;

■ ограничения по задержке в прохождении сигнала по цепям;

■ ограничения по трасспруемости.

В главе рассмотрены основные этапы решения задачи размещения стандартных ячеек с постоянным и переменным расстоянием между рядами размещения. Типичная схема процесса проектирования топологии схемы представлена на рис. 1.

Зачастую после шага глобального размещения происходит оценка всех характеристик схемы и возникает необходимость оптимизации некоторых критериев. Процесс ECO (Engineering Change Order) возникает на этапе оптимизации частотных характеристик схемы. Типично он может состоять из следующих действий:

1. Добавить или убрать усиливающие элементы (buffering).

2. Заменить вентиль на более или менее мощный (resizing).

3. Удовлетворить требования трассировки.

4. Произвести локальный ресинтез (изменить локально логическую схему).

После таких изменений размещение элементов становится нелегальным. Необходимо восстановить легальность. Этот процесс

Рис. 1. Типичная схема процесса проектирования топологии

называется ECO размещением.

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

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

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

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

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

S

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

Рис. 2. ЕСО - маршрут топологического проектирования СБИС

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

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

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

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

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

Сложность алгоритма складывается из двух величин: сложности построения всего графа и сложности его обновления. Сложность построения графа перестановок есть 0(я2), в предположении, что максимальное количество элементов в цепи S и максимальное количество цепей Л, содержащих один н тот же элемент, ограничено константой. Сложность обновления графа есть 0(и ■ к), где к есть максимальное количество вершин, которые нужно обновить. Величина k£3*h-s, поэтому при действующих о фан мнениях это тоже константа. Отсюда, сложность всего алгоритма есть 2).

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

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

П

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

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

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

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

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

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

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

Алгоритм ECO размещения основан на следующих предположениях:

• Известно, какие элементы были изменены или добавлены. Они называются ЕСО-эффектнымм элементами.

• Задано некоторое значение - MaxD. Оно ' характеризует максимально возможное перемещение для элементов, не вредящее частотным характеристикам схемы.

• Предполагается, что перемещение ЕСО-эффектных элементов сильнее влияет на частотные характеристики схемы, чем перемещение остальных элементов.

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

). Построить список из элементов СБИС. Отсортировать его по следующим критериям в порядке убывания значимости:

a. принадлежность элемента к группе ЕСО-эффектных;

b. физический размер элемента (от большего к меньшему). 2. Последовательно проверять размещение каждого элемента из

списка. Пусть координаты размещения элемента будут

(х,, ), ближайшее найденное легальное место размещения . имеет координаты (jfJ »>■'). Если \х, — х'\ + \у( - у]\£ MaxD

элемент ei фиксируется и полагается ) = (х',у'), иначе

начинает работу алгоритм оптимизации ECO размещения методом перестановок.

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

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

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

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

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

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

Разработан вероятностный алгоритм оценки и оптимизации трассируемости. Вероятностный алгоритм оценки трассируемости основан на моделировании возможной трассировки 2-контактной цепи. Для этого сначала строится минимальное связывающее дерево (MST) или прямоугольное Штейнерово дерево (RST) многоконтактной цепи, а затем используется 2-контактная модель для каждой пары соединенных контактов. Алгоритмы построения MST работают быстрее, но менее точно моделируют трассировку цепи. В выборе между MST и RST заключается баланс между скоростью и точностью. Алгоритм построения и оценки деревьев Штейнера, основанный на знаниях, рассмотрен в Главе 4.

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

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

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

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

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

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

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

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

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

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

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

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

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

18

С помощью этой функции будет) определено расстояние между

множествами.

Средний радиус множества С?

Г

<р{0)=

Г2

Чу

1, при |0| ==

точки этого множества, d^y|tVJ

[<!?[ по 2.

'|с|

- число сочетаний из

точек на плоскости есть

, При|С?|>1

где

)-

расстояние между ними, а

Характеристической функцией множества М точек на плоскости называется функция <рм (и): {1,..., |Л/|} —>Я+ такая, что

щ

Верно следующее утверждение: V множества Мп мощности П 3 множество С М„ мощности (к — 1) такое, что

<р{Мп^ ) < <р{Мп ), Следовательно, характеристическая функция положительна и не убывает. |

На множестве характеристических функций вводится метрика пространства 1р. Таким образом, | расстояние между множествами полагается равным метрике между] характеристическими функциями множеств. !

Пусть имеется два множества! М^ и размерностей

N и

К соответственно, причем N < К. Для нахождения соответствия между этими множествами необходимо:

Шаг 1: Привести их к одинаковой размерности, т.е. найти подмножество М'ы С Мк, размерности N, расстояние от которого до множества Ми

19

минимально среди всех подмножеств размерности N.

Шаг 2: Найти соответствие вершин на этих множествах и .

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

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

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

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

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

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

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

• для определения изменения целевой функции при применении перестановки не нужно производить ее явное вычисление (это в точности вес цикла в графе);

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

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

• предусмотрена возможность перераспределения незанятого места на кристалле и устранения трассировочных перегрузок;

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

3. Разработан алгоритм оптимизации размещения по равномерности загрузки кристалла, который, в отличие от известных алгоритмов:

• работает ннкрементально;

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

4. Разработан алгоритм построения и оценки деревьев Штейнера, который, в отличие от известных алгоритмов:

• адаптируется к заданным критериям трассировки;

• позволяет получать более точную оценку длины по сравнению с полу пер и м етром;

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

Областью применения алгоритма являются цепи с небольшим числом контактов, что типично при проектировании СБИС.

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

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

7. Результаты тестирования на реальных примерах показали эффективность работы реализованных алгоритмов.

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

[1] М.А. Марченко Оценка и оптимизация трасснруемости // Информационные технологии. - 2004, - № 3. — С. 10-20.

[2] М.А. Марченко Метод оптимизации легального размещения СБИС по длине цепей и равномерности загрузки кристалла // Высокопроизводительные вычислительные системы. -М.: ИМВС РАН, 2004. - Вып. 2. - С. 15-25.

[3] М.А. Марченко Модель графа перестановок для оптимизации размещения элементов СБИС И Материалы 8 Международного семинара «Дискретная математика и ее приложения», - 2004. -С. 2S5-288.

[4] М.А. Марченко Метод построения деревьев Штейнера, основанный на знаниях // Труды Международных научно-технических конференций «Интеллектуальные системы (IEEE AIS'02)» и «Интеллектуальные САПР CAD-2002». -2002.

[5] М.А. Марченко Алгоритм ECO размещения с оптимизацией методом перестановок и вставок // ШЕЕ A1S'04 CAD-2004. - M.: Физматлит, 2004. - С. 62-65.

[6] М.А. Марченко Метод оптимизации легального размещения СБИС по длине цепей и равномерности загрузки кристалла // Труды конференции «Интеллектуальные системы и Интеллектуальные САПР».-2003.-С.75-76.

[7] М.А. Марченко Эвристический алгоритм установления изоморфизма графов H Труды Международных научно-технических конференций «Интеллектуальные системы (IEEE AIS'02)» и «Интеллектуальные САПР CAD-2002». -2002. - С. 167-169.

Введение

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

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

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

1.3. Критерии качества и тестовые примеры

1.4. Аналитические методы

1.5. Дихотомические алгоритмы

1.6. Комбинированные алгоритмы

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

1.8. Методы легализации, детального размещения и ЕСО

1.9. Эффективность алгоритмов размещения в зависимости от схемы и библиотеки 49 Выводы

Глава 2. Методы оптимизации размещения

2.1. Модель графа перестановок

2.2. Алгоритм оптимизации размещения элементов

Глава 3. Оценка трассируемости с использованием вероятностного анализа

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

3.2. Оценка перегрузок

3.3. Запреты на трассировку

3.4. Оптимизация трассируемости 97 Выводы

Глава 4. Метод оценки деревьев Штейнера, адаптирующийся к критериям трассировки

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

4.2. Похожие деревья

4.3. Нахождение взаимнооднозначного соответствия между вершинами

4.4. Алгоритм построение дерева Штейнера.

Выводы

Глава 5. Программная реализация алгоритмов

5.1 Структура данных для алгоритмов оптимизации

5.2 Оценка трассируемости

5.3 Реализация общего оптимизационного алгоритма

5.4 Оптимизация трассируемости

5.5 Легализация элементов СБИС 135 5.6. ЕСО размещение 139 Выводы

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

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

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

- разработка математической модели графа перестановок;

- разработка общего эффективного алгоритма оптимизации размещения элементов СБИС;

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

- разработка алгоритма ЕСО размещения (размещение и легализация элементов, добавленных для достижения заданных технологических параметров)

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

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

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

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

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

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

Реализация.

На базе предложенных алгоритмов разработан комплекс программ оптимизации размещения, оценки трассируемости и ЕСО размещения по различным критериям. Программы оценки трассируемости, оптимизации размещения по длине цепей и трассируемости, легализации используются в модуле размещения программного продукта "Go Placement". Программа ЕСО размещения реализована в виде отдельной подсистемы и предназначена для корректировки размещения согласно списку технологических нарушений. Разработанные программы внедрены в ЗАО "Гамбит" и использовались в ИППМ РАН.

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

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

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

• Международная научно-техническая конференция «Интеллектуальные САПР» (г. Геленджик, 2002-2005 г., 4 доклада)

• 8 Международный семинар «Дискретная математика и ее приложения» (МГУ, 2004 г., 1 доклад)

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

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

Выводы

1. Программный пакет "Go Placement" представляет собой платформу для реализации различных алгоритмов размещения и оптимизации элементов СБИС;

2. Представленные в этой главе реализации алгоритмов работают в составе общей системы и общего потока проектирования СБИС;

3. Результаты тестирования на реальных примерах показали эффективность работы реализованных алгоритмов;

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

Заключение.

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

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

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

• для определения изменения целевой функции при применении перестановки не нужно производить ее явное вычисление (это в точности вес цикла в графе);

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

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

• предусмотрена возможность перераспределения незанятого места на кристалле и устранения трассировочных перегрузок;

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

3. Разработан алгоритм оптимизации размещения по равномерности загрузки кристалла, который, в отличие от известных алгоритмов:

• работает инкрементально,

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

4. Разработан алгоритм построения и оценки деревьев Штейнера, который, в отличие от известных алгоритмов:

• адаптируется к заданным критериям трассировки,

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

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

Областью применения алгоритма являются цепи с небольшим числом контактов, что типично при проектировании СБИС.

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

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

7. Результаты тестирования на реальных примерах показали эффективность работы реализованных алгоритмов.

1. http://www.itrs.net/Common/20051TRS/lnteiconnect2005 pdf

2. N. Viswanathan and С. С -N. Chu. Fastplace: Efficient analytical placement using cell hifting, iterative local refinement and a hybrid net model. IEEE Trans. Computer-Aided Design, to appear, 2005.

3. Goto. An efficient algorithm for the two-dimensional placement problem in electrical circuit layout. IEEE Trans, on Circuits and Systems, Vol. CAS-28(1):12-18, 1981.

4. A. E. Caldwell, A. B. Kahng, I. L. Markov, "Can Recursive Bisection Alone Produce Routable Placements?" DAC'OO, p. 477.

5. A. E. Caldwell, A. B. Kahng, I. L. Markov, "Optimal Partitioners and End-case Placers for Standard-cell Layout," IEEE Trans. On CAD 19(11), pp. 1304-1314, 2000.

6. A. E. Caldwell, A. B. Kahng, I. L. Markov, "Design and Implementation of Move-Based Heuristics for VLSI Hypergraph Partitioning," ACM J. on Experimental Algorithms, vol. 5,2000.

7. A. E. Caldwell, A. B. Kahng, I. L. Markov, "Improved Algorithms for Hypergraph Bipartitioning," ASPDAC 2000, pp. 661-666.

8. N. Selvakkumaran and G. Karypis, "THETO: A Fast and High-Quality Partitioning Driven Global Placer," Technical Report 03-046,2003, University of Minnesota.

9. K. W. Morton and D. F. Mayers. Numerical Solution of Partial Differential Equations. Cambridge University Press, 1994.

10. J. Cong and J. Shinnerl, editors. Multilevel Optimization in VLSICAD. Kluwer, Boston, 2003.

11. G. Karypis. Multilevel hypergraph partitioning. In Multilevel Optimization in VLSICAD, chapter 3. Kluwer Academic Publishers, Boston, 2003.

12. T. Chan, J. Cong, and K. Sze. Multilevel generalized force-directed method for circuit placement. In Proc. Int'l Symp. on Phys. Design, 2005.

13. A. Kahng and Q. Wang. Implementation and extensibility of an analytic placer. In Proc. Int'l Symp. on Phys. Design, pages 18-25, 2004.

14. K. Arrow, L. Huriwicz, and H.Uzawa. Studies in Nonlinear Programming. Stanford University Press, Stanford, CA, 1958.

15. J.Cong, M.Romesis, and J.Shinnerl. Fast floorplanning by look-ahead enabled recursive bipartitioning. In Asia South Pacific Design Automation Conf. 2005.

16. C.E. Radke. A justification of, and an improvements on, a useful rule for predicting circuit-to-pin ratios. In Proc. Design Automation Conf, pages 257-267, 1969.

17. D. Hill US patent 6,370,673: Method and system fro high speed detailed placements of cells within integrated circuit design, 2002.

18. A. B. Kahng and Q. Wang, "Implementation and Extensibility of Analytic Placer", Proc. Int. Symp. Physical Design, 2004, pp. 18-25.

19. A. B. Kahng and X. Xu, "Accurate Pseudo-Constructive Wirelength and Congestion Estimation", Proc. ACMInt Worbhop on System-Level Interconnect Prediction, April 2003, pp. 61-68.

20. W. Naylor et al., "Non-linear Optimization Systems and Method for Wire Length and Delay Optimization for an Automatic Electric Circuit Placer", US Patent 6301693, 0ct.2001.

21. B.Hu and M.Marek-Sadovska, "Multilevel Fixed-Points-Additions based Placement", to Appear on IEEE Trans. On CAD.

22. N.Viswanathan and C.C.-N Chu, "FastPlace:Efficient Analytical Placement using Cell Shifting, Iterative Local Refinement and Hybrid Net Model", Proc. Intl. Symp. On Physical Design, 2004.

23. K.Doll, F.M.Johannes, and K.J.Antreich. Iterative placement improvement by network flow methods. IEEE Trans. On CAD of Circuit and Systems, 13(10): 11891200, 1994.

24. T. F. Chan et al., "mPL6: A Robust Multilevel Mixed-Size Placement Engine". ISPD '05:227-229, 2005.

25. NuCAD. "IBM-PLACE benchmark", http://www.ece.nwu.edu/nucad/ibm-place.html.

26. M.А. Марченко "Оценка и оптимизация трассируемости", Информационные технологии, т 3, 2004.

27. Taraneh Taghavi, Xiaojian Yang, Bo-Kyung Choi "Dragon2005: large-scale mixed-size placement tool", ISPD '05,2005, p.245-247

28. Gi-Joon Nam "The ISPD'05 placement contest and benchmark suite", ISPD '05,2005, p.216-219

29. Patrick Hung, Michael J. Flynn "Stochastic congestion model for VLSI systems" Technical Report No. CSL-TR-97-737 October 1997

30. Jinan Lou, Shankar Krishnamoorthy, Henry S. Sheng "Estimating routing congestion using probabilistic analysis" ISPD 2001.

31. C.K. Cheng and E.S. Kuh. "Module placement based on resistive network optimization "IEEE Transactions onComputer aided design, 3(3):218-225, 1984.

32. R. S. Tsay, E.S. Kuh, and C. P. Hsu "PROUD: a sea-of-gates placement algorithms". IEEE Design and test of computers, 44-56, 1988.

33. M. A. Breuer "A Class of min-cut placement algorithms". In Design Automation Conference, 284-290. IEEE/ACM, 1977

34. M. A. Breuer. "Min-cut placement". J. Design Automation Fault-Tolerant Computing, l(4):343-382, 1977

35. U. Lauther. "A min-cut placement algorithm for general cell assemblies based an graph representation", In Desogn Automation Conference, pages 1-10. IEEE/ACM, 1979.

36. A. E. Dunlop and B. W. Kernigan. "A procedure for placement of standard cell VLSI circuits". IEEE Transactions on Computer Aided Design, 4(l):92-98, 1985

37. A. Srinivasan, K. Chaudhary, and E. S. Kuh. "RITUAL: A performance-driven placement algorthm". IEEE Transactions on Circuits and Systems 2: Analog and Digital Processing, 39(11):825-840, 1992.

38. D. Stroobandt and J. Van Campenhout. "Accurate interconnection length estimations for predictions early in the design cycle". VLSI Design, Special Issue on Physical Design in Deep Submicron, 10(1): 1-20, 1999

39. P. R. Suaris and G. Kedem. "Quadrisection: A new approach to standard cell layout". In International Conference on Computer-Aided Design, pages 474-477. IEEE/ACM, 1987

40. D. Huang and A. B. Kahng. "Partitioning-based standard-cell global placement with exact objective". In International Symposium on Physical Design, pages 18-25. ACM, 1997.

41. K. Shahookar and P. Mazumber. "VLSI Cell Placement Techniques". ACM Computing Surveys, 23(2): 143-220, 1991

42. С. Sechen. VLSI placement and global routing using simulated annealing. Kluwer, B. V., Deventer, The Netherlands, 1988.

43. C. Sechen. The TimberWolf3.2 standard cell placement and global routing program: user's guide for version 5/2, release 2. 1986

44. C. Sechen and A. Sangiovanni-Vincentelli. "TimberWolO.2: a new standard cell placement and global routing package". In Design Automation Conference, pages 432-439. IEEE/ACM, 1986.

45. L. Nagel. "SPICE2, A computer program to simulate semiconductor circuits", Univ. California, Berkley, CA, TR ERL-M520, 1995.

46. C. J. Alpert, A. Devgan, and C. Kashyap, "A two moment delay metric for performance optimization", in Proc Int. Symp. Physical Design, 2000, pages 69-74.

47. L. T. Pillage and R. A. Rohrer, "Asymptotic waveform evaluation for timing analysis", IEEE Trans. Computer-Aided Design, vol. 13, pp. 1526-1535, 1994.

48. C. L. Ratzlaff, N. Gopal, and L. T. Pillage, "RICE: Rapid interconnect circuit evaluator", in Proc. IEEE/ACM Design Automation Conf, 1991, pp. 555-560.

49. B. Tutiani, F. Dartu, and L. Pileggi, "Explicit RC-circuit delay approximation based on the first three moments of the impulse response", in Proc. IEEE/ACM Design Automation Conf, 1996, pp. 611-616.

50. A. B. Kahng and S. Muddu, "Two-pole analysis of interconnection trees", in Proc. IEEE Multi-Chip Module Conf, 1995, pp. 105-110.

51. W. C. Elmore, "The transient response of damped linear network with particular regard to wideband amplifiers", J Appl. Phys.,\ol 19, pp.55-63, 1948

52. L. T. Pileggi, "Timing metrics for physical design of deep submicron technologies", in Proc. Int Symp Physical Design, 1998, pp 28-33

53. J. Rubinstein, P. Penfield Jr., and M. A. Horowitz, "Signal delay in RC tree networks", IEEE Trans Computer Aided Design, vol. CAD-2, pp. 202-211, 1983.

54. R. Gupta, B. Tutuianu, and L. T. Pileggi, "The Elmore delay as a bound for RC trees with generalized input signals", IEEE Trans. Computer Aided Design, vol. 16, pp. 95104,1997.

55. J. Cong, L. He, C.-K. Koh, and P.H. Madden, "Performance optimization of VLSI interconnect layout", Integr. VLSI J., vol 21, pp. 1-94, 1996.

56. C.-K. Cheng, J. Lillis, S. Lin, and N. Chang, Interconnect Analysis and Synthesis. New York: Willey, 2000.

57. A. B. Kahng and S. Muddu, "Accurate analytical delay models for VLSI interconnects", Univ. California, Los Angeles, CA, UCLA CS Dept. TR-950034, 1995

58. A. B. Kahng and S. Muddu, "An analytical delay model for RLC interconnects", IEEE Trans. Computer-Aided Design, vol. 16, pp. 1507-1514, 1997.

59. B. Krauter, R. Gupta, J. Willis, and L. T. Pileggi, "Transmission line synthesis", in Proc. IEEE/ACM Design Automation Conference, 1995, pp. 358-363.

60. R. Kay and L. Pileggi, "PRIMO: Probability interpretation of moments for delay calculation", in Proc. IEEE/ACM Design Automation Conference, 1998, pp. 463-468.

61. L. O. Chua, Desoer, and Kuh, Linear and Non-linear Circuits. New york: McGraw-Hill, 1987.

62. M.Pedram and N.Bhat, "Layout Driven Technology Mapping", In Design Automation Conference, pp.99-105, 1991.

63. M.Pedram and N.Bhat, "Layout Driven Logic Restructure/Decomposition", Proc of Int. Conf. on Computer-Aided Design, pp. 134-137, 1991.

64. T.Kutzschebauch and L.Stok, "Congestion Aware Layout Driven Logic Synthesis", Proc. of Int. Conf. on Computer-Aided Design, pp.216-223, 2001.

65. P.Kudva, A.Sullivan and W. Dougherty, "Metrics for Structural Logic Synthesis", Proc. of Int. Conf on Computer-Aided Design, pp. 551-556, 2002.

66. Q. Liu and M. Marek-Sadowska, "A Study ofNetlist Structure and Placement Efficiency" In Int. Symp. On Phys. Design, pp. 198-203, 2004.

67. A.E.Caldwell, A.B.Kahng and I.L.Markov, "Can Recursive Bisection alone Produce Routable Placements", Design Automation Conference, pp.260-263, 2000.

68. T. F. Chan, J. Cong, J. Shinnerl and K. Sze, "An Enhanced Multilevel Algorithm for Circuit Placement", Proc. of Int. Conf on Computer-Aided Design, pp. 299-306, November 2003.

69. В Hu and M.Marek-Sadowska, "Fine-granularity Clustering for Large-scale Placement Problems", In Proc. Intl Symp. on Physical Design, pp.67-74, Apr 2003.

70. Tom Chen and Alkan Cengiz "Measuring Routing Congestion for Multi-Layer Global Routing" GLSVLSI2000.

71. Chin-liang Eric Cheng "RISA: Accurate and Efficient Placement Routability Modeling", 1994.

72. M. Burnstaein and S.J. Hong "Hierarchical VLSI Layout: Simultaneous Placement and Wiring of Gate Arrays" in VLSI, pp. 45-60,1983

73. S. Mayrhofer and U. Lauther, "Congestion-Driven Placement using a new multi-partitioning heuristic", IEEE International Conf. on CAD, pp. 332-335, 1990.

74. R.-S. Tsay, and S.C. Chang, "Early Wirability Checking and 2-D Congestion Driven Circuit Placement", IEEE International Conf. on ASIC, 1992.

75. Bryan Preas & Michael Lorenzetti, "Physical Design Automation of VLSI Systems", pp. 96-97, 1988.

76. W.-J. Sun & C. Sechen, "Efficient and effective placement for very large circuits", IEEE International Conference on CAD, pp. 170-177, 1993.

77. J. Soukup, "Circuit Layout", Proc of the IEEE, Vol. 69, No. 10, Oct. 1981

78. P.G. Karger and M. Malek "Formulation of components placement as a constrained optimization problem", Proceedings of the ICCAD, p. 814-819, 1984

79. C-L. E. Cheng, "RISA: Accurate and Efficient Placement Routability Modeling", Procedengs of International Conference an Computer Aided Design, pp. 690-695, 1994

80. M. Wang and M. Sarrafzadeh, "On the behavior of congestion minimization during placement", International symposium on physical design, pp. 145-150, 1999

81. S. Mayrhoferand U. Lauther, "Congestion-Driven Placement Using a New Multi-partitioning Heuristic", Proceedings of International Conference on Computer Aided Design, pp.332-335, 1990

82. P.N. Parakh, R.B. Brown and K.A. Sakallah, "Congestion Driven Quadratic Placement", Proceedings of 35th Design Automation Conference, pp. 275-278, 1998

83. R.S. Tsay, S.C. Chang and J. Thorvaldson, "Early Wireability Checking and 2-D Congestion Driven Circuit Placement", Proceedings of Fifth Annual IEEE International ASIC Conference and Exhibit, pp. 50-53, 1992

84. M. Wang and M. Sarrafzadeh, "Modeling and Minimization of Routing Congestion", Proceedings of Asian-Pacific Design Automation Conference, pp. 185-190,2000

85. Patrick Hung, Michael J. Flynn "Stochastic congestion model for VLSI systems" Technical Report No. CSL-TR-97-737, 1997

86. М.А. Марченко "Метод оптимизации легального размещения СБИС по длине цепей и равномерности загрузки кристалла", «Высокопроизводительные вычислительные системы» ИМВС РАН №2, 2004

87. L. Maliniak, "1С Tool Creates a Floorplan from HDL Code", Electronic Design, 1996

88. C. S. Chen, Y. W. Tsay, T. Hwang, A. Wu, and Y. L. Lin, "Combining Technology Mapping and Placement for Delay Minimization in FPGA Designs", IEEE transactions on Computer Aided Design of Integrate Circuits and Systems, pages 1076-1084, 1995

89. R. Dudzinski, "RTL Floorplanning Set to Drive Synthesis", EE Times, page 52,1995

90. T. Okamoto, and J. Cong, "Buffer Steiner Tree Construction with Wire Sizing for Interconnection Layout Optimization", Proc. Design Automation Conference, pp. 740-745, 1996

91. C.C.N. Chu and D.F. Wong, "A New Approach to Simultaneous Buffer Insertion and Wire Sizing", Proc. International Conference on Computer Aided Design, pp.614-622,1997

92. J. Lillis, and C.K.Cheng, "Timing Optimization for Multi-Source Nets: Characterization and Optimal Repeater Insertion", Proc. Design Automation Conference, pp. 214-219, 1997

93. J. Cong, C.K. Koh, and K.-S. Leung, "Simultaneous Buffer and Wire Sizing for Performance and Power Optimization", Proc. Int. Symp. On Low Power Electronics and Design, pp. 271-276, 1996

94. Coudert, R. Haddad, and S. Manne, "New Algorithms for Gate Sizing: A Comparative Study", Proc. Design Automation Conference, pp. 734-739, 1996

95. L.A. Entrena, E. Olias, and J. Uceda, "Timing Optimization by Redundancy Addition and Removal", Proc. Physical Design Workshop, pp. 13-20, 1996

96. Y.M. Jiang, A. Kristic, K.T. Cheng, and M. Marek-Sadowska, "Post-Layout Logic Restructuring for performance Optimization", Proc. Design Automation Conference, pp. 662-665, 1997

97. Марченко M.A. "Метод оптимизации легального размещения СБИС по длине цепей и равномерности загрузки кристалла", Труды Конференции «Интеллектуальные системы и Интеллектуальные САПР», с.75-76, 2003

98. Марченко М.А. "Модель графа перестановок для оптимизации размещения элементов СБИС", Материалы 8 Международного семинара «Дискретная математика и ее приложения», с.285-288, 2004

99. В. М. Щемеленин "Автоматизация топологического проектирования БИС" Москва 2001

100. Xiaojian Yang, Bo-Kyung Choi, Majid Sarrafzadeh "Routability Driven Space Allocation for Fixed-Die Standard-Cell Placement", ISPD 2002.

101. Quinn, Breuer "A forced directed component placement procedure for printed circuit boards", Transactions on Circuits and Systems 1979102. www ggtcorp com103. www.boost.org

102. Naveed Sherwani "Algorithms for VLSI physical design automation."

103. Thomas Lengauer "Combinatorial Algorithms for Integrated Circuit Layout."106. Орэ "Теория графов".

104. Ф. Харари, Э. Палмер "Перечисление графов".

105. Andrew В. Kahng, Gabriel Robins "On optimal interconnection for VLSI" Kluwer 1995.

106. M.A. Марченко «Метод построения деревьев Штейнера, основанный на знаниях» Труды Международных научно-технических конференций «Интеллектуальные системы (IEEE AIS'02)» и «Интеллектуальные САПР CAD-2002», 2002

107. М.А. Марченко «Алгоритм ЕСО размещения с оптимизацией методом перестановок и вставок» IEEE AIS'04 CAD-2004 с.62-65, Физматлит 2004

108. Утверждаю» Генершщыйдиректор ЗАО «Гамбит»

109. Т.А.Илуридзе 04 июля 2005 г.1. Акт о внедрении

110. Внедрены в эксплуатацию в ЗАО «Гамбит» в 2002 2004 годах.123298, Москва, 3-я Хорошевская ул, 11

111. Third Khoroshevskaya St, Moscow 123298, Russia

112. Tel (095)197-1065, (095)197-4864 Fax (095)192-4018 E-mail info@gambit com ru1. УТВЕРЖДАЮ

113. Заведующий Сектором автоматизации логического проектирования ИППМ РАН, д.т.н.1. A.JI. Глебов