Содержание к диссертации
Введение
Глава 1. Современные проблемы автоматизации проектирования топологии СБИС
1.1. Технологические тенденции и конструкторские требования
1.2. Основные этапы решения задачи размещения 9
1.3. Критерии качества и тестовые примеры 14
1.4. Аналитические методы 29
1.5. Дихотомические алгоритмы 37
1.6. Комбинированные алгоритмы 41
1.7. Результаты сравнения на ISPD-2005 46
1.8. Методы легализации, детального размещения и ЕСО 46
1.9. Эффективность алгоритмов размещения в зависимости от схемы и библиотеки 49 Выводы 55
Глава 2. Методы оптимизации размещения 56
2.1. Модель графа перестановок
2.2. Алгоритм оптимизации размещения элементов 60
2.3. Реализация и результаты тестирования
2.4. ЕСО размещение
Выводы
Глава 3. Оценка трассируемости с использованием вероятностного анализа 76
3.1. Постановка задачи 76
3.2. Оценка перегрузок 79
3.3. Запреты на трассировку 94
3.4. Оптимизация трассируемости 97
Выводы ЮЗ
Глава 4. Метод оценки деревьев Штейнера, адаптирующийся к критериям трассировки 104
4.1. Постановка задачи 104
4.2. Похожие деревья 105
4.3. Нахождение взаимнооднозначного соответствия между вершинами 112
4.4. Алгоритм построение дерева Штейнера.
Выводы 120
Глава 5. Программная реализация алгоритмов 121
5.1 Структура данных для алгоритмов оптимизации 124
5.2 Оценка трассируемости 127
5.3 Реализация общего оптимизационного алгоритма 129
5.4 Оптимизация трассируемости 132
5.5 Легализация элементов СБИС 135
5.6. ЕСО размещение 139
Выводы 141
Заключение 142
Акт о внедрении 145
Список литературы
- Технологические тенденции и конструкторские требования
- Алгоритм оптимизации размещения элементов
- Нахождение взаимнооднозначного соответствия между вершинами
- Структура данных для алгоритмов оптимизации
Введение к работе
Актуальность работы.
Прогресс в развитии нанотехнологий, а именно, дальнейшее уменьшение технологических размеров транзисторов и проводников привел к уменьшению удельного веса задержки в транзисторе в общей задержке по цепи более чем на три порядка. Эта тенденция отразилась на эволюции алгоритмов размещения элементов СБИС, которые активно развивались в последнее время. Задача размещения элементов СБИС существенно усложнилась также за счет увеличения размерности задачи до нескольких миллионов элементов и ужесточения технологических требований. В совокупности это привело к необходимости проведения дополнительной оптимизации после глобального и детального размещения элементов Критериями оптимизации могут быть трассируемость, рабочая частота, выделение тепла, потребление питания и другие. В совокупности этот этап носит название этапа инженерных изменений (ЕСО) В настоящее время на этапе ЕСО применяются различные эвристические методы, в том числе интерактивные процедуры Отсутствие общей методологии проведения ЕСО - оптимизации делает этот этап одним из критических. Задача разработки ЕСО - методологии является крайне актуальной.
Цель диссертационной работы состоит в разработке ЕСО маршрута, который позволит объединить в одном ЕСО процессе как автоматические, так и интерактивные методы оптимизации размещения и стандартные ЕСО операции, а также в разработке эффективных методов и алгоритмов оптимизации размещения элементов СБИС по различным критериям. Для достижения данной цели в диссертационной работе решаются следующие задачи: разработка математической модели графа перестановок; разработка общего эффективного алгоритма оптимизации размещения элементов СБИС; разработка алгоритмов оценки и оптимизации трассируемости, разработка метода построения деревьев Штейнера, основанного на знаниях, для быстрой точной оценки топологии цепи; разработка алгоритма ЕСО размещения (размещение и легализация элементов, добавленных для достижения заданных технологических параметров)
Научная новизна результатов, представленных в данной диссертационной работе, заключается в следующем: предложен метод, объединяющий в одном ЕСО процессе как автоматические, так и интерактивные алгоритмы оптимизации размещения и стандартные ЕСО операции, который, в отличие от известных, позволяет восстанавливать легальность размещения после внесения изменений без проведения полного переразмещения элементов. разработана модель графа перестановок, которая в отличие от известных, учитывает изменение длины цепей, позволяет точно определять стоимость каждой перестановки, что дает возможность улучшить качество и скорость оптимизации; предложен алгоритм оценки деревьев Штейнера, основанный на знаниях. Отличительной особенностью этого алгоритма является то, что он строит деревья Штейнера по заданному образцу, тем самым могут быть использованы любые неформальные критерии и учтены сложные ограничения. Кроме того, алгоритм является универсальным и может быть адаптирован под любую конкретную задачу через создание специализированной библиотеки образцов; разработан алгоритм оптимизации и оценки трассируемости, его отличительной особенностью является то, что он не производит полного переразмещения элементов, сохраняет легальность и не нарушает других характеристик размещения; разработан быстродействующий алгоритм оптимизации размещения элементов по длине цепей. Предложенный алгоритм не производит переразмещения элементов, сохраняет глобальную структуру размещения и легальность.
Реализация.
На базе предложенных алгоритмов разработан комплекс программ оптимизации размещения, оценки трассируемости и ЕСО размещения по различным критериям. Программы оценки трассируемости, оптимизации размещения по длине цепей и трассируемости, легализации используются в модуле размещения программного продукта "Go Placement". Программа ЕСО размещения реализована в виде отдельной подсистемы и предназначена для корректировки размещения согласно списку технологических нарушений. Разработанные программы внедрены в ЗАО "Гамбит" и использовались в ИППМ РАН.
Практическая значимость работы.
Алгоритмы и подходы, предложенные в данной работе, реализованы в виде программы оптимизации размещения элементов, которая используются при проектировании СБИС. Алгоритмы оценки и оптимизации трассируемости используются при проектировании СБИС с высокой утилизацией и сложными технологическими ограничениями. Реализация алгоритма ЕСО размещения является неотъемлемой частью процесса ЕСО, широко используемого при проектировании специализированных СБИС (время прохождения сигнала, минимизация потребления электроэнергии) в настоящее время. С использованием данных программ было произведено проектирование ряда СБИС для ведущих мировых производителей микропроцессоров.
Апробация основных теоретических и практических результатов работы проводилась на конференциях:
Международная научно-техническая конференция «Интеллектуальные САПР» (г. Геленджик, 2002-2005 г., 4 доклада)
8 Международный семинар «Дискретная математика и ее приложения» (МГУ, 2004 г., 1 доклад)
Публикации. Результаты диссертации отражены в 7 публикациях.
Структура и объем диссертационной работы. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы. Работа содержит 156 страниц и акты о внедрении.
Технологические тенденции и конструкторские требования
В последнее десятилетие произошло смещение акцентов в проектировании СБИС. Это связано в первую очередь с переходом на новый качественный уровень нанотехнологии. В связи с этим межсоединения начали доминировать над транзисторами по всем характеристикам. В Таблице 1.1 приведены сравнительные данные по задержкам в транзисторе и в межсоединениях для различных технологий [1].
Очевидна тенденция уменьшения удельного веса задержки в транзисторе в общей задержке по цепи. Соотношение между задержками в транзисторе и проводнике изменилось в 2500 раз, при этом методология проектирования и базовые алгоритмы практически не изменились. Описанные выше тенденции требуют адекватного отражения в методах проектирования.
Таким образом, задержка на межсоединениях требует совмещения этапов логического и физического проектирования, а логический синтез без учета реализации схемы в кремнии неэффективен.
Подобные тенденции отразились на эволюции алгоритмов размещения элементов СБИС, которые активно развивались в последнее время. Их можно разбить на три главных типа: аналитические, дихотомические и моделирования отжига. Для тестирования алгоритмов были разработаны новые тестовые примеры, которые отражают современные тенденции в размещении элементов СБИС: ? более 1 миллиона размещаемых элементов ? наличие макроблоков ? наличие элементов ввода-вывода и необходимость их размещения ? ограничения по задержке в прохождении сигнала по цепям ? ограничения по трассируемости
Существуют два базовых варианта постановки задачи размещения стандартных ячеек: с постоянным и переменным расстоянием между рядами размещения[4]. Цели задачи размещения для двух постановок различны.
При размещении с переменным расстоянием между рядами трассировка производится с помощью канальных трассировщиков, используя каналы между двумя соседними рядами. Расстояния между рядами и длина ряда не фиксирована до начала размещения. Минимизация площади и удовлетворение ограничений на время прохождения сигнала являются основными целями размещения.
Актуальность задачи размещения с постоянным расстоянием между рядами обусловлена возникновением иерархического стиля проектирования. Она используется для размещения блоков (подсхем), а не всей схемы. В сравнении с первой постановкой задачи размещения вторая наиболее соответствует текущим техническим тенденциям. В задаче размещение с фиксированным расстоянием между рядами число и расположение допустимых посадочных мест для элементов фиксировано до начала размещения. Трассировка производится в нескольких слоях (более чем в трех слоях металла), используя технику трассировки над элементами. Поэтому нет необходимости резервировать расстояние между рядами размещения, если трассировка не очень сложна или распределение трассировочных ресурсов по горизонтальному и вертикальному направлению равномерно. Целью размещения в этом случае, в отличие от случая минимизации площади, является достижение трассируемости при заданном расстоянии между рядами. Другим важным критерием является соблюдение ограничений, связанных с производительностью схемы.
Для задачи с фиксированным расстоянием между рядами размещение может оказаться очень сложным или даже недостижимым, если заданная область размещения недостаточно велика {плотность размещение высока), либо ограничения, связанные с производительностью, слишком жесткие. Эти две ситуации могут быть вызваны планированием с агрессивным бюджетированием площади или времени прохождения сигнала. Поэтому необходим механизм обратной связи, позволяющий влиять на процесс планирования размещения. Оценки времени прохождения сигнала и загрузки области размещения очень важны на ранних стадиях размещения и способны существенно улучшить производительность схемы.
С другой стороны, если трассировка не является сложной, задача минимизации максимальной задержки прохождения сигнала в цепи выходит на первый план. Алгоритмы размещения должны учитывать относящуюся к трассировке информацию, такую как количество трассировочных ресурсов, распределение запретов и другие. Более того, необходим хороший алгоритм оценки и управления трассируемостью, иначе полученное размещение будет перегружено, что ухудшит трассируемость и производительность схемы.
Алгоритмы размещения обычно состоят из 3-х основных частей: глобального размещения, легализации и детального размещения. Фаза глобального размещения делится на начальное глобальное размещение, физическую кластеризацию и финальное глобальное размещение.
Целью начального глобального размещения является равномерное распределение элементов по области размещения для последующей физической кластеризации. Во время этой стадии рассматривается полный список цепей, включающий в себя стандартные элементы и макроблоки. Далее итеративно используется техника глобальной оптимизации и переброски элементов, описанная в [2].
Алгоритм оптимизации размещения элементов
Пусть на графе перестановок найден цикл не более чем из 3-х ребер суммарного веса /. Тогда при перестановке элементов по этому циклу значение функции качества изменится в точности на /.
Ограничение на длину цикла в три ребра обусловлено необходимостью того, чтобы любые две вершины в цикле были независимы. Согласно теореме 1, изменение функции качества совпадает с длиной цикла в графе перестановок. Это важное свойство лежит в основе алгоритма, представленного на рис.2.3. Особое внимание следует уделить процедуре пересчета весов ребер в графе. Для сохранения основного свойства графа необходимо пересчитывать веса ребер в графе. Очевидно, что при применении перестановки изменились только веса ребер, исходящих из вершин, участвующих в перестановке, и зависимых от них вершин. Сложность алгоритма складывается из двух величин: сложности построения всего графа и сложности его обновления (шаг "пересчитать веса ребер в графе" на рис. 2.3). Сложность построения графа перестановок есть о(«2), в предположении, что максимальное количество элементов в цепи s и максимальное количество цепей к, содержащих один и тот же элемент, ограничено константой. Сложность обновления графа есть о(п-к), где к есть максимальное количество вершин, которые нужно обновить. Величина к 3 -к s, поэтому при действующих ограничениях это тоже константа. Отсюда, сложность всего алгоритма есть 0[пг).
Алгоритм последовательно перебирает все вершины графа перестановок и ищет циклы положительной длины, содержащие эту вершину. Далее элементы переставляются по циклу, веса ребер в графе обновляются и поиск продолжается. Критерием останова является отсутствие циклов, содержащих вершину, либо превышение заданного числа итераций с вершиной. Последний параметр может варьироваться, сохраняя баланс между скоростью работы и качеством найденного решения.
В качестве примера рассмотрим 6 элементов, размещенных легально и соответствующий граф перестановок (рис.2.2). В графе существуют два цикла положительной длины 2: (2,4) и (5,6). В процессе работы алгоритма первым будет найден цикл (2,4). Результат применения этой перестановки и новый граф перестановок показаны на рис. 2.4. В полученном фафе нет циклов с положительной суммой весов ребер, следовательно, нет оптимизирующих перестановок, суммарная длина соединений уменьшена на 2.
Следует отметить, что в текущей формулировке алгоритма каждое следующее найденное решение будет лучше предыдущего, поскольку осуществляются только перестановки с положительным весом. То есть алгоритм является жадным и существует вероятность остановки работы в некотором локально оптимальном решении. Для решения этой проблемы могут быть разрешены перестановки с небольшим отрицательным весом, равным /. Этот вес может быть задан как внешний параметр, либо рассчитан исходя из статистики весов всех ребер в графе. Например, если сумма весов всех ребер в графе отрицательна и равна -S, а число ребер равно г, то можно положить / = —. То г есть принимать перестановки элементов по циклу можно в том случае, если длина цикла больше /, На практике этот метод иногда показывает результат лучше традиционного, а так как время работы оптимизационного алгоритма не велико, то возможно его применение с разными весами и выбор наилучшего решения.
Нахождение взаимнооднозначного соответствия между вершинами
С помощью последней теоремы получаем необходимое условие того, чтобы можно было строить приближенную характеристическую функцию. 4.3. Нахождение взаимнооднозначного соответствия между вершинами.
Пусть имеется два множества MN и Мк, размерностей N и К соответственно, причем N К. Для нахождения соответствия между этими множествами необходимо: Шаг 1: Привести их к одинаковой размерности, т.е. найти подмножество M NQMK, размерности JV, расстояние от которого до множества MN минимально среди всех подмножеств размерности jV. Шаг 2: Найти соответствие вершин на этих множествах M N и МN. Рассмотрим шаги алгоритма подробнее Реализация шага 1
Для того чтобы привести множества к одной размерности, нужно вычеркнуть [К -N) элементов из множества Мк . Для этого рассмотрим все его подмножества из N элементов и выберем такое M N сЛ/к, что р\МNiM N) -минимально, т.е. (4.5) KvH I Случай, когда найдется несколько подмножеств, удовлетворяющих формуле (5), будет рассмотрен ниже.
В обозначениях М = МN uG = МК, реализация алгоритма выглядит следующим образом.
Теперь необходимо еще раз рассмотреть формулу (4). В этой формуле не указано, какое из множеств M N, M"N выбрать, если на них обоих достигается минимум. В нашем случае критерием может служить количество основных вершин 115 в выбранном подмножестве. Окончательно, среди всех подмножеств M N, удовлетворяющих условию (4), выберем то, для которого у(М н) максимально. Таким образом, при нахождении среди точек множества Gz подмножества, расстояние от которого до Pt и 5, минимально, предпочтение отдается подмножествам, содержащим наибольшее число вершин из Р2. 4.4. Алгоритм построения дерева Штейнера.
Алгоритм построения дерева Штейнера на точках Р2 делится на две части: непосредственное применение знаний (известного решения ,(/; u 5,, Я,)) и построение недостающей части решения. Этап 1 (применение знаний): ребра на множестве К в соответствии с результатом работы алгоритма FindMap
После применения алгоритма этапа 1 сформировано дерево Тг(К,Е 2). Если P7(zK, то все основные точки уже включены в дерево, и этап 2 проводить не нужно. Пусть PjttK. Положим Р2 = Р2 \ К. Этап 2 (построение недостающей части решения):
В качестве примера работы алгоритма рассмотрим следующую задачу. Дано множество точек, состоящее из 1 источника и 4-х стоков, показанное на рис. 4.10. На рис 4.11 показаны два образца деревьев Штейнера, подаваемые на вход. Первое имеет минимальную длину, а второе минимальный радиус.
Алгоритмы, представленные в предыдущих главах, были реализованы на языке C++ в среде Linux в составе коммерческого программного продукта для автоматизации проектирования элементов СБИС "Go Placer" компании Golden Gate Technology[103].
Был использован стандартный интерфейс программного комплекса "Go Placer", который позволяет считывать данные о дизайнах в формате LEF/DEF. Также была реализована поддержка обоих форматов: Gate Array и Standard Cell. Были реализованы следующие алгоритмы: ? Оценка трассируемости ? Оптимизация трассируемости ? Оптимизация размещения элементов СБИС ? Легализация элементов СБИС ? ЕСО размещение элементов СБИС Общая схема проектирования с использованием пакета "Go Placer" представлена на схеме 5.1.
Первым этапом проектирования является обработка данных о проекте из распространенных форматов "LEF/DEF" и "Verilog". Затем эта информация обрабатывается и преобразуется во внутреннюю базу данных.
Вторым этапом является проведение глобального размещения элементов, в результате которого достигается баланс между равномерностью размещения и суммарной длиной цепей. На этом этапе элементы помещаются в центры ячеек сетки, которая покрывает область размещения, поэтому полученное размещение не является легальным.
Третьим этапом является легализация размещения элементов, которая заключается в устранении пересечений между элементами и контроль других технологических параметров. Была реализована поддержка двух форматов посадочных мест на области размещения "Gate Array" и "Standard Cell".
На любом шаге размещения или легализации элементов может быть получена текущая оценка трассируем ости, которая реализована отдельной подсистемой. Также доступна графическая визуализация текущей карты загруженности.
Четвертым этапом является оптимизация размещения, существует возможность выбора критерия оптимизации: длина, трассируем ость, критерий, программируемый пользователем.
Отдельной подсистемой реализовано ЕСО размещение. Для ее запуска необходимо загрузить список ЕСО команд из внешнего анализатора. Подсистема выполнит команды, соблюдая заданные ограничения, проверит и восстановит легальность размещения.
Структура данных для алгоритмов оптимизации
Для этого применяется стандартные методы построения и оптимизации графа перестановок и специальный класс-критерий для определения весов ребер в графе. Основным его отличием от трех стандартных классов, описанных выше, является то, что вес любого ребра из элемента перегруженной ячейки в элемент свободной ячейки имеет положительный вес. Вес выбирается так, что он пропорционален весу ребра в классическом определении. Веса остальных ребер выбираются стандартным образом.
В результате работы алгоритма загруженность проблемных ячеек снижается до допустимого уровня, а загруженность остальных ячеек повышается незначительно. Таким образом, благодаря специальному выбору оптимизационной области (средняя загруженность по всей области меньше допустимой), загруженность во всех ячейках области не превышает допустимую.
Возвращаясь к определениям главы 2, число перегруженных ячеек представляет собой параметр Х\ а суммарное превышение допустимого уровня загрузки ячеек параметр Хг
Было произведено тестирование алгоритма на общедоступных тестовых проектах [25]. В таблице 5.5 представлены результаты на 5 проектах с числом размещаемых элементов от 10 до 60 тысяч. На каждом из них получено улучшение по характеристикам %х и %г от 23% до 95%, как показано в таблице 5.6.
Был реализован алгоритм верификации и легализации размещения элементов СБИС для проектов с архитектурой "Gate Array" и "Standard Cell" в виде отдельной подсистемы. В ее основе лежит базовый класс "fPlacementVerifierBase". На его основе была построена иерархия классов для проверки легальности и легализации размещения элементов СБИС. Также он используется в оценке трассируемое через класс "fCongestionEstimator".
На первом уровне наследования лежит класс "(PlacementVerifier", который содержит атрибуты правил размещения (placement_parameters) и данные о внешней среде размещения (external_data). Также определены базовые методы работы с элементами (wnte() и unwnte()), которые реализуют и поддерживают актуальность действий по размещению и перемещению элементов. Метод "isSuitableType()" проверяет возможность размещения заданного элемента в заданном посадочном месте. Так как правила проверки существенно отличаются для технологий типа "Gate Array" и "Standard Cell", метод был задан виртуальным и переопределен в каждом из производных классов "fPlacementVerifierSC" и "fPlacementVerifierGA".
Метод "isSuitable()" агрегирует внутри себя использование метода "isSuitab!eType()" и отвечает за фактическое размещение элемента.
На следующем уровне иерархии лежат классы "fPlacementVerifierAdvanced" и "forrecterVerificatorBase". Они расширяют функциональность базовых классов определением методов оптимизации ориентации элементов "OptimizeOrientationsO", генерации прямоугольников Хам мана "GenerateHannanRectanglesO", определения функции качества "QualityFunctionQ" и общей управляющей процедурой легализации всех элементов "Suitln()" Общая управляющая процедура последовательно перебирает все элементы, которые предварительно сортируются с помощью специальных классов обхода элементов (рис. 5.8), которые представляют собой четыре типа: ? "Border2Center_Visitor" представляет собой упорядочивание элементов по размеру и расстоянию от центра области размещения в сторону уменьшения и удаления от центра; ? "Center2Border_Visitor" обратное упорядочивание по длине по сравнению с предыдущим классом, сначала рассматриваются элементы ближе к границе области размещения; ? "Corner2Corner_Visitor" сортирует элементы волной между двумя самыми дальними друг от друга точками области размещения; ? "CornerSimultaneously_Visitor" сортирует элементы волнами, запуская их одновременно из двух самых дальних точек области размещения.
Затем для каждого элемента строится прямоугольник Хаммана, и в нем начинается поиск подходящего посадочного места с наилучшей функцией качества. Финальным шагом является оптимизация ориентации размещения.
