Geri Dön

Platform and data-aware execution of sparse triangular solve on CPU-GPU heterogeneous systems

Başlık çevirisi mevcut değil.

PDF İndir

  1. Tez No: 696264
  2. Yazar: NAJEEB AHMAD
  3. Danışmanlar: DR. ÖĞR. ÜYESİ DİDEM UNAT ERTEN
  4. Tez Türü: Doktora
  5. Konular: Mühendislik Bilimleri, Engineering Sciences
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2021
  8. Dil: İngilizce
  9. Üniversite: Koç Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 105

Özet

Seyrek üçgen çözüm (SpTRSV), doğrudan yöntemler, yinelemeli çözücüler ve en küçük kare problemleri gibi birçok bilimsel ve sayısal doğrusal cebir uygulamalarında kullanılan önemli bir hesaplama çekirdeğidir. Seyrek matris vektör çarpımı (SpMV) gibi diğer seyrek çekirdeklerle karşılaştırıldığında, SpTRSV doğası gereği farklı bilinmeyenlerin hesaplamaları arasındaki bağımlılıkların varlığı nedeniyle çoğu zaman, bir uygulamada en çok zaman alan işlemlerden biri olduğu da gözlemlenmiştir. CPU'lar ve GPU'lar için çeşitli SpTRSV algoritmaları ve uygulamaları mevcuttur. Verilenin performansı algoritması, giriş matrisinin seyreklik özelliklerine ve temeldeki donanıma büyük ölçüde bağlıdır. Ne yazık ki, tüm girdi matrisleri için en iyi performansı elde ettiği gösterilen tek bir algoritma veya donanım platformu yoktur. Bu tezde, modern CPU-GPU heterojen sistemlerinde belirli bir giriş matrisi için daha yüksek SpTRSV performansı elde etmeyi amaçlayan araçlar ve teknikler öneriyoruz. Bu amaçla, iki yönlü bir yaklaşım benimsiyoruz: Bir girdi matrisinin seyreklik özelliklerine bağlı olarak, (i) matris için en iyi CPU veya GPU SpTRSV algoritmasını otomatik olarak seçmek, (ii) paralel parça paralel uyumlu bir algoritma ile yürütülecek ve sıralı parça sıralı dostu bir algoritma ile yürütülecek şekilde SpTRSV'yi bölmek için yöntemler ve araçlar öneriyoruz. Amaç, tek bir algoritma kullanmaktan daha yüksek bir SpTRSV performansı elde etmektir. İki algoritma potansiyel olarak iki farklı platformda (CPU ve GPU) çalışabilir. SpTRSV algoritma seçimi için, yapısal özelliklerine dayalı olarak belirli bir seyrek matris için en hızlı yürütme süresini veren SpTRSV uygulamasını tahmin etmek için denetimli makine öğrenimi tabanlı bir tahmin çerçevesi öneriyoruz. Çerçeve, matris özelliklerini çıkararak, algoritma performans verilerini toplayarak ve SuiteSparse Matrix Koleksiyonundan yaklaşık 1000 gerçek, kare matrisli bir tahmin modeli eğiterek çalışır. Model, belirli bir makine üzerinde eğitildikten sonra, belirli bir matris için en hızlı SpTRSV uygulamasını tahmin eder. Çerçeve, yinelemeli çözücüler gibi bilimsel uygulamalarda ortaya çıkabilecek CPU-GPU iletişim ek yüklerini de hesaba katabilir. Çerçeveyi modern bir CPU-GPU makinesinde test diyoruz. Modern bir CPU-GPU platformunda deneysel sonuçlar (Intel Xeon Gold + NVIDIA Tesla V100 GPU), en hızlı algoritmanın makul bir doğrulukla (% 87) seçildiğini ve tahmin edilen SpTRSV uygulamasının, tek bir algoritmanın tembel bir seçimiyle karşılaştırıldığında (1.4-2.7 × harmonik ortalama) önemli hız artışlarına ulaştığını göstermektedir. ̇kinci olarak, SpTRSV yürütmesini CPU ve GPU arasında bölmek için bir SpTRSV bölünmüş yürütme modeli öneriyoruz. Model, mevcut araştırmalardan elde edilen ampirik kanıtlara dayanılarak tasarlanmıştır; (i) SpTRSV için yüksek oranda paralel algoritmalar, adım başına hesaplanan çok sayıda bilinmeyenle birkaç ardışık adım gerektiren, (ii) adım başına hesaplanan birkaç bilinmeyenle daha fazla adım gerektiren sıralı bir algoritma SpTRSV için daha iyi performans gösterir. Oldukça paralel ve sıralı adımların bir karışımına sahip olan matrisler için, paralel bir algoritmanın çok sayıda bilinmeyenli adımlar için fayda ağlaması beklenir, performansının birkaç bilinmeyenli adımlar için kötüleşmesi beklenir. Sohbet hakkında söylenebilir bu tür matrisler için sıralı algoritmaların performansı. Oldukça paralel ve sıralı bir algoritma kullanarak bu tür matrisler için bölünmüş yürütme gerçekleştirmek amacıyla, bölünmüş yürütme modelimiz bir SpTRSV'nin uygunluğunu otomatik olarak belirleyebilir. Bölünmüş yürütme için, uygun bölme noktasını bulur ve gerekli herhangi bir platformlar arası iletişimi otomatik olarak yönetirken iki SpTRSV algoritmasını kullanarak SpTRSV'yi bölünmüş bir şekilde yürütür. Model, birden çok CPU-GPU algoritmasını destekleyen C ++ / CUDA kitaplığı olarak uygulanmaktadır. Modelin deneysel değerlendirmesi SuiteSparse Matrix Collection'dan 327 matrislik bir matris veri kümesine sahip iki CPU-GPU'da (Intel Xeon Gold + NVIDIA Tesla V100 ve Intel Core I7 + NVIDIA G1080 Ti) matrislerin% 88'i ve% 83'ü için en hızlı SpTRSV yöntemini doğru şekilde seçtiğini göstermektedir. Bu platformlarda sırasıyla 10 × ve 6.36 × aralığında hızlanma sağlar. Bu tezde önerilen araçların ve yöntemlerin hem akademiye hem de endüstriye fayda sağlayacağını ve aynı zamanda seyrek doğrusal cebir hesaplamaları için CPU-GPU sistemlerinin verimli kullanımı alanında daha fazla araştırmanın yolunu açacağını umuyoruz.

