Topics in Programming Languages:
Approximate And Probabilistic Programming Systems

Spring 2024 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 2024, our particular focus will be on the approximations and accuracy concerns of edge systems with machine learning components.

 

News  


Lectures:
Wednesday (Urbana) and Friday (Chicago)
11am-12:15pm
Siebel Center 1214 (Urbana) or 200 Wecker Dr 707 (Chicago)

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

Office Hours:
After class or by appointment

TA:
Shubham Ugare
Computer Science, UIUC
3107 Siebel Center sugare2@illinois.edu

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 30%
  • 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 Monday (for Wednesday papers) and Wednesday (for Friday papers). This gives enough time for the paper lead to prepare for the discussion.
  • Can skip or submit late up to 3 without penalty; each additional decreases the final grade by proportionally to the total number of reviews.
  • Discuss the paper on the on-line reviewing platform before the class and in the class.
(For PhD and MS Thesis Students) Presentation and Discussion Lead 20%
  • Select at least five papers you would like to present by 2/15.
  • 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.
(For MCS and Undergrad students) Homework 20%
  • Will be given throughout the course to practice the concepts taught in lectures.
  • Total 4-5 of these exercises, about 1-2 weeks apart.
  • Occasionally will give out optional homework for extra credit (XC).
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
  • In groups of two. Discuss with Sasa if you have questions.
Extra Credit One grade up
  • For PhD and MS Thesis Students: do the Homework Exercises.
  • For MCS and Undergrad Students: do the Presentation and Discussion Lead

 

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

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/19

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

Approximations: Numerical Computations

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

Approximations: Machine Learning (1)

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
1/31

Approximations: Machine Learning (2)

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

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

Quality-Aware Optimization Systems: Theory and Autotuning

Background Read: Metaheuristics Book (Ch.1, Ch.2, Ch.3, Ch.7)
Background Read: Accuracy-aware Compilers (book chapter)
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/9

Quality-Aware Optimization Systems: Program Analysis

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

Quality-Aware Optimization Systems: Machine Learning

Background Read: The deep learning compiler: A comprehensive survey (IEEE Tras. Par. Distr. Sys.)
Background Read: Ansor: Generating High-Performance Tensor Programs for Deep Learning (SOSP 2020)
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/16

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/19 Submit Paper Preferences (see Piazza for details)
2/21

Probabilistic Programming (2)

Examples: Examples worked out in class
Background Read: Frank Wood's Essentials of Bayesian Inference Lecture Notes
Background Read: PPAML Summer School 2016
Sasa
Slides
Background Read: Probabilistic Models of Cognition, Ch.7
Additional Read: Modeling Agents with Probabilistic Programs (online book)
2/23

Probabilistic Programming (3)

Examples: Examples worked out in class
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/28

Testing 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)
Sasa
Slides
Additional Read: A practical guide for using statistical tests to assess randomized algorithms in software engineering (ICSE 2011)
3/1 Submit Project Proposal (2 pages)
3/1

Verifying Approximate, Nondeterministic, and Probabilistic Software

Background Read: Trustworthy AI (CACM 2021)
Background Read: Toward verified artificial intelligence (CACM 2022)
Sasa
Slides
Additional Read: Certified adversarial robustness via randomized smoothing (ICML 2019)
3/6

Approximate Systems (1)

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

Approximate Systems (2)

Primary Read: High Performance Correctly Rounded Math Libraries for 32-bit Floating Point Representations (PLDI 2021)
Secondary Read: Rigorous floating-point mixed-precision tuning (POPL 2017)
Sasa Additional Read: Stochastic Optimization of Floating-Point Programs with Tunable Precision (PLDI 2014)
Fun Facts: Borgerson and Freitas. A reliability model for gracefully degrading and standby-sparing systems (IEEE Trans. on Computers 1975)
3/9
Spring Break (no class)
3/17
3/20

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)
David 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)
Fun Facts: What is the state of Neural Network Prunnig? (MLSYS 2020)
3/22

Accuracy-Aware DNN Inference (2)

Primary Read: AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration (2023)
Secondary Read: GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers (2023)
Changshu Additional Read: Quantized neural networks: training neural networks with low precision weights and activations (JMLR 2017)
3/27

Accuracy-Aware DNN Inference (3)

Primary Read: SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot (ICML 2023)
Secondary Read: A Simple and Effective Pruning Approach for Large Language Models (2023)
Kaizhuo
3/29

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

DNN Autotuning

Primary Read: Ansor: Generating High-Performance Tensor Programs for Deep Learning (SOSP 2020)
Secondary Read: Tensor Program Optimization with Probabilistic Programs (NeurIPS 2022) (sections 1-2)
Mohsin
4/5

Testing: Probabilistic and ML Applications

Primary Read: FLEX: Fixing Flaky Tests in Machine Learning Projects by Updating Assertion Bounds (FSE 2021)
Secondary Read: FASER: Balancing Effectiveness and Flakiness of Non-Deterministic Machine Learning Tests (ICSE 2023)
TBD Additional Read: TERA: Optimizing Stochastic Regression Tests in Machine Learning Projects (ISSTA 2021)
4/10

Testing: Numerical Applications

Primary Read: Exposing numerical bugs in deep learning via gradient back-propagation (FSE 2021)
Secondary Read: Efficient Generation of Error-Inducing Floating-Point Inputs via Symbolic Execution (ICSE 2020)
Stanley Additional Read: Towards automatic significance analysis for approximate computing (CGO 2016)
4/12

Testing and Analysis: Robustness

Primary Read: Incremental Randomized Smoothing Certification (ICLR'24) (with appendix)
Secondary Read: Proof Transfer for Fast Certification of Multiple Approximate Neural Networks (OOPSLA'22)
Shubham Additional Read: Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach (ICLR 2018)
Additional Read: ReluDiff: differential verification of deep neural networks (ICSE'20)
4/17

Probabilistic Programming Systems (1)

Primary Read: Etalumis: Bringing probabilistic programming to scientific simulators at scale (Supercomputing 2019)
Secondary Read: Compiling Markov Chain Monte Carlo Algorithms for Probabilistic Modeling (PLDI 2017)
Manvik Additional Read: FlexGibbs: Reconfigurable Parallel Gibbs Sampling Accelerator for Structured Graphs (FCCM 2019)
4/19

Probabilistic Programming Systems (2)

Primary Read: SPPL: Probabilistic Programming with Fast Exact Symbolic Inference (PLDI 2021)
Secondary Read: Probabilistic Programming with Stochastic Probabilities (PLDI 2023)
Vimarsh Additional Read: Deep Probabilistic Programming Languages: A Qualitative Study
Additional Read: Pyro: Deep Universal Probabilistic Programming (JMLR 2018)
4/24

Probabilistic Programming Systems (3)

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

Probabilistic Programming (4)

Primary Read: Probabilistic Programs as Measures (Chapter 2 in Foundations of PP Book; previous version: ESOP 2017
Secondary Read: Probabilistic Programming with Densities in SlicStan: Efficient, Flexible and Deterministic (POPL 2019)
Ayesha Additional 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)
5/1

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.

-