SHF: Medium: Compiling Parallel Algorithms to Memory Systems

Columbia University, New York NY

Investigators

Abstract

This project aims to improve the practice of parallel programming - perhaps the central problem facing computer science in the 21st century. While the sequential model first introduced by Von Neumann and others has served us well, its inefficiency has been brought into sharp focus by the availability of billion-transistor chips, which are greatly underutilized yet power-hungry when running sequential algorithms. This project aims to improve the programmability and efficiency of distributed memory systems, a key issue in the execution of parallel algorithms. While it is fairly easy to put, say, thousands of independent adders on a single chip, it is far more difficult to supply them with useful data to add, a task that falls to the memory system. This research will develop compiler optimization algorithms able to configure and orchestrate parallel memory systems able to utilize such parallel computational resources. To make more than incremental progress, this project departs from existing hegemony in two important ways. First, its techniques will be applied only to algorithms expressed in the functional style, a more abstract, mathematically sound representation that enables precise reasoning about parallel algorithms and very aggressive optimizations. Second, it targets field-programmable gate arrays (FPGAs) rather than existing parallel computing platforms. FPGAs provide a highly flexible platform that enables exploring parallel architectures far different than today's awkward solutions, which are largely legacy sequential architectures glued together. While FPGAs are far too flexible and power-hungry to be the long-term "solution" to the parallel computer architecture question, their use grounds this project in physical reality and will produce useful hardware synthesis algorithms as a side-effect. Judicious and efficient data movement is the linchpin of parallel computing. This project attacks that challenge head on, establishing the constructs and algorithms necessary for hardware and software to efficiently manipulate data together. This research will lay the groundwork for the next generation of storage and instruction set architectures, compilers, and programming paradigms -- the bedrock of today's mainstream computing.