# Research

## Programming Languages

If you were told that the world would be destroyed tomorrow and that you could transmit a 50 some characters of knowledge to the future, what would you choose? I would choose Lambda Calculus. If you don't know what that is and if you are a student of Computer Science and Mathematics, you must start learning about it now. So go do it. Then come back and enjoy the papers below, which are inspired by it.

Efficient and Scalable Parallel Functional Programming through Disentanglement

PhD Thesis. 2022.

Sam Westrick

Provably Space-Efficient Parallel Functional Programming.

ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). 2021.

Jatin Arora, Sam Westrick, Umut A. Acar.

*(Distinguished Paper Award.)*

Task Parallel Assembly Language for Uncompromising Parallelism.

ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2021.

Mike Rainey, Ryan Newton, Kyle Hale, Nikos Hardavellas, Simone Campanoni, Peter Dinda, Umut A. Acar.

Responsive Parallelism with Futures and State

ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2020.

Stefan Muller, Kyle Singer, Noah Goldstein, Umut A. Acar, Kunal Agrawal, I-Ting Angelina Lee

Disentanglement in Nested-Parallel Programs.

ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). 2020.

Sam Westrick, Rohan Yadav, Matthew Fluet, Umut A. Acar.

Program equivalence for assisted grading of functional programs.

ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA). 2020.

Joshua Clune, Vijay Ramamurthy, Ruben Martins, Umut A. Acar

Provably and Practically Efficient Granularity Control.

ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP). 2019.

Umut A. Acar, Vitaly Aksenov, Arthur Chargueraud, Mike Rainey.

*(SIGPLAN Research Highlight")*

Fairness in Responsive Parallelism.

ACM International Conference on Functional Programming (ICFP). 2019.

Stefan K. Muller, Sam Westrick, Umut A. Acar

Disentanglement, Theory and Practice

Rohan Yadav. B.S. Thesis. 2019.

Zeus: Algorithmic Program Equivalence

Vijay Ramamurthy. B.S. Thesis. 2019

Competitive Parallelism: Getting your Priorities Right.

ACM International Conference on Functional Programming (ICFP). 2018.

Full paper on ArXiV.

Stefan K. Muller, Umut A. Acar, Robert Harper.

Heartbeat Scheduling: Provable Efficiency for Nested Parallelism.

ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2018.

Umut A. Acar, Arthur CharguĂ©raud, Adrien Guatto, Mike Rainey, Filip Sieczkowski.

Hierarchical Memory Management for Mutable State.

ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP). 2018.

Full paper on ArXiV.

Adrien Guatto, Sam Westrick, Ram Raghunathan, Umut A. Acar, Matthew Fluet.

Poster: Performance Challenges in Modular Parallel Programs.

ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP). 2018

Umut A. Acar, Vitaly Aksenov, Arthur Chargueraud, Mike Rainey.

Responsive Parallel Computation.

Stefan Muller. Ph.D. Thesis. 2018.

Responsive Parallel Computation: Bridging Competitive and Cooperative Threading.

ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2017.

Stefan K. Muller, Umut A. Acar, Robert Harper.

ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP). 2017.

Full version. Carnegie Mellon University. Technical Report CMU-CS-16-133.

Umut A. Acar, Naama Ben-David, Mike Rainey.

Parallel Work Inflation, Memory Effects, and their Empirical Analysis.

ArXiv Manuscript 1709.03767. 2017.

Umut A. Acar, Arthur Chargueraud, and Mike Rainey.

Oracle-Guided Scheduling for Controlling Granularity in Implicitly Parallel Languages.

Journal of Functional Programming Special Issue on Parallel Computing (JFP). 2016.

Umut A. Acar, Arthur Chargueraud, and Mike Rainey.

(Invited paper.)

Dag-Calculus: A Calculus for Parallel Computation

ACM International Conference on Functional Programming (ICFP). 2016.

Umut A. Acar, Arthur Chargueraud, Mike Rainey, Filip Sieczkowski.

Hierarchical Memory Management for Parallel Programs.

ACM International Conference on Functional Programming (ICFP). 2016.

Ram Raghunathan, Stefan K. Muller, Umut A. Acar, and Guy Blelloch.

Automatically Splitting a Two-Stage Lambda Calculus.

European Symposium on Programming (ESOP). 2016.

Nicolas Feltman, Kayvon Fatahalian, Umut A. Acar, and Carlo Angiuli.

A Work-Efficient Algorithm for Parallel Unordered Depth-First Search.

ACM/IEEE Conference on High Performance Computing (SC). 2015.

Umut A. Acar, Arthur Chargueraud, Mike Rainey.

iThreads: A Threading Library for Parallel Incremental Computation.

International Conference on Architectural Support for Programming Languages and Operating System (ASPLOS). 2015.

Pramod Bhatotia, Pedro Fonseca, Umut A. Acar, Bjoern B. Brandenburg, Rodrigo Rodrigues.

Refinement Types for Incremental Computation Complexity.

European Symposium on Programming (ESOP). 2015.

Ezgi Cicek, Deepak Garg, Umut A. Acar.

Bridging Theory and Practice in Interaction.

Summit on Advances in Programming Languages (SNAPL). 2015.

Stefan Muller and Umut A. Acar.

Coupling Memory and Computation for Locality Management.

