CS744 : Cyber-Physical Systems (Fall 2008)

Instructor

Insik Shin, CS Building (E3-1) 1420, Tel: (042)350-3524, Email:

Time and Place
Wednesday 1:00-4:00 pm, CS Building (E3-1) room 2443 (제3강의실)

Schedule

Date	Topic		Reading List	Lecture Slides
9/2	Introduction to Cyber-Physical Systems
9/10	Application of interdisciplinary theories to computer science problems	Optimization Theory & Performance Composition
9/17		No class (IEEE ETFA)
9/24		Performance Composition
10/1		Control Theory
10/8	Real-Time Systems: each week covers - classical results & - their extension towards compositionality	Periodic/Aperiodic Scheduling
10/15		Synchronization Protocols
10/22		No class (ACM EMSOFT)
10/29		Distributed Systems (end-to-end delay)
11/5		Multicore Scheduling
11/12	TBA
11/19	TBA
11/26	TBA
12/3	No class (IEEE RTSS)
12/10	Term-Project Presentation

Reading List

CPS Introduction

- “Cyber-Physical Systems: Executive Summary”, CPS Steering Group, 2008

Application of interdisciplinary theories to computer science problems

1. Optimization Theory & Performance Optimization for Software Systems

- ”Network Layering as Optimization Decomposition: A Mathematical Theory of Network Architectures”, Mung Chiang, S. H. Low, A. R. Calderbank, J. C. Doyle, Proceedings of IEEE 2007.

- "Integrating Adaptive Components: An Emerging Challenge in Performance-Adaptive Systems and a Server Farm Case-Study”, Jin Heo, Dan Henriksson, Xue Liu and Tarek Abdelzaher, RTSS 2007

2. Control Theory

- “Controlware: A middleware architecture for feedback control of software performance”, Ronghua Zhang, Chenyang Lu, Tarek F. Abdelzaher, John A. Stankovic, ICDCS 2002

Real-Time Systems

1. Periodic/Aperiodic Scheduling

- classical results

- ”Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment”, C. L. Liu and J. W. Layland, Journal of ACM 1973.

- extension for compositionality

- “Periodic Resource Model for Compositional Real-Time Guarantees," Insik Shin and Insup Lee, RTSS 2003 (Best Paper Award)

- “Compositional Real-Time Scheduling Framework with Periodic Model", Insik Shin and Insup Lee, ACM TECS 2008

2. Synchronization Protocols

- classical results

- "Priority Inheritance Protocols: An Approach to Real-Time Synchronization", Lui Sha, Ragunathan Rajkumar, and John P. Lehoczky, IEEE Transactions on Computers, 39 (9): 1175–1185, September 1990.

- “A stack-based allocation policy for realtime processes”, Ted Baker, RTSS 1990.

- “Resource sharing in EDF-scheduled systems: a closer look”, Sanjoy Baruah, RTSS 2006.

- extension for compositionality

- “Synthesis of Optimal Interfaces for Hierarchical Scheduling with Resources”, Insik Shin, Moris Behnam, Thomas Nolte, Mikael Nolin, to appear in RTSS 2008 (nominated for Best Paper Award)

3. Multicore Scheduling

- classical results

- extension for compositionality

- "Hierarchical Scheduling Framework for Virtual Clustering of Multiprocessors", Insik Shin, Arvind Easwaran, Insup Lee, ECRTS 2008 (Best Paper Runner Up)

4. Distributed Systems (end-to-end delays)

- classical results

- extension for compositionality

- “A Delay Composition Theorem for Real-Time Pipelines”, Praveen Jayachandran and Tarek Abdelzaher, ECRTS 2007 (Best Student Paper Award)

Description

This course presents an introduction to an emerging research discipline, cyber-physical systems. A cyber-physical system (CPS) is a computing systems that interacts with physical processes. Many recent years have seen a growing development of embedded systems. An embedded system is a special-purpose computer system designed to perform dedicated functions for specific physical devices (e.g., automobiles and consumer electronics). Since the embedded system is dedicated to specific tasks, optimization is a first-class design issue; design engineers can optimize it, reducing the size and cost of the product, or increasing the reliability and performance. Here, embedded systems are generally assumed to be standalone. What if they can be connected to each other, forming a larger-scale network of heterogeneous physical devices? What happened when heterogeneous smaller networks (e.g., LANs) are connected into a single larger-scale network, the Internet?

The last decade has been an explosive development of the Internet all over the world. The advent of Internet has raised numerous grand research challenges and has brought arguably the greatest technological impact on society as well, allowing a new communication paradigm. Cyber-physical systems will bring another (even bigger) research challenges and social impacts, suggesting yet another new paradigm of controlling information and physical devices. Cyber-physical systems are now facing various obstacles to their success. For example, a proper level of abstraction is necessary to tackle the complexity of large-scale CPS design; it needs to abstract heterogenous physical devices across various domains, hiding diverse domain-specific knowledge and techniques. Furthermore, autonomous is another must property that CPS should support. The advent of large-scale CPS would provide people with so much information and numerous devices to control, beyond their handling capacity. Here, CPS should be able to digest information and control individual devices dynamically and autonomously, achieving some given global performance optimization. Moreover, there are various other research issues to consider, including real-time, privacy, reliability, and etc.

A range of future CPS applications is only limited by our imagination. Many new applications will arise that improve the quality of life (e.g., smart assisted living facilities), enhance social experiences and human communication (e.g., new cyber-physical communication media), improve accessibility of information (e.g., wide-area data services), and help advance fundamental knowledge in many environmental, biological, and physical disciplines. In order to host such new applications, computer science must be redefined. New models and paradigms are needed for a new type of computation, and new underlying theoretical foundations are needed to support such paradigms. New programming languages and distributed middleware tools must be developed around the emerging abstractions of cyber-physical computation. Networking must be redefined to integrate myriads of physical data sources, actuators, and computing elements, as well as to develop appropriate application-layer data services. New operating systems are needed that are optimized for the new computing realm, as opposed to the current machine architectures and applications. Data mining and machine learning techniques are needed to identify data patterns, learn context, and act autonomously without human assistance.

In this course, we will explore various research challenges and directions that CPS imposes, present the underlying theoretical foundations, and shed light on related recent standards and embedded system technologies. Completing this course successfully, students will be equipped with a new perspective that helps to approach research problems from the CPS viewpoint, as well as some of the recent technological advances in CPS. Students are encouraged to participate actively in classes. Students are also required to submit a few paper critics and a term-project draft (aiming at submission to a CPS-related conference) and do a couple of class presentations (related to their term-projects).