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: Hiperçizgeler, Seyrek matrisler, Hypergraphs, Sparse matrixes
- 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ı: Belirtilmemiş.
Ö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
- 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
- Improving data locality for compiler optimization by using hybrid genetic algorithms
Karma genetik algoritmaları kullanarak derleyici en iyileme için veri yerelliğini iyileştirmek
GÜLŞAH YILMAZ
Yüksek Lisans
İngilizce
2005
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. HALUK TOPÇUOĞLU
- A Cache-independent benchmark suite
Başlık çevirisi yok
NİLGÜN OLCAY
Yüksek Lisans
İngilizce
1993
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. MEHMET UFUK ÇAĞLAYAN
- Locality aware task scheduling in heterogeneous computing environments
Heterojen hesaplama ortamlarında yersellik bilinçli görev çizelgeleme
ALPER KÖSE
Yüksek Lisans
İngilizce
2007
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ.DR. HALUK TOPÇUOĞLU