Cache locality exploiting methods and models for sparse matrix-vector multiplication
Seyrek matris-vektor çarpımında önbellek yerellği sağlayan yöntem ve modeller
- Tez No: 246708
- 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: 2009
- 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ı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Sayfa Sayısı: 70
Özet
Seyrek matrix-vektör çarpımı doğrusal denklem sistemi çözen yazılımlarda çok önemli bir çekirdek işlemdir.Aynı seyrek matris, seyrek olmayan bir vektörle çok defa çarpılır.Şu anki teknolojinin sunduğu çok seviyeli önbellekler etkin kullanılırsa, bu çarpma işlemi sırasında önemli performans kazançları olabilmektedir.Lakin düzensiz veri erişimine neden olan matrisler önbellekteki veri yerelliğinin kullanımını olumsuz etkilemektedir.Bu problemi çözmek için önbellek yerelliğini kullanan pek çok yöntem şu zamana kadar sunulmuştur.Bu çalışmada, biz de iki farklı çerçeve sunuyoruz: tek matris-vektor çarpımı ve çoklu matris-vektor çarpımı.Tek matris-vektör çarpımı çerçevesinde, önbelleğin boyutunu dikkate alarak matrisin satır ve sütunlarını yeniden sıralayan ve bu sıralam işlemini hiperçizge bölümleme ile yapan bir yöntem sunuyoruz.Ve bu yöntemlere ek olarak önbelleğin boyutunu dikkate almadan yerelliği sağlayacak bir yöntem öneriyoruz.Bir de sutunları sıkıştırıp alansal yerelliği sağlayan önişleme yöntemi sunuyoruz.Çoklu matris-vektör çarpımı çerçevesinde, matrisi alt matrislere ayırarak veri yerelliğini sağlamaya çalışmayı hedefliyoruz.Yine bu ayırma işleminde de hiperçizge kullanılıyor.Alt matrislerin çarpma sırası da önem taşıdığından veri yerelliğini arttıran bir sıralamayı bulma problemini de seyyar satıcı problemi olarak çözülebileceğini açıklıyoruz.Deneysel sonuçlar bu önerilen çerçeve ve yöntemlerin şu anda kullanılan yöntemlerden daha hızlı çalıştığını göstermektedir.
Özet (Çeviri)
The sparse matrix-vector multiplication (SpMxV) is an important kernel operationwidely used in linear solvers. The same sparse matrix is multiplied by a dense vec-tor repeatedly in these solvers to solve a system of linear equations. High performancegains can be obtained if we can take the advantage of today?s deep cache hierarchyin SpMxV operations. Matrices with irregular sparsity patterns make it difficult toutilize data locality effectively in SpMxV computations. Different techniques are pro-posed in the literature to utilize cache hierarchy effectively via exploiting data local-ity during SpMxV. In this work, we investigate two distinct frameworks for cache-aware/oblivious SpMxV: single matrix-vector multiply and multiple submatrix-vectormultiplies. For the single matrix-vector multiply framework, we propose a cache-sizeaware top-down row/column-reordering approach based on 1D sparse matrix parti-tioning by utilizing the recently proposed appropriate hypergraph models of sparsematrices, and a cache oblivious bottom-up approach based on hierarchical clusteringof rows/columns with similar sparsity patterns. We also propose a column compres-sion scheme as a preprocessing step which makes these two approaches cache-line-sizeaware. The multiple submatrix-vector multiplies framework depends on the partition-ing the matrix into multiple nonzero-disjoint submatrices. For an effective matrix-to-submatrix partitioning required in this framework, we propose a cache-size awaretop-down approach based on 2D sparse matrix partitioning by utilizing the recentlyproposed fine-grain hypergraph model. For this framework, we also propose a trav-eling salesman formulation for an effective ordering of individual submatrix-vectormultiply operations. We evaluate the validity of our models and methods on a widerange of sparse matrices. Experimental results show that proposed methods and mod-els outperforms state-of-the-art schemes.
Benzer Tezler
- A low latency, high throughput and scalable hardware architecture for flow tables in software defined networks
Yazılım tanımlı bilgisayar ağları'ndakı akış tabloları için düşük gecikmeli, yüksek veri hacimli ve ölçeklendirilebilir bir donanım mimarisi
GÖKSAN ERAL
Yüksek Lisans
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. ŞENAN ECE SCHMİDT
- Memory system optimizations for cache miss reduction
Önbellek başarı oranını arttırıcı bellek sistemi optimizasyonları
DİNDAR ÖZ
Yüksek Lisans
İngilizce
2010
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. OĞUZ TOSUN
- Rendering three-dimensional scenes with tetrahedral meshes
Üç boyutlu sahnelerin dörtyüzlü örgüler ile görselleştirilmesi
AYTEK AMAN
Doktora
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. UĞUR GÜDÜKBAY
- Increasing data reuse in parallel sparse matrix-vector and matrix-transpose-vector multiply on shared-memory architectures
Paylaşılan bellek mimarisinde gerçekleştirilen paralel seyrek matris-vektör ve devrik-matris-vektör çarpımında veri yeniden kullanımını arttırmak
MUSTAFA OZAN KARSAVURAN
Yüksek Lisans
İngilizce
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Grafik işleme birimi önbelleklerinde yerelliğe bağlı dinamik yazma politikası
Locality driven dynamic cache write policy on graphics processing units
ÇAĞATAY TURGUT
Yüksek Lisans
Türkçe
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolTOBB Ekonomi ve Teknoloji ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. OĞUZ ERGİN