Summit on Advances in Programming Languages (SNAPL). 2015.

Umut A. Acar, Guy Blelloch, Matthew Fluet, Stefan Muller, Ram Raghunathan.

Practical and Safe Abstractions for Interactive Computation via Linearity.

Technical Report. CMU-CS-15-130.

Stefan K. Muller, William A. Duff, Umut A. Acar.

Practical Abstractions for Concurrent Interactive Programming.

Technical Report. CMU-CS-15-131.

Stefan K. Muller, William A. Duff, Umut A. Acar.

Implicit Self-Adjusting Computation for Purely Functional Programs.

Journal of Functional Programming (JFP). 2014.

Yan Chen, Joshua Dunfield, Matthew Hammer, Umut A. Acar.

Functional Programming for Dynamic and Large Data with Self-Adjusting Computation.

International Conference on Functional Programming (ICFP). 2014.

Yan Chen, Umut A. Acar, and Kanat Tangwongsan.

Database Queries that Explain their Work.

International Symposium on Principles and Practice of Declarative Programming (PPDP). 2014.

James Cheney, Amal Ahmed, Umut A. Acar. 2014.

A core calculus of provenance.

Journal of Computer Security (JCS). 2013.

Special Issue for the First Conference on Principles of Security and Trust.

Umut A. Acar, Amal Ahmed, James Cheney, and Roly Perera.

(Invited paper.)

A consistent semantics of self-adjusting computation

Journal of Functional Programming (JFP). 2013.

The complete Twelf proof: as a text file, and as a tar ball.

Umut A. Acar, Matthias Blume, Jake Donham.

Scheduling Parallel Programs by Work Stealing with Private Deques

ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP). 2013.

Umut A. Acar, Arthur Chargueraud, and Mike Rainey.

Towards a Theory of Self-Explaining Computation.

Lecture Notes in Computer Science, LNCS Volume 8000. 2013.

James Cheney, Umut A. Acar, and Roly Perera.

Language Support for Efficient Dynamic Computation.

Off the Beaten Track Workshop. 2013.

Umut A. Acar, Ezgi Cicek, Deepak Garg.

Streaming Big Data with Self-Adjusting Computation.

Workshop on Data Driven Functional Programming. 2013.

Umut A. Acar and Yan Chen.

Type Directed Automatic Incrementalization.

Programming Language Design and Implementation (PLDI) 2012.

Yan Chen, Joshua Dunfield, Umut A. Acar.

Functional Programs that Explain their Work

International Conference on Functional Programming (ICFP). 2012.

Full version (Technical Report).

Roly Perera, Umut A. Acar, James Cheney, Paul Blain Levy.

Non-Monotonic Self-Adjusting Computation.

European Symposium on Programming (ESOP) 2012.

Ruy Ley-Wild, Umut A. Acar, Guy E. Blelloch.

A Core Calculus of Provenance.

Conference on Principles of Security and Trust (POST) 2012.

Umut A. Acar, Amal Ahmed, James Cheney, Roly Perera.

Primitives for Creating and Scheduling Parallel Computations.

ACM Workshop on Deterministic Aspects of Multicore Programming (DAMP). 2012.

Umut A. Acar, Arthur Chargueraud, Mike Rainey.

Ph.D. Thesis. University of Chicago. 2012.

Matthew Hammer.

Kinetic Mesh Refinement in 2D.

ACM Symposium on Computational Geometry (SCG). 2011.

Umut A. Acar, Benoit Hudson, Duru Turkoglu.

Implicit Self-Adjusting Computation for Purely Functional Programs.

International Conference on Functional Programming (ICFP). 2011.

Yan Chen, Joshua Dunfield, Matthew Hammer, Umut A. Acar.

Oracle Scheduling: Controlling Granularity in Implicitly Parallel Languages.

ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA). 2011.

Umut A. Acar, Arthur Chargueraud, Mike Rainey.

Self-Adjusting Stack Machines.

ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA). 2011.

Matthew Hammer, Georg Neis, Yan Chen, Umut A. Acar.

Provenance as Dependency Analysis.

Mathematical Structures in Computer Science (MSCS), 21(06).

Special Issue on Programming Language Interference and Dependence. 2011.

James Cheney, Amal Ahmed, and Umut A. Acar.

Implementing implicit self-adjusting computation.

ACM SIGPLAN Workshop on ML. 2011.

Yan Chen, Joshua Dunfield, Matthew A. Hammer, Umut A. Acar.

Traceable Data Types for Self-Adjusting Computation.

ACM-SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2010.

Umut A. Acar, Guy E. Blelloch, Ruy Ley-Wild, Kanat Tangwongsan, and Duru Turkoglu.

Programmable Self-Adjusting Computation

Ph.D. Thesis. Carnegie Mellon University Technical Report.

CMU-CS-10-146. 2010.

Ruy Ley-Wild.

An Experimental Analysis of Self-Adjusting Computation.

ACM Transactions on Programming Languages and Systems (TOPLAS). 2009.

Umut A. Acar, Guy E. Blelloch, Matthias Blume, Robert Harper, and Kanat Tangwongsan.

CEAL: A C-Based Language for Self-Adjusting Computation.

ACM-SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2009.

Full version. Toyota Technological Institute Technical Report.

