Reducing communication volume increase in latency efficient store-and-forward scheme
Gecikme verimli sakla-ve-yönlendir şemasında iletişim hacmi artışının azaltılması
- Tez No: 983382
- 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: 2025
- 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ı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: Belirtilmemiş.
Özet
Seyrek matris-vektör (SpMV) gibi seyrek matris işlemleri, işlemciler tarafından gönderilen mesaj sayısının genel iletişim yükünü belirlediği gecikim-sınırlı uygulamalardır. Önceki çalışmalarda, SpMV gibi ince-taneli işlemleri ölçeklendirmek için Sanal İşlemci Topolojileri (VPT'ler) üzerinde çalışan Sakla-ve-Yönlendir (SvY) şeması önerilmiş ve uygulanmıştır. Ancak SvY şeması SvY yükünden dolayı iletişim hacminde bir artışa yol açar. Toplam iletişim hacmindeki bu artış, özellikle seyrek matrisin uzun ve ince yoğun bir matrisle sağdan çarpıldığı seyrek matris-matris (SpMM) çekirdeklerinde, SvY şemasının ölçeklenebilirliğini bozar. Bu çalışmada, başlangıçtaki görev bölümlemesi tarafından üretilen birebir atamayı yinelemeli olarak iyileştirmek için Kernighan-Lin tabanlı (KL) bir sezgisel öneriyor ve uyguluyoruz. Bu sezgiselin amacı, SpMV ve SpMM türü çekirdeklerde SvY şemasının yaratacağı toplam iletişim hacmindeki artışı azaltmaktır. Önerilen KL tabanlı sezgiselin etkinliğini, farklı boyutlardaki VPT'ler ve yapıcı atama yöntemleri kullanılarak yapılan deneysel performans karşılaştırmalarıyla Toplam İletişim Hacmi ve Maksimum Ağırlıklı İletişim Hacmi metrikleri açısından değerlendirdik.
Özet (Çeviri)
Sparse matrix operations such as sparse matrix-vector (SpMV) are latency bound applications where number of messages sent by processors dominate the overall communication overhead. In prior work, Store and Forward (STFW) scheme was proposed and implemented to scale such fine-grain operations as SpMV by operating on specialized Virtual Process Topologies (VPTs). However, the STFW scheme incur an increase in the communication volume due to the STFW overhead. This increase in total communication volume disturbs the scalability of the STFW scheme, especially in sparse matrix-matrix (SpMM) kernels where a sparse matrix is post-multiplied by a tall-and-skinny dense matrix. In this work, we propose and implement a Kernighan-Lin-based (KL) heuristic to iteratively improve the one-to-one mapping produced by the initial task partition. The objective of this heuristic is to reduce the increase in the total communication volume to be incurred by the STFW scheme in SpMV, and SpMM type of kernels. We evaluated the effectiveness of the proposed KL-based heuristic in improving the Total Communication Volume and Maximum Weighted Communication Volume metrics through experimental performance comparisons using VPTs of various dimensions and constructive mapping methods.
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
- 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
- Reducing communication volume overhead in large-scale parallel SpGEMM
Büyük ölçekli paralel SyGEMM'de iletişim hacmini düşürme
BAŞAK ÜNSAL
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
- 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
- Sendika dergilerinde özelleştirme gündemi: Petrol-İş ve Tek Gıda-İş örnekleri
Privatization agenda in union magazines: Examples of Petrol-İş and tek Gıda-İş
GAYE KUAS
Yüksek Lisans
Türkçe
2022
İletişim BilimleriGalatasaray ÜniversitesiRadyo Televizyon ve Sinema Ana Bilim Dalı
DOÇ. DR. CEREN SÖZERİ ÖZDAL