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.

News

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!

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

Instructor:
Sasa Misailovic
Assistant Professor, CS UIUC
4110 Siebel Center misailo@illinois.edu

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

Overview

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)	Sasa Slides
8/25	Probability Review	Sasa Slides	*Language:* webppl.org *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)	Sasa Slides	*Additional Materials:* Probabilistic Models of Cognition (online book)
9/1	Probabilistic Programming (2)	Sasa Slides	*Additional Materials:* Bayesian Reasoning and Machine Learning (online book)
9/6	Probabilistic Semantics and Inference Bayesian inference using data flow analysis (FSE 2013)	Sasa Slides Submit Review
9/8	Probabilistic Symbolic Analysis (1) Probabilistic Symbolic Execution (ISSTA 2012)	Farah 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)	Wei 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	Abdulrahman 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)	August 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)	Sasa Slides	*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)	Sasa
9/29	Domain Specific Languages Tabular: A Schema-Driven Probabilistic Programming Language (POPL 2014)	Daejun 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)	Sasa Slides	*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)	Radha 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)	Deniz 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)	Subho 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	Doris 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)	Vimuth 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)	Sasa 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)	Santiago
11/10	Approximation and Systems (2) ApproxHadoop: Bringing Approximations to MapReduce Frameworks (ASPLOS 2015)	Atul
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/24	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	All
12/6	Student Projects	All

Resources

Probabilistic Programming

probabilistic-programming.org -- a collection of various resources about probabilistic programming languages
ForestDB -- A database of generative models (typically written in Church)
The Design and Implementation of Probabilistic Programming Languages (online book)

Approximate Computing

Benchmark Suites:

Workshops:

Dagstuhl Seminars:

Approximate and Probabilistic Computing: Design, Coding, Verification

Approximate And Probabilistic Computing Across the System Stack