Synchronous Reactive Systems

Stephen Edwards
sedwards@synopsys.com

Synopsys, Inc.

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Outline
• Synchronous Reactive Systems
• Heterogeneity and Ptolemy
• Semantics of the SR Domain
• Scheduling the SR Domain

2

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Reactive Embedded Systems
• Run at the speed of their environment
• When as important as what
• Concurrency for controlling the real world
• Determinism desired
• Limited resources (e.g., memory)
• Discrete-valued, time-varying
• Examples:
– Systems with user interfaces
∗ Digital Watches
∗ CD Players
– Real-time controllers
∗ Anti-lock braking systems
∗ Industrial process controllers

3

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

The Digital Approach
Why do we build digital systems?
• Voltage noise is unavoidable
• Discretization plus non-linearity can filter out
low-level noise completely
• Complex systems becomes predictable and
controllable
• Incredibly successful engineering practice

4

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

The Synchronous Approach
Idea: Use the same trick to filter out “time noise.”
• Noise: Uncontrollable and unpredictable
delays
• Discretization ⇔ global synchronization
• The synchrony hypothesis:
Things compute instantaneously

• Already widespread:
– Synchronous digital systems
– Finite-state machines

5

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

The Synchronous Model of Time
• Synchronous: time is an ordered sequence of
instants
• Reactive: Instants initiated by environmental
events

System responds to each instant
Time
Nothing happens between instants

• A system only needs to be “fast enough” to
simulate synchronous behavior

Time

6

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Who Uses This Stuff?
• Virtually all digital logic designed this way
• In software,
– Dassult (French aircraft manufacturer)
builds avionics with synchronous software
– Polis (Berkeley HW/SW codesign project)
uses Esterel for specifying EFSMs
– Cadence built product (Cierto VCC) based
on Polis
– TI exploring using synchronous software
for specifying/simulating DSPs

7

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Outline
• Synchronous Reactive Systems
• Heterogeneity and Ptolemy
• Semantics of the SR Domain
• Scheduling the SR Domain

8

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Heterogeneity
Why are there so many system description
languages?
• Want a succinct description for my system.
• “Let the language fit the problem”
Bigger systems have more diverse problems; use
a fitting language for each subproblem.
Want a heterogeneous coordination scheme that
allows many languages to communicate.

9

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Heterogeneity in Ptolemy
Ptolemy: A system for rapid prototyping of
heterogeneous systems
A Ptolemy domain (model of computation):
• Set of blocks:
Atomic pieces of computation that can be
“fired” (evaluated).
A

C

D

B
• Scheduler:
Determines block firing order before or during
system execution.
A

B

C

D

10

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Schedulers Support
Heterogeneity
• Scheduler does not know block contents, only
how to fire
• Block contents may be anything
• “Wormhole”: A block in one domain that
behaves as a system in another
• Hierarchical heterogeneity: Any system may
contain subsystems described in different
domains

11

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Outline
• Synchronous Reactive Systems
• Heterogeneity and Ptolemy
• Semantics of the SR Domain
• Scheduling the SR Domain

12

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

The SR Domain
• Reactive systems need concurrency
• The synchronous model makes for
deterministic concurrency
– No “interleaving” semantics
– Events are totally-ordered
– “Before,” “after,” “at the same time” all
well-defined and controllable
• Embedded systems need boundedness;
dynamic process creation a problem
• SR system: fixed set of synchronized,
communicating processes

13

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

The SR Domain (2)
Zero-delay blocks
Instantaneous communication
with feedback

Single driver, multiple receiver channels
• Block functions may change between instants
for time-varying behavior
• Blocks may be specified in any language

14

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Zero Delay and Feedback
How to maintain determinism?

A

B

Which goes first?
Need an
order-invariant
semantics

Contradictory!
Need to attach
meaning to such
systems.

15

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Dealing with Feedback
Why bother at all?
Answer: Heterogeneity
• Cycles are usually broken by delay elements
at the lowest level
• Some schemes insist on this
• False feedback often appears at higher levels
• Data dependent cycles can appear when
sharing resources
• Virtually all cycles are “false,” yet must be
dealt with.

16

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Fixed-point Semantics are Natural
for Synchronous Specifications
with Feedback
Why a fixed point?
Self-reference:
The essence of a cycle
f (xt ) = xt
System function

Vector of signals

(composition of

at time t

block functions)

(zero delay)

fixed point ⇐⇒ stable state

determinism ⇐⇒ unique solution
17

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Unique Least Fixed Point
Theorem
A monotonic function on a complete
partial order (with ⊥) has a unique
least fixed point.

What does it mean to make the system function f
monotonic and the signal values a CPO?

18

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

The Least Fixed Point of What?

A

C
I
B

f

O

D

Interpret as &

% Take LFP
B(I, f (I)) = f (I)
B

I

A
O

B

O

C
D

19

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Vector of Signals is a CPO
Values along an upward path grow more defined.
1

0

More Defined

⊥

Incomparable

“Undefined”
element

Less Defined

11

01

10

00

⊥1

1⊥

0⊥

⊥0

vector-valued extension

⊥⊥
Formally, x v y if y is at least as defined as x.

20

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Adding ⊥ Is Enough
Any set {a1 , a2 , . . . , an , . . .} can easily be “lifted” to
give a flat partial order:
a1

a2

a3

···

an

···

⊥
A CPO for signals with pure events:
absent

present

⊥
A CPO for valued events:
absent v1

v2

···

vn

···

⊥
Why not absent v present?
present A then ... else ... end
Violates monotonicity
21

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Monotonic Block Functions
Giving a more defined input to a monotonic
function always gives a more defined output.
f ( f ( f ( f (⊥))))

f ( f ( f (⊥)))
f ( f (⊥))
f (⊥)
⊥
Formally, x v y implies f (x) v f (y).
A monotonic function never recants (“changes its
mind”).

22

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Many Languages Use Strict
Functions, Which Are Monotonic
A strict function:
g(. . . , ⊥, . . .) = (⊥, . . . , ⊥)
| {z }
| {z }
outputs
inputs
Outside:
A strict
monotonic
function

Inside:
Simple
“function call”
semantics

Most common imperative languages only
compute strict functions.
Danger: Cycles of strict functions
deadlock—fixed point is all ⊥—need some
non-strict functions.
23

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Outline
• Synchronous Reactive Systems
• Heterogeneity and Ptolemy
• Semantics of the SR Domain
• Scheduling the SR Domain

24

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

A Simple Way to Find the Least
Fixed Point
⊥ v f (⊥) v f ( f (⊥)) v · · · v LFP = LFP = · · ·
For each instant,
1. Start with all signals at ⊥
2. Evaluate all blocks (in some order)
3. If any change their outputs, repeat Step 2
f0 a

f1

b

f2

c

(a, b, c) = (⊥, ⊥, ⊥)
f0 (⊥, ⊥, ⊥) = (0, ⊥, ⊥)
f1 (0, ⊥, ⊥) = (0, 1, ⊥)
f2 (0, 1, ⊥) = (0, 1, 0)
f2 ( f1 ( f0 (0, 1, 0))) = (0, 1, 0)
25

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

The Dependency Graph
Transform into single-output functions:
1

A

2

C
3

B

4

5

6

D

7

⇓
1
2

5
3

6

4

7

26

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

The Scheduling Algorithm
1. Decompose into strongly-connected
components
2. Remove a head (set of vertices) from each
SCC, leaving a tail
3. Recurse on each tail

27

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Evaluating SCCs
Split a strongly-connected graph into a head and
tail:

H
T
↓

T

H

T

Good heads break T’s strong connectivity.

28

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Example
0

A

3

1

B

2

5

System
C

