Investigation Performance of Strassen Matrix Multiplication Algorithm on Distributed Systems

Abstract

Parallel computation is the concurrent performance of a task with multiple processors in order to obtain rapid results. This method is based on that the process of solving a problem can usually be divided into smaller problem parts and with some coordination, these solution parts perform simultaneously. Simply put, parallel computing is the concurrent use of different computing resources for solving a computational problem. Parallel computing saves time, solves large problems efficiently and is cost-effective or non-local sources. There are two important models in the architecture of parallel computing: I. Shared memory: In this multiprocessor system, all of the allocated processors can access to a common memory. II. Message passing: In this multiprocessor system, each processor has its own local memory; processors exchange messages and share data through an internal connection network. In this thesis Strassen recursive algorithm is implemented for multiplying square matrices in parallel form for a distributed homogeneous system in order to improve its execution time. Strassen multiplying algorithm is a divide and conquer problem, with temporal complexity O ( ). Since this algorithm is recursive, total parallelism is impossible thus, matrices must be divided and distributed according to a special distribution topology in which affects on the performance time. This thesis represents an economical distribution topology with distributing matrices, which minimize the multiplication time of matrices in a parallel environment. Dividing and distributing matrices according to a basic distribution topology (two-fold distribution), led to favorable and unfavorable results. To improve the results, the matrix distribution topology needs to be changed. Finding a desirable and convenient topology is necessary aiming to achieve suitable results by considering matrices dimensions and the number of nodes. So, this method is expected to reduce the execution time in comparison with Strassen-BMR method. Keywords: Parallel Computation, Message Passing, Strassen Algorithm, Divide and Conquer, Topology

ÖZ: Paralel hesaplama, hızlı sonuç elde etmek amacıyla, bir görevin birden fazla işlemci tarafından eşzamanlı hesaplanmasıdır. Bu yöntem, genellikle, büyük bir problemi küçük parçalara ayırıp çözme gerçeğine dayanmaktadır. Ve bu parçaların çözümü, bazı koordinasyonlarla, aynı anda gerçekleştirilir. Basitçe söylemek gerekirse, paralel hesaplama sistemi bir hesaplama problemini çözmek için farklı işlem kaynaklarının eşzamanlı kullanılmasıdır. Paralel hesaplama sistemi, zaman kazandıran, büyük problemleri verimli bir şekilde çözen, düşük maliyetli, yerel olmayan kaynaklardır.Paralel hesaplama mimarisi için iki önemli model kullanılmaktadır: I. Paylaşılan bellek: Bu çok işlemcili sistemde, tüm tahsis edilen işlemciler ortak bir belleğe erişebilir. II. Mesaj geçen: Bu çok işlemcili sistemde, her işlemcinin kendi yerel hafızası vardır; işlemciler dahili bir bağlantıyla ağ üzerinden mesaj alış verisi yaparak veri paylaşabilirler. Bu tezde, Strassen'in özyinelemeli algoritması, kare matrislerin çarpımı için, paralel şekilde dağıtılmış homojen bir sistemde, yürütme süresini iyileştirilmek amacıyla mesaj geçişi modeliyle uygulanmıştır. Strassen çarpım algoritması zamansal karmaşıklığı O ( ) ile, problemi böl ve yönet (divide and conquer) yöntemidir. Bu algoritma özyinelemeli olduğu için, tamamen eşzamanlı yapılması imkansızdır.Bu nedenle, yürütme süresini azaltmak için, matrisler özel bir dağıtım topolojisine göre bölünüp dağıtılmalıdır. Bu tez, paralel bir ortamda, matrislerin çarpma süresini azaltmak maksadıyle, ekonomik bir dağıtım topolojisi önermektedir. Matrisleri temel bir dağıtım topolojisiyle (ikili dağıtım) bölüp ağ üzerinde dağıtmak, olumlu ve olumsuz sonuçlara yol açar. Sonuçları iyileştirmek için, matris dağıtım topolojisinin iyileştirilmesi gerekmektedir. İstenilen bir sonuç elde etmek için, matris boyutları ve bilgisayar sayısı dikkate alınarak, arzu edilen, uygun bir topoloji bulunması gerekmektedir. Bu tezde, önerilen bir topoloji üzerinde Strassen algoritması uygulanmıştır. Elde edilen sonuçlara göre, önerilen yöntem ve topoloji önceki yöntemlerle karşılaştırıldığında yürütme zamanında azalma olduğu tespit edilmiştir. Anahtar Kelimeler: Paralel Hesaplama, Mesaj Geçen, Strassen Algoritması, Böl ve Yönet, Topoloji