İzlenceleme problemleri için alt sınır tahmin yöntemleri
| dc.contributor.advisor | Dalkılıç, Mehmet Emin | |
| dc.contributor.author | Dindir, Rıza | |
| dc.date.accessioned | 2024-08-19T19:44:04Z | |
| dc.date.available | 2024-08-19T19:44:04Z | |
| dc.date.issued | 1998 | |
| dc.department | Ege Üniversitesi, Fen Bilimleri Enstitüsü, Uluslararası Bilgisayar Ana Bilim Dalı | en_US |
| dc.description | Bu tezin, veri tabanı üzerinden yayınlanma izni bulunmamaktadır. Yayınlanma izni olmayan tezlerin basılı kopyalarına Üniversite kütüphaneniz aracılığıyla (TÜBESS üzerinden) erişebilirsiniz. | en_US |
| dc.description.abstract | Özet İzlenceleme Problemleri için Alt Sınır Tahinin Yöntemleri DİNDİR, Rıza Yüksek Lisans Tezi, Bilgisayar Bilimleri Tez Yöneticisi: Doç. Dr. Mehmet E. Dalkılıç Ağustos 1998, 137 sayfa Sayısal sistem tasarımında. kullanılan en önemli araçlardan birisi üst düzey sentezdir. Üst düzey sentez (USD), tasarımcıya bir devreyi tasarlaması için üst düzey bir modelleme aracı sunar. Üst düzey sentezin önemli alt problemlerinden bir tanesi izlencelemedir (Scheduling). İzlenceleme verilen bir kontrol/veri akış (CDF) çizge- sindeki işlemlerin çalışma sırasını belirler. İzlenceleme NP-Hard bir optimizasyon problemidir ve verilen bir problemin çözüm uzayını, bir çözüm ve genel olarak optimum bir çözüm için tarar. İzlencelemeyi daha verimli hale getirmek için verilen bir problemin çözüm uzayı sınırlandırılmalıdır. Alt sınır tahmin (AST) yön temleri, çözüm uzaylarını sınırlamak ve bir çözüm uzayını tarama işlemini yönlendirmek için kullanılırlar. Bu tezde izlenceleme ve izlencelemede kullanılan alt sınır tahmin yöntemleri incelenmiştir. Zaman kısıtlı ve kaynak kısıtlı alt sınır tahmin yöntemleri için örnek alt sınır tahmin algoritmaları (Greedy, Recursive, Etkin Alanlar, Frame Analizi) uygulanıp, bu algoritmalar ürettikleri sonuçlar açısından aralarında karşılaştırılmıştır. İncelenen algoritmalar içinde Greedy ve Aralık Analizi algoritmaları belirgin bir hız avantajına sahip tir. Bu ikiliden ortalama on kat yavaş olan Recursive algoritması pratikte uygulanabilecek kadar hızlı iken, ortalama çalışma zamanı yüzlerce kez daha yavaş olan Etkin Alanlar algoritması izlenceleme esnekliğinin fazla olduğu durumlarda pratik değildir. Çoğu zaman bir problemde birden fazla izlence aynı çözümü üretir. Aynı çözümü üreten bu izlencelerden bir tanesinin incelenmesi ile, diğer izlencelerin üreteceği çözümler incelenmiş olur. Verilen bir problemin çözüm uzayında, simetrik izlenceleri bulan bir simetri analizi algoritması geliştirilmiştir. Geliştirilen simetri analizi algorit-VI ması bir Branch- and- Bound izlenceleme algoritmasına (referans algoritma) eklenmiştir. Simetri analizli algoritma ile referans algoritma çalışma zamanı açısından karşılaştırılmıştır. Alınan sonuçlara göre simetri analizli algoritma birçok problem için yüksek oranda (%50) simetrik izlence bulmuştur. Buna rağmen bu algoritma, referans algoritmaya göre çoğu örnek problem için %30 daha fazla çalışma zamanına ihtiyaç duymaktadır; az sayıdaki örnek problem için ise çalışma zamanında bir iyileşme (%15) sağlamaktadır. Simetri analizli izlenceleme algoritmasının çalışma zamanı simetri analizi modelinin geliştirilmesi ile iyileştirilebilir. Anahtar Sözcükler: İzlenceleme, AST, VLSI Tasarımı, ÜDS, Op- timizasyon '4M; | en_US |
| dc.description.abstract | vıı Abstract Lower Bound Estimation Methods for Scheduling Problems DİNDİR, Rıza MSc. Thesis in Computer Science Supervisor: Assoc. Prof. Dr. Mehmet E. Dalkılıç August 1998, 137 pages High- Level synthesis (HLS) is one of the most important tools used in digital system design. HLS provides the designer with ab stract, high level modelling tools. These tools can be used to specify systems that are to be designed. One of the important sub-problems of HLS is scheduling. Scheduling can be seen as a design space ex ploration task, which explores the design space of a given problem to find a solution, and possibly an optimal solution. To make scheduling more time efficient, the design space of a given problem must be bounded. Lower-Bound estimation algo- ritms are used to bound the design space and guide the design space exploration task. In this thesis, scheduling and lower-bound esti mation algorithms have been studied. For Time- Constrained and Resource-Constrained lower-bound estimation methods, a number of lower-bound estimation algorithms have been implemented. These algorithms are compared on a common platform and the quality of the results produced by them are quantified. Traditional scheduling algorithms use lower-bound methods to bound the design space of a given problem. Design spaces contain many partial schedules that generate the same solution. Such sched ules can be named as symmetric schedules. By examining one of these symmetrical schedules, all the other schedules, that are sym metric with the examined schedule, can be removed safely. A foundation for a symmetry analysis method has been devel oped and a symmetry analysis algorithm has been implemented. The implemented symmetry analysis algorithm has been embedded to a Branch-and-Bound scheduling algorithm. The results show that thevia CDFGs (Control/Data Flow Graph) used in digital design are fairly symmetric. Altough the symmetry analysis method found a high ratio (approximately %50) of symmetrical schedules, a speed-up (of up to 15%) has been obtained only on few cases over the scheduling method without symmetry analysis. On most cases the scheduling algorithm with symmetry analysis took up to 30% more time com pared to the scheduling algoritm without the symmetry analysis. To make the symmetry analysis method more time efficient, more research has to be made in this direction and the given symmetry analysis model must be elaborated. Keywords: Scheduling, Lower Bound Estimation, VLSI De sign, High-Level Synthesis, Optimization | en_US |
| dc.identifier.endpage | 129 | en_US |
| dc.identifier.startpage | 1 | en_US |
| dc.identifier.uri | https://hdl.handle.net/11454/86169 | |
| dc.identifier.yoktezid | 77420 | en_US |
| dc.language.iso | tr | en_US |
| dc.publisher | Ege Üniversitesi | en_US |
| dc.relation.publicationcategory | Tez | en_US |
| dc.rights | info:eu-repo/semantics/closedAccess | en_US |
| dc.subject | Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol | en_US |
| dc.subject | Computer Engineering and Computer Science and Control | en_US |
| dc.subject | Programlama sistemi | en_US |
| dc.subject | Programming systems | en_US |
| dc.title | İzlenceleme problemleri için alt sınır tahmin yöntemleri | en_US |
| dc.title.alternative | Lower bound estimation methods for scheduling problems | en_US |
| dc.type | Master Thesis | en_US |
