I think hard about abstractions that help programmers easily express complex problems yet are sufficiently constrained such that we can build runtimes to efficiently implement those abstractions. Broadly speaking, I build abstractions and runtimes for (i) probabilistic programming and approximate computing and (ii) parallel programming.
- Probabilistic Programming in General Purpose Programs:
Applications that sense and reason about the complexity of the world use estimates. Mobile phone applications estimate location with GPS sensors, search estimates information needs from search terms, machine learning estimates hidden parameters from data, and approximate hardware estimates precise hardware to improve energy efficiency. The difference between an estimate and its true value is uncertainty. This work builds novel tools and runtimes to help developers reason about uncertain data. Uncertain<T> is a generic type which lifts operations on T to distributions over T. Its abstractions are designed to help novice developers incorporate, compute, and reason about uncertain data in their programs without requiring a PhD degree in statistics. Likewise, probabilistic assertions let programmers specify quality constraints in programs as probabilistic correctness properties and our runtime and compiler efficiently verifies whether those probabilistic assertions are likely to hold.
- Data Parallel Finite State Machines and Dynamic Programming:
Hardware is parallel. While desktops, tablets, and even phones have vector instructions, multiple cores, and GPUs, many important algorithms are unable to exploit all of this parallelism. In this work, we introduce convergence, a new method for breaking data dependencies in loops and demonstrate how it makes FSMs and a class of dynamic programming algorithms data parallel. We frame both FSMs and dynamic programming algorithms as the repeated application of matrix-vector and matrix-matrix products in an appropriate semring. Convergence is an empirical property of repeated matrix-matrix products wherein the rank of the resulting matrix after a small sequence of matrix-matrix products tends to be small. Our results demonstrate multi-factor speedups on data parallel hardware.
- Veselin Raychev, Madanlal Musuvathi, and Todd Mytkowicz, Parallelizing User-Defined Aggregations using Symbolic Execution, USENIX – Advanced Computing Systems Association, October 2015.
- Yufei Ding, Yue Zhao, Xipeng Shen, Madanlal Musuvathi, and Todd Mytkowicz, Yinyang K-Means: A Drop-In Replacement of the Classic K-Means with Consistent Speedup, in Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, July 2015.
- Yufei Ding, Xipeng Shen, Madanlal Musuvathi, and Todd Mytkowicz, TOP: A Framework for Enabling Algorithmic Optimizations for Distance-Related Problems, in PVLDB, vol. 8, no. 10, pp. 1046–1057, June 2015.
- James Bornholt, Todd Mytkowicz, and Kathryn S. McKinley, Uncertain<T>: Abstractions for Uncertain Hardware and Software, in IEEE MICRO Top Picks, 35(3):132--143, IEEE – Institute of Electrical and Electronics Engineers, May 2015.
- James Bornholt, Na Meng, Todd Mytkowicz, and Kathryn S. McKinley, Programming the Internet of Uncertain <T>hings, in Sensors to Cloud Architectures Workshop (SCAW), pp. 1--7, ACM – Association for Computing Machinery, February 2015.
- Margus Veanes, Todd Mytkowicz, David Molnar, and Benjamin Livshits, Data-Parallel String-Manipulating Programs, in POPL 2015: 42nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM – Association for Computing Machinery, January 2015.
- Benjamin Livshits and Todd Mytkowicz, Saving Money While Polling with InterPoll using Power Analysis, AAAI - Association for the Advancement of Artificial Intelligence, 2 November 2014.
- Adrian Sampson, Pavel Panchekha, Todd Mytkowicz, Kathryn S. McKinley, Dan Grossman, and Luis Ceze, Expressing and Verifying Probabilistic Assertions, in ACM Conference on Programming Languages and Implementation (PLDI), pp. 112-122, ACM – Association for Computing Machinery, June 2014.
- Benjamin Livshits and Todd Mytkowicz, Saving Money While Polling with InterPoll using Power Analysis, no. MSR-TR-2014-50, 15 April 2014.
- Todd Mytkowicz, Madanlal Musuvathi, and Wolfram Schulte, Data-Parallel Finite-State Machines, Architectural Support for Programming Languages and Operating Systems (ASPLOS), March 2014.
- James Bornholt, Todd Mytkowicz, and Kathryn S. McKinley, Uncertain<T>: A First-Order Type for Uncertain Data, in ACM International Conference on Architectural Support for Programming Languages and Systems (ASPLOS), pp. 51-66, Selected for ACM SIGPLAN Research Highlight 2014, and IEEE MICRO Top Picks 2015, ACM – Association for Computing Machinery, March 2014.
- Saeed Maleki, Madanlal Musuvathi, and Todd Mytkowicz, Parallelizing Dynamic Programming Through Rank Convergence, ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), February 2014.
- Benjamin Livshits and Todd Mytkowicz, InterPoll: Crowd-Sourced Internet Polls (Done Right), no. MSR-TR-2014-3, 7 January 2014.
- Aman Kansal, Scott Saponas, AJ Brush, Kathryn McKinley, Todd Mytkowicz, and Ryder Ziola, The Latency, Accuracy, and Battery (LAB) Abstraction: Programmer Productivity and Energy Efficiency for Continuous Mobile Context Sensing, in OOPSLA, ACM, 31 October 2013.
- Bin Ren, Gagan Agrawal, James R. Larus, Todd Mytkowicz, Tomi Poutanen, and Wolfram Schulte, SIMD parallelization of applications that traverse irregular data structures, in Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization (CGO), vol. 0, pp. 1-10, IEEE Computer Society, Los Alamitos, CA, USA, 2013.
- James Bornholt, Todd Mytkowicz, and Kathryn S. McKinley, The Model is Not Enough-Understanding Energy Consumption in Mobile Devices, Hot Chips, August 2012.
- Todd Mytkowicz and Wolfram Schulte, Maine: A Library for Data Parallel Finite Automata, no. MSR-TR-2012-62, July 2012.
- Todd Mytkowicz and Wolfram Schulte, Waiting for Godot: The Right Language Abstractions for Parallel Programming Should be Here Soon, no. MSR-TR-2012-63, July 2012.
- Margus Veanes, David Molnar, Todd Mytkowicz, and Benjamin Livshits, Data-Parallel String-Manipulating Programs, no. MSR-TR-2012-72, July 2012.
- Todd Mytkowicz and Mark Marron, Single-Core Performance is Still Relevant in the Multi-Core Era, in PLDI FIT, ACM, June 2011.
- Leo A. Meyerovich, Todd Mytkowicz, and Wolfram Schulte, Data Parallel Programming for Irregular Tree Computations, in HotPAR, USENIX, May 2011.