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. NEW: We have set up the Piazza, which contains the Zoom link for lectures!

 

News  

  • 9/20/2020: NEW: We posted several probabilistic programming examples here.

  • 9/15/2020: The paper leads have been assigned.

  • 9/8/2020: Fill in the paper preference survey

  • 8/24/2020: We have set up the Piazza. You should be able to see the Zoom for lectures there!

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


 Lectures:
 Tuesday/Thursday
 11:00am-12:15pm
 Mostly on-line

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

 Office Hours:
 After class
 Mostly on-line

Overview  

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, HotCRP for paper reviewing and discussion, Piazza for announcements, Q&A, etc., and Slack for quick in-class 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, 500-1000 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 on Sunday (for Tuesday papers) and Tuesday (for Thursday papers).
  • Can skip or submit late up to 3 without penalty; each additional decreases the grade by 1%.
  • Discuss the paper on the on-line reviewing platform and in the class.
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 approximate applications, probabilistic programming systems, and probabilistic techniques for system reliability.

Date Topic Presenter Notes
8/25

Introduction

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

Approximations in Software Systems

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

Approximations: Numerical Computations

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

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)
Sasa
Slides
Additional read: Tensorflow: A system for large-scale machine learning (OSDI 2016)
Additional read: Demystifying Parallel and Distributed Deep Learning: An In-depth Concurrency Analysis (ACM CSUR 2019)
Software: Intel Distiller
9/8

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)
Sasa
Slides
Additional Read: EnerJ: Approximate Data Types for Safe and General Low-Power Computation (PLDI 2011)
Additional Read: Unconventional Parallelization of Noneterministic Applications (ASPLOS 2018)
9/10

Quality-Aware Optimization Systems (1)

Background Read: Metaheuristics Book (Ch.1, Ch.2, Ch.3, Ch.7)
Sasa
Slides
Additional Read: Evolutionary Algorithms for Solving Multi-Objective Problems (Ch.1)
Additional Read: Language and Compiler Support for Auto-Tuning Variable-Accuracy Algorithms (CGO 2011)
Software: OpenTuner
9/12 Submit Your Paper Choices: Link
9/15

Quality-Aware Optimization Systems (2)

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

Probabilistic Programming (1)

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

Probabilistic Programming (2)

Background Read: Probabilistic Models of Cognition, Ch.7
Examples: Examples worked out in class
Background Read: PPAML Summer School 2016
Sasa
Slides
Additional Read: Modeling Agents with Probabilistic Programs (online book)
9/24

Probabilistic Programming (3)

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

Testing and Verifying Approximate, Nondeterministic, and Probabilistic Software

Background Read: A Comprehensive Study of Real-World Numerical Bug Characteristics (ASE 2017)
Background Read: Testing Probabilistic Programming Systems (FSE 2018)
Background Read: A practical guide for using statistical tests to assess randomized algorithms in software engineering (ICSE 2011)
Sasa
Slides
10/1

Approximate Systems (1)

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)
Rafae Additional Read: Phase-Aware Optimization in Approximate Computing (CGO 2017)
Additional Read: Image Perforation: Automatically Accelerating Image Pipelines by Intelligently Skipping Samples (SIGGRAPH 2016)
10/6

Approximate Systems (2)

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

Approximate Systems (3)

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

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)
(Hashim) Additional Read: 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)
10/15

Pruning/Distilling in Neural Networks

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

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)
Daniel
10/22

Training DNNs in Low-Precision

Primary Read: Understanding and Optimizing Asynchronous Low-Precision Stochastic Gradient Descent (ISCA 2017)
Secondary Read: Training Deep Neural Networks with 8-bit Floating Point Numbers (NeurIPS 2018)
Ashish Additional read: Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent (NIPS 2011)
Additional read: High-Accuracy Low-Precision Training
Additional read: Highly Scalable Deep Learning Training System with Mixed-Precision: Training ImageNet in Four Minutes
10/27

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)
Dimitrios Additional Read: DeepTest: Automated Testing of Deep-Neural-Network-driven Autonomous Cars (ICSE 2018)
10/29

Testing: Probabilistic Applications

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

Testing: Numerical Applications

Primary Read: Efficient Generation of Error-Inducing Floating-Point Inputs via Symbolic Execution (ICSE 2020)
Secondary Read: Effective Floating-Point Analysis via Weak-Distance Minimization (PLDI 2019)
(Online)
11/5

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 Statistical Software)
(TBD) Background Read: Continuation Passing Style Notes (from CS 421)
Additional Read: The Design and Implementation of Probabilistic Programming Languages (online book)
11/10

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)
Jonah Additional Read: FlexGibbs: Reconfigurable Parallel Gibbs Sampling Accelerator for Structured Graphs (FCCM 2019)
11/12

