Parallel stochastic gradient descent on multicore architectures
Çok çekirdekli sistemlerde paralel olasılıksal gradyan alçalma
- Tez No: 640773
- Danışmanlar: DOÇ. DR. MUHAMMET MUSTAFA ÖZDAL, 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ı: Belirtilmemiş.
- 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
- 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
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUHAMMET MUSTAFA ÖZDAL
PROF. DR. CEVDET AYKANAT
- 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
2019
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ŞEVKET İLKER BİRBİL
- Hybrid parallelization of stochastic gradient descent
Olasılıksal gradyan alçalmanın hibrit paralelleştirilmesi
KEMAL BÜYÜKKAYA
Yüksek Lisans
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- 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
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- 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
2019
EnerjiSivas Cumhuriyet Üniversitesiİşletme Ana Bilim Dalı
PROF. DR. HÜDAVERDİ BİRCAN