Topics in Programming Languages:
Approximate And Probabilistic Programming Systems

Spring 2022 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 Spring 2022, our particular focus will be on the approximations and accuracy concerns of edge systems including machine learning components and techniques for checking correctness of randomized/probabilistic applications.

 

News  


 Lectures:
 Tuesday/Thursday
 3:30-4:45pm
 Siebel Center 0216

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

 Office Hours:
 After class

Overview  

This is a research-oriented course. It will include lectures, reading research papers, in-class discussions, and a final research project. In addition to in person lectures, we plan to use a combination of Zoom for some lectures and recording of asynchronous presentations, HotCRP for paper reviewing and discussion, and Piazza for announcements and Q&A. 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 final grade by 1%.
  • Discuss the paper on the on-line reviewing platform before the class and in the class.
Presentation and Discussion Lead 20%
  • Select at least five papers you would like to present by 2/8:
    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 (2 pages): beginning of October. Feel free to discuss the topics with Sasa beforehand.
  • Presentation (10 minutes): beginning of December.
  • Report (5 double-column pages): beginning of December.
  • Template for the report: same as PLDI
  • Preferrable in groups of two; or individual. Discuss with Sasa.
Homework 10%
(+ 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
1/18

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)
1/20

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)
1/25

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)
1/27

Approximations: Machine Learning

Background Read: Approximate Computing Techniques for Deep Neural Networks Book Chapter
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)
Additional Read: Neural Network Quantization Survey
Software: Intel Distiller
2/1

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)
2/3

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
2/8 Submit Your Paper Choices: Link
2/8

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)
2/10

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)
2/15

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)
2/17

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)
2/22

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
2/24

Approximate Systems (1)

Primary Read: Input responsiveness: using canary inputs to dynamically steer approximation (PLDI 2016)
Secondary Read: ApproxIt: A Quality Management Framework of Approximate Computing for Iterative Methods (IEEE TCAD 2020) (Sections 1 and 2)
Additional Read: Image Perforation: Automatically Accelerating Image Pipelines by Intelligently Skipping Samples (SIGGRAPH 2016) Additional Read: Phase-Aware Optimization in Approximate Computing (CGO 2017)
3/1

Approximate Systems (2)

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

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)
Additional Read: Stochastic Optimization of Floating-Point Programs with Tunable Precision (PLDI 2014)
Additional Read: Towards automatic significance analysis for approximate computing (CGO 2016)
Fun Facts: Borgerson and Freitas. A reliability model for gracefully degrading and standby-sparing systems (IEEE Trans. on Computers 1975)
3/8 Submit Project Proposal (1-2 pages)
3/8

Accuracy-Aware DNN Inference (1)

Primary Read: Deep Compression: Compressing Neural Networks With Pruning, Trained Quantization, and Huffman Coding (ICLR 2016)
Secondary Read: ApproxTuner: A Compiler and Runtime System for Adaptive Approximations (PPOPP 2021)
Additional Read: PerforatedCNNs: Acceleration through Elimination of Redundant Convolutions (NIPS 2016)
Fun Facts: Overparameterization: A Connection Between Software 1.0 and Software 2.0 (SNAPL 2019)
3/10

Accuracy-Aware DNN Inference (2)

Primary Read: Scalpel: Customizing DNN Pruning to the Underlying Hardware Parallelism (ISCA 2017)
Secondary Read: What is the state of Neural Network Prunnig? (MLSYS 2020)
3/15
Spring Break (no class)
3/17
3/22

Accuracy-Aware DNN Inference (3)

Primary Read: The Lottery Ticket Hypothesis: Finding Small, Trainable Neural Networks (ICLR 2019)
Secondary Read: NPAS: A Compiler-aware Framework of Unified Network Pruning and Architecture Search for Beyond Real-Time Mobile Acceleration (CVPR 2021)
Additional Read: Quantized neural networks: training neural networks with low precision weights and activations (JMLR 2017)
3/24

DNN Accuracy vs. Privacy

Primary Read: Shredder: Learning Noise Distributions to Protect Inference Privacy (ASPLOS 2020)
Secondary Read: Defensive approximation: securing CNNs using approximate computing (ASPLOS 2021)
3/29

Testing: Deep Learning Applications

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

Testing: Probabilistic Applications

Primary Read: TERA: Optimizing Stochastic Regression Tests in Machine Learning Projects (ISSTA 2021)
Secondary Read: FLEX: Fixing Flaky Tests in Machine Learning Projects by Updating Assertion Bounds (FSE 2021)
Additional Read: Statistical Algorithmic Profiling for Randomized Approximate Programs (ICSE 2019)
Additional Read: Testing Probabilistic Programming Systems (FSE 2018)
4/5

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)
4/7

Testing and Analysis: Robustness

Primary Read: TBD (TBD)
Secondary Read: TBD (TBD)
4/12

Probabilistic Programming Systems (1)

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)
4/14

TBD

4/19

Probabilistic Programming Systems (2)

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

Probabilistic Programming Systems (3)

Primary Read: Reactive probabilistic programming (PLDI 2020)
Secondary Read: Scenic: a language for scenario specification and scene generation (PLDI 2019)
Additional Read: Picture: A probabilistic programming language for scene perception (CVPR 2015)
4/26

Probabilistic Programming: Transformations (1)

Primary Read: Probabilistic Programming with Densities in SlicStan: Efficient, Flexible and Deterministic (POPL 2019)
Secondary Read: Static Analysis for Probabilistic Programs: Inferring Whole Program Properties from Finitely Many Paths (PLDI 2013)
Additional Read: A Theory of Slicing for Probabilistic Control Flow Graphs (FoSSaCS 2016)
Additional Read: Probabilistic program abstractions (UAI 2017)
4/28

Probabilistic Programming: Transformations (2)

Primary Read: Transforming Probabilistic Programs for Model Checking (FODS 2020)
Secondary Read: FairSquare: probabilistic verification of program fairness (OOPSLA 2017)
5/3

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.

-