华中科技大学计算机学院：第2版《计算机系统结构》习题解答

清华第2版《计算机系统结构》习题解答 华中科技大学计算机学院林安 目录 第一章(P33 1.7-1.9(透明性概念),1.12-1.18( Amdahl定律),1.19、1.21、1.24( CPI/MIPS) 第二章(P124) 2.3、2.5、2.6(浮点数性能),2.13、2.15(指令编礓) 第三章(P202) 3.3(存储层次性能),3.5(并行主存系统),3.15-3.15加1题(堆栈模拟),3.19中(3)(4)(6)(8) 问(地址映象/替换算法-实存状况图) 第四章(P250) 4.5(中断屏蔽字表/中断过程示意图),4.8(通道流量计算/通道时间图) 第五章(P343) 5.9(流水线性能/时空图),5.15(2种调度算法) 第六章(P391) 6.6(向量流水时间计算),6.10( Amdahl定律/ MFLOPS) 第七章(P446) 7.3、7.29(互连函数计算),7.6-7.14(互连网性质),7.4、7.5、7.26(多级网寻径算法),7.27 (寻径/选播算法) 第八章(P498) 8.12(SISD/SIMD算法) 第九章(P562) 9.18(SISD/多功能部件/ SIMD/MIMD算法) 注:每章可选1-2个主要知识点,每个知识点可只选1题。有下划线者为推荐的主要知识点。)

1 清华第 2 版《计算机系统结构》习题解答 华中科技大学计算机学院 林安 目录 第一章(P33) 1.7-1.9（透明性概念），1.12-1.18（Amdahl 定律），1.19、1.21、1.24（CPI/MIPS） 第二章(P124) 2.3、2.5、2.6（浮点数性能），2.13、2.15（指令编码） 第三章(P202) 3.3（存储层次性能），3.5（并行主存系统），3.15-3.15 加 1 题（堆栈模拟），3.19 中(3)(4)(6)(8) 问（地址映象/替换算法--实存状况图） 第四章(P250) 4.5（中断屏蔽字表/中断过程示意图），4.8（通道流量计算/通道时间图） 第五章(P343) 5.9（流水线性能/时空图），5.15（2 种调度算法） 第六章(P391) 6.6（向量流水时间计算），6.10（Amdahl 定律/MFLOPS） 第七章(P446) 7.3、7.29（互连函数计算），7.6-7.14（互连网性质），7.4、7.5、7.26（多级网寻径算法），7.27 （寻径/选播算法） 第八章(P498) 8.12（SISD/SIMD 算法） 第九章(P562) 9.18（SISD/多功能部件/SIMD/MIMD 算法） (注：每章可选 1-2 个主要知识点，每个知识点可只选 1 题。有下划线者为推荐的主要知识点。)

第一章(P33) (1)从指定角度来看,不必要了解的知识称为透明性概念 (2)见下表,“√”为透明性概念,“P”表示相关课文页数 模m父义,了 浮点数据,X,P4 通道与LO处理机,×,P4 总线觅度,√ 阵列运算部件,×, 结合型与独立型通道,√, 访问保护 指令控制方式,√ 堆栈指令,X 最小编址单位,X ache存储器,√ 1.8见下表,“√”为透明性概念,“P”表示相关课文页 指令地址寄存器,×, 指令缓冲器,√ 时标发生器,√ 条件码寄存器, 乘法器,√ 主存地址寄存器,√ 磁盘, 先行进位链,√, 移位器,√ 通用寄存器,X, 中断字寄存器,×, 1.9见下表,“√”表示都透明,“应”表示仅对应用程序员透明,“×”表示都不透明 数据通路宽度,√, 虚拟存储器,应, Cache存储器,√ 程序状态子, “启动IO”指令,应, “执行”指令, 指令缓冲寄存器,√ 1.12已知Se=20,求作Fe-Sn关系曲线。 将Se代入 Adah定律得 1-F。 1.13上式中令Sn=2,解出Fe=10/19≈0.526 1.14上式中令Sn=10,解出Fe=18/19≈0.947 1.15已知两种方法可使性能得到相同的提高,问哪一种方法更好 (1)用硬件组方法,已知Se=40,Fe=0.7,解出Sn=40/12.7≈3.1496(两种方法得到的相同性能) (2)用软件组方法,已知Se=20,Sn=40/12.7,解出Fe=27.3/38≈0.7184(第二种方法的百分比) (3)结论:软件组方法更好。因为硬件组需要将Se再提高100%(20→40),而软件组只需将Fe 再提高1.84%(0.7→0.7184)

2 第一章(P33) 1.7 (1)从指定角度来看，不必要了解的知识称为透明性概念。 (2)见下表，“√”为透明性概念，“P”表示相关课文页数。 1.8 见下表，“√”为透明性概念，“P”表示相关课文页数。 1.9 见下表，“√”表示都透明，“应”表示仅对应用程序员透明，“×”表示都不透明。 1.12 已知 Se=20 , 求作 Fe-Sn 关系曲线。 将 Se 代入 Amdahl 定律得 e n F S 20 19 1 1 − = 1.13 上式中令 Sn=2，解出 Fe=10/19≈0.526 1.14 上式中令 Sn=10，解出 Fe=18/19≈0.947 1.15 已知两种方法可使性能得到相同的提高，问哪一种方法更好。 (1)用硬件组方法，已知 Se=40，Fe=0.7，解出 Sn=40/12.7≈3.1496（两种方法得到的相同性能） (2)用软件组方法，已知 Se=20，Sn=40/12.7，解出 Fe=27.3/38≈0.7184（第二种方法的百分比） (3)结论：软件组方法更好。因为硬件组需要将 Se 再提高 100%（20→40），而软件组只需将 Fe 再提高 1.84%（0.7→0.7184）。 模 m 交叉，√， 浮点数据，×，P4 通道与 I/O 处理机，×，P4 总线宽度，√， 阵列运算部件，×， 结合型与独立型通道，√， 单总线，√， 访问保护，×， 中断，×， 指令控制方式，√， 堆栈指令，×， 最小编址单位，×， Cache 存储器，√， 指令地址寄存器，×， 指令缓冲器，√， 时标发生器，√， 条件码寄存器，×， 乘法器，√， 主存地址寄存器，√， 磁盘，×， 先行进位链，√， 移位器，√， 通用寄存器 ，×， 中断字寄存器，×， 数据通路宽度，√， 虚拟存储器，应， Cache 存储器，√， 程序状态字，×， “启动 I/O”指令，应， “执行”指令，×， 指令缓冲寄存器，√， Sn 20 1 0 1 Fe

0.1 0914 1.18记f—时钟频率,T=1/f—时钟周期,B——带宽(Byte/s) 方案一:B1==4f(Byte/s) 方案二:B2 75%×2+25%×1 ×4=3.5f(Byte/s) 2T 1.19由各种指令条数可以得到总条数,以及各百分比,然后代公式计算。 IC=>IC:=10 (1)CP=∑(CP1x)=1×045+2×0.32+2×015+2×0.08=1.55 40×10 (2) MIPS ≈25.806 CPIx 155×10°1.55 (3)T= ≈0.003876(秒) MPS×106400 (1)CPI=1×06+2×0.18+4×0.12+8×0.1=224 (2)MIPS= 40×10 CPI×10°2.24×10 1.24记Tc—新方案时钟周期,已知CPI=CPI:=1 原时间=CPI×IC×0.95c=0.95IC×Tc 新时间=(0.3×2/3+0.7)×IC×Tc=0.9IC×Tc 二者比较,新时间较短

