Трассировка соединений в интегральной схеме (1132270)

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

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

Лекции 8-912/30/2014Математические вопросы проектированиятопологии интегральных схем1Эйлеровы путиОпределение 5: Эйлеровым путем в графе называетсяпуть v1,…,vm+1, такой, что каждое ребро eEпоявляется в последовательности v1,…,vm+1 в точностиодин раз как e={vi,vi+1}. Если v1 = vm+1, то такой путьназывается эйлеровым циклом.Теорема 2: Эйлеров путь в графе существует тогда итолько тогда, когда граф связный и содержит не болеечем две вершины нечетной степени .12/30/2014Математические вопросы проектированиятопологии интегральных схем2Алгоритм нахождения эйлерова циклаbegin2.3.4.5.16.end15.End12/30/2014СТЕК  ; CE  ;//CE-цикл в виде последовательности вершинv  произвольная вершина графаСТЕК  vwhile СТЕК   do6.begin v  top(СТЕК)7.if ЗАПИСЬ[v]   then8.

begin u  первая из ЗАПИСЬ[v]9. СТЕК  u//удалить ребро из {v,u} графа10. ЗАПИСЬ[v]  ЗАПИСЬ[v] \{u};10. ЗАПИСЬ[u]  ЗАПИСЬ[u] \{v};11. v  u13.14.end12. endelsebegin v  СТЕК ; CE  v;// ЗАПИСЬ[v] = Математические вопросы проектированиятопологии интегральных схем3СТЕК={}V=CE={}U=72ЗАПИСЬ51: (2,3,4,10)2: (1,4)813: (1,4,10,11)4:(1,2,3,7,6,11)45: (6,7,8,9)6: (4,5)37: (4,5)961012/30/2014118: (5,9)9: 5,8()10: (1,3)11: (3,4)Математические вопросы проектированиятопологии интегральных схем4СТЕК={}V=?CE={1,10,3,11,4,3,1,4,7,5,9,8,5,6,4,2,1}U=?72ЗАПИСЬ51: (2,3,4,10)2: (1,4)813: (1,4,10,11)4: (1,2,3,7,6,11)5: (6,7,8,9)46: (4,5)37: (4,5)8: (5,9)961012/30/20149: (5,8)10: (1,3)11: (3,4)11Математические вопросы проектированиятопологии интегральных схем5Утверждение 1. Для последовательнойцепочки транзисторов Эйлеров путьвсегда существует.Утверждение 2.

Для параллельнойцепочки транзисторов Эйлеров циклвсегда существует.12/30/2014Математические вопросы проектированиятопологии интегральных схем6Нахождение Эйлеровых путей вэлектрической схемеTransistor Placement for Noncomplementary Digital VLSI Cell Synthesis, MICHAEL A. RIEPE and KAREMA.

SAKALLAH, ACM Transactions on Design Automation of Electronic Systems, Vol. 8, No. 1, January2003.An example of a complex gate designed in the “functional cell” style of Uehara and Van-Cleemput [1981]12/30/2014Математические вопросы проектированиятопологии интегральных схем7Иллюстрация идеи12/30/2014Математические вопросы проектированиятопологии интегральных схем8Нахождение кратчайших путейв графе12/30/2014Математические вопросы проектированиятопологии интегральных схем9Кратчайшие путиОпределение 7: Ориентированный граф G=V,Eназывается взвешенным, если каждой дуге u,vEпоставлено в соответствие некоторое вещественноечисло a(u,v), называемое весом данной дуги, крометого, a(u,v)=, если u не соединена с v. Еслипоследовательность вершин v0,…,vp определяет путь вG, то его длина определяется как сумма a(vi-1, vi).Лемма 1: При условии положительной длины всехконтуров  s,tV  v : d(s,t)=d(s,v)+a(v,t) .12/30/2014Математические вопросы проектированиятопологии интегральных схем10Алгоритм нахождения кратчайшего путиДанные: расстояния D[v] от вершины s до всех остальных вершин v  V,фиксированная вершина t, матрица весов ребер A[u,v], u,v  V.Результаты: СТЕК содержит последовательность вершин, определяющуюкратчайший путь из s в t.beginСТЕК  ; СТЕК  t; v  t;while v  s dobeginu  вершина, для которой D[v] = D[u] + A[u,v];СТЕК  u; v  u;endend12/30/2014Математические вопросы проектированиятопологии интегральных схем11Вычисление расстояний12/30/2014Математические вопросы проектированиятопологии интегральных схем12Алгоритм Форда и БеллманаДанные: орграф V,E с n вершинами и выделенным источником s  V,фиксированная вершина t, матрица весов дуг A[u,v], u,v  V.

