Tez No	İndirme	Tez Künye	Durumu
398811		Hypergraph models for parallel sparse matrix-matrix multiplication / Paralel seyrek matris-matris çarpımı için hiperçizge modelleri Yazar:KADİR AKBUDAK 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:Hiperçizgeler = Hypergraphs	Onaylandı Doktora İngilizce 2015 123 s.
C = AB şeklindeki genel seyrek matris-matris çarpımı (SyGEMM), moleküler dinamik benzetimi, cizge işlemleri, doğrusal programlama gibi pek çok uygulamada çekirdek işlem olarak kullanılmaktadır. SyGEMM işlemi için farklı paralelleştirme yöntemleri bulunmaktadır. Bu yöntemler için paralel SyGEMM algoritmaları önermekteyiz. Önerilen algoritmalar iki evreden oluşmaktadır. Evrelerden birisi yerel çarpma işlemleri içermekte olup, çarpma evresi olarak isimlendirilmektedir. Diğer evre ise, çarpma evresi için gerekli matris elemanlarının taşınması veya çarpma evresinde üretilen kısmi sonuçların aktarılarak toplanmasından oluşmakta olup, iletişim evresi olarak isimlendirilmektedir. Bu paralel algoritmalar için, girdi ve çıktı matrislerini aynı anda veri yinelemesiz olarak bölümleyebilen üç tane hiperçizge modeli önermekteyiz. Bu üç model, girdi A ve B matrislerini tek boyutlu (1D) olarak bölümlemekle beraber, ilk model çıktı C matrisini sıfır-dışı tabanlı olarak iki boyutlu (2D) ve geri kalan modeller ise çıktı C matrisini 1D olarak bölümlemektedir. Bu modellerde, köşe ağırlıkları üzerinde tanımlı olan bölümleme kısıtı, işlemcilerin işlemsel yüklerini dengelemeye karşılık gelmektedir. Keside kalan hiperkenarlar üzerinde tanımlanan kesi boyutunun azaltılması olan bölümleme amacı ise, iletişim evresinde yapılan toplam iletişim hacmini azaltmaya karşılık gelmektedir. Ayrıca, toplam mesaj sayısını azaltmakla beraber her bir işlemcinin yönettigi iletişimin hacmini dengelemeyi hedefleyen hiperçizge modelleri de önermekteyiz. Önerilen hiperçizge modellerinin geçerliliğini deneysel olarak da doğrulamak amacıyla, MPI (Message Passing Interface) tabanlı SyGEMM paket programı geliştirilmiştir. Çok çeşitli seyrek matrisler üzerinde bu program kullanılarak JUQUEEN isimli bir IBM Blue-Gene/Q sisteminde büyük ölçekli deneyler gerçekleştirilmiştir. Yapılan deneylerin sonucunda, önerilen hiperçizge modellerinin hesaplamarı önemli miktarda hızlandırdığı gözlemlenmiştir.
Multiplication of two sparse matrices (i.e., sparse matrix-matrix multiplication, which is abbreviated as SpGEMM) is a widely used kernel in many applications such as molecular dynamics simulations, graph operations, and linear programming. We identify parallel formulations of SpGEMM operation in the form of C = AB for distributed-memory architectures. Using these formulations, we propose parallel SpGEMM algorithms that have the multiplication and communication phases: The multiplication phase consists of local SpGEMM computations without any communication and the communication phase consists of transferring required input/output matrices. For these algorithms, three hypergraph models are proposed. These models are used to partition input and output matrices simultaneously. The input matrices A and B are partitioned in one dimension in all of these hypergraph models. The output matrix C is partitioned in two dimensions, which is nonzero-based in the first hypergraph model, and it is partitioned in one dimension in the second and third models. In partitioning of these hypergraph models, the constraint on vertex weights corresponds to computational load balancing among processors for the multiplication phase of the proposed SpGEMM algorithms, and the objective, which is minimizing cutsize defined in terms of costs of the cut hyperedges, corresponds to minimizing the communication volume due to transferring required matrix entries in the communication phase of the SpGEMM algorithms. We also propose models for reducing the total number of messages while maintaining balance on communication volumes handled by processors during the communication phase of the SpGEMM algorithms. An SpGEMM library for distributed memory architectures is developed in order to verify the empirical validity of our models. The library uses MPI (Message Passing Interface) for performing communication in the parallel setting. The developed SpGEMM library is run on SpGEMM instances from various realistic applications and the experiments are carried out on a large parallel IBM BlueGene/Q system, named JUQUEEN. In the experimentation of the proposed hypergraph models, high speedup values are observed.