Hypergraph partitioning and reordering for parallel sparse triangular solves and tensor decomposition
Paralel seyrek üçgensel sistemler ve tensör ayrıştırma için hiperçizge bölümleme ve yeniden sıralama yöntemleri
- Tez No: 686809
- Danışmanlar: PROF. DR. CEVDET AYKANAT, PROF. DR. MURAT MANGUOĞLU
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2021
- 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ı: 151
Özet
Bir çok bilimsel ve gerçek hayatta karşılaşılan problem, seyrek matris veya daha genel haliyle çok boyutlu seyrek tensör hesaplamalarını gerektirmektedir. Seyrek matris hesaplamaları için, içerdiği işlemlerin doğal seri yapısı sebebiyle, seyrek üçgensel sistemlerin paralelleştirilmesi önemli zorluklar ortaya çıkarmaktadır. Seyrek üçgensel sistemleri paralelleştirmek için bir yaklaşım, seyrek üçgensel SPIKE (stSPIKE) algoritmasını kullanmaktır. İlk olarak paylaşımlı bellekler için önerilmiş olan stSPIKE, problemi daha küçük bağımsız sistemlere ayrıştırır ve çok daha küçük bir indirgenmiş seyrek üçgensel sistemin çözümünü gerektirir. Biz bu çalışmada, stSPIKE algoritmasını dağıtık bellekli sistemler için genişleterek yazılımını gerçekleştirdik. Daha sonra, stSPIKE algoritmasını kullanarak dağıtık bellekli paralel Gauss-Seidel (dmpGS) ve ILU (dmpILU) algoritmalarını önerdik. Ayrıca, dmpGS ve dmpILU çözümünde ortaya çıkan indirgenmiş sistemlerin boyutunu ve sıfırdışı eleman sayısını en aza indirmek amacıyla özgün hiperçizge bölümleme modelleri ve blok-içi yeniden sıralama yöntemleri önerdik. Diğer yandan seyrek tensör hesaplamaları konusunda, tensör ayrıştırma, çok boyutlu verilerin analizi için oldukça yaygın kullanılmaktadır. Kanonik çok öğeli ayrıştırma (CPD), en sık kullanılan tensör ayrıştırma yöntemlerinden biridir ve yaygın olarak CPD-ALS algoritması ile çözülür. CPD-ALS algoritmasının yüksek hesaplama ve hafıza talepleri sebebiyle, dağıtık bellekli paralel bir algoritma kullanmak verimlilik için kaçınılmazdır. Çok boyutlu kartezyen tensör bölümleme yöntemini benimseyen orta ölçekli CPD-ALS algoritması, seyrek tensör ayrıştırması için önerilmiş en başarılı dağıtık bellekli CPD-ALS algoritmalarından biridir. Biz, çok boyutlu kartezyen tensör bölümlemesinin iletişim hacmini en aza indirgemeyi, bölümleme hedefiyle doğru bir şekilde karşılayan özgün bir hiperçizge bölümleme modeli (CartHP) öneriyoruz. Gerçek hayat problemlerinden elde edilmiş seyrek matris ve tensörler üzerindeki geniş kapsamlı deneyler, önerilen algortimaların paralel ölçeklenebilirliğini ve önerilen hiperçizge bölümleme ve yeniden sıralama modellerinin etkinliğini doğrular niteliktedir.
Özet (Çeviri)
Several scientific and real-world problems require computations with sparse matrices, or more generally, sparse tensors which are multi-dimensional arrays. For sparse matrix computations, parallelization of sparse triangular systems introduces significant challenges because of the sequential nature of the computations involved. One approach to parallelize sparse triangular systems is to use sparse triangular SPIKE (stSPIKE) algorithm, which was originally proposed for shared memory architectures. stSPIKE decouples the problem into independent smaller systems and requires the solution of a much smaller reduced sparse triangular system. We extend and implement stSPIKE for distributed-memory architectures. Then we propose distributed-memory parallel Gauss-Seidel (dmpGS) and ILU (dmpILU) algorithms by means of stSPIKE. Furthermore, we propose novel hypergraph partitioning models and in-block reordering methods for minimizing the size and nonzero count of the reduced systems that arise in dmpGS and dmpILU. For sparse tensor computations, tensor decomposition is widely used in the analysis of multi-dimensional data. The canonical polyadic decomposition (CPD) is one of the most popular tensor decomposition methods, which is commonly computed by the CPD-ALS algorithm. Due to high computational and memory demands of CPD-ALS, it is inevitable to use a distributed-memory-parallel algorithm for efficiency. The medium-grain CPD-ALS algorithm, which adopts multi-dimensional cartesian tensor partitioning, is one of the most successful distributed CPD-ALS algorithms for sparse tensors. We propose a novel hypergraph partitioning model, CartHP, whose partitioning objective correctly encapsulates the minimization of total communication volume of multi-dimensional cartesian tensor partitioning. Extensive experiments on real-world sparse matrices and tensors validate the parallel scalability of the proposed algorithms as well as the effectiveness of the proposed hypergraph partitioning and reordering models.
Benzer Tezler
- Hypergraph models for sparse matrix partitioning and reordering
Seyrek matris bölümleme ve yeniden-düzenleme için hiperçizge modelleri
ÜMİT VEYSEL ÇATALYÜREK
Doktora
İngilizce
1999
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Yazılımı Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT
- Reordering methods for exploiting spatial and temporal localities in parallel sparse matrix-vector multiplication
Paralel seyrek matris vektör çarpımında uzaysal ve zamansal yerelliği kullanmak için sıralma yöntemleri
NABIL F. T. ABUBAKER
Yüksek Lisans
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- A Hypergraph-partitioning based remapping model for image-space parallel volume rendering
Görüntü-uzayı paralel hacim görüntüleme için hiperçizge bölümlemeye dayalı yeniden eşleme modeli
BERKANT BARLA
Yüksek Lisans
İngilizce
2000
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT
- Exploiting replicated data for communication load balancing in image-space parallel direct volume rendering of unstructured grids
Düzensiz ızgaralarda görüntü-uzayı paralel hacim görüntüleme için iletişim yükü eşitlemede kopyalanmış veriden faydalanma
ERKAN OKUYAN
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
- ParPaToH: A 2D parallel hypergraph partitioning tool
ParPaToH: Bir 2-boyutlu paralel hiperçizge bölümleme aracı
EVREN KARACA
Yüksek Lisans
İngilizce
2006
Mühendislik Bilimleriİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT