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
- Şeker şurubunun inversiyonuna etki eden kimi faktörlerin araştırılması
Başlık çevirisi yok
SAİDE GÜNERİ
- Katı yakıtların akışkan yatakta yakılması ve katı miktarının yatak yüksekliğine etkisi
Combustion of solid fuels in the fkuidized beds and the effects of solid quantity to the height of bed
KAMİL BEKİR KOÇ
- Pleurotus ostreatus mantarının bazı kağıtçılık hammaddelerinde yaptığı biyolojik degradasyon
Başlık çevirisi yok
M. KEMAL YALINKILIÇ
Yüksek Lisans
Türkçe
1987
Karadeniz Teknik ÜniversitesiOrman Endüstri Mühendisliği Ana Bilim Dalı
Yükleniyor...
- Yerçekimi dengelenmesinin Helianthus annuus fidelerinde hücre çeperi ekstensibilitesine şeker ve nişasta içeriğine etkisi
Başlık çevirisi yok
MUAMMER ÜNAL