1.1 Model of Computation - Kahn Process Network(KPN)
- Model of Computation - Sychronous Data Flow
1.1.1 Examine the determinacy of there two algorithm. Prove or disprove your
conclusion. Examine the fairness of these two algorithm.
答：
Algorithm 1 是不確定的谋逻。
一個process要滿足確定性的話呆馁，必須滿足所有通道的歷史進(jìn)程只和歷史的輸入有關(guān)
F(X)函數(shù)的行為與時間無關(guān)。
Algorithm 1的輸出取決于輸入的先后順序毁兆，不滿足單調(diào)性浙滤，確定性。
Prove：
X = ([x1,x2],[?]);
X' = ([x1,x2],[x3])气堕；
顯然有X ? X'
F(X) = ([x1,x2]);
F(X') = ([x1,x3,x2]);
有F(X) ? F(X');
所以纺腊，其不滿足確定性。
Algorithm 1 滿足fairness茎芭。
即使輸入序列長度不等揖膜，但卻始終遵循FIFO
即X =([x1,x2],[x3]) → F(X) = ([x1,x3,x2])
Prove:
Algorithm 2 是確定的，同理：
X=([x1,x2],[?]);
X'=([x1,x2],[x3])梅桩；
推出 X ? X'
F(X) = ([?]);
F(X') = ([x3]);
有F(X) ? F(X');
Algorithm 2 的輸出是由輸入的長度決定的壹粟，
server短的輸入優(yōu)先，這樣就會導(dǎo)致L1[X]和L2[X]同時
到達(dá)時摘投，若L1[X]>L2[X]，則L1[X]會進(jìn)入等待虹蓄。
所以Algorithm不滿足fairness
1.1.2 Draw a Kahn process network that can generate the sequance of quadratic
numbers n(n+1)/2. Use basic processes that add two numbers, multiply two
numbers, or duplicate a number. You can also use initialization processes that
generate a constant and then simply forward their input. Finally, you can use a
sink process.
Use f(n) = n(n+1)/2 = 0+1+2+3+…+n犀呼。
Translate to recursion
f(0) = 0
f(n) = n + f(n-1) , n\>=1
定義各個進(jìn)程的功能：
- "+"： 將兩個輸入的variables相加：
for (;;)
{
a:=wait(in.1);
b:=wait(in,2);
send(a+b,out);
}
- "C": 常量，設(shè)置輸入等于輸出：
for (;;)
{
a:=wait(in);
send(a,out);
}
- "D": 復(fù)制薇组，將一份輸入復(fù)制成兩份相同的輸出：
for (;;)
{
a:=wait(in);
send(a,out.1);
send(a,out.2);
}
- "S": 輸出結(jié)果外臂，只有一個輸入，等待n次過后的最終f(n):
for (;;)
{
wait(in);
}
f(n)計算
n = (n-1) +1
使用"C1"（常量1）
"Cn"(當(dāng)前常量n)律胀，"+"(Cn = Cn-1 + 1), "D"將輸出復(fù)制
f(n) = n + f(n-1)
使用"C0"（從0開始計算f(n)宋光，用于存儲每次更新的f(n)），
"S"（等待f(n)）
1.2.1 Given the SDF graph in Figure 2.
Determine the topological matrix of these two SDF graphs
a)
a-b=0; -a+b=0;
Ma =
b)
2a-b=0; -a+b=0;
Mb =
Are these two graphs consistent?
Ma -(r2+r1)-\> [1 -1 ; 0 0] 即：R(Ma) = 1;
Mb -(r2+0.5\*r1)-\> [2 -1 ; 0 0.5] 即R(Mb)=2炭菌；
Therefore罪佳，a is consistent while b is not consistent.
If yes, determine the number of firings of each node, which leads for a peiodic
execution.How ofteneach node must fire thereby at least?
a=1
b=2
1.2.2 Given the SDF graph in Figure 3
Determine the topological matrix of this SDF graph
Quelle - DCT = 0;
DCT - Q = 0;
Q - RLC = 0;
RLC - 77C = 0;
C - R = 0;
77R - Q = 0;
M =
Examine the consistency
M -(r6+r3)-\> R(M) = 6
Therefore, it's consistent.
Determine the relative number of node firings, which leads for periodic
execution at node firings.
Quelle: 77 DCT: 77 Q: 77 RLC: 77 C: 1 R: 1