3 1.17 3.57 1.4 5 5 0.9 0.1 1 =  + Sn = 1.18 记 f ── 时钟频率，T=1/f ── 时钟周期，B ── 带宽（Byte/s）。 方案一： 4 ( / ) 1 4 1 f Byte s T B =  = 方案二： 4 3.5 ( / ) 2 75% 2 25% 1 2 f Byte s T B  =  +  = 1.19 由各种指令条数可以得到总条数，以及各百分比，然后代公式计算。 = = = 4 1 5 10 i i IC IC (1) = =  =  +  +  +  = 4 1 ( ) 1 0.45 2 0.32 2 0.15 2 0.08 1.55 i i i IC IC CPI CPI (2) 25.806 1.55 40 1.55 10 40 10 10 6 6 6 =    =  = CPI f MIPS (3) 0.003876（秒） 400 1.55 106 =   = MIPS IC T 1.21 (1) CPI =10.6+ 20.18+ 40.12+80.1= 2.24 (2) 17.86 2.24 10 40 10 10 6 6 6    =  = CPI f MIPS 1.24 记 Tc ── 新方案时钟周期，已知 CPI = CPIi = 1 原时间 = CPI × IC × 0.95Tc = 0.95IC×Tc 新时间 = （0.3×2/3+0.7）× IC × Tc = 0.9IC×Tc 二者比较，新时间较短

第二章(P124) 2.3(忽略P124倒1行~P125第8行文字,以简化题意)已知2种浮点数,求性能指标。 此题关键是分析阶码、尾数各自的最大值、最小值。 原图为数据在内存中的格式,阶码的小数点在其右端,尾数的小数点在其左端,遵守规格化要 由于尾数均为原码,原码的绝对值与符号位无关,所以最大正数与最小负数的绝对值相同,可 用“±最大绝对值”回答:最小正数与最大负数的绝对值相同,可用“±最小绝对值”回答 第1小问中,阶码全部位数为8,作无符号数看待真值为0~255,作移-127码看待真值为-127~ +128:尾数(不计符号位)有23位小数,另加1位整数隐藏位,所以尾数绝对值为1.0~2.0 223,有效位数p=24 第2小问中,阶码全部位数为11,作无符号数看待真值为0~2047,作移-1023码看待真值为 -1023~+1024;尾数(不计符号位)有52位小数,另加1位整数隐藏位,所以尾数绝对值为1.0~ 2.0-252,有效位数p=53 最大绝对值为最大阶码与最大尾数绝对值的组合,最小绝对值为最小阶码与最小尾数绝对值的 组合。代入相关公式后得最终结果如下表 士最大绝对值 ±(1-22)·223 ±(1-2-3)·203 士最小绝对值 表数精度δ 表数效率n 100% 100% 2.5 (1)r,=2,r。=2,p=24(隐藏最高位),q=7。 (2)Nx=1.7×103,-|N|=-1.47×103 6≤5.96×108≈1072,n=100% 2.6 (1)0.2=0.33333H×16 1位7位 位 设阶码为移-63码(即-2°+1,原题未指明) L01111133331 0.2=0.110011001100110011001101B×22 (其中最高有效位需隐藏) 阶码为移-127码(即-2+1) 001111100110010 101 (2)符号位不变,(阶码-63)×4+127:尾数左规,除去最高位 (3)符号位不变,(阶码-127)/4+63:尾数补最高位,按除法余数右移若干位,左补0。 2.13已知10条指令使用频度,求3种编码方法的平均码长与信息冗余量 (1)此问中的“最优 Huffman编码法”实际是指码长下限,即信源的平均信息量—熵,代公式

