General Information

Lecture Time: Tuesday 11:30AM - 2:20PM

Room: EIT 3151 Moved to EIT 3141

Office Hour: Based on appointment

Syllabus

Calendar Description

This course covers concepts, theory and research issues in safety-critical embedded systems and Cyber-Physical Systems (CPS), with a focus on the architectural design and analysis of the underlying hardware/software computing system.

Topics include: challenges in CPS design, predictable computer architectures, scheduling of hardware resources, operating system abstractions for CPS, timing and performance analysis, modeling and verification, CPS applications.

Course Description

Cyber-Physical Systems (CPS) are systems featuring a tight integration of computation with physical processes. Applications of CPS include new generation automotive systems, high confidence medical devices, avionics, smart power infrastructure, process control, distributed robotics, and others. All such systems exhibit stringent real-time and safety requirements: computation must progress in parallel with physical processes in the environment, and system disruption can lead to catastrophic consequences. Compared to traditional embedded systems, the vision for CPS calls for open, interconnected systems rather than closed, "black box" devices.

The goal of this course is to introduce the students to the key challenges, design methodologies and research directions in the field of cyber-physical systems, with an emphasis on the design of the underlying computing architecture. In particular, we will show how CPS requirements of predictability and reliability lead to significant changes in the hardware architecture, and we will study state-of-the-art solutions in this area. Due to the multidisciplinary nature of CPS design, the course will also touch on related topics, including: predictable operating system abstractions, timing analysis, modeling and verification.

Lecture Material

You should make sure to read the required papers before coming to class. The list of required papers for a given class will be published by Wednesday 11:59PM the week before. You are not required to read the other references, but you might want to keep a copy on hand because they might be discussed in class.

Lecture Topic	Slides	Papers	Student Presentations
Lecture 1: Introduction to CPS and Course Overview	Instructor Slides
Lecture 2: Introduction to Real-Time Systems	Instructor Slides Slides: Delay-Aware Period Assignment in Control Systems	Required Reading: Cyber Physical Systems: Design Challenges Further References: Delay-Aware Period Assignment in Control Systems
Lecture 3: CPS Applications	Instructor Slides	Required Reading: 777 Flight Control Validation Process Cyber-Physical Modeling of Implantable Cardiac Medical Devices Further References: Autonomous Driving in Urban Environments: Boss and the Urban Challenge The Electric Power Grid: Today and Tomorrow Comprehensive Experimental Analyses of Automotive Attack Surfaces
Lecture 4: Predictable Computer Architectures - Memories	Instructor Slides	Required Reading: Explicit Reservation of Local Memory in a Predictable, Preemptive Multitasking Real-time System Predator: A Predictable SDRAM Memory Controller Further References: Scratchpad Memories vs Locked Caches in Hard Real-Time Systems: A Quantitative Comparison Impact of Cache Partitioning on Multi-Tasking Real Time Embedded Systems A Dynamic Scratchpad Memory Unit for Predictable Real-Time Embedded Systems PRET DRAM Controller: Bank Privatization for Predictability and Temporal Isolation Worst Case Analysis of DRAM Latency in Multi-Requestor Systems	E.M.: Impact of Cache Partitioning on Multi-Tasking Real Time Embedded Systems
Lecture 5: Predictable Computer Architectures - Interconnects	Instructor Slides	Required Reading: AEthereal Network on Chip: Concepts, Architectures, and Implementations Hardware Support for WCET Analysis of Hard Real-Time Multicore Systems Further References: Real-Time Communication for Multicore Systems with Multi-Domain Ring Buses Predictable Implementation of Real-Time Applications on Multiprocessor Systems-on-Chip	A.D.: The Smart Thermostat: Using Occupancy Sensors to Save Energy in Homes B.F.: The Electric Power Grid: Today and Tomorrow K.E.: Body Area Networks: A Survey N.H.: Autonomous Driving in Urban Environments: Boss and the Urban Challenge
Lecture 6: Predictable Computer Architectures - Microarchitecture	Instructor Slides	Required Reading: Predictable Programming on a Precision Timed Architecture Memory Hierarchies, Pipelines, and Buses for Future Architectures in Time-critical Embedded Systems Further References: Time-Predictable Out-of-Order Execution for Hard Real-Time Systems	M.G: PRET DRAM Controller: Bank Privatization for Predictability and Temporal Isolation M.B.: Worst Case Analysis of DRAM Latency for Real-Time Multi-core Systems A.B.: Predictable Implementation of Real-Time Applications on Multiprocessor Systems-on-Chip
Lecture 7: Predictable Computer Architectures - Heterogeneous	Instructor Slides	Required Reading: Further References: GPUSync: A Framework for Real-Time GPU Management Anytime Algorithms for GPU Architectures Real-Time Control of I/O COTS Peripherals for Embedded Systems
Lecture 8: OS	Instructor Slides Memguard Slides	Required Reading: On the Scalability of Real-Time Scheduling Algorithms on Multicore Platforms: A Case Study An Overview of Interrupt Accounting Techniques for Multiprocessor Real-Time Systems MemGuard: Memory Bandwidth Reservation System for Efficient Performance Isolation in Multi-core Platforms Further References: Real-Time Synchronization on Multiprocessors: To Block or Not to Block, to Suspend or Spin? A Predictable Execution Model for COTS-based Embedded Systems Making Shared Caches More Predictable on Multicore Platforms
Lecture 9: Timing Analysis 1	Instructor Slides	Required Reading: System architecture evaluation using modular performance analysis: a case study End-to-End Delay Analysis of Distributed Systems with Cycles in the Task Graph Schedulability Analysis for Tasks with Static and Dynamic Offsets Further References: Tighter Response-Times for Tasks with Offsets Real-time communication analysis for on-chip networks with wormhole switching	N.P.: A Predictable Execution Model for COTS-based Embedded Systems
Lecture 10: Timing Analysis 2		Required Reading: Further References: Timing analysis of concurrent programs running on shared cache multi-cores Worst Case Delay Analysis for Memory Interference in Multicore Systems Real-time queueing network theory	A.A.: Real-time queueing network theory R.S.: Timing Analysis of Concurrent Programs Running on Shared Cache Multi-Cores
Lecture 11: Models and Verification	Instructor Slides Timed Automata Slides PCI HW Monitoring Slides	Required Reading: Hybrid Cyberphysical System Verification With Simplex Using Discrete Abstractions Further References: Automatic Verification of Real-Time Communicating Systems by Constraint Solving Handling Mixed Criticality in SoC-based Real-Time Embedded Systems Sampling-based Runtime Verification	B.Y: Sampling-based Runtime Verification R.O.: Handling Mixed Criticality in SoC-based Real-Time Embedded Systems
Lecture 12: Project Presentations		Required Reading: Further References:

