Содержание к диссертации
Введение
Глава 1. Аналитический обзор алгоритмов трансформации топологического слоя СБИС для технологии двойного шаблона 14
1.1. Аналитический обзор задачи трансформации топологии СБИС для технологии двойного шаблона 14
1.2. Анализ параллельных алгоритмов обработки топологии слоя СБИС
1.2.1. Аналитический обзор применения высокопроизводительных вычислительных систем при проектировании и производстве СБИС 16
1.2.2. Аналитический обзор подходов и методов разбиения топологического слоя СБИС для последующей обработки на высокопроизводительных вычислительных системах 18
1.2.3. Анализ параллельных алгоритмов проверки конструкторско технологических ограничений 21
1.3. Анализ алгоритмов трансформации топологического слоя СБИС для технологии двойного шаблона 23
1.4. Аналитический обзор применения алгоритмов теории графов для трансформации топологического слоя СБИС для технологии двойного шаблона 35
1.5. Топологический слой СБИС с неманхэттенской геометрией 36
Выводы по Главе 1 39
Глава 2. Параллельные алгоритмы построения модели представления топологического слоя СБИС для трансформации для технологии двойного шаблона
2.1. Постановка задачи построения модели представления топологического слоя СБИС для трансформации для технологии двойного шаблона 43
2.2. Параллельный алгоритм построения графа противоречий для топологического слоя СБИС с манхэттенской геометрией 45
2.3. Алгоритм поиска противоречий для топологического слоя СБИС с манхэттенской геометрией на основе модифицированного алгоритма сканирующей прямой 49
2.4. Алгоритм построения графа противоречий для топологического слоя СБИС с неманхэттенской геометрией 56
2.5. Алгоритм поиска противоречий для топологического слоя СБИС с неманхэттенской геометрией на основе «оконных» запросов 61
Выводы по Главе 2 65
Глава 3. Параллельный алгоритм трансформации топологического слоя СБИС для технологии двойного шаблона на основе графовоймодели представления топологии 67
3.1. Параллельный алгоритм трансформации топологического слоя СБИС с произвольной геометрией для технологии двойного шаблона 67
3.2. Параллельный алгоритм раскраски графа противоречий в два цвета 72
3.3. Визуализация и аналитическая поддержка проектирования топологического слоя СБИС для технологии двойного шаблона 75
Выводы по Главе 3 78
Глава 4. Практическая реализация и экспериментальное исследование предложенных алгоритмов 80
4.1. Программа трансформации топологического слоя СБИС для технологии двойного шаблона Parallel DPLayout Migrator 80 Стр.
4.2. Экспериментальное исследование временной сложности разработанных параллельных алгоритмов с использованием Parallel DPLayout Migrator 84
4.3. Экспериментальное исследование трансформации топологии СБИС с использованием Parallel DPLayout Migrator 91
4.4. Экспериментальное исследование методов аналитической поддержки проектирования СБИС ПО
Выводы по Главе 4 115
Общие выводы и заключение 118
Список литературы
- Аналитический обзор подходов и методов разбиения топологического слоя СБИС для последующей обработки на высокопроизводительных вычислительных системах
- Параллельный алгоритм построения графа противоречий для топологического слоя СБИС с манхэттенской геометрией
- Параллельный алгоритм раскраски графа противоречий в два цвета
- Экспериментальное исследование временной сложности разработанных параллельных алгоритмов с использованием Parallel DPLayout Migrator
Аналитический обзор подходов и методов разбиения топологического слоя СБИС для последующей обработки на высокопроизводительных вычислительных системах
Для создания фотошаблонов традиционно используются файлы в формате GDS II (Graphic Database System, GDSII, GDS) [5]. GDS II является де-факто промышленным стандартом для обмена данными по интегральным схемам и их топологиям. Данный формат описывает геометрические объекты на плоскости, текстовые метки и другую информацию в иерархической форме. Для хранения файлов в формате GDS II, описывающих системы на кристалле (System-on-Chip, SoC), состоящие из множества сложно-функциональных блоков (Intellectual Property Blocks, IP-блоков), необходимы значительные объемы памяти и вычислительных ресурсов [6].
При проектировании и производстве СБИС все большее применение находят подходы, использующие высокопроизводительные вычислительные системы [7, 8]. Использование вычислительных систем такого класса при трансформации топологии СБИС позволяет уменьшить время требуемое на обработку топологической информации и повысить допустимый размер входных данных. Снижение временных затрат на проектирование позволяет снизить стоимость разработки новых СБИС. В свою очередь увеличение объема обрабатываемых данных позволяет проектировать систем с постоянно увеличивающейся степенью интеграции. Однако применение параллельных вычислительных систем требует разработки алгоритмов, учитывающих параллельную организацию вычислений [9, 10]. Ограничения параллельных вычислительных систем описаны законом Амдала [11]: Sp =—У , (1.6) v где Sp - ускорение, которое может быть достигнуто на многопроцессорной вычислительной системе из р процессоров, по сравнению с однопроцессорным решением; а - доля от общего объёма вычислений, которая может быть выполнена только последовательными расчётами; 1 — а - доля вычислений, которая может быть идеально распараллелена, то есть время выполнения вычислений будет обратно пропорционально числу задействованных процессорных узлов р.
Закон Амдала показывает, что возможное ускорение вычислений зависит от выбранного алгоритма решения поставленной задачи и ограничено сверху для любой задачи с а 0. Не для каждой задачи имеет смысл увеличение количества процессоров в вычислительной системе. Более того, с учетом потерь на передачу данных между узлами вычислительной системы зависимость времени вычислений от числа узлов будет иметь максимум. Это приводит к ограничению масштабируемости вычислительной системы: с определенного момента добавление новых процессоров в вычислительную систему будет увеличивать время выполнения задачи.
Вопросы разбиения топологии СБИС для последующей ее обработки на параллельных вычислительных системах были рассмотрены в работах [12, 13]. Основная идея предложенных подходов состоит в том, что топология СБИС разбивается на несколько частей и затем эти части обрабатываются параллельно. При этом разбиение может быть выполнено либо согласно площади, занимаемой топологией СБИС, либо согласно плотности распределения геометрических примитивов.
Разбиение на части, основанное на площади топологии СБИС, может осуществляться двумя способами: на вертикальные или горизонтальные полосы или на прямоугольники [14]. В первом случае топология делится на несколько полос одинаковой площади. Размеры полос выбираются, исходя из следующих ограничений: минимальный допустимый периметр полосы и количество процессоров, участвующих в обработке. Первое условие обусловлено тем, что условие минимального допустимого периметра заметно упрощает процесс коммуникации между отдельными процессорами в ходе обработки топологии СБИС, второе - эффективным использованием доступных вычислительных ресурсов. Разбиение на прямоугольники осуществляется аналогично на основе рассмотренных выше принципов. Пример применения такого подхода представлен на Рисунке 1.2. Недостатком данного подхода является возможность неравномерной загрузки процессоров при обработке геометрии. Это может быть вызвано тем, что в разных полосах или прямоугольниках может быть разное количество геометрических примитивов.
В методе, основанном на разбиении на основе плотности распределения геометрических примитивов, топология СБИС представляется в виде множества примитивов, каждый из которых отображается точкой, которая, например, может являться центром полигона [15]. Этот подход показан на Рисунке 1.3. Цель разбиения формулируется как задача получения в каждой части топологии СБИС приблизительно одинакового количества точек. В данном случае возможны также две стратегии разбиения: разбиение на полосы или на прямоугольники с одинаковым количеством точек. Размеры прямоугольников или ширина полос может различаться, а их количество зависит от количества процессоров или вычислительных узлов, которые применяются для обработки топологии СБИС.
При разделении на вертикальные полосы ширина полосы зависит от количества плотности распределения геометрических примитивов по оси X (Рисунок 1.3, а). При разделении на прямоугольники площадь прямоугольника зависит от плотности распределения геометрических примитивов по осям X и У.
Недостатком данного подхода является необходимость проведения достаточно сложного препроцессинга для разделения исходной топологии на полосы или прямоугольники.
Для использования параллельных вычислительных систем для решения задачи трансформации топологического слоя СБИС для технологии двойного шаблона необходима разработка алгоритмов, допускающих параллельную обработку конструкторско-технологических ограничений и ограничений технологии двойного шаблона.
Параллельный алгоритм построения графа противоречий для топологического слоя СБИС с манхэттенской геометрией
В манхэттенской топологии допустимы только отрезки, параллельные осям координат. Исходя из этого, возможно упростить выражения (2.3) и (2.4). В работах [43, 44] показано, что манхэттенскую геометрию можно представить только в виде горизонтальных или вертикальных отрезков. Если геометрия представлена только в виде горизонтальных отрезков, то вертикальные можно восстановить на основе горизонтальных. В таком случае полигон можно представить как множество горизонтальных отрезков: Polp = [sxpl,Sxp2, ...,SxpSlp], (2.10) где Рои - р-ый полигон /-ого топологического слоя; Sxps - s-ьт отрезок /7-ОГО полигона; sip - количество отрезков, составляющих полигон Рои. Тогда выражение (2.2) можно привести к виду: Lat = {Poll,Pol2,...,PolPl} {Sx1,...,SxSl}, (2.11) где Si = Y. Sip количество отрезков /-ого топологического слоя. Для обработки на высокопроизводительных вычислительных машинах необходимо представить топологию СБИС в виде структуры данных, допускающей последующую параллельную обработку.
В диссертационной работе предлагается использовать следующую структуру данных, позволяющую обрабатывать топологию СБИС в параллельном режиме. Она представляет собой следующие массивы геометрических объектов и должна быть построена для каждого топологического слоя: массив полигонов Ро, которые представлены в виде массива точек, которые их составляют; массив всех горизонтальных отрезков Sx, которые составляют топологический слой, каждый из которых состоит из указателей на точки начала и конца отрезка и указателя на полигон, которому отрезок принадлежит. Отрезки в массиве Sx должны быть упорядочены по оси ординат. Следует отметить, что в предложенной структуре данных вертикальные отрезки необязательно хранить в памяти, что может заметно сократить потребление памяти при работе программного обеспечения, которое можно реализовать на основе предлагаемой структуры данных. Математически подобное представление топологии СБИС можно представить следующим образом: A = (a1,a2,...,aAf , (2.12) где at - элемент кортежа, который включает в себя кортеж более низкого уровня иерархии, содержащий нескольких горизонтальных отрезков {Sxm,...,Sxm+pJ, входящих в і-ю горизонтальную полосу; N - число вычислительных узлов. Кортеж А представляет собой упорядоченное множество отрезков по оси ординат.
Количество горизонтальных полос at для /-го топологического слоя можно рассчитать по формуле: A i=, (2.13) где Mi - количество отрезком в каждом at. Предложенная структура данных для представления топологии СБИС удобна тем, что критический слой декомпозирован на горизонтальные полосы. Полученные полосы могут быть обработаны на отдельных процессорах (Рисунок 2.1). Для учета взаимного влияния полигонов, которые расположены близко друг к другу, декомпозиция топологического слоя на горизонтальные полосы выполняется в внахлёст, чтобы обеспечить перекрытие получаемых участков топологического слоя цифровой схемы.
При таком разделении полос между процессорами выполняется таким образом, чтобы равномерно загрузить все доступные процессоры. Для этого необходимо определить число доступных процессоров и разделить топологию на N горизонтальных полос с Мг. При этом ширина полосы не может быть меньше критического параметра технологии двойного шаблона.
Также следует заметить, что для манхэттенской топологии, которая преобразована в предложенную структуру данных, достаточно проверять только условия, сформулированные в выражениях (2.6) и (2.8), причем не для полигонов, а для отрезков.
Исходная геометрия Представление в программе Процессор Процессор Рисунок 2.1. Механизм распределения задач между процессорами Функция 11Е(х), которая определяет множество ребер графа противоречий, может быть задана следующим образом: цЕ(х) = б.тЫ{РоиРо}) ак, (2.14) где dmin(Poi,POj ) - минимальное расстояние между /-ым иу -ым полигонами, которое рассчитывается как расстояние между отрезками, которое находиться с помощью модифицированного алгоритма сканирующей прямой; ак - текущее значения параметра для декомпозиции топологии СБИС из множества а. Множество а задано множеством допустимых значений параметра технологии двойного шаблона: а = {ttmin amin + SP атах) (2-15) где cc-min - минимально допустимое значение параметра двойного шаблона; sp -шаг изменения параметра двойного шаблона; атах - желаемое значение параметра технологии двойного шаблона. Размерность множества а определяет количества итераций выполнения алгоритма построения графа противоречий для топологического слоя.
Параллельный алгоритм раскраски графа противоречий в два цвета
Процесс миграции топологии цифровой схемы для технологии двойного шаблона заключается в декомпозиции топологических слоев, составляющих топологию (Рисунок 1.1).
На Рисунке 3.1 представлен предложенный алгоритм разделения критического слоя Lai для технологии двойного шаблона. На вход алгоритма поступают: топологический слой Lah который представлен в виде множества полигонов; максимальное и минимальное значение параметра декомпозиции a-min и атах; шаг изменения параметра декомпозиции step. На первом шаге алгоритма выполняется поиск решения для технологии двойного шаблона для топологического слоя. Если решение найдено, то производиться разделение топологического слоя Ьщ на два новых слоя: La[ и La". Если решение не найдено, то результатом работы алгоритма является аналитика по неразрешенным противоречиям в топологическом слое Lai. Алгоритм поиска решения для декомпозиции критического слоя для технологии двойного шаблона будет рассмотрен ниже.
В главе 2 были предложены структуры данных и алгоритмы, которые позволяют генерировать граф противоречий Gc для топологического слоя Lat СБИС с манхэттенской (Рисунок 2.1) и неманхэттенской (Рисунок 2.10) геометриями для определенного значения параметра декомпозиции топологии
О-к С использованием графа противоречий можно выполнить поиск решения для декомпозиции топологического слоя на два новых для технологии двойного шаблона. Поиск решения может быть сведен к задаче раскраски графа противоречий в два цвета [3, 4, 22, 25, 29, 30].
На Рисунке 3.2 показан предложенный алгоритм поиска решения для декомпозиции критического слоя цифровой схемы при наличии ограничений технологии двойного шаблона [71]. На вход алгоритма поступают: топологический слой Lah который представлен в виде множества полигонов; максимальное и минимальное значение параметра декомпозиции amin и атах; шаг изменения параметра декомпозиции step. На первом шаге алгоритма текущему значению параметра декомпозиции а присваивается максимальное значение атах. На следующем шаге алгоритма выполняется построение графа противоречий.
Алгоритм поиска решения для декомпозиции критического топологического слоя цифровой схемы для технологии двойного шаблона на основе раскраски графа противоречий в два цвета
Алгоритм для построение графа противоречий для топологического слоя Lai выбирается на основании геометрии: если топологический слой имеет только манхэттенскую геометрию, то используется параллельный алгоритм построения графа противоречий на основе разработанного алгоритма сканирующей прямой (Рисунок 2.2); в случае неманхэттенской геометрии (например, Y- и Х-геометрия) применяется параллельный алгоритм построения графа противоречий на основании структуры данных для «оконных» запросов (Рисунок 2.11).
Далее производиться проверка построенного графа противоречий Gc на двухцветность. Если граф противоречий двухцветный, то решение найдено и результатом работы алгоритма является граф противоречий Gc, раскрашенный в два цвета. Если граф не двухцветный, то значение параметра а уменьшается на шаг step. Процесс поиска решения повторяется до тех пор, пока не будет найдено решение или значение параметра а не станет равным минимальному значению. В таком случае результатом работы алгоритма будет нечеткий цикл в графе противоречий Gc.
На Рисунке 3.3 представлена иллюстрация работы алгоритма для слоя металла элемента 4И с манхэттенской геометрией.
На Рисунке 3.3 а показаны слой металлизации ячейки 4И и граф противоречий до проверки на двудольность. На Рисунке 3.3 б показан граф противоречий по результатам его раскраски в два цвета. На Рисунке 3.3 в отображены два новых слоя, которые были получены в результате декомпозиции исходного слоя.
На Рисунках 3.4 и 3.5 представлен пример трансформации топологии слоя металла ячейки мультиплексора 2X4 библиотеки Low Power Open Cell Library для технологии двойного шаблона по технологическому процессу 45 нм [72] с неманхэттенской геометрией: Х-геометрия, трассировка под 45 градусов. Н Рисунке 3.4 показан слой металла до трансформации. На Рисунке 3.5 показана топология после трансформации: красным показан первый слой после трансформации, слой состоит из 2-х полигонов. Синиам показан второй слой после трансформации, слой состоит из 3 полигонов.
Экспериментальное исследование временной сложности разработанных параллельных алгоритмов с использованием Parallel DPLayout Migrator
В качестве тестовых топологий были выбраны следующие: мультиплексор, 4И, 4ИЛИ-НЕ, Исключающее ИЛИ, ячейка памяти и сумматор. Экспериментальные исследования проводились на рабочей станции с аппаратными характеристиками, которые перечислены в Таблице 1. Выбор данных ячеек обусловлен распространённостью их использования в более сложных функциональных блоках. Трансформация топологии для технологии двойного шаблона производилась для техпроцесса 90 нм.
Необходимо отметить, что использование широко известных критериев качества топологии СБИС, рассмотренных, например, в [94-96], не представляется возможным в связи со специфическим характером трансформации топологического слоя цифровой схемы при наличии ограничений технологии двойного шаблона.
Для оценки качества трансформации топологии для технологии двойного шаблона могут быть использованы различные подходы. Один из них базируется на компьютерном моделировании оптических эффектов. Однако этот подход отличается большими вычислительными затратами для выполнения моделирования процесса литографии. В связи с этим в [3] был предложен подход, базирующийся на использовании эвристических правил. К его недостаткам следует отнести относительно невысокую точность по сравнению с методом, базирующимся на моделировании оптических эффектов. Однако этот подход требует меньших вычислительных затрат и позволяет оценить улучшение топологии с точки зрения последующего воспроизводства.
В диссертационной работе для характеристики качества топологии СБИС после трансформации были предложены следующие метрики [46]: отношение числа полигонов в слое 1 к числу полигонов в слое 2; отношение локальной плотности заполнения слоя 1 к локальной плотности слоя 2 (далее - относительная локальная плотность); минимальное значение из значений относительного минимального расстояния между полигонами в слое 1 и слое 2 (далее - относительное минимальное расстояние). Отметим, что далее в работе для вычисления локальной плотности заполнения слоя расчет производился по следующей формуле: d = SJSy4, (4.1) где S3Jl - площадь полигонов в рассматриваемом слое; Sy4 - площадь, занимаемая слоем.
Относительное минимальное расстояние между полигонами после трансформации рассчитывается как отношение минимального расстояния между полигонами в слое / (i=l, 2) после трансформации к минимальному расстоянию в критическом слое до трансформации.
Результаты работы Parallel DPLayout Migrator приведены на Рисунках 4.10 - 4.17; слой 1 дан красным, слой 2 дан синим. На Рисунках 4.10, 4.13, 4.16, 4.17 радиус вершины рассчитан по формуле (3.1).
На Рисунке 4.11, а приведена топология ячейки 4И, на Рисунке 4.11, б исходный слой металлизации элемента 4И. На Рисунке 4.10 представлен граф противоречий, который содержит 8 вершин и 3 ребра. На Рисунках 4.11, в и г представлены результаты трансформации слоя металлизации для технологии двойного шаблона на 2 слоя. На Рисунке 4.12, а показан исходный слой металлизации ячейки мультиплексора, который является критическим в связи с сильными проявлениями эффекта взаимной дифракции. На Рисунке 4.13 представлен граф противоречий, который содержит 42 вершины и 55 ребер. На Рисунках 4.12, б и в приведены результаты разделения слоя металлизации на 2 слоя. На Рисунке 4.14, а приведена исходная топология элемента 4ИЛИ-НЕ, на Рисунке 4.14, б приведен исходный слой металлизации. На Рисунке 4.16 представлен граф противоречий после раскраски в два цвета с 7-ю вершинами и 4-мя ребрами. На Рисунках 4.14, виг представлены результаты трансформации слоя металлизации для технологии двойного шаблона. На Рисунке 4.15, а приведена исходная топология элемента Исключающее ИЛИ, на Рисунке 4.15, б приведен исходный слой металлизации. На Рисунке 4.17 представлен граф противоречий после раскраски в два цвета с 19-ю вершинами и 24-мя ребрами. На Рисунках 4.15, в и г представлены результаты трансформации слоя металлизации для технологии двойного шаблона.