Parallel sparse matrix vector multiplication techniques for shared memory architectures
Paylaşımlı hafıza sistemleri için parallel seyrek matris - dizi çarpım teknikleri
- Tez No: 367510
- 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: 2014
- 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ı: 115
Özet
Seyrek matris dizi çarpımı, denklem çözücülerde kullanılan anahtar işlemdir. Seyrek matrix tarafından yapılan düzensiz hafıza erişimleri nedeniyle, buyruk ön yükleyicisi, işlemci ön belleği ve dizi buyrukları gibi bir çok donanım etkili bir şekilde kullanılamamaktadır. Buda paralel verimliliğin düşmesine neden olur. Bu çalışmada, paylaşımlı hafıza sistemlerinde kullanılmak üzere, • Öğrenme yetisine sahip planlayıcı ve yük dengeleyici algoritmalar, • Dizi buyruklarını etkili bir şekilde kullanmaya olanak sağlayan melez bir seyrek veri yapısı ve • Bu veri yapısını oluşturmada kullanılan bir algoritma geliştirilmiştir. Bu çalışmada belirtilen teknikler, hem ön yapılandırmalı hemde direkt olarak seyrek matrix-dizi çarpımında kullanılabilir. Testler Intel tarafından üretilen Xeon Phi adlı, x86 tabanlı çekirdeklere ve bu çekirdekleri birbirine bağlayan halka ağ protokolüne sahip, yardımcı kartlar üzerinde yapılmıştır. Önerilen teknikler ekran kartlarında da kullanılabilir.
Özet (Çeviri)
SpMxV (Sparse matrix vector multiplication) is a kernel operation in linear solvers in which a sparse matrix is multiplied with a dense vector repeatedly. Due to random memory access patterns exhibited by SpMxV operation, hardware components such as prefetchers, CPU caches, and built in SIMD units are under-utilized. Consequently, limiting parallelization efficieny. In this study we developed; • an adaptive runtime scheduling and load balancing algorithms for shared memory systems, • a hybrid storage format to help effectively vectorize sub-matrices, • an algorithm to extract proposed hybrid sub-matrix storage format. Implemented techniques are designed to be used by both hypergraph partitioning powered and spontaneous SpMxV operations. Tests are carried out on Knights Corner (KNC) coprocessor which is an x86 based many-core architecture employing NoC (network on chip) communication subsystem. However, proposed techniques can also be implemented for GPUs (graphical processing units).
Benzer Tezler
- 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
- 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
- Parallel sparse matrix-vector multiplies and iterative solvers
Paralel seyrek matris-vektör çarpımı ve dolaylı yöntemler
BORA UÇAR
Doktora
İngilizce
2005
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Reordering methods for exploiting spatial and temporal localities in parallel sparse matrix-vector multiplication
Paralel seyrek matris vektör çarpımında uzaysal ve zamansal yerelliği kullanmak için sıralma yöntemleri
NABIL F. T. ABUBAKER
Yüksek Lisans
İ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
- Hypergraph models for sparse matrix partitioning and reordering
Seyrek matris bölümleme ve yeniden-düzenleme için hiperçizge modelleri
ÜMİT VEYSEL ÇATALYÜREK
Doktora
İ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