第一章 概论(次重点)

第二章 数据表示、寻址方式与指令系统(重点)

可能存在大题

1、浮点数计算

根据国际IEEE_754,任意一个进制数浮点数V可也表示成下面的形式。

$V=(-1)^s*M*R^E$

1、$(-1)^s$表示符号位,当s=0时,v为正数,当s=1时,v为负数

2、M表示有效数字,大于等于1,小于2;

3、$R^E$表示指数位

4、R基数,表示十进制数R就是10,表示二进制数R就是2

2、浮点数相关公式

1、$r_m$:浮点数基、$p$:阶值位数、$m$:尾数位数

2、$m^′=m/{log_2}{r_m}$

3、最小阶值:0

4、最大阶值:$2^p-1$

5、阶的个数:$2^p$

6、最小尾数值:$r_m^{-1}$

7、最大尾数值:$1-r_m^{-m^′}$

8、可表示的最小值:$r_m^{-1}$

9、可表示的最大值:$r_m^{2^p-1}*(1-r_m^{-m^′})$

10、可表示的数的个数:${2^p}*{r_m^{m′}(1-\frac{1}{r_m})}$

3、指令优化(哈夫曼编码)

列:假设模型机共有7条指令,使用频度如下:

指令	使用频度($p_i$)	指令	使用频度($p_i$)
I1	0.15	I5	0.05
I2	0.03	I6	0.3
I3	0.4	I7	0.03
I4	0.04

(1)若操作码用定长码表示,求操作码的码长、信息源熵H和信息冗余率。

• 定长码:${log_2}^8=3$,这里指数为8,是因为总共7条指令,但是7不是2的指数倍,所以向上取整,使其刚好是2的值数倍,公式：${log_2}^n$
• 信息源熵H(最小理论值):$H=-\sum_{i=1}^{7}\ast{p_i}\ast{log_2}^{p_i}$
• H=0.15*2.73+0.03*5.05+0.4*1.32+0.04*4.64+0.05*4.32+0.3*1.73+0.03*5.05$\approx$2.17
• 信息冗余率=$\frac{平均码长-H}{平均码长}$=$\frac{3-2.17}{3}=$28% (2)采用哈夫曼编码,构造哈夫曼树,并求操作码平均码长和信息冗余率。
• 第一步:按使用频度从小到大依次排列,0.03<=0.03<0.04<0.05<0.15<0.3<0.4
• 第二步:两个最小的频度,构成一个新的频度值,新的频度值同理放入上方列表中,依次排列,其中原始频度写在最下方,依次完成构建。最后树根节点依次往下标值,左1右0(相反也可也,很少用)。统计每个频度的码值串。整个过程如图:
• 平均码长为:$\sum_{i=1}^7{p_i}\ast{l_i}$ $l_i$:新的码长 0.4*1+0.3*2+0.15*3+0.05*5+0.04*5+0.03*5+0.03*5=2.2
• 信息冗余率: $\frac{2.2-2.17}{2.2}$=1.36%

(3)采用扩展操作码编码,求操作码平均码长和信息冗余率。

• 根据哈夫曼编码结果,需要4种码长才能表示,所以:${log_2}^4$=2; 其计算方式与前面完全哈夫曼编码一致,只是讲频度最高的指令,采用最小位标识,多出来的作为扩展码继续优化剩余的指令;再求平均码长以及信息冗余率。

  指令	频度	码值	码长	扩展码值	码长
  I3	0.4	0	1	00	2
  I6	0.3	10	2	01	2
  I1	0.15	110	3	10	2
  I5	0.05	11100	5	1100	4
  I4	0.04	11101	5	1101	4
  I2	0.03	11110	5	1110	4
  I7	0.03	11111	5	1111	4

  平均码长: $\sum_{i=1}^{7}{p_i}\ast{l_i}$=0.4*2+0.3*2+0.15*2+0.05*4+0.04*4+0.03*4+0.03*4=2.3 信息冗余率: $\frac{2.3-2.17}{2.3}$=5.6%

第三章 存储、中断、总线与I/O系统(重点)

中断

可能存在大题

