Partitioning sparse rectangular matrices for parallel computing of AATx

Abstract

IV ÖZET SEYREK DİKDÖRTGENSEL MATRİSLERİN AATx'W PARALEL İŞLEMCİLERDE HESAPLANABİLMESİ İÇİN PARÇALANMASI Bora Uçar Bilgisayar ve Enformatik Mühendisliği, Yüksek Lisans Tez Yöneticisi: Doc. Dr. Cevdet Aykanat Eylül, 1999 Birçok bilimsel uygulama, bir seyrek dikdörtgensel matrisin bir vektör ve de aynı matrisin transpozunun bir başka vektör ile çarpılmasını içermektedir. Şimdiye kadar kullanılan çizge ve hiperçizge parçalanması algoritmalarında toplam haberleşme hacmi azaltılırken işlemciler arasındaki işlemsel denge, ma trisin tek boyutlu ayrıştırılması ile yakalanmaya çalışılmıştır. Bu tezde, toplam haberleşme sayısı ve hacmi iki yaklaşımla azaltılmaya çalışılmıştır. Genel haberleşme yaklaşımındaki birleşik haberleşme hacminin azaltılması problemi, matrislerin tek sınırlı çarpraz bloklar haline getirilmesi problemine dönüştü rülmüştür. Bu yaklaşımdaki birleşik ve toplam haberleşme sayısı paralel iş lemcilerin bağlantısına bağlı olup değiştirilememektedir. Kişiselleştirilmiş ha berleşme yaklaşımındaki toplam haberleşme sayısı ve hacmi iki aşamada azal tılmıştır. Birinci aşamada, toplam haberleşme hacmi azaltılırken işlemsel denge sağlanılmıştır. ikinci aşamada, önerilen haberleşme hiperçizgesi yardımı ile toplam haberleşme sayısı azaltılırken işlemciler arasında haberleşme işi dengesi sağlanmaya çalışılmıştır. Sunulan yöntemler birçok matris üzerinde sınanmış ve iyi yönde sonuçlar elde edilmiştir. Anahtar kelimeler: Seyrek dikdörtgensel matrisler, hesap hiperçizgesi, haber leşme hiperçizgesi, hiperçizge parçalama.

Ill ABSTRACT PARTITIONING SPARSE RECTANGULAR MATRICES FOR PARALLEL COMPUTING OF AATx Bora Uçar M.S. in Computer Engineering and Information Science Supervisor: Asoc. Prof. Dr. Cevdet Aykanat Spetember, 1999 Many scientific applications involve repeated sparse matrix- vector and matrix- transpose- vector product computations. Graph and hypergraph partitioning based approaches used in the literature aim at minimizing the total commu nication volume while maintaining computational load balance through one dimensional partitioning of sparse matrices. In this thesis, we consider two approaches which consider minimizing both the total message count and com munication volume while maintaining balance on the communication loads of the processors. Two communication schemes are investigated for the fold and expand operations needed in the parallel algorithm. For the global communica tion scheme, we show that the problem of minimizing concurrent communica tion volume can be formulated as the problem of permuting the sparse matrix into a singly-bordered block-diagonal form, where the total and concurrent message count is determined by the interconnection topology. For the person alized communication scheme, a two stage approach is proposed. In the first stage, the total communication volume is minimized while maintaining balance on the computational loads of the processors. In the second stage, a novel com munication hypergraph model is proposed which enables the minimization of the total message count while maintaining balance on the communication loads of the processors through hypergraph-partitioning-like methods. The solution methods are tested on various matrices and results, which are quite attractive in terms of solution quality and running times, are obtained. Key words: Sparse Rectangular Matrices, Computational Hypergraph Model, Communication Hypergraph Model, Hypergraph Partitioning.