Compiling Irregular Software to Specialized Hardware
High-level synthesis (HLS) has simplified the design process for hardware accelerators: a designer specifies an accelerator’s behavior in a high-level language, and a toolchain generates a blueprint for hardware implementing that behavior. While many HLS systems can produce efficient hardware designs for regular algorithms (i.e., those with regular memory access patterns and limited conditionals), their use of C-like input languages makes it difficult to reason about and parallelize irregular algorithms that rely on dynamic, data-dependent memory access patterns (e.g., traversing pointer-based structures like lists, trees, or graphs).
Motivated by this problem, I will present an alternative HLS methodology that generates efficient hardware for irregular algorithms. The main contribution is a compiler that translates pure, functional programs into modular, parallel dataflow networks in hardware. I will also present two compiler optimizations that improve our circuits’ performance: one rearranges pointer-based structures to decrease a synthesized circuit’s execution time and its memory footprint, the other increases memory level parallelism by transforming divide-and-conquer programs and partitioning the memory system. We can thus generate hardware from functional specifications and apply performance-improving optimizations that customize the memory system to the demands of irregular applications.
Richard Townsend is a 6th year PhD student at Columbia University studying Programming Languages and Compilers under Stephen A. Edwards and Martha A. Kim. His research focuses on the use of functional languages and high-level optimizations to translate recursive algorithms with irregular memory access patterns into efficient hardware designs. This work revolves around his research group's current project: an optimizing Haskell-to-SystemVerilog compiler.
Host: Professor Kathi Fisler