Paralel matris işlemleri kütüphanesinin çizge bölümlemeye dayalı olarak gerçeklenmesi

Abstract

ÖZET PARALEL MATRİS İŞLEMLERİ KÜTÜPHANESİNİN ÇİZGE BÖLÜMLEMEYE DAYALI OLARAK GERÇEKLENMESİ ALP, Ali Yüksek Lisans Tezi, Uluslararası Bilgisayar Enstitüsü Tez Yöneticisi: Prof.Dr. Kayhan ERCİYEŞ Ağustos, 2002, 107 sayfa Bu tezde çizge bölümleme metodları kullanılarak dinamik paralel matris işlemleri kütüphanesi gerçekleştirilmiş ve çizge bölümleme için yeni yöntemler önerilmiştir. Çizge bölümleme problemini çözmek için geliştirilen seri ve paralel algoritmaların coğrafi bilgi sistemleri, bilimsel hesaplamalar, iş paylaşımı vb. gibi bir çok alanda uygulamaları vardır. Bu tezde sunulan çizge bölümleme algoritması diğer yöntemlerde olduğu gibi kabalaştırma, parçalama ve ayrıştırma aşamalarını içermektedir. Eski metodlardan farklı olarak önerilen yöntemde ilk olarak birbirlerinden belirli uzaklıkta olan sabit düğümler seçilir ve bunlar kabalaştırma aşamasında kendilerine komşu olan uygun düğümler ile kümelenir. Yeni yöntem ile elde edilen sonuçlar diğer metodların sonuçları ile karşılaştırıldığında, yeni yöntemin çok daha dengeli, eşit büyüklükteVI çizge bölümleri oluşturduğu görülmüştür. Bu tezde ayrıca, önerilen merkezi düğüm algoritması paralel hale getirilmiş ve iş istasyonları grubu kullanılarak uygulaması yapılmıştır. Elde edilen sonuçlar paralel algoritmanın seri algoritmaya göre daha iyi çalışma zamanına sahip olduğunu göstermiştir. Basit paralel matris işlemlerini gerçekleştiren çok sayıda paralel matris kütüphanesi bulunmasına karşın, bu tezde gerçekleştirilen kütüphanede kullanıcılar, matris boyutunu, yapılacak matris işlemini ve bu işlemde kullanılacak olan çizge bölümleme yöntemini seçebildiği için kütüphane dinamik bir yapıya sahiptir. Seri çalışma zamanı oldukça yüksek olan matris çarpımı, kofaktör ve adjoint matrisinin bulunması, ters matrisin hesaplanması işlemleri paralel matris kütüphanesinde gerçekleştirildiğinde seri sürenin altına inildiği ve yüksek speed-up değerlerinin elde edildiği görülmüştür. Ancak, matris toplama, çıkarma, matris determinantının ve kronecker çarpımının hesaplanması gibi kısa seri çalışma zamanlarına sahip işlemlerde seri sürenin altına inilemememiştir. Elde edilen sonuçlar, bu işlemlerin paralelleştirilmeye uygun olmadığını göstermiştir. Anahtar Sözcükler: Çizge bölümleme, paralel programlama, dağıtık sistemler, matris işlemleri.

VII ABSTRACT PARALLEL MATRIX LIBRARY USING GRAPH PARTITIONING ALP, Ali Msc in International Computing Institute Supervisor: Prof.Dr. Kayhan HRCİYEŞ August, 2002, 1 07 pages In this thesis, a dynamic parallel matrix library using graph partitioning is. realized and new methods are developed for the graph partitioning. Serial and parallel algorithms for the graph partitioning problem that has extensive applications in many areas, including scientific computing, task scheduling and geographical information systems have been presented The presented algorithm has coarsening, partitioning and uncoarsening phases like other partitioning methods. But, fixed nodes which have a specified distance to each others have been chosen and they have been coarsened with their neighbor nodes in the coarsening phase. Much better balanced partitions have been obtained in the new method than in other algorithms. Also, a parallel method for the centered node matching(CM) algorithm has been developed. It is shown that parallel CM has better runtimes than the serial one.VIII Although there are many parallel matrix libraries which implement basic parallel matrix operations, the library implemented in this thesis differs from them because of its dynamic structure. In this dynamic parallel matrix library, user can choose the matrix size, matrix operation and the graph partitioning method. Some matrix operations such as multiplication, calculation of the inverse, cofactor and adjoint matrixes have long serial run time. Fortunately, in the paralel matrix library, these operations have shorter parallel runtimes than the serial times and high speed-up values, good efficiencies. However, because of the very short serial run times of some matrix operations such as matrix addition/subtraction, calculation of the Kronecker Product and the determinant of a matrix, library has obtained longer parallel am times and bad speed-up values for this operations. Therefore, it is seen that addition/subtraction, Kronecker Product and determinant operations is not suitable for parallelization. Keywords: Graph Partitioning, parallel programming, distributed systems, matrix operations.