CAREER: The Exocompiler: Decoupling Algorithms from the Organization of Computation and Data

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

The performance of many important algorithms is dominated by the way their computations and data are organized for execution on specific hardware. Traditional ways of programming conflate algorithms and their organization such that a straightforward implementation is unacceptably slow. At the same time, neither one can be written or optimized independently, which limits the productivity of programmers and the portability of programs to future hardware. Optimized organizations are often an order of magnitude faster and more complex since they necessarily take a global, rather than per-operation, view of the algorithm to exploit parallelism and locality. This project's novelty is in creating a new kind of programming language in which the algorithm and its organization are decoupled from one another. Programming systems are the tool through which computation is applied to human problems. The project's impact will be transforming the way major classes of software are written, enabling a wider range of people to more productively write new algorithms which are both high-performance and portable to future computing hardware. This project explores a programming model that decouples algorithms from their organization, represented explicitly in the language as a "schedule." It extends this paradigm from multidimensional arrays to more general computations and data structures, including sparse matrices and graphs, and builds a machine-learning system to automatically find schedules competitive with human experts. To realize this vision, it pursues four major research directions: (a) combining tree search with neural networks in a reinforcement learning system to automatically find expert-quality schedules; (b) broadening the class of expressible computations and schedules to include general loops and program gradients; (c) broadening the class of data structures and schedules with a relational model to process sparse and linked data; and (d) creating a comprehensive performance benchmark suite to serve as our evaluation testbed, and also be shared broadly to foster new research in systems, compilers, and architecture. The resulting language and compiler enables productive high-performance programming and provides a powerful foundation for easily building new domain-specific programming systems. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.