Locality aware reordering for sparse triangular solve
Seyrek üçgensel sistemlerin önbellek yerelliğine göre yeniden sıralanması
- Tez No: 374350
- 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ı: 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
- 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
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Bölümü
PROF. DR. CEVDET AYKANAT
- 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
2022
MimarlıkKonya Teknik ÜniversitesiMimarlık Ana Bilim Dalı
DOÇ. DR. EMİNE YILDIZ KUYRUKÇU
- 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
- 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
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. BUĞRA GEDİK
- 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
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKoç ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
Prof. Dr. ÖZNUR ÖZKASAP
Assoc. Prof. Dr. ALPTEKİN KÜPÇÜ