Parallel sparse matrix-vector multiplies and iterative solvers
Paralel seyrek matris-vektör çarpımı ve dolaylı yöntemler
- Tez No: 198895
- Danışmanlar: PROF. DR. CEVDET AYKANAT
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Sparse matrices, parallel matrix-vector multiplication, iterative meth-ods, preconditioning, approximate inverse preconditioner, hypergraph partition-ing
- Yıl: 2005
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 156
Özet
Seyrek matris-vektür carpımı (MxV) bir cok bilimsel hesaplama uygula-oş şmasının cekirdeğini oluşturmaktadır. Dolayısıyla, MxV carpımlarının par-ş g s şalelleştirilmesi, bilimsel hesaplama cevrelerinin ünem verdiği bir konudur. Bus ş o gkonuda yapılmış calışmalar yü k dengelemeye ve toplam haberleşme hacminisş s u sazaltmaya odaklanmıştır. Bu tezde, toplam haberleşme sayısının da ünemlis s oolabileceği güsterilmiştir.go s Ayrıca, işlemcilere düşen en bü yü k haberleşmes us uu shacminin ve sayısının niceliğinin de ünemli olabileceği güsterilmiştir. Bu dürtg o go s ohaberleşme ülşutü nü n azaltılmasını sağlayacak hiperşizge modelleri ve bu mod-s o cü u u g cellerin bülü mlenmesini sağlayacak yüntemler ünerilmiştir. Bu ünerilen model-ou g o o s olerin ve yüntemlerin, tek boyutlu ve iki boyutlu matris bülü mlendirilmesindeo ounasıl kullanılacağı güsterilmiştir. MxV işleminin en cok kullanıldıgı yer lineergo s s şsistem cüzü mlemelerinde kullanılan dolaylı yüntemlerdir. Bu dolaylı yüntemlerşo u o ocoğu zaman matris iyileştirme teknikleri kullanırlar. Matrislerin yaklaşık ters-şg s sleriyle iyileştirme tekniği, bir cok simetrik ve simetrik olmayan matris ceşitlerines g ş şsuygulanabilen ve cokşa kullanılan bir tekniktir. Bu teknik, temel olarak, MxVşcişleminin yerine ardışık MxV işlemlerini koyar. Yani, bir MxV işlemi, matrislerins s s syaklaşık tersleriyle iyileştirme tekniğini kullanan dolaylı yüntemlerde daha bü yü ks s g o uubir hesaplama işleminin sadece kü cuk bir parşasıdır. Ardışık MxV carpımlarınıns uşü c s şarasında etkileşim vardır. Bu etkileşimler, verimli paralelleştirme işin matris-s s s clerin bir arada bülü mlendirilmesini zorunlu kılmaktadır. Bu tezde, bir aradaoubülü mlendirmenin, değişik dolaylı yüntemler işin değişik matris bülü mlendirmeou gs o c gs oumodellerine yol aştıgı güsterilmiştir. Sıkşa kullanılan bir cok dolaylı yünteminc o s c ş ohangi matris bülü mlendirme modelleriyle paralelleştirilebileceği güsterilmiştir.ou s go sBu matris bülü mlendirme modellerinin elde edilmesini sağlamak işin, üncedenou g c oünerilmiş hiperşizge modellerini birleştirerek bileşik hiperşizge modelleri geliştireno s c s s c sviviiişlemler tanımlanmıştır. Bileşik hiperşizge modellerinin bülü mlenmesi ile ma-s s s c outrislerin bir arada bülü mlendirilebileceği güsterilmiştir. Yukarıda bahsedilenou go scalışmaların pratikte işe yarayıp yaramadıklarını gürmek işin, paralel MxVşs s o cişlemini yapan bir program yazdık. Bu programla yaptığımız deneyler sırasında,s gdaha genel bir paralel program sınıfının calışma sü resinin günder işlemlerininşs u o ssırasına bağlı olduğunu gürdü k. En iyi günder işlemi sırasının bazı varsayımlarg g ou o saltında nasıl bulunabileceğini güsterdik.g oAnahtar süzcükler : Seyrek matrisler, paralel matris-vektür carpımı, dolaylıou oşyüntemler, matris iyileştirme, matrislerin yaklaşık tersleriyle iyileştirme,o s s shiperşizge bülü mleme.c ou
Özet (Çeviri)
parse matrix-vector multiply (SpMxV) operations are in the kernel of manyscientiï¬c computing applications. Therefore, eï¬cient parallelization of SpMxVoperations is of prime importance to scientiï¬c computing community. Previousworks on parallelizing SpMxV operations consider maintaining the load balanceamong processors and minimizing the total message volume. We show that the to-tal message latency (start-up time) may be more important than the total messagevolume. We also stress that the maximum message volume and latency handledby a single processor are important communication cost metrics that should beminimized. We propose hypergraph models and hypergraph partitioning methodsto minimize these four communication cost metrics in one dimensional and twodimensional partitioning of sparse matrices. Iterative methods used for solvinglinear systems appear to be the most common context in which SpMxV operationsarise. Usually, these iterative methods apply a technique called preconditioning.Approximate inverse preconditioningâwhich can be applied to a large class ofunsymmetric and symmetric matricesâreplaces an SpMxV operation by a se-ries of SpMxV operations. That is, a single SpMxV operation is only a piece of alarger computation in the iterative methods that use approximate inverse precon-ditioning. In these methods, there are interactions in the form of dependenciesbetween the successive SpMxV operations. These interactions necessitate parti-tioning the matrices simultaneously in order to parallelize a full step of the subjectclass of iterative methods eï¬ciently. We show that the simultaneous partitioningrequirement gives rise to various matrix partitioning models depending on theiterative method used. We list the partitioning models for a number of widelyused iterative methods. We propose operations to build a composite hypergraphby combining the previously proposed hypergraph models and show that par-titioning the composite hypergraph models addresses the simultaneous matrixpartitioning problem. We strove to demonstrate how the proposed partitioningivvmethodsâboth the one that addresses multiple communication cost metrics andthe other that addresses the simultaneous partitioning problemâhelp in practice.We implemented a library and investigated the performances of the partitioningmethods. These practical investigations revealed a problem that we call messageordering problem. The problem asks how to organize the send operations to min-imize the completion time of a certain class of parallel programs. We show howto solve the message ordering problem optimally under reasonable assumptions.
Benzer Tezler
- Minimizing communication latencies in conjugate gradient type parallel herative solvers
Eşlenik gradyan tipi paralel özyineli çözücülerde iletişim gecikme sürelerinin en aza indirgenmesi
M. MUSTAFA ÖZDAL
Yüksek Lisans
İngilizce
2001
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Platform and data-aware execution of sparse triangular solve on CPU-GPU heterogeneous systems
Başlık çevirisi yok
NAJEEB AHMAD
Doktora
İngilizce
2021
Mühendislik BilimleriKoç ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ DİDEM UNAT ERTEN
- Latency-centric models and methods for scaling sparse operations
Seyrek işlemlerin ölçeklenebilmesi için gecikim-merkezli model ve yöntemler
REHA OĞUZ SELVİTOPİ
Doktora
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Web-site-based partitioning techniques for efficient parallelization of the pagerank computation
Sayfadeğeri hesaplamasının etkin olarak paralelleştirilmesi için ağ sitesi tabanlı bölümleme yöntemleri
ALİ CEVAHİR
Yüksek Lisans
İngilizce
2006
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Parallel sparse and banded matrix–multiple vectors multiplication
Paralel seyrek ve bant matris–çoklu vektör çarpımı
MEFTUN CİNCİOĞLU
Yüksek Lisans
İngilizce
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. MURAT MANGUOĞLU