1、通道流量计算

2、并行主存

1. 单体单子、单体多字 公式: 频宽或者速率($B_m$)=字长($W$)/访问周期($T_m$)=$B_m=\frac{W}{T_m}$
2. 多体多字、多体单子 公式: $B_m=m*\frac{W}{T_m}$,m:模、m分体数或者m个存储体
3. 每个存储周期能访问到的平均字数 公式: $B=\frac{1-(1-\lambda)^m}{\lambda}$ $\lambda$:缓存队转移概率 4、总结话术 4.1 表面现象:提高模对提高频宽的影响甚微。 4.2 引申:m变大,会使工程复杂度变高,成本变高,实际性能可能更低。 4.3 总结:m不宜过大

3、并行主存的无冲突访问

1. 要实现无冲突访问,需要在给定二维数组上,线上找一个质数(只能被1或本身整除的数)。公式参考:$2^{2p}+1$

第四章 存储体系(次重点)

可能存在大题

1、页面替换算法

先进先出页面替换算法(FIFO)

把先进入内存的替换掉,依次写,第n次的页与前一次相同,即为命中,改考点与《操作系统》中的计算缺页相关内容大体相似。

近期未使用替换算法(LRU)

从当前页往前推,把距离当前页最远的页替换。如果给出的是地址流,需要先把地址转换成页;从第0位开始。 例题: 一、Cache—主存存储层次中,主存有0~7共8块,Cache为4块,采用组相联映像,分2组。假设Cache 已先后访问并预取进了主存的第4、1、3、6块,现访存块地址流又为1、2、4、1、3、7、0、2、5、6时,请完成: (1)画出用LRU替换算法,Cache内各块的实际替换过程图,并标出命中时刻。 基础知识:

实际替换过程图,以及命中时刻,以及此期间的Cache命中率

堆栈模拟(后进先出算法(FILO))

依次进栈,新进页自上而下从新进栈,命中率不区分页在主存中的顺序

第五章 标量处理机(重点、难点)

可能存在大题

1、时空图

相关公式

• 实际吞吐率 $T_p=\frac{n}{\sum_{i=1}^{m}\bigtriangleup_{t_i}+(n-1)\bigtriangleup_{t_j}}$,实际理解为,n条任务/n条任务执行完成耗时
• $\bigtriangleup_{t_j}$:流水线中的瓶颈流水线耗时
• $\bigtriangleup_{t_i}$:每一条任务耗时
• n:任务数 m:流水线或者说功能段
• $\sum_{i=1}^{m}\bigtriangleup_{t_i}$ :一条任务在m条流水线上的总耗时
• 效率公式 $\eta=\frac{n\sum_{i=1}^{m}\bigtriangleup_{t_i}}{m(\sum_{i=1}^{m}\bigtriangleup_{t_i}+(n-1)\bigtriangleup_{t_j})}$, 实际理解为实际总任务面积/时空图所占总面积

延迟禁止表和时空图

第六章 向量处理机(重点、难点)

可能存在大题

1、阵列处理机

2、CRAY-1向量流水处理

1. 启动访存:1拍
2. 访存:6拍
3. 送入流水线:1拍
4. 写入(存入):1拍
5. 整数加:3拍
6. 浮点加:6拍
7. 浮点乘:7拍
8. 浮点迭代和求权:14拍
9. 逻辑:2拍
10. 位原算:4拍
11. 通用公式:M+(N-1) M:第一条执行完成时间 N:元素位

第七章 多处理机

1、互联网络

1.1 单级网络

1.2 多级立方体网络

互连一般函数,以三级互连为列:$Cube(b_2b_1b_0)=b_2\,\overline{b_1}\,\overline{b_0}$

1.3 多级混洗交换网络

1、霍纳法则

1. 运算级数:平行的算每一个运算算一级$T_l$
2. 运算级数:从根节点到最低部:$T_p$
3. 加速比:$S_p=T_l/T_p$
4. 效率:$E_p=S_p/P$ ,$P$:处理机个数

1、FORK JOIN

列题:

第八章 数据流计算机和归约机

延伸阅读