Send volume balancing in reduce operations
İndirgeme işlemlerinde gönderme yükünün dengelenmesi
- Tez No: 633370
- 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: 2020
- 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ı: 44
Özet
İndirgeme işlemleri içeren uygulamalarda gönderme yükünü dengeleme incelenmektedir. Bu tür uygulamalarda, verilen bir hesaplama işi-işlemci ataması; işlemcilerin, muhtemelen diğer işlemciler tarafından indirgenmek üzere ürettiği kısmi sonuçlar oluşturmaktadır. Bu durum, işlemciler arası iletişime neden olmaktadır. İndirgeme iletişim işi atama problemi; indirgeme iletişim işlerinin, gönderme yükü en fazla olan işlemcinin yükünü en aza indirgeyecek şekilde işlemcilere atanması olarak tanımlanmaktadır. Bu indirgeme iletişim işi atama problemini çözmek için bir adet bağımsız iş atama problemi bazlı ve dört adet kutu istifleme problemi bazlı yeni algoritma sunulmaktadır. Sunulan algoritmaların başarımı, seyrek matris-seyrek matris çarpımı (SpGEMM) ve seyrek matris-matris çarpımı (SpMM) çekirdek işlemleri için doğrulanmıştır. Deneysel sonuçlar; azami iletişim yükü metriğinde, SpGEMM'de ortalama %23'e varan bir iyileştirme, SpMM'de ise ortalama %12'ye varan bir iyileştirme olduğunu göstermektedir.
Özet (Çeviri)
We investigate balancing send volume in applications that involve reduce operations. In such applications, a given computational-task-to-processor mapping produces partial results generated by processors to be reduced possibly by other processors, thus incurring inter-processor communication. We define the reduce communication task assignment problem as assigning the reduce communication tasks to processors in a way that minimizes the send volume load of the maximally loaded processor. We propose one novel independent-task-assignment-based algorithm and four novel bin-packing-based algorithms to solve the reduce communication task assignment problem. We validate our proposed algorithms on two kernel operations: sparse matrix-sparse matrix multiplication (SpGEMM) and sparse matrix-matrix multiplication (SpMM). Experimental results show improvements of up to 23% on average for the maximum communication volume cost metric in SpGEMM and up to 12% improvement on average in SpMM.
Benzer Tezler
- Kredi kartları riskleri ve güvenlik önlemlerinin sigortacılık açısından incelenmesi
Research on the risks of credit cards and security implementations in the view of insurance
AYŞEGÜL BÖLÜKBAŞI
- 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
- Worst case delay analysis of arinc 664: Comparing theory with OMNeT++ simulation
Arınc 664'ün en kötü durum gecikme analizi: OMNeT++ simülasyonu ile karşılaştırma teorisi
PINAR SAVAŞ
Yüksek Lisans
İngilizce
2022
Havacılık ve Uzay MühendisliğiYıldız Teknik ÜniversitesiAviyonik Mühendisliği Ana Bilim Dalı
DOÇ. DR. AYDIN YEŞİLDİREK
DR. İBRAHİM HÖKELEK
