Geri Dön

Send volume balancing in reduce operations

İndirgeme işlemlerinde gönderme yükünün dengelenmesi

  1. Tez No: 633370
  2. Yazar: MUHAMMED ÇAVUŞOĞLU
  3. Danışmanlar: PROF. DR. CEVDET AYKANAT
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2020
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
  13. 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

  1. 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

    Yüksek Lisans

    Türkçe

    Türkçe

    1995

    BankacılıkMarmara Üniversitesi

    DOÇ.DR. ÖMÜR Ş. BABAOĞLU

  2. 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

    İngilizce

    2020

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CEVDET AYKANAT

  3. 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

    İngilizce

    2009

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Bölümü

    PROF. DR. CEVDET AYKANAT

  4. 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

    İngilizce

    2022

    Havacılık ve Uzay MühendisliğiYıldız Teknik Üniversitesi

    Aviyonik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. AYDIN YEŞİLDİREK

    DR. İBRAHİM HÖKELEK

  5. Factoring ve yeniden yapılanma

    Başlık çevirisi yok

    ALİ ORHAN

    Doktora

    Türkçe

    Türkçe

    1996

    Mühendislik Bilimleriİstanbul Teknik Üniversitesi

    Y.DOÇ.DR. MEHMET BOLAK