4 第二章(P124) 2.3（忽略 P124 倒 1 行 ～ P125 第 8 行文字，以简化题意）已知 2 种浮点数，求性能指标。 此题关键是分析阶码、尾数各自的最大值、最小值。 原图为数据在内存中的格式，阶码的小数点在其右端，尾数的小数点在其左端，遵守规格化要 求。 由于尾数均为原码，原码的绝对值与符号位无关，所以最大正数与最小负数的绝对值相同，可 用“±最大绝对值”回答；最小正数与最大负数的绝对值相同，可用“±最小绝对值”回答。 第 1 小问中，阶码全部位数为 8，作无符号数看待真值为 0～255，作移-127 码看待真值为-127～ +128；尾数（不计符号位）有 23 位小数，另加 1 位整数隐藏位，所以尾数绝对值为 1.0～2.0 – 2 -23，有效位数 p=24； 第 2 小问中，阶码全部位数为 11，作无符号数看待真值为 0～2047，作移-1023 码看待真值为 -1023～+1024；尾数（不计符号位）有 52 位小数，另加 1 位整数隐藏位，所以尾数绝对值为 1.0～ 2.0 – 2 -52，有效位数 p=53。 最大绝对值为最大阶码与最大尾数绝对值的组合，最小绝对值为最小阶码与最小尾数绝对值的 组合。代入相关公式后得最终结果如下表。 2.5 (1) rm = 2，re = 2，p = 24（隐藏最高位）,q = 7。 (2) Nmax = 1.7×1038，-|N|min = -1.47×10-39 δ ≤ 5.96×10-8 ≈ 10-7.22，η = 100% 2.6 (1) 0.2 = 0.333333H×160 设阶码为移-63 码（即-2 6 +1，原题未指明） 0.2 = 0.110011001100110011001101B×2 -2 （其中最高有效位需隐藏） 阶码为移-127 码（即-2 7 +1） (2) 符号位不变，（阶码 – 63）×4 + 127；尾数左规，除去最高位； (3) 符号位不变，（阶码 – 127）/ 4 + 63；尾数补最高位，按除法余数右移若干位，左补 0。 2.13 已知 10 条指令使用频度，求 3 种编码方法的平均码长与信息冗余量。 (1)此问中的“最优 Huffman 编码法”实际是指码长下限，即信源的平均信息量──熵，代公式 32 位 64 位 ±最大绝对值 ±(1-2 -24)·2 129 ±(1-2 -53)·2 1025 ±最小绝对值 ±2 -127 ±2 -1023 表数精度δ 2 -24 2 -53 表数效率η 100% 100% 1 位 7 位 6 位 0 0111111 333333 1 位 8 位 23 位 0 01111101 10011001100110011001101

得H=2.9566 (2) Huffman编码性能如下表 (3)2/8扩展编码是8/64/512法的变种,第一组2条指令,码长为2(1位扩展标志,1位编码), 第二组8条指令,码长为4(1位扩展标志,与第一组区别,加3位编码),编码性能如下表 (4)3/7扩展编码是15/15/15法的变种,第一组3条指令,码长为2(共有4种组合,其中3种 组合分别代表3条指令,留1种组合作为扩展前缀标志),第二组7条指令,码长为5(2位固定 的前缀扩展标志,与第一组区别,加3位编码,只用其中7种组合),编码性能如下表 Huffman编码 2/8扩展编码 3/7扩展编码 平均码长L 2.99 信息冗余量R 4.61% 7.59% 2.15 (1)15条/63条/64条 (2)14条/126条/128条 第三章(P202) 3.3直接代公式计算存储层次性能指标 (1)74ns,38ns,23.6ns (2)0.258,0.315,0.424 (3)T256Kc128K>c64K (4)19.092,11.97,10.0064。答案是256K方案最优 5已知K 1-(1-g),其中g=0 g 依题意有K=1-(1-g)”1 ≥Kn+021-(-8) g 整理得09≥0.2,解出nS02 ≈1528,向下取整,得15: lg0.9 按另一种题意理解是向上取整,得16,也对。 3.15欲知可能的最高命中率及所需的最少主存页数,较好的办法是通过“堆栈模拟法”,求得命 中次数随主存页数变化的函数关系。下图就是“堆栈模拟图”,其中“√”表示命中

