Partitioning models for scaling distributed graph computations
Dağıtık çizge hesaplamalarının ölçeklendirilmesi için bölümleme yöntemleri
- Tez No: 577194
- Danışmanlar: PROF. DR. CEVDET AYKANAT
- Tez Türü: Doktora
- 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: İhsan Doğramacı Bilkent Ü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ı: 151
Özet
Bu tezin odak noktası, dağıtık bellekli sistemlerde paralel çizge hesaplamalarının performansını ölçeklendirmek için akıllı bölümleme modelleri ve yöntemleridir. Bu kapsamda dağıtık veritabanları, sunucular arasında veri-yerelliği ve iş-yükü dengesi sağlamak için grafik bölümlemeden yararlanır. Veritabanında gerçekleştirilen bazı sorgular, birbirlerini tetikleyen sorgular nedeniyle ardışıklık gösterebilir. Mevcut bölümleme yöntemleri, grafik yapısını ve sorgu-iş yükünün kayıtlarını dikkate almaktadır. Bu çalışmada ardışıklık gösteren işlemler sırasında sunucular arasındaki toplam iletişim maliyetini en aza indirgemek amacıyla ardışıklığa duyarlı grafik bölümleme problemi ortaya konmaktadır. Bu haliyle tarafımızdan büyük ölçekli bölümleme için girdi olarak kullanmak üzere grafik yapısını ve ardışık işlemleri birlikte değerlendiren rastsal bir algoritma önerilmektedir. Gerçek sosyal ağları temsil eden çizgeler üzerinde yapılan deneyler, önerilen çözümün bölümlendirme hedefleri açısından etkinliğini göstermektedir. Seyrek-genelleştirilmiş-matris çarpımı~(SyGEMM), bilimsel hesaplamalarda ve yüksek performanslı çizge hesaplarında kullanılan anahtar bir hesaplama çekirdeğidir. Yineleyici çerçevesi sayesinde yüksek performanslı dağıtık hesaplama yapabilen Accumulo veritabanı için tarafımızdan bir SyGEMM algoritması önerilmektedir. Önerilen algoritma, Accumulo'nun toplu tarama özelliğini ve sunucu düzeyinde paralellik yapılarını kullanarak yazma-yerelliği sağlar ve matrislerini birden fazla kez taranmasına neden olmaz. Ayrıca bu çalışmada sunucular arasında toplam iletişim hacmini azaltan ve iş yükü dengesi sağlayan bir matris bölümleme şeması önerilmektedir. Konuya dönük olarak gerçek problemlerde ortaya çıkan ve sentetik olarak üretilen seyrek matrisler üzerinde yapılan kapsamlı deneyler, önerilen algoritmanın ve matris bölümleme şemasının önemli performans iyileştirmeleri sağladığını göstermektedir. Paralel SyGEMM algoritmalarının ölçeklendirilebilirliği yoğun bir şekilde iletişim işlemlerine bağlıdır. SyGEMM'in iş yükünün çok boyutlu bölümlenmesi daha yüksek ölçeklenebilirlik elde etmek için şarttır. Bu itibarla işlemcilerin dizilimini dikkate alarak ve aynı zamanda SyGEMM'in iş yükü üzerinde çok boyutlu bölümleme elde eden hiperçizge modelleri tarafımızdan önerilmektedir. Yapılan kapsamlı deneyler, önerilen bölümleme modellerinin etkinliğini göstermektedir.
Özet (Çeviri)
The focus of this thesis is intelligent partitioning models and methods for scaling the performance of parallel graph computations on distributed-memory systems. Distributed databases utilize graph partitioning to provide servers with data-locality and workload-balance. Some queries performed on a database may form cascades due to the queries triggering each other. The current partitioning methods consider the graph structure and logs of query workload. We introduce the cascade-aware graph partitioning problem with the objective of minimizing the overall cost of communication operations between servers during cascade processes. We propose a randomized algorithm that integrates the graph structure and cascade processes to use as input for large-scale partitioning. Experiments on graphs representing real social networks demonstrate the effectiveness of the proposed solution in terms of the partitioning objectives. Sparse-general-matrix-multiplication~(SpGEMM) is a key computational kernel used in scientific computing and high-performance graph computations. We propose an SpGEMM algorithm for Accumulo database which enables high performance distributed parallelism through its iterator framework. The proposed algorithm provides write-locality and avoids scanning input matrices multiple times by utilizing Accumulo's batch scanning capability and node-level parallelism structures. We also propose a matrix partitioning scheme that reduces the total communication volume and provides a workload-balance among servers. Extensive experiments performed on both real-world and synthetic sparse matrices show that the proposed algorithm and matrix partitioning scheme provide significant performance improvements. Scalability of parallel SpGEMM algorithms are heavily communication bound. Multidimensional partitioning of SpGEMM's workload is essential to achieve higher scalability. We propose hypergraph models that utilize the arrangement of processors and also attain a multidimensional partitioning on SpGEMM's workload. Thorough experimentation performed on both realistic as well as synthetically generated SpGEMM instances demonstrates the effectiveness of the proposed partitioning models.
Benzer Tezler
- Improving the performance of 1D vertex parallel GNN training on distributed memory systems
Dağıtık bellek sistemlerinde 1D düğüm paralel GNN eğitiminin performansının iyileştirilmesi
KUTAY TAŞCI
Yüksek Lisans
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Training memory-constrained deep learning models using automatic dataflow-graph partitioning
Başlık çevirisi yok
FAREED MOHAMMAD FAREED QARARYAH
Yüksek Lisans
İngilizce
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKoç ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. DİDEM UNAT
- Latency-centric models and methods for scaling sparse operations
Seyrek işlemlerin ölçeklenebilmesi için gecikim-merkezli model ve yöntemler
REHA OĞUZ SELVİTOPİ
Doktora
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Dağıtılmış nesneye dayalı sistemler için dağıtılmış bileşik nesne modeli
Distributed composite object model for distributed object based system
GÜRAY YILMAZ
Doktora
Türkçe
2002
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. TAKUHİ NADİA ERDOĞAN
- Incremental forming of light weight sheet materials at elevated temperature: An investigation of formability, failure, and output quality of the process
Başlık çevirisi yok
HOSEIN KHALATBARI
Doktora
İngilizce
2021
Makine MühendisliğiKoç ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. İSMAİL LAZOĞLU