Geri Dön

Locality aware reordering for sparse triangular solve

Seyrek üçgensel sistemlerin önbellek yerelliğine göre yeniden sıralanması

  1. Tez No: 374350
  2. Yazar: TUĞBA TORUN
  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: 2014
  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 Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 82

Özet

Seyrek üçgensel sistem çözümü, bir çok bilimsel ve mühendislik uygulamalarında yaygın olarak kullanılan bir çekirdek işlemdir. Bu çekirdek işlemin çok seviyeli önbellekler üzerinde etkili bir şekilde yürütülmesi, yüksek performans elde etmek açısından önemlidir. Biz bu çalışmada, seyrek üçgensel sistem çözümünde kullanılmak üzere etkili bir çerçeve sunuyoruz. Seyrek lineer sistemlerin direkt metod ile çözümü, L alt üçgensel faktör ve U üst üçgensel faktör olmak üzere, LUz = b biçimindeki bir üçgensel denklem çözümünü gerektirir. Önbelleği kullanmak için, üçgensel sistemdeki veri bağlılığını da göz önüne alarak L faktörünün satır ve sütunlarını yeniden sıraladık. Üçgensel sistemdeki veri bağlılıklarını yönlü bir hiperçizge olarak kodlayıp, bu yapı üzerinde sıralı bir bölümleme modeli inşa ettik. Bu amaçla, bağlılık sınırlamalarına riayet edecek biçimde Fiduccia-Mattheyses (FM) algoritmasını farklı bir şekilde yeniden geliştirdik. Ayrıca, bu işlemde daha fazla esneklik elde etmek için, L faktörlerini seyrek ve yoğun parçalara ayırma fikrini benimsedik ve her bir parçayı otomatik ayarlanmış farklı çekirdek yöntemlerle çözdük. Farklı depolama yöntemleri kullanarak L faktörünün ve buna karşılık gelen seyrek ve yoğun parçaların performans değişimini inceledik. İşlemci ve hafıza arasındaki hız farklarından kaynaklanan performans kayıplarını önlemek için, OSKI tarafından sağlanan otomatik ayarlama yöntemlerinden faydalandık. Gerçek veriler üzerinde yürütülen deneyler, önerilen modelin etkinliğini doğrular niteliktedir.

Özet (Çeviri)

Sparse Triangular Solve (SpTS) is a commonly used kernel in a wide variety of scientific and engineering applications. Efficient implementation of this kernel on current architectures that involve deep cache hierarchy is crucial for attaining high performance. In this work, we propose an effective framework for cache-aware SpTS. Solution of sparse linear symmetric systems utilizing the direct methods require the triangular solve of the form LUz = b, where L is lower triangular factor and U is upper triangular factor. For cache utilization, we reorder the rows and columns of the L factor regarding the data dependencies of the triangular solve. We represent the data dependencies of the triangular solve as a directed hypergraph and construct an ordered partitioning model on this structure. For this purpose, we developed a variant of Fiduccia-Mattheyses (FM) algorithm which respects the dependency constraints. We also adopt the idea of splitting L factors into dense and sparse components and solving them seperately with different autotuned kernels for achieving more flexibility in this process. We investigate the performance variation of different storage schemes of L factors and the corresponding sparse and dense components. We utilize autotuning provided by Optimized Sparse Kernel Interface (OSKI) to reduce performance degradation that incurs due to the gap between processors and memory speeds. Experiments performed on real-world datasets verify the effectiveness of the proposed framework.

Benzer Tezler

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

    KADİR AKBUDAK

    Yüksek Lisans

    İngilizce

    İngilizce

    2009

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

    Bilgisayar Mühendisliği Bölümü

    PROF. DR. CEVDET AYKANAT

  2. Ağa Han mimarlık ödüllü yapıların yer'le ilişkisinin okunması

    Reading the relationship of Ağa Han architecture awarded buildings with the ground

    HAVVA ÖZKAN

    Yüksek Lisans

    Türkçe

    Türkçe

    2022

    MimarlıkKonya Teknik Üniversitesi

    Mimarlık Ana Bilim Dalı

    DOÇ. DR. EMİNE YILDIZ KUYRUKÇU

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

    İngilizce

    2007

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ.DR. HALUK TOPÇUOĞLU

  4. Locality-aware distributed state partitioning for stream processing systems

    Veri katarı işleme sistemleri için veri yerelliği farkındalığı olan dağıtık durum bölümlendirmesi

    MUHAMMED YAĞMUR ŞAHİN

    Yüksek Lisans

    İngilizce

    İngilizce

    2016

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. BUĞRA GEDİK

  5. SEALA: Secure, efficient, availability, and locality-aware peer-to-peer cloud storage platform-as-a-service

    Başlık çevirisi yok

    YAHYA HASSANZADEH NAZARABADI

    Doktora

    İngilizce

    İngilizce

    2019

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

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    Prof. Dr. ÖZNUR ÖZKASAP

    Assoc. Prof. Dr. ALPTEKİN KÜPÇÜ