Required Reading List

This is a list of papers that will be required reading during the course. Please see the table above to determine which papers are assigned for each class. You can not select one of these papers for your formal presentation. For students selecting the applied track, the final exam will be focused on the required papers and additional instructor slides. I reserve the right to change this list before the end of the course.

Introduction to CPS

• Cyber Physical Systems: Design Challenges

CPS Applications

• 777 Flight Control Validation Process
• Cyber-Physical Modeling of Implantable Cardiac Medical Devices

Predictable Computer Architectures

• Explicit Reservation of Local Memory in a Predictable, Preemptive Multitasking Real-time System
• Predator: A Predictable SDRAM Memory Controller
• AEthereal Network on Chip: Concepts, Architectures, and Implementations
• Hardware Support for WCET Analysis of Hard Real-Time Multicore Systems
• Predictable Programming on a Precision Timed Architecture
• Memory Hierarchies, Pipelines, and Buses for Future Architectures in Time-critical Embedded Systems

OS Abstractions

• On the Scalability of Real-Time Scheduling Algorithms on Multicore Platforms: A Case Study
• An Overview of Interrupt Accounting Techniques for Multiprocessor Real-Time Systems
• MemGuard: Memory Bandwidth Reservation System for Efficient Performance Isolation in Multi-core Platforms

Timing and Performance Analysis

• System architecture evaluation using modular performance analysis: a case study
• End-to-End Delay Analysis of Distributed Systems with Cycles in the Task Graph
• Schedulability Analysis for Tasks with Static and Dynamic Offsets

Models and Verification

• Hybrid Cyberphysical System Verification With Simplex Using Discrete Abstractions

Paper Presentation List

Each student is required to provide a formal seminar presentation during lecture. Each seminar presentation covers one or two related research papers and shall provide an introduction followed by sufficient details for the class to understand the motivation, problems, and main solutions provided by the authors. Papers can be selected from the list below (divided by topic). If you wish to cover a different but related topic, please contact the instructor.

Seminar Presentation Details

This year, each presentation will be allocated a 18 minutes slot + 5 minutes for questions. The presentation will be run "conference style", i.e., all questions will be asked at the end. Keep into mind this essential points when preparing your presentation:

• Structure your presentation with a clear introduction, main section and conclusions.
• While I will introduce the main topic in class before each seminar, keep into mind that the audience is not very familiar with the specific problem at hand. Hence, include enough details that students can clearly understand the motivation and problem covered by the paper.
• Since you have limited time, focus more on discussing good points/results/limitations of the main solution discussed in the paper rather than trying to cover all technical details.
• Try to provide a critique of the paper (even if not perfect): what did you like about the paper? What do you think are weaknesses? Could it be improved?

You will be evaluated based on: 1. oral presentation 2. slides quality and organization 3. content. To simplify running the presentation during class, if possible provide your slides to the instruction in either .pdf or powerpoint format before the start of the lecture (either by email of USB stick). If you prefer to use a different file format, you can alternatively use your own laptop.

CPS Applications

• The Smart Thermostat: Using Occupancy Sensors to Save Energy in Homes
• Autonomous Driving in Urban Environments: Boss and the Urban Challenge
• Body Area Networks: A Survey
• The Electric Power Grid: Today and Tomorrow
• Comprehensive Experimental Analyses of Automotive Attack Surfaces

Predictable Computer Architectures

• Scratchpad Memories vs Locked Caches in Hard Real-Time Systems: A Quantitative Comparison
• Impact of Cache Partitioning on Multi-Tasking Real Time Embedded Systems
• A Dynamic Scratchpad Memory Unit for Predictable Real-Time Embedded Systems
• PRET DRAM Controller: Bank Privatization for Predictability and Temporal Isolation
• Worst Case Analysis of DRAM Latency in Multi-Requestor Systems
• Real-Time Communication for Multicore Systems with Multi-Domain Ring Buses
• Predictable Implementation of Real-Time Applications on Multiprocessor Systems-on-Chip
• Time-Predictable Out-of-Order Execution for Hard Real-Time Systems
• GPUSync: A Framework for Real-Time GPU Management
• Deterministic Mechanism for Run-time Reconfiguration Activities in an RTOS
• Anytime Algorithms for GPU Architectures
• Real-Time Control of I/O COTS Peripherals for Embedded Systems

OS Abstractions

• HIRES: a System for Predictable Hierarchical Resource Management
• Real-Time Synchronization on Multiprocessors: To Block or Not to Block, to Suspend or Spin?
• A Predictable Execution Model for COTS-based Embedded Systems
• Memory-Centric Scheduling for Multicore Hard Real-Time Systems
• Making Shared Caches More Predictable on Multicore Platforms

Timing and Performance Analysis

• Timing analysis of concurrent programs running on shared cache multi-cores
• Worst Case Delay Analysis for Memory Interference in Multicore Systems
• Real-time communication analysis for on-chip networks with wormhole switching
• Real-time queueing network theory
• Tighter Response-Times for Tasks with Offsets

Models and Verification

• Automatic Verification of Real-Time Communicating Systems by Constraint Solving
• Handling Mixed Criticality in SoC-based Real-Time Embedded Systems
• Sampling-based Runtime Verification

Course Deadlines

List of deadlines for the course project - research track. Please see the syllabus and Lecture 1 slides for additional details.

• Project proposal - Feb 3 8:00AM
• Literature Review - Mar 3 8:00AM
• Project presentation - during Lecture 12, April 1
• Project report - due on final exam date
• Final - To Be Announced

List of deadlines for the applied track. Please see the syllabus and Lecture 1 slides for additional details.

• Midterm report - Mar 3 Mar 10 8:00AM
• Project presentation - during Lecture 12, April 1
• Project report - April 4 11:59PM (last day of class)
• Final - To Be Announced

Final Exam

This is an example text for the final exam, research track. Students will be generally assigned a topic close to their interests. The actual number of questions in the exam could be different from the exam, but it will be similarly structured.

The final exam for the applied track consists of a traditional 2 hours and 30 mins written exam. See Lecture 1 slides for more details. This is an example set of questions for the final exam, applied track - note that the question set is not necessarily representative of the length of the exam, but it covers the main types of questions that will appear in the exam.