Geri Dön

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

  1. Tez No: 246708
  2. Yazar: KADİR AKBUDAK
  3. Danışmanlar: PROF. DR. CEVDET AYKANAT
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2009
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Bölümü
  12. Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  13. 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

  1. 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

    İngilizce

    2016

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ŞENAN ECE SCHMİDT

  2. 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

    İngilizce

    2010

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. OĞUZ TOSUN

  3. Rendering three-dimensional scenes with tetrahedral meshes

    Üç boyutlu sahnelerin dörtyüzlü örgüler ile görselleştirilmesi

    AYTEK AMAN

    Doktora

    İngilizce

    İngilizce

    2022

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. UĞUR GÜDÜKBAY

  4. 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

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CEVDET AYKANAT

  5. 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

    Türkçe

    2017

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolTOBB Ekonomi ve Teknoloji Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. OĞUZ ERGİN