5 得 H=2.9566。 (2)Huffman 编码性能如下表； (3)2/8 扩展编码是 8/64/512 法的变种，第一组 2 条指令，码长为 2（1 位扩展标志，1 位编码）, 第二组 8 条指令，码长为 4（1 位扩展标志，与第一组区别，加 3 位编码），编码性能如下表； (4)3/7 扩展编码是 15/15/15 法的变种，第一组 3 条指令，码长为 2（共有 4 种组合，其中 3 种 组合分别代表 3 条指令，留 1 种组合作为扩展前缀标志）,第二组 7 条指令，码长为 5（2 位固定 的前缀扩展标志，与第一组区别，加 3 位编码，只用其中 7 种组合），编码性能如下表。 2.15 (1) 15 条/63 条/64 条 (2) 14 条/126 条/128 条 第三章(P202) 3.3 直接代公式计算存储层次性能指标。 (1)74ns，38ns，23.6ns (2)0.258，0.315，0.424 (3)T256K c128K > c64K (4)19.092，11.97，10.0064。答案是 256K 方案最优。 3.5 已知 g g K n n 1− (1− ) = ，其中 g=0.1 依题意有 0.2 1 (1 ) 0.2 1 (1 ) 1 1 + − −  + = − − = + + g g K g g K n n n n 整理得 0.9n≥0.2，解出 15.28 lg 0.9 lg 0.2 n   ，向下取整，得 15； 按另一种题意理解是向上取整，得 16，也对。 3.15 欲知可能的最高命中率及所需的最少主存页数，较好的办法是通过“堆栈模拟法”，求得命 中次数随主存页数变化的函数关系。下图就是“堆栈模拟图”，其中“√”表示命中。 Huffman 编码 2/8 扩展编码 3/7 扩展编码 平均码长 L 2.99 3.1 3.2 信息冗余量 R 1.10% 4.61% 7.59%

3命中次数 0137 (1)Hmx=7/12≈58.3% 3)当1次页面访问代表连续1024次该页内存储单元访问时,后1023次单元访问肯定是命中的, 而第1次单元访问的命中情况与这1次页面访问的命中情况相同。根据上图中最高命中情况,共 有7次页命中(折算为7×1024次单元命中),5次页不命中(折算为5×1023次单元命中,也 可写为5×1024-5),单元访问总次数为12×1024,故有 H11(12×1024-5)/(12×1024)=12283/12288≈99.96% 3.15加1题一个二级存储层次,采用全相联映象和最久没有使用算法,实存共5页,为2道程 序分享,页地址流分别如下 P1=12341321 P2=12342233 试作2个实存分配方案,分别使2道程序满足 1)命中率相同 (2)命中次数之和最大。 解:分别为2道程序作“堆栈模拟图”,其中“√”表示命中 命中次数 =1 0

6 (1)Hmax=7/12≈58.3% (2)n=4 (3)当 1 次页面访问代表连续 1024 次该页内存储单元访问时，后 1023 次单元访问肯定是命中的， 而第 1 次单元访问的命中情况与这 1 次页面访问的命中情况相同。根据上图中最高命中情况，共 有 7 次页命中（折算为 7×1024 次单元命中），5 次页不命中（折算为 5×1023 次单元命中，也 可写为 5×1024-5），单元访问总次数为 12×1024，故有： Hcell=(12×1024-5)/(12×1024)=12283/12288≈99.96% 3.15 加 1 题 一个二级存储层次，采用全相联映象和最久没有使用算法，实存共 5 页，为 2 道程 序分享，页地址流分别如下 P1 = 1 2 3 4 1 3 2 1 P2 = 1 2 3 4 2 2 3 3 试作 2 个实存分配方案，分别使 2 道程序满足 (1)命中率相同； (2)命中次数之和最大。 解：分别为 2 道程序作“堆栈模拟图”，其中“√”表示命中。 P= 4 5 3 2 5 1 3 2 3 5 1 3 命中次数 4 5 3 2 5 1 3 2 3 5 1 3 4 5 3 2 5 1 3 2 3 5 1 4 5 3 2 5 1 1 2 3 5 4 4 3 2 5 5 1 2 2 4 4 4 4 4 4 4 n=1 0 n=2 √ 1 n=3 √ √ √ 3 n=4 √ √ √ √ √ √ √ 7 n=5 √ √ √ √ √ √ √ 7 P1 = 1 2 3 4 1 3 2 1 命中次数 N(1) 1 2 3 4 1 3 2 1 1 2 3 4 1 3 2 1 2 3 4 1 3 1 2 2 4 4 n1= 1 0 n1= 2 0 n1= 3 √ √ 2 n1= 4 √ √ √ √ 4