Özet (Çeviri)

Sparse triangular solve (SpTRSV) is an important computational kernel used in many scientific and numerical linear algebra applications such as direct methods, iterative solvers and least square problems. In comparison with other sparse kernels such as sparse matrix-vector multiplication (SpMV), SpTRSV is an inherently sequential operation owing to the presence of dependencies among computations of different unknowns. Often, it has also been observed to be one of the most time consuming operations in an application. The performance of a given algorithm highly depends upon the sparsity characteristics of the input matrix and the underlying hardware. Several SpTRSV algorithms and their implementations are available for the CPUs and the GPUs. Unfortunately, there is no single algorithm or hardware platform that has been shown to achieve the best performance for all input matrices. In this dissertation, we propose tools and techniques aimed at extracting higher SpTRSV performance for a given input matrix on modern CPU-GPU heterogeneous systems. Towards this end, we adopt a two-pronged approach: Depending upon the sparsity characteristics of the input matrix, we propose to (i) automatically select the best CPU or GPU SpTRSV algorithm for the matrix, (ii) split a single SpTRSV execution into parallel and sequential parts such that the parallel part is executed with a parallel-friendly algorithm and the sequential part is executed with a sequential-friendly algorithm. The aim is to achieve a higher SpTRSV performance than using a single algorithm. The two algorithms can also potentially execute on two different platforms (CPU and GPU). For the SpTRSV algorithm selection, we propose a supervised machine learning-based prediction framework to predict the SpTRSV implementation giving the fastest execution time for a given sparse matrix based on its structural features. The framework works by extracting matrix features, collecting algorithm performance data, and training a prediction model with around 1000 real square matrices from the SuiteSparse Matrix Collection. Once trained on a given machine, the model can predict the fastest SpTRSV implementation for a given matrix by paying a one-time matrix feature extraction cost. The framework is also capable of taking into account CPU-GPU communication overheads that might be incurred in scientific applications such as iterative solvers. We test the framework on a modern CPU-GPU machine. Experimental results on a modern CPU-GPU platform (Intel Xeon Gold + NVIDIA Tesla V100 GPU) show that the fastest algorithm is selected with a reasonable accuracy (87%) as well as the predicted SpTRSV implementation achieves significant speedups compared (1.4-2.7× harmonic mean) with a lazy choice of a single algorithm. Secondly, for dividing the SpTRSV execution between the CPU and GPU, we propose an SpTRSV split execution model. The model has been designed based on the empirical evidence from the existing research that; (i) a highly parallel algorithms perform well for SpTRSV requiring few sequential steps, with high number of unknowns computed per step, (ii) a sequential algorithms perform better for SpTRSV requiring more steps with few unknowns computed per step. For matrices having a mix of highly parallel and sequential steps, a parallel algorithm is expected to provide benefits for steps with large number of unknowns, its performance is expected to deteriorate for steps with few unknowns. The converse can be said about the performance of sequential algorithms for such matrices. With the aim of performing split-execution for such matrices using a highly parallel and a sequential algorithm, our split execution model can automatically determine the suitability of an SpTRSV for split-execution, find the appropriate split point, and execute SpTRSV in a split fashion using two SpTRSV algorithms while automatically managing any required inter-platform communication. The model is implemented as a C++/CUDA library supporting multiple CPU-GPU algorithms. Experimental evaluation of the model on two CPU-GPU with a matrix dataset of 327 matrices from the SuiteSparse Matrix Collection shows that our approach correctly selects the fastest SpTRSV method (split or unsplit) for 88% of the matrices on Intel Xeon Gold + NVIDIA Tesla V100 and 83% of the matrices on Intel Core I7 + NVIDIA G1080 Ti platform achieving speedups up to 10× and 6.36×, respectively. We expect that the tools and methods proposed in this dissertation will benefit both academia and industry while at the same time will pave the way for further research in the area of efficient exploitation of CPU-GPU systems for sparse linear algebra computations.

