Approximate And Probabilistic Computing Across the System Stack

Fall 2020 Edition

The current drive for energy-efficiency has made approximation a key concept in designing and implementing software in various areas, such as data analytics, mobile computing, multimedia processing, and engineering simulations. This course will focus on foundations and system-level techniques for processing for representing noise in program's data and reasoning about profitable tradeoffs between accuracy, reliability, and energy consumption. In addition to selected algorithmic-level approximations, we will study (i) programming languages that natively operate on probabilistic and/or uncertain data, (ii) compilers and programming systems that automatically approximate programs while verifying or testing the accuracy of optimized programs, and (iii) hardware devices that expose approximate components. In Fall 2020, our particular focus will be on the approximations and accuracy concerns of machine learning systems and techniques for checking correctness of randomized/probabilistic applications.

In Fall 2020, we will organize the class as a sequence of synchronous and asynchronous on-line activities. Our goal is to support every student, whether on-campus or off-campus (or even across the globe) through a flexible plan we will jointly develop. If you want to discuss your current concerns or situation, please feel free to email Sasa anytime.



  • 7/30/2020: The website is up!

 Mostly on-line

 Sasa Misailovic
 Assistant Professor
 Computer Science, UIUC
 4110 Siebel Center

 Office Hours:
 After class
 Mostly on-line


This is a research-oriented course. It will include lectures, reading research papers, in-class discussions, and a final research project. We plan to use a combination of Zoom for real-time lectures and recording of asynchronous presentations, Piazza for announcements, Q&A, etc., and Slack for quick chats. We will also experimentally try Gather for some optional social events. We will add the class-specific links soon.

We will compute the final grade using the following tentative table:

Activity Grade Details
Reviews and Discussion 20%
  • Summary and review of the paper, up to 500 words. See the first lecture slides for format.
  • Read entire primary paper and the introduction of the secondary paper (and more if you like it).
    The review form will ask for the relationship between the two.
  • Submission deadline is midnight the day before the class.
  • Can skip or submit late up to 3 without penalty; each additional decreases the grade by 1%.
Presentation and Discussion Lead 25%
  • Select at least five papers you would like to present by 9/10:
    Submission link
  • Schedule a meeting with Sasa a week before your presentation slot.
  • Submit the final version of the slides to Sasa 48 hours before the lecture.
Project 50%
  • Proposal (1 page): beginning of October. Feel free to discuss the topics with Sasa beforehand.
  • Presentation (5-10 minutes): beginning of December.
  • Report (5 pages): beginning of December.
Homework 5%
(+ 10% XC)
  • Will be given in the first few weeks of the course practice basics taught in lectures.
  • Submission deadline is 10am the next class.
  • Occasionally will give out optional homework for extra credit (XC).


Tentative Schedule  

We will first spend several weeks covering the key concepts of approximations in systems, accuracy management, and probabilistic programming. Then we will follow with studying recent research in approximation systems, systems and techniques for approximating deep learning, testing and analysis of machhine learning, probabilistic, and numerical programs, probabilistic programming systems, and probabilistic notions of system reliability.

Date Topic Presenter Notes


Background Read: Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms (CSUR 2020)
Fun Facts: J. von Neumann. Probabilistic logics and synthesis of reliable organisms from unreliable components (Automata Studies, 1956)

Approximations in Software Systems

Background Read: Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms (CSUR 2020)
Fun Facts: Computing, Approximately -- Ravi Nair's talk (WACI@ASPLOS 2008)

Approximations: Numerical Computations

Background Read: What Every Computer Scientist Should Know About Floating-Point Arithmetic (ACM 1991)
Additional Read: Towards a Compiler for Reals (TOPLAS 2017)
Software: Precimonious
Fun Facts: How Accurate is Scientific Software? (IEEE 1994)

Approximations: Machine Learning

Background Read: Neural Network Quantization Survey
Background Read: A Survey of Model Compression and Acceleration for Deep Neural Networks (IEEE Signal Processing Magazine, 2020)
Additional read: Tensorflow: A system for large-scale machine learning (OSDI 2016)
Software: Intel Distiller

Approximations: Non-deterministic