Matthew Hammer, Umut A. Acar, and Yan Chen.

A Cost Semantics for Self-Adjusting Computation.

ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). 2009.

Full version. Carnegie Mellon University Technical Report.

Ruy Ley-Wild, Umut A. Acar, and Matthew Fluet.

Workshop on Declarative Aspects of Multicore Programming (DAMP). 2009.

Lukasz Ziarek, Suresh Jagannathan, Matthew Fluet, and Umut A. Acar.

Self-Adjusting Computation (An Overview).

Plenary Talk at ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM). 2009.

Umut A. Acar.

Imperative Self-Adjusting Computation.

ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). 2008.

Full version. University of Chicago Technical Report 2007-18.

Umut A. Acar, Amal Ahmed, and Matthias Blume.

Compiling Self-Adjusting Programs with Continuations.

International Conference on Functional Programming (ICFP). 2008.

Ruy Ley-Wild, Matthew Fluet, and Umut A. Acar.

Memory Management for Self-Adjusting Computation.

International Symposium on Memory Management (ISMM). 2008.

Matthew Hammer and Umut A. Acar.

Exception Handlers as Extensible Cases.

Proceedings of the Sixth ASIAN Symposium on Programming Languages and Systems (APLAS). 2008.

Matthias Blume, Umut A. Acar, and Wonseok Chae.

Self-Adjusting Computation in Delta ML.

Notes for Advanced Functional Programming Summer School (AFP) Lectures. 2008.

Umut A. Acar and Ruy Ley-Wild.

arXiv:0812.0564v1. 2008.

James Cheney, Umut Acar, Amal Ahmed.

A Consistent Semantics of Self-Adjusting Computation.

European Symposium on Programming (ESOP). 2007.

Full version. Carnegie Mellon University. Technical Report CMU-CS-06-168.

Umut A. Acar, Matthias Blume, and Jacob Donham.

Provenance as Dependency Analysis.

International Symposium on Database Programming Languages (DBPL). 2007.

James Cheney, Amal Ahmed, and Umut A. Acar.

A Proposal for Parallel Self-Adjusting Computation.

Workshop on Declarative Aspects of Multicore Programming (DAMP). 2007.

Matthew Hammer, Umut A. Acar, Mohan Rajagopalan, and Anwar Ghuloum.

Adaptive Functional Programming.

ACM Transactions on Programming Languages and Systems (TOPLAS). 2006.

Umut A. Acar, Guy E. Blelloch, and Robert Harper.

An Experimental Analysis of Self-Adjusting Computation.

ACM-SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2006.

Umut A. Acar, Guy E. Blelloch, Matthias Blume, and Kanat Tangwongsan.

Extensible Programming with First-Class Cases.

International Conference on Functional Programming (ICFP). 2006.

Matthias Blume, Umut A. Acar, and Wonseok Chae.

Optimal-Time Dynamic Mesh Refinement: Preliminary Results.

Fall Workshop on Computational Geometry. 2006.

Umut A. Acar and Benoit Hudson.

A Library for Self-Adjusting Computation.

ACM-SIGPLAN Workshop on ML. 2005.

Also in Electronic Notes in Theoretical Computer Science (ENTCS). 148 (2).

Umut A. Acar, Guy E. Blelloch, Matthias Blume, Robert Harper, and Kanat Tangwongsan.

PhD. Thesis. 2005.

Umut A. Acar.

Dynamizing Static Algorithms with Applications to Dynamic Trees and History Independence.

ACM-SIAM Symposium on Discrete Algorithms (SODA). 2005.

Umut A. Acar, Guy E. Blelloch, Robert Harper, Maverick Woo, and Jorge Vittes.

ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). 2003.

Full version. Carnegie Mellon University. Technical Report CMU-CS-04-155.

Umut A. Acar, Guy E. Blelloch, and Robert Harper.

Adaptive Functional Programming.

ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). 2002.

Umut A. Acar, Guy E. Blelloch, and Robert Harper

## Parallel Computing

Usually motivated by increased parallelism in hardware and computing systems, parallelism research may be viewed as a natural evolution or computer science research. Maybe: my view is that sequential computing is merely a stunted phase in the history of computing. Concretely put, sequential computing is P = 1, and is therefore a fundamentally uninteresting "edge case". Parallelism however is a hard problem. The fundamental problem is that with parallelism, the gap between an algorithm and the program implementing the algorithm is too big to leave it as an "exercise to the reader" or the practicing programmer. Solving this problem will therefore likely require bringing together the two computationally equivalent but decidedly distinct theories of computing, by Church and Turing. This is what we do in our work. It addition to its relatively broad theoretical foundation, the work is also realized on modern hardware and languages including in Parallel ML and C/C++.

The MaPLe compiler for Parallel ML

Efficient and Scalable Parallel Functional Programming through Disentanglement

PhD Thesis. 2022.

Sam Westrick

Provably Space-Efficient Parallel Functional Programming.

ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). 2021.

Jatin Arora, Sam Westrick, Umut A. Acar.

*(Distinguished Paper Award.)*

Task Parallel Assembly Language for Uncompromising Parallelism.

ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2021.

Mike Rainey, Ryan Newton, Kyle Hale, Nikos Hardavellas, Simone Campanoni, Peter Dinda, Umut A. Acar.

