Transcript Communication-Aware Allocation and Scheduling Framework

Dependable communication
synthesis for distributed
embedded systems
Nagarajan Kandasamy, John P. Hayes, Brian T. Murray
Presented by John David Eriksen and Jamie Unger-Fink
Overview
• Real-time distributed systems
▫
▫
▫
▫
Network
Sensors
Processors
Actuators
• Requirements
▫ Strict performance targets
▫ Fault-tolerance
▫ Safety-critical operation
Related Work
• Network Protocols
▫ Controller Area Network protocol (CAN)
 Common protocol used in embedded systems networks.
 Messages scheduled using variable priority levels
▫ Time-Division Multiple Access (TDMA)
 Time-multiplexed frame-based protocol
• Network topology considerations
▫ Fixed network topology assumption
▫ Synthesize topology given application requirements
 Can be accomplished using a task graph model
 Can be accomplished assuming a CAN or TDMA network
protocol
TDMA Overview
• Time-Division Multiple Access (TDMA) communication protocol
▫ Faster than CAN
▫ Used in this paper TTP and FlexRay networking protocols
TDMA in FlexRay
• A round is a set of identical-sized slots determined by a given
communication schedule.
• A processor Pj is allocated one or more sending slots during a
round.
• Number of slots and size of slots determined by designer.
• A processor can only place messages in the slots allocated to it.
Topology Overview
• Topology restricted to multiple-bus systems
• Multiple-buses used for fault tolerance and to spread larger
communication loads – network media typically low-bandwidth and
inexpensive.
• Each processor connects to subset of communication buses
• Coprocessor attached to each processor handles message
communication without interrupting process execution
Summary of Approach
• Target: a low-cost and reliable communication
network
• Use a set of distributed applications modeled as
task graphs {Gi}.
• Allocated messages to minimum number of
buses {Bj} where each Bj has a fixed bandwidth.
Summary of Approach
• Target a generic TDMA protocol (FlexRay)
• Assume a multi-rate system where each graph Gi may have a
different execution period period(Gi)
• Support dependable message communication by establishing
redundant transmission paths between between processors.
• Maintain efficient network usage by reusing transmission slots
allotted to a given processor between multiple messages sent by it.
Topology Development
• How is final number of necessary buses
determined?
▫ Initially, each message is assigned its own bus.
▫ Iterative clustering heuristic used to minimize the
number of buses used.
 Clustering is NP-complete
 Clustering heuristic SYNTH({mi}) used instead
Topology Development
Message Clustering
• SYNTH({mi})
▫ Cluster synthesis
▫ Group message mi with existing cluster Cj if:
 No two replicas of one k-FT message is allocated to Cj
 All messages in Cj continue to meet deadlines.
 Length of Cj communication schedule does not exceed application
specifications.
 Memory size of Cj communication schedule must fit in memory size of
communication network co-processor.
 This grouping process is considered to be a bin-packing problem (NPComplete) so a heuristic used.
▫ Results in efficient use of bus bandwidth through sharing and re-use of
transmission slots between multiple messages whenever possible.
▫ Each cluster assigned to separate bus in final topology.
Task Deadline Assignment
• Task scheduling range [ri, di]
▫ ri – Release (start) time
▫ di – Deadline
• Deadline computation
▫ NP-Complete
▫ Hueristic used instead (Natale and Stankovic)
Task Scheduling
a)
b)
c)
d)
Initial task graph with execution times parenthesized and fixed
execution period of 2000 microseconds.
Path selection and slack allocation.
Path {T1,T2,T4,T5} scheduled and removed. {T3} then scheduled.
Final release/deadline scheduling range.
Task Scheduling
• Tasks assigned priorities according to the
parameters of their schedule (release time and
deadline)
• A processor executes the highest-priority task
that has been released for execution
• Feasible only if:
▫ All tasks can complete by their deadlines
▫ All messages can be received by their deadlines
Case Study
• Applications modeled
▫ Adaptive cruise control - Maintain safe following distance behind
moving car
▫ Electric Power Steering - Provide steering assistance
▫ Traction Control - Maintain intended path on slippery terrain
Case Study Parameters
•
•
•
•
•
Bus bandwidth of 250 KB/s
Transmission slot width of 50 microsec.
Max number of slots 16
Slot reuse on or off
Round lengths fixed at three different sizes: 12,
16, and 10.
• Round lengths are harmonic multiples of three
base periods: 3, 4, and 5.
Case Study Results
• No slot reuse yielded designs with less free slots that can be used for
non-critical messages.
• Slot reuse yielded more free slots.
• Optimal solution used a period base 4 and yielded solution with
three buses and plenty of free slots.
Conclusion
• Synthesis of low-cost TDMA communication
network for distributed system showed to be
feasible.
▫ Proven via formal mathematical proofs.
▫ Demonstrated via realistic case study.
• Future work:
▫ Message scheduler on co-processors not part of
this design.
▫ Fault-tolerant allocation of tasks to processors
not addressed.