6
4

1
Graph

2

4

0
6
5

Head

3
1

2

4

0

Tail

6
5

3
29

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Schedules
1

2

4

0
6
5

3

4

0
6
5

head
z}|{

z

3
tail
}|

{

head tail
head tail
z}|{ z}|{
z}|{ z}|{
( 12 . ( 4 . 5 ) 6 ( 0 . 3 ))
{z
} |
{z
}
|
SCC
SCC
545 6 303 12 545 6 303 12 545 6 303

30

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Finding Good Heads
Must break strong connectivity—remove a border
of a set of vertices:
D
H

A
E
B
F

I

C
G
border of { A, B, C }
(vertices with incoming edges)

H

A
B

I

C
31

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Choosing Good Border Sets
Heuristic: “Grow” a set starting from a vertex and
greedily include the best border vertex:
2

5
1

Set

Border

1

5

15

23

152

3

1523

7

15237

46

152374

6

3

6

4

7

2 is better (3 would
increase border)

32

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

rs rs rs rs rs
sr rsrs rsrs rs rs rsrs
rs exact
t sweep
u
rs rs
s
r
rs rs rsrsrs
rsrs rs rs
rsrs rsrs rs
rs
rs
rs rs rs rs
s
r
s
r
s
r
rs rs
rsrs
rsrs rsrs rs
rs
s
r
s
r
tu
u
s
r
rs rs
rsrsrs u
t
t
u
t
u
t
rs u
t
tu
u
rs rs
tu
tu
t
u
t
tu
t
rsrsrsrsrs rs rsrs rs rsrsu
tu
t
u
t
u
t
u
t
u
tu
t
u
t
u
t
u
t
u
t
u
tu
u
tu
u
t
u
tu
trsu
u
tu
u
tu
u
t
u
rs u
tt
u
t
u
t
tu
u
t
u
t
t
t
u
t
t
u
rs rs rs rs rsrs rs rs rs u
t
u
t
u
t
u
t
u
t
rsu
tu
u
t
u
t
u
s
r
t
t
u
t
t
u
t
t
u
t
u
t
u
s
r
t
u
t
u
t
u
t
u
t
u
t
u
s
r
t
u
t
u
t
u
t
t
u
s
r
s
r
t
u
rs
t
t
u
tu
u
tu
tu
t
tu
u
trsu
u
t
u
tu
u
trsu
u
t
t
rs rsu
tu
trsu
u
rsu
t
u
trsu
u
t
u
t
rsu
t
rsu
t
tu
u
rsu
tu
tu
u
t
t
u
rsu
t
t
t
u
t
trsu
u
tu
t
u
t
tu
u
rsrsu
tu
trsu
u
t
rsu
trsu
t
u
t
t
u
t
rsrsu
rsu
tu
u
t
t
u
t
u
t
rsu
rsrsu
t
t
u
t
u
t
u
s
r
s
r
t
t
u
t
u
t
u
t
u
t
u
t
u
s
r
t
t
u
t
t
u
s
r
s
r
t
u
t
t
t
u
t
u
t
u
t
s
r
s
r
s
r
s
r
s
r
s
r
s
r
s
r
t
u
t
u
t
u
s
r
t
u
t
t
u
t
u
s
r
s
r
t
u
t
u
t
u
s
r
t
u
t
u
t
u
s
r
s
r
t
u
t
u
t
u
s
r
s
r
s
r
s
r
t
u
t
u
s
r
t
u
t
u
t
u
t
u
s
r
t
u
t
u
s
r
s
r
s
r
t
u
t
u
t
u
t
u
s
r
t
u
s
r
tu
rsu
t u
trsu
t u
rsrsu
t
t
rsu
rsu
trsu
trsu
t
t
trsrsu
rsu
trsu
t
tu
t
t
rsu
t
trsrsu
trsrsu
trsu
u
trsu
u
srrs

100s
10s
1s
0.1s

0

20

40

60

80

100 120

Number of Outputs
Speedup Over Exact

Time to Compute Schedule

Scheduling Results

1000×
100×
10×
1×

rsrsrs
srrsrsrsrsrsrsrsrs
rsrsrsrsrsrs
s
r
s
r
rsrs
rsrsrsrsrsrsrs
s
r
rsrsrsrsrsrs
s
r
s
r
s
r
s
r
rsrsrsrsrsrs rs
s
r
s
r
s
r
rsrsrsrsrsrsrsrs rs rs
rs
s
r
rsrsrsrsrsrsrsrsrs
s
r
s
r
rsrsrsrsrsrsrsrsrsrsrsrsrsrsrsrsrsrsrsrsrs
s
r
s
r
s
r
rsrsrsrsrs

0.1×
0.1s 1s 10s 100s
Time to Compute Exact

33

S YNCHRONOUS R EACTIVE S YSTEMS
S TEPHEN E DWARDS

The Cost of Using the Heuristic
25%20%15%10% 5% 0
Fraction of Runs

40

60

80

rs
rs
rs
rs rs
rs
rs rsrs rs
rs
s
r
s
r
s
r
rs rs
rs
s
r
rs rs
s
r
rsrs
rs
s
r
s
r
rs
rs
rs
rs
s
r
rs
rsrsrs rs rs rsrs
rs rs
s
r
s
r
rsrs
rsrs rs
rs rs rs rsrs
rs rs
s
r
s
r
rs rs rs rsrsrsrs rsrs rsrs rsrs rs rs rs
rsrs rs
rs rs rs
rs
rs rs rs rs rs
s
r
s
r
s
r
s
r
rs rsrs
rs rsrs rs rs rsrs rs
rs rs
rs sr
s
r
s
r
s
r
s
r
s
r
s
r
s
r
s
r
rs rsrsrsrsrs rsrsrs rs rsrs rsrs rsrsrsrs rs rs rs rs
rs srrs
rs
rs rs rs rs rs
rs rsrs rsrsrsrsrsrs rsrsrsrsrs rsrsrs rsrsrs rs rsrs rsrs rs rs rsrs rsrs rs

20

Number of Outputs

150%

100%

50%

0%

Increase in Cost of Schedule

34

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Asymptotic Schedule Cost
n2

Optimal Schedule Cost

1000

100

b b

10

b

n1.5

b
bbbbbb bb
b
b
bbb bbbbbbbbbbbbbbbbbb
bbbb
b b
bbbbbbbbbbbb bbbbbb
bb bbb bbbbb bbb n
b bbbbbbb bbbb
bb
b b bbbbbbbbb bb
b b bbbb bb bbb bb b
bbbbbb b
b
bbbbbbb bbbb b
b
b
b b bb b bbbb
b
b
b
b b bb
bb bb b bb
b
b bb bb
bb b
b
b b b
bb

b
b
b

1
1

10
Number of Outputs

100

35

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Conclusions
• Reactive embedded systems
– Run at the speed of their environment
– When as important as what
– Concurrent, deterministic, bounded,
discrete-valued
• The synchronous approach
– Discrete instants, globally synchronized
– Assumes instantaneous computation
• Heterogeneity in Ptolemy
– Domain: Blocks and Scheduler
– Hierarchical heterogeneity through
domain embedding

36

S TEPHEN E DWARDS

S YNCHRONOUS R EACTIVE S YSTEMS

Conclusions (2)
• The SR domain
– Concurrent zero-delay blocks
– Semantics: the least fixed point of a
monotonic function on a CPO
– Values include “undefined” (⊥)
• Scheduling the SR Domain
– Use single-output dependency graph
– Decompose into SCCs; remove a head
from each; recurse
– Head is the border of the tail
– Choose a head by greedily growing a set
of vertices
– Fast, efficient. O(n1.25 ) execution

37