233命中次数Na nz n2=2 将两图结果综 个分配方案的命中率情况表如下 结论如下 1)命中率相同的方案是n=3而n2=2 (2)命中次数之和最大的方案是n=4而n2=1。 3.19中(3)(4)(6)(8)问 虚存 实012131 虚组0 实存 虚组 实组0 虚3 虚组2 3/)奖1 页 虚组3 456 (a)虚页集合与实页集合的对应关系 (b)对应关系表(√为有关系) (4)通过作“实存状况图”模拟各虚块的调度情况,可获得 Cache的块地址流序列

7 将两图结果综合，得到 4 个分配方案的命中率情况表如下 结论如下 (1)命中率相同的方案是 n1= 3 而 n2= 2； (2)命中次数之和最大的方案是 n1= 4 而 n2= 1。 3.19 中(3)(4)(6)(8)问 (3) (4)通过作“实存状况图”模拟各虚块的调度情况，可获得 Cache 的块地址流序列。 P2 = 1 2 3 4 2 2 3 3 命中次数 N(2) 1 2 3 4 2 2 3 3 1 2 3 4 4 2 2 1 2 3 3 4 4 1 1 1 1 1 n2= 1 √ √ 2 n2= 2 √ √ 2 n2= 3 √ √ √ √ 4 n2= 4 √ √ √ √ 4 6 5 N(1)+N(2) 4 3 2 N(1) N(2) 1 1+4 2+3 3+2 4+1 n1 1 2 3 4 N(1) 0 0 2 4 n2 4 3 2 1 N(2) 4 4 2 2 N(1)+N(2) 4 4 4 6 虚存 实页 0 1 2 3 虚组 0 0 0 √ √ 1 实存 1 √ √ 虚组 1 2 · 0 实组 0 2 √ √ 3 · 1 虚 3 √ √ 虚组 2 4 · 2 实组 1 页 4 √ √ 5 · 3 5 √ √ 虚组 3 6 6 √ √ 7 7 √ √ (a) 虚页集合与实页集合的对应关系 (b) 对应关系表（√为有关系）

4*「4444*44*4*4* CI 11*1*1*0 入入入入中中替替中替替中 102 10123 此问最容易出错的地方是忽略“组相联”地址约束,将虚页装错实组。另外没有及时标注“*” 号也容易导致淘汰对象错误 (6)H=4/12≈33% (8)做法同3.15题(3)问,H1=(12×16-8)/(12×16)≈95.8% 第四章(P250) 4.5已知中断服务次序为3-2-4-1,。 (1)中断屏蔽字表如下图: 时间中断请求主程序1级2级3级4级 (2)中断过程示意图如右图 DI, D2 DI D D4 01|1|0 (1)f=2×10字节/秒,T=5us (②)Ts+Td=5us,通道时间图如下。作图时注意:至少要画到最慢设备的第二次请求出现,才能确 定是否丢失数据(因为响应优先级低的设备较易丢失数据)