Responsive Parallelism with Futures and State

ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2020.

Stefan Muller, Kyle Singer, Noah Goldstein, Umut A. Acar, Kunal Agrawal, I-Ting Angelina Lee

Priority Scheduling for Interactive Applications.

ACM Symposium on Parallel Algorithms and Architectures (SPAA). 2020.

Kyle Singer, Noah Goldstein, Stefan Muller, Kunal Agrawal, I-Ting Lee, Umut A. Acar.

Parallel Batch-Dynamic Trees via Change Propagation.

European Symposium on Algorithms (ESA). 2020.

Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, Sam Westrick.

Disentanglement in Nested-Parallel Programs.

ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). 2020.

Sam Westrick, Rohan Yadav, Matthew Fluet, Umut A. Acar

Provably and Practically Efficient Granularity Control.

ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP). 2019.

Umut A. Acar, Vitaly Aksenov, Arthur Chargueraud, Mike Rainey.

*(SIGPLAN Research Highlight")*

Fairness in Responsive Parallelism.

ACM International Conference on Functional Programming (ICFP). 2019.

Stefan K. Muller, Sam Westrick, Umut A. Acar

Parallel Batch-Dynamic Graph Connectivity.

ACM Symposium on Parallel Algorithms and Architectures (SPAA). 2019.

Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala.

Brief Announcement: Work Efficient Parallel Graph Isomorphism.

ACM Symposium on Parallel Algorithms and Architectures (SPAA). 2019.

Rohan Yadav, Umut A. Acar.

Disentanglement, Theory and Practice

Rohan Yadav. B.S. Thesis. 2019.

Heartbeat Scheduling: Provable Efficiency for Nested Parallelism.

ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2018.

Umut A. Acar, Arthur CharguĂ©raud, Adrien Guatto, Mike Rainey, Filip Sieczkowski.

Hierarchical Memory Management for Mutable State.

ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP). 2018.

Full paper on ArXiV.

Adrien Guatto, Sam Westrick, Ram Raghunathan, Umut A. Acar, Matthew Fluet.

Poster: Performance Challenges in Modular Parallel Programs.

ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP). 2018

Umut A. Acar, Vitaly Aksenov, Arthur Chargueraud, Mike Rainey.

Responsive Parallel Computation.

Stefan Muller. Ph.D. Thesis. 2018.

Competitive Parallelism: Getting your Priorities Right.

ACM International Conference on Functional Programming (ICFP). 2018.

Full paper on ArXiV.

Stefan K. Muller, Umut A. Acar, Robert Harper.

Hierarchical Memory Management for Mutable State.

ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP). 2018.

Full paper on ArXiV.

Adrien Guatto, Sam Westrick, Ram Raghunathan, Umut A. Acar, Matthew Fluet.

Responsive Parallel Computation: Bridging Competitive and Cooperative Threading.

ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2017.

Stefan K. Muller, Umut A. Acar, Robert Harper.

ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP). 2017.

Full version. Carnegie Mellon University. Technical Report CMU-CS-16-133.

Umut A. Acar, Naama Ben-David, Mike Rainey.

Brief Announcement: Parallel Dynamic Tree Contraction via Self-Adjusting Computation.

ACM Symposium on Parallel Algorithms and Architectures (SPAA). 2017.

Umut A. Acar, Vitaly Aksenov, and Sam Westrick.

Parallel Work Inflation, Memory Effects, and their Empirical Analysis.

ArXiv Manuscript 1709.03767. 2017.

Umut A. Acar, Arthur Chargueraud, and Mike Rainey.

Oracle-Guided Scheduling for Controlling Granularity in Implicitly Parallel Languages.

Journal of Functional Programming Special Issue on Parallel Computing (JFP). 2016.

Umut A. Acar, Arthur Chargueraud, and Mike Rainey.

(Invited paper.)

ACM Symposium on Parallel Algorithms and Architectures (SPAA). 2016.

Stefan K. Muller and Umut A. Acar.

Dag-Calculus: A Calculus for Parallel Computation

ACM International Conference on Functional Programming (ICFP). 2016.

Umut A. Acar, Arthur Chargueraud, Mike Rainey, Filip Sieczkowski.

Hierarchical Memory Management for Parallel Programs.

ACM International Conference on Functional Programming (ICFP). 2016.

Ram Raghunathan, Stefan K. Muller, Umut A. Acar, and Guy Blelloch.

A Work-Efficient Algorithm for Parallel Unordered Depth-First Search.

ACM/IEEE Conference on High Performance Computing (SC). 2015.

Umut A. Acar, Arthur Chargueraud, Mike Rainey.

iThreads: A Threading Library for Parallel Incremental Computation.

International Conference on Architectural Support for Programming Languages and Operating System (ASPLOS). 2015.

Pramod Bhatotia, Pedro Fonseca, Umut A. Acar, Bjoern B. Brandenburg, Rodrigo Rodrigues.

Incremental Parallel and Distributed Systems

Ph.D. Thesis, 2015.

Pramod Bhatotia

Coupling Memory and Computation for Locality Management.

Summit on Advances in Programming Languages (SNAPL). 2015.

Umut A. Acar, Guy Blelloch, Matthew Fluet, Stefan Muller, Ram Raghunathan.

