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要满足确定性的话，必须满足所有通道的历史进程只和历史的输入有关
F(X)函数的行为与时间无关。
Algorithm 1的输出取决于输入的先后顺序，不满足单调性，确定性。
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短的输入优先，这样就会导致L1[X]和L2[X]同时
到达时，若L1[X]>L2[X]，则L1[X]会进入等待。
所以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
定义各个进程的功能：
- "+"： 将两个输入的variables相加：
for (;;)
{
a:=wait(in.1);
b:=wait(in,2);
send(a+b,out);
}
- "C": 常量，设置输入等于输出：
for (;;)
{
a:=wait(in);
send(a,out);
}
- "D": 复制，将一份输入复制成两份相同的输出：
for (;;)
{
a:=wait(in);
send(a,out.1);
send(a,out.2);
}
- "S": 输出结果，只有一个输入，等待n次过后的最终f(n):
for (;;)
{
wait(in);
}
f(n)计算
n = (n-1) +1
使用"C1"（常量1）
"Cn"(当前常量n)，"+"(Cn = Cn-1 + 1), "D"将输出复制
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
