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
- AI-enhanced dynamic preemptive resource allocation in next generation cellular networks
Yeni nesil hücresel ağlarda yapay zeka destekli dinamik öncelikli kaynak tahsisi
EGE ENGİN
Doktora
İngilizce
2025
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. HAKAN ALİ ÇIRPAN
- Heterojen insansız hava aracı sürüleri için müzakere tabanlı dağıtık dinamik görev atama algoritması ve ajan haberleşme dili geliştirilmesi
Auction based distributed task assignment algorithm and agent communication language development for heterogeneous unmanned aerial vehicle swarms
MUTULLAH EŞER
Doktora
Türkçe
2025
Elektrik ve Elektronik MühendisliğiAnkara ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ASIM EGEMEN YILMAZ
- Benchmarking simultaneous authentication schemes
Eş zamanlı kimlik doğrulama şemalarının karşılaştırmalı analizi
MORTEZA AZMOUDEH AFSHAR
Yüksek Lisans
İngilizce
2025
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilişim Uygulamaları Ana Bilim Dalı
PROF. DR. ENVER ÖZDEMİR
- 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
- 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