Background Read: Approximate Communication: Techniques for Reducing Communication Bottlenecks in Large-Scale Parallel Systems (CSUR 2018)
Background Read: Probabilistic CMOS Technology: A Survey and Future Directions (VLSI 2006)
Additional Materials: EnerJ: Approximate Data Types for Safe and General Low-Power Computation (PLDI 2011)
Additional Read: Unconventional Parallelization of Noneterministic Applications (ASPLOS 2018)
9/10 Submit Your Paper Choices: Link

Quality-Aware Optimization Systems

Background Read: Metaheuristics Book (Ch.1, Ch.2, Ch.3, Ch.7)
Additional Read: Evolutionary Algorithms for Solving Multi-Objective Problems (Ch.1)
Additional Read: Language and Compiler Support for Auto-TuningVariable-Accuracy Algorithms (CGO 2011)

Probabilistic Programming (1)

Background Read: Probabilistic Programming (ICSE/FoSE 2014)
Background Read: An Introduction to Probabilistic Programming
Additional Materials:
Probabilistic Models of Cognition (online book)

Probabilistic Programming (2)

Examples: Examples worked out in class
Background Read: PPAML Summer School 2016
Additional Materials:
Modeling Agents with Probabilistic Programs (online book)

Probabilistic Programming (3)

Background Read: Bayesian inference using data flow analysis (FSE 2013)
Additional Materials: The Design and Implementation of Probabilistic Programming Languages (online book)

Testing and Verifying Approximate, Nondeterministic, and Probabilistic Software

Background Read: TBD

Approximate Systems (1)

Primary Read: Managing Performance vs. Accuracy Trade-offs With Loop Perforation (FSE 2011)
Secondary Read: Best-Effort Parallel Execution Framework for Recognition and Mining Applications (IPDPS 2009)
Additional Materials: Using Code Perforation to Improve Performance, Reduce Energy Consumption, and Respond to Failures (2009)
Additional Materials: Green: A Framework for Supporting Energy-Conscious Programming using Controlled Approximation (PLDI 2010)

Approximate Systems (2)

Primary Read: Input responsiveness: using canary inputs to dynamically steer approximation (PLDI 2016)
Secondary Read: Crayon: Saving Power through Shape and Color Approximation on Next-Generation Displays (EuroSys 2016)
Additional Materials: Phase-Aware Optimization in Approximate Computing (CGO 2017)
Additional Materials: Image Perforation: Automatically Accelerating Image Pipelines by Intelligently Skipping Samples (SIGGRAPH 2016)

Approximate Systems (3)

Primary Read: Proactive control of approximate programs (ASPLOS 2016)
Secondary Read: JouleGuard: Energy Guarantees for Approximate Applications (SOSP 2015)
Additional Materials: Capri: A Control System for Approximate Programs
Additional Materials: Control Strategies for Self-Adaptive Software Systems (ACM TAAS 2017)

Approximate Systems (4)

Primary Read: Rigorous floating-point mixed-precision tuning (POPL 2017)
Secondary Read: Chisel: Reliability- and Accuracy-Aware Optimization of Approximate Computational Kernels (OOPSLA 2014)
Additional Read: Stochastic Optimization of Floating-Point Programs with Tunable Precision (PLDI 2014)
10/13 Submit Project Proposal (1-2 pages)

Accuracy-Aware DNN Inference

Primary Read: ApproxHPVM: A Portable Compiler IR for Accuracy-aware Optimizations (OOPSLA 2019)
Secondary Read: PerforatedCNNs: Acceleration through Elimination of Redundant Convolutions (NIPS 2016)
Additional Materials: Relay: A New IR for Machine Learning Frameworks (MAPL 2018) Fun Facts: Overparameterization: A Connection Between Software 1.0 and Software 2.0 (SNAPL 2019)

Pruning/Distilling in Neural Networks

Primary Read: Scalpel: Customizing DNN Pruning to the UnderlyingHardware Parallelism (ISCA 2017)
Secondary Read: ExTensor: An Accelerator for Sparse Tensor Algebra (MICRO 2019)
Additional Read: What is the state of Neural Network Prunnig? (MLSYS 2020)
Secondary Read: The Lottery Ticket Hypothesis: Finding Small, Trainable Neural Networks (ICLR 2019)

Quantization of Neural Networks

Primary Read: Deep Compression: Compressing Neural Networks With Pruning, Trained Quantization, and Huffman Coding (ICLR 2016)
Secondary Read: Quantized neural networks: training neural networks with low precision weights and activations (JMLR 2017)

