Tez No	İndirme	Tez Künye	Durumu
577194		Partitioning models for scaling distributed graph computations / Dağıtık çizge hesaplamalarının ölçeklendirilmesi için bölümleme yöntemleri Yazar:GÜNDÜZ VEHBİ DEMİRCİ Danışman: PROF. DR. CEVDET AYKANAT Yer Bilgisi: İhsan Doğramacı Bilkent Üniversitesi / Mühendislik ve Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:Dağıtık veri tabanı sistemleri = Distributed database systems ; Grafik bölümleme = Graph partitioning ; Seyrek matrisler = Sparse matrixes	Onaylandı Doktora İngilizce 2019 151 s.
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.
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.