Accelerating pagerank with a heterogeneous two phase CPU-FPGA algorithm

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.