Consider the following Timed Dataflow Graph.
(3 pts) Make the graph deadlock free by adding one initial token to a channel, in such a way that the following schedule is valid for the new graph.
\(\sigma(A, 0) = 3\) \(\sigma(A, 1) = 13\) \(\sigma(A, 2) = 25\) \(\sigma(B, 0) = 1\) \(\sigma(B, 1) = 10\) \(\sigma(B, 2) = 21\) \(\sigma(C, 0) = 20\) \(\sigma(C, 1) = 17\) \(\sigma(C, 2) = 30\) \(\sigma(D, 0) = 7\) \(\sigma(D, 1) = 17\) \(\sigma(D, 2) = 30\) (3 pts) Give the self-timed schedule \(\sigma_2\) for the first three iterations of the new graph, assuming that the added initial token is available at time 0.
(1 pts) Determine the makespan of the schedule of Item b.
(3 pts) What are the possible values of the throughput of Actor \(A\) in a valid schedule, \(\sigma_3\), of the deadlock-free graph in which \(\sigma_3(D, k)=15+10\cdot{}k\) for all \(k\in{}\mathbb{N}\).
(4 pts) Compute the following event sequences: \[[10, 10]^1\] \[-5 \otimes [0, -\infty{}, 10]\] \[[0, -\infty{}, -\infty{}] \oplus [-\infty{}, 10, 20]\] \[[0, 2, 4] \otimes [-\infty{}, 10, 10, 20, 20]\]
(4 pts) Consider a max-plus-linear and index-invariant system \(S\) with a single input \(i\) and a single output \(o\). The impulse response of \(S\) is \[ h_{i,o} = [0, 0, 6, -\infty{}, -\infty{}, -\infty{}, \ldots{}]\]
If input \(i\) to system \(S\) is equal to \[i=[1,2,3, 4, 5]\] compute the output event sequence \(o\) such that \[i\mathbin{\stackrel{S}{\longrightarrow}}o\]
(4 pts) Let input \(i'\) to system \(S\) be equal to \[i' = i \oplus [-\infty{}, -\infty{}, 10, -\infty{}, -\infty{}]\] Use the results from Item f, and the superposition principle to determine the output event sequence \(o'\) such that \[i'\mathbin{\stackrel{S}{\longrightarrow}}o'\]
(5 pts) Consider the following max-plus matrix \({\textrm{\bf{}{M}}}\).
\[ {\textrm{\bf{}{M}}} = \begin{bmatrix}{1}&{2}&{3}&{4}\\{1}&{-\infty{}}&{3}&{-\infty{}}\\{1}&{-\infty{}}&{-3}&{0}\\{-\infty{}}&{-2}&{-\infty{}}&{0}\\\end{bmatrix} \]
Determine the largest eigenvalue of the matrix \({\textrm{\bf{}{M}}}\) and determine a normal eigenvector for this eigenvalue.
Answers
(3 pts) An initial token is needed on the cycle between the actors \(A\)–\(D\)–\(B\) to make the graph deadlock free. The given schedule satisfies the channel constraints for the channels \(B\)–\(A\) and \(A\)–\(D\) without initial tokens, but not for channel \(D\)–\(B\). With one initial token, the constraints for channel \(D\)–\(B\) are satisfied, so that is where we need to add the initial token. Note that also the constraints for channel \(A\)–\(C\) are satisfied.
Grading:+1 for adding a token that makes the graph deadlock free.
+2 for a solution that makes the schedule valid.(3 pts)
The self-timed schedule is as follows.
\(\sigma(A, 0) = 1\) \(\sigma(A, 1) = 7\) \(\sigma(A, 2) = 13\) \(\sigma(B, 0) = 0\) \(\sigma(B, 1) = 6\) \(\sigma(B, 2) = 12\) \(\sigma(C, 0) = 4\) \(\sigma(C, 1) = 10\) \(\sigma(C, 2) = 16\) \(\sigma(D, 0) = 4\) \(\sigma(D, 1) = 10\) \(\sigma(D, 2) = 16\) Grading:+1.5 for a valid schedule.
+1.5 for the unique self-timed schedule.(1 pts) The makespan is the completion time of the last actor firing of the schedule. The makespan is \(18\) as both actors \(C\) and \(D\) complete their third firing at time \(18\).
Grading:+1 for the correct answer.
(3 pts) According to the channel constraint on channel \(A\)–\(D\), we know that for all \(k\in\mathbb{N}\), \[\sigma_3(A, k) + 3 \leq{} \sigma_3(D, k) = 15+10\cdot{}k\] \[\sigma_3(A, k) \leq{} 12+10\cdot{}k\]
According to the channel constraint on channels \(D\)–\(B\), we know that for all \(k\in\mathbb{N}\), \[\sigma_3(D, k) + 2 = 17+10\cdot{}k \leq{} \sigma_3(B, k+1) \] and thus that for all \(k\geq{} 1\), \[7+10\cdot{}k \leq{} \sigma_3(B, k) \] According to the channel constraint on channels \(B\)–\(A\), we know that for all \(k\in\mathbb{N}\), \[\sigma_3(B, k) + 1 \leq{} \sigma_3(A, k) \] Together we have that for all \(k\geq{}1\), \[8 + 10\cdot{}k \leq{} \sigma_3(A, k) \leq{} 12 + 10\cdot{} k \]
The throughput of \(A\) is given by \[\lim_{k\rightarrow{}\infty} \frac{k}{\sigma_3(A, k)}\]
Hence, the throughput of \(A\) can only take the value \(\frac{1}{10}\).
Grading:+1 for an answer that includes the possible throughput of \(\frac{1}{10}\).
+1 for the final answer that it can only be \(\frac{1}{10}\).
+1 for a valid reasoning or proof.(4 pts)
The results are: \[[-\infty{},10,10]\] \[[-5, -\infty{}, 5]\] \[[0, 10, 20]\] and \[[-\infty{}, 10, 12]\]
Grading:+1 for correct expression 1.
+1 for correct expression 2.
+1 for correct expression 3.
+1 for correct expression 4.(4 pts)
The result is the convolution of the input and the impulse response: \[[1,2,3,4,5]\otimes[0,0,6,-\infty{},-\infty{}, \ldots] = [1, 2, 7, 8, 9]\]
Grading:+2 for knowing that the output is the convolution between input and impulse response.
+2 for a correctly computed result.(4 pts)
From the superposition principle we know that \(o' = o\oplus o''\), where \[[-\infty{}, -\infty{}, 10, -\infty{}, -\infty{}] \mathbin{\stackrel{S}{\longrightarrow}} o''\] \[o'' = [-\infty{}, -\infty{}, 10, 10, 16]\] \[o' = [1, 2, 10, 10, 16]\]
Grading:+2 for a valid application of the superposition principle.
+2 for a correctly computed result.(5 pts) The precedence graph of the matrix \({\textrm{\bf{}{M}}}\) is shown below on the left. The red cycle is the cycle with the Maximum Cycle Mean, which is 2. Hence the largest eigenvalue is 2. On the right the precedence graph of \(-\lambda\otimes{\textrm{\bf{}{M}}}\) is shown.
Determining the longest paths starting from node \(x_3\) on the critical cycle leads to the eigenvector \([1~1~0~-3]^T\). The corresponding normal eigenvector is \([0~0~-1~-4]^T\).
Grading:+1 for a correct precedence graph of \({\textrm{\bf{}{M}}}\).
+1 for a correctly identified MCM / eigenvalue.
+1 for the precedence graph of \(-\lambda\otimes{}{\textrm{\bf{}{M}}}\).
+1 for a correct eigenvector.
+1 for a normal eigenvector.