8 此问最容易出错的地方是忽略“组相联”地址约束，将虚页装错实组。另外没有及时标注“*” 号也容易导致淘汰对象错误。 (6)H=4/12≈33% (8)做法同 3.15 题(3)问，Hcell=(12×16-8)/(12×16)≈95.8% 第四章(P250) 4.5 已知中断服务次序为 3-2-4-1，。 (1)中断屏蔽字表如下图； (2)中断过程示意图如右图。 4.8 (1)f=2×105 字节/秒，T=5us (2)Ts+Td=5us，通道时间图如下。作图时注意：至少要画到最慢设备的第二次请求出现，才能确 定是否丢失数据（因为响应优先级低的设备较易丢失数据）。 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 时间 中断请求 主程序 1 级 2 级 3 级 4 级 D1，D2 D3，D4 D1 D2 D3 D4 D1 0 1 1 1 D2 0 0 1 0 D3 0 0 0 0 D4 0 1 1 0

设优 备先 团zz团团z 时间 (us)0102030 708090100110120130140150160170 (4)D2丢失第一次请求的数据 (5)参见P245 第五章(P343) 5.9为了缩短运算时间,首先应考虑“最少切换算法”,即先执行完所有乘法(任务编号1-6) 再执行加法(任务编号7-11),其次在加法中采用“最少相关算法”(即二叉树算法)。 记c1=A1×B1 c=A×B,下图(a)是加法的计算顺序二叉树,注意任务10应该用前一级 最早完成的任务7和8的结果,如果用任务9的结果则要推迟1拍启动,使总时间增加1拍。 F=c1+c2+c3+e4+cs+c66 4[24 [i234s 0123456789 121415 根据时空图(b)得 TP=11/(22△t)=1/(2△t) S=(6×4△t+5×4△t)/(22△t)=2

9 (3)5，160，20，40； (4)D2 丢失第一次请求的数据； (5)参见 P245。 第五章(P343) 5.9 为了缩短运算时间，首先应考虑“最少切换算法”，即先执行完所有乘法（任务编号 1-6） 再执行加法（任务编号 7-11），其次在加法中采用“最少相关算法”（即二叉树算法）。 记 c1=A1×B1，……，c6=A6×B6，下图(a)是加法的计算顺序二叉树，注意任务 10 应该用前一级 最早完成的任务 7 和 8 的结果，如果用任务 9 的结果则要推迟 1 拍启动，使总时间增加 1 拍。 根据时空图(b)得 TP = 11/(22Δt) = 1/(2Δt) S = (6×4Δt + 5×4Δt)/(22Δt) = 2 设 优 备 先 号 级 D1 1 D2 4 D3 2 D4 3 时间 (us) 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 F=c1+c2+c3+c4+c5+c6 6 1 2 3 4 5 6 7 8 9 10 11 5 1 2 3 4 5 6 7 8 9 4 1 2 3 4 5 6 3 7 8 9 10 11 10 2 7 8 9 10 11 1 1 2 3 4 5 6 7 8 9 10 11 11 0 1 2 3 4 5 6 7 8 9 12 14 15 18 22 (a) (b)

E=(6×4△t+5×4△t)/(6×22△t)=1/3 5.15△t=10ns=10°秒 (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)所示 12345678 初态 初态 1010101 00011L (7)插入前TP /3△t=1/30ns,插入后TPn=1/2△t=1/20ns (8)插入前TP=10/33△t=1/33ns,插入后TP=10/26△t=1/26ns,如下图所示

10 E = (6×4Δt + 5×4Δt)/(6×22Δt) = 1/3 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。 (8)插入前 TP = 10/33Δt = 1/33ns，插入后 TP = 10/26Δt = 1/26ns，如下图所示。 1 2 3 4 5 6 7 8 初态 4，6，≥8 S1 × 1 2 × 初态 3，4，≥6 S2 × 1 × 1 0 0 0 1 0 1 S3 × 4，6，≥8 4，6，≥8 1 0 0 1 1 S4 1 × × 2 5 D1 × 1 0 1 0 1 0 1 1 0 0 0 1 1 1 D2 × 2 5 (a) (b) (c)