Scheduling Parallel Programs by Work Stealing with Private Deques

ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP). 2013.

Umut A. Acar, Arthur Chargueraud, and Mike Rainey.

Parallelism in Dynamic Well-Spaced Point Sets.

ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 2011.

Umut A. Acar, Andy Cotter, Benoit Hudson, Duru Turkoglu.

The Data Locality of Work Stealing.

Theory of Computing Systems 35(3) (TOCS). 2002.

Umut A. Acar, Guy E. Blelloch, and Robert D. Blumofe.

(Invited paper.)

The Data Locality of Work Stealing.

ACM Symposium on Parallel Algorithms and Architectures (SPAA). 2000.

Umut A. Acar, Guy E. Blelloch, and Robert D. Blumofe.

## Disentanglement

Disentanglement refers to a memory property of many parallel algorithms: computations are oblivious to the data created by other concurrent computations. This property is common and appears to be a fundamental one, probably because parallelism dictates some degree of separation. For example, all data-race-free programs, including purely functional programs, are disentangled. Many parallel programs with data races are also disentangled. Using disentanglement, it is possible to integrate scheduling and memory management to improve overall efficiency and performance of parallel programs. Fundamentally, disentanglement permits overcoming the challenges of communication costs that may appear inherent to parallelism. In this work, we study the theory and practice of disentanglement and apply it to develop a new compiler and run-time system for the Parallel ML language.

The MaPLe compiler for Parallel ML

Efficient and Scalable Parallel Functional Programming through Disentanglement

PhD Thesis. 2022.

Sam Westrick

Provably Space-Efficient Parallel Functional Programming.

ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). 2021.

Jatin Arora, Sam Westrick, Umut A. Acar.

*(Distinguished Paper Award.)*

Disentanglement in Nested-Parallel Programs.

ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). 2020.

Sam Westrick, Rohan Yadav, Matthew Fluet, Umut A. Acar

Disentanglement, Theory and Practice

Rohan Yadav. B.S. Thesis. 2019.

Hierarchical Memory Management for Mutable State.

ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP). 2018.

Full paper on ArXiV.

Adrien Guatto, Sam Westrick, Ram Raghunathan, Umut A. Acar, Matthew Fluet.

Hierarchical Memory Management for Parallel Programs.

ACM International Conference on Functional Programming (ICFP). 2016.

Ram Raghunathan, Stefan K. Muller, Umut A. Acar, and Guy Blelloch.

## Responsive Parallelism

Parallel computing research traditionally aims to minimize the run-time for a program by using multiple processors. This throughput oriented view permeates nearly all aspects of parallel computing, from the design of programming languages, schedulers, and run-time systems to their implementation. In reality, however, many parallel applications must ensure not just high throughput but also responsiveness. For example, an interactive application that serves user requests must guarantee that each request completes quickly. In this line of research, we develop programming languages, scheduling algorithms, and run-time systems for "responsive parallelism" that provides guarantees not only on throughput but also responsiveness.

Responsive Parallelism with Futures and State

ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2020.

Stefan Muller, Kyle Singer, Noah Goldstein, Umut A. Acar, Kunal Agrawal, I-Ting Angelina Lee

Priority Scheduling for Interactive Applications.

ACM Symposium on Parallel Algorithms and Architectures (SPAA). 2020.

Kyle Singer, Noah Goldstein, Stefan Muller, Kunal Agrawal, I-Ting Lee, Umut A. Acar.

Fairness in Responsive Parallelism.

ACM International Conference on Functional Programming (ICFP). 2019.

Stefan K. Muller, Sam Westrick, Umut A. Acar

Competitive Parallelism: Getting your Priorities Right.

ACM International Conference on Functional Programming (ICFP). 2018.

Full paper on ArXiV.

Stefan K. Muller, Umut A. Acar, Robert Harper.

Responsive Parallel Computation: Bridging Competitive and Cooperative Threading.

ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2017.

Stefan K. Muller, Umut A. Acar, Robert Harper.

ACM Symposium on Parallel Algorithms and Architectures (SPAA). 2016.

Stefan K. Muller and Umut A. Acar.

## Incremental and Self-Adjusting Computation

Incremental computation aims to take advantage of a property common to many data sets: they change slowly over time. For example, in a (social, road, cyber) network, the connections between the nodes of the network remain the same for long stretches of time, before they are altered. Such changes may be frequent, but they are usually small in relation to the size of the whole data set. Given this, we ought to be able to compute properties of interest as the data changes more efficiently compared to re-computing from scratch. In this research, we develop techniques to do this automatically. Given an algorithm or a piece of code that computes some property and a change, self-adjusting computation can compute the necessary updates automatically and efficiently, so efficiently in fact that it can compete with dynamic algorithms carefully designed by experts, and it can even help solve problem that remain difficult to solve otherwise. That all being said, this technique remains underutilized in practice, partly because it requires some infrastructure code, but its time will come (hopefully before all other bad ideas are exhausted). For example, Jane Street seems to be having success with it.

Efficient Parallel Self-Adjusting Computation.

ACM Symposium on Parallel Algorithms and Architectures (SPAA). 2021.

Daniel Anderson, Guy Blelloch, Anubhav Baweja, Umut A. Acar

Parallel Batch-Dynamic Trees via Change Propagation.

