Tez No	İndirme	Tez Künye	Durumu
641212		Reducing communication overhead in sparse matrix and tensor computations / Seyrek matris ve tensör hesaplamalarında iletişim yükünün azaltılması Yazar:MUSTAFA OZAN KARSAVURAN 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:Bilgisayar iletişimi = Computer communication ; Hiperçizgeler = Hypergraphs ; Veri iletişimi = Data communication	Onaylandı Doktora İngilizce 2020 125 s.
Seyrek ve düzensiz uygulamalar paralelleştirilirken iletişim yükünün azaltılması için birden fazla iletişim maliyeti ölçütünün (hacim ve gecikim) kapsanması önemlidir. İletişim hiperçizge modeli birden fazla iletişim maliyeti ölçütünü kapsayacak şekilde iki fazlı bir yöntem olarak önerilmiştir. Toplama-iletişim-hiperçizge modeli işlemciler arasındaki gönderim-hacmi dengesini doğru bir şekilde modelleyememektedir. Önerdiğimiz yeni köşe ağırlığı şeması ile bölüm ağırlıklarının doğru gönderim-hacmine karşılık gelmesi sayesinde işlemciler arasındaki gönderim hacmini dengelemekteyiz. Ayrıca bu hiperçizge modeli bölümleme sırasında toplam iletişim hacminde artışa neden olmaktadır. Bu artışı azaltma amacı ile özyinelemeli ikiye-bölümleme (ÖB) yaklaşımı kullanan ve her ikiye bölümleme sırasında köşeleri karşılıklı yer değiştiren bir yöntem önermekteyiz. Performans değerlendirmesi için toplama-görevi ataması ortaya çıkartan bilinen en yaygın uygulamalardan olan sütun-paralel SyMV işlemini kullanmaktayız. 313 matris üzerinde yapılan kapsamlı deneylerle gösterildiği üzere önerdiğimiz yöntemler, var olan modele göre tüm iletişim maliyeti ölçütlerinde kayda değer iyileşme elde etmiştir. Bu iyileşmeler, yüksek düzensizlikteki 70 SyMV örneği için 512 işlemcide ortalama %30 daha az paralel koşma elde edilmesini sağlamıştır. İletişim hiperçizge modelini daha da geliştirerek bir işlemci tarafından gönderilen en fazla mesaj sayısını da kapsamasını sağlamaktayız. Bu amaç için hiperçizgenin bölümlenmesinde kullanılmak üzere, ÖB yaklaşımı ile gerçeklediğimiz yeni bir toplam paha ölçütü önermekteyiz. Ayrıca toplam iletişim hacmindeki artışı azaltmak için, bu artışı doğrudan bölümleme hedefi ile modelleyen yeni bir tür hiperkenar önermekteyiz. 300 matris üzerinde 1024 işlemci için gerçekleştirdiğimiz deneylerde önerdiğimiz yöntemler iletişim maliyeti ölçütlerinde kayda değer iyileşme elde etmiş ve bu iyileşmeler daha iyi sütun-paralel SyMM koşma zamanı sağlamıştır. Seyrek tensör bölümlemesi amacıyla bölümleme üzerine herhangi bir topolojik kısıt gerektirmeyen, genel orta-taneli hiperçizge modeli önermekteyiz. Önerdiğimiz model verilen tensörün sıfırdışı-ayrık bileşen tensörlerine ayrılması tabanlıdır. Sonrasında her bir bileşen tensörü için boyut-bağımlı iri-taneli hiperçizge oluşturmaktayız. Önerdiğimiz hiperkenar bütünleştirme yöntemi ile bu boyut-bağımlı iri-taneli hiperçizgelerden bileşik orta-taneli hiperçizge oluşturmaktayız. Önerdiğimiz bileşik orta-taneli hiperçizge modeli toplam iletişim hacminin en aza indirilmesini doğru bir şekilde kapsamaktadır. Önerdiğimiz ayırma sezgiseli ile tensörün yoğun dilimlerindeki sıfırdışı elemanları ayırarak bileşen tensörlerinde seyrek dilimler elde etmekteyiz. Ayrıca ÖB yaklaşımı kullanarak ayırma sezgiselinin daha kaliteli sonuçlar elde etmesini sağlamaktayız. Önerdiğimiz orta-taneli üç-kümeli çizge modeli ile toplam iletişim hacmini arttırma pahasına daha hızlı bölümleme zamanı elde etmekteyiz. Gerçek problemlerden elde edilmiş 10 tensör üzerinde 1024 işlemciye kadar gerçekleştirdiğimiz paralel deneyler önerdiğimiz yöntemlerin geçerliliğini doğrulamaktadır.
Encapsulating multiple communication cost metrics, i.e., bandwidth and latency, is proven to be important in reducing communication overhead in the parallelization of sparse and irregular applications. Communication hypergraph model was proposed in a two-phase setting for encapsulating multiple communication cost metrics. The reduce-communication hypergraph model suffers from failing to correctly encapsulate send-volume balancing. We propose a novel vertex weighting scheme that enables part weights to correctly encode send-volume loads of processors for send-volume balancing. The model also suffers from increasing the total communication volume during partitioning. To decrease this increase, we propose a method that utilizes the recursive bipartitioning (RB) paradigm and refines each bipartition by vertex swaps. For performance evaluation, we consider column-parallel SpMV, which is one of the most widely known applications in which the reduce-task assignment problem arises. Extensive experiments on 313 matrices show that, compared to the existing model, the proposed models achieve considerable improvements in all communication cost metrics. These improvements lead to an average decrease of 30% in parallel SpMV time on 512 processors for 70 matrices with high irregularity. We further enhance the reduce-communication hypergraph model so that it also encapsulates the minimization of the maximum number of messages sent by a processor. For this purpose, we propose a novel cutsize metric which we realize using RB paradigm while partitioning the reduce-communication hypergraph. We also introduce a new type of net for the communication hypergraph which models decreasing the increase in the total communication volume directly with the partitioning objective. Experiments on 300 matrices show that the proposed models achieve considerable improvements in communication cost metrics which lead to better column-parallel SpMM time on 1024 processors. We propose a hypergraph model for general medium-grain sparse tensor partitioning which does not enforce any topological constraint on the partitioning. The proposed model is based on splitting the given tensor into nonzero-disjoint component tensors. Then a mode-dependent coarse-grain hypergraph is constructed for each component tensor. A net amalgamation operation is proposed to form a composite medium-grain hypergraph from these mode-dependent coarse-grain hypergraphs to correctly encapsulate the minimization of the communication volume. We propose a heuristic which splits the nonzeros of dense slices to obtain sparse slices in component tensors. We also utilize the well-known RB paradigm to improve the quality of the splitting heuristic. We propose a medium-grain tripartite graph model with the aim of a faster partitioning at the expense of increasing the total communication volume. Parallel experiments conducted on 10 real-world tensors on up to 1024 processors confirm the validity of the proposed hypergraph and graph models.