Training DNNs in Low-Precision

Primary Read: Understanding and Optimizing Asynchronous Low-Precision Stochastic Gradient Descent (ISCA 2017)
Secondary Read: Highly Scalable Deep Learning Training System with Mixed-Precision: Training ImageNet in Four Minutes
Additional read: Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent (NIPS 2011)
Additional read: High-Accuracy Low-Precision Training

Testing: Deep Learning Applications

Primary Read: DeepXplore: automated whitebox testing of deep learning systems (SOSP 2017)
Secondary Read: Is Neuron Coverage a Meaningful Measure for Testing Deep Neural Networks? (FSE 2020)
Additional Read: DeepTest: Automated Testing of Deep-Neural-Network-driven Autonomous Cars (ICSE 2018)

Testing: Numerical Applications

Primary Read: A Comprehensive Study of Real-World Numerical Bug Characteristics (ASE 2017)
Secondary Read: Efficient Generation of Error-Inducing Floating-Point Inputs via Symbolic Execution (ICSE 2020)

Testing: Probabilistic Applications

Primary Read: Statistical Algorithmic Profiling for Randomized Approximate Programs (ICSE 2019)
Secondary Read: Testing Probabilistic Programming Systems (FSE 2018)
Additional Read: Detecting Flaky Tests in Probabilistic and Machine Learning Applications (ISSTA 2020)

Probabilistic Programming Systems (1)

Primary Read: Design and Implementation of Probabilistic Programming Language Anglican (IFL 2016)
Secondary Read: Stan: A Probabilistic Programming Language (Journal of Probabilistic Programming)
Background Read: Continuation Passing Style Notes (from CS 421)
Additional Materials: The Design and Implementation of Probabilistic Programming Languages (online book)

Probabilistic Programming Systems (2)

Primary Read: Compiling Markov Chain Monte Carlo Algorithms for Probabilistic Modeling (PLDI 2017)
Secondary Read: AcMC 2: Accelerating Markov Chain Monte Carlo Algorithms for Probabilistic Models (ASPLOS 2019)
Additional Read: FlexGibbs: Reconfigurable Parallel Gibbs Sampling Accelerator for Structured Graphs (FCCM 2019)

Probabilistic Programming Systems (3)

Primary Read: Gen: a general-purpose probabilistic programming system with programmable inference
Secondary Read: Pyro: Deep Universal Probabilistic Programming (JMLR 2018)
Additional Read: Deep Probabilistic Programming Languages: A Qualitative Study

Probabilistic Programming Systems (4)

Primary Read: R2: An Efficient MCMC Sampler for Probabilistic Programs (AAAI 2014)
Secondary Read: Probabilistic Programming with Densities in SlicStan: Efficient, Flexible and Deterministic (POPL 2019)
Additional Read: A Theory of Slicing for Probabilistic Control Flow Graphs (FoSSaCS 2016)


Thanksgiving (no class)

Application of Probabilistic Analysis 1

Primary Read: Static Analysis for Probabilistic Programs: Inferring Whole Program Properties from Finitely Many Paths (PLDI 2013)
Secondary Read: PMAF: an algebraic framework for static analysis of probabilistic programs (PLDI 2018)

Application of Probabilistic Analysis 2

Primary Read: Verifying Quantitative Reliability for Programs that Execute on Unreliable Hardware (OOPSLA 2013)
Secondary Read: Approxilyzer: Towards A Systematic Framework forInstruction-Level Approximate Computing and itsApplication to Hardware Resiliency (MICRO 2016)
Additional Materials: Borgerson and Freitas. A reliability model for gracefully degrading and standby-sparing systems (IEEE Trans. on Computers 1975)

Student Project Presentations



Probabilistic Programming

Benchmark Suites:
  • ForestDB -- A database of generative models (typically written in Church)
  • StanExamples -- a collection of diverse Stan models
Community: (Our) Tools:
  • Probfuzz -- A framework for testing probabilistic programming systems
  • PSense -- A framework for symbolic sensitivity analysis of probabilistic programs
  • PSI -- A symbolic solver for probabilistic programs

Approximate Computing

Benchmark Suites: Community: Dagstuhl Seminars: Tools:
  • OpenTuner -- autotuning framework, with accuracy choice
  • Accept -- optimization framework with multiple approximations
  • AxProf -- framework for testing approximate randomized applications