Հայաստանի ատենախոսությունների բաց մատչելիության պահոց = Open Access Repository of the Armenian Electronic Theses and Dissertations (Armenian ETD-OA) = Репозиторий диссертаций Армении открытого доступа

Հատումների գրաֆների կիրառությունը ուղեգծման խնդիրներում

Փիլիպոսյան, Էդուարդ Տիգրանի (2013) Հատումների գրաֆների կիրառությունը ուղեգծման խնդիրներում. PhD thesis, ՀՀ ԳԱԱ Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ .

[img]
Preview
PDF (Abstract)
Available under License Creative Commons Attribution.

Download (1146Kb) | Preview

    Abstract

    Интенсивное развитие вычислительной техники, многократное уменьшение размеров и усовершенствование важнейших характеристик современных электронных устройств достигаются в результате внедрения новых технологий проектирования и конструирования. В этих условиях первостепенное значение приобретает автоматизация процесса проектирования этих устройств и их основных составляющих, в частности, больших и сверхбольших интегральных схем – БИС и СБИС. Одним из важнейших и трудоемких этапов автоматизации проектирования БИС является этап трассировки соединений, главной задачей которого является проведение соединений, обеспечивающих эквипотенциальность контактов цепей схемы. Существует два уровня трассировки: глобальная трассировка и детальная трассировка. На первом уровне вся область трассировки разбивается на подобласти. Задача глобальной трассировки заключается в распределении соединений по подобластям. Детальная трассировка заключается в реализации соединений в каждой подобласти. Обычно детальная трассировка делится на канальную трассировку и трассировку коробки соединений (switchbox). Продолжающееся увеличение количества компонент и цепей электрических схем исключает применение «ручных» и переборных методов трассировки, делает практически неприемлемым использование волновых алгоритмов трассировки и предполагает разработку новых, эффективных алгоритмов решения возникающих задач. Степень автоматизации проектирования и технические характеристики проектируемых устройств во многом зависят как от удачного выбора математической модели их представления, так и от «качества» решения тех математических задач, к которым они сводятся в рамках выбранной модели. В частности, если в качестве математической модели представления схемы выбран гиперграф, то минимизация числа связных между собой пар блоков сводится к построению минимальной реализации гиперграфа. В случае графового представления схемы, задачи трассировки канала и коробки соединений сводятся к нахождению минимальной раскраски и максимального независимого множества вершин соответствующего графа пересечений. Однако оказывается, что даже в некоторых частных случаях эти задачи являются NP-трудными. Поэтому актуальны как выделение практически важных частных случаев этих задач, для решения которых существуют эффективные точные алгоритмы, так и получение достижимых оценок значений исследуемых параметров. Հաշվողական տեխնիկայի բուռն զարգացումը, ժամանակակից էլեկտրոնային սարքավորումների չափսերի բազմակի փոքրացումն ու կարևորագույն բնութագրիչների աննախադեպ բարելավումը հնարավոր են դառնում ի շնորհիվ այդ սարքավորումների նախագծման ու պատրաստման նոր տեխնոլոգիաների ներդրման: Այս առումով առաջնակարգ նշանակություն է ստանում ինտեգրալ սխեմաների նախագծման գործընթացի ավտոմատացումը, որի կարևորագույն փուլերից է միացումների ուղեգծումը, մասնավորաբար՝ կապուղիների և միացման արկղերի ուղեգծումը: Ինտեգրալ սխեմաներում բաղադրիչների ու շղթաների քանակի մեծ լինելն ու շարունակական աճը բացառում են հատարկման մեթոդների օգտագործումը, գործնականում անհնար են դարձնում ուղեգծման ալիքային ալգորիթմների կիրառումն ու ենթադրում են առաջացող խնդիրների լուծման նոր, արագագործ ալգորիթմների մշակում: Նախագծման ավտոմատացման աստիճանն ու նախագծվող սարքավորումների տեխնիկական բնութագրիչները մեծապես կախված են ինչպես դրանց ներկայացման հաջող մաթեմատիկական մոդելի ընտրությունից, այնպես էլ այն մաթեմատիկական խնդիրների լուծման որակից, որոնց բերվում են նախագծման խնդիրներն ընտրված մոդելի շրջանակներում: Մասնավորապես, սխեմայի ներկայացման գրաֆային մոդելի ընտրման դեպքում, կապուղիների և միացման արկղերի ուղեգծման հարցերը բերվում են հատուկ տիպի հատումների գրաֆների մինիմալ ներկման և մաքսիմալ անկախ բազմության կառուցման խնդիրներին: Սակայն պարզվում է, որ նույնիսկ որոշ մասնավոր դեպքերում այդ խնդիրներն NP-դժվար են: Այդ առումով արդիական են, ինչպես այդ խնդիրների գործնականում պիտանի մասնավոր դեպքերի առանձնացումը, որոնց լուծման համար գտնվում են ճշգրիտ ու արդյունավետ ալգորիթմներ, այնպես էլ հետազոտվող պարամետրերի հասանելի գնահատականների ստացումը: Այս հարցերի ուսումնասիրմանն է նվիրված ներկա ատենախոսությունը: Ատենախոսության նպատակը ինտեգրալ սխեմաների ներկայացման տարբեր մոդելների և այդ սխեմաների նախագծման կոնստրուկտորական փուլում առաջացող մաթեմատիկական խնդիրների ուսումնասիրումն է: Որպես մաթեմատիկական մոդելներ ուսումնասիրվել են. Շրջանագծին ներգծված բազմանկյունների հատումների գրաֆները, մասնավորապես դրանցում մաքսիմալ անկախ բազմություն կառուցելու խնդիրը: Թվային հաջորդականությունները, մասնավորապես դրանց տրոհումը մինիմալ թվով աճող ենթահաջորդականությունների: Հիպերգրաֆները, մասնավորապես հատուկ տիպի հիպերգաֆների մինիմալ իրացման խնդիրը Ուղղանկյունների հատումների գրաֆները, մասնավորապես մաքսիմալ կշռով անկախ բազմության կառուցման խնդիրը: The great boost in computing technology development, the drastic decrease in physical size of modern electronic devices and the unprecedented improvement of the most important characteristics are made possible due to the new technologies of design and integration of these devices. In this respect the problem of VLSI design process automation gains utmost importance. One of its main stages is routing of the connections, in particular channel and switchbox routings. The big number of components and nets exclude the usage of wave algorithms of routing and assume new and effective solutions for emerged problems. The purpose of the work is to study different VLSI design models and the mathematical problems emerging in them. The following mathematical models were studied. Intersection graphs of polygons inscribed in a circle, in particular, the problem of constructing the maximum independent set in them. Numeric sequences, in particular, the problem of partitioning the sequence into a minimal number of increasing subsequences. Hypergraphs, in particular, the problem of minimal realization for two types of hypergraphs. Intersection graphs of rectangles, in particular, the problem of constructing the maximum weighted independent set.

    Item Type: Thesis (PhD)
    Additional Information: Հատումների գրաֆների կիրառությունը ուղեգծման խնդիրներում: Application of intersection graphs in routing problems.
    Uncontrolled Keywords: Փիլիպոսյան Էդուարդ Տիգրանի, Piliposyan Eduard T.
    Subjects: Informatics and Computer Systems
    Divisions: UNSPECIFIED
    Depositing User: NLA Circ. Dpt.
    Date Deposited: 28 Sep 2016 14:58
    Last Modified: 28 Sep 2016 15:05
    URI: http://etd.asj-oa.am/id/eprint/3509

    Actions (login required)

    View Item