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

    418655

    Accelerating local search algorithms for travelling salesman problem using GPU effectively

    Grafik işlemci biriminin etkin kullanımıyla gezgin satıcı problemi için yerel arama algoritmalarının hızlandırılması

    GİZEM ERMİŞ

    Yüksek Lisans

    İngilizce

    İngilizce

    2015

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı Üniversitesi

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

    PROF. DR. BÜLENT ÇATAY

  3. Tez No

    421223

    Determining the effect of roughness and crystallinity on protein adsorption for polyurethane films

    Poliüretan filmlerde yüzey pürüzlülüğü ve kristalinitenin protein adsorpsiyonuna etkilerinin incelenmesi

    SELİN SOFİ KÜRKCÜOĞLU

    Yüksek Lisans

    İngilizce

    İngilizce

    2015

    Polimer Bilim ve Teknolojisiİstanbul Teknik Üniversitesi

    Polimer Bilim ve Teknolojisi Ana Bilim Dalı

    PROF. DR. FATMA SENİHA GÜNER

    YRD. DOÇ. DR. AYŞE ÖZGE KÜRKÇÜOĞLU LEVİTAS

  4. Tez No

    244165

    Accelerating volume rendering by frame indexing

    Çerçeve indexleme yöntemiyle hacim görüntüleme işleminin hızlandırılması

    ŞAHİN MANSUROĞLU

    Yüksek Lisans

    İngilizce

    İngilizce

    2009

    Elektrik ve Elektronik MühendisliğiÇukurova Üniversitesi

    Elektrik ve Elektronik Mühendisliği Bölümü

    YRD. DOÇ. DR. ULUS ÇEVİK

  5. Tez No

    255822

    Effectiveness of set accelerating admixtures with different cement types

    Farklı çimento tipleri ile priz hızlandırıcı katkıların etkinliği

    DİDEM TUĞBA ÜSTÜNER

    Yüksek Lisans

    İngilizce

    İngilizce

    2009

    İnşaat MühendisliğiOrta Doğu Teknik Üniversitesi

    Çimento Mühendisliği Ana Bilim Dalı

    PROF. DR. MUSTAFA TOKYAY

Geri Dön