Approximate And Probabilistic Computing
Across the System Stack

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 representing uncertainty 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.



    9/20/2016: Please write down a paragraph about you current project plan by Sunday (9/25).

  • 8/31/2016: The paper assignments are out!

  • Location: Siebel Center, room 1302

  • 8/20/2016: The website is up!


 Tuesday/Thursday 2-3:15 pm
 Siebel Center, 1302

 Sasa Misailovic
 Assistant Professor, CS UIUC
 4110 Siebel Center

 Office Hours:
 4110 Siebel Center
 Tuesday/Thrusday 3:15-4 pm


This is a reasearch-oriented course. It will include lectures, reading research papers, in-class discussions, and a final research project. We will compute the final grade using the following table:

Activity Grade Details
Miniquizzes 10%
  • At the beginning of each lecture; five minutes long.
  • Can skip 5 without penalty; each additional decreases the grade by 0.5%.
Reviews and Discussion 15%
  • Summary and review of the paper, up to 500 words. See the first lecture slides for format.
  • 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 25%
  • Select at least five papers you would like to present by this Sunday (8/28):
    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 topics with Sasa.
  • Presentation (5-10 minutes): beginning of December.
  • Report (5 pages): beginning of December.

More details: Course Logistics Slides.


Tentative Schedule  

Date Topic Presenter Notes
8/23 Introduction
Background Read: J. von Neumann. Probabilistic logics and synthesis of reliable organisms from unreliable components (Automata Studies, 1956)
8/25 Probability Review Sasa
Additional Materials:
OpenIntro Stats (online book)
8/28 Submit Top Paper Choices: Link
8/30 Probabilistic Programming (1)
Background Read: Probabilistic Programming (ICSE/FoSE 2014)
Additional Materials:
Probabilistic Models of Cognition (online book)
9/1 Probabilistic Programming (2) Sasa
Additional Materials:
Bayesian Reasoning and Machine Learning (online book)
9/6 Probabilistic Semantics and Inference
Bayesian inference using data flow analysis (FSE 2013)
Slides Submit Review

9/8 Probabilistic Symbolic Analysis (1)
Probabilistic Symbolic Execution (ISSTA 2012)
Submit Review
Additional Read:
Reliability Analysis in Symbolic Pathfinder (ICSE 2013)
9/13 Probabilistic Symbolic Analysis (2)
Static Analysis for Probabilistic Programs: Inferring Whole Program Properties from Finitely Many Paths (PLDI 2013)
Submit Review
Additional Read:
Dynamic Enforcement of Knowledge-Based Security Policies (CSF 2011)
9/15 Probabilistic Models of Uncertainty
Uncertain<T>: A First-Order Type for Uncertain Data (ASPLOS 2014)
Background Read: SPR test
Code: SPRT test implementation in WebPPL
Submit Review
Additional Reads:
Expressing and Verifying Probabilistic Assertions (PLDI 2014)
A Probabilistic Language based upon Sampling Functions (POPL 2005)
9/20 Optimizing Probabilistic Programs
Slicing Probabilistic Programs (PLDI 2014)
Background Reads: Denotational Semantics (On-line Book), SSA Form (CS 526 materials), Bayes Ball rules (Stanford Graph Models class)
Submit Review
Additional Read: R2: An Efficient MCMC Sampler for Probabilistic Programs (AAAI 2014)
9/22 Probabilistic Program Verification (1)
Reference: Abstraction, Refinement and Proof for Probabilistic Systems (Ch.1, Ch.2)
Additional Materials:
Probabilistic Programming: A True Verification Challenge
9/27 Probabilistic Program Verification (2)
Conditioning in Probabilistic Programming (Electronic Notes In Theoretical Computer Science, 2015)
9/29 Domain Specific Languages
Tabular: A Schema-Driven Probabilistic Programming Language (POPL 2014)
Submit Review
Additional Read: Measure Transformer Semantics for Bayesian Machine Learning (ESOP 2011)
10/4 Approximate Computing Trends in Software
Background Read: Loop Perforation (paper 1, paper 2, paper 3)
Additional Materials:
Approximate and Probabilistic Computing: Design, Coding, Verification
10/6 Approximate Transformations (1)
Green: A Framework for Supporting Energy-Conscious Programming using Controlled Approximation (PLDI 2010)
Submit Review
Additional Read: Dynamic Knobs for Responsive Power-Aware Computing (ASPLOS 2011)
10/7 Submit Project Proposal (1 page)
10/11 Approximate Transformations (2)
Image Perforation: Automatically Accelerating Image Pipelines by Intelligently Skipping Samples (SIGGRAPH 2016)
Submit Review
Additional Read: Input responsiveness: using canary inputs to dynamically steer approximation (PLDI 2016)
10/13 Approximation Accuracy: Probabilistic
BlinkDB: queries with bounded errors and bounded response times on very large data (EuroSys 2013)
Submit Review
Additional Read: Randomized Accuracy-Aware Program Transformations For Efficient Approximate Computations (POPL 2012)
10/18 Approximation Accuracy: Numerical
Spark: Cluster Computing with Working Sets
and MLlib: Machine Learning in Apache Spark
Submit Review
Additional Read: Declarative Machine Learning – A Classification of Basic Properties and Types
10/20 Approximation Safety
EnerJ: Approximate Data Types for Safe and General Low-Power Computation (PLDI 2011)
Submit Review
Additional Read: Proving Acceptability Properties of Relaxed Nondeterministic Approximate Programs (PLDI 2012)
10/25 Approximation and Reliability
Chisel: Reliability- and Accuracy-Aware Optimization of Approximate Computational Kernels (OOPSLA 2014)
Submit Review
Additional Read: Verifying Quantitative Reliability for Programs That Execute on Unreliable Hardware (OOPSLA 2013)
10/27 Resiliency-oriented Algorithms
Markov chain algorithms: a template for building future robust low-power systems (Philosophical Transactions of Royal Society, 2013)
Elizabeth Additional Read: Belief Propagation Algorithms on Noisy Hardware (IEEE Transactions on Communications, 2014)
11/1 Radha will give a talk on Approxilyzer (MICRO 2016).
11/3 OOPSLA (no class)
11/8 Approximation and Systems (1)
HELIX-UP: relaxing program semantics to unleash parallelization (CGO 2015)
11/10 Approximation and Systems (2)
ApproxHadoop: Bringing Approximations to MapReduce Frameworks (ASPLOS 2015)
11/15 Approximate Architectures (1)
ERSA: Error Resilient System Architecture for Probabilistic Applications (IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2012)
Saurabh Additional Read: Probabilistic System-on-a-chip Architectures (ACM Transactions on Design Automation of Electronic Systems, 2007)
11/17 Approximate Architectures (2)
Neural Acceleration for General-Purpose Approximate Programs (MICRO 2012)
Khalique Additional Read: Building fast Bayesian computing machines out of intentionally stochastic, digital parts (Arxiv, 2014)
11/22 Thanksgiving (no class)
11/29 Approximate Memories
Flikker: Saving DRAM Refresh-power through Critical Data Partitioning (ASPLOS 2011)
Suleman Additional Read: Approximate Storage in Solid-State Memories (MICRO 2013)
12/1 Student Projects
12/6 Student Projects


Probabilistic Programming

Approximate Computing

Benchmark Suites: Workshops: Dagstuhl Seminars: