Geri Dön

Parallel sparse matrix-vector multiplies and iterative solvers

Paralel seyrek matris-vektör çarpımı ve dolaylı yöntemler

  1. Tez No: 198895
  2. Yazar: BORA UÇAR
  3. Danışmanlar: PROF. DR. CEVDET AYKANAT
  4. Tez Türü: Doktora
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Sparse matrices, parallel matrix-vector multiplication, iterative meth-ods, preconditioning, approximate inverse preconditioner, hypergraph partition-ing
  7. Yıl: 2005
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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 manyscientific computing applications. Therefore, efficient parallelization of SpMxVoperations is of prime importance to scientific 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 efficiently. 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

  1. 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

    İngilizce

    2001

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CEVDET AYKANAT

  2. Platform and data-aware execution of sparse triangular solve on CPU-GPU heterogeneous systems

    Başlık çevirisi yok

    NAJEEB AHMAD

    Doktora

    İngilizce

    İngilizce

    2021

    Mühendislik BilimleriKoç Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ DİDEM UNAT ERTEN

  3. 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

    İngilizce

    2016

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CEVDET AYKANAT

  4. 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

    İngilizce

    2006

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CEVDET AYKANAT

  5. 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

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MURAT MANGUOĞLU