Geri Dön

Parallel streaming graph partitioning utilizing multilevel framework

Çok düzeyli yapıyı kullanarak paralel akış çizelge bölümleme

  1. Tez No: 518294
  2. Yazar: NAZANIN JAFARI
  3. Danışmanlar: Prof. Dr. CEVDET AYKANAT
  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: 2018
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Ü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ı: 60

Özet

Çizelge bölümleme, çeşitli uygulamaların verimli bir şekilde paralelleştirilmesi için yaygın olarak kullanılmaktadır. Akış grafiği bölümleme, çevrimdışı çizelge bölümleyicilerin yüksek hesaplama maliyetlerini aşmak için sağlanan bir geçiş bölümleme çözümüdür. Bu aktarım algoritmaları, bölümleme özelliklerinde daha fazla geliştirmeyi amaçlayan ardışık olarak yeniden bölümlendirme için kullanılabilir olsa da, kalite iyileştirmeleri, birkaç geçişle sınırlıdır. Çevrimdışı çizelge bölümleme araçlarını, oluşturulan yüksek kaliteli bölümler nedeniyle çizelge bölümleme için hala istenen bir çözüm halindedir. Çizelge bölümleme probleminde kalite ve performans arasındaki dengeyi azaltabilen akış algoritmalarını kullanarak çok düzeyli bir yaklaşım öneriyoruz. Ayrıca Openmp tabanlı çok parçalı uygulamalarımız, son teknoloji ürünü çevrimdışı yüksek kaliteli çizelge bölümleme aracı olan METIS için çok iş parçacıklı bir çözüm olan \ emph {mt-metis} ile kıyaslandığında hızlı ve yüksek ölçeklenebilir çözümler üretebilir. Sonuçlarımız, yöntemimizin büyük çizelge veri setlerinde on beş kat daha hızlı ve daha ölçeklenebilir sonuçlar üretebildiğini göstermektedir. Ayrıca, yöntemin, birkaç kez yeniden bölümlendirildikten sonra en gelişmiş akış grafiği bölümleme algoritması LDG'ye kıyasla önemli ölçüde bölümlerin kalitesini artırabildiğini gösteriyoruz. Ortalama olarak LDG algoritmasından 29 % daha iyi niteliklere sahip bölümler üretiyoruz.

Özet (Çeviri)

Graph partitioning is widely used for efficient parallelization of a variety of applications. Streaming graph partitioning is a one pass partitioning solution provided to overcome high computation costs of offline graph partitioners. Even though these streaming algorithms can be used for successively repartitioning, aiming at further improvements in partitioning qualities, quality improvements is limited to few passes that make offline graph partitioning tools still a desirable solution for graph partitioning due to the generated high-quality partitions. We propose a multilevel approach using streaming algorithms that can alleviate the tradeoff between quality and performance in graph partitioning problem. Moreover, our OpenMP based multi-threaded implementation can generate fast and highly scalable solutions compared to mt-metis, a multi-threaded solution for METIS, and the state-of-the-art offline high-quality graph partitioning tool. Our results show that our method can produce up to fifteen times faster and more scalable results in large graph datasets. We also show that our method can improve the quality of partitions significantly compared to state-of-the-art streaming graph partitioning algorithm LDG after repartitioning several times. On average we produce partitions with 29% better qualities than the LDG algorithm.

Benzer Tezler

  1. S3-TM: Scalable streaming short text matching

    Ölçeklenebilir akan kısa metin eşleme

    FUAT BASIK

    Yüksek Lisans

    İngilizce

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. HAKAN FERHATOSMANOĞLU

    YRD. DOÇ. DR. BUĞRA GEDİK

  2. Distributed stream-processing framework for graph-based sequence alignment

    Çizge tabanlı okuma hizalandırması için dağıtık akıntı işleme sistemi

    ALİM ŞÜKRÜCAN GÖKKAYA

    Yüksek Lisans

    İngilizce

    İngilizce

    2020

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Mühendislik Bilimleri Ana Bilim Dalı

    YRD. DOÇ. CAN ALKAN

  3. Traffic and mobility aware delay modeling for software-defined networks (SDN)

    Yazılım tanımlı ağlar için trafik ve hareket duyarlı gecikme modeli

    MÜGE ÖZÇEVİK

    Doktora

    İngilizce

    İngilizce

    2019

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. BERK CANBERK

  4. MAG kaynak yönteminde dış manyetik alanların kaynak dikiş formuna ve ITAB'a etkisi

    The Effect of external magnetic fields an weld bead form and heat affected zone in MAG welding process

    İZZET TÜRKOCAĞI

    Doktora

    Türkçe

    Türkçe

    1991

    Makine Mühendisliğiİstanbul Teknik Üniversitesi

    PROF. SALAHADDİN ANIK

  5. Banka şube mimarisinin yeni teknolojilere adapte olabilme potansiyelinin ölçülmesine yönelik bir yaklaşım önerisi

    Measuring adaptability of the banking branchs to the new technologies: A new approach

    SEÇİL ÖZER

    Yüksek Lisans

    Türkçe

    Türkçe

    2018

    Mimarlıkİstanbul Teknik Üniversitesi

    Bilişim Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ ASLI KANAN