北理工计算机体系结构习题解答-课件.ppt

1、1234567891011121314151617120(1)/2020 19SFFF18)20/()1(12FF 53.01910F1920niICiIiCPI1)*(81.25)10*55.1/(10*40)10*CPI/(f666MIPS速率秒3610*875.3)10*401(*)2*80002*150002*320001*45000(t2122%10*8%12*4%18*2%60*1CPI17.8610*2.2440MHZ10*CPIfMIPS662324252627282930310.010.30.010.020.020.030.030.040.110.130.140.150.15

2、0.040.121.000.570.270.020.430.190.240.050.070.040.080.1236555553333436323334353637382-5 一个处理机共有一个处理机共有10条指令，各指令在程序中出条指令，各指令在程序中出现的概率如下：现的概率如下：指令指令 概率概率 Huffman 2/8扩展扩展 3/7扩展扩展 I1 0.25 I2 0.20 I3 0.15 I4 0.10 I5 0.08 I6 0.08 I7 0.05 I8 0.04 I9 0.03 I10 0.0239（1）计算这）计算这10条的操作码最短平均长度。条的操作码最短平均长度。（2）采用）

3、采用Huffman编码法编写这编码法编写这10条指令的条指令的操作码，并计算操作码的平均长度和信息冗操作码，并计算操作码的平均长度和信息冗余量。余量。（3）采用）采用2/8扩展编码法编写这扩展编码法编写这10条指令的条指令的操作码，并计算操作码的平均长度和信息冗操作码，并计算操作码的平均长度和信息冗余量。余量。（4）采用）采用3/7扩展编码法编写这扩展编码法编写这10条指令的条指令的操作码，并计算操作码的平均长度和信息冗操作码，并计算操作码的平均长度和信息冗余量。余量。40410.151.000.430.570.030.020.080.050.040.230.170.320.130.090.0

4、50.080.250.200.1001I1I2I3I4I5I6I7I8I9I1001010101010101014243440.151.000.430.570.030.020.080.050.040.230.170.320.130.090.050.080.250.200.1001I1I2I3I4I5I6I7I8I9I104546474849505152534条条254条条8条条8条条16条条5455单位单位565758596061D1D2D3D4D5ttttt0 10 20 30 40 50 60 70 80 90 100 通道处理完各台设备的第一次数据服务请求通道处理完各台设备的第一次数据服

5、务请求的时刻分别为：的时刻分别为：5s，10s，20s，30s，90s。62636465D1D2D3D4tttt0 10 20 30 40 50 60 70 80 90 100120130140150160110 （3）通道处理完各台设备的第一次数据服）通道处理完各台设备的第一次数据服务请求的时刻分别为：务请求的时刻分别为：5s，160s，20s，40s。6667686970717273747576S2S1时,CC2CC SC SSS1122124-2 解：（1）（2）ta=ht1+(1-h)t277（3）rhhhhthhtttatett)1(1)1(12)1(11112（4）he991001

6、r=100时，0.95=1/(100-99h)h=0.9994778nnHnHH111n=75.475m=n m=15.1（5）1 0.960.999471n 重复访问重复访问必考必考79804-3 解：解：（1）FIFO 1 2 3 4 5 6 7 8 9 10 11 12 2 3 2 1 5 2 4 5 3 2 5 2 中 *中 *中 *81（2）LRU 1 2 3 4 5 6 7 8 9 10 11 12 2 3 2 1 5 2 4 5 3 2 5 2 中 *中 *中 *中 中82（2）LRU堆栈法堆栈法 1 2 3 4 5 6 7 8 9 10 11 12 2 3 2 1 5 2 4

7、5 3 2 5 2 中 *中 *中 *中 中83（3）OPT 1 2 3 4 5 6 7 8 9 10 11 12 2 3 2 1 5 2 4 5 3 2 5 2 中 *中 *中 中 *中 中84（2）FIFO算法页 H=3/12=25%LRU算法页 H=5/12=41.7%OPT算法页 H=6/12=50%8586874-4 解：解：标记标记 组号组号 块内地址块内地址组号组号 组内块号组内块号 块内地址块内地址（1）主存地址格式）主存地址格式2111（2）Cache地址格式地址格式44先写先写cache地址地址88组组0组组1组间直接映象组间直接映象组内全相联映象组内全相联映象Cache主

8、存主存标记标记00标记标记01标记标记10标记标记1189 1 2 3 4 5 6 7 8 9 10 11 12 6 2 4 1 4 6 3 0 4 5 7 3*中 *（4）LRU利用堆栈法利用堆栈法块命中率 H=1/12=8.3%90 1 2 3 4 5 6 7 8 9 10 11 12 6 2 4 1 4 6 3 0 4 5 7 3 中 中*中 *(5)LRU块命中率块命中率 H=3/12=25%91 1 2 3 4 5 6 7 8 9 10 11 12 6 2 4 1 4 6 3 0 4 5 7 3 中 中*中 *(5)LRU利用堆栈法利用堆栈法块命中率 H=3/12=25%92（6）=

9、1-(1-0.25)/(16*16)=0.997nnHnHH111命中率的两个公式必考命中率的两个公式必考对应不同的情况对应不同的情况一个是一个是“重环重环”？注意注意n的含义的含义9394装入位为装入位为1才可以变才可以变959611 121cache地址地址主存地址主存地址97组组0组组1组间直接映象组间直接映象组内全相联映象组内全相联映象Cache主存主存98时刻时刻地址流地址流命命中中替替换换替替换换替替换换替替换换替替换换命命中中替替换换替替换换替替换换替替换换991001011021031041051065-1 解：解：分析k分析k+1分析k+2执行k执行k+1执行k+2取指k取指

10、k+1取指k+2分析k分析k+1分析k+2执行k执行k+1执行k+2取指k取指k+1取指k+2分析k分析k+1分析k+2执行k执行k+1执行k+2取指k取指k+1取指k+2(a)(b)(c)107（1）(t取指取指+t分析分析+t执行执行)n T=(t+2 t+3 t)n=6nt（2）t取指取指+nt分析分析+(n-1)maxt取指取指,t执行执行+t执行执行 T=t+(2 t+3 t)n=(1+5n)t（3）t取指取指+maxt取指取指,t分析分析+(n-2)maxt取指取指,t分析分析,t执行执行+maxt分析分析,t执行执行+t执行执行 T=t+2 t+3 t n=(3+3n)t 108

11、109分析k分析k+1分析k+2执行k执行k+1执行k+2取指k取指k+1取指k+2分析k分析k+1分析k+2执行k执行k+1执行k+2取指k取指k+1取指k+2分析k分析k+1分析k+2执行k执行k+1执行k+2取指k取指k+1取指k+2(a)(b)(c)110111112s1s2s3s4部件时间111124233635444272435t 555677886687999 10110981010231231211263547109811 121613151417 18输入：1263547109812354(t)t1410注意从哪里开始停，注意从哪里开始停，10的哪个位置的哪个位置113 1

12、1 2 2 3 3 4 4 1 2 3 4 1 2 3 4部件部件时间时间 IVI II III24812 14 16 18 20 22610114这一章必须会画图这一章必须会画图会计算会计算1151161175-5 解：解：1 1 3 3 3 5 1 3 2 4124 6 7 8 9 10 113 5空空间间时间时间 S4S1 S2 S3 12 2 2 4 5 4 4 5 5 6 6 6 6 7 7 7 8 8 9118TP=5/(7t)=0.714/t S=(54t+2t)/7t=22t/(7t)=3.14 E=45t/(47t)=0.714=71.4%119120121122123571

13、000111110001101101011112576576画向量表画向量表随着流水线往前走随着流水线往前走只是右移补零只是右移补零右移多少位然后或操作右移多少位然后或操作124能找到就可以，如果题目没要求全找不用全找能找到就可以，如果题目没要求全找不用全找1251261271285-17 设指令由取指、分析、执行三个子部件组成。设指令由取指、分析、执行三个子部件组成。每个子部件经过时间为每个子部件经过时间为t，连续执行，连续执行12条指令。请条指令。请分别画出在常规标量流水处理机及度分别画出在常规标量流水处理机及度m均为均为4的超的超标量处理机、超长指令字处理机、超流水线处理机标量处理机、超

14、长指令字处理机、超流水线处理机上工作的时空图，分别计算它们相对常规标量处理上工作的时空图，分别计算它们相对常规标量处理机的加速比机的加速比SP。超标量、常规标量：概念必须清楚超标量、常规标量：概念必须清楚129常规标量流水处理机常规标量流水处理机12356791011子部件时间取指分析执行(t)481212356791011481212356791011481212356791011481201314130度度m=4的超标量处理机的超标量处理机加速比加速比SP=14 t/5t=2.811111222233333244444515556267687378849199102101110111131

15、212124子部件时间取指分析执行(t)0131度度m=4的超长指令字处理机的超长指令字处理机加速比加速比SP=14 t/5t=2.8111131321451221222324332333子部件时间取指分析执行(t)0132度度m=4的超流水线处理机的超流水线处理机加速比加速比SP=14 t/5.75t=2.4311111222233333244444515556267687378849199102101110111131212124子部件时间取指分析执行(t)5.75 60阶梯状阶梯状1/n1336-1 画出画出16台处理器仿台处理器仿ILLIAC 的连接模式进行互的连接模式进行互连的互连结

16、构图，列出连的互连结构图，列出PE0分别经一步、二步和三分别经一步、二步和三步传送，能将信息传送到的各处理器号。步传送，能将信息传送到的各处理器号。134PU0PU1PU2PU3PU4PU5PU6PU7PU8PU9PU10PU11PU12PU13PU14PU15环怎么连环怎么连除了画图表达除了画图表达还要搞清楚互联还要搞清楚互联函数函数135PE0（PU0）经一步可将信息传送至）经一步可将信息传送至PU1、PU4、PU12、PU15。PE0（PU0）至少需经二步才能将信息传送至）至少需经二步才能将信息传送至PU2、PU3、PU5、PU8、PU11、PU13、PU14。PE0（PU0）至少需经三

17、步才能将信息传送至）至少需经三步才能将信息传送至PU6、PU7、PU9、PU10。1366-2 编号为编号为0、1、15的的16个处理器用单级个处理器用单级互连网络互连。当互连函数分别为互连网络互连。当互连函数分别为(1)Cube3(2)PM2+3(3)PM2-0(4)Shuffle(5)Shuffle(Shuffle)单级单级13716个处理器的编号可用个处理器的编号可用4位二进制位二进制P3P2P1P0表示，其中表示，其中第第13号处理器的二进制编号为号处理器的二进制编号为1101。(1)Cube3=P3P2P1P0=01012=5。(2)PM2+3=j+23(mod 16)=13+8(m

18、od 16)=5(3)PM2-0=j-20(mod 16)=13-1(mod 16)=12(4)Shuffle=P2P1P0P3=10112=11(5)Shuffle(Shuffle)=P1P0P3P2=01112=73P互联函数必须都记住互联函数必须都记住建立一个建立一个 欧米茄欧米茄 欧米茄网络是什么网络欧米茄网络是什么网络典型的是典型的是16个个控制信号：用的是什么控制信号，级控制还是单元控制控制信号：用的是什么控制信号，级控制还是单元控制=路线不同路线不同同一个信号控制下，同路存在，可同时通信同一个信号控制下，同路存在，可同时通信但如果用到同一个开关，而且方向相反，必须注意但如果用到同一个开关，而且方向相反，必须注意138