Optimal Hypergraph Partitioning
Optimal Hiperçizge Parçalama
- Tez No: 507362
- Danışmanlar: DR. ÖĞR. ÜYESİ KAMER KAYA
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2018
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 85
Özet
Hiperçizge parçalama literatürde oldukça popüler bir problemdir. Dağıtık algoritmalar ve VLSI devre tasarımı gibi uygulamaların performasi bu yöntemle büyük ölçüde arttırılabilir. Son 20 yılda, hiperçizgeyi hızlı bir şekilde parçalayabilen araçlar geliştirilmiştir. Ancak bu problem NP-Zor olduğu için, bu araçlar sezgisel yöntemlere dayanmaktadır. Bu yüzden genelde optimal olmayan sonuçları bulmaktadırlar. Optimal hiperçizge problemi üzerine sezgisel yöntemlere dayalı çalışmalara nazaran çok daha az sayıda araştırma bulunmaktadır. Bu tezde, literatürdeki bir çok metriğe göre optimal parçalamayi bulan, PHaraoh isimli koşut hiperçizge parçalama aracı sunulmaktadır. Optimal sonuçların bulunması sayesinde, böyle bir araç, daha önceden geliştirilen hiperçizge parçalama araçlarının gerçek performansını, olası en iyi sonuçile karşılaştırarak ölçmemizi sağlar. PHaraoh herhangi bir parçalama ile başlatılabilir ve bu sonucu sürekli olarak geliştirmeye çalışır. Bu sayede, istenen optimal hiperçizge parçalama islemini verilen sürede tamamlayamasa bile, baslangıçta verilen parçalamanın kalitesini iyileştirebilir. Gerçek hayattaki uygulamalarda karşılaşılan hiperçizge modelleri üzerinde yaptığımız deneylere göre, PHaraoh pratikte en çok kullanılan araçların ürettiği parçalamaların kalitesini dal ve sınır arama yöntemini kullanarak büyük ölçüde iyileştirmektedir. Arama uzayında bulunan optimal parçalamanın bulunma süresini kısaltmak icin,“usta yamak”ve“iş çalma”yöntemlerine dayalı koşut algoritmalardan faydalandik. Daha önceki çalışmalarımızda ve bu tezde yaptığımız deneylere göre hiperçizge parçalama problemi icin dal ve sınır ağacındaki öğelerin sırası PHaraoh'ın performansını önemli oranda etkilemektedir. Bu tezde, değişik sıralama yöntemleri önerip, bunların PHaraoh'ın çalışma süresini nasıl değiştirdiğini ve bu değişikliğin nedenlerini hiperçizgelerin özelliklerine bağlayarak açıkladık.
Özet (Çeviri)
Hypergraph partitioning into K parts has many applications in practice such as distributed algorithms and very large scale integrated circuit (VLSI) design. There are various tools proposed in the literature which can partition a given hypergraph very fast. However, since the problem is NP-Hard and the traditional approaches heavily use heuristics, these tools do not provide an optimal partition. There is limited research on partitioning hypergraphs optimally. In this thesis, we proposePHaraoh, a parallel hypergraph partitioner that can provide optimal partitions for many metrics used in the literature. Such a partitioner is important in practice since it enables us to evaluate the true performance of the existing tools. Furthermore, PHaraoh can be started with an initial partition. Thanks to that, even an optimal solution is not found within the given time limit, PHaraoh improves the cost of the provided initial partition. Experimental results on hypergraphs obtained from real life matrices show that the quality of the partitions of existing tools can be improved significantly for most of the hypergraphs. In order to increase the speed up the search-space exploration, we experimented with both master-slave and work-stealing parallelization. It also has been shown that the runtime of the algorithm highly depends on the order of the items in the branch and bound tree. In this study, we propose different ordering strategies which can offer great speed ups depending on the characteristics of the hypergraph.
Benzer Tezler
- Polyhedral approaches to hypergraph partitioning and cell formation
Hiperçizge parçalama problemine polyhedral yaklaşımlar ve hücre belirlenmesi
LEVENT KANDİLLER
Doktora
İngilizce
1994
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiDOÇ.DR. MUSTAFA AKGÜL
- Balance preserving min-cut replication set for a K-way hypergraph partitioning
K parçalı bir hiperçizge bölümlemesi için denge korumalı min-kesit çoklama kümesi
VOLKAN YAZICI
Yüksek Lisans
İngilizce
2010
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Independent task assignment for heterogeneous systems
Heterojen sistemler için bağımsız iş atama
ERTUĞRUL KARTAL TABAK
Doktora
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Bölümü
PROF. DR. CEVDET AYKANAT
- Scheduling wireless ad hoc networks in polynomial time using claw-free conflict graphs
Başlık çevirisi yok
ALPER KÖSE
Yüksek Lisans
İngilizce
2017
Bilgi ve Belge YönetimiUniversité libre de Bruxelles (École polytechnique de Bruxelles)DR. MURİEL MEDARD
- Optimal trajectory tracking guidance of an aircraft with final velocity constraint
Bir hava aracının son hız vektörü koşullu optimal-yörünge takibi güdümü
DENİZ ERDOĞMUŞ
Yüksek Lisans
İngilizce
1999
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. MEHMET KEMAL LEBLEBİCİOĞLU