Recursive bipartitioning models for performance improvement in sparse matrix computations
Seyrek matris hesaplamalarında performans iyileşmesi için özyinelemeli ikiye bölümleme modelleri
- Tez No: 472891
- Danışmanlar: PROF. DR. CEVDET AYKANAT
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Bilim ve Teknoloji, Computer Engineering and Computer Science and Control, Science and Technology
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- 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ı: 166
Özet
Seyrek matris hesaplamaları lineer cebirin en önemli yapıtaşlarından olup bilim ve mühendislik alanlarında birçok problemde ortaya çıkmaktadırlar. Bu hesaplamalar, problem türüne bağlı olarak seyrek matris yoğun matris çarpımı (SyMM), seyrek matris vektör çarpımı (SyMV), veya seyrek simetrik bir matrisin faktorizasyonu şeklinde olabilirler. Dağıtık bellekli mimarilerde gerçekleştirilen SyMM ve SyMV işlemlerinde, özellikle düzensiz seyreklik örüntüsü olan matrisler için, işlemciler arasındaki veri ve görev bölümlemesi paralel performansı fazlaca etkilemektedir. Paralel SyMM işlemciler arasındaki yüksek hacimli iletişimler ile nitelendirilirken, paralel SyMV için hem iletişim hacmi hem de mesaj sayısı önemli olmaktadır. Zarf yöntemlerinde gerçekleştirilen faktörizasyonda, matris zarfının büyüklüğü yani matris profili faktörizasyon performansını belirleyen önemli bir etmendir. Bahsi geçen hesaplamaların performanslarını iyileştirmek amacıyla bu hesaplamaların herbiri için özyinelemeli ikiye bölümleme (ÖİB) paradigmasını kullanan çizge/hiperçizge bölümleme modelleri önermekteyiz. Önerilmekte olan modeller, ÖİB tarafından sunulan avantajları ilgili hesaplamanın performans iyileşmesi yönünde spesifik ihtiyaçlarını karşılama amacıyla kullanmaktadırlar. ÖİB işlemi bölümleme objektifinin, SyMM için önerilen modellerde birden fazla hacim tabanlı iletişim maliyeti ölçütlerini, SyMV için ise hem hacim hem mesaj sayısı ölçütlerini hedefleyecek şekilde kullanılmasını sağlamaktadır. Zarf yöntemlerindeki faktörizasyon için önerilen modelde ise, ÖİB işlemi, matris profilini küçültme ile yakından ilişkili olan iki yeni kalite ölçütünün tanımlanıp hedeflenmesine izin vererek girdi matrisin satır ve sütunlarını bu hedefle yeniden sıralanmasını sağlamaktadır. Deneysel sonuçlar ÖİB yaklaşımının bahsi geçen herbir hesaplama için alanında var olan en iyi yöntemlerden daha başarılı olduğunu göstermektedir.
Özet (Çeviri)
Sparse matrix computations are among the most important building blocks of linear algebra and arise in many scientific and engineering problems. Depending on the problem type, these computations may be in the form of sparse matrix dense matrix multiplication (SpMM), sparse matrix vector multiplication (SpMV), or factorization of a sparse symmetric matrix. For both SpMM and SpMV performed on distributed-memory architectures, the associated data and task partitions among processors affect the parallel performance in a great extent, especially for the sparse matrices with an irregular sparsity pattern. Parallel SpMM is characterized by high volumes of data communicated among processors, whereas both the volume and number of messages are important for parallel SpMV. For the factorization performed in envelope methods, the envelope size (i.e., profile) is an important factor which determines the performance. For improving the performance in each of these sparse matrix computations, we propose graph/hypergraph partitioning models that exploit the advantages provided by the recursive bipartitioning (RB) paradigm in order to meet the specific needs of the respective computation. In the models proposed for SpMM and SpMV, we utilize the RB process to enable targeting multiple volume-based communication cost metrics and the combination of volume- and number-based communication cost metrics in their partitioning objectives, respectively. In the model proposed for the factorization in envelope methods, the input matrix is reordered by utilizing the RB process in which two new quality metrics relating to profile minimization are defined and maintained. The experimantal results show that the proposed RB-based approach outperforms the state-of-the-art for each mentioned computation.
Benzer Tezler
- Reducing communication overhead in sparse matrix and tensor computations
Seyrek matris ve tensör hesaplamalarında iletişim yükünün azaltılması
MUSTAFA OZAN KARSAVURAN
Doktora
İngilizce
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Latency-centric models and methods for scaling sparse operations
Seyrek işlemlerin ölçeklenebilmesi için gecikim-merkezli model ve yöntemler
REHA OĞUZ SELVİTOPİ
Doktora
İ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
- Hypergraph-based data partitioning
Hiperçizge tabanlı veri bölümleme
ENVER KAYAASLAN
Doktora
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- A recursive graph bipartitioning algorithm by vertex separators with fixed vertices for permuting sparse matrices into block diagonal form with overlap
Seyrek matrislerin örtüşen blok köşegen biçime düzenlenmesi için düğüm ayıracı ve sabit düğümleri kullanan özyineli bir çizge bölümleme algoritması
SEHER ACER
Yüksek Lisans
İngilizce
2011
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Bölümü
PROF. DR. CEVDET AYKANAT
- Özyinelemeli çizim tabanlı sınırsız kapalı alan sanal gerçeklik motoru geliştirilmesi
Recursive rendering based infinite closed space virtual reality engine development
ALİ EMRE GÜLCÜ
Yüksek Lisans
Türkçe
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolTOBB Ekonomi ve Teknoloji ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. ALİ AYDIN SELÇUK