Hardware Acceleration of Recursive Application
Event details
Date | 26.08.2019 |
Hour | 14:00 › 16:00 |
Speaker | Jovan Blanusa |
Location | |
Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Babak Falsafi
Thesis advisor: Prof. Paolo Ienne
Thesis co-advisor: Dr. Kubilay Atasu
Co-examiner: Prof. Wenzel Jakob
Abstract
Many data- and graph-mining problems rely on recursive search and exploration. Examples of such problems include finding communities in social networks (e.g. cliques and clusters) and detecting patterns in graphs in the form of a subgraph with a specific structure. Due to the irregularity of the underlying data structures and the parallelism that arises dynamically, it is challenging to parallelize these workloads. The search tree constructed during the recursion can be very unbalanced, which can lead to uneven distribution of the workload across different threads. Scheduling, synchronization, and random memory accesses are additional challenges. The goal of this project is to discover the limits of scaling recursive algorithms on existing multi-core platforms and to propose more efficient and scalable architectures that can address the existing limitations. In this proposal, we discuss three papers that serve as the foundation for this project. First, we introduce a state-of-theart algorithm that performs a recursive search and computes all the maximal cliques of a given graph. Next, we discuss a paper which introduces a new approach for parallelizing ”irregular” algorithms, by exposing data parallelism that arises dynamically, and presents a graph processing framework which uses this approach. Finally, we examine a specific FPGA implementation of a graph processing accelerator, which uses hardware transactional memory, and discuss the way the authors tackled some problems specific to the parallelization of graph algorithms.
Background papers
Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time, by Eppstein et al.
The Tao of Parallelism in Algorithms by Pingali et al.
FPGA-Accelerated Transactional Execution of Graph Workloads, by Ma et al.
Exam president: Prof. Babak Falsafi
Thesis advisor: Prof. Paolo Ienne
Thesis co-advisor: Dr. Kubilay Atasu
Co-examiner: Prof. Wenzel Jakob
Abstract
Many data- and graph-mining problems rely on recursive search and exploration. Examples of such problems include finding communities in social networks (e.g. cliques and clusters) and detecting patterns in graphs in the form of a subgraph with a specific structure. Due to the irregularity of the underlying data structures and the parallelism that arises dynamically, it is challenging to parallelize these workloads. The search tree constructed during the recursion can be very unbalanced, which can lead to uneven distribution of the workload across different threads. Scheduling, synchronization, and random memory accesses are additional challenges. The goal of this project is to discover the limits of scaling recursive algorithms on existing multi-core platforms and to propose more efficient and scalable architectures that can address the existing limitations. In this proposal, we discuss three papers that serve as the foundation for this project. First, we introduce a state-of-theart algorithm that performs a recursive search and computes all the maximal cliques of a given graph. Next, we discuss a paper which introduces a new approach for parallelizing ”irregular” algorithms, by exposing data parallelism that arises dynamically, and presents a graph processing framework which uses this approach. Finally, we examine a specific FPGA implementation of a graph processing accelerator, which uses hardware transactional memory, and discuss the way the authors tackled some problems specific to the parallelization of graph algorithms.
Background papers
Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time, by Eppstein et al.
The Tao of Parallelism in Algorithms by Pingali et al.
FPGA-Accelerated Transactional Execution of Graph Workloads, by Ma et al.
Practical information
- General public
- Free