Large-scale transactional execution of FPGA-accelerated irregular applications

Abstract

Irregular workloads are programs organized around pointer-based data structures such as graphs. They are widely used in many fields such as computer/human network analysis, machine learning, data mining, graphics, electronic design automation, and so on. Many irregular applications have massive data-level parallelism because they iterate over a large number of graph nodes or edges using the same operators. This dissertation proposes large-scale transactional execution, as well as an architecture to achieve this approach. We apply this approach to irregular applications by executing a large number of graph operations concurrently and as transactions to deal with potential conflicts. Before this work, large-scale transactional execution was generally considered impractical because doing so might incur too many conflicts that would negate the potential benefits of the parallelization. We propose a set of techniques to address the high conflict issue and argue that given the large size and topology of many modern graphs, large-scale, multi-threaded, transactional execution can provide performance, energy efficiency, and programability benefits. We present challenges of realizing such an architecture, including the requirement of scalable conflict detection, livelock avoidance and transactional state overflow handling, and propose solutions. While the proposed techniques are also applicable to CPUs and ASICs, we focus on using FPGAs and implement the proposed architecture as a synthesizable FPGA RTL design. We compare our implementation in performance and energy efficiency against an Intel Haswell-based baseline platform. In addition, we perform an extensive study of various micro-architectural design choices in large-scale transactional execution architecture and evaluate their impact on performance. Finally, we explore the use of fine-grained locks to replace transactions to further improve performance.