Transcript Jean-Vivien Millo: Static Scheduling in Process

Periodic scheduling in
process network
Application to latency insensitive design
Jean-Vivien MILLO, EPI AOSTE
Synchron 2008, 2 December 2008
2
SoC design
• Designers make IP.
• Builders get together IPs in a SoC
• Issues:
• IPs come from differents builder. Its have to interact
• Latencies occurs in long interconnection wires
Synchronous
hypothesis
A
B
Latency
A
B
Goal
• Find a method to formally design interconnection
of SoC :
• Including Latencies
• Keeping a maximal rate
• Minimizing size of interconnection resources
• Due to embedded constraints
3
4
The method
SoC
• Synchronous model
IP1
IP2
IP3
SoC
• Asynchronous model
IP1
IP2
IP3
• Marked/Event Graph
SoC
• Resynchronized model
IP1
IP2
IP3
Plan
• Process Network: Marked Graph
• Dynamic scheduling:
Latency Insensitive Design
• Static scheduling:
Equalization
• Balanced static scheduling
Balanced binary word
5
6
Process network
Marked graph
Pre
condition
IP1
Computation
latency=3
Communication
latency=3
IP2
IP3
7
Basic notions and results
• The number of token by cycle is invariant
# tokens
• Rate of a cycle=
# latencies
• Graph rate=slowest cycle rate
8
Scheduling
• Firable node: All it’s input channel
contain a token
• An execution step: Parallel
execution of a subset of firable
node.
• ASAP execution:{firing
node}={firable node}
• State of the system=place marking.
9
Scheduling
• ASAP execution of a closed
system is periodic
• During an execution, schedule of a
node can be represented as a
binary word
• 1 means activity, 0 inactivity
10
Schedules of nodes
00111110
=
01111100
11111000
11
12
Latency Insensitive
Design
Latency insensitive design
• Solves problems of heterogeneous IP
interconnection and latencies but:
• Rate of the graph is not even maximal
• Communication resources are overrate
• It’s a Marked graph with:
• Place with capacity 2
 this implement a back pressure protocol
C=2
13
Outcome of LID
14
• Back pressure protocol needs additional control
paths
• Places of capacity 2 allow a correct behavior
but are overrate:
• Place with capacity 1 or 2 at “some places” should
be enough.
• What “some places” means ?
 Equalization Process
15
Equalization
Equalization
• Result of the PhD thesis of Julien Boucaron
• Reduce size of communication buffer and
simplify back-pressure protocol
– Statically increase the rate of fast cycle as
close as possible to the rate of the critical cycle.
– Statically schedule cycle (due to periodic
behavior)
Equalization Process: add latencies
• C1 : 5/8 and C2 :3/3
C1 is critical
•If we add an integer
•latency on C2 : 3/4
•If we add an other
latency, C2 :3/5<5/8 :
Rate of the graph is reduced
 We need fractional latency
Fractional Register
18
• It’s a wire when not hold.
• It’s a register when hold.
hold
Val_in
FR Val_out
Reg
• A simple register followed by a FR has the same
capacity than a Relay station but…
• we can add it only where we need
Equalization Process: scheduling
Symbolic simulation to find:
– FR placement (and it’s rate)
– Static schedule of nodes
– Static schedule of FR
00(01100111)*
00(11001110)*
4
11(00001111)*
01(10011101)*
00(01110110)*
11(00111011)*
10(01110110)*
Outcome of equalization
• Addition of virtual latency is use to reduce data
accumulation: 
• Symbolic simulation definitively fixes the static
schedules of the graph. Sometimes, an “other
schedule” should greatly reduce the size of
interconnection buffer: 
• The idea is good but it have to be associate to
another idea to find optimal solution.
Select the good schedule : Balanced Schedule.
Balanced schedule: example
• Agraph with 2 cycles with rate: 5/7 et 2/2.
(0011111)*
(0110111)*
(0121000)*
(0111000)*
(0110110)*
(0111110)*
(1101110)*
4
3
(0010000)*
1
(1111100)*
(1011101)*
(1100111)*
(1101101)*
(1111001)*
(0111011)*
(1110011)*
(1110110)*
Schedule are binary words said “balanced”
21
22
Balanced binary word
Balanced word
• The difference in the occurrence of the
same factor in two sub words of the same
length is bounded by 1.
U= 00100101001001
||v|1-|w|1|≤1
Rotation
• Unitary rotation :
• For all finite binary word, u (|u|=n)
– (u)=unu1u2u3…un-1
• Ex: (1001001)=1100100.
• So i =  o i-1.
• -i : The reverse rotation.
Transposition
• Unitary transposition relation:
• v is the transpose of u iff $u1,u2 such that
u=u110u2 and v=u101u2. We note v=t(u)
α is the inverse of –k modulo p
k such that v =t(u).
• "uSkp, $! vS
-k*α≡
1 mod p
p
• For all (k,p), It exist an integer α such that
uSkp,
-α(u) = t(u)
Balanced word
• Ex: (k,p)=(5,8), α=3
u=11011010
u=11011010
11010110
t(u)=11010110
11010110
-α(u)=11010110
27
Construction of a
balanced static
schedule of a graph
A new approach
• We’ll analytically compute the best schedule,
analytically build the solution and force the system
to reach this behavior
• Best schedule is a balanced schedule
28
Integer latencies insertion
•C1 : 5/8 and C2 :3/3
C1 is critical
•We add a integer latency
on C2 : 3/4
And we add…
29
FR insertion
•C1 : 5/8 and C2 :3/4
We must add a FR on a
channel of C2 independent of
C1
4
30
Compute schedules of nodes
Rate of the graphe=5/8
(k,p)=(5,8):
k
01101101 S01101011
p
P1
10110101
P1-4*a
P1
P1
11010110
P1
4
10110110
11011010
10101101
01101101
01011011
P1
P1
P1
10110110
P1
31
Compute schedules of FRs
01001011
For a FR r :
While the graph is equalized and
schedules of nodes are balanced 
Only one RF by channel is enough.
4
32
Compute state of the steady phase
?
01101011
01001011
10110101
?
11010110
?
?
?
10101101
?
10110110
11011010
?
?
?
01101101
01011011
?
10110110
?
33
Find initialization
Initial phase
00
(
00(01101011)
00
)
Steady phase
00(11010110)
01(01001011)
01
00
10(10110110)0 1
00
00(11011010)
10
00(10110101)
01(10101101)
10
10(01101101)
11
10
10(10110110)
11(01011011)
34
Conclusions
00(01101011) 00(01101011)
The construction of a balanced
scheduling in addition to integer
latency insertion results to a graph
with maximal rate and minimal
communication resources size.
00(01101011)
IP1
01(01001011)
00(10110101)
IPIP2
10(10110110)
IP3
10(10110110)
Thanks.