Geri Dön

İzlenceleme problemleri için alt sınır tahmin yöntemleri

Lower bound estimation methods for scheduling problems

  1. Tez No: 77420
  2. Yazar: RIZA DİNDİR
  3. Danışmanlar: DOÇ. DR. MEHMET EMİN DALKILIÇ
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: İzlenceleme, AST, VLSI Tasarımı, ÜDS, Op- timizasyon '4M, Scheduling, Lower Bound Estimation, VLSI De sign, High-Level Synthesis, Optimization
  7. Yıl: 1998
  8. Dil: Türkçe
  9. Üniversite: Ege Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Uluslararası Bilgisayar Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 129

Özet

Ö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.

Özet (Çeviri)

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.

Benzer Tezler

  1. Tez No

    186174

    Tommaso Campanella ve Thomas More'un ütopyalarının karşılaştırılması

    Comparing Thomas More and Tommaso Campanella's utopias

    MAHMUT AVCI

    Yüksek Lisans

    Türkçe

    Türkçe

    2006

    FelsefeAtatürk Üniversitesi

    Felsefe ve Din Bilimleri Ana Bilim Dalı

    YRD. DOÇ. DR. OSMAN ELMALI

  2. Tez No

    574026

    AUC maximization for binary classification using combinatorial benders cuts

    Başlık çevirisi yok

    İBRAHİM EDHEM SAKARYA

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

    Endüstri ve Endüstri MühendisliğiÖzyeğin Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ÖMER ERHUN KUNDAKCIOĞLU

  3. Tez No

    462023

    A decision support system for production planning and scheduling in a smart factory environment

    Akıllı fabrika ortamında üretim planlama ve zaman çizelgeleme için bir karar destek sistemi

    HAKTAN CİNKILIÇ

    Yüksek Lisans

    İngilizce

    İngilizce

    2017

    Endüstri ve Endüstri MühendisliğiBoğaziçi Üniversitesi

    Yönetim Bilişim Sistemleri Ana Bilim Dalı

    PROF. DR. ASLI SENCER

  4. Tez No

    335622

    Approximate dynamic programming approach for sequential change diagnosis problem

    Ardışık değişim ve tanı problemi için yaklaşık dinamik programlama yaklaşımı

    ELİF AKBULUT

    Yüksek Lisans

    İngilizce

    İngilizce

    2013

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Bölümü

    DOÇ. DR. SAVAŞ DAYANIK

  5. Tez No

    246597

    Stochastic lot sizing problems under monopoly

    Tekel altında rassal öbek boyutlandırma problemleri

    İHSAN YANIKOĞLU

    Yüksek Lisans

    İngilizce

    İngilizce

    2009

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Bölümü

    DOÇ. DR. HANDE YAMAN

Geri Dön