Tez No İndirme Tez Künye Durumu
640249
Scratch-pad memory based custom processor design for graph applications / Çizge uygulamaları için müsvedde bellek temelli özel işlemci tasarımı
Yazar:GÜLCE PULAT
Danışman: PROF. DR. ÖZCAN ÖZTÜRK
Yer Bilgisi: İhsan Doğramacı Bilkent Üniversitesi / Mühendislik ve Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin:
Onaylandı
Yüksek Lisans
İngilizce
2020
83 s.
Çizge analizi uygulamalarının önemi, giderek daha çok alanın sürekli büyüyen çizge yapılarını işlemeye başlamasıyla daha da belirgin hale gelmiştir. Bununla birlikte, genel amaçlı işlemciler çizge uygulamalarının geniş bellek ayak izi ve rastgele bellek erişimleri karşısında zorlanmaktadır. Dolayısıyla araştırmacılar alana özel donanım içerikli çözümlere yönelmiştir. Bu tezde, çizge uygulamalarının performansını bellek erişimlerini azaltarak artırmaya çalışan özel bir RISC-V çizge işlemcisi sunulmaktadır. Çizge işlemcisinin yeniliği içerdiği yazılım kontrollü Ayrıt Müsvedde (ESP), Düğüm Müsvedde (VSP) ve Global Müsvedde (GSP) isimli müsvedde belleklerine (scratch-pad memories - SPMler) dayanmaktadır. SPMler genel amaçlı sistemlerde bulunan geleneksel ön-belleklerin yerini almak için tasarlanmıştır. ESP çekirdeğin işlemlerine paralel olarak ayrıt verisiyle önceden yüklenirken, VSP düğüm ile ilgili bellek erişimlerinin neden olduğu çakışmaları azaltarak düğüm trafiğini hafifletir. GSP ise geriye kalan bellek erişimlerinin yükünü üstlenmektedir. Çizge işlemcisine gömülü bu yeni işlevselliğin yazılım tarafından kontrol edilebilir olması için RISC-V komut kümesi mimarisi SPM ile ilgili özel komutlarla genişletilmiştir. Komutların ihtiyaç duyduğu derleyici desteği de sağlanmıştır. Tasarımın gerektirdiği yazılım-donanım etkileşimini göstermek için yaygın olarak kullanılan PageRank, Tek Kaynaklı En Kısa Yol ve Sığ Öncelikli Arama algoritmaları çizge işlemcisi tarzında değiştirilmiştir. Bu uygulamalarla yapılan deneylerin sonuçları, çizge işlemcisinin aynı RISC-V çekirdeğini kullanan genel amaçlı bir işlemciye kıyasla veri yolunu durdurucu bellek erişimlerini yüzde 18 ile yüzde 72 daha az yaptığını göstermektedir.
As more and more domains have started to process ever-growing graphs, the importance of graph analytics applications became more apparent. However, general-purpose processors are challenged to deal with the large memory footprint and the associated random memory accesses in graph applications, directing researchers towards domain-specific solutions. In this dissertation, we present a custom RISC-V graph processor that tries to increase the performance of graph applications by reducing the memory accesses. The novelty of the graph processor lies in the design of our software-controlled scratch-pad memories: Edge Scratch-Pad (ESP), Vertex Scratch-Pad (VSP), and Global Scratch-Pad (GSP). While ESP is preloaded with the edge data in parallel with the execution, VSP relieves the vertex traffic by reducing the conflicts caused by the vertex-related memory accesses. GSP takes over the load of the rest of the memory accesses as these three SPMs replace the conventional caches found in general-purpose systems. For the software to control this new functionality embedded in the graph processor, we extended RISC-V instruction set architecture with custom SPM-related instructions. We provided compiler support for the instructions and we modified the widely used PageRank, Single-Source Shortest Path, and Breadth-First Search algorithms in graph processor fashion to demonstrate the software-hardware interaction needed for the design. The experimental results on these applications show that the graph processor makes 18% to 72% less datapath-blocking memory accesses compared to a general-purpose processor based on the same RISC-V core.