Probabilistic Programming Systems (3)

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

Probabilistic Programming Systems (4)

Primary Read: Scenic: a language for scenario specification and scene generation (PLDI 2019)
Secondary Read: Picture: A probabilistic programming language for scene perception (CVPR 2015)
Dawei Additional Read: Bayonet: Probabilistic Inference for Networks (PLDI 2018)
11/19

TBD

11/24
Thanksgiving (no class)
11/26
12/1

Application of Probabilistic Analysis 1

Primary Read: Static Analysis for Probabilistic Programs: Inferring Whole Program Properties from Finitely Many Paths (PLDI 2013)
Secondary Read: Probabilistic Programming with Densities in SlicStan: Efficient, Flexible and Deterministic (POPL 2019)
Shubham Additional Read: A Theory of Slicing for Probabilistic Control Flow Graphs (FoSSaCS 2016)
Additional Read: R2: An Efficient MCMC Sampler for Probabilistic Programs (AAAI 2014)
12/3

Application of Probabilistic Analysis 2

Primary Read: Probabilistic program abstractions (UAI 2017)
Secondary Read: PMAF: an algebraic framework for static analysis of probabilistic programs (PLDI 2018)
Justin Additional Read: Bounded expectations: resource analysis for probabilistic programs (PLDI 2018)
12/8

Student Project Presentations


All
 

Course 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
 

General Resources  


Mental Health:
Diminished mental health, including significant stress, mood changes, excessive worry, substance/alcohol abuse, or problems with eating and/or sleeping can interfere with optimal academic performance, social development, and emotional wellbeing. The University of Illinois offers a variety of confidential services including individual and group counseling, crisis intervention, psychiatric services, and specialized screenings at no additional cost. If you or someone you know experiences any of the above mental health concerns, it is strongly encouraged to contact or visit any of the University’s resources provided below. Getting help is a smart and courageous thing to do -- for yourself and for those who care about you.
Counseling Center: 217-333-3704, 610 East John Street Champaign, IL 61820
McKinley Health Center:217-333-2700, 1109 South Lincoln Avenue, Urbana, Illinois 61801

Sexual Misconduct Reporting Obligation:
The University of Illinois is committed to combating sexual misconduct. Faculty and staff members are required to report any instances of sexual misconduct to the University’s Title IX Office. In turn, an individual with the Title IX Office will provide information about rights and options, including accommodations, support services, the campus disciplinary process, and law enforcement options.
A list of the designated University employees who, as counselors, confidential advisors, and medical professionals, do not have this reporting responsibility and can maintain confidentiality, can be found here: http://wecare.illinois.edu/resources/students/#confidential
Other information about resources and reporting is available here: wecare.illinois.edu.

Academic Integrity:
The University of Illinois at Urbana-Champaign Student Code should also be considered as a part of this syllabus. Students should pay particular attention to Article 1, Part 4: Academic Integrity. Read the Code at the following URL: http://studentcode.illinois.edu/.
Academic dishonesty may result in a failing grade. Every student is expected to review and abide by the Academic Integrity Policy: https://studentcode.illinois.edu/article1/part4/1-401/. Ignorance is not an excuse for any academic dishonesty. It is your responsibility to read this policy to avoid any misunderstanding. Do not hesitate to ask the instructor(s) if you are ever in doubt about what constitutes plagiarism, cheating, or any other breach of academic integrity.

Religious Observances:
Illinois law requires the University to reasonably accommodate its students' religious beliefs, observances, and practices in regard to admissions, class attendance, and the scheduling of examinations and work requirements. You should examine this syllabus at the beginning of the semester for potential conflicts between course deadlines and any of your religious observances. If a conflict exists, you should notify your instructor of the conflict and follow the procedure at https://odos.illinois.edu/community-of-care/resources/students/religious-observances/ to request appropriate accommodations. This should be done in the first two weeks of classes.

Disability-Related Accommodations:
To obtain disability-related academic adjustments and/or auxiliary aids, students with disabilities must contact the course instructor and the Disability Resources and Educational Services (DRES) as soon as possible. To contact DRES, you may visit 1207 S. Oak St., Champaign, call 333-4603, e-mail disability@illinois.edu or go to https://www.disability.illinois.edu. If you are concerned you have a disability-related condition that is impacting your academic progress, there are academic screening appointments available that can help diagnosis a previously undiagnosed disability. You may access these by visiting the DRES website and selecting “Request an Academic Screening” at the bottom of the page.

Family Educational Rights and Privacy Act (FERPA):
Any student who has suppressed their directory information pursuant to Family Educational Rights and Privacy Act (FERPA) should self-identify to the instructor to ensure protection of the privacy of their attendance in this course. See https://registrar.illinois.edu/academic-records/ferpa/ for more information on FERPA.

-