Bilkent University
Department of Computer Engineering
MS THESIS PRESENTATION

 

OPENCL-BASED EFFICIENT HLS IMPLEMENTATION OF ITERATIVE GRAPH ALGORITHMS ON FPGA

 

Kenan Çağrı Hırlak
MS Student
(Supervisor: Prof. Dr. Özcan Öztürk)
Computer Engineering Department
Bilkent University

Emergence of CPU-FPGA hybrid architectures create a demand for high abstraction programming tools such as High Level Synthesis (HLS). HLS handles most of the FPGA development tasks automatically thus freeing up programmers to create applications effortlessly on FPGAs with familiar programming languages. However, HLS often trades speed for convenience which makes it a bad choice when it comes to applications in which speed is a key necessity such as Graph Algorithms. In the scope of iterative graph algorithms, we developed custom HLS-based optimizations. Specifically, we applied these on PageRank (PR), Breadth-First Search (BFS), and Connected Components (CC) algorithms so that they can be synthesized in a performant way by HLS tools. We observed that well-pipelined OpenCL kernels can provide up to 3 times speedups on the Intel Xeon-FPGA architecture compared to CPU implementations. We optimized traversal of vertices for pipelining to execute applications faster. Furthermore, our approach relies on HLS workflow in order to make it effortless for the programmer.

 

DATE: 11 December 2020, Friday @ 10:00