Geri Dön

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

  1. Tez No: 556783
  2. Yazar: MUSTAFA KEMAL TAŞ
  3. Danışmanlar: DR. ÖĞR. ÜYESİ KAMER KAYA
  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: Belirtilmemiş.
  7. Yıl: 2019
  8. Dil: İngilizce
  9. Üniversite: Sabancı Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

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

    Türkçe

    2017

    Makine MühendisliğiTrakya Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    DOÇ. DR. HİLMİ KUŞÇU

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

    İngilizce

    2017

    Makine Mühendisliğiİstanbul Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. ERKAN GÜNPINAR

  3. Metasezgisel algoritmalarla araç rotalama probleminin modellenmesi

    Modeling of vehicle routing problem with metaheuristic algorithms

    KADİR YILDIZ

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolErciyes Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ BİLAL BABAYİĞİT

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

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Kemerburgaz Üniversitesi

    Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. OĞUZ BAYAT

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

    İngilizce

    2021

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEskişehir Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. AHMET ARSLAN

    DR. ÖĞR. ÜYESİ ZÜHAL KARTAL