European Symposium on Algorithms (ESA). 2020.

Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, Sam Westrick.

Brief Announcement: Parallel Dynamic Tree Contraction via Self-Adjusting Computation.

ACM Symposium on Parallel Algorithms and Architectures (SPAA). 2017.

Umut A. Acar, Vitaly Aksenov, and Sam Westrick.

iThreads: A Threading Library for Parallel Incremental Computation.

International Conference on Architectural Support for Programming Languages and Operating System (ASPLOS). 2015.

Pramod Bhatotia, Pedro Fonseca, Umut A. Acar, Bjoern B. Brandenburg, Rodrigo Rodrigues.

Refinement Types for Incremental Computation Complexity.

European Symposium on Programming (ESOP). 2015.

Ezgi Cicek, Deepak Garg, Umut A. Acar.

Incremental Parallel and Distributed Systems

Ph.D. Thesis, 2015.

Pramod Bhatotia

Incoop: MapReduce for Incremental Computations.

Advances in data processing techniques in the era of Big Data. CRC Press.

Pramod Bhatotia, Alexander Wieder, Umut A. Acar, Rodrigo Rodrigues.

(Invited chapter.)

Implicit Self-Adjusting Computation for Purely Functional Programs.

Journal of Functional Programming (JFP). 2014.

Yan Chen, Joshua Dunfield, Matthew Hammer, Umut A. Acar.

Functional Programming for Dynamic and Large Data with Self-Adjusting Computation.

International Conference on Functional Programming (ICFP). 2014.

Yan Chen, Umut A. Acar, and Kanat Tangwongsan.

Slider: Incremental Sliding Window Analytics.

ACM/IFIP/Usenix Middleware. 2014.

Pramod Bhatotia, Umut A. Acar, Flavio P. Junqueira, Rodrigo Rodrigues.

A consistent semantics of self-adjusting computation

Journal of Functional Programming (JFP). 2013.

The complete Twelf proof: as a text file, and as a tar ball.

Umut A. Acar, Matthias Blume, Jake Donham.

Language Support for Efficient Dynamic Computation.

Off the Beaten Track Workshop. 2013.

Umut A. Acar, Ezgi Cicek, Deepak Garg.

Streaming Big Data with Self-Adjusting Computation.

Workshop on Data Driven Functional Programming. 2013.

Umut A. Acar and Yan Chen.

Dynamic well-spaced point sets.

Journal of Computational Geometry, Theory and Applications. 2013.

Umut A Acar, Andy Cotter, Benoit Hudson, Duru Turkoglu.

Type Directed Automatic Incrementalization.

Programming Language Design and Implementation (PLDI) 2012.

Yan Chen, Joshua Dunfield, Umut A. Acar.

Non-Monotonic Self-Adjusting Computation.

European Symposium on Programming (ESOP) 2012.

Ruy Ley-Wild, Umut A. Acar, Guy E. Blelloch.

Ph.D. Thesis. University of Chicago. 2012.

Matthew Hammer.

Stable Algorithms and Kinetic Mesh Refinement.

Ph.D. Thesis. University of Chicago. 2012.

Duru Turkoglu.

Incoop: MapReduce for Incremental Computations.

ACM Symposium on Cloud Computing (SoCC). 2011.

Pramod Bhatotia, Alexander Wieder, Rodrigo Rodrigues, Umut A. Acar, Rafael Pasquini.

(Also appears as an invited chapter in CRC Press' Big-Data Book.)

Parallelism in Dynamic Well-Spaced Point Sets.

ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 2011.

Umut A. Acar, Andy Cotter, Benoit Hudson, Duru Turkoglu.

Kinetic Mesh Refinement in 2D.

ACM Symposium on Computational Geometry (SCG). 2011.

Umut A. Acar, Benoit Hudson, Duru Turkoglu.

Implicit Self-Adjusting Computation for Purely Functional Programs.

International Conference on Functional Programming (ICFP). 2011.

Yan Chen, Joshua Dunfield, Matthew Hammer, Umut A. Acar.

Self-Adjusting Stack Machines.

ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA). 2011.

Matthew Hammer, Georg Neis, Yan Chen, Umut A. Acar.

Large-scale Incremental Data Processing with Change Propagation.

USENIX Workshop on Hot Topics in Cloud Computing (HotCloud). 2011.

Pramod Bhatotia, Alexander Wieder, Istemi Ekin Akkus, Rodrigo Rodrigues, Umut A. Acar.

Implementing implicit self-adjusting computation.

ACM SIGPLAN Workshop on ML. 2011.

Yan Chen, Joshua Dunfield, Matthew A. Hammer, Umut A. Acar.

Traceable Data Types for Self-Adjusting Computation.

ACM-SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2010.

Umut A. Acar, Guy E. Blelloch, Ruy Ley-Wild, Kanat Tangwongsan, and Duru Turkoglu.

Dynamic Well-Spaced Point Sets.

ACM Symposium on Computational Geometry (SCG). 2010.

Umut A. Acar, Andrew Cotter, Benoit Hudson, and Duru Turkoglu.

Kinetic Mesh Refinement in 2D.

Fall Workshop on Computational Geometry, 2010.

Umut A. Acar, Benoit Hudson, and Duru Turkoglu.

