Reducing communication volume overhead in large-scale parallel SpGEMM
Büyük ölçekli paralel SyGEMM'de iletişim hacmini düşürme
- Tez No: 444797
- 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: 2016
- 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ı: Belirtilmemiş.
Özet
Seyrek matris-matris çarp ımlar ı (SyGEMM) bir çok alanda en s ık kullanı lan operasyonlardan biridir. Bu i şlemler genel olarak karma şık ve uzun çal ışma s ürelerine sahiptir. Da ğıtı k bellek sistemlerinde bu i şlemleri parallelle ştirmek i çin bir çok y öntem mevcuttur. Bunlar: d ış çarpı m, i ç çarpı m, sat ır-satı r çarpı m ve s üt un-s üt un çarp ımıdıır. Bu tezde, d üşük önhaz ırlı k, iyi performans ve sembolik çarpma gerektirmemesi gibi bir çok getirisinden dolay ı sat ır-satır çarpı mı na yo ğunla şılm ıştı r. Sat ır-satır çarp ım ın ın paralelle ştirilmesinde iki-k ümeli çizgeler ve hiper çizgeler kullan ılabilmektedir. Daha verimli bir paralle ştirme i çin, toplam hacim ve en y üksek hacim gibi bir çok hacim odaklı öl c üt dikkate al ınabilir. Sat ır-sat ır çarp ımlar için var olan y öntemler, bir çok hacim odakl ı ol c ut u ayn ı anda ger çekle stirmekte ba şar s z olmaktad ırlar. Bu tezde, bir çok hacim odakl ı öl çüt ü ayn ı anda d üşürmek i çin iki a şamal ı bir y öntem önerdik. İlk a şamada, toplam hacim iki k ümeli çizge kullan ılarak d üş ür ülm ü şt ür. İkinci a şamada ise toplam hacimdeki art ışı en azda tutmaya çal ışarak en y üksek hacimi d üşürd ük. Deneylerimizde g ör ülebilmektedir ki, önerdi ğimiz y öntem çeşitli SyGEMM i şlemleri i çin bir çok hacim odakl ı ölçe ği ayn ı anda d üşürm ü şt ür.
Özet (Çeviri)
Sparse matrix-matrix multiplication of the form of C = A x B, C = A x A and C = A x AT is a key operation in various domains and is characterized with high complexity and runtime overhead. There exist models for parallelizing this operation in distributed memory architectures such as outer-product (OP), inner-product (IP), row-by-row-product (RRP) and column-by-column-product (CCP). We focus on row-by-row-product due to its convincing performance, row preprocessing overhead and no symbolic multiplication requirement. The parallelization via row-by-row-product model can be achieved using bipartite graphs or hypergraphs. For an efficient parallelization, we can consider multiple volume-based metrics to be reduced such as total volume, maximum volume, etc. Existing approaches for RRP model do not encapsulate multiple volume-based metrics. In this thesis, we propose a two-phase approach to reduce multiple volume-based cost metrics. In the rst phase, total volume is reduced with a bipartite graph model. In the second phase, we reduce maximum volume while trying to keep the increase in total volume as small as possible. Our experiments show that the proposed approach is effective at reducing multiple volume-based metrics for different forms of SpGEMM operations.
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
- 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
- Novel algorithms and models for scaling parallel sparse tensor and matrix factorizations
Paralel seyrek tensör ve matris ayrışımı için yeni yöntem ve modeller
NABIL F. T. ABUBAKER
Doktora
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Bilgi ve iletişim teknolojilerinin Türkiye'nin ihracat performansına etkisi
The impact of information and communication technologies on Turkish export performance
DENİZ FEYZA AYKULTELİ
- Global marka değeri yaratmanın pazarlama iletişimi stratejilerindeki yeri: Godiva Çikolata örneği
The place of global brand value creation in marketing communication strategy: The example of Godiva Chocolate
ELİF YAMAN
Yüksek Lisans
Türkçe
2022
İşletmeGalatasaray Üniversitesiİletişim Ana Bilim Dalı
PROF. DR. BANU BAŞKAN KARSAK