Transcript Design of Fault Tolerant Data Flow in Ptolemy II

Design of Fault Tolerant Data Flow in
Ptolemy II
Mark McKelvin
EE290 N, Fall 2004
Final Project
Motivation
• Designers of safety critical, cost sensitive applications
commonly use block diagrams to model system component
interactions
– Block diagrams define the topology of the system and data
dependencies among components
– Components may be distributed across a hardware platform and
characterized by redundant software and hardware components to
improve reliability
• Creating design environments and tools based on a precise
models of computation to aid formal techniques, Fault Tolerant
Data Flow (FTDF)
– Examples: Deriving fault trees from a system specification,
automatically generating code on a distributed platform
Course 290N, Fall 2004
2
Fault Tolerant Data Flow
• FTDF is an experimental model of computation amenable to
describe periodic feedback control systems, i.e. controlling a
plant (Pinello, 2004)
– A data flow variant introduced as a formalism for which automatic
techniques for formal analysis and validation can be performed
• A FTDF specification is composed of functional components
(actors) and communication media (channel buffers)
Course 290N, Fall 2004
3
FTDF Semantics
• A data flow process F is computed as a sequence of firings that
are enabled by a firing rule
Actor
outputs
F, f
inputs
• f is a (possibly partial) function that must be defined for all firing
rules of an actor and is finite
• We can proceed to find a least fixed point by repeatedly firing
the actor based on its firing function such that the firing rules are
satisfied, and in doing so, we define the operational semantics
of a data flow process
• In FTDF, an actor can fire on a subset of inputs
Course 290N, Fall 2004
4
Rules of Composition
• Given a set of actors, A, and a set of communication media, M,
connecting actors, a FTDF graph, G = (V, E) where V = A and
E= M
• Legal FTDF Graph Constraints
– G contains no causality cycles
– A legal graph must start with source actors and complete a cycle
with sink actors
– All actors in graph G must execute at least once before a new cycle
begins
• FTDF tokens are exchanged on each cycle with synchronous
semantics
• Based on these constraints for composition, we can determine
the data dependencies of the Actors in the graph. It determines
the order, or schedule, which actors may fire and
communication may occur
Course 290N, Fall 2004
5
FTDF Assumptions
•
A fault event in nodes in the FTDF graph assume fail silence
– Fail silence: produces correct results or produces no results at all
•
In general, fault events could be generated due to:
– Processing element fault
– Communication media fault
– Actor fault (i.e. may be due to failure or producing invalid outputs)
However, I simplify by only assuming an actor fault since the graph is
“flattened” and no fault on communication channel
Course 290N, Fall 2004
6
Implementation
• Requirements
– 1. For each actor in a graph, a firing function is defined that
satisfies each actor’s firing rules
– 2. Construction of a “legal” FTDF graph
• Ptolemy II
– 1. If requirements above are satisfied, all actors are placed in a list
and ordered based on functional dependencies
– 2. Each actor executes according to a schedule known before
compile time
– 3. If an actor cannot fire, an Exception is thrown alerting the
designer that an actor cannot fire due to not satisfying its firing rules
Course 290N, Fall 2004
7
Conclusions and Open Issues
• Scheduler for the FTDF domain is constructed in Ptolemy II
– Programming issues and bugs with remainder of the FTDF domain
still needs resolving
• Bounded memory execution?
– Yes. Synchronous semantics ensures only one firing per cycle for
any upstream actor
• Is such a domain useful?
– Possibly adjusting FTDF behavior to other existing domains
• What if tokens arrive out of order, “late”?
• Can FTDF models be statically scheduled as in SSDF (Statically
Schedulable Data Flow)
– Its possible, but balance equations must be dynamically altered
between cycles
Course 290N, Fall 2004
8
References
C. Pinello, L. P. Carloni, and A. L. Sangiovanni-Vincentelli. Fault-tolerant deployment of embedded software for
cost-sensitive real-time feedback-control applications, Proc. Conf. Design, Automation, and Test in
Europe (DATE), 2004.
S. Edwards, L. Lavagno, E. Lee, A. Sangiovanni-Vincentelli. Design of Embedded Systems: Formal Methods,
Validation and Synthesis. Proceedings of the IEEE, vol. 85(n.3) – March 1997, p366-290.
E. A. Lee and T. M. Parks, ``Dataflow Process Networks,'', Proceedings of the IEEE, vol. 83, no. 5, pp. 773-801,
May, 1995.
E. A. Lee and D. G. Messerschmitt, ``Static Scheduling of Synchronous Data Flow Programs for Digital Signal
Processing,'' IEEE Trans. on Computers, January, 1987.
Course 290N, Fall 2004
9
Reliability Block Diagrams
• RBDs are diagrams for representing how components of a
system are arranged and structurally connected in terms of
reliability
B
A
1/2
D
C
• Commercial Tools: Relex RBD (Relex Software Corporation),
BlockSim (ReliaSoft)
Course 290N, Fall 2004
10