Контурыотрицательной длины отсутствуют.Результаты: расстояние от источника до всех вершин графа D[v]=d(s,v),v  V.beginfor v  V do D[v]  A[s,v]; D[s]  0;for k  1 to n-2 dofor v  V \ {s} dofor u  V do D[v]  min(D[v], D[u]+A[u,v])end12/30/2014Математические вопросы проектированиятопологии интегральных схем13Работа алгоритма Форда и Беллмана2(3)3(3)(1)(8)(2)133381-524(1)k1D[1]D[2]D[3]D[4]D[5]01310144-120143-130143-1(-5)(3)(4)512/30/20144Математические вопросы проектированиятопологии интегральных схем14Алгоритм ДейкстрыДанные: орграф V,E с n вершинами и выделенным источником s  V,фиксированная вершина t, матрица весов дуг A[u,v], u,v  V. Все весанеотрицательны.Результаты: расстояние от источника до всех вершин графа D[v]=d(s,v),v  V.beginfor v  V do D[v]  A[s,v]; D[s]  0;T  V \ {s};while T   dobeginT  T \ {u}// D[u] = min(D[p]: p  T )for v  T do D[v]  min { D[v], D[u]+A[u,v] }endend12/30/2014Математические вопросы проектированиятопологии интегральных схем15Работа алгоритма Дейкстры(7)2(5)(1)3(2)(1)6(1)(1)(4)(2)41(3)12/30/2014D[1]D[2]D[3]D[4]D[5]D[6]01016301637801637701637785Математические вопросы проектированиятопологии интегральных схем16Алгоритм ФлойдаДанные: матрица весов дуг A[i,j] орграфа без контуров отрицательнойдлины.Результаты: расстояния между всеми парами вершин D[i,j]=d(vi,vj),beginfor i=1 to n dofor j=1 to n do D[i,j]  A[i,j];for i=1 to n do D[i,i]  0for m=1 to n dofor i=1 to n dofor j=1 to n doD[i,j]  min(D[i,j], D[i,m]+ D[m,j] )end12/30/2014Математические вопросы проектированиятопологии интегральных схем17Инкрементальный алгоритм поиска кратчайшихпутей в графеСтатическая задача:Алгоритм Флойда-Уоршелла O(V3)Алгоритм Дейкстры O(V2)Динамическая задача:12/30/2014Нет эффективных алгоритмов, известныеалгоритмы работают слишком долгоМатематические вопросы проектированиятопологии интегральных схем18Маршрут проектирования топологииСБИСВвод схемыРазбиениеУпорядочивание областей трассировкиПланировкаНачальное размещениеОпределение областей трассировкиГлобальная трассировкаОценка качества12/30/2014Детальная трасссировкаОценка качестваСжатиеЗапись в БДМатематические вопросы проектированиятопологии интегральных схем19Топология на основе стандартныхячеек12/30/2014Математические вопросы проектированиятопологии интегральных схем20Классификация алгоритмовтрассировки12/30/2014Математические вопросы проектированиятопологии интегральных схем21V-based methodologyConcrete ViewMake DRC-clean layoutby compactionSplit in MFGRestore MFGCoarse MFGfor detailedroutingRegioncoarseningand resourcereservation12/30/2014DetailedRoutingRouterefinementGlobalRoutingМатематические вопросы проектированиятопологии интегральных схем22ГлобальнаятрассировкаN3N1N3ДетальнаятрассировкаN3N3N3N1N2N3N1N1N2HorizontalSegment*литературный источник[6] слайды 49-5023N1N2VerticalSegmentN1N2ViaПредставление областей трассировкиГраф трассировки (Grid graph model)1234512345678910678910111213141511121314151617181920161718192021222324252122232425ggrid = (V,E), where the nodes v  V represent therouting grid cells (gcells) and the edges representconnections of grid cell pairs (vi,vj)24*литературный источник[6] слайды 53-55Представление областей трассировки 2Граф связности каналов (Channel connectivity graph)44551 236912378678G = (V,E), where the nodes v  V represent channels,and the edges E represent adjacencies of the channels259Представление областей трассировки 3Граф связности пересений каналов (Switchbox connectivity graph)145298112673115210131449121013673118G = (V, E), where the nodes v  V represent switchboxes14and an edge exists between two nodes if the corresponding switchboxesare on opposite sides of the same channel26Прямоугольная трассировка (Rectilinear Routing)B (2, 6)B (2, 6)C (6, 4)A (2, 1)S (2, 4)A (2, 1)Rectilinear minimumspanning tree (RMST)Rectilinear Steinerminimum tree (RSMT)*литературный источник[6] слайды 59-6027C (6, 4)Дерево Штейнера минимальнойдлины (SMT) Теорема Ханана: дерево Штейнера минимальнойдлины существует на Ортогональной Опорной Сетке(ООС) . Оценка числа точек Штейнера: s  n-2. Оценка длины дерева Штейнера: MST/SMT  3/2. Простой эвристический алгоритм – использоватьсканирующую линию на ООС12/30/2014Математические вопросы проектированиятопологии интегральных схем28Преобразование связывающего дерева в деревоШтейнераp2p2p3p1p3p1S1p1Construct L-shapes between pointswith (most) overlap of net segments29p2p2p3Sp3p1Final tree (RSMT)A Sequential Steiner Tree Heuristic1.2.3.4.5.Find the closest (in terms of rectilinear distance) pin pair,construct their minimum bounding box (MBB)Find the closest point pair (pMBB,pC) between any point pMBB on the MBBand pC from the set of pins to considerConstruct the MBB of pMBB and pCAdd the L-shape that pMBB lies on to T (deleting the other L-shape).If pMBB is a pin, then add any L-shape of the MBB to T.Goto step 2 until the set of pins to consider is empty30Пример.

Исходные данные.131Пример. Шаг 1.12321Пример. Шаг 1.pc312MBB331Пример. Шаг 2.31213122pMBB344Пример. Шаг 3.31213122312434535Пример. Шаг 4.312312123124345312463645Пример. Шаг 5.31231213122434531246312465737545Пример. Шаг 6.3123121312243453124631246573853124566745Пример. Решение.3123121312243453124631246573953124566745Классификация алгоритмовтрассировки12/30/2014Математические вопросы проектированиятопологии интегральных схем40Волновая трассировка (Maze)Основная идея метода – волновой алгоритм (Lee, 1961) Используется поиск в ширину (BFS) Путь определяется обратным проходом с минимизацией подополнительному критерию (число поворотов) Всегда находится кратчайший путь, если он существует12/30/2014Математические вопросы проектированиятопологии интегральных схем41Проблемы волновой трассировкиБольшой расход памятиВыч. Сложность O(n2)Последовательный характер трассировки12/30/2014Математические вопросы проектированиятопологии интегральных схем42.

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

Тип файла PDF

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

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

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