Размещение модулей интегральной схемы (1132269)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекции 5-6Математические модели и методы синтеза СБИС1СодержаниеСведения о КМОП технологии и методологияпроектирования СБИСЗадача разбиения электрической схемыЗадача размещения модулей СБИСЗадача трассировки соединенийМатематические методы проектированиятопологии СБИСМатематические модели и методы синтеза СБИС3Проблема размещенияМатематические модели и методы синтеза СБИС4Суммарная длина соединений (Total Wirelength)ehcafjilbklfidgeag© 2011 Springer Verlagkcbjdh5Математические модели и методы синтеза СБИСМатематические модели и методы синтеза СБИС6Дискретные методы размещенияФормулировка задачиОбратное размещениеМетод ветвей и границМатематические модели и методы синтеза СБИС7Метод обратного размещенияКлассификация взаимодействий между блокамиB3D4122A5CE01C  2001 2 0 00 4 3 04 0 2 03 2 0 50 0 5 0Математические модели и методы синтеза СБИС8Метод обратного размещенияМатрица расстояний:01D  2341 2 3 4 100 1 2 3 71 0 1 2 62 1 0 1 73 2 1 0 10СуммыэлементовстрокМатематические модели и методы синтеза СБИСD+9Метод обратного размещенияАлгоритм1.

Упорядочить E+ по убыванию2. Упорядочить D+ по убыванию3. Разместить элемент i на позицию синдексом i.Математические модели и методы синтеза СБИС10Метод ветвей и границОпределение: Конфигурационное пространство задачиминимизации является древовидным (tree-structured) еслиможно определить дерево T, с вершинами z которогоассоциируются подмножества конфигураций Sz, такие, что:1.Если r – корень, то Sr содержит оптимальное решение2.Если z – внутренняя вершина T и z1,…,zk – дочерниевершины z, то  Szi= Sz3.Если z – вершина T, то существует нижняя граница Lzc(s)для sSz4.Если z – вершина T, то существует верхняя граница такая,что Uz= или Uz=c(sz), если z – лист, то Lz UzМатематические модели и методы синтеза СБИС11Метод ветвей и границ(продолжение)beginu  , CurrentBest  , вставить (r,Lr) в Drepeat выделить следующий (z,Lz) из Dlfor z’ дочерней вершины z doвычислить Lz’ and Uz’if Uz’<u thenCurrentBest  sz’, u  Uz’удалить все (z’’,Lz’’) такие, что Lz’’u из Dif Lz’<u thenвставить (z’,Lz’) в Dl  min(l,Lz’)until D =endПроверенноепространствоБудет проверятьсяАктивныевершиныНе будет проверятьсяМатематические модели и методы синтеза СБИС12Решение задачи линейного размещения методомветвей и границx4x2x1x5x61x323456Математические модели и методы синтеза СБИС13Правило ветвления, нижняя оценка,целевая функция1 m m1 F ( p)   cij r p (i ) p ( j )  (C R)2 i 1 j 12( A B)  (increase( A)decrease( B))L  Lфикс  Lсвоб  LфсМатематические модели и методы синтеза СБИС14ВетвлениеQQ11Q21Q31Q41Q51Математические модели и методы синтеза СБИСQ6115Математические модели и методы синтеза СБИС16Непрерывные методы размещенияФормулировка задачиМетоды планировкиСиловые алгоритмыМатематические модели и методы синтеза СБИС17Гильотинные алгоритмы ПУ-21.

Определение размеров поля для размещения блоков:Lx = Ly =Si2. Собственно размещение:X1S1=x1LyXS2=(Lx-x1)LyLx=L0<x1<LxY1YМатематические модели и методы синтеза СБИС18Негильотинные алгоритмы ПУ-5S1=x2y1X1S2=(Lx-x2)y2S3=(Lx-x1)(Ly-y2)S4=x1(Ly-y1)X2LxXY1Y2S5=(x2-x1)(y2-y1)LyLx=L0<x1< x2< LxY0<y1< y2< LxМатематические модели и методы синтеза СБИС19Силовой алгоритм размещенияКлассификация взаимодействий между блокамиB3D4122A5CE01C  2001 2 0 00 4 3 04 0 2 03 2 0 50 0 5 0Математические модели и методы синтеза СБИС20Силовой алгоритм. Идея – суперпозиция сил.CBCDAEDBAEсуперпозициясилAМатематические модели и методы синтеза СБИС21Силовой алгоритм размещенияВычисление расширенной матрицы связей1p12 (a, b) 1cab0.0011 1 10.75p12 (a, b, c)    0.75cac ccb 2 4E  0.501.08111p12 (a, c, d , b)  1.331.28cac ccd cdbmin( pij ), i  jeij  0, i  j0.75 0.50 1.08 1.28 0.00 0.25 0.33 0.530.25 0.00 0.50 0.700.33 0.50 0.00 0.200.53 0.70 0.20 0.00Математические модели и методы синтеза СБИС22Силовой алгоритм размещенияВычисление матрицы отношений между блокамиnn1E 2eijn  n i 1,i  j j 1eij  E , i  jrij  0, i  j0.14  0.11 0.470.67  0.00 0.140.000.360.280.08R    0.11  0.36 0.00  0.11 0.09 0.470.280.110.000.41 0.67  0.08 0.09  0.41 0.00 Критерий сильной связности: rij<0Математические модели и методы синтеза СБИС23Силовой алгоритм размещенияВычисление сил притяжения и отталкивания междублокамиk (r  a), r  aF 0,0  r  a k (r  a),0  r  aF 0, r  aМатематические модели и методы синтеза СБИС24Simulated Annealing (Моделированиеотжига) Это итерационный алгоритм. В отличие от жадных алгоритмов, SA можетпринимать в качестве кандидата решение схудшим значением целевой функции.2525Моделирование отжигаСтоимостьНачальное решениеЛокальный минимумГлобальный минимумПространство решений26Моделирование отжига Generate an initial solution Sinit, and evaluate its cost. Generate a new solution Snew by performing a random walk Snew is accepted or rejected based on the temperature T Higher T means a higher probability to accept Snew if COST(Snew) > COST(Sinit) T slowly decreases to form the final solution Boltzmann acceptance criterion, where r is a random number [0,1)COST ( Sinit ) COST ( S new )Te27r27Моделирование отжига,дополнениеLogT543210Числоитераций-1-2012/30/201450100Математические вопросы проектированиятопологии интегральных схем28Современное состояние проблемыКлассификация алгоритмовПримерыМатематические модели и методы синтеза СБИС29Дихотомические – СapoJarrod A.