Programmable Self-Adjusting Computation

Ph.D. Thesis. Carnegie Mellon University Technical Report.

CMU-CS-10-146. 2010.

Ruy Ley-Wild.

An Experimental Analysis of Self-Adjusting Computation.

ACM Transactions on Programming Languages and Systems (TOPLAS). 2009.

Umut A. Acar, Guy E. Blelloch, Matthias Blume, Robert Harper, and Kanat Tangwongsan.

CEAL: A C-Based Language for Self-Adjusting Computation.

ACM-SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2009.

Full version. Toyota Technological Institute Technical Report.

Matthew Hammer, Umut A. Acar, and Yan Chen.

A Cost Semantics for Self-Adjusting Computation.

ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). 2009.

Full version. Carnegie Mellon University Technical Report.

Ruy Ley-Wild, Umut A. Acar, and Matthew Fluet.

Self-Adjusting Computation (An Overview).

Plenary Talk at ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM). 2009.

Umut A. Acar.

A Dynamic Algorithm for Well-Spaced Point Sets.

Fall Workshop on Computational Geometry. 2009.

Umut A. Acar, Benoit Hudson, and Duru Turkoglu.

Imperative Self-Adjusting Computation.

ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). 2008.

Full version. University of Chicago Technical Report 2007-18.

Umut A. Acar, Amal Ahmed, and Matthias Blume.

Compiling Self-Adjusting Programs with Continuations.

International Conference on Functional Programming (ICFP). 2008.

Ruy Ley-Wild, Matthew Fluet, and Umut A. Acar.

Adaptive Inference on General Graphical Models.

Uncertainty in Artificial Intelligence (UAI). 2008.

Umut A. Acar, Alexander T. Ihler, Ramgopal Mettu, Ozgur Sumer.

Memory Management for Self-Adjusting Computation.

International Symposium on Memory Management (ISMM). 2008.

Matthew Hammer and Umut A. Acar.

Robust Kinetic Convex Hulls in 3D.

European Symposium on Algorithms (ESA). 2008.

Umut A. Acar, Guy E. Blelloch, Kanat Tangwongsan, and Duru Turkoglu.

Self-Adjusting Computation in Delta ML.

Notes for Advanced Functional Programming Summer School (AFP) Lectures. 2008.

Umut A. Acar and Ruy Ley-Wild.

Conference on Neural Information Processing Systems (NIPS). 2007.

Umut A. Acar, Alexander T. Ihler, Ramgopal Mettu, Ozgur Sumer.

A Consistent Semantics of Self-Adjusting Computation.

European Symposium on Programming (ESOP). 2007.

Full version. Carnegie Mellon University. Technical Report CMU-CS-06-168.

Umut A. Acar, Matthias Blume, and Jacob Donham.

A Proposal for Parallel Self-Adjusting Computation.

Workshop on Declarative Aspects of Multicore Programming (DAMP). 2007.

Matthew Hammer, Umut A. Acar, Mohan Rajagopalan, and Anwar Ghuloum.

Kinetic 3D Convex Hulls via Self-Adjusting Computation (An Illustration).

ACM Symposium on Computational Geometry (SCG). 2007.

Umut A. Acar, Guy E. Blelloch, and Kanat Tangwongsan.

Adaptive Functional Programming.

ACM Transactions on Programming Languages and Systems (TOPLAS). 2006.

Umut A. Acar, Guy E. Blelloch, and Robert Harper.

An Experimental Analysis of Self-Adjusting Computation.

ACM-SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2006.

Umut A. Acar, Guy E. Blelloch, Matthias Blume, and Kanat Tangwongsan.

Kinetic Algorithms via Self-Adjusting Computation.

European Symposium on Algorithms (ESA). 2006.

Umut A. Acar, Guy E. Blelloch, and Kanat Tangwongsan.

An Experimental Analysis of Change Propagation in Dynamic Trees.

ACM-SIAM Workshop on Algorithm Engineering and Experiments (ALENEX). 2005.

Umut A. Acar, Guy E. Blelloch, Jorge Vittes.

A Library for Self-Adjusting Computation.

ACM-SIGPLAN Workshop on ML. 2005.

Also in Electronic Notes in Theoretical Computer Science (ENTCS). 148 (2).

Umut A. Acar, Guy E. Blelloch, Matthias Blume, Robert Harper, and Kanat Tangwongsan.

PhD. Thesis. 2005.

Umut A. Acar.

Dynamizing Static Algorithms with Applications to Dynamic Trees and History Independence.

ACM-SIAM Symposium on Discrete Algorithms (SODA). 2005.

Umut A. Acar, Guy E. Blelloch, Robert Harper, Maverick Woo, and Jorge Vittes.

ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). 2003.

Full version. Carnegie Mellon University. Technical Report CMU-CS-04-155.

Umut A. Acar, Guy E. Blelloch, and Robert Harper.

Adaptive Functional Programming.

ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). 2002.

Umut A. Acar, Guy E. Blelloch, and Robert Harper.

ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). 2003.

Full version. Carnegie Mellon University. Technical Report CMU-CS-04-155.

Umut A. Acar, Guy E. Blelloch, and Robert Harper.

Adaptive Functional Programming.

ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). 2002.

Umut A. Acar, Guy E. Blelloch, and Robert Harper.

