exercice sheet 4 mbes

Question

Hello,

I don't really understand what changes in the 2nd exercice of the exercice sheet 4 of mbes when we remove z6. Isn't the solution for the balanced equation the same and therefore the periodic schedule too?

Answer 1

The solution of the balance equations is the same that is right, so that we can compute the same periodic schedule that would run the DPN with bounded memory. The rate vector, i.e., the T-invariant is the same in both cases. 

However, if we do not enforce a periodic schedule and allow the nodes to fire on their own, then the DPN with buffer z6 is still bounded, while without z6 is it not. That is checked with the existence of a positive S-invariant. With buffer z6, there are the S-invariants (1,2,0,0,0,0), (0,0,4,2,0,0) and (1,0,-2,0,2,2) whose sum is (2,2,2,2,2,2) and that is a positive S-invariant so that that DPN is bounded for ALL schedules. Without z6, we just have S-invariants (1,2,0,0,0) and (0,0,4,3,0) whose linear combinations all have a 0 entry in the final component. Hence, buffer z5 may overflow if nodes a,d fire faster than nodes b,c.

Try the teaching tool https://es.cs.uni-kl.de/tools/teaching/DataflowStaticScheduling.html

with buffer z6

(z1:4,z2:4,z3:4,z4:4,z5:4,z6:4) = init()
(z2:0:1:0:1:0:1,z5:1:0:1:0:1:0) = a(z1:1:1:1:1:1:1)
(z4:1:1) = b(z3:0:1,z5:1:0)
(z3:0:1:0:1,z6:1:0:1:0) = c(z4:1:1:1:1)
(z1:1:1) = d(z2:0:1,z6:1:0)

and without z6:

(z1:4,z2:4,z3:4,z4:4,z5:4) = init()
(z2:0:1:0:1:0:1,z5:1:0:1:0:1:0) = a(z1:1:1:1:1:1:1)
(z4:1:1) = b(z3:0:1,z5:1:0)
(z3:0:1:0:1) = c(z4:1:1:1:1)
(z1:1:1) = d(z2:0:1)