The
Fixed Logical Execution Time (FLET)
Assumption
Tom Henzinger
of California, Berkeley
University
The History of Computer Science:
Lifting the Level of Abstraction
High-level languages:
Programming to the application
Compilation:
perhaps “the” success
story of computer science
The “assembly age”:
Programming to the platform
It is feasible to
abstract the platform.
The History of Computer Science:
Lifting the Level of Abstraction
Automatic program synthesis:
No more programming
Code generation
from specifications:
still mostly a dream
High-level languages:
Programming to the application
It is not feasible to
abstract algorithms
and data structures.
Compilation:
perhaps “the” success
story of computer science
The “assembly age”:
Programming to the platform
It is feasible to
abstract the platform.
Current Practice in Embedded Software Design
Some automatic
code generation from models
-often inefficient
-often unpredictable
-e.g. Real-Time Workshop
Some manual
programming to the platform
-difficult to reuse
-difficult to verify
-requires systems experts
Current Practice in Embedded Software Design
Mathematical models
(e.g. Simulink)
Code
generation
difficult
Code
verification
difficult
Efficient code
(scheduled by RTOS)
Advocated Practice in Embedded Software Design
Mathematical models
(e.g. Simulink)
The missing link:
platform-independent programming model
Efficient code
(possibly schedule-carrying)
Advocated Practice in Embedded Software Design
Mathematical models
(e.g. Simulink)
Verification
The missing link:
platform-independent programming model
Compilation
Efficient code
(possibly schedule-carrying)
Advocated Practice in Embedded Software Design
Mathematical models
(e.g. Simulink)
Verification
The missing link:
platform-independent programming model
Compilation
Efficient code
(possibly schedule-carrying)
-verifiable
-reusable
-efficiently implementable
Advocated Practice in Embedded Software Design
Mathematical models
(e.g. Simulink)
Verification
The missing link:
platform-independent programming model
Compilation
Efficient code
(possibly schedule-carrying)
-verifiable
-reusable
-efficiently implementable
Reusable =
composable + portable
Advocated Practice in Embedded Software Design
Requirement
A
Program
A
Platform
P
+
Requirement
B
+
Program
B
Compositionality
Advocated Practice in Embedded Software Design
Requirement
A
Program
A
Platform
P
+
Requirement
B'
+
Program
B'
Compositionality
Advocated Practice in Embedded Software Design
Requirement
A
Program
A
Platform
P
Portability
Platform
Q
Advocated Practice in Embedded Software Design
Mathematical models
(e.g. Simulink)
-concurrency
-environment time
Verification
The missing link:
platform-independent programming model
Compilation
Efficient code
(possibly schedule-carrying)
-distribution
-platform (CPU) time
Advocated Practice in Embedded Software Design
Mathematical models
(e.g. Simulink)
-concurrency
-environment time
Verification
The missing link:
platform-independent programming model
-concurrency
-environment time
Compilation
Efficient code
(possibly schedule-carrying)
-distribution
-platform (CPU) time
Advocated Practice in Embedded Software Design
Mathematical models
(e.g. Simulink)
-descriptive
-mathematics / logic
Verification
The missing link:
platform-independent programming model
-concurrency
-environment time
Compilation
Efficient code
(possibly schedule-carrying)
-prescriptive
-algorithms + data structures
Advocated Practice in Embedded Software Design
Mathematical models
(e.g. Simulink)
-descriptive
-mathematics
Verification
The missing link:
platform-independent programming model
-concurrency
-environment time
-prescriptive
-virtual machine
Compilation
Efficient code
(possibly schedule-carrying)
-prescriptive
-algorithms + data structures
Advocated Practice in Embedded Software Design
Mathematical models
(e.g. Simulink)
e.g.
What is the control equation?
What is the sampling rate?
Verification
The missing link:
platform-independent programming model
e.g.
Which procedure computes
the control equation?
Which event triggers the
computation?
Compilation
Efficient code
(possibly schedule-carrying)
e.g.
Which CPU executes the
control procedure?
What priority has the
execution?
First Attempt
Mathematical models
(e.g. Simulink)
The missing link:
platform-independent programming model
Efficient code
(scheduled by RTOS)
Priorities
First Attempt
Mathematical models
(e.g. Simulink)
Programming model:
Priorities
Efficient code
(scheduled by RTOS)
Not sufficiently abstract
-not about environment time
-not compositional
First Attempt
Mathematical models
(e.g. Simulink)
Correctness?
Scheduling theory
Programming model:
Priorities
Efficient code
(scheduled by RTOS)
Not sufficiently abstract
-not about environment time
-not compositional
Efficiency!
Second Attempt
Mathematical models
(e.g. Simulink)
The missing link:
platform-independent programming model
Efficient code
(scheduled by RTOS)
Synchrony
assumption:
platform time
infinitely faster than
environment time
Second Attempt
Mathematical models
(e.g. Simulink)
Synchronous programming languages
(Esterel, Lustre, Signal, etc.)
Efficient code
(scheduled by RTOS)
Too abstract
difficult to compile to
resource-constrained,
distributed platforms
Second Attempt
Mathematical models
(e.g. Simulink)
Synchronous programming languages
(Esterel, Lustre, Signal, etc.)
Efficient code
(scheduled by RTOS)
Correctness!
Too abstract
difficult to compile to
resource-constrained,
distributed platforms
Efficiency?
Our Attempt
Mathematical models
(e.g. Simulink)
The missing link:
platform-independent programming model
Efficient code
(possibly schedule-carrying)
FLET
assumption:
-verifiable
-efficiently implementable
-composable
-portable
The FLET (Fixed Logical Execution Time) Assumption
Software Task
read sensor
input at time t
write actuator
output at time
t+d, for fixed d
The FLET (Fixed Logical Execution Time) Assumption
Software Task
read sensor
input at time t
d>0 is the
task's "logical
execution time"
write actuator
output at time
t+d, for fixed d
The FLET Programming Model
The programmer specifies d (could be any event)
to solve the problem at hand.
The compiler ensures that d is met on a given
platform (hardware resources and performance);
otherwise it rejects the program.
The FLET (Fixed Logical Execution Time) Assumption
time t
possible physical
execution on CPU
time t+d
buffer output
Portability
50% CPU speedup
Composability
Task 1
Task 2
Verifiability through Predictability (Internal Determinism)
-timing predictability: minimal jitter
-function predictability: no race conditions
Contrast FLET with Standard Practice
output as soon
as ready
Contrast FLET with Standard Practice
Race
… yes but, what about the sacrifice in performance ?!
Test Case: Flight Control Software
UC Berkeley (Horowitz, Liebman, Ma, Koo, Sangiovanni-Vincentelli, Sastry).
Two connected CPUs.
Flight Control Software Architecture
Flight Control Software Architecture
200 Hz
400 Hz
200 Hz
1 kHz
Platform-independent Software Model
1. Concurrent periodic tasks:
-sensing
-control law computation
-actuating
2. Multiple modes of operation:
-navigational modes (autopilot, manual, etc.)
-maneuver modes (taxi, takeoff, cruise, etc.)
-degraded modes (sensor, actuator, CPU failures)
Platform-independent Software Model
Mode 1
Condition 1.2
Mode 2
Task S 400 Hz
Task S 400 Hz
Task C 200 Hz
Task C 200 Hz
Task A 1 kHz
Condition 2.1
Task A’ 1 kHz
Task A” 1 kHz
Mode 3
Task S 400 Hz
Task C 200 Hz
Task A 2 kHz
Mode 4
Task C’ 100 Hz
Task A 1 kHz
Platform-independent Software Model
Host code
e.g. C
Functionality.
-No time.
-Sequential.
Glue code
e.g. Giotto
Timing and interaction.
-Environment time, not platform time.
-Concurrency, not distribution.
This kind of software
is understood:
The software complexity lies in the
glue code (minimize jitter!):
Host code may (sometimes)
be generated automatically.
Giotto enables requirements-driven rather
than platform-driven glue-code programming.
1. The Giotto Programmer’s Model: Time-triggered FLET
2. The Giotto Compiler
The Giotto Programmer’s Model
Programming in terms of environment time:
Programmer’s fiction:
-time-triggered task invocation
-tasks are functions with a fixed duration
-platform offers sufficient performance
Implementation in terms of platform time:
Compiler must maintain programmer’s fiction:
-needs access to global time, no other platform requirements
-tasks may finish early, but outputs cannot be observed early
-tasks may be preempted and distributed
Functional Components
1. Units of scheduled host code (application-level tasks).
e.g. control law computation
Input ports
Output ports
Task
2. Units of synchronous host code (system-level drivers).
e.g. device drivers
Task
Task driver loads
task input ports.
Environment Timeline (defined by Giotto semantics)
Task duration
Sensor
Actuator
Driver
d
Task
Driver execution in
environment time 0.
Sensor/output
ports read.
Time t
Task execution in
environment time d.
Input ports
loaded.
Output ports
read.
Actuator/input
ports loaded.
Time t
Time t+d
Time t+d
Platform Timeline (chosen by Giotto compiler)
Sensor
Actuator
Driver
d
Task
Task on CPU.
Input ports
loaded.
Time t
Time t
Output ports
read.
Time t+d
Time t+d
Platform Independence ensures Predictability
The Giotto compiler chooses for a given platform a platform timeline
that is value equivalent to the environment timeline defined by the
Giotto semantics.
Internal Determinism:
For a given sequence of sensor readings, the corresponding
sequence of actuator settings is uniquely determined
(i.e., there are no race conditions).
Simplified Helicopter Software
10
Control
a
i
Sensors
s
5
Navigation
Actuators
Simplified Helicopter Software
10
Control
a
Actuators
i
Sensors
s
5
Navigation
Simulink / legacy design
Helicopter Software: Giotto Syntax
…
mode Flight ( ) period 10ms
Control
10
{
a
actfreq 1 do Actuator ( actuating ) ;
i
s
Navigation
taskfreq 1 do Control ( input ) ;
5
taskfreq 2 do Navigation ( sensing ) ;
}
…
Helicopter Software: Environment Timeline
Task
a
i
a
i
Control
s
s
Navigation
t
t
Block of synchronous code
(nonpreemptable)
s
Navigation
t+5ms t+5ms
t+10ms t+10ms
Scheduled tasks
(preemptable)
Single-CPU Helicopter: Platform Timeline (EDF)
Task
t
t
t+5ms
t+5ms
t+10ms t+10ms
Two-CPU Helicopter: Platform Timeline
(Time-triggered Communication)
TDMA Slot
HeliCtr
HeliNet
HeliNav
t
t
t+5ms t+5ms
t+7ms t+10ms t+10ms
Two-CPU Helicopter: Platform Timeline
(Event-triggered Communication)
Message
HeliCtr
HeliNet
HeliNav
t
t
t+5ms
t+5ms
t+10ms t+10ms
1. The Giotto Programmer’s Model
2. The Giotto Compiler
The Giotto Compiler
Functionality
Timing
Interaction
Platform
Tasks and Drivers
Native Code
Giotto Program
Platform Specification
Giotto-P
-topology (CPUs, networks)
-performance (WCETs, latencies)
-APIs (RTOSs, protocols)
Giotto Compiler
“Failure”
Executables
or
either Giotto-P overconstrained,
or compiler not smart enough
(distributed scheduling problem)
Closing the Gap: Annotated Giotto
Functionality
Timing
Interaction
Platform
Map
Tasks and Drivers
Native Code
Giotto Program
-topology (CPUs, networks)
-performance (WCETs, latencies)
-APIs (RTOSs, protocols)
-assign tasks to CPUs
-assign connections to networks
Giotto-P
Giotto-PM
Giotto Compiler
“Failure”
Executables
or
either Giotto-PM overconstrained,
or compiler not smart enough
(global scheduling problem)
Closing the Gap: Annotated Giotto
Functionality
Timing
Interaction
Platform
Map
Communication
Tasks and Drivers
Native Code
Giotto Program
-topology (CPUs, networks)
-performance (WCETs, latencies)
-APIs (RTOSs, protocols)
Giotto-P
Giotto-PM
-assign tasks to CPUs
-assign connections to networks
Giotto-PMC
-assign connections to TDMA slots (say)
Giotto Compiler
“Failure”
Executables
or
Giotto-PMC overconstrained
(local scheduling problems solvable)
Code Generation
Functionality
Timing
Interaction
Platform
Map
Communication
Native Code
Tasks and Drivers
Giotto Program
Giotto-P
-topology (CPUs, networks)
-performance (WCETs, latencies)
-APIs (RTOSs, protocols)
Giotto-PM
-assign tasks to CPUs
-assign connections to networks
Giotto-PMC
-assign connections to TDMA slots (say)
Giotto Compiler
or
VxWorks
OSEK …
“Failure”
Code Generation: The Embedded Machine
Functionality
Timing
Interaction
Platform
Map
Communication
Native Code
Tasks and Drivers
Giotto Program
Giotto-P
-topology (CPUs, networks)
-performance (WCETs, latencies)
-APIs (RTOSs, protocols)
Giotto-PM
-assign tasks to CPUs
-assign connections to networks
Giotto-PMC
-assign connections to TDMA slots (say)
Giotto Compiler
Embedded Machine code
Embedded Machine interpreter
or
“Failure”
The Embedded Machine
-a virtual machine that mediates the interaction of
physical processes (sensors and actuators) and
software processes (tasks and drivers) in real time
-the Giotto compiler can be retargeted to a new
platform by porting the Embedded Machine
The Embedded Machine
Environment
Environment Processes: environment time
Software Processes: platform time
Software
The Embedded Machine: Time is like Memory
Environment
Reactivity: programming in environment time
Embedded Machine
Schedulability: time safety checking for platform time
Software
The Embedded Machine
e.g. clock
Environment Ports
environment
triggers
sense
actuate
Embedded Machine
task
triggers
e.g. task
completion
call drivers
schedule tasks
Task Ports
Driver Ports
read
write
The Embedded Machine: Three Instructions
Call driver:
call(d)
Schedule task:
schedule(T)
T
Hand task t over to the
system scheduler (RTOS).
Execute driver d now.
Enable trigger:
future(g,B:)
g
B:
Have code B
executed as
soon as trigger
g becomes true.
Giotto Code Generation
Task
a
B1: call(actuate) a
i
call(sense)
Control
call(input)
schedule(Control)
schedule(Navigation)
future(now+5, B2:)
s relax
s
Navigation
Navigation
i
s
t
t
t+5ms t+5ms
t+10ms t+10ms
Giotto Code Generation
Task
B2: call(sense)
a
i
schedule(Navigation)
Control
future(now+5, B1:)
relax
s
s
Navigation
t
a
t
i
s
Navigation
t+5ms t+5ms
t+10ms t+10ms
Embedded Machine Code combines
Synchronous code:
-Embedded Machine instructions and drivers
-kernel context (trigger-related interrupts disabled)
Scheduled code:
-tasks
-user context (trigger-related interrupts enabled)
Real-Time Programs
Task-triggered code:
-triggers on environment and task ports
-observable behavior depends on environment and scheduler
Environment-triggered code:
-triggers only on environment ports
-observable behavior depends on environment only
All Giotto programs result in environment-triggered code.
Real-Time Programs
Time-safe code:
No driver accesses a scheduled task before completion.
Time-live code:
There is no infinite synchronous computation.
All Giotto programs result in time-live code.
Time safety is checked by the Giotto compiler.
Alternatively, time safety violations can be can be handled through
run-time exceptions.
Real-Time Programs
Time Safety:
Violations due to combination of
-insufficient synchrony (environment events too frequent)
-insufficient platform utilization (scheduler too weak)
-insufficient platform performance (hardware too slow)
Our approach systematically integrates
synchronous programming and scheduling theory.
Distributed Giotto Compiler
Giotto
Program
Giotto Compiler
E Code
Distributed Giotto Compiler
Giotto
Program
Giotto-P
Platform Spec
Giotto Compiler with
Time Safety Checker
E Code
Proof of Time Safety
= Schedule
Schedule-Carrying Code
Giotto
Program
Giotto-P
Platform Spec
Giotto Compiler with
Time Safety Checker
E Code + Proof of Time Safety
(Schedule)
Schedule-Carrying Code
Giotto
Program
Giotto-P
Platform Spec
Giotto Compiler with
Time Safety Checker
E Code + S Code
(Executable Schedule)
Giotto Code Generation
Task
a
B1: call(actuate)
a
i
call(sense)
Control
call(input)
schedule(Control)
schedule(Navigation)
future(now+5, B2:)
s relax
s
Navigation
Navigation
i
s
t
t
t+5ms t+5ms
t+10ms t+10ms
Giotto EDF Schedule Generation
Task
a
B1: call(actuate)
a
i
call(sense)
Control
call(input)
schedule(Control)
schedule(Navigation)
future(now+5, B2:)
s dispatch(Navigation,
s
now+5)
Navigation
Navigation
dispatch(Control,
now+5)
idle(now+5)
i
s
t
t
t+5ms t+5ms
t+10ms t+10ms
Advantages of SCC (Schedule-Carrying Code)
Advantages of PCC:
-schedule generation is harder than schedule validation
(nonpreemptive or distributed case: NP-hard vs. linear)
-once generated, schedule can be reused
-compiler does not need to be trusted
Advantages of SCC (Schedule-Carrying Code)
Advantages of PCC:
-schedule generation is harder than schedule validation
(nonpreemptive or distributed case: NP-hard vs. linear)
-once generated, schedule can be reused
-compiler does not need to be trusted
Advantages of Executability:
-flexible scheduling scheme
-no system scheduler (RTOS) necessary
-overhead reduction of up to 80%
The Giotto Project
www.eecs.berkeley.edu/~tah/giotto
Software Tools:
Simulink to Giotto translator (Pree)
Giotto to E code compiler (Kirsch)
E Machine on Linux, VxWorks, OSEK (Kirsch)
S code time safety checker (Matic)
Integrated E and S machine on StrongARM (Kirsch, Sanvido)
Event-triggered xGiotto (Ghosal, Sanvido)
Applications:
Lego Mindstorms (Horowitz, Kirsch, Majumdar)
Zurich helicopter (Kirsch, Sanvido)
Berkeley helicopter (Horowitz, Liebman, Ma, Sastry)
BMW electronic throttle control (Kirsch, Pree)
GIOTTO:
FLET for periodic tasks with time-triggered mode switching
Mode 1
Mode 2
Task S Task
C Condition
1.2
xGIOTTO:
General (event-triggered) FLET programming
1. Schedule Instruction:
schedule Task by Event ;
logical deadline
2. Reaction Block:
react {
when Event do Block ;
whenever Event do Block ;
begin … end ;
} until Event ;
xGIOTTO:
General (event-triggered) FLET programming
If all events can happen at any time, then few
programs would be time-safe.
However, nested reaction blocks can be used
for event scoping
(i.e., not all events are listened to all the time).
xGIOTTO:
General (event-triggered) FLET programming
If all events can happen at any time, then few
programs would be time-safe.
However, nested reaction blocks can be used
for event scoping
(i.e., not all events are listened to all the time).
xGiotto = Structured Real-Time Programming
The Giotto Project
www.eecs.berkeley.edu/~tah/giotto
Participants:
Ben Horowitz
Arkadeb Ghosal
Christoph Kirsch
Slobodan Matic
Marco Sanvido
Sponsors:
DARPA SEC (Software-Enabled Control)
NSF CHESS (Center for Hybrid & Embedded Software Systems)
Descargar

Slides - UIC - Computer Science