Hypergraph models for parallel sparse matrix-matrix multiplication

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.