（4）19.092，11.97，10.0064。
答：
256K方案最优。
3.19中（3）（4）（6）（8）问
虚存实页0123
虚组000√√
1实存1√√
虚组12·0实组02√√
3·1虚3√√
虚组24·2实组1页4√√
5·35√√
虚组366√√
77√√
（a）虚页集合与实页集合的对应关系（b）对应关系表（√为有关系）
（3）
（4）通过作“实存状况图”模拟各虚块的调度情况，可获得Cache的块地址流序列。
P=
6
2
4
1
4
6
3
0
4
5
7
3
C0
4
4*
4
4
4
4*
4
4*
4*
4*
C1
1
1*
1*
1*
0
0*
5
5
5
C2
6
6*
6*
6*
6*
6
6*
6*
6*
6*
7
7*
C3
2
2
2
2
2*
3
3
3
3
3*
3
入
入
入
入
中
中
替
替
中
替
替
中
C=
2
3
0
1
0
2
3
1
0
1
2
3
此问最容易出错的地方是忽略“组相联”地址约束，将虚页装错实组。
另外没有及时标注“*”号也容易导致淘汰对象错误。
（6）H=4/12≈33%
（8）做法同3.15题（3）问，Hcell=（12×16-8）/（12×16）≈95.8%
时间中断请求主程序1级2级3级4级
D1，D2
D3，D4
4.5已知中断服务次序为3-2-4-1
（1）中断屏蔽字表如下图；
D1
D2
D3
D4
D1
0
1
1
1
D2
0
0
1
0
D3
0
0
0
0
D4
0
1
1
0
（2）中断过程示意图如右图。
4.8
（1）f=2×105字节/秒，T=5µs
（2）Ts+Td=5µs，通道时间图如下。
作图时注意：
至少要画到最慢设备的第二次请求出现，才能确定是否丢失数据（因为响应优先级低的设备较易丢失数据）。
设优
备先
号级
D11
D24
D32
D43
时间
（µs）0102030405060708090100110120130140150160170
（3）5，未处理D2第一次服务请求（即“无”。
答160也可），20，40
（4）D2丢失第一次请求的数据；
（5）增加通道的最大流量，动态改变设备的优先级，增加一定数量的数据缓冲器（教材P245）。
F=A1×B1＋A1×B1＋A1×B1＋A1×B1＋A1×B1＋A6×B6
123456
789
10
11
（a）计算顺序二叉树
5.9为了缩短运算时间，首先应考虑“最少切换算法”，即先执行完所有乘法（任务编号1-6）再执行加法（任务编号7-11），其次在加法中采用“最少相关算法”（即二叉树算法）。
右图（a）是计算顺序二叉树，其中任务1-6是乘法，任务7-11是加法。
注意任务10应该用前一级最早完成的任务7和8的结果，如果用任务9的结果则要推迟1拍启动，使总时间增加1拍。
右图（b）是时空图，由它得
TP=11/（22Δt）=1/（2Δt）
S=（6×4Δt+5×4Δt）/（22Δt）=2
E=（6×4Δt+5×4Δt）/（6×22Δt）=1/3
6
5
4
3
2
1
01234567891214151822
（b）时空图
5.15Δt=10ns=10-8秒
（1）F={1，2，5}，C=（10011）
（2）状态转移图如下图（a）所示。
（3）最小启动循环=（3）,最小平均启动距离=3Δt。
（4）插入2个延迟，最小启动循环=
（2）,最小平均启动距离=2Δt。
（5）新预约表如下图（b）所示。
（6）F={1，3，7}，C=（1000101），状态转移图如下图（c）所示。
（7）插入前TPmax=1/3Δt=1/30ns，插入后TPmax=1/2Δt=1/20ns。
12345678初态4，6，≥8
S1×12×
初态3，4，≥6S2×1×1000101
S3×4，6，≥84，6，≥8
10011S41××25
D1×10101011000111
D2×25
（a）（b）（c）
（8）插入前TP=10/33Δt=1/33ns，插入后TP=10/26Δt=1/26ns，如下图所示。
S4
S3………
S2
S1
3t
（a）插入前9×36
D2
D1
S4………
S3
S2
S1
2t
（b）插入后9×28
6.6（注意阅读P372倒数第9行－倒数第6行）
已知n=32，k加=6，k乘=7，k访存=6，k倒数=14，启动、输出延迟各1。
求各小题总拍数。
7.3已知输入端编号13=1101B。
（1）Cube3（1101B）=0101B=5
（2）PM2+3（13）=（13+23）mod16=21mod16=5
（3）PM2-0（13）=（13-20）mod16=12
（4）Shuffle（1101B）=1011B=11
（5）Shuffle（Shuffle（1101B））=Shuffle（1011B）=0111B=7
7.10用混洗―交换网络模拟Cube网。
当模拟Cube0功能时，只需一次交换即可完成；而模拟Cubei且i≠0时，需先作n–i步混洗，再作1步交换，最后作i步混洗才能完成，共计n+1步。
综上所述，下限为1步，上限为n+1步。
7.26
（1）～（3）；
（1）见下图实线。
（2）见下图虚线；不会阻塞，因为两条路径的控制信号都是1110，形成级控模式，所以不会阻塞。
（3）一次通过实现的置换数为168=4294967296，全部置换数为N!
=20922789888000，前者约占后者的0.02%。
级3级2级1级0
00000000
00010001
00100010
00110011
01000100
01010101
01100110
01110111
10001000
10011001
10101010
10111011
11001100
11011101
11101110
11111111
7.27
（3）求作超立方体贪心选播树
源结点编号的二进制形式1010在Cube0～Cube3位分别与7、6、5、6个目的结点的二进制形式不同，所以总时间=4（如某一位没有与源结点不同的目的结点，则该维不发送，总时间减少1），并且Cube0方向应该最先发送，Cube2方向最后发送，其它2个方向的发送先后顺序没有限制。
我们可以采用Cube0、Cube1、Cube3、Cube2的发送顺序，生成的选播树如下图所示，总流量=11。
1010
Cube0
10101011
Cube1
1010100010111001
Cube3
10100010100000001011001110010001
Cube2
1010111000100110100011000000010010111111001101111001110100010101
1014268120411153791315
超立方体贪心选播树
8.12问题为S=A1×B1+……+A32×B32，其中T乘=4Δt，T加=2Δt，T传=1Δt。
（1）在串行计算机上，各操作不论是否相关均不能重叠，总时间恒等于各操作单独时间之和，所以不必考虑运算顺序。
T=32·T乘+31·T加=（32×4+31×2）Δt=190Δt
（2）设此双向环可以并行传送（即为“移数环”，因为SIMD系统各种数据操作都能并行）。
按平均分配原则，每个结点内有4对数据。
首先在各结点用串行算法它们的相乘与求和，需时T1=4·T乘+3·T加=（4×4+3×2）Δt=22Δt；
然后用二叉树并行算法将8个结点中的部分和相加（见下图），其中并行加法需3次，每次时间相同，而并行传送3次的每次时间却随距离倍增，依次为1、2、4步，所以有T2=（1+2+4）·T传+3·T加=（7×1+3×2）Δt=13Δt；
总时间T=T1+T2=35Δt
s=s1+s2+s3+s4+s5+s6+s7+s8
①.右传20步
加法1步
②.右传21步
加法1步
③.右传22步
加法1步
9.6
解法1：
设处理机甲执行一个任务的时间为R，则处理机乙执行一个任务的时间为2R。
仍记C为一个任务与异机任务的通信时间，K为处理机甲分得的任务数。
参考公式（9.1）得，总时间T=R·max{2（M-K）,K}+C（M-K）K
由于
是max函数的转折点，所以T也可写成分段函数
图形如下
TT
2MR2MR
MRMR
02/3MMK02/3MMK
（A）当
时，K=M处最低（B）当
时，K=2/3M处最低
由于二次函数的上凸性，T的最小点只可能位于
或K=M二者之一。
为求临界条件，令
T|K=2/3M=T|K=M，得
，解出
。
结论：
当
时，最佳分配参数
；
当
时，最佳分配参数
。
解法2：
设处理机乙执行一个任务的时间为R，则处理机甲执行一个任务的时间为R/2。
仍记C为一个任务与异机任务的通信时间，K为处理机甲分得的任务数。
参考公式（9.1）得，总时间T=R·max{（M-K）,K/2}+C（M-K）K
由于
是max函数的转折点，所以T也可写成分段函数
图形如下
TT
MRMR
MR/2MR/2
02/3MMK02/3MMK
（A）当
时，K=M处最低（B）当
时，K=2/3M处最低
由于二次函数的上凸性，T的最小点只可能位于
或K=M二者之一。
为求临界条件，令
T|K=2/3M=T|K=M，得
，解出
。
结论：
当
时，最佳分配参数
；
当
时，最佳分配参数
。
9.18问题为S=（A1+B1）×……×（A8+B8），其中T加=30ns，T乘=50ns，T传=10ns。
将加法记为任务1-8，乘法记为任务9-15。
（1）在串行计算机上，同8.12题1问分析，共计15步运算，T=8·T加+7·T乘=（8×30+7×50）ns=590ns。
（2）多功能部件SISD计算机的工作方式可参考P346题18（3）。
为了充分利用加法器与乘法器的可并行性，尽量让加法与乘法交替进行，可自左向右顺序运算（见下图）。
T=2·T加+7·T乘=（2×30+7×50）ns=410ns
15
8147×50ns
A8B8
713乘法910111215
A7B7加法12345678
8×30ns
9
21
A2B2A1B1
（3）同8.12题2问，设单向环可以并行传送（即为“移数环”，理由同8.12题2问）。
12345678102040
2468传送
48乘法505050
8加法30
T=T加+3·T乘+（1+2+4）·T传=（30+3×50+7×10）ns=250ns
[算法改进：
将8对数据的加法由8个结点同时完成（共30ns）改成4个结点分两批完成（共60ns），这样要多花30ns；但由于结果在4个结点中，其后的累乘就只需要做2次传输，距离分别是1步、2步，省去了原来最费时间的第3次传输（4×10ns=40ns），收支相抵之后还省下了10ns，实际用240ns。
一般原则：
对于传输时间随距离上升的网络来说，如果二叉树并行算法的末尾的一次传输时间大于一次运算时间，就把n对数据改存于n/2甚至n/4个结点中，以增加运算次数的代价来换取减少长距离传输的收益。
其判决条件就是“传输时间vs运算时间”。
]
（4）在全互连网络上，任意两个结点之间的距离均为1步，所以任何置换都能在1步完成，故
101010
传送
乘法505050
加法30
T=T加+3·T乘+（1+1+1）·T传=（30+3×50+3×10）ns=210ns
9章加1题：
采用由4个PE和以太网（一次只允许发送一个数据）组成的多处理机计算下式：
A1×B1+……+A32×B32，每个PE完成一次乘法、加法、发送数据均需一个单位时间（接收数据不占用PE时间）。
（1）画出最快算法的计算树；
（2）画出最快算法的时空图；
（3）写出最快算法所需时间；
（4）写出串行算法（即只使用一个PE）所需时间；
（5）求加速比。
解：
（1）计算树；
（2）时空图；
S=S1+S2+S3+S4处理机
P4
P3
P2
P1
（8+7）Δt4Δt时间
其中S1表示求和操作
，S1在P1内顺序完成。
S2～S4的处理方法相同。
（3）并行算法时间；T=15Δt+4Δt=19Δt
（4）串行算法时间；T=32Δt+31Δt=63Δt
（5）加速比：
S=63Δt/19Δt≈3.32
升级会员 