Разбиение интегральной схемы (1132268)

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

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

Математические методыпроектирования топологии СБИСА.М.МарченкоСодержаниеСведения о КМОП технологии и методологияпроектирования СБИСЗадача разбиения электрической схемыЗадача размещения модулей СБИСЗадача трассировки соединенийМатематические методы проектированиятопологии СБИСЛитература1.2.3.4.5.6.T. Lengauer. Combinatorial algorithms for integrated circuitlayout. Wiley, 1990, 694 p.Naveed Sherwani.

Algorithms for VLSI physical designautomation. Kluwer academic publishers, 1995, 538p.Г.Г.Казеннов, В.М.Щемелинин. Топологическоепроектирование нерегулярных БИС. М., Высшая школа,1990, 109с.Introduction to Algorithms, T. Cormen, C. Lesierson, R. Rivest,The MIT Press, Second Printing, 1996.Handbook of Algorithms for Physical design Automation, Editedby Charles J. Alpert Dinesh P.

Mehta Sachin S. Sapatnekar,2009.Andrew B. Kahng, Jens Lienig, Igor L. Markov, Jin Huю VLSIPhysical Design: From Graph Partitioning to Timing Closure,2011Математические методы проектированиятопологии СБИССведения из теории графовОпределение 1: Конечный граф G=V,E состоит изконечного множества вершин V={v1,…,vn} и конечногомножества ребер E={e1,…,em}, причем EVV дляориентированного графа и E{(x,y):x,yVxy} длянеориентированного.Способы представления графов:Матрица инциденций;Списки ребер (пар вершин, соединенных ребром);Матрица смежностей (весов);Списки инцидентности;Кодовые схемыМатематические методы проектированиятопологии СБИСГрафыГиперграфыbМультиграфыbbaefcdegaadcfМатематические методы проектированиятопологии СБИСcОриентированные графы с цикламиccfabОриентированные графы без цикловdgabfabdeeМатематические методы проектированиятопологии СБИСgНеориентированные графыОриентированные деревьяabafcdegcbefМатематические методы проектированиятопологии СБИСgdhijkRectilinear minimum spanningtree (RMST)b (2,6)Rectilinear Steiner minimumtree (RSMT)b (2,6)Steiner pointc (6,4)a (2,1)c (6,4)a (2,1)Математические методы проектированиятопологии СБИСNetlistaN1bxN3N2N4yzN5c(a: N1)(b : N 2 )(c: N5)(x: IN1 N1, IN2 N2, OUT N3)(y: IN1 N1, IN2 N2, OUT N4)(z: IN1 N3, IN2 N4, OUT N5)(N1: a, x.IN1, y.IN1)(N2: b, x.IN2, y.IN2)(N3: x.OUT, z.IN1)(N4: y.OUT, z.IN2)(N5: z.OUT, c)Pin-Oriented NetlistNet-Oriented NetlistМатематические методы проектированиятопологии СБИСРасстояние между двумя точками P1 (x1,y1) и P2 (x2,y2)dnx2  x1  y2  y1nnd E ( P1 , P2 )  ( x2  x1 ) 2  ( y2  y1 ) 2with n = 2: Euclidean distanced M ( P1 , P2 )  x2  x1  y2  y1n = 1: Manhattan distanceP1 (2,4)dM = 7dE = 5dM = 7P2 (6,1)Математические методы проектированиятопологии СБИССпособы представления графовМатрица инциденций34517196624328512345611010002110000Математические методы проектированиятопологии СБИС3100010401001050011006000110700010180000119011000Способы представления графов3451{1,1,3}, {2,1,2}, {3,1,5},719662432Списки ребер8{4,2,5}, {5,3,4}, {6,4,5},{7,4,6}, {8,6,5}, {9,2,3}5Математические методы проектированиятопологии СБИССпособы представления графов3Матрица смежностей (весов)4162512345610110002101010Математические методы проектированиятопологии СБИС3110100400101150101016000110Способы представления графов341625Списки инцидентности ЗАПИСЬ[v]1235nil2135nil3124nil4356nil5124645Математические методы проектированиятопологии СБИСnil6nilСпособы представления графов1234561011000210101031101004001011Кодовые схемы – код Харари50101016000110110001010100111Математические методы проектированиятопологии СБИСОцените сложность алгоритмаперевода одного описания графа вдругое.Математические методы проектированиятопологии СБИСПоиск в глубину (Depth First Search)Поиск в глубину из вершины vprocedure WG(v)begin рассмотреть v НовыйСмежный[v]  false for u  ЗАПИСЬ[v] do If НовыйСмежный[u] thenWG(u)Поиск в глубину в графеbeginfor v  V doНовыйСмежный[v]  truefor v  V doif НовыйСмежный[v] thenendWG(v)endСвязные компоненты графа можно вычислить за время O(n+m)Математические методы проектированиятопологии СБИСПоиск в ширину (Bread First Search)Поиск в ширину из вершины vprocedure WS(v)begin рассмотреть vОчередь  vНовыйСмежный[v]  falsewhile Очередь   do begin p  Очередь for u  ЗАПИСЬ[p] do if НовыйСмежный[u] thenbegin Очередь  uНовыйСмежный[u]  falseendendendМатематические методы проектированиятопологии СБИССтягивающие деревьяОпределение 2: Деревом называется произвольный неориентированный граф без циклов.procedure WGD(v)begin НовыйСмежный[v]  falsefor u  ЗАПИСЬ[v] doif НовыйСмежный[u] thenbeginT  T  {v,u}WGD(u)endendbegin //главная программаfor u  V doНовыйСмежный[v]  trueT   // множество// найденных реберWGD(r) // произвольная// вершина графаendМатематические методы проектированиятопологии СБИС32576814129131011Математические методы проектированиятопологии СБИСПример32576814129131011Математические методы проектированиятопологии СБИСГиперграфы Определение 10: Конечный граф G=V,E называетсягиперграфом, если элементами множества E являютсяне обязательно двухэлементные, а любыеподмножества множества V. Определение 11: Двудольный граф – это граф G=V,E,такой что V=V1V2 и V1V2=, причем всякое реброиз E соединяет вершину из V1 с вершиной из V2.Математические методы проектированиятопологии СБИСПредставление гиперграфовУтверждение: Гиперграф G=V,E может бытьинтерпретирован как двудольный граф G’=VE,U,где uU: u=(v,e), v – вершина гиперграфа, а e – егогиперребро .контактыМатематические методы проектированиятопологии СБИСцепиМатематические методы проектированиятопологии СБИСПостановка задачиОпределение 1: Пусть дано множество модулей V={v1,…,vn} .

Kpartitioning Pk={C1,…,Ck} состоит из k взаимно непересекающихсякластеров таких, что C1C2 …Ck=V.Определение 2: Min-cut bipartitioning – минимизироватьF(P2)=|E(C1)|=|E(C2)| при C1  0, C2  0.Определение 3: Min-cut bisection - минимизировать F(P2)=|E(C1)|при |w(C1)-w(C2)|   .Определение 4: Size-constrained min-cut bipartitioning –минимизировать F(P2)=|E(C1)| при L  w(Ci)  U, для i=1,2.Определение 5: Minimum ratio cut bipartitioning – минимизироватьF(P2)=|E(C1)|/(w(C1)w(C2))Математические методы проектированиятопологии СБИСПримерыV1V310099V5100Min-cut bipartitioning:{(v1),(v2,v3,v4,v5,v6)};cut size=18100Min-cut bisection:100100{(v1,v2,v4),(v3,v5,v6)};cut size=300V210V4100V6Оптимальный разрез:{(v1,v2),(v3,v4,v5,v6)};cut size=19Математические методы проектированиятопологии СБИСКлассификация алгоритмовдекомпозиции электрической схемыАлгоритмы декомпозицииИтерационныеКернигана-ЛинаФедуччи-МаттеусаМоделирования отжигаТабу-поискГеометрическиеКвадратичноеразмешениеХоллаМетодсобственныхвекторовГенетическиеДругиеВекторноеразбиениеКомбинаторныеМинимизациязадержкиМетодкратчайшегопутиКластерныеНакопленияИерархическиеМатематическоепрограммированиеНечеткоеразбиениеМатематические методы проектированиятопологии СБИСMeTiSИтерационные (moved-based)алгоритмыОсновные парадигмы:i.ii.Структура соседства (neighborhood structure) –определяет способы локального изменения текущегорешения;Предистория – может быть использована длявыбора лучшего продолжения.Преимущества:естественностьпростотаМатематические методы проектированиятопологии СБИСАлгоритм Кернигана-Лина (KL, 1970)Каждый модуль двигается строго одинраз.

KL итеративно меняет местами парумодулей с максимальным значениемцелевой функцииСложность алгоритма – O(n3)Математические методы проектированиятопологии СБИСАлгоритм Кернигана-Лина (определения)Определение 6: External edge cost - для вершиныviA:A,B – начальное разбиениеОпределение 7: Internal edge cost - для вершиныviA:Определение 8: Gain - для вершины viA:Математические методы проектированиятопологии СБИСE (i )  c( e)e {vi ,v j }Ev j BI (i )  c ( e)e {vi ,v j }Ev jAD(i)  E (i)  I (i)Алгоритм Кернигана-Линаprocedure KLbeginPair:array[1:n/2] of pair of [1:n];Cost:array[0:n/2] of integer;Locked:array[1:n] of Boolean;D:array[1:n] of integer;C:array[1:n,1:n] of integer;BestChange: [1:n/2];BestCost: integer;imin, jmin: [1:n];Compute the С and D values;for i from 1 to n do Locked[i]  false ;BestChange  0;BestCost  Cost[0]  cutsize(A,B);for s from 1 to n/2 do Cost[s] ;for i,j from 1 to n such that viA and Locked[i]==false and vjB and Locked[j]== false do if 2С[i,j]-D[i]-D[j]< Cost[s] then Pair[s]  (i,j); Cost[0] 2С[i,j]-D[i]-D[j];(imin, jmin)  Pair[s];Locked[imin]  Locked[jmin]  true;for i,j from 1 to n such that Locked[i]== falsedoif viA then D[i]D[i]–c[i,jmin]+c[i,imin] else D[i]D[i]–c[i,imin]+ c[i,jmin];Cost[s]  Cost[s-1] + Cost[s];if Cost[s] < BestCost then BestChange s; BestCost  Cost[s];for s from 1 to BestChange do Exchange Pair[s];endendМатематические методы проектированиятопологии СБИС100ab-11c2degfh30Все возможные пары: 2c[i,j]-D[i]-D[j], c – вес ребра(a,c,2), (a,d,0), (a,e,-1), (a,h,-1);(b,c,1), (b,d,1), (b,e,0), (b,h,0);C=8(g,c,0), (g,d,-4), (g,e,-1), (g,h,-1);(f,c,-1), (f,d,-1), (f,e,-2), (f,h,0).Математические методы проектированиятопологии СБИС-1Обмен: g  d-2ab-1-2cegВсе возможные пары: 2c[i,j]-D[i]-D[j](a,c,4), (a,e,3), (a,h,1);0dfh0C=4(b,c,3), (b,e,4), (b,h,2);(f,c,1), (f,e,2), (f,h,2).Математические методы проектированиятопологии СБИС0Обмен: a  hab-1-2cegВсе возможные пары: 2c[i,j]-D[i]-D[j](b,c,1), (b,e,2);-2dfhC=5(f,c,3), (f,e,4).Математические методы проектированиятопологии СБИС0Обмен: b  cab-10cegВсе возможные пары: 2c[i,j]-D[i]-D[j](f,e,2).-2dfhC=6Математические методы проектированиятопологии СБИСЛучшее разбиениеСледующий этап: повторить алгоритмдля другого начального разбиения-1-2ab-1-2cdeg0fh0Математические методы проектированиятопологии СБИСC=4Анализ алгоритма1.2.3.4.5.6.Все вершины графа должны быть единичного веса.

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

Тип файла PDF

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

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

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