Geri Dön

Minimizing communication through computational redundancy in parallel iterative solvers

Paralel yinelemeli çözümleyicilerde fazla hesaplama ile haberleşme azaltımı

  1. Tez No: 287392
  2. Yazar: FAHREDDİN ŞÜKRÜ TORUN
  3. Danışmanlar: PROF. DR. CEVDET AYKANAT
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2011
  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 Bölümü
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 70

Özet

y=Ax biçimindeki seyrek matris-vektör çarpımı (SMxV) bilimsel uygulamalardayinelemeli doğrusal denklem çözümleyicilerinde kullanılan bir çekirdekoperasyondur. Bu çözümleyicilerde, yinelemeler vasıtasıyla yakınsayıncaya kadaraynı seyrek matris ile SMxV operasyonu tekrarlanarak uygulanır. Paralel ortamdaparalel SMxV operasyonu matrise ve onun ayrışımına göre işlemcilerarasında haberleşmeye ihtiyaç duyar. Bu haberleşme akıllı ayrışımlar ileazaltılabilinir. Fakat, biz veri replikasyonu ve fazla hesaplama ile bu haberleşmeyidaha da fazla azaltabiliriz. Satır-paralel SMxV hesaplamada bu haberleşme x vektörelemanlarının transferi yüzünden oluşur. Bir sonraki yinelemenin girdivektörü x, bazı doğrusal operasyonlar vasıtasıyla yürürlükteki yinelemenin çiktivektörü y ile hesaplanır. Bundan dolayı, bir işlemci başka bir işlemciden bir x vektörelemanı almak yerine fazla bir y vektör elemanını, ki bu y vektör elemanıbir sonraki yinelemenin x vektör elemanına öncülük eder, hesaplayabilir. Böylece,fazla y vektör elemanı hesaplamak haberleşmenin azalmasına yol açabilir.Bu tezde, biz yukarıda bahsedilen yinelemeli denklem çözümlayiciler içinhesaplama ve haberleşme desenini doğru yakalayan yönlü çizge tabanlı modeltasarladık. Bundan başka, biz fazla y vektör elemanı hesaplaması sebebiylehaberleşme azalışını yönlü çizge modeli uzerinde bir kombinatoriyal problemolarak formülledik. Biz bu kombinatoriyal problemi çözmek için iki tane buluşsalyöntem önerdik. Deneysel sonuçlar göstermektedir ki fazla hesaplama yaparakhaberleşme azaltma stratejisi gelecek vaat etmektedir.

Özet (Çeviri)

Sparse matrix vector multiplication (SpMxV) of the form y = Ax is a kerneloperation in iterative linear solvers used in scientific applications. In thesesolvers, the SpMxV operation is performed repeatedly with the same sparse matrixthrough iterations until convergence. Depending on the matrix and its decomposition,parallel SpMxV operation necessitates communication among processorsin the parallel environment. The communication can be reduced by intelligentdecomposition. However, we can further decrease the communication throughdata replication and redundant computation. The communication occurs due tothe transfer of x-vector entries in row-parallel SpMxV computation. The inputvector x of the next iteration is computed from the output vector of the currentiteration through linear vector operations. Hence, a processor may compute ay-vector entry redundantly, which leads to a x-vector entry in the following iteration,instead of receiving that x-vector entry from another processor. Thus,redundant computation of that y-vector entry may lead to reduction in communication.In this thesis, we devise a directed-graph-based model that correctly capturesthe computation and communication pattern for above-mentioned iterativesolvers. Moreover, we formulate the communication minimization by utilizingredundant computation of y-vector entries as a combinatorial problem on thisdirected graph model. We propose two heuristics to solve this combinatorialproblem. Experimental results indicate that the communication reducing strategyby redundantly computing is promising.

Benzer Tezler

  1. Partitioning sparse rectangular matrices for parallel computing of AATx

    Seyrek dikdörtgensel matrislerin AATx (A A üssü T x)'in paralel işlemcilerde hesaplanabilmesi için parçalanması

    BORA UÇAR

    Yüksek Lisans

    İngilizce

    İngilizce

    1999

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

    Bilgisayar Yazılımı Ana Bilim Dalı

    DOÇ. DR. CEVDET AYKANAT

  2. Partitioning models for scaling distributed graph computations

    Dağıtık çizge hesaplamalarının ölçeklendirilmesi için bölümleme yöntemleri

    GÜNDÜZ VEHBİ DEMİRCİ

    Doktora

    İngilizce

    İngilizce

    2019

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CEVDET AYKANAT

  3. Advanced algorithms and solution techniques for U-shaped assembly line balancing problems

    U şekilli montaj hattı problemleri için gelişmiş algoritmalar ve çözüm teknikleri

    MUHAMMAD IRFAN AZHAR

    Doktora

    İngilizce

    İngilizce

    2023

    Endüstri ve Endüstri MühendisliğiKoç Üniversitesi

    Endüstri Mühendisliği ve Operasyon Yönetimi

    PROF. DR. METİN TÜRKAY

  4. A robust framework covering measures developed using EVM metric against jamming attacks in next-generation communication systems

    Yeni nesil haberleşme sistemlerinde karıştırma saldırılarına karşı EVM metriği kullanılarak geliştirilen önlemleri kapsayan güçlü bir çerçeve

    CEM ÖRNEK

    Doktora

    İngilizce

    İngilizce

    2024

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    PROF. DR. MESUT KARTAL

  5. Bilişsel radyoda özdeğer tabanlı spektrum sezme yöntemleri

    Eigenvalue based spectrum sensing techniques for cognitive radio

    SERDAR İNGÖK

    Yüksek Lisans

    Türkçe

    Türkçe

    2012

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    PROF. DR. M. ERTUĞRUL ÇELEBİ