Greedy algorithms for distance-2 graph coloring and bipartite graph partial coloring
İki mesafeli çizge boyama ve iki parçalı çizge boyama için açgözlü algoritmalar
- Tez No: 556783
- 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: 2019
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 92
Özet
oşut bir uygulamanın görev etkileşim çizgesi komşu görevlerin farklı renklerle boyandığında birbirleri ile aynı renkteki görevler aynı anda pahalı bir senkronizasyon veri yapısı kullanılmadan aynı anda çalıştırılabilmektedir. Bu tür bir çalıştırmada bir renkteki görevler bitirilmeden, başka bir renkteki görev koşut halde şlenemeyeceğinden boyama esnasında kullanılan renk sayısı koşut uygulamanın çalıştırılması esnasında karşılaşılacak senkronizasyon adım sayısını belirtmektedir. Literatürde çizge boyama problemi ''bir çizgeyi mümkün olan en az sayıda renk kullanarak komşu noktalara farklı renkler vermek'' olarak tanımlanmıştır ve bir optimizasyon problemi olarak görüldüğünde NP-Hard sınıfındadır. Çizge boyama probleminin farklı çeşitleri de paralel hesaplama, özellikle paralel bilimsel hesaplama alanında önemlidir. Problemin yukarıda bahsedilen basit halinde 1-uzaklık kullanılırken, k-uzaklık tanımı da özellikle k = 2 için pratikte kullanılmaktadır. Bu tezde de bu problem üzerine yoğunlaşılmıştır. Problemin genel hali ''bir çizgeyi mümkün olan en az sayıda renk kullanarak birbirinden k ve daha az uzaklıktaki nokta ikililerine farklı renkler vermek'' olarak tanımlanabilir. Literatürde bu problem için az renk kullanan buluşsal yöntemler önerilmiştir ve bu yöntemler k = 1 için oldukça hızlıdır. Fakat k = 2 için özellikle büyük çizgelerde bu buluşsal yöntemler dakikalar mertebesinde zaman alabilmektedirler. Çizge boyamanın bir uygulamanın çalışması için sadece bir ön işlem olduğu düşünüldüğünde bu işlemin getirdiği ekstra zamanın mümkün olduğu kadar az olması işlemin uygulanabilirliği için önemlidir. Bu tezde 2-uzaklık çizge boyama ve bu problemin farklı bir türü olan iki parçalı çizge boyama problemleri için iyimser ve açgözlü buluşsal yöntemler önerilmiştir. Bu yöntemler çok çekirdekli işlemcilerde ve Grafik İşleme Ünitelerinde koşut olarak gerçeklenmiş, ve ölçeklenebilirlikleri analiz edilmiştir. Yapılan deneylerde önerilen yöntemlerin ölçeklenebilir ve 16 çekirdek kullanıldığında literatürdeki yöntemlerden ortalama 25 kat hızlı oldukları görülmüş, özellikle sosyal ağ karakteri taşıyan çizgeler için büyük performans artışı sağladığı saptanmıştır. Yine bu tez çerçevesinde aynı renge sahip nokta kümelerinin eleman sayılarının birbirine yakın olması üzerine de çalışılmıştır. Bu tür dengeli dağılımlı bir boyama, uygulamanın çok çekirdekli işlemciler ve özellikle GİÜ'ler üzerinde çalışması esnasında her senkronizasyon adımında bütün çekirdekleri doyuracak kadar iş yükü olmasını sağlayacağından yüksek performans için önemli olabilmektedir. Bu tezde neredeyse hiç ekstra külfet getirmeden bunu sağlayabilecek iki yöntem önerilmiştir. Yapılan deneylerde bu yöntemlerin başarılı olduğu sonucuna varılmıştır.
Özet (Çeviri)
In parallel computing, a valid graph coloring yields a lock-free processing of the colored tasks, data points, etc., without expensive synchronization mechanisms. However, the coloring stage is not free and the overhead can be significant. In particular, for distance-2 graph coloring (D2GC) and bipartite graph partial coloring (BGPC) problems, which have various use-cases within the scientific computing and numerical optimization domains, the coloring overhead can be in the order of minutes with a single thread for many real-life graphs, having millions and billions of vertices and edges. In this thesis, we propose a novel greedy algorithm for the distance-2 graph coloring problem on shared-memory architectures. We then extend the algorithm to bipartite graph partial coloring problem, which is structurally very similar to D2GC. The proposed algorithms yield a better parallel coloring performance compared to the existing shared-memory parallel coloring algorithms, by employing greedier and more optimistic techniques. In particular, when compared to the state-of-the-art, the proposed algorithms obtain 25x speedup with 16 cores, without decreasing the coloring quality. Moreover, we extend the existing distance-2 graph coloring algorithm to manycore architectures. Due to architectural limitations, the multicore algorithm can not easily be extended to manycore. Thus several optimizations and modifications are proposed to overcome such obstacles. In addition to multi and manycore implementations, we also offer novel optimizations for both D2GC and BGPC on social network graphs. Exploiting the structural properties of social graphs, we propose faster heuristics to increase the performance without decreasing the coloring quality. Finally, we propose two costless balancing heuristics that can be applied to both BGPC and D2GC, which would yield a better color-based parallelization performance with a better load-balancing, especially on manycore architectures.
Benzer Tezler
- Labirentlerde yapay zeka tabanlı yön bulma algoritmaları kullanan bir gezgin robot geliştirilmesi
Development of mobile robot based on artificial intelligence for navigation algorithms in mazes
AYDIN GÜLLÜ
Doktora
Türkçe
2017
Makine MühendisliğiTrakya ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. HİLMİ KUŞÇU
- A K-means clustering-based shape retrieval technique for 3D mesh models
Üç boyutlu çözüm ağları için K-means kümeleme tabanlı şekil araması
MOHAMMADHASSAN REZAEI
Yüksek Lisans
İngilizce
2017
Makine Mühendisliğiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ERKAN GÜNPINAR
- Metasezgisel algoritmalarla araç rotalama probleminin modellenmesi
Modeling of vehicle routing problem with metaheuristic algorithms
KADİR YILDIZ
Yüksek Lisans
Türkçe
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolErciyes ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ BİLAL BABAYİĞİT
- Smart location-based mobile shopping Android application
Akıllı konum tabanlı mobil alışveriş Android uygulaması
GÜNAY GÜLTEKİN
Yüksek Lisans
İngilizce
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Kemerburgaz ÜniversitesiElektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. OĞUZ BAYAT
- P-hub center and routing network design problem and solution algorithms
P-ana dağıtım üssü merkez ve rotalama ağ tasarımı problemı ve çözüm algorıtmaları
ABDUL KADER KASSOUMEH
Yüksek Lisans
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEskişehir Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. AHMET ARSLAN
DR. ÖĞR. ÜYESİ ZÜHAL KARTAL