Approximate And Probabilistic Computing Across the System Stack

Fall 2019 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 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/4/2019: The paper signup is available here

  • 8/26/2019: Piazza is set up! (link)

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


 Lectures:
 Tuesday/Thursday
 11:00am-12:15pm
 Siebel Center, 1304

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

 Office Hours:
 After class
 4110 Siebel Center

Overview  

This is a research-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.
  • 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 20%
  • 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  


Date Topic Presenter Notes
8/27

Introduction

Background Read: Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms 		Sasa
Slides
8/29

Approximations in Software and Hardware (1)

Background Read: J. von Neumann. Probabilistic logics and synthesis of reliable organisms from unreliable components (Automata Studies, 1956)
Sasa
Slides		 Fun Facts: Computing, Approximately -- Ravi Nair's talk (WACI@ASPLOS 2008)
9/3

Approximations in Software and Hardware (2)

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) 		Sasa
Slides
9/5

Numerical Approximations

Background Read: Towards a Compiler for Reals (TOPLAS 2017)
Background Read: Neural Network Quantization Survey 		Sasa
Slides		 Additional Materials: What Every Computer Scientist Should Know About Floating-Point Arithmetic (ACM 1991)
Software: Intel Distiller, Precimonious
Fun Facts: How Accurate is Scientific Software? (IEEE 1994)
9/10 Submit Your Paper Choices: Link
9/10

Randomized Approximations

Background Read: Sketching Data Lecture notes 		Sasa
Slides 		Additional Materials:
Mining of Massive Datasets (on-line book)
SPR test, Concentration inequalities
SPR test implementation in WebPPL
9/12

Probabilistic Programming (1)

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

Probabilistic Programming (2)

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

Probabilistic Programming (3)

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

Approximate Software Systems (1)

Primary Read: Green: A Framework for Supporting Energy-Conscious Programming using Controlled Approximation (PLDI 2010)
Secondary Read: Using Code Perforation to Improve Performance, Reduce Energy Consumption, and Respond to Failures (2009)
 Sasa
Submit
Review		 Additional Materials: Best-Effort Parallel Execution Framework for Recognition and Mining Applications (IPDPS 2009)
Additional Materials: EnerJ: Approximate Data Types for Safe and General Low-Power Computation (PLDI 2011)
9/26

Approximate Software Systems (2)

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

Approximate Software Systems (3)

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)
 Ziang
Submit
Review 		Additional Materials: Phase-Aware Optimization in Approximate Computing (CGO 2017)
Additional Materials: Image Perforation: Automatically Accelerating Image Pipelines by Intelligently Skipping Samples (SIGGRAPH 2016)
10/3 Submit Project Proposal (1-2 pages)
10/3

Approximation Tuning (1)

Primary Read: Rigorous floating-point mixed-precision tuning (POPL 2017)
Secondary Read: Stochastic Optimization of Floating-Point Programs with Tunable Precision (PLDI 2014)
  		Yifan
Submit
Review
10/8

Approximation Tuning (2)

Primary Read: Verifying Quantitative Reliability for Programs that Execute on Unreliable Hardware (OOPSLA 2013)
Secondary Read: Chisel: Reliability- and Accuracy-Aware Optimization of Approximate Computational Kernels (OOPSLA 2014)
 Sasa Additional Materials: Borgerson and Freitas. A reliability model for gracefully degrading and standby-sparing systems (IEEE Trans. on Computers 1975)
10/10

Hardware Approximations (1)

Primary Read: Lax: Driver Interfaces for Approximate Sensor Device Access (HotOS 2015)
Primary Read: Warp: A Hardware Platform for Efficient Multi-Modal Sensing with Adaptive Approximation (IEEE Micro 2019)
Secondary Read: ERSA: error resilient system architecture for probabilistic applications (DATE 2010)
 Rutvik Additional Materials: Towards full-system energy-accuracy tradeoffs: A case study of an approximate smart camera system (DAC 2017)
10/15

Hardware Approximations (2)

Primary Read: RFVP: Rollback-Free Value Prediction with Safe-to-Approximate Loads (ACM TACO 2016)
Secondary Read: Load Value Approximation (MICRO 2014) 		Keyur Additional Materials: Approximate Cache Architectures (book chapter)
10/17 TBD
10/22 TBD
10/24 TBD
10/29

Approximate Machine Learning (1)

Primary Read: Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent (NIPS 2011)
Secondary Read: Tensorflow: A system for large-scale machine learning (OSDI 2016)
 Linyi Fun Facts: Overparameterization: A Connection Between Software 1.0 and Software 2.0 (SNAPL 2019)
Additional read: PerforatedCNNs: Acceleration through Eliminationof Redundant Convolutions (NIPS 2016)
10/31

Approximate Machine Learning (2)

Primary Read: Project Adam: Building an Efficient and Scalable Deep Learning Training System (OSDI 2014)
Secondary Read: Unconventional Parallelization of Noneterministic Applications (ASPLOS 2018)
 Jiyong
11/5

Approximate Machine Learning (3)

Primary Read: TVM: An Automated End-to-End Optimizing Compiler for Deep Learning (OSDI 2018)
Secondary Read: Backpropagation with Callbacks: Foundations for Efficient and Expressive Differentiable Programming (NeurIPS 2018)
 Hashim Additional Materials: Relay: A New IR for Machine Learning Frameworks (MAPL 2018)
11/7

Probabilistic Programming Systems (1)

Primary Read: Deep Probabilistic Programming Languages: A Qualitative Study
Secondary Read: Pyro: Deep Universal Probabilistic Programming (JMLR 2018)
Secondary Read: Deep Probabilistic Programming (ICLR 2017)
 Hussein
11/12

Probabilistic Programming Systems (2)

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

Probabilistic Programming Systems (3)

Primary Read: Gen: a general-purpose probabilistic programming system with programmable inference
Secondary Read: Compiling Markov Chain Monte Carlo Algorithms for Probabilistic Modeling (PLDI 2017)
 Saikat
11/19

Hardware for Probabilistic Inference

Primary Read: AcMC 2 : Accelerating Markov Chain Monte Carlo Algorithms for Probabilistic Models (ASPLOS 2019)
Secondary Read: FlexGibbs: Reconfigurable Parallel Gibbs Sampling Accelerator for Structured Graphs (FCCM 2019)
 TBD
11/21

Probabilistic Analysis (1)

Primary Read: Fine-Grained Semantics for Probabilistic Programs (ESOP 2018)
Secondary Read: Semantics for probabilistic programming: higher-order functions, continuous distributions, and soft constraints (LICS 2016)
 TBD Additional Materials: A Denotational Semantics for Nondeterminism in Probabilistic Programs (MFPS 2019)
11/26
Thanksgiving (no class)
11/28
12/3

Probabilistic Analysis (2)

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

Probabilistic Analysis (3)

Primary Read: Probabilistic Programming with Densities in SlicStan: Efficient, Flexible and Deterministic (POPL 2019)
Secondary Read: A Theory of Slicing for Probabilistic Control Flow Graphs (FoSSaCS 2016)
 Sasa
12/10

Student Projects


 All
 

Resources  


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
-