Geri Dön

Accelerating pagerank with a heterogeneous two phase CPU-FPGA algorithm

İşlemci ve FPGA kullanarak ayrışık iki fazlı yöntemi ile pagerank algoritmasını hızlandırmak

PDF İndir

  1. Tez No: 654342
  2. Yazar: FURKAN USTA
  3. Danışmanlar: DOÇ. MUHAMMET MUSTAFA ÖZDAL
  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ı: 52

Özet

PageRank a ̆g analizinde kullanılan, her noktanın ̧cizge i ̧cerisindeki ̈oneminihesaplayan bir algoritmadır. ̈oz ̈unde Seyrek-Matris ve Vekt ̈or ̧carpımını e ̧sitolan bir problem olup aynı performans sıkıntılarından muzdariptir: d ̈uzensizhafıza eri ̧simi ve hesaplama-ileti ̧sim oranının d ̈u ̧s ̈uk olması. Dahası, PageRanki ̧cin hali hazırda mevcut bulunan Alanda Programlanabilir Kapı Dizisi (FPGA)hızlandırıcıları ya ̧cizgenin tamamının hızlandırıcının hafızasında bulunmasınıgerektiriyor ya da var olan kaynakları yeteri kadar etkili kullanamıyor. Yakınzamanda yayınlanmıs olan, Yayılma Tıkama (PB) metodu PageRank'i gruplamave toplama adı verilen iki adıma ayırarak performansını arttırmaktadır. Bizde bu makelede PB algoritmasının ilk a ̧saması FPGA ̈uzerinde ikini a ̧samasıise Merkezi ̇I ̧slem Birimi (CPU) ̈uzerinde ayrı ̧sık bi ̧cimde y ̈uksek hacimli olarak ̧calı ̧saca ̆gı bir tasarım sunduk. Daha ̈onceden var olan y ̈ontemlerin aksine bizimtasarımımız herhangi boyuttaki ̧cizgeleri, sadece hızlandırıcı ̈uzerindeki hafızayıkullanarak i ̧sleyebilmektedir. Deneylerimiz sonucunda elde etti ̆gimiz sonu ̧clar bizehızlandırıcımızın %40'a kadar hız artı ̧sı sa ̆gladı ̆gını g ̈ostermektedir.

Özet (Çeviri)

PageRank is a network analysis algorithm that is used to measure the importance of each vertex in a graph. Fundamentally it is a Sparse Matrix-Vector multiplication problem and suffers from the same bottlenecks, such as irregular memory access and low computation-to-communication ratio. Moreover, the existing Field Programmable Gate Array (FPGA) accelerators for PageRank algorithm either require large portions of the graph to be in-memory, which is not suitable for big data applications or cannot fully utilize the memory bandwidth. Recently published Propagation Blocking(PB) methodology improves the performance of PageRank by dividing the execution into binning and accumulation phases. In this paper, we propose a heterogeneous high-throughput implementation of the PB algorithm where the binning phase executed on the FPGA while accumulation is done on a CPU. Unlike prior solutions, our design can handle graphs of any sizes with no need for an on-board FPGA memory. We also show that despite the low frequency of our device, compared to the CPU, by offloading random writes to an accelerator we can still improve the performance significantly. Experimental results show that with our proposed accelerator, PB algorithm can gain up to 40\% speedup.

Benzer Tezler

  1. Tez No

    378409

    Çizge tabanlı metin özetleme

    Graph based text summarization

    CAN YALKIN

    Yüksek Lisans

    Türkçe

    Türkçe

    2014

    Mühendislik BilimleriYıldız Teknik Üniversitesi

    Matematik Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. NİLGÜN GÜLER BAYAZIT

  2. Tez No

    463654

    Accelerating line of sight analysis algorithms with parallel programming

    Görüş hattı analizi algoritmalarının paralel programlama ile hızlandırılması

    GÖKHAN YILMAZ

    Yüksek Lisans

    İngilizce

    İngilizce

    2017

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Modelleme ve Simülasyon Ana Bilim Dalı

    DOÇ. DR. ALPTEKİN TEMİZEL

    YRD. DOÇ. ELİF SÜRER

  3. Tez No

    576081

    Accelerating the understanding of life's code through better algorithms and hardware design

    Yaşamın kodunu anlamayı daha iyi algoritmalar ve donanım tasarımlarıyla hızlandırmak

    MOHAMMED H. K. ALSER MOHAMMED H. K. ALSER

    Doktora

    İngilizce

    İngilizce

    2018

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    Assist. Prof. Dr. CAN ALKAN

    Prof. Dr. ONUR MUTLU

  4. Tez No

    580190

    DNA sekanslarında genlerin CUDA ve OpenCL kullanılarak hızlı saptanması

    Accelerating gene identification in DNA sequences with CUDAand OpenCL

    SHAFIEI ABDI SULEIMAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKaradeniz Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. İBRAHİM SAVRAN

  5. Tez No

    386089

    Accelerating stencil computation in multi-core architecture

    Çok çekirdek mimarlığında hızlandırılması stencıl hesaplama

    AMAR RAEED KHORSHİD ALHİLALİ

    Yüksek Lisans

    İngilizce

    İngilizce

    2015

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolÇankaya Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. EMRE SERMUTLU

Geri Dön