Geri Dön

Parallel stochastic gradient descent on multicore architectures

Çok çekirdekli sistemlerde paralel olasılıksal gradyan alçalma

  1. Tez No: 640773
  2. Yazar: SELÇUK GÜLCAN
  3. Danışmanlar: DOÇ. DR. MUHAMMET MUSTAFA ÖZDAL, 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ı: Belirtilmemiş.
  13. Sayfa Sayısı: 78

Özet

Tezin odak noktası Olasılıksal Gradyan Alçalma (SGD) algoritmasının çok çekirdekli sistemlerde parallelleştirilmesidir. Asenkron yöntemler ve 2 boyutlu ızgara bölümlemeden yararlanan blok tabanlı yöntemler, algoritmanın paylaşımlı bellekli sistemlerde paralelleştirilmesi için kullanılan yaygın yaklaşımlardır. Asenkron yöntemler bellek üzerindeki düzensiz erişimleri sebebiyle ön-bellek sorunlarıyla karşılaşmaktadır. Izgara tabanlı yöntemlerde ise işlek arasında yük dengesizliği problemi görülebilmektedir. Tezimizde mevcut paralel SGD algoritmalarının performans seviyeleri ve paralel darboğaz noktaları incelenmiştir ve bu darboğaz noktalarını hedef alan yeni algoritmalar önerilmiştir. 2 boyutlu bölümlemede işlekler arasında yük dengesizliği problemini çözmek için kutulama tabanlı algoritmalar önerilmiştir. Belleği etkili bir şekilde kullanmak için de ızgara tabanlı asenkron paralel SGD algoritması önerilmiştir. Bu algoritma belleği daha etkili kullanmak için sıfırdışı güncelleme sırasını, faktör güncelleme sırasını bozmadan değiştirmekte ve buna uygun olarak saklı faktör matrislerini bellek üzerinde değiştirmektedir. Elde ettiğimiz deney sonuçları, önerdiğimiz yöntemlerin alternatif yöntemlere göre önemli ölçüde daha iyi çalıştığını göstermektedir.

Özet (Çeviri)

The focus of the thesis is efficient parallelization of the Stochastic Gradient Descent (SGD) algorithm for matrix completion problems on multicore architectures. Asynchronous methods and block-based methods utilizing 2D grid partitioning for task-to-thread assignment are commonly used approaches for shared-memory parallelization. However, asynchronous methods can have performance issues due to their memory access patterns, whereas grid-based methods can suffer from load imbalance especially when data sets are skewed and sparse. In this thesis, we first analyze parallel performance bottlenecks of the existing SGD algorithms in detail. Then, we propose new algorithms to alleviate these performance bottlenecks. Specifically, we propose bin-packing-based algorithms to balance thread loads under 2D partitioning. We also propose a grid-based asynchronous parallel SGD algorithm that improves cache utilization by changing the entry update order without affecting the factor update order and rearranging the memory layouts of the latent factor matrices. Our experiments show that the proposed methods perform significantly better than the existing approaches on shared-memory multi-core systems.

Benzer Tezler

  1. Parallel stochastic gradient descent with sub-iterations on distributed memory systems

    Dağıtık bellekli sistemlerde alt-iterasyonlu paralel olasılıksalgradyan alçalma

    ORHUN ÇAĞLAYAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2022

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MUHAMMET MUSTAFA ÖZDAL

    PROF. DR. CEVDET AYKANAT

  2. Novel gradient-based methods for data distribution and privacy in data science

    Veri biliminde mahremiyet ve veri dağılımına dayalı gradyan tabanlı yeni metodlar

    NURDAN KURU

    Doktora

    İngilizce

    İngilizce

    2019

    Endüstri ve Endüstri MühendisliğiSabancı Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. ŞEVKET İLKER BİRBİL

  3. Hybrid parallelization of stochastic gradient descent

    Olasılıksal gradyan alçalmanın hibrit paralelleştirilmesi

    KEMAL BÜYÜKKAYA

    Yüksek Lisans

    İngilizce

    İngilizce

    2022

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

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

    PROF. DR. CEVDET AYKANAT

  4. Matrix factorization with stochastic gradient descent for recommender systems

    Öneri sistemleri için olasılıksal eğim iniş ile matris çarpanlarına ayırma

    ÖMER FARUK AKTULUM

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CEVDET AYKANAT

  5. Türkiye enerji sektörünün stratejik konumu ve yapay sinir ağı modelleriyle enerji tüketiminin tahmini

    Turkish energy sector strategic position and neural network prediction of energy consumption models with

    HATİCE GENÇ KAVAS

    Doktora

    Türkçe

    Türkçe

    2019

    EnerjiSivas Cumhuriyet Üniversitesi

    İşletme Ana Bilim Dalı

    PROF. DR. HÜDAVERDİ BİRCAN