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



страница3/3
Дата31.03.2018
Размер387.29 Kb.
#63983
1   2   3

while I ≤ |N| - t

  • do if bi+t-ait and ai+t –bit

  • then do i I +1

  • else do tt + 1

  • return t

    Деъствителния маршрут за канала на речната маршрутизация могат да бъдат произведени в алчен начин от маршрута една мрежа към момента от ляво на дясно, и маршрутизациятана всяка мрежа да започва от левия терминал. Маршрутизацията на всяка мрежа пътува вертикално когато не е блокирана от по-рано маршрутизираната мрежа, пътува хоризонтално докато може да започне да пътува вертикално пак или докато не достигне хоризонталната позиция на дясния терминал на мрежата. На тези маршрутизация в най-лошия случай и е неопхпдимо време O(n2).

    Изследователски проблеми и обобщения

    Тази глава дава общ преглед на проблемите при проектирането, произтичаяи от комютърното оформление на схеми VLSI и някои от алгоритмичните исползвани потходи. Алгоритамът представен в тази глава разчита на теоретичните основи разглеждани в другите глави. Графичните модели преобладават и и често се исползват за уляване на ограничения. Тъй като много от проблемите са NP-изпълними, евристички се исползват. Изследванията продолжават на този област, за да намерат методи за решаване на теси проблеми- както в ефективноста така и в качеството на решението- и за моделиране и решаване на нови проблеми, офомления, произтичащти от всякога-промянаъки я технологията на производството и опаковане на VLSI. Оформлени са техники за се по-популярните технологии, като например областа за програмируеми масиви и и могочипови модули са били и продолжават да бъдат разработени.



    Основната тема в моменталните изследвания в VLSI разглеждането е ефективноста на веригата и оформлението. Като характеристиката на продолжава да се свива, закаснението по проводника се превръща в все по-голяма част от общите закаснения на схемата. Ето защо, закаснението въведено от маршрутизацията е все по-важно. За разглеждането на испълнението им е неопходимо нова техника, не само за маршрутизацията но и за разделяне и за настаняване. В някой случай, техниките площ-базиран шаблон са раширени да се счита закаснение. На пример, симулираниат подход до настаняването е бил променен за да взема предвид закаснението на критичните пътища. Все пак, много изследвания са разработили нов подоход за обврзана с постигнатите резултати офомления. На пример, един намира исползването на техниките на линейното програмиране, цяло числено програмиранеи дори специализирани по-повисок ред програмиране б последно време изпълнение-задвижване оформления. Часовник-дърво маршрутизаци, свеждане на минимум часовник забавяне и часовник наклон, е получаван като вашен елемент от задвишване на изпълнението на плана.

    Определяне изрази

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

    Плътност на канала: Ориентира канал така че горния и долния край са хоризонтални ръбове. Тогава плъттноста на всяка вертикална линия пресичаща канала е броя на мрежи който омат терминали и на лявата и на дясната страна от вертикалната линия. Мрежите ц терминали на вертикалната линя допринася за плътноста освен ако всички терминали на мрежата лежът на вертикалната линия. Плътноста на канала е максималната плътност на било кой вертикален разрез на канала.

    Канална маршрутизация: Проблема за определяне на маршрутизация т.е. пътеки и слоеве за кабели за канала на маршрутизация.

    Уплътняване: Процеса на промяна дадени оформления за премахване на допълнително пространство между елементите на оформлениео.

    Floor plan: Приблизително оформление на схема, което е извършено преди структурата на съставните елементи на веригата да са напълно определени.

    Floor plan sizing: Даден floor plan и набор от компоненти, бсеки от които с формата на функцията, намиране на работа на специфичните форми на компонентите, така че областта на оформлението е сведено до минимум.

    Floor planning: Проектиране на floor plan.

    Оформление обща клетка: Стил на оформление в който компонентите могат да бъдат с произволна височина и и ширина и функционална слошност.

    Глобална маршрутизация: Когато областа на оформление се разлага на канали, проблемат при глобалната маршрутизация е коъ канал ще се исплзва за да се направи взаимното свързване за всяка мрежа.

    Разделяне на графиката: Даден е граф с тегла по върховете си и разходите по ръбовете му, проблема с разделянена точките в някакъв определен брой k на приблизително продукти с равни тегла такива, че разходите на краищата, които свързват точките в различни подгрупи е сведена до минимум.

    Оцветяване на графиката на интервали : Дадено е крайно множество от n интервали {[li,ri],1≤in} за цяло число li и ri, оцветяваме интервалите со минимален брой цветове, така че два интервала, които се присичат, са в същтия цвят. Представляването на графиката е пряко: всеки връх претставлява интервал, и има граница между два върха ако съответните интервали от времем се присичат. Тогава оцветяването графиката на интервали съответства на оцветяването на интервалите.

    Jog: В праволинейния маршрутен модел, вертикален сегмент в пътя, който обокновено работи хоризонтално, или обрарно.

    Работен слой: Даден е набор от дървета в равнината, всяако съединава терминалите на мрежата, прехврляне на на маршрутния слоъ за всякой сегмент от всяко дърво така че в резултата на оформление на кабели е правен при определяне на маршрутния модел.

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

    Мрежа: Набор от терминали които са свързани взаимно.

    Праволинейна: По отношение на оформлението, описва оформления за които има извършена двойка ортогонални оси определяни като „хоризонтална“ и „вертикална“; особеностите на оформленията, като страните на компонентите и сегментите от пътищата на кабелите, са хоризонтални и вертикаални сегментни линии.

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

    Shape function: Функция кояато ни ги дава възможните димензии на оформление на компонетн с гъвкаво разспеделение.За shape function s:[ɯmin,∞]→[hmin,∞], s(ɯ) е минималната височина на всеки правоъгалник или ширина ɯ която съдържа оформление на компонента.

    Slicing floor plan: Floor plan който може да бъде получен от рекурсивни два пъти разделяни на правоъгален план и са с вертикални и хоризонтални сегментни линии.

    Дървото на Щайнер: Даден е граф G=(V,E) дървото на Щтайнер за дадена подсъвкупност от върхове U от V в група от краища от G които формират едно дърво и съдържат сред своите крайни точки всички върхове от U. Дървото може да съдържа и други точки осве те от U. За дървото на Euclidean Steiner, U е мношество от точки в плана на Euclidean, и дървото съединаващо U може да съдържа произволни точки и отсечки в равнината.

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

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

    Топологично сортиране: Дава насочени, ациклена графика, едно топологично сортиране на върховете на графиката е пълно подредване на върховете, така че ако върха U преди върха V в подредаването, не съяествува директен път от V до U.

    Чрез минимизиране: Даден е сет от дървета на повърхноста, всяако съединаващо терминалите на мрежата, определяне слоя на заданието, коъто минимизира броя на точки при коъто възниква промяна на слоя.


    Каталог: saa
    saa -> Вероятностни алгоритми Цел: Упражняване в създаването и програмната реализация на вероятностни алгоритми Теоретична част
    saa -> Лекция №2 алгоритмично-програмни конструкции видове алгоритми
    saa -> Дървета Цел
    saa -> На снимката саксофонистът е Миньо Георгиев, акордеон Диньо Льолев, Пенка Манолова е но-ниската от двете певици. Снимката е от дъщерята на Стойчо Кузмов и е направена на Чирпанския панагир
    saa -> Евристически алгоритми
    saa -> Лекция №4 с о р т и р а н е и с м е с в а н е същност на сортирането
    saa -> Сортировка чрез вмъкване Същност на алгоритъма
    saa -> Конспект Синтез и анализ на алгоритми и програми


    Сподели с приятели:
  • 1   2   3




    ©obuch.info 2024
    отнасят до администрацията

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