Minimizing communication through computational redundancy in parallel iterative solvers
Paralel yinelemeli çözümleyicilerde fazla hesaplama ile haberleşme azaltımı
- Tez No: 287392
- Danışmanlar: PROF. DR. CEVDET AYKANAT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2011
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Bölümü
- Bilim Dalı: Belirtilmemiş.
- 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
- 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
1999
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Yazılımı Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT
- 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
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- 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
2023
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği ve Operasyon Yönetimi
PROF. DR. METİN TÜRKAY
- 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
2024
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. MESUT KARTAL
- 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
2012
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. M. ERTUĞRUL ÇELEBİ