## Dynamic Algorithms

Many real-world problems involve dynamically changing data sets (including both discrete and continuous changes, e.g., as in motion). In our work, we develop algorithms that operate efficiently on dynamically changing data. Such algorithms can be very complex, especially if they are to be used in practice. We therefore also develop and apply general principles that bestow algorithms the ability to "adapt" to change.

Efficient Parallel Self-Adjusting Computation.

ACM Symposium on Parallel Algorithms and Architectures (SPAA). 2021.

Daniel Anderson, Guy Blelloch, Anubhav Baweja, Umut A. Acar

Parallel Batch-Dynamic Graph Connectivity.

ACM Symposium on Parallel Algorithms and Architectures (SPAA). 2019.

Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala.

Brief Announcement: Parallel Dynamic Tree Contraction via Self-Adjusting Computation.

ACM Symposium on Parallel Algorithms and Architectures (SPAA). 2017.

Umut A. Acar, Vitaly Aksenov, and Sam Westrick.

Theory and Practice of Chunked Sequences.

European Symposium on Algorithms (ESA). 2014.

Umut A. Acar, Arthur Chargueraud, Mike Rainey.

Parallelism in Dynamic Well-Spaced Point Sets.

ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 2011.

Umut A. Acar, Andy Cotter, Benoit Hudson, Duru Turkoglu.

Kinetic Mesh Refinement in 2D.

ACM Symposium on Computational Geometry (SCG). 2011.

Umut A. Acar, Benoit Hudson, Duru Turkoglu.

Dynamic Well-Spaced Point Sets.

ACM Symposium on Computational Geometry (SCG). 2010.

Umut A. Acar, Andrew Cotter, Benoit Hudson, and Duru Turkoglu.

A Dynamic Algorithm for Well-Spaced Point Sets.

Fall Workshop on Computational Geometry. 2009.

Umut A. Acar, Benoit Hudson, and Duru Turkoglu.

Robust Kinetic Convex Hulls in 3D.

European Symposium on Algorithms (ESA). 2008.

Umut A. Acar, Guy E. Blelloch, Kanat Tangwongsan, and Duru Turkoglu.

An Experimental Analysis of Change Propagation in Dynamic Trees.

ACM-SIAM Workshop on Algorithm Engineering and Experiments (ALENEX). 2005.

Umut A. Acar, Guy E. Blelloch, Jorge Vittes.

Dynamizing Static Algorithms with Applications to Dynamic Trees and History Independence.

ACM-SIAM Symposium on Discrete Algorithms (SODA). 2005.

Umut A. Acar, Guy E. Blelloch, Robert Harper, Maverick Woo, and Jorge Vittes.

## Machine Learning

Adaptive Inference for Graphical Models.

Ph.D. Thesis. University of Chicago. 2012.

Ozgur Sumer.

Adaptive Exact Inference in Graphical Models.

Journal of Machine Learning Research (JMLR). 2011.

Ozgur Sumer, Umut A. Acar, Alexander Ihler, and Ramgopal Mettu.

Fast Parallel and Adaptive Updates for Dual-Decomposition Solvers.

Conference on Artificial Intelligence (AAAI).

Ozgur Sumer, Umut A. Acar, Alexander Ihler, Ramgopal Mettu.

Adaptive Updates for MAP Configurations with Applications to Bioinformatics.

IEEE/SP 15th Workshop on Statistical Signal Processing (SSP). 2009.

Umut A. Acar, Alexander T. Ihler, Ramgopal Mettu, Ozgur Sumer.

Adaptive Inference on General Graphical Models.

Uncertainty in Artificial Intelligence (UAI). 2008.

Umut A. Acar, Alexander T. Ihler, Ramgopal Mettu, Ozgur Sumer.

Conference on Neural Information Processing Systems (NIPS). 2007.

Umut A. Acar, Alexander T. Ihler, Ramgopal Mettu, Ozgur Sumer.

## Provenance

Functional Programs that Explain their Work

International Conference on Functional Programming (ICFP). 2012.

Full version (Technical Report).

Roly Perera, Umut A. Acar, James Cheney, Paul Blain Levy.

Non-Monotonic Self-Adjusting Computation.

European Symposium on Programming (ESOP) 2012.

Ruy Ley-Wild, Umut A. Acar, Guy E. Blelloch.

A Core Calculus of Provenance.

Conference on Principles of Security and Trust (POST) 2012.

Umut A. Acar, Amal Ahmed, James Cheney, Roly Perera.

Provenance as Dependency Analysis.

Mathematical Structures in Computer Science (MSCS), 21(06).

Special Issue on Programming Language Interference and Dependence. 2011.

James Cheney, Amal Ahmed, and Umut A. Acar.

A graph model of data and workflow provenance.

USENIX/ACM Workshop on the Theory and Practice of Provenance. 2010.

Umut Acar, Peter Buneman, James Cheney, Jan Van den Buscsche, Natalia Kwasnikowska, Stijn Vansummeren.

arXiv:0812.0564v1. 2008.

James Cheney, Umut Acar, Amal Ahmed.

Provenance as Dependency Analysis.

International Symposium on Database Programming Languages (DBPL). 2007.

James Cheney, Amal Ahmed, and Umut A. Acar.