Benzer Tezler

  1. Tez No

    804468

    Investigation of asset management practices in airports

    Havalimanlarında varlık yönetimi uygulamalarının incelenmesi

    CEMİL CAN UZUN

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

    İnşaat Mühendisliğiİstanbul Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    PROF. DR. ESİN ERGEN PEHLEVAN

  2. Tez No

    774752

    İnternette elektronik ticaret ortamı sağlayan aracı hizmet sağlayıcıların yükümlülükleri ve alıcıya karşı hukukî sorumluluğu

    Obligations and legal liability towards the buyer of intermediary service providers providing an electronic commerce environment on the internet

    REYHAN ÇELENKOĞLU

    Yüksek Lisans

    Türkçe

    Türkçe

    2023

    HukukGalatasaray Üniversitesi

    Özel Hukuk Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ MEHTAP İPEK İŞLETEN

  3. Tez No

    765594

    Novel data partitioning and scheduling schemes for dynamic federated vehicular cloud

    Dinamik federe araç bulutu için yeni bir görev yükü paylaşımı ve iş planlaması şemaları

    WISEBORN MANFE DANQUAH

    Doktora

    İngilizce

    İngilizce

    2022

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. DENİZ TURGAY ALTILAR

  4. Tez No

    27120

    Sigortada dağıtım ve tutundurma metodları

    Başlık çevirisi yok

    BANU GÖNENÇ

    Yüksek Lisans

    Türkçe

    Türkçe

    1994

    SigortacılıkMarmara Üniversitesi

    Sigortacılık Ana Bilim Dalı

    DOÇ. DR. OSMAN GÜRBÜZ

  5. Tez No

    539456

    Reducing processor-memory performance gap and improving network-on-chip throughput

    İşlemci-bellek performans farkını azaltmak ve yonga-üstü-ağ verimini artırmak

    MUSTAFA NAVEED UL

    Doktora

    İngilizce

    İngilizce

    2019

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. ÖZCAN ÖZTÜRK

Geri Dön