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

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.