close

Вход

Забыли?

вход по аккаунту

Памятка;pdf

код для вставкиСкачать
Параллельный алгоритм трансформации слоя
топологии субмикронных СБИС с произвольной
геометрией для технологии двойного шаблона
В.А. Шахнов, Л.А. Зинченко, В.А. Верстов
МГТУ
им. Н.Э. Баумана
Содержание
•  Постановка задачи
•  Параллельные алгоритмы трансформации топологии СБИС
для технологии двойного шаблона
o  Обработка топологии
o  Формирование графа противоречий
o  Параллельный алгоритм декомпозиции топологии СБИС
•  Экспериментальные исследование
•  Заключение
МГТУ
им. Н.Э. Баумана
Содержание
•  Постановка задачи
•  Параллельные алгоритмы трансформации топологии СБИС
для технологии двойного шаблона
o  Обработка топологии
o  Формирование графа противоречий
o  Параллельный алгоритм декомпозиции топологии СБИС
•  Экспериментальные исследование
•  Заключение
МГТУ
им. Н.Э. Баумана
Постановка задачи
Направления развития литографии
Первый год производства
193 нм Иммерсия с водой
193 нм Иммерсия Двойной Шаблон
Экстремальный Ультрафиолет
Экстремальный Ультрафиолет
193 нм Иммерсия Двойной / Мульти
Шаблон
Безмасочная литография
Наноимпринтная литография
нет доказанного оптического решения ниже
Экстремальный Ультрафиолет
193 нм Инновационная Иммерсия
Мульти Шаблон
Безмасочная литография
Наноимпринтная литография
Прямая самосборка
Интерфереционная литография
Экстремальный Ультрафиолет
Безмасочная литография
Наноимпринтная литография
Наноимпринтная литография
Интерфереционная литография
4
МГТУ
им. Н.Э. Баумана
Постановка задачи
Декомпозиция топологии для двойного шаблона
Конфликты
Слой 1
Слой 2
5
Кафедра ИУ-4
МГТУ
им. Н.Э. Баумана
Постановка задачи
Обработка неманхэттеновской геометрии:
• 
Радиационно-стойкие схемы
o  H-транзисторы
o  O-транзисторы
6
Кафедра ИУ-4
МГТУ
им. Н.Э. Баумана
Постановка задачи
Ручное
проектирование
7
Кафедра ИУ-4
САПР
САПР и
суперкомпьютеры
МГТУ
им. Н.Э. Баумана
Содержание
•  Постановка задачи
•  Параллельные алгоритмы трансформации топологии
СБИС для технологии двойного шаблона
o  Обработка топологии
o  Формирование графа противоречий
o  Параллельный алгоритм декомпозиции топологии СБИС
•  Экспериментальные исследование
•  Заключение
МГТУ
им. Н.Э. Баумана
Алгоритм декомпозиции топологии
МГТУ
им. Н.Э. Баумана
Алгоритм декомпозиции топологии
•  Внутренняя структура позволяет
находить конфликты для одного
полигона за:
O(lgN + K),
где N – количество полигонов, K –
количество конфликтов
МГТУ
им. Н.Э. Баумана
Содержание
•  Постановка задачи
•  Параллельные алгоритмы трансформации топологии СБИС
для технологии двойного шаблона
o  Обработка топологии
o  Формирование графа противоречий
o  Параллельный алгоритм декомпозиции топологии СБИС
•  Экспериментальные исследование
•  Заключение
МГТУ
им. Н.Э. Баумана
Внутренняя структура данных для обработки
топологии
Полигон
Полигон 1
Представление в виде
отрезков
Отрезок 1
Полигон
•  Структура данных для
представления Отранзистора.
•  Полигон, состоящий из
N-точек,
представляется в виде
N-отрезков
Вершина 1
Точка 1
Вершина 2
Точка 2
Вершина 3
Вершина 4
.
.
.
Вершина N
Отрезок N
Полигон
Точка 1
Точка 2
•  Отрезки хранятся в
структуре данных для
оконных запросов
(какие отрезки
попадают в окно)
МГТУ
им. Н.Э. Баумана
Распределение задач между процессорами
i-ая полоса, процессор i
Исходная геометрия
Представление в программе
i+1 полоса, процессор i+1
Тестовый слой с F- и О-транзисторами для 2-ух процессоров
МГТУ
им. Н.Э. Баумана
Содержание
•  Постановка задачи
•  Параллельные алгоритмы трансформации топологии СБИС
для технологии двойного шаблона
o  Обработка топологии
o  Формирование графа противоречий
o  Параллельный алгоритм декомпозиции топологии СБИС
•  Экспериментальные исследование
•  Заключение
МГТУ
им. Н.Э. Баумана
Формирование графа противоречий и графа ограничений
Граф ограничений:
,
G1 = (V1, E1),
где V1 = {v11, v12, ..., v1n} – множество вершин графа
ограничений;
|V1| = n – число геометрических объектов в заданной
топологии СБИС;
E1 = {e11, e12, ..., e1m} – множество ребер в графе
ограничений,
|E1| = m1 – число ребер в графе ограничений.
1
Кафедра ИУ-4
МГТУ
им. Н.Э. Баумана
Формирование графа противоречий и графа ограничений
Граф противоречий:
,
G2 = (V2, ~E2),
где V2 = {x21, x22, ..., x2n} – множество вершин графа
противоречий;
|V2| = n – число геометрических объектов в заданной
топологии СБИС;
~E2 = {e21, e22, ..., e2m2} - множество ребер графа
противоречий, которое определяется функцией µE(x) от
параметра технологии двойного шаблона x,
|E2| = m2 – число ребер в графе противоречий.
1
Кафедра ИУ-4
МГТУ
им. Н.Э. Баумана
Алгоритм поиска конфликтов
Размер прямоугольного окна R(Si) определяется текущим
значением α.
Для всех отрезков, попавших в окно, производится проверка:
d(Si, Sk) < α, где d – расстояние между отрезками, Sk – отрезок,
попавший в окно R(Si).
1
Отрезок Si
Окно R для отрезка
Si
1
2
2
Тестовый слой с F- и О-транзисторами для 2-ух процессоров
МГТУ
им. Н.Э. Баумана
Содержание
•  Постановка задачи
•  Параллельные алгоритмы трансформации топологии СБИС
для технологии двойного шаблона
o  Обработка топологии
o  Формирование графа противоречий
o  Параллельный алгоритм декомпозиции топологии
СБИС
•  Экспериментальные исследование
•  Заключение
МГТУ
им. Н.Э. Баумана
Layout Decomposition Algorithm
Алгоритм основан на проверке на
двуцветность графа противоречий, который
сформирован для:
где min – минимальное
значение α,
max – максимальное
значение α,
step – шаг для изменения
текущего значения α.
МГТУ
им. Н.Э. Баумана
Layout Decomposition Algorithm
Проверка на двуцветность – основная
часть алгоритма, которая может быть
выполнена в параллельном режиме.
МГТУ
им. Н.Э. Баумана
Параллельный алгоритм проверки графа на
двуцветность
•  Предложен параллельный
алгоритм поиска в ширину для
проверки графа на двуцветность.
•  Для каждого значения α мы можем
найти декомпозицию слоя на два
новых или нечетный цикл
конфликтов в исходном слое.
МГТУ
им. Н.Э. Баумана
Результат работы алгоритма
Трансформация элемента 4И для технологии двойного шаблона с
помощью разработанных алгоритмов
Слой металлизации
2
Кафедра ИУ-4
Граф противоречий
Слой после декомпозиции
МГТУ
им. Н.Э. Баумана
Результат работы алгоритма
Мультиплексор 2x4, металл 45о
Инвертор х32, металл
Сумматор:
•  Металл
•  поликремний
2
Кафедра ИУ-4
МГТУ
им. Н.Э. Баумана
Содержание
•  Постановка задачи
•  Параллельные алгоритмы трансформации топологии СБИС
для технологии двойного шаблона
o  Обработка топологии
o  Формирование графа противоречий
o  Параллельный алгоритм декомпозиции топологии СБИС
•  Экспериментальные исследование
•  Заключение
МГТУ
им. Н.Э. Баумана
«Parallel DPLayout Migrator»
Операционная система: CentOS
Язык программирования: С++
Технологии параллельных вычислений:
• OpenMP
2
Кафедра ИУ-4
МГТУ
им. Н.Э. Баумана
Результаты экспериментального исследования
Библиотека 45 nm Nangate Open Cell Library, параметр
технологии двойного шаблона – 90 нм.
LowPowerOpenCellLibrary
120
100
80
60
Ячеек декомпозировано , шт.
40
Всего ячеек, шт.
20
0
Поликремний
Металл 1
Металл 2
Металл 3
Общий итог
NangateOpenCellLibrary
450
400
350
300
250
Ячеек декомпозировано , шт.
200
Всего ячеек, шт.
150
100
50
0
Поликремний
2
Металл 1
Кафедра ИУ-4
Металл 2
Металл 3
Общий итог
МГТУ
им. Н.Э. Баумана
Результаты экспериментального исследования
Библиотека 45 nm Nangate Open Cell Library, параметр
технологии двойного шаблона – 90 нм.
LowPowerOpenCellLibrary
1000
800
600
Количество полигонов, шт.
400
Количество конфликтов, шт.
200
Конфликтов разрешено, шт.
0
Поликремний
Металл 1
Металл 2
Металл 3
Общий итог
NangateOpenCellLibrary
8000
7000
6000
5000
Количество полигонов, шт.
4000
Количество конфликтов, шт.
3000
Конфликтов разрешено, шт.
2000
1000
0
Поликремний
2
Кафедра ИУ-4
Металл 1
Металл 2
Металл 3
Общий итог
МГТУ
им. Н.Э. Баумана
Результаты исследования временной
сложности алгоритмов
• 
t, с
• 
Зависимость от
количества процессоров
t, с
25
Зависимость от
размерности задачи
10000
1000
20
100
15
10
1
10
0,1
5
0,01
0
1
2
3
4
5
6
7
8
Количество нитей выполнения, шт
2
Кафедра ИУ-4
0,001
18
180
с чтением
1800
18000
180000 1800000
без чтения Полигоны, шт
МГТУ
им. Н.Э. Баумана
Содержание
•  Постановка задачи
•  Параллельные алгоритмы трансформации топологии СБИС
для технологии двойного шаблона
o  Обработка топологии
o  Формирование графа противоречий
o  Параллельный алгоритм декомпозиции топологии СБИС
•  Экспериментальные исследование
•  Заключение
МГТУ
им. Н.Э. Баумана
Заключение
1. 
2. 
3. 
4. 
5. 
6. 
3
Предложены и разработаны параллельные алгоритмы трансформации топологии СБИС с
манхэттеновской и произвольной геометрии для технологии двойного шаблона для
высокопроизводительных вычислительных систем, которые позволяют увеличить
минимальное расстояние между полигонами в топологическом слое в среднем в 1,35 раза
для первого слоя относительно исходного, получаемого в результате декомпозиции
критического слоя, и в 2,78 раза для второго слоя относительного исходного, что может
существенно повысить выход годных при производстве СБИС.
Разработанные параллельные алгоритмы трансформации топологии субмикронных
СБИС для технологии двойного шаблона проводить трансформацию топологий
субмикронных СБИС с О- и H-транзисторами, которые широко применяются в
радиационно-стойких схемах.
Реализован программный комплекс «Parallel DPLayout Migrator» на основе
разработанных алгоритмов.
Проведены теоретические и экспериментальные исследования предложенных и
разработанных алгоритмов, которые показали, что временная сложность предложенных
алгоритмов не превышает nlog(n) и что наблюдается снижение времени трансформации
топологии СБИС для технологии при использовании вычислительных ресурсов
многоядерных вычислительных систем.
Определена основная метрика для определения качества работы разработанных
алгоритмов – «Относительное минимальное расстояния» между полигонами.
Определено дальнейшее направление проведения исследований.
Кафедра ИУ-4
МГТУ
им. Н.Э. Баумана
Вопросы?
Спасибо за внимание!
31
МГТУ
им. Н.Э. Баумана
1/--страниц
Пожаловаться на содержимое документа