Geri Dön

Reducing communication volume overhead in large-scale parallel SpGEMM

Büyük ölçekli paralel SyGEMM'de iletişim hacmini düşürme

PDF İndir

  1. Tez No: 444797
  2. Yazar: BAŞAK ÜNSAL
  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: 2016
  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ı: Belirtilmemiş.
  13. Sayfa Sayısı: 59

Ö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ütun-sütun ç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ı ölcüt dikkate alınabilir. Satır-satır çarpımlar için var olan yöntemler, bir çok hacim odaklı olcutu aynı anda gerçeklestirmekte başarsz 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

  1. Tez No

    641212

    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

  2. Tez No

    752083

    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

    İngilizce

    2022

    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. Tez No

    246588

    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. Tez No

    492500

    A framework for task placement on multicore architectures

    Çok çekirdekli mimariler üzerinde görev yerleştirme için çerçeve

    PIRAH NOOR SOOMRO

    Yüksek Lisans

    İngilizce

    İngilizce

    2018

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKoç Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    Assist. Prof. Dr. DİDEM UNAT

  5. Tez No

    83716

    Hypergraph models for sparse matrix partitioning and reordering

    Seyrek matris bölümleme ve yeniden-düzenleme için hiperçizge modelleri

    ÜMİT VEYSEL ÇATALYÜREK

    Doktora

    İngilizce

    İngilizce

    1999

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

    Bilgisayar Yazılımı Ana Bilim Dalı

    DOÇ. DR. CEVDET AYKANAT

Geri Dön