File preview
Introducing Embedded Systems:
A Cyber- Physical Systems Approach
Edward A. Lee
Robert S. Pepper Distinguished Professor UC Berkeley
With special thanks to my collaborators: • Jeff Jensen, National Instruments • Sanjit Seshia, UC Berkeley
CPS PI Meeting Education Keynote
National Harbor, Maryland October 5, 2012
Background: Five Years of Experience with “Introduction to Embedded Systems”
This course is intended to introduce students to the design and analysis of computational systems that interact with physical processes.
• • • • • • • • • • • • • • • • • • • • Cyber-Physical Systems Model-Based Design Sensors and Actuators Interfacing to Sensors and Actuators Actors, Dataflow Modeling Modal Behavior Concurrency: Threads and Interrupts Hybrid Systems Simulation Specification; Temporal Logic Reachability Analysis Controller Synthesis Control Design for FSMs and ODEs Real-Time Operating Systems (RTOS) Scheduling: Rate-Monotonic and EDF Concurrency Models Execution Time Analysis Localization and Mapping Real-Time Networking Distributed Embedded Systems Lee, Berkeley 2
A major theme of this course will be on the interplay of practical design with formal models of systems, including both software components and physical dynamics. A major emphasis will be on building high confidence systems with real-time and concurrent behaviors.
The course has recently been extended to become a mezzanine-level course, aimed at advanced undergraduates and beginning graduate students. Dovetails with a new professional masters program with a focus on robotics and embedded systems.
http://LeeSeshia.org
Approach: Interplay of Modeling, Design, and Analysis
Lee, Berkeley 3
http://LeeSeshia.org
Lee, Berkeley 4
This Talk: Focus on Design
(and specifically, design of software)
¢
Traditional design of embedded systems:
Embedded software is software on small computers. The technical problem is one of optimization (coping with limited resources and extracting performance).
¢
CPS-based design of embedded systems:
Computation and networking integrated with physical processes. The technical problem is managing dynamics, time, and concurrency in networked computational + physical systems.
Lee, Berkeley 5
Our Approach: Emphasis on Critical Thinking
“Our view is that the field of cyber-physical systems is very young, and it would not serve our students well to leave them with the illusion that completing the course equates to mastery of the subject.”
[Lee, Seshia, Jensen, WESE 2012]
We teach them to think critically about today’s technology, not just to master it.
Lee, Berkeley 6
Design Lab: Structure
¢
6 weeks of structured labs introducing students to some of the tools of the trade. 9 weeks of group projects.
¢
Draft lab manual available…
Lee, Berkeley 7
The Tools of the Trade
Model-Based Design Concepts: Concurrent models of computation, code generation, determinism, ... Real-Time Operating Systems Concepts: Scheduling, priorities, mutual exclusion, nondeterminism, ... Bare-Iron Programming Concepts: Interrupts, polling, memory models, timing, ...
In the first six weeks, students get experience with three levels of abstraction in embedded software design.
Lee, Berkeley 8
The Hardware Platform for the First Six Weeks
Modified iRobot Create with wireless networking, many built-in sensors, and a three-axis accelerometer.
Lee, Berkeley 9
Computational Platform: Single-Board Rio (National Instruments)
analog & digital IO
This board provides all three layers of abstraction:
¢
Xilinx FPGA
Freescale PowerPC
Bare iron C programming on a Xilinx Microblaze soft core. RTOS C programming on a PowerPC running VxWorks. LabVIEW modelbased design with code generation.
¢
¢
RS-232 Serial
SD card
CAN
USB
Ethernet
Lee, Berkeley 10
The “Harry Potter” Approach to Embedded Software Design (Bare Iron Level)
On an Atmega 168 (a popular 8-bit microcontroller):
// Set timer1 to generate an interrupt every 1ms TCCR1A = 0x00; TCCR1B = (_BV(WGM12) | _BV(CS12)); Expelliatmega! OCR1A = 71;
Learn the right spells, and express them with conviction...
Lee, Berkeley 11
The Emphasis on Critical Thinking (Bare Iron Level)
TCCR1B = (_BV(WGM12) | _BV(CS12)); Hunt for header files used by the compiler #define #define #define #define #define #define _MMIO_BYTE(mem_addr)(*(volatile uint8_t *)(mem_addr)) _SFR_MEM8(mem_addr) _MMIO_BYTE(mem_addr) _BV(bit) (1 << (bit)) TCCR1B _SFR_MEM8 (0x81) WGM12 3 CS12 2 C preprocessor (*(volatile uint8_t *)(0x81)) = (1 << 3) | (1 << 2);
Although TCCR1B appears to be a C variable, it is not (and cannot be, since C provides no way to force a variable to reside at a particular memory address). Evidently, C is not a perfect match for the problem at hand!
Lee, Berkeley 12
The Emphasis on Critical Thinking (RTOS Level)
Levels of abstraction for concurrent programs. Critical thinking requires understanding pitfalls of scheduling and locks.
Lee, Berkeley 13
A Scenario
Under Integrated Modular Avionics, software in the aircraft engine continually runs diagnostics and publishes diagnostic data on the local network.
Proper software engineering practice suggests using the observer pattern.
An observer process updates the cockpit display based on notifications from the engine diagnostics.
Lee, Berkeley 14
#include <pthread.h> ... int value; pthread_mutex_t lock; void addListener(notify listener) { pthread_mutex_lock(&lock); ... add the listener to the list ... pthread_mutex_unlock(&lock); }
Threads: the Prevailing Concurrency Model
A carefully constructed “thread safe” multitasking solution. It turns out it carries risk of lurking errors… If multiple threads call update(), the updates will occur in some order. But there is no assurance that the listeners will be notified in the same order. Listeners may be mislead about the “final” value.
void update(int newValue) { pthread_mutex_lock(&lock); value = newValue; ... copy the list of listeners ... pthread_mutex_unlock(&lock); ... notify the listeners on the copy ... } int main(void) { pthread_mutex_init(&lock, NULL); ... start diagnostic & observer threads. }
Lee, Berkeley 15
Recall the Scenario
Under Integrated Modular Avionics, software in the aircraft engine continually runs diagnostics and publishes diagnostic data on the local network.
Proper software engineering practice suggests using the observer pattern.
An observer process updates the cockpit display based on notifications from the engine diagnostics.
Lee, Berkeley 16
The Emphasis on Critical Thinking (Model-Based Design Level)
Levels of abstraction for concurrent programs. Critical thinking requires understanding concurrent models of computation.
Lee, Berkeley 17
Model-Based Design
Accelerometer update loop (200 Hz)
Emphasis on concurrency and timing. Lab experience with LabVIEW, classroom discussion of other model-based design formalisms.
alpha 0.25
lowpass (exponential moving average) filter input output = (1 - alpha) sum * sum + alpha * input; alpha input output = (1 - alpha) sum * sum + alpha * input; alpha output output
5
accel x accel y
stop iRobot sensor update loop (67 Hz) iRobot sensor interval (ms) 15 sensor stream align delay (ms) 1 iRobot Sensor Stream Read (all sensors).vi sensors If a packet is read, delay until next packet should arrive; otherwise, wait a short period to see if a packet has arrived (aligning with the stream)
stop
Control loop (40 Hz)
25
y offset (V) x offset (V) accel x accel y +1g offset (V) uphill angle (rad)
interpret acccerometer
Cal Climber State Machine.vi iRobot Drive Direct.vi stop
Tilt Threshold (g) 0.1 sensors Max Wheel Speed (mm/s) 250 Speed Increment (mm/s^2 5
Lee, Berkeley 18
Capstone Projects
¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢
Cegway-like two-wheel robot Distributed Pacman Cooperative self-parking vehicles Face-tracking quadrotor Robotic convoys Elevator operator Automatic xylophone Dataglove gesture replicator Gesture-driven robot steering Mapping and localization Robotic summo wrestling …
Lee, Berkeley 19
Capstone Projects
Lee, Berkeley 20
The Canon
Teachers should teach what they know.
Actually, the most valuable teachers are the ones who teach what is not known…
Lee, Berkeley 21
Conclusion
Our job isn't to get our students to replicate us. Our job is to get our students to replace us. If we succeed, our students will make us obsolete. If we fail, their students will make us obsolete.
Lee, Berkeley 22
Backup Slides
Lee, Berkeley 23
Applications First? Or Foundations First?
Bottom-up: - foundations first - derive the applications
Top-down: - applications first - derive the foundations
Lee, Berkeley 24
Class Projects are Defined by the Students. Example:
May 16, 2008
One of the five project teams in 2008 developed a balancing robot inspired by the Segway. They used a Nintendo Wiimote as a controller communicating with a PC running LabVIEW, communicating with a Lego Mindstorm NXT, which they programmed in C.
Lee, Berkeley 25
Modeling Physical Dynamics
Lee, Berkeley 26
Actor Model of Systems
A system is a function that accepts an input signal and yields an output signal. The domain and range of the system function are sets of signals, which themselves are functions. Parameters may affect the definition of the function S.
Lee, Berkeley 27
State Machines and Modal Models
Modal models combine such actor models with state machines, where each state of the machine represents a mode of operation.
Lee, Berkeley 28
A Cyber- Physical Systems Approach
Edward A. Lee
Robert S. Pepper Distinguished Professor UC Berkeley
With special thanks to my collaborators: • Jeff Jensen, National Instruments • Sanjit Seshia, UC Berkeley
CPS PI Meeting Education Keynote
National Harbor, Maryland October 5, 2012
Background: Five Years of Experience with “Introduction to Embedded Systems”
This course is intended to introduce students to the design and analysis of computational systems that interact with physical processes.
• • • • • • • • • • • • • • • • • • • • Cyber-Physical Systems Model-Based Design Sensors and Actuators Interfacing to Sensors and Actuators Actors, Dataflow Modeling Modal Behavior Concurrency: Threads and Interrupts Hybrid Systems Simulation Specification; Temporal Logic Reachability Analysis Controller Synthesis Control Design for FSMs and ODEs Real-Time Operating Systems (RTOS) Scheduling: Rate-Monotonic and EDF Concurrency Models Execution Time Analysis Localization and Mapping Real-Time Networking Distributed Embedded Systems Lee, Berkeley 2
A major theme of this course will be on the interplay of practical design with formal models of systems, including both software components and physical dynamics. A major emphasis will be on building high confidence systems with real-time and concurrent behaviors.
The course has recently been extended to become a mezzanine-level course, aimed at advanced undergraduates and beginning graduate students. Dovetails with a new professional masters program with a focus on robotics and embedded systems.
http://LeeSeshia.org
Approach: Interplay of Modeling, Design, and Analysis
Lee, Berkeley 3
http://LeeSeshia.org
Lee, Berkeley 4
This Talk: Focus on Design
(and specifically, design of software)
¢
Traditional design of embedded systems:
Embedded software is software on small computers. The technical problem is one of optimization (coping with limited resources and extracting performance).
¢
CPS-based design of embedded systems:
Computation and networking integrated with physical processes. The technical problem is managing dynamics, time, and concurrency in networked computational + physical systems.
Lee, Berkeley 5
Our Approach: Emphasis on Critical Thinking
“Our view is that the field of cyber-physical systems is very young, and it would not serve our students well to leave them with the illusion that completing the course equates to mastery of the subject.”
[Lee, Seshia, Jensen, WESE 2012]
We teach them to think critically about today’s technology, not just to master it.
Lee, Berkeley 6
Design Lab: Structure
¢
6 weeks of structured labs introducing students to some of the tools of the trade. 9 weeks of group projects.
¢
Draft lab manual available…
Lee, Berkeley 7
The Tools of the Trade
Model-Based Design Concepts: Concurrent models of computation, code generation, determinism, ... Real-Time Operating Systems Concepts: Scheduling, priorities, mutual exclusion, nondeterminism, ... Bare-Iron Programming Concepts: Interrupts, polling, memory models, timing, ...
In the first six weeks, students get experience with three levels of abstraction in embedded software design.
Lee, Berkeley 8
The Hardware Platform for the First Six Weeks
Modified iRobot Create with wireless networking, many built-in sensors, and a three-axis accelerometer.
Lee, Berkeley 9
Computational Platform: Single-Board Rio (National Instruments)
analog & digital IO
This board provides all three layers of abstraction:
¢
Xilinx FPGA
Freescale PowerPC
Bare iron C programming on a Xilinx Microblaze soft core. RTOS C programming on a PowerPC running VxWorks. LabVIEW modelbased design with code generation.
¢
¢
RS-232 Serial
SD card
CAN
USB
Ethernet
Lee, Berkeley 10
The “Harry Potter” Approach to Embedded Software Design (Bare Iron Level)
On an Atmega 168 (a popular 8-bit microcontroller):
// Set timer1 to generate an interrupt every 1ms TCCR1A = 0x00; TCCR1B = (_BV(WGM12) | _BV(CS12)); Expelliatmega! OCR1A = 71;
Learn the right spells, and express them with conviction...
Lee, Berkeley 11
The Emphasis on Critical Thinking (Bare Iron Level)
TCCR1B = (_BV(WGM12) | _BV(CS12)); Hunt for header files used by the compiler #define #define #define #define #define #define _MMIO_BYTE(mem_addr)(*(volatile uint8_t *)(mem_addr)) _SFR_MEM8(mem_addr) _MMIO_BYTE(mem_addr) _BV(bit) (1 << (bit)) TCCR1B _SFR_MEM8 (0x81) WGM12 3 CS12 2 C preprocessor (*(volatile uint8_t *)(0x81)) = (1 << 3) | (1 << 2);
Although TCCR1B appears to be a C variable, it is not (and cannot be, since C provides no way to force a variable to reside at a particular memory address). Evidently, C is not a perfect match for the problem at hand!
Lee, Berkeley 12
The Emphasis on Critical Thinking (RTOS Level)
Levels of abstraction for concurrent programs. Critical thinking requires understanding pitfalls of scheduling and locks.
Lee, Berkeley 13
A Scenario
Under Integrated Modular Avionics, software in the aircraft engine continually runs diagnostics and publishes diagnostic data on the local network.
Proper software engineering practice suggests using the observer pattern.
An observer process updates the cockpit display based on notifications from the engine diagnostics.
Lee, Berkeley 14
#include <pthread.h> ... int value; pthread_mutex_t lock; void addListener(notify listener) { pthread_mutex_lock(&lock); ... add the listener to the list ... pthread_mutex_unlock(&lock); }
Threads: the Prevailing Concurrency Model
A carefully constructed “thread safe” multitasking solution. It turns out it carries risk of lurking errors… If multiple threads call update(), the updates will occur in some order. But there is no assurance that the listeners will be notified in the same order. Listeners may be mislead about the “final” value.
void update(int newValue) { pthread_mutex_lock(&lock); value = newValue; ... copy the list of listeners ... pthread_mutex_unlock(&lock); ... notify the listeners on the copy ... } int main(void) { pthread_mutex_init(&lock, NULL); ... start diagnostic & observer threads. }
Lee, Berkeley 15
Recall the Scenario
Under Integrated Modular Avionics, software in the aircraft engine continually runs diagnostics and publishes diagnostic data on the local network.
Proper software engineering practice suggests using the observer pattern.
An observer process updates the cockpit display based on notifications from the engine diagnostics.
Lee, Berkeley 16
The Emphasis on Critical Thinking (Model-Based Design Level)
Levels of abstraction for concurrent programs. Critical thinking requires understanding concurrent models of computation.
Lee, Berkeley 17
Model-Based Design
Accelerometer update loop (200 Hz)
Emphasis on concurrency and timing. Lab experience with LabVIEW, classroom discussion of other model-based design formalisms.
alpha 0.25
lowpass (exponential moving average) filter input output = (1 - alpha) sum * sum + alpha * input; alpha input output = (1 - alpha) sum * sum + alpha * input; alpha output output
5
accel x accel y
stop iRobot sensor update loop (67 Hz) iRobot sensor interval (ms) 15 sensor stream align delay (ms) 1 iRobot Sensor Stream Read (all sensors).vi sensors If a packet is read, delay until next packet should arrive; otherwise, wait a short period to see if a packet has arrived (aligning with the stream)
stop
Control loop (40 Hz)
25
y offset (V) x offset (V) accel x accel y +1g offset (V) uphill angle (rad)
interpret acccerometer
Cal Climber State Machine.vi iRobot Drive Direct.vi stop
Tilt Threshold (g) 0.1 sensors Max Wheel Speed (mm/s) 250 Speed Increment (mm/s^2 5
Lee, Berkeley 18
Capstone Projects
¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢
Cegway-like two-wheel robot Distributed Pacman Cooperative self-parking vehicles Face-tracking quadrotor Robotic convoys Elevator operator Automatic xylophone Dataglove gesture replicator Gesture-driven robot steering Mapping and localization Robotic summo wrestling …
Lee, Berkeley 19
Capstone Projects
Lee, Berkeley 20
The Canon
Teachers should teach what they know.
Actually, the most valuable teachers are the ones who teach what is not known…
Lee, Berkeley 21
Conclusion
Our job isn't to get our students to replicate us. Our job is to get our students to replace us. If we succeed, our students will make us obsolete. If we fail, their students will make us obsolete.
Lee, Berkeley 22
Backup Slides
Lee, Berkeley 23
Applications First? Or Foundations First?
Bottom-up: - foundations first - derive the applications
Top-down: - applications first - derive the foundations
Lee, Berkeley 24
Class Projects are Defined by the Students. Example:
May 16, 2008
One of the five project teams in 2008 developed a balancing robot inspired by the Segway. They used a Nintendo Wiimote as a controller communicating with a PC running LabVIEW, communicating with a Lego Mindstorm NXT, which they programmed in C.
Lee, Berkeley 25
Modeling Physical Dynamics
Lee, Berkeley 26
Actor Model of Systems
A system is a function that accepts an input signal and yields an output signal. The domain and range of the system function are sets of signals, which themselves are functions. Parameters may affect the definition of the function S.
Lee, Berkeley 27
State Machines and Modal Models
Modal models combine such actor models with state machines, where each state of the machine represents a mode of operation.
Lee, Berkeley 28