I'm an assistant professor at UIUC in the Computer Science department, and Electrical and Computer Engineering department (by courtesy) and researcher at Google Deepmind/Cloud. Previously, I was a PhD candidate and undergrad at MIT studying computer science and physics. Before that, I attended Thomas Jefferson High School for Science and Technology (TJHSST) in Northern Virginia. My group has multiple PhD positions available for Fall 2025. If you are interested in compilers or high performance computing, including with applications to machine learning, climate science, databases, security, or biology, please reach out and apply to the Computer Science department at UIUC (I can also advise students from other departments).
To take full advantage of a specific hardware target, performance engineers need to gain control on compilers in order to leverage their domain knowledge about the program and hardware. Yet, modern compilers are poorly controlled, usually by configuring a sequence of coarse-grained monolithic black-box passes, or by means of predefined compiler annotations/pragmas. These can be effective, but often do not let users precisely optimize their varying compute loads. As a consequence, performance engineers have to resort to implementing custom passes for a specific optimization heuristic, requiring compiler engineering expert knowledge. In this paper, we present a technique that provides fine-grained control of general-purpose compilers by introducing the Transform dialect, a controllable IR-based transformation system implemented in MLIR. The Transform dialect empowers performance engineers to optimize their various compute loads by composing and reusing existing - but currently hidden - compiler features without the need to implement new passes or even rebuilding the compiler. We demonstrate in five case studies that the Transform dialect enables precise, safe composition of compiler transformations and allows for straightforward integration with state-of-the-art search methods.
@misc{transformcgo, title = {The MLIR Transform Dialect. Your compiler is more powerful than you think}, author = {Lücke, Martin Paul and Zinenko, Oleksandr and Moses, William S. and Steuwer, Michel and Cohen, Albert}, booktitle = {2025 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)}, year = {2025}, volume = {}, issn = {}, pages = {119-132}, publisher = {ACM}, month = mar, shortname = {CGO'25}, pdf = {https://arxiv.org/pdf/2409.03864} }
The size and complexity of software applications is increasing at an accelerating pace. Source code repositories (along with their dependencies) require vast amounts of labor to keep them tested, maintained, and up to date. As the discipline now begins to also incorporate automatically generated programs, automation in testing and tuning is required to keep up with the pace – let alone reduce the present level of complexity. While machine learning has been used to understand and generate code in various contexts, machine learning models themselves are trained almost exclusively on static code without inputs, traces, or other execution time information. This lack of training data limits the ability of these models to understand real-world problems in software.
In this work we show that inputs, like code, can be generated automatically at scale. Our generated inputs are stateful, and appear to faithfully reproduce the arbitrary data structures and system calls required to rerun a program function. By building our tool within the compiler, it both can be applied to arbitrary programming languages and architectures and can leverage static analysis and transformations for improved performance. Our approach is able to produce valid inputs, including initial memory states, for 90% of the ComPile dataset modules we explored, for a total of 21.4 million executable functions. Further, we find that a single generated input results in an average block coverage of 37%, whereas guided generation of five inputs improves it to 45%.
@misc{ivanov2024inputgenguidedgenerationstateful, title = {Input-Gen: Guided Generation of Stateful Inputs for Testing, Tuning, and Training}, author = {Ivanov, Ivan R. and Meyer, Joachim and Grossman, Aiden and Moses, William S. and Doerfert, Johannes}, year = {2024}, eprint = {2406.08843}, archiveprefix = {arXiv}, primaryclass = {cs.SE}, url = {https://arxiv.org/abs/2406.08843}, pdf = {https://arxiv.org/pdf/2406.08843}, shortname = {arXiv} }
The size and complexity of software applications is increasing at an accelerating pace. Source code repositories (along with their dependencies) require vast amounts of labor to keep them tested, maintained, and up to date. As the discipline now begins to also incorporate automatically generated programs, automation in testing and tuning is required to keep up with the pace – let alone reduce the present level of complexity. While machine learning has been used to understand and generate code in various contexts, machine learning models themselves are trained almost exclusively on static code without inputs, traces, or other execution time information. This lack of training data limits the ability of these models to understand real-world problems in software.
In this work we show that inputs, like code, can be generated automatically at scale. Our generated inputs are stateful, and appear to faithfully reproduce the arbitrary data structures and system calls required to rerun a program function. By building our tool within the compiler, it both can be applied to arbitrary programming languages and architectures and can leverage static analysis and transformations for improved performance. Our approach is able to produce valid inputs, including initial memory states, for 90% of the ComPile dataset modules we explored, for a total of 21.4 million executable functions. Further, we find that a single generated input results in an average block coverage of 37%, whereas guided generation of five inputs improves it to 45%.
@inproceedings{10444828, author = {Ivanov, Ivan R. and Zinenko, Oleksandr and Domke, Jens and Endo, Toshio and Moses, William S.}, booktitle = {2024 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)}, title = {Retargeting and Respecializing GPU Workloads for Performance Portability}, year = {2024}, volume = {}, issn = {}, pages = {119-132}, doi = {10.1109/CGO57630.2024.10444828}, url = {https://doi.ieeecomputersociety.org/10.1109/CGO57630.2024.10444828}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, month = mar, shortname = {CGO'24}, pdf = {https://c.wsmoses.com/papers/polygeist24.pdf} }
Code is increasingly becoming a core data modality of modern machine learning research impacting not only the way we write code with conversational agents like OpenAI’s ChatGPT, Google’s Bard, or Anthropic’s Claude, the way we translate code from one language into another, but also the compiler infrastructure underlying the language. While modeling approaches may vary and representations differ, the targeted tasks often remain the same within the individual classes of models. Relying solely on the ability of modern models to extract information from unstructured code does not take advantage of 70 years of programming language and compiler development by not utilizing the structure inherent to programs in the data collection. This detracts from the performance of models working over a tokenized representation of input code and precludes the use of these models in the compiler itself. To work towards the first intermediate representation (IR) based models, we fully utilize the LLVM compiler infrastructure, shared by a number of languages, to generate a 182B token dataset of LLVM IR. We generated this dataset from programming languages built on the shared LLVM infrastructure, including Rust, Swift, Julia, and C/C++, by hooking into LLVM code generation either through the language’s package manager or the compiler directly to extract the dataset of intermediate representations from production grade programs. Statistical analysis proves the utility of our dataset not only for large language model training, but also for the introspection into the code generation process itself with the dataset showing great promise for machine-learned compiler components.
@article{grossman2023compile, title = {ComPile: A Large IR Dataset from Production Sources}, author = {Grossman, Aiden and Paehler, Ludger and Parasyris, Konstantinos and Ben-Nun, Tal and Hegna, Jacob and Moses, William and Diaz, Jose M Monsalve and Trofin, Mircea and Doerfert, Johannes}, journal = {arXiv preprint arXiv:2309.15432}, year = {2023}, shortname = {arXiv}, pdf = {https://arxiv.org/pdf/2309.15432.pdf} }
Quantum computing promises transformational gains for solving some problems, but little to none for others. For anyone hoping to use quantum computers now or in the future, it is important to know which problems will benefit. In this paper, we introduce a framework for answering this question both intuitively and quantitatively. The underlying structure of the framework is a race between quantum and classical computers, where their relative strengths determine when each wins. While classical computers operate faster, quantum computers can sometimes run more efficient algorithms. Whether the speed advantage or the algorithmic advantage dominates determines whether a problem will benefit from quantum computing or not. Our analysis reveals that many problems, particularly those of small to moderate size that can be important for typical businesses, will not benefit from quantum computing. Conversely, larger problems or those with particularly big algorithmic gains will benefit from near-term quantum computing. Since very large algorithmic gains are rare in practice and theorized to be rare even in principle, our analysis suggests that the benefits from quantum computing will flow either to users of these rare cases, or practitioners processing very large data.
@article{choi2023quantum, title = {The Quantum Tortoise and the Classical Hare: A simple framework for understanding which problems quantum computing will accelerate (and which it will not)}, author = {Choi, Sukwoong and Moses, William S and Thompson, Neil}, journal = {arXiv preprint arXiv:2310.15505}, year = {2023}, series = {arXiv}, shortname = {arXiv}, pdf = {https://arxiv.org/pdf/2310.15505.pdf} }
While parallelism remains the main source of performance, architectural implementations and programming models change with each new hardware generation, often leading to costly application re-engineering. Most tools for performance portability require manual and costly application porting to yet another programming model.We propose an alternative approach that automatically translates programs written in one programming model (CUDA), into another (CPU threads) based on Polygeist/MLIR. Our approach includes a representation of parallel constructs that allows conventional compiler transformations to apply transparently and without modification and enables parallelism-specific optimizations. We evaluate our framework by transpiling and optimizing the CUDA Rodinia benchmark suite for a multi-core CPU and achieve a 58% geomean speedup over handwritten OpenMP code. Further, we show how CUDA kernels from PyTorch can efficiently run and scale on the CPU-only Supercomputer Fugaku without user intervention. Our PyTorch compatibility layer making use of transpiled CUDA PyTorch kernels outperforms the PyTorch CPU native backend by 2.7\texttimes.
@inproceedings{moses2022high, author = {Moses, William S. and Ivanov, Ivan R. and Domke, Jens and Endo, Toshio and Doerfert, Johannes and Zinenko, Oleksandr}, title = {High-Performance GPU-to-CPU Transpilation and Optimization via High-Level Parallel Constructs}, year = {2023}, isbn = {9798400700156}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3572848.3577475}, doi = {10.1145/3572848.3577475}, booktitle = {Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming}, pages = {119–134}, numpages = {16}, keywords = {CUDA, MLIR, barrier synchronization, polygeist}, location = {Montreal, QC, Canada}, series = {PPoPP '23}, shortname = {PPoPP '23}, papertype = {conference}, pdf = {https://dl.acm.org/doi/pdf/10.1145/3572848.3577475} }
Automatic differentiation (AutoDiff) in machine learning is largely restricted to expressions used for neural networks (NN), with the depth rarely exceeding a few tens of layers. Compared to NN, numerical simulations typically involve iterative algorithms like time steppers that lead to millions of iterations. Even for modest-sized models, this may yield infeasible memory requirements when applying the adjoint method, also called backpropagation, to time-dependent problems. In this situation, checkpointing algorithms provide a trade-off between recomputation and storage. This paper presents the package Checkpointing.jl that leverages expression transformations in the programming language Julia and the package ChainRules.jl to automatically and transparently transform loop iterations into differentiated loops. The user may choose between various checkpointing algorithm schemes and storage devices. We describe the unique design of Checkpointing.jl and demonstrate its features on an automatically differentiated MPI implementation of Burgers’ equation on the Polaris cluster at the Argonne Leadership Computing Facility.
@inproceedings{10.1007/978-3-031-36024-4_37, author = {Schanen, Michel and Narayanan, Sri Hari Krishna and Williamson, Sarah and Churavy, Valentin and Moses, William S. and Paehler, Ludger}, editor = {Miky{\v{s}}ka, Ji{\v{r}}{\'i} and de Mulatier, Cl{\'e}lia and Paszynski, Maciej and Krzhizhanovskaya, Valeria V. and Dongarra, Jack J. and Sloot, Peter M.A.}, title = {Transparent Checkpointing for Automatic Differentiation of Program Loops Through Expression Transformations}, booktitle = {Computational Science -- ICCS 2023}, year = {2023}, publisher = {Springer Nature Switzerland}, address = {Cham}, pages = {483--497}, isbn = {978-3-031-36024-4}, shortname = {ICCP '23}, pdf = {https://c.wsmoses.com/papers/checkpointing_jl.pdf} }
Automatic differentiation, also known as backpropagation, AD, autodiff, or algorithmic differentiation, is a popular technique for computing derivatives of computer programs accurately and efficiently. Sometimes, however, the derivatives computed by AD could be interpreted as incorrect. These pitfalls occur systematically across tools and approaches. In this paper we broadly categorize problematic usages of AD and illustrate each category with examples such as chaos, time-averaged oscillations, discretizations, fixed-point loops, lookup tables, and linear solvers. We also review debugging techniques and their effectiveness in these situations. With this article we hope to help readers avoid unexpected behavior, detect problems more easily when they occur, and have more realistic expectations from AD tools
@article{huckelheim2023understanding, title = {Understanding Automatic Differentiation Pitfalls}, author = {H{\"u}ckelheim, Jan and Menon, Harshitha and Moses, William and Christianson, Bruce and Hovland, Paul and Hasco{\"e}t, Laurent}, journal = {arXiv preprint arXiv:2305.07546}, year = {2023}, series = {arXiv}, shortname = {arXiv}, pdf = {https://arxiv.org/pdf/2305.07546.pdf} }
@article{brown2022performance, title = {Performance Portable Solid Mechanics via Matrix-Free $ p $-Multigrid}, author = {Brown, Jed and Barra, Valeria and Beams, Natalie and Ghaffari, Leila and Knepley, Matthew and Moses, William and Shakeri, Rezgar and Stengel, Karen and Thompson, Jeremy L and Zhang, Junchao}, journal = {arXiv preprint arXiv:2204.01722}, papertype = {preprint}, shortname = {arXiv}, year = {2022}, pdf = {https://arxiv.org/pdf/2204.01722.pdf} }
@inproceedings{transformersLLVM, title = {Enabling Transformers to Understand Low-Level Programs}, author = {Guo, Zifan and Moses, William S.}, booktitle = {2022 IEEE High Performance Extreme Computing Conference (HPEC)}, year = {2022}, organization = {IEEE}, shortname = {HPEC '22}, papertype = {conference}, overleaf = {https://www.overleaf.com/project/62d1dd7a6097679455a75368}, pdf = {https://c.wsmoses.com/papers/hpectransformers.pdf} }
@inproceedings{enzymePar, title = {Scalable Automatic Differentiation of Multiple Parallel Paradigms through Compiler Augmentation}, author = {Moses, William S and Hari Krishna Narayanan, Sri and Paehler, Ludger and Churavy, Valentinand H{\"u}ckelheim, Jan and Schanen, Michel and Doerfert, Johannes and Hovland, Paul}, booktitle = { {SC} '22: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, year = {2022}, location = {St. Louis, Missouri}, conference = { {SC} '22: The International Conference for High Performance Computing, Networking, Storage and Analysis}, award = {Best Student Paper Award and Best Paper Finalist}, shortname = {SC '22}, papertype = {conference}, overleaf = {https://www.overleaf.com/project/60eb1022cd54f70251e1294b}, pdf = {https://c.wsmoses.com/papers/enzymePar.pdf} }
Computing derivatives is key to many algorithms in scientific computing and machine learning such as optimization, uncertainty quantification, and stability analysis. Enzyme is a LLVM compiler plugin that performs reverse-mode automatic differentiation (AD) and thus generates high performance gradients of programs in languages including C/C++, Fortran, Julia, and Rust. Prior to this work, Enzyme and other AD tools were not capable of generating gradients of GPU kernels. Our paper presents a combination of novel techniques that make Enzyme the first fully automatic reversemode AD tool to generate gradients of GPU kernels. Since unlike other tools Enzyme performs automatic differentiation within a general-purpose compiler, we are able to introduce several novel GPU and AD-specific optimizations. To show the generality and efficiency of our approach, we compute gradients of five GPU-based HPC applications, executed on NVIDIA and AMD GPUs. All benchmarks run within an order of magnitude of the original program’s execution time. Without GPU and AD-specific optimizations, gradients of GPU kernels either fail to run from a lack of resources or have infeasible overhead. Finally, we demonstrate that increasing the problem size by either increasing the number of threads or increasing the work per thread, does not substantially impact the overhead from differentiation.
@inproceedings{enzymeGPU, title = {Reverse-Mode Automatic Differentiation and Optimization of {GPU} Kernels via Enzyme}, author = {Moses, William S and Churavy, Valentin and Paehler, Ludger and H{\"u}ckelheim, Jan and Hari Krishna Narayanan, Sri and Schanen, Michel and Doerfert, Johannes}, booktitle = { {SC} '21: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, year = {2021}, location = {St. Louis, Missouri}, conference = { {SC} '21: The International Conference for High Performance Computing, Networking, Storage and Analysis}, award = {Best Student Paper Finalist and Best Reproducibility Advancement Finalist}, shortname = {SC '21}, pdf = {https://c.wsmoses.com/papers/EnzymeGPU.pdf}, papertype = {conference}, tex = {https://github.com/wsmoses/Paper-EnzymeSC21}, overleaf = {https://www.overleaf.com/project/60395b62c1de7024e5b878fc} }
We present Polygeist, a new compilation flow that connects the MLIR compiler infrastructure to cutting edge polyhedral optimization tools. It consists of a C and C++ frontend capable of converting a broad range of existing codes into MLIR suitable for polyhedral transformation and a bi-directional conversion between MLIR and OpenScop exchange format. The Polygeist/MLIR intermediate representation featuring high-level (affine) loop constructs and n-D arrays embedded into a single static assignment (SSA) substrate enables an unprecedented combination of SSA-based and polyhedral optimizations. We illustrate this by proposing and implementing two extra transformations: statement splitting and reduction parallelization. Our evaluation demonstrates that Polygeist outperforms on average both an LLVM IR-level optimizer (Polly) and a source-to-source state-of-the-art polyhedral compiler (Pluto) when exercised on the Polybench/C benchmark suite in sequential (2.53x vs 1.41x, 2.34x)and parallel mode (9.47x vs 3.26x, 7.54x) thanks to the new representation and transformations.
@inproceedings{polygeistPACT, title = {Polygeist: Raising {C} to Polyhedral {MLIR}}, author = {Moses, William S. and Chelini, Lorenzo and Zhao, Ruizhe and Zinenko, Oleksandr}, booktitle = {Proceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques}, numpages = {12}, location = {Virtual Event}, shortname = {PACT '21}, publisher = {Association for Computing Machinery}, year = {2021}, address = {New York, NY, USA}, keywords = {Polygeist, MLIR, Polyhedral, LLVM, Compiler, C++, Pluto, Polly, OpenScop, Parallel, OpenMP, Affine, Raising, Transformation, Splitting, Automatic-Parallelization, Reduction, Polybench}, pdf = {https://c.wsmoses.com/papers/Polygeist_PACT.pdf}, papertype = {conference}, tex = {https://github.com/wsmoses/Paper-PolygeistPACT21}, overleaf = {https://braintex.goog/project/6113bf60410be30098c30301} }
We present Polygeist, a new tool that reroutes polyhedral compilation flows to use the representation available in the recent MLIR compilation infrastructure. It consists of two parts: a C and C++ frontend capable of converting a wide variety of existing codes into MLIR suitable for polyhedral trans- formation, and a bi-directional conversion between MLIR’s polyhedral representation and existing polyhedral exchange formats. We demonstrate Polygeist’s flow by converting the entire Polybench/C benchmark suite into MLIR, and by per- forming an IR-to-IR optimization leveraging an existing polyhedral compiler (Pluto). Our flow produces results within 1.25% of the state-of-the-art Clang compiler, enabling direct comparison of source-to-source and IR-to-binary compilers. We believe Polygeist can improve the interoperation between MLIR and the existing polyhedral tooling, benefiting both the research and the production compiler communities.
@inproceedings{polygeistIMPACT, title = {Polygeist: Affine {C} in {MLIR}}, author = {Moses, William S. and Chelini, Lorenzo and Zhao, Ruizhe and Zinenko, Oleksandr}, booktitle = {IMPACT 2021-11th International Workshop on Polyhedral Compilation Techniques}, year = {2021}, pdf = {https://acohen.gitlabpages.inria.fr/impact/impact2021/papers/IMPACT_2021_paper_1.pdf}, shortname = {IMPACT '21}, papertype = {workshop}, tex = {https://github.com/wsmoses/Paper-PolygeistIMPACT21}, overleaf = {https://braintex.goog/project/5fc12a5b595bff00806782b7} }
Applying differentiable programming techniques and machine learning algorithms to foreign programs requires developers to either rewrite their code in a machine learning framework, or otherwise provide derivatives of the foreign code. This paper presents Enzyme, a high-performance automatic differentiation (AD) compiler plugin for the LLVM compiler framework capable of synthesizing gradients of statically analyzable programs expressed in the LLVM intermediate representation (IR). Enzyme can synthesize gradients for programs written in any language whose compiler targets LLVM IR including C, C++, Fortran, Julia, Rust, Swift, MLIR, etc., thereby providing native AD capabilities in these languages. Unlike traditional source-to-source and operator-overloading tools, Enzyme performs AD on optimized IR. On a machine-learning focused benchmark suite including Microsoft’s ADBench, AD on optimized IR achieves a geometric mean speedup of 4.5x over AD on IR before optimization allowing Enzyme to achieve state-of-the-art performance. Packaging Enzyme for PyTorch and TensorFlow provides convenient access to gradients of foreign code with state-of-the art performance, enabling foreign code to be directly incorporated into existing machine learning workflows.
@inproceedings{enzymeNeurips, author = {Moses, William and Churavy, Valentin}, booktitle = {Advances in Neural Information Processing Systems}, editor = {Larochelle, H. and Ranzato, M. and Hadsell, R. and Balcan, M. F. and Lin, H.}, pages = {12472--12485}, publisher = {Curran Associates, Inc.}, title = {Instead of Rewriting Foreign Code for Machine Learning, Automatically Synthesize Fast Gradients}, url = {https://proceedings.neurips.cc/paper/2020/file/9332c513ef44b682e9347822c2e457ac-Paper.pdf}, volume = {33}, year = {2020}, award = {Spotlight Presentation}, shortname = {NeurIPS '20}, pdf = {https://proceedings.neurips.cc/paper/2020/file/9332c513ef44b682e9347822c2e457ac-Paper.pdf}, hackernews = {https://news.ycombinator.com/item?id=26012289}, reddit = {https://www.reddit.com/r/cpp/comments/j7fb4a/enzyme_highperformance_automatic_differentiation}, papertype = {conference}, tex = {https://github.com/wsmoses/Paper-EnzymeNeurips20}, overleaf = {https://www.overleaf.com/project/5ec2b7bc4e59f40001a9be13} }
@article{haj2020protuner, title = {ProTuner: tuning programs with Monte Carlo tree search}, author = {Haj-Ali, Ameer and Genc, Hasan and Huang, Qijing and Moses, William and Wawrzynek, John and Asanovi{\'c}, Krste and Stoica, Ion}, journal = {arXiv preprint arXiv:2005.13685}, year = {2020}, shortname = {arXiv}, papertype = {preprint}, tex = {https://github.com/wsmoses/Paper-Protuner}, overleaf = {https://www.overleaf.com/project/5e4f77f9a690c5000145ac3a}, pdf = {https://arxiv.org/pdf/2005.13685.pdf} }
@misc{govindarajan2020syfer, title = { {SyFER-MLIR}: Integrating Fully Homomorphic Encryption Into the {MLIR} Compiler Framework}, author = {Govindarajan, Sanath and Moses, William S}, pdf = {https://math.mit.edu/research/highschool/primes/materials/2020/Govindarajan-Moses.pdf}, papertype = {preprint}, year = {2020} }
The performance of the code a compiler generates depends on the order in which it applies the optimization passes. Choosing a good order–often referred to as the \em phase-ordering problem–is an NP-hard problem. As a result, existing solutions rely on a variety of heuristics. In this paper, we evaluate a new technique to address the phase-ordering problem: deep reinforcement learning. To this end, we implement a framework that takes a program and finds a sequence of passes that optimize the performance of the generated circuit. Without loss of generality, we instantiate this framework in the context of an LLVM compiler and target high-level synthesis programs. We use random forests to quantify the correlation between the effectiveness of a given pass and the program’s features. This helps us reduce the search space by avoiding orderings that are unlikely to improve the performance of a given program. We compare the performance of deep reinforcement learning to state-of-the-art algorithms that address the phase-ordering problem. In our evaluation, we show that reinforcement learning improves circuit performance by 28% when compared to using the -O3 compiler flag, and it achieves competitive results compared to the state-of-the-art solutions, while requiring fewer samples. More importantly, unlike existing state-of-the-art solutions, our reinforcement learning solution can generalize to more than 12,000 different programs after training on as few as a hundred programs for less than ten minutes.
@article{haj2020autophase, title = {AutoPhase: Juggling HLS Phase Orderings in Random Forests with Deep Reinforcement Learning}, author = {Haj-Ali, Ameer and Huang, Qijing Jenny and Xiang, John and Moses, William and Asanovic, Krste and Wawrzynek, John and Stoica, Ion}, booktitle = {Proceedings of Machine Learning and Systems}, editor = {Dhillon, I. and Papailiopoulos, D. and Sze, V.}, pages = {70--81}, url = {https://proceedings.mlsys.org/paper/2020/file/4e732ced3463d06de0ca9a15b6153677-Paper.pdf}, volume = {2}, year = {2020}, papertype = {conference}, tex = {https://github.com/wsmoses/Paper-AutophaseMLSys}, overleaf = {https://www.overleaf.com/project/5c9ad45dd502c2597ba2c3b1} }
@inproceedings{huang2019autophase, title = {Autophase: Compiler phase-ordering for {HLS} with deep reinforcement learning}, author = {Huang, Qijing and Haj-Ali, Ameer and Moses, William and Xiang, John and Stoica, Ion and Asanovic, Krste and Wawrzynek, John}, booktitle = {2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)}, pages = {308--308}, year = {2019}, organization = {IEEE}, shortname = {FCCM '19}, papertype = {workshop}, tex = {https://github.com/wsmoses/Paper-AutophaseFCCM}, overleaf = {https://www.overleaf.com/project/5c1325e30800c53868650613}, pdf = {https://ieeexplore.ieee.org/abstract/document/8735549} }
An algorithmic decision-maker incentivizes people to act in certain ways to receive better decisions. These incentives can dramatically influence subjects’ behaviors and lives, and it is important that both decision-makers and decision-recipients have clarity on which actions are incentivized by the chosen model. While for linear functions, the changes a subject is incentivized to make may be clear, we prove that for many non-linear functions (e.g. neural networks, random forests), classical methods for interpreting the behavior of models (e.g. input gradients) provide poor advice to individuals on which actions they should take. In this work, we propose a mathematical framework for understanding algorithmic incentives as the challenge of solving a Markov Decision Process, where the state includes the set of input features, and the reward is a function of the model’s output. We can then leverage the many toolkits for solving MDPs (e.g. tree-based planning, reinforcement learning) to identify the optimal actions each individual is incentivized to take to improve their decision under a given model. We demonstrate the utility of our method by estimating the maximally-incentivized actions in two real-world settings: a recidivism risk predictor we train using ProPublica’s COMPAS dataset, and an online credit scoring tool published by the Fair Isaac Corporation (FICO)
@inproceedings{shavit2019extracting, title = {Extracting Incentives from Black-Box Decisions}, shortname = {NeurIPS AI in FS}, author = {Shavit, Yonadav and Moses, William S.}, year = {2019}, booktitle = {2019 NeurIPS Workshop on AI in Financial Services}, pdf = {https://arxiv.org/pdf/1910.05664.pdf}, papertype = {workshop}, tex = {https://github.com/wsmoses/Paper-IncentiveNeuripsFinancial}, overleaf = {https://www.overleaf.com/project/5d76a1cf13500f0001f9999d} }
Deep learning frameworks automate the deployment, distribution, synchronization, memory allocation, and hardware acceleration of models represented as graphs of computational operators. These operators wrap high-performance libraries such as cuDNN or NNPACK. When the computation does not match any predefined library call, custom operators must be implemented, often at high engineering cost and performance penalty, limiting the pace of innovation. To address this productivity gap, we propose and evaluate: (1) a domain-specific language with a tensor notation close to the mathematics of deep learning; (2) a Just-InTime optimizing compiler based on the polyhedral framework; (3) carefully coordinated linear optimization and evolutionary algorithms to synthesize high-performance CUDA kernels; (4) the transparent integration of our flow into PyTorch and Caffe2, providing the fully automatic synthesis of high-performance GPU kernels from simple tensor algebra. The performance is comparable to, and often exceeds the performance of, highly tuned libraries.
@article{Vasilache:2019:NAL:3366460.3355606, author = {Vasilache, Nicolas and Zinenko, Oleksandr and Theodoridis, Theodoros and Goyal, Priya and Devito, Zachary and Moses, William S. and Verdoolaege, Sven and Adams, Andrew and Cohen, Albert}, booktitle = {Architecture and Code Optimization (TACO)}, shortname = {TACO}, title = {The Next 700 Accelerated Layers: From Mathematical Expressions of Network Computation Graphs to Accelerated {GPU} Kernels, Automatically}, journal = {ACM Trans. Archit. Code Optim.}, issue_date = {October 2019}, volume = {16}, number = {4}, month = oct, year = {2019}, issn = {1544-3566}, pages = {38:1--38:26}, articleno = {38}, numpages = {26}, url = {http://doi.acm.org/10.1145/3355606}, doi = {10.1145/3355606}, acmid = {3355606}, publisher = {ACM}, address = {New York, NY, USA}, keywords = {Deep learning layers, GPU acceleration, polyhedral compilation}, pdf = {https://c.wsmoses.com/papers/tc-taco.pdf}, papertype = {journal}, tex = {https://github.com/wsmoses/Paper-TCTACO} }
Deterministic software transactional memory (STM) is a useful programming model for writing parallel codes, as it improves programmability (by supporting transactions) and debuggability (by supporting determinism). This paper presents LiTM, a new deterministic STM system that achieves both simplicity and efficiency at the same time. LiTM implements the deterministic reservations framework of Blelloch et al., but without requiring the programmer to understand the internals of the algorithm. Instead, the programmer writes the program in a transactional fashion and LiTM manages all data conflicts and automatically achieves deterministic parallelism. Our experiments on six benchmarks show that LiTM outperforms the state-of-the-art framework Galois by up to 5.8x on a 40-core machine
@inproceedings{xia2019litm, title = { {LiTM}: A Lightweight Deterministic Software Transactional Memory System}, author = {Xia, Yu and Yu, Xiangyao and Moses, William and Shun, Julian and Devadas, Srinivas}, booktitle = {Proceedings of the 10th International Workshop on Programming Models and Applications for Multicores and Manycores}, shortname = {PPoPP PMAMM '19}, pages = {1--10}, year = {2019}, organization = {ACM}, pdf = {https://c.wsmoses.com/papers/litm.pdf}, papertype = {workshop} }
Tapir (pronounced TAY-per) is a compiler intermediate representation (IR) that embeds recursive fork-join parallelism, as supported by task-parallel programming platforms such as Cilk and OpenMP, into a mainstream compiler’s IR. Mainstream compilers typically treat parallel linguistic constructs as syntactic sugar for function calls into a parallel runtime. These calls prevent the compiler from performing optimizations on and across parallel control constructs. Remedying this situation has generally been thought to require an extensive reworking of compiler analyses and code transformations to handle parallel semantics. Tapir leverages the “serial-projection property,” which is commonly satisfied by task-parallel programs, to handle the semantics of these programs without an extensive rework of the compiler.For recursive fork-join programs that satisfy the serial-projection property, Tapir enables effective compiler optimization of parallel programs with only minor changes to existing compiler analyses and code transformations. Tapir uses the serial-projection property to order logically parallel fine-grained tasks in the program’s control-flow graph. This ordered representation of parallel tasks allows the compiler to optimize parallel codes effectively with only minor modifications. For example, to implement Tapir/LLVM, a prototype of Tapir in the LLVM compiler, we added or modified less than 3,000 lines of LLVM’s half-million-line core middle-end functionality.These changes sufficed to enable LLVM’s existing compiler optimizations for serial code—including loop-invariant-code motion, common-subexpression elimination, and tail-recursion elimination—to work with parallel control constructs such as parallel loops and Cilk’s Cilk_Spawn keyword. Tapir also supports parallel optimizations, such as loop scheduling, which restructure the parallel control flow of the program. By making use of existing LLVM optimizations and new parallel optimizations, Tapir/LLVM can optimize recursive fork-join programs more effectively than traditional compilation methods. On a suite of 35 Cilk application benchmarks, Tapir/LLVM produces more efficient executables for 30 benchmarks, with faster 18-core running times for 26 of them, compared to a nearly identical compiler that compiles parallel linguistic constructs the traditional way.
@article{tapirTOPC, author = {Schardl, Tao B. and Moses, William S. and Leiserson, Charles E.}, title = {Tapir: Embedding Recursive Fork-Join Parallelism into {LLVM}'s Intermediate Representation}, year = {2019}, pdf = {https://dl.acm.org/doi/10.1145/3365655}, shortname = {TOPC}, issue_date = {December 2019}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, volume = {6}, number = {4}, issn = {2329-4949}, url = {https://doi.org/10.1145/3365655}, doi = {10.1145/3365655}, journal = {ACM Trans. Parallel Comput.}, month = dec, articleno = {19}, numpages = {33}, keywords = {parallel computing, control-flow graph, OpenMP, fork-join parallelism, optimization, compiling, LLVM, multicore, serial-projection property, Tapir, Cilk}, papertype = {journal} }
Deep learning models with convolutional and recurrent networks are now ubiquitous and analyze massive amounts of audio, image, video, text and graph data, with applications in automatic translation, speech-to-text, scene understanding, ranking user preferences, ad placement, etc. Competing frameworks for building these networks such as TensorFlow, Chainer, CNTK, Torch/PyTorch, Caffe1/2, MXNet and Theano, explore different tradeoffs between usability and expressiveness, research or production orientation and supported hardware. They operate on a DAG of computational operators, wrapping high-performance libraries such as CUDNN (for NVIDIA GPUs) or NNPACK (for various CPUs), and automate memory allocation, synchronization, distribution. Custom operators are needed where the computation does not fit existing high-performance library calls, usually at a high engineering cost. This is frequently required when new operators are invented by researchers: such operators suffer a severe performance penalty, which limits the pace of innovation. Furthermore, even if there is an existing runtime call these frameworks can use, it often does not offer optimal performance for a user’s particular network architecture and dataset, missing optimizations between operators as well as optimizations that can be done knowing the size and shape of data. Our contributions include (1) a language close to the mathematics of deep learning called Tensor Comprehensions, (2) a polyhedral Just-In-Time compiler to convert a mathematical description of a deep learning DAG into a CUDA kernel with delegated memory management and synchronization, also providing optimizations such as operator fusion and specialization for specific sizes, (3) a compilation cache populated by an autotuner. In particular, we demonstrate the suitability of the polyhedral framework to construct a domain-specific optimizer effective on state-of-the-art deep learning models on GPUs. Our flow reaches up to 4× speedup over NVIDIA libraries on kernels relevant to the Machine Learning Community, and on an actual model used in production at Facebook. It is integrated with mainstream frameworks Caffe2 (production-oriented), PyTorch (research-oriented), through the ATen asynchronous tensor library.
@article{tc, title = {Tensor Comprehensions: Framework-Agnostic High-Performance Machine Learning Abstractions}, booktitle = {arXiv preprint}, shortname = {arXiv}, author = {Vasilache, Nicolas and Zinenko, Oleksandr and Theodoridis, Theodoros and Goyal, Priya and DeVito, Zachary and Moses, William S and Verdoolaege, Sven and Adams, Andrew and Cohen, Albert}, journal = {arXiv preprint arXiv:1802.04730}, year = {2018}, reddit = {http://www.reddit.com/r/MachineLearning/comments/7xjqq9/r_announcing_tensor_comprehensions/}, hackernews = {http://news.ycombinator.com/item?id=16377389}, pdf = {https://arxiv.org/pdf/1802.04730.pdf}, papertype = {preprint} }
Optimizing compilers for task-level parallelism are still in their infancy. This work explores a compiler front end that translates OpenMP tasking semantics to Tapir, an extension to LLVM IR that represents fork-join parallelism. This enables analyses and optimizations that were previously inaccessible to OpenMP codes, as well as the ability to target additional runtimes at code generation. Using a Cilk runtime back end, we compare results to existing OpenMP implementations. Initial performance results for the Barcelona OpenMP task suite show performance improvements over existing implementations.
@inproceedings{openmpir, author = {Stelle, George and Moses, William S. and Olivier, Stephen L. and McCormick, Patrick}, title = { {OpenMPIR}: Implementing OpenMP Tasks with Tapir}, booktitle = {Proceedings of the Fourth Workshop on the LLVM Compiler Infrastructure in HPC}, shortname = {LLVM-HPC'17}, year = {2017}, isbn = {978-1-4503-5565-0}, location = {Denver, CO, USA}, pages = {3:1--3:12}, articleno = {3}, numpages = {12}, url = {http://doi.acm.org/10.1145/3148173.3148186}, doi = {10.1145/3148173.3148186}, acmid = {3148186}, publisher = {ACM}, address = {New York, NY, USA}, pdf = {https://c.wsmoses.com/papers/openmpir.pdf}, papertype = {workshop}, tex = {https://github.com/lanl/openmpir-llvm2017} }
This paper explores how fork-join parallelism, as supported by concurrency platforms such as Cilk and OpenMP, can be embedded into a compiler’s intermediate representation (IR). Mainstream compilers typically treat parallel linguistic constructs as syntactic sugar for function calls into a parallel runtime. These calls prevent the compiler from performing optimizations across parallel control constructs. Remedying this situation is generally thought to require an extensive reworking of compiler analyses and code transformations to handle parallel semantics. Tapir is a compiler IR that represents logically parallel tasks asymmetrically in the program’s control flow graph. Tapir allows the compiler to optimize across parallel control constructs with only minor changes to its existing analyses and code transformations. To prototype Tapir in the LLVM compiler, for example, we added or modified about 6000 lines of LLVM’s 4-million-line codebase. Tapir enables LLVM’s existing compiler optimizations for serial code – including loop-invariant-code motion, common-subexpression elimination, and tail-recursion elimination – to work with parallel control constructs such as spawning and parallel loops. Tapir also supports parallel optimizations such as loop scheduling.
@inproceedings{tapir, author = {Schardl, Tao B. and Moses, William S. and Leiserson, Charles E.}, title = {Tapir: Embedding Fork-Join Parallelism into {LLVM}'s Intermediate Representation}, booktitle = {Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming}, shortname = {PPoPP '17}, month = jan, year = {2017}, isbn = {978-1-4503-4493-7}, location = {Austin, Texas, USA}, pages = {249--265}, numpages = {17}, pdf = {https://c.wsmoses.com/papers/tapir.pdf}, doi = {10.1145/3018743.3018758}, acmid = {3018758}, publisher = {ACM}, address = {New York, NY, USA}, award = {Best Paper Award}, reddit = {http://www.reddit.com/r/programming/comments/5ra59l/mit_says_their_modified_llvm_compiler_optimizes/}, mitnews = {http://news.mit.edu/2017/optimizing-code-compiler-parallel-programs-0130}, hackernews = {http://news.ycombinator.com/item?id=13568585}, blog = {/tapir}, papertype = {conference} }
This thesis explores how fork-join parallelism, as supported by concurrency platforms such as Cilk and OpenMP, can be embedded into a compiler’s intermediate representation (IR). Mainstream compilers typically treat parallel linguistic constructs as syntactic sugar for function calls into a parallel runtime. These calls prevent the compiler from performing optimizations across parallel control constructs. Remedying this situation is generally thought to require an extensive reworking of compiler analyses and code transformations to handle parallel semantics. Tapir is a compiler IR that represents logically parallel tasks asymmetrically in the program’s control flow graph. Tapir allows the compiler to optimize across parallel control constructs with only minor changes to its existing analyses and code transformations. To prototype Tapir in the LLVM compiler, for example, the Tapir team added or modi- fied about 6000 lines of LLVM’s 4-million-line codebase. Tapir enables LLVM’s existing compiler optimizations for serial code — including loop-invariant-code motion, commonsubexpression elimination, and tail-recursion elimination — to work with parallel control constructs such as spawning and parallel loops. Tapir also supports parallel optimizations such as loop scheduling.
@mastersthesis{wmoses-meng, title = {How {S}hould {C}ompilers {R}epresent {F}ork-{J}oin {P}arallelism?}, author = {Moses, William S.}, booktitle = {Master's Thesis}, shortname = {Thesis '17}, school = {Massachusetts Institute of Technology}, year = {2017}, month = may, pdf = {https://c.wsmoses.com/papers/wmoses-meng.pdf}, blog = {/tapir}, papertype = {thesis}, overleaf = {https://www.overleaf.com/project/58fceac4b55260d42f75e8c3}, tex = {https://github.com/wsmoses/Paper-MEng} }
@inproceedings{tapirCPC, title = {Embedding Fork-Join Parallelism into LLVM IR}, author = {Moses, William S. and Schardl, Tao B. and Leiserson, Charles E.}, booktitle = {19th Workshop on Compilers for Parallel Computing}, year = {2016}, shortname = {CQC '16}, pdf = {https://cpc2016.infor.uva.es/wp-content/uploads/2016/06/CPC2016_paper_12.pdf}, papertype = {workshop} }
Music has long been an interesting subject of analysis for mathematicians and has led to many interesting questions in music theory and other fields. For the most part, computer scientists have looked into applying artificial intelligence to music and finding algorithms and data structures to solve various problems in music. Prior work on these algorithms often involves computing various properties of music such as the edit distance between two songs or the optimal fingering. These problems tend to be solvable in polynomial time using dynamic programming and have various application such as the music identification service Shazam or operations on RISM, an online music database. This paper takes an additional step in this direction, asking what sorts of problems in music cannot be efficiently computed. Specifically, this paper asks how various constraints affect the computational complexity of arranging music originally written for one set of instruments down to a single instrument. The paper then applies these results to other domains including musical choreography (such as ice skating and ballet) as well as creating levels for rhythm games (such as Rock Band). We prove that all of the problems are NP-complete, meaning that there is no efficient algorithm to solve them (assuming the standard conjecture that P != NP).
@incollection{moves15, author = {Demaine, Erik D. and Moses, William S.}, title = {Computational Complexity of Arranging Music}, booktitle = {Revised Papers from MOVES 2015: Mathematics of Various Entertaining Subjects}, shortname = {MOVES '15}, publisher = {Princeton University Press}, year = {2015}, pdf = {https://c.wsmoses.com/papers/moves15.pdf}, papertype = {book}, overleaf = {https://www.overleaf.com/project/54f60a71728bff850ed36c73}, tex = {https://github.com/wsmoses/Paper-MOVES15} }
@inproceedings{spacex15, title = {Extreme Multi-Resolution Visualization: A Challenge on Many Levels}, author = {Balme, Joanna and Brown-Dymkoski, Eric and Guerrero, Victor and Jones, Stephen and Kessler, Andre and Lichtl, Adam and Lung, Kevin and Moses, William and Museth, Ken and Roberson, Nathan and others}, booktitle = {SuperComputing Visualization Contest 2015}, shortname = {SCVis '15}, year = {2015}, pdf = {https://c.wsmoses.com/papers/spacex15.pdf}, papertype = {workshop} }
Adaptive frequency hopping is one way to maximize the utilization of the wireless spectrum. Yet, when the environment itself is changing, the frequency at which the radio senses can become increasingly less optimal. By having the radio create a model of the environment based off of the sensing data, it is possible to achieve high data rates when the spectrum is not being heavily utilized and maintain a low level of interference at times when it is. The radio was modeled both mathematically and run in simulations. The outcomes of these tests were compared with existing standards such as Bluetooth (random frequency hopping) and IEEE 802.22 (fixed sensing rate). In order to evaluate data rate and interference simultaneously, a metric was created that combined them by taking the product of data rate and ( 1 - interference ). Overall, the online adaptive frequency hopper had a 35% increase in the combined metric over the random frequency hopper and 25% increase over the fixed sensing rate radio.
@misc{oafh, title = {Online Adaptive Frequency Hopping}, author = {Moses, William and Robertson, Andrew and Dell, John}, booktitle = {TJHSST Teknos 2014}, shortname = {TJHSST '14}, year = {2014}, pdf = {https://c.wsmoses.com/papers/oafh.pdf}, papertype = {report} }