Roy, David A. Papa, Saurabh N. Adya, Hayward H. Chan, AaronN. Ng, James F. Lu, Igor L. Markov “Capo: Robust and scalable opensource min-cut floorplacer”, ISPD’05, 2005, p.224-226Математические модели и методы синтеза СБИС30Capo – хорошо известная академическая программа размещенияразработанный в Калифорнийском университете (UCLA – University ofCalifornia, Los Angeles). Исходные тексты Capo доступны в Интернете.Capo реализует рекурсивный алгоритм бисекции (min-cut recursive approach).Этот алгоритм основан на подходе “разделяй и властвуй” (divide andconquer). Идея алгоритма состоит в том, что схема и площадь кристалларазбиваются на две части, такие, что количество соединений между этимичастями минимально. Затем задача решается для каждой из частей отдельноаналогичным способом, т.е. каждая часть так же разбивается на две части,и т.д.

Рекурсивное разбиение заканчивается тогда, когда размер каждойчасти станет достаточно малым и на этом уровне задача решается точно длякаждой из полученных частей.Для задачи разбиения на две части с минимальным количеством соединенийне существует эффективных алгоритмов решающих задачу точно, поэтомуиспользуются различные эвристические алгоритмы, причем Capo используетразличные эвристики, в зависимости от размеров разбиваемой части: наверхнем уровне применяются алгоритмы, которые работают быстрее, норешают задачу хуже, чем алгоритмы, используемые на нижнем уровнеМатематические модели и методы синтеза СБИС31Моделирования отжига – DragonTaraneh Taghavi, Xiaojian Yang, Bo-Kyung Choi “Dragon2005:large-scale mixed-size placement tool”, ISPD’05, 2005, p.245-247Математические модели и методы синтеза СБИС32Dragon разработан в северо-западном университете (NorthwesternUniversity) и доступен в ИнтернетеDragon использует рекурсивное делениена четыре части с минимальнымразбиением (recursive min-cutquadrisection), и затем, для детальногоразмещения используетсямоделирование отжига.Первая стадия аналогична алгоритмуиспользуемому в Capo: на первой стадиисхема и площадь кристалла разбиваютсяна четыре части, каждая из которыхпотом также разбивается на четыречасти, и т.д.

до тех пор, пока дляполученных малых частей нельзя будетрешить задачу точноРис. : Рекурсивное разбиение с минимальнымпересечением (Dragon)Математические модели и методы синтеза СБИС33Силовые KraftwerkМатематические модели и методы синтеза СБИС34mPL5Tony Chan, Jason Cong, Kenton Sze “Multilevel generalized forcedirected method for circuit placement”, ISPD’05, 2005, p.185-192Математические модели и методы синтеза СБИС35Программа размещения – mPL5 использует подходмногоуровневой оптимизацииМатематические модели и методы синтеза СБИС36mPL5На первом шаге группы элементов связанных друг с другом,объединяются в один элемент, затем эта операция повторяетсядо тех пор, пока количество элементов не станет достаточномалым (меньше 500).На втором шаге производится размещение получившихся группэлементов так называемым методом квадратичного размещения(quadratic placement).

Для этого производится поиск минимумафункции ,где aij – степень связности между элементами i и j, (xi,yi) –положение элемента i.На третьем, заключительном шаге производитсяпоследовательная детализация размещения, т.е. вычисляетсяположение для каждой из подгрупп элементов, а затем и длякаждого отдельного элементаМатематические модели и методы синтеза СБИС37Результаты, полученные на тестах от210K до 2.1M gatesМатематические модели и методы синтеза СБИС38APlace: гладкая аппроксимация целевой функции1.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций