Построяване на свърх голями алгоритми



страница1/3
Дата31.03.2018
Размер387.29 Kb.
  1   2   3
ЮУГОЗАПАДЕН УНИВЕРСИТЕТ

„НЕОФИТ РИЛСКИ”

Природо математически факултет


Катедра: Комюутърни системи и технологии

КУРСОВ РАБОТА

По


Синтез и анализ на алгоритми

Студенти: Филип Спасо Георгиев - 0726004

Дияна Апостолова - 0726003

Любчо Яанакиевски - 0726078

Димитър Безински

факултет: ПМФ специалност: КСТ IV- курс




Тема: “Построяване на свърх голями алгоритми”
Дата на предаване: 15.12.2010г.

ръководител: .....................................

/доц.д-р П. Миланов/

Благоевград 2010

23. VLSI Layout Algorithms
Автоматизираното проектиране на цифрови схеми е една от многото области на приложения, която ефекивно използва дизайна и анализа на алгоритми. В тази глава ще се съсредоточим върху една област, областта на компютърното проектиране. Ще обсъдим конкретни проблеми в оформлението VLSI и как алгоритмичните техники са били успешно приложени. Тази глава няма да представлява широк преглед на CAD техниките за оформление, но ще привлече вниманието на няколко проблема, които са важни и имат особено приятни алгоритмични решения.

Интегралните схеми са изработени чрез организиране на активни елементи (обикновено транзистори). Може да има няколко слоя, които могат да бъдат използвани за проводници, но има ограничения за това как жиците в различните слоеве могат да се свържат, както и изискванията на разделите между проводниците и елементите.

VLSI вериги съдържат стотици хиляди до милиони транзистори. Поради това не е възможно да се помисли за позициониране на всеки транзистор отделно. Транзисторите са организирани в subcircuits наречени компоненти; това може да стане йерархично, в резултат на няколко нива от общия брой на определяне от страна на отделни транзистори и пълния кръг VLSI. Разположението и свързването на компонентите стават основен проблем в VLSI схемите.

Графическите модели се използват силно, както за моделиране на компоненти и връзките си, така и да улови ограничение между обектите. Геометричните аспекти на оформлението са проблем,който също трябва да бъде моделиран. По-долу представяме няколко от най-известните и най-добре разбраните проблеми в оформлението VLSI.


23.1 Background
Ние ще разгледаме дизайнерски стил, известен като „обща клетка”. Като оформлението и компонентите се различават по размер и степен на функционална сложност. Някои компоненти могат да бъдат от предварително проектирани библиотеки и имат здраво определени положения (напр. регистър банка), а други могат да бъдат дизайн по поръчка, в която градивни елементи са отделни транзистори и проводници. Компонентите могат да бъдат определени йерархично, така, че степента на гъвкавост по отношение на оформлението на всеки компонент е доста променлива. Други дизайнерски стилове, като например стандартните клетки, gate array и sea-of-gates, са по-ограничени, но имат много от същите техники оформление. Проблемът за разположението на чип VLSI често се разделя на два етапа: поставяне на компоненти и маршрутизация на проводници. За това разграждане, веригата е описана като набор от компоненти, както и набор от взаимовръзки между тези компоненти. Компонентите са поставени в равнината, на базата на техния размер, форма и взаимно свързване. Площта, необходима за още неопределен маршрут трябва да бъдат взети под внимание.

Описаните по- горе проблеми при разположението и маршрутизацията е много общо. За да обсъдим по- специфични проблеми и алгоритми, ние ще се използваме по-ограничен модел. В нашия модел, компоненти ще бъдат правоъгълници. Всеки компонент ще съдържа набор от точки по границата им, на терминала. Няколко от тези точки образуват мрежи, които трябва да бъдат свързани помежду си. А оформлението се състои от разположение на компонентите в равнината и набор на пътища в равнината, които не се пресичат, освен в терминалите и при свързване на терминалите. Пътеките са съставени от сегменти в различни слоеве на равнината. (виж фиг. 23.1.)

Макар че тези предположения са общи това ще ни позволи да се илюстрират важни алгоритмични резултати, има доста работа по неправоъгълните компоненти, по-гъвкавите терминали и „over-the-cell” маршрутизацията.

(Фиг. 23.1.)

Фиг.23.1. Пример за оформление. Този план е праволинеен и има два слоя за проводници.

В праволинейното оформление, е на лице една основна двойка ортогонални оси "хоризонтална" и "вертикална" и страните от компонентите са ориентирани успоредно на тези оси. Пътеките на проводниците се състоят от хоризонтални и вертикални сегменти. В нашата дискусия по-долу, и ние често ще говорим за праволинейно оформление.

Ако системата VLSI е твърде голяма, за да се побере на един чип, тогава той за пръв път е разделен на малки парчета, като целта е да се създадат най-малко чипове с най-малко връзки между тях.

Поставянето на елементите е тясно свързано с етажното планиране. Етажното планиране се прави преди дизайна на компоненеите които ще участват в проекта. Резултатът на приблизителната подредба се нарича Floorplan. Определят се грубите позиции на компонентите. Тези позиции могат да повлияят на формата и разположението на всеки компонент, тъй като неговото разполагане се усъвършенства. За йерархично определени компоненти, може да се работи „отдолу-нагоре” за груби изчисления на размера, след това отгоре надолу, за да получите груби изчисления на позиция, а след това отдолу-нагоре отново, за да уточните позиции и размери.

След като получим оформление за една верига VLSI, чрез използване на инструменти или на ръка с редактора за оформления, все още може да се наложи да се направят някои подобрения. Уплътняването се отнася до процеса на изменение на дадено оформление, за да премахнете излишното пространство между елементите на плана, пространството, което не се изисква от правилата за проектиране.

23.2 Техники за поставяне

Техниките за поставяне могат да бъдат разделени на два типа: конструктивен алгоритъм за първоначалното разположение и повтарящ се алгоритми за подобрение. Първоначалното разположение може да бъде произволно разположено или можеда бъде продукт на конструктивен алгоритъм първоначалното разположение. Подобряването на разположението може да се осъществи по различни начини. Набор от допустими движения, т.е. начините, по които по разположенито може да бъде променено. Тези ходове трябва да са прости за изпълнение. Обикновено, компонент се завърта или двойка компоненти се разменят. Итеративният алгоритъм за подобряване многократно променя разположението, оценява новото разположение, и решава дали този ход трябва да бъде като отправна точка за по-нататъшни ходове. Един от най-широко използваните алгоритми за първоначално разположение е рекурсивния метод за разделяне. При този метод, правоъгълнаta област за оформление се определя от размерите и свързаността.

(а) Разделяне на кръга: Всеки връх представлява компонент; областта на компонента е числото във вътрешността на върха. Връзката между устройствата са представени с линии. Няколко линии между върховете показват множество мрежи, свързващи компоненти.

(б) Разделяне на правоъгълник, пропорционално на дял от всяка област.


Като се има предвид графика G = (V, E), функцията ω: V -> N, функцията с: E -> N, и балансиращ фактор. Проблемът на графиката за разделяне е разделена на две подмножества V и V2 са такива, че:



и стойността

е сведена до минимум.

Сред многото техники за разделяне графики, една от наи известните е чрез симулирано закаляване. Тя е подобрена в контекста на оформлението на проблемите чрез Fiduccia и Mattheyses, които движат един връх в даден момент.

Втората група от алгоритми за изграждане на разположения се основава на групиране. При този подход, компонентите са избрани един по един. Компонентите са групирани, така че силно свързан набор от компоненти са близо един до друг. Когато функцията за оформление включва оценка за дължината на проводниците, могат да се ползват няколко метода. Целта е да се определи мярка за всяка мрежа. Тези оценени дължина могат да бъдат сумирани за всички мрежи, за да получим примерна общата дължина проводниците. Също така можем да ползваме половината от периметъра на най-малкия правоъгълник, съдържащ всички терминали на мрежата.


23.3 Уплътняване
Уплътняване може да се направи на различни нива на проекта: цяло оформление може да бъде уплътнено на нивото на транзистори и проводници, също така структурата на отделните компоненти и оформление на компонентите може да бъде уплътнено, без да променя структурата на компонента. С цел опростяване на нашата дискусия, ние ще приемем, че подредбата е праволинейна. За уплътняване на нашия модел ще бъде съставен изцяло от правоъгълници. Тези правоъгълници могат да представляват най-основни геометрични елементи на веригата: части от транзистори или сегменти от проводници, или могат да представляват по-сложни елементи като сложни компоненти. Различават се два вида функции: тези, които са с фиксиран размер и форма, и тези, които могат да се удължат или свиват в една или и две величини. Уплътняването основно представлява двуизмерен проблем. Въпреки това, двуизмерното уплътняване е много трудно. Алгоритми, базирани на линейно програмиране са разработени, но не садостатъчно ефективни да се използват на практика. Ето защо, проблемът обикновено се опростява чрез уплътняване във всяка посока отделно: първо всички възможности на оформление се поставят заедно хоризонтално, така че правилата за проектиране ще позволят запазване на вертикалните фиксирани положения, след това всички характеристики на оформление се поставят заедно вертикално така че правилата за проектиране да позволят запазване на хоризонталното положение фиксирано. Вертикалното уплътняване може в действителност да позволи повече възможности за хоризонталено уплътняване, така че процесът може да се повтори. Този метод не гарантира намирането на минималната област на уплътняване, но е най- оптимално решение за уплътняване.
Ще разгледаме алгоритъма по отношение на хоризонталното уплътняване, вертикалното уплътняване е аналогична. Ние използваме графически модел, при който върховете представляват хоризонтално разположение на функциите; линиите представляват ограничения между позициите на функциите.
Топологично сортиране (G)

  1. SВсички върхове без входящи ръбове (източници)

  2. UV

  3. докато S не е празно

  4. избери който и да е връх от S

  5. РЕВИЗИРАМЕ

  6. за всеки върх u така че (,u)E

  7. извърши Е E – {(,u)}

  8. ако u е източник

  9. тогава S S {u}

  10. U U – {u}

  11. S S – {u}

  12. ако U не е празно

  13. тогава ERROR G не е ациклично

В нашия път проблем с един източник, започваме с един източник, S, върха на левия край от макета. Изчисляваме най-краткия път од s до всеки върх , с ознаката l(). Инициализираме l() преди линия 3 да бъде 0 за l(s) и ∞ за всички останали върхове. Тогава за всеки върх ʋ селектираме линия 4, и всеки край (ʋ,u) който триеме на линия 7 апдейтираме за всички найкратки патища който водат чрез ʋ с l(u)min{l(u), l(ʋ) + дължината(u, ʋ)}. Когато топологичното сортиране е завършено l(ʋ) ще съдържа найкраткия път от s до ʋ. Алгоритъма отнема O(|V| + |E|) време.

Внашия найпрост случай всички ограничения са минимални. В общия случай понякога се налага да имаме максимално сепарационни ограничения. Това се случва когато ограниченията за свързаност се изоилзват и когато ограниченията за изпълнение, който ограничават дължината на използваните кабели. Тогава имаме ограничения от типа:



+

Или еквивалентно



-

Такова ограничение е моделирано като край от върха B до върха A с тегло . Например, за да моделираме хоризонтален кабел W който има интервал от l до r по чието протежение може да се приключи компонента C (вижте Фиг. 23.4) използваме двойката ограничения





Фиг. 23.4.

- -l и - r

След като се позволат двете и максимум и минимум сепарационни ограничения имаме много по обща система линейни ограничения



x – y d

произтичащия граф ограничения не трябва да е ацикличен. За разрешаване на алгоритмът за найкраток път с един източник, ще ни трябва O(|V||E|) временски Белман-Форд алгоритъм. Този алгоритаъм работи само ако графа не съдържа негативни цикли. Ако ограничения граф е получен от оформление което отговаря на дадените ограничения, това ще е вярно, тъй като отрицателните цикли претставляват набор от технически невозможни ограничения. Белман-Фордовия алгоритъм може да го детектира това състояние, тъй като набора от ограничения е невъзможен, оформления не могат да бъдат произведени.

Ако ограничения граф е получен от оформление което отговаря на всички ограничения, наблюдение на Maley [21] ни позволяава да използваме алгоритма на Дийкстра, да изчисли найкратките патища по-ефективно. За използване на алгоритма на Дийкстра теглата на всички краища трябва да са положотелни. Maley наблюдавал че когато првоначално оформление съществува, првоначалните позиции на функциите могат да се използват за преобразуване на всички дължини както следва. Нека и са првоначални позиции от функциите A и B. Ограничения граф е модифициран така че дължината на края (, ) от върха на А до върха на B става дължина(, ) + - . Тъй като първичното оформление отговаря на ограничението - дължина(, ), получаваме - - дължина(, ) или - + дължина(, ) 0.

Дори когато ограничения граф не е ацикличен и когато първично невъзможно оформление не е налично, ограничение от тип или структура от ограничения могат да се използват за да се получат по-бързи алгоритми. Например, Lengauer и Mehlhorn дават O(|V|+|E|)-времен алгоритъм когато ограничения граф има специална структура наречена “Chain DAG” или “Веригата на ДАГ” която се намира когато единствените ограничения освен минималните сепарационни ограничения са тези които идват от гъвкави конекции както тези моделирано от Eqs. Liao и Wong и Meta претставлят O(|V|+|E|)-временни алгоритми, кадето е набор от ръбове, получени от ограничения различни от минимални сепарационни ограничения. Тези алгоритми се основават на наблюдението, че E - е директно ациклен граф. Топологичното сортиране се използва като подпрограма за решаване на проблема за найкраток път с един източник с ръбове E - . Солуцията на този проблем може да наруши ограниченията претставени от . Така че, след намиране найкратките пътища за E - , позициите се променят в опит да отговарят на другите ограничения, алгоритъма за найкратък път с един източник за E - се кандидатира отново. За еднодимензионалното уплътняване което обсъдихме игнорира мн практически въпроси. Факта че правите кабели свързват два компонента, може да е и артивакт на оформлението, но тя поставля компонентите в lock-step по време на уплътняване. Добавляне на огъване на тела ще позволи на компонентите да се придвижват независимо. Друг въпрос е позволяване компонентите да си променят техния ред. Тази промяна дава по-малко оформление, но проблема с уплътняване става по-голям. Такъв обмен може да създаде проблеми към свързване на кабелите.



Оразмеряване Етажа и Класически Разделяй и Владей

Проблема който сега ще разгледаме, наречен оразмеряване етажа, е срещан през определени стилове на разположение на етажа. С някои разумни предложения, проблемът може да бъде решен оптимално с полином-времен алгоритъм това е пример за класическо разделяне. Оразмеряване етажа възниква когато етажа е първонарочно предвиден като правоъгълно оформление, претставля чип, в подправоъгълници. Всеки подправоъгълник отговаря на съответен компонент. Приемаме че правоъгълното разделяне е праволинейна. За тази дисклусия, взимаме набор от компоненти C, с „план за C”, ще означаваме правоъгълна част от правоъгълник в |C| правоъгълниците и един към друг картиране от C до подправоъгълниците. Този дял включва релативната позиция на компонентите, но подправоъгълниците са ограничени да имат приблизително същата площ както и компонентите, но да не са и в съотношение. Когато компонентите се постават в местата им оформлението ще се промени. Освен това, възможно е да се ориентира всеки компонент, така че подългите димезнии да са хоризонтални или вертикални. Това ще го олицетворим чрез shape function (форма функция).

Дефиниция: Форма функция за даден компонент е картографиране s:[ ,] [ , ] такова че s монотонно да намалява. Тълкуването на s(w) е това че е минималната висина на всеки правоъгълник с ширина w който съдържа оформление от компонент. е минималната ширина а минималната висина. Изискването монотоност претставлява факт така че ако съществува оформление за компонент кой се вписва в ws(w) правоъгълника, със сигурност трябва да се побира в (w+d) *s(w) правоъгълник за всеки d0, ето защо, s(w+d)s(w).

Дадена действителна форма, за всеки компонент, определяща минималната ширина и висина на правоъгълния план претставля проблем на уплътняване. Всяка димензия е направена отделно, и два ограничителни графики са изработени. Ще обсъдим хоризонталната ограничителна графа; вертикалната е аналогична. Хоризонталната ограничителна графа има върх за всяка вертикална страна от подправоъгълникот, в правоъгълната част. Съществува пряк раб от всеки връх претставляващ лявата страна на подправоъгълника до всеки връх претставляващ дясната страна от подправоъгълник. Има и два насочени ръбове помежду върховете претставляват две








  1   2   3


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница