曾道免费资料大全正版l
大学生考试网 让学习变简单
赞助商链接

计算机体系结构作业答案(高性能)

计算机体系结构作业答案(高性能)

曾道免费资料大全正版l www.140827.com




第一讲:计算机系统基础

1. 在三台不同指令系统的计算机上运行同一程序 P 时,A 机需要执行 1.0*10 条指令,B 机 需要执行 2.0*10 条指令,C 机需要执行 4.0*10 条指令,但实际执行时间都是 10 秒,请分 别计算这三台机器在实行程序 P 时的实际运行速度,以 MIPS 为单位。这三台计算机在运行 程序 P 时,哪台性能最高?为什么?
8 8

8

2. 如果要给标量处理器增加向量运算部件,并且假定向量模式的运算速度是标量模式的 8 倍,这里把向量模式所占的百分比时间称作向量化百分比。 a) 画出一张图来表示加速比和向量化百分比的关系,X 轴为向量化百分比,Y 轴为加速比。 b) 向量化百分比为多少时,加速比能达到 2?当加速比达到 2 时,向量模式占了运算运行 时间的百分之多少?向量化百分比为多少时,加速比能达到最大加速比的一半? c) 假设程序的向量化百分比为 70%。如果需要继续提升处理器的性能,一种方法是增加硬 件成本将向量部件的速度提高一倍,另外一种方法是通过改进编译器来提高向量模式的 应用范围,那么需要提升多少向量化百分比才能得到与向量部件运算速度提高一倍得到 相同的性能?你推荐哪一种设计方案?

3. 假设有一个代表典型应用的基准测试程序。一款不包含浮点部件的处理器(可以通过整 数指令的模拟来执行浮点指令)运行该基准程序的运行速度是 120MIPS,在该处理器上增加 浮点协处理器后运行该基准程序的运行速度是 80MIPS。下面给出了一些参数:I-基准测试 中整数指令的数目, F-基准测试中浮点指令的数目, Y-模拟一条浮点指令需要的整数指令 的数目, W-无浮点协处理器时基准程序的运行时间, B-有浮点协处理器时基准程序的运行 时间。 a) 用上面的参数符号表示出两种配置处理器的 MIPS 值。 b) 在没有协处理器的配置下,假定 F=8*10 ,Y=50,W=4 秒,求 I 的值。 c) 在上题的条件下,求 B 的值。 d) 在包含协处理器的配置下,系统的 MFLOPS 是多少? e) 你的同事想要购买这种协处理器来提高性能,而该配置下 MIPS 降低了,请问他的决策 正确吗?解释你的观点。
6

4. 假设晶片成品率的经验公式如下:晶片成品率 = (1+b*晶片面积/a) ,其中 a = 4 是衡 量工艺复杂度的参数。 a) 假设每 cm 晶圆的成本为 c,缺陷密度为 b = 0.6/cm ,利用电子表格,计算当晶片面积
1
2 2

-a

从 0.5cm 变化到 4cm 时晶片的成本。 然后, 适用数学分析工具拟合出晶片成本和面积关 系的多项式曲线,使其与电子表格中计算出来的数据相吻合。 b) 假设缺陷密度更高,b = 2.0/cm ,求最接近的最低次数的多项式。
2

2

2

5. 对某处理器进行功耗测试,得到如下数据:时钟不翻转,电压 1.2V 时,电流为 500mA; 时钟频率为 1GHz,电压 1.2V 时,电流为 2500mA。请计算此处理器的静态功耗以及 500MHz 下的总功耗。

6. 证明以下结论: a) N 个正数的几何平均小于算术平均; b) 用归一化的 SPEC CPU2000 程序分值进行 A、B 两台机器的性能比较与所使用的参考机无 关;

7. 试讨论冯·诺伊曼结构的主要特点。 a) 查阅资料,分别给出一款 Intel、AMD、IBM 商业处理器的峰值性能和访存带宽。 b) 分析这 3 种处理器的访存带宽和存储层次参数(一级 cache 大小和延迟、二级 cache 大 小和延迟等)之间的关系。

8. 在一台个人计算机上(如 Pentium-4、Core、Opteron 的 CPU) a) 查阅相关资料,给出该机器的浮点运算峰值。

2

第二讲:二进制与逻辑电路

9. 定点数的表示 a) 分别给出 64 位定点原码和补码表示的数的范围。 解:[-2 , 2 -1] b) 在 32 位定点补码表示中,0x80000000 表示什么数? 解:-2
31 63 63

10. 浮点数的表示 a) 把单精度数转化为十进制数:0x7ff0000, 0xbe400000, 0xff800000 解 : 0x7ff0000=0,0000 1111,111 1111 0000 0000 0000 0000=(1.1111111)2*2 3.8368135610839464260099560574934e-34 0xbe400000=1,0111 1100,100 0000 0000 0000 0000=-(1.1)2*2 0xff800000=1,1111 1111,000 0000 0000 0000 0000=-∞ b) 把双精度数转化为十进制数:0x4035000000000000, 0x8008000000000000 解 : 0x4035000000000000=0,10000000011,0101000000000000000000000000000000000000 000000000000=(1.0101)2*2 0x8008000000000000 =
-1022 (1027-1023) (124-127) (15-127)

=

=-0.1875

=21

1,00000000000,1000000000000000000000000000000000000000 =-2
-1023

000000000000=-(0.1)2*2

c) 把十进制数转化为单精度数:-100.0, 0.25 解:-100.0=-(1.100100)2*2 =0b1 10000101 10010000000000000000000=0xc2c80000 0.25=(1.0)*2 =0b0 01111101 00000000000000000000000=0x3e800000; d) 把十进制数转化为双精度数:1024.0,0.25 解:1024.0=(1.0)*2 =0x4090000000000000 0.25=(1.0)*2 =0x3fd0000000000000
-2 10 -2 6

11. 画出 e=a*b+c*d 的晶体管级电路图。 解:

3

VDD

a

b

a

VDD

b e

GND

VDD

c

d

GND

c

d

GND

12. 计算一个 FO4 的延迟,假设反向器的输入电容为 0.0036pf,平均每个负载连线电容为 0.0044pf,翻转延迟为 0.023ns,每 pf 延迟为 4.5ns。 解: FO4 指的是某类型的电路单元驱动四个相同类型的电路单元。 FO4 延迟=本征延迟+负载延迟=0.023+4.5*((0.0036+0.0044)*4)=0.167ns

13. 分析 CMOS EDFF 触发器的建立时间、保持时间、和 CLK->Q 的构成。对于下图的电路, 假设反相器的延迟为 1ns,传输门从源到漏(或从漏到源)的延迟为 0.5ns,传输门从栅到漏 (或源)的延迟为 0.75ns,不考虑由于 latch 的 fight 对反相器延迟的影响。请从概念上 分析此电路的 setup 时间和 hold 时间为多少,给出分析过程。

4

解:

传输门的结构 许多数字电路设计都是以库单元为基本单位, 这些库单元将传统的晶体管电路设计 “封 装”起来,只提供数字电路设计者所关心的时序、面积、功耗等信息。正是这种“封装” , 促进了数字电路 EDA 工具的发展, 解放了电路设计人员的生产力, 极大丰富电子芯片种类和 数量。 本题深入到库单元内部的电路结构,讨论数字电路设计者所看到的某触发器建立时间、 保持时间和 CLK?Q 时间等时序的形成原因。 数字电路设计者看到的“封装”后的触发器如下图所示

而题中所给图是该触发器内部电路结构图,触发器内部的两个传输门控制端信号 C 和

CN 就是时钟信号形成的,它控制电路相应部分的开启和关闭。我们先观察触发器内部时钟
延迟:

5

CK ? C:经过两级反相器,1+1=2 ns CK ? CN:经过一级反相器和两级传输门,传输门的输入到输出延迟就是传输门源到漏 (或漏到源)的时间(参考传输门晶体管结构) ,1+0.5+0.5=2 ns

观察如上图所示的触发器结构图,在 C=1(CN=0)时,前级传输门打开,D 端数据进入 N1,打破 N1 和 N2 之间的反相器环,强制将 N1 处状态改成与 D 端相同,N2 处状态改为与 D 端相反, 反相器环维持新的状态, 由于后级传输门关断, N2 处状态无法传播到 N3 处。 当 C=0 (CN=1)时,前级传输门关闭,D 端数据无法影响触发器内部状态,而后级传输门打开,触 发器状态则通过 N3、 N4 和 Q 输出, 同时 N3 和 N4 间反相器环状态也被打破更改为与 N2 相符, 当下一个 C=1(CN=0)关闭后级传输门时,N3 和 N4 间反相器环仍能保持状态并驱动 Q 端。 建立时间指的是在时钟触发沿(此题为下降沿)到来之前数据(D 端)必须稳定的时间。 换句话说,此触发器的建立时间就是在时钟信号到达 CK 端之前,将触发器内部 N1 及 N2 状 态改变并稳定为与 D 端数据相符所需的时间。这样,D 端数据必须通过 D ? N0 ? N1 ? N2 才能真正改变触发器内部状态,但即使如此,由于 N1 和 N2 间反相器环驱动能力不能确定, 为保守起见,还需要加上 N2 ? N1 时间。此外考虑到接口处 CK 端时钟信号到 C 和 CN 的传 播时延,如果 C 和 CN 的传播时延不一,可能导致传输门输出弱 1 或弱 0 情况,仍从保守情 况出发取两者的较小值,另外还要算上传输门控制端栅到漏(源)的延迟。这样,该触发器 建 立 时 间 Tsetup=TD-N0-N1-N2-N1 - (min(TCK-C,TCK-CN)+Ttran)=(1+0.5 + 1+1)(min(2,2)+0.75)=0.75 ns 保持时间指的是在时钟触发沿到来之后数据必须保持不变的时间。 换句话说, 此触发器

6

的保持时间就是在时钟信号到达 CK 端之后,D 端需要等待多长时间,使得即使其数据变化 也不影响触发器内部状态。 反过来想, 那什么情况下 D 端数据变化可能会影响内部状态呢? 只有当前级传输门在完全关断之前, D 端数据已经进入到 N1, 进而才有可能对内部状态产生 影响。所以只需保证在前级传输门关断时变化的 D 端数据不进入 N1 即可。此外也要考虑到 时钟信号的传播延迟,仍从保守情况出发取两者较大值,加上传输门控制端栅到漏(源)的 延迟。这样, Thold=(max(TCK-C,TCK-CN)+Ttran) - TD-N0-N1 = (max(2,2)+0.75)-(1+0.5) =1.25ns CK ? Q 时间指的是时钟触发沿到来之后 Q 端输出新的触发器状态所需的时间。只有当 后级传输门打开后,Q 端才有可能与触发器内部状态相符,也就是 C=1?0(CN=0?1)时钟 下降沿时,这时候 N2 处的状态需要通过 N2 ? N3 ? N4 ? Q,此时由于后级传输门出于 打开状态,N3-N4 处的反相器环一般不可能再破坏这个新状态。此外仍出于保守考虑时钟信 号的传播延迟取较大值,并加上传输门控制端栅到漏(源)的延迟。这样,该触发器 CK ? Q 时 间 TCK-Q=(max(TCK-C,TCK-CN)+Ttran) +TN2-N3-N4-Q=(max(2,2)+0.75)+(0.5+1+1) =5.25ns

第三讲 指令系统结构

14. 给定下面的代码片段: A=B-C; D=A-C; B=D+A; a) 分别写出上述代码片段在四种指令系统类型(堆栈型、累加器型、寄存器-存储器型、 寄存器-寄存器型)下的汇编语言代码。 b) 假设操作码占用 8 位编码,内存地址和操作数都是 16 位,寄存器型结构有 16 个通用寄 存器。对每种结构回答以下问题:1)需要读取多少指令字节?2)与内存交换的数据有 多少字节?3) 依据代码量衡量哪种结构最好?4) 依据与内存交换的数据 (指令和数据) 量衡量哪种结构最好? 解: stack Push B Push C Sub Pop A Load C Neg Add B Store A
7

acc

R-M Load R1,B Sub R1,C Store R1,A Sub R1,C

R-R Load R1,B Load R2,C Sub R3,R1,R2 Store R3,A

Push A Push C Sub Pop D Push D Push A Add Pop B

Load C Neg Add A Store D Add A Store B

Store R1,D Add R1,A Store R1,B

Sub R4,R3,R2 Store R4,D Add R5,R4,R3 Store R5,B

1、30;18; ; ; 2、24;16;√; ; 3、28;14; ; ; 4、29; 10; ;√;

15. 16 进制数 0x4C4F4F4E47534F4E 要存在 64 位双字中。 a) 假设存储是 8 字节对齐的,请依据小尾端的格式将此 16 进制数写入内存中,并将每个 字节解释为一个 ASCII 字符写在对应的字节下边。 解:
Address 0x 0xxx000 4E 0xxx001 4F 0xxx010 53 0xxx011 47 0xxx100 4E 0xxx101 4F 0xxx110 4F 0xxx111 4C

b) 按照大尾端的格式重做上题。 解:
Address 0x 0xxx000 4C 0xxx001 4F 0xxx010 4F 0xxx011 4E 0xxx100 47 0xxx101 53 0xxx110 4F 0xxx111 4E

16. 根据 MIPS 指令的编码格式回答下列问题: a) 条件转移指令的跳转范围。 解:16+2 位 256KB(+-128KB)



指令都是

字节对齐的, 即寻址时都是

字节

字节寻址, 所以寻址范围为

,

以下同) b) 直接跳转指令的跳转范围。 解:26+2 位 256MB(+-128MB)
8

17. 用 MIPS 的 LWL/LWR/SWL/SWR 指令编写一段程序,把内存单元 1005-1008 的值取到 R1, 并存到内存单元 2005-2008. 解: 小尾端下 dli r2, 1005 lwr r1, 0x0(r2) lwl r1, 0x3(r2) dli r2, 2005 swr r1, 0x0(r2) swl r1, 0x3(r2)

18. 用 MIPS 的 LL/SC 指令编写一段从内存单元 100(R2)取数、把取出来的数加 100 并存回 到 100(R2)的原子操作代码,并说明如果在此过程中处理器发生终端或该单元被其它处理器 修改时处理器如何保证上述操作的原子性。 解: 1:ll r1, 100(r2) add r1, r1, 100 sc r1, 100(r2) beqz r1, 1b nop 如果在 ll 和 sc 之间(含 ll 和 sc) ,发生了中断或者其他处理器修改 100(r2),则 sc 之后 r1 会变 0,回到标号 1 重新执行。

19. 列出 X86 和 MIPS 的所有减法指令(包括不同字长、定点和浮点、不同寻址方式等)并 比较它们的异同。 解: 的减法指令如下: 定点减法:

9

影响: 被影响 模式下例外:

模式下例外

10

模式下例外



模式下例外 模式 模式例外

浮点减法指令如下:

和 影响:

将定点转化为

的扩展双精度浮点格式

11

浮点例外:

模式下例外:

模式下例外

模式下例外



模式下例外 模式 模式例外

12

的减法如下: 定点减法: 减法 例外: 无符号减法 例外: 减法 限制:

例外: 无符号减法 限制:

例外: 无 浮点减法 如下: 单精度 双精度 并行单精度 将



的上下两部分分别相减

限制:

例外: 浮点例外:

和 字长:

减法指令比较:

13

的定点减法指令支持 位、 位、 位、 位字长;而 定点减法支持 位和 位字长。 浮点: 的浮点减法指令均为 位扩展双精度格式;而 浮点减法支持单精度、双精 度和并行单精度格式。 寻址方式: 的减法只支持寄存器寻址。 的定点减法支持寄存器寻址、立即数和内存寻址方式 直接寻址、变址寻址、间接 寻址、基址寻址、基址加变址寻址 ; 的浮点减法支持寄存器寻址 浮点寄存器栈 和内存寻址方式 直接寻址、变址寻址、 间接寻址、基址寻址、基址加变址寻址 。 其他区别: 的定点减法会修改 , 浮点减法会修改 , 而 的减法没有 。 的减法和 减法产生的例外由于体系结构的不同而有很大不同: 的减法会产生 例外、 例外;除了 在 模式下之外,还会产生 例外、 例 外;所有的浮点减法还会产生 ( )例 外;在 模式下进行浮点减法还会产生 ( )例外。 的 、 和所有的浮点减法会触发保留指令例外, 和 会 触发溢出例外,浮点减法会触发协处理器不可用例外和一些浮点例外

20. 给出以下常见处理器中至少三种的 load-use 延迟:Pentium III, Pentium IV, MIPS R10000, Alpha 21264, HP PA8000, Ultra Sparc III, Itanium II, Power IV, AMD K8. 解: Pentium: 2cycle Pentium 4: 2cycle (fix)/6cycle (float) Alpha21264 : 3cycle Itanium II: 0cycle MIPS R10000: 2cycle HP PA8000: 2cycle Ultra Sparc III : 2cycle Godson-2/Godson-3: 3cycle (fix)/4cycle (float)

14

第四讲 静态流水线 21. 假定某 RISC 处理器为标准的五级流水线 (IF/ID/EX/MEM/WB) 结构, 并且包含旁路硬件。 对于下列指令序列: LW LW ADD SW LW ADD SW R1, 0(R0) R2, 4(R0) R3, R1, R2 R3, 12(R0) R4, 8(R0) R5, R1, R4 R5, 16(R0) ; c=b+f ; a=b+e

分析上述指令序列之间的相关, 并重排序执行序列避免相关。 重排序指令序列可以比原先指 令序列的执行减少多少拍?

22. 对于下面的计算: A = A + B C = A - B 写出 MIPS 程序代码,并且画出 5 级静态流水线(无旁路)上的流水线状态。

23. 对于向量加法 X(i)= a*X(i) + Y(i),假设 X,Y 的首地址分别存在 R1,R2,a 的值存 在 F0 中。 a) 试写出对应的 MIPS 汇编代码。 b) 假设单发射流水线结构为 IF/ID/EX/MEM/WB,功能部件足够, Load、Store 操作和整数 操作都花费 1 个时钟周期,加法操作为 4 个周期,乘法操作为 10 个周期。给出第一个 循环所有指令的流水线时空图。

24. 假定某 RISC 处理器为标准的五级流水线(IF/ID/EX/MEM/WB)结构,该静态流水线处理 器可配置包含硬件旁路电路、延迟槽、分支预测等技术,并假定所有的运算和访存操作均为 一拍完成。下面的代码在该处理器中执行。 Loop: LD R1, 0(R2) ; 从地址 0+R2 处读入 R1 ; R1= R1+4 ; 将 R1 存入地址 0+R2 处 ; R2=R2+4 ; R4=R3-R2 ; R4 不等于 0 时跳转到 Loop
15

DADDI R1, R1, #4 SD 0(R2), R1

DADDI R2, R2, #4 DSUB BNEZ R4, R3, R2 R4, Loop

已知 R3 的初值为 R2+400。 a) 不使用旁路硬件,但在同一个周期内寄存器的读和写能进行旁路,分支预测采用 not taken 策略,如果猜测错误则刷新(flushing)流水线上的错误指令,画出这个指令序 列在 RISC 流水线上执行的时序,并计算执行这个循环需要多少个时钟周期。 b) 使用旁路硬件,采用 taken 策略进行分支预测,如果猜测错误则刷新(flushing)流水 线上的错误指令,画出这个指令序列在 RISC 上执行的序列,并计算执行这个循环需要 多少个时钟周期。 c) 假设 RISC 流水线带有单拍的分支延迟和前递或旁路硬件,对包括延迟槽在内的指令序 列进行调度,可以重排指令序列,并修改某些指令的操作数,但不能改变指令的数目和 采用别的指令,画出该流水线的时序图,并计算整个循环需要的时钟周期数。

25. 许多指令集中都会有一条空操作指令 (例如 MIPS 指令集中的 nop 指令) , 请给出设计空 指令的几个作用。

26. 下面是静态流水线章节中讲述的 5 级流水处理器的部分 Verilog 代码。 a) (硕士)请完善其中的 ALU ???。 b) (博士) 请完善该 CPU 的代码并并编写一个定点乘法程序在该 CPU 模拟环境上正确执行。 注意,不用考虑 Forwarding,ALU 部件可以直接用+号,每一级流水都要有有效位,0 号通 用寄存器的值恒为 0。 15 14 13 12 11 10 9 ADD SUB AND OR NOT SL SR SRU ADDI LD ST BZ 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 rd rd rd rd rd rd rd rd rd rd rd 000 8 7 rs1 rs1 rs1 rs1 rs1 rs1 rs1 rs1 rs1 base base rs1 6 5 4 rs2 rs2 rs2 rs2 rs2 rs2 rs2 rs2 imm offset offset offset 3 2 1 000 000 000 000 000 000 000 000 0

16

BGT BLE

1100 1100

001 010

rs1 rs1

offset offset

`timescale 1ns/10ps module system; wire clock,reset;

cpu cpu00(.clock(clock),.reset(reset));

initial clock<=1'b0; always #20 clock<=~clock;

initial begin #0 reset<=1'b1; #70 reset<=1'b0; end

17

endmodule

module cpu(clock,reset); input clock; input reset;

wire [17:0]brbus; wire [15:0]inst; wire [2:0] ex_dest,mem_dest,wb_dest; wire [19:0]wbbus; wire [55:0]idbus; wire [39:0]exbus; wire [39:0]membus;

fetch_module fetch(.clock(clock),.reset(reset),.brbus(brbus),.inst(inst));

decode_module decode(.clock(clock),.reset(reset),.inst(inst), .ex_dest(ex_dest),.mem_dest(mem_dest),.wb_dest(wb_dest), .wbbus(wbbus),.brbus(brbus),.idbus(idbus));

alu_module alu(.clock(clock),.reset(reset), .idbus(idbus),.exbus(exbus),.ex_dest(ex_dest));

mem_module mem(.clock(clock),.reset(reset), .exbus(exbus),.membus(membus),.mem_dest(mem_dest));

wb_module wb(.clock(clock),.reset(reset), .membus(membus),.wbbus(wbbus),.wb_dest(wb_dest));

endmodule

`timescale 1ns/10ps module fetch_module(clock,reset,brbus,inst);
18

input clock; input reset; input [17:0]brbus; output [15:0] inst;

reg [15:0] pc;

wire brbus_valid; wire brbus_taken; wire [15:0]brbus_offset;

assign brbus_valid=brbus[17]; assign brbus_taken=brbus[16]; assign brbus_offset=brbus[15:0];

// -- Enter your statements here -- //

endmodule

`timescale 1ns/10ps module decode_module(clock,reset,inst,ex_dest,mem_dest,wb_dest,wbbus,brbus,idbus); input clock; input reset; input [15:0]inst; input [2:0] ex_dest,mem_dest,wb_dest; input [19:0]wbbus; output [55:0]idbus; output [17:0]brbus; reg [15:0] ir;

wire wbbus_valid; wire [2:0]wbbus_dest; wire [15:0]wbbus_value;
19

wire idbus_valid; wire [3:0]idbus_op; wire [2:0]idbus_dest; wire [15:0]idbus_value1; wire [15:0]idbus_value2; wire [15:0]idbus_stvalue;

wire brbus_valid; wire brbus_taken; wire [15:0]brbus_offset;

assign wbbus_valid=wbbus[19]; assign wbbus_dest=wbbus[18:16]; assign wbbus_value=wbbus[15:0];

// -- Enter your statements here -- //

assign brbus[17]=brbus_valid; assign brbus[16]=brbus_taken; assign brbus[15:0]=brbus_offset;

assign idbus[55]=idbus_valid; assign idbus[54:51]=idbus_op; assign idbus[50:48]=idbus_dest; assign idbus[47:32]=idbus_value1; assign idbus[31:16]=idbus_value2; assign idbus[15:0]=idbus_stvalue;

endmodule

`timescale 1ns/10ps module alu_module(clock,reset,idbus,exbus,ex_dest); input clock;
20

input reset; input [55:0]idbus; output [39:0]exbus; output [2:0]ex_dest;

wire idbus_valid; wire [3:0]idbus_op; wire [2:0]idbus_dest; wire [15:0]idbus_value1; wire [15:0]idbus_value2; wire [15:0]idbus_stvalue;

wire exbus_valid; wire [3:0]exbus_op; wire [2:0]exbus_dest; wire [15:0]exbus_exresult; wire [15:0]exbus_stvalue;

assign idbus_valid=idbus[55]; assign idbus_op=idbus[54:51]; assign idbus_dest=idbus[50:48]; assign idbus_value1=idbus[47:32]; assign idbus_value2=idbus[31:16]; assign idbus_stvalue=idbus[15:0];

// -- Enter your statements here -- //

assign exbus[39]=exbus_valid; assign exbus[38:35]=exbus_op; assign exbus[34:32]=exbus_dest; assign exbus[31:16]=exbus_exresult; assign exbus[15:0]=exbus_stvalue;

endmodule
21

`timescale 1ns/10ps module mem_module(clock,reset,exbus,membus,mem_dest); input clock; input reset; input [39:0]exbus; output [39:0]membus; output [2:0]mem_dest;

wire exbus_valid; wire [3:0]exbus_op; wire [2:0]exbus_dest; wire [15:0]exbus_exresult; wire [15:0]exbus_stvalue;

wire membus_valid; wire [3:0]membus_op; wire [2:0]membus_dest; wire [15:0]membus_exresult; wire [15:0]membus_memresult;

assign exbus_valid=exbus[39]; assign exbus_op=exbus[38:35]; assign exbus_dest=exbus[34:32]; assign exbus_exresult=exbus[31:16]; assign exbus_stvalue=exbus[15:0];

// -- Enter your statements here -- //

assign membus[39]=membus_valid; assign membus[38:35]=membus_op; assign membus[34:32]=membus_dest; assign membus[31:16]=membus_exresult; assign membus[15:0]=membus_memresult;
22

endmodule

`timescale 1ns/10ps module wb_module(clock,reset,membus,wbbus,wb_dest); input clock; input reset; input [39:0]membus; output [19:0]wbbus; output [2:0]wb_dest;

wire membus_valid; wire [3:0]membus_op; wire [2:0]membus_dest; wire [15:0]membus_exresult; wire [15:0]membus_memresult;

wire wbbus_valid; wire [2:0]wbbus_dest; wire [15:0]wbbus_value;

assign membus_valid=membus[39]; assign membus_op=membus[38:35]; assign membus_dest=membus[34:32]; assign membus_exresult=membus[31:16]; assign membus_memresult=membus[15:0];

// -- Enter your statements here -- //

assign wbbus[19]=wbbus_valid; assign wbbus[18:16]=wbbus_dest; assign wbbus[15:0]=wbbus_value;

endmodule
23

`timescale 1ns/10ps module rom(raddr,rout); input [11:0] raddr; output [15:0] rout;

reg [15:0] rom[4095:0]; integer i; initial begin $readmemb("rom.vlog",rom); $display("\nLoad rom successfully !!\n\n"); end assign rout = rom[raddr];

endmodule

`timescale 1ns/10ps module ram(clock,raddr,rout,wen,waddr,win); input clock; input wen; input [15:0] win; input [11:0] raddr; input [11:0] waddr; output [15:0] rout;

reg [15:0] ram[4095:0]; assign rout = ram[raddr];

always @(posedge clock) begin if (wen) begin ram[waddr] = win; end end
24

endmodule

`timescale 1ns/10ps module regfile(clock,raddr1,rout1,raddr2,rout2,wen, waddr,win); input clock; input wen; input [15:0] win; input [2:0] raddr1,raddr2; input [2:0] waddr; output [15:0] rout1,rout2;

reg [15:0] ram[7:0]; assign rout1 = ram[raddr1]; assign rout2 = ram[raddr2];

always @(posedge clock) begin ram[0]<=16'b0; if (wen) begin if(waddr!=0) ram[waddr]<= win; end end

endmodule

25

第五讲 动态流水线

27. 简述乱序流水线相对于按序流水线有哪些性能优势, 并给出一段代码说明这种设计在性 能方面的提高。

28. 对于以下的循环片段: 1 2 3 4 5 6 7 8 if(b>c){ d = d + 1; b = b + d + e; }else{ e = e + 1; f = f + e; c = b + f; } b = a + f;

假设只有 b 和 c 才会在后面的程序里继续使用, 并且假设在程序执行期间没有例外, 请描述 出这些指令序列之间所有类型的相关。 对于控制相关, 说明如何保持结果的正确性前提下把 程序段提在 if 语句之前执行。

29. 证明:如果如果数组元素 A(a*i+b)和 A(c*i+d)之间存在相关,那么 GCD(c,a)能够整出 (d-b)。

30. 请比较 Tomasulo 和计分牌方法分别是如何处理 RAW、WAR 和 WAW 相关的。

31. 请简述动态流水线中如何实现精确例外。

32. 以下这个循环是高斯消元法中的核心操作, 称为 DAXPY 循环 (双精度的 a 乘以 X 再加上 Y) ,以下代码实现了对长度为 100 的向量进行 DAXPY 操作:Y = a * X + Y。 bar: L.D MUL.D L.D ADD.D S.D DADDUI F2, 0(R1) F4, F2, F0 F6, 0(R2) F6, F4, F6 0(R2), F6 R1, R1, #8 ; 取数 X(i) ; 乘法操作 a * X(i) ; 取数 Y(i) ; 加法操作 a * X(i) + Y(i) ; 存数 Y(i) ; X 的下标加 1
26

DADDUI DSGTUI BEQZ

R2, R2, #8 R3, R1, #800 R3, bar

; Y 的下标加 1 ; 测试循环是否结束 ; 如果循环没有结束,转移到 bar

在单发射静态流水线上,假定浮点流水线的延迟如下表所示,分支指令在译码阶段(ID)计 算结果,采用了分支延迟槽技术,整数操作在一拍之内发射和完成,并且结果是完全旁路的 (fully bypassed) 。 产生结果的指令 FP ALU op FP ALU op Load double Load double 使用结果的指令 延迟(时钟周期)

Another FP ALU op 3 Store double FP ALU op Store double 2 1 0

a) 把这个循环展开足够的次数,要求消除所有停顿周期和循环开销指令。循环将会被展开 多少次?写出调度后的代码,每产生一个结果需要多少执行时间? b) 写出 DAXPY 循环在软件流水后的代码,可以省略软件流水的装入代码和排空代码,每产 生一个结果需要多少执行时间?

33. 假设有一个如下图所示的支持精确例外处理的浮点流水线。 流水线分成发射、 执行并写 回、以及提交三个阶段,其中浮点加法部件延迟为 2 拍(即假设第 T 拍操作数准备好开始运 算,第 T+1 拍可以写回结果) ,浮点乘法部件延迟为 3 拍,浮点操作队列中已有图中所示的 指令,请给出 6 拍内每一拍的寄存器以及结果总线值的变化。

27

第六讲 多发射结构数据通路

34. 假定一个 4 发射的处理器,每拍可以取指 4 条指令,译码 4 条指令,发射 4 条指令,提 交时从 Reorder Buffer 提交 4 条指令,在发射和提交时需要检查哪些数据相关?试画出发 射时和提交时相关的检测硬件图。 解: 发射时: 检查 4 条指令的源寄存器的状态以判断是否存在和之前的指令的 RAW 相关。 判断第 2,3,4 条指令的源寄存器是否和第 1 条指令的目的寄存器相关。 判断第 3,4 条指令的源寄存器是否和第 2 条指令的目的寄存器相关。 判断第 4 条指令的源寄存器是否和第 3 条指令的目的寄存器相关。 提交时: 按指令顺序提交即可。

35. 在多发射乱序执行的处理器上,编译器的调度还需要吗?举例说明。 解: 需要,动态调度只能处理 200 条指令以内的相关。编译器可以在更大的范围上进行调度。例 如死代码删除、软流水等技术只能通过编译器来实现。

36. 以下有 4 段 MIPS 代码片段,每段包含两条指令: 1) DADDI R2, R2, 2 LD R2, 4(R2)

2) DSUB R3,R1,R2 SD 3) S.D S.D 4) BLE SD R2, 7(R1) F2, 7(R1) F2, 200(R7) R2, place R2, 7(R2)

a) 分析上述 4 个代码片段,给出可能的相关和解决办法。 解:1)存在 RAW 相关和 WAW 相关??梢酝ü拇嫫髦孛饩?2)不存在相关 3)访存相关,可以通过维护处理器序的访存队列来解决 4)不存在相关
28

b) 假设目标硬件的流水线是支持乱序执行的双发射结构,每个代码段的两条指令能够同时 发射吗? 解:不能,能,能,能。访存相关一般都是同时发射,等发现冲突了再说。

37. 假设流水线延迟如下表所示,分支延迟为 1 个周期,没有延迟槽。 产生结果的指令 FP ALU op FP ALU op Load double Load double 使用结果的指令 延迟(时钟周期)

Another FP ALU op 3 Store double FP ALU op Store double 3 1 0

下面循环计算 Y[i] = a*X[i] + Y[i]高斯消元法中的关键一步。 L: L.D L.D MUL.D ADD.D S.D DSUBUI DSUBUI BNEZ F4,0(R2) F0, 0(R1) F0,F0,F2 F0,F0,F4 F0,0(R2) R2,R2,8 R1,R1,8 R1,L ;读 Y[i] ;读 X[i] ;求 a*X[i] ;求 a*X[i]+Y[i] ;保存 Y[i]

a) 假设目标机器的流水线是单发射的,将次循环展开足够的次数,使得代码执行没有不必 要的延迟,写出调度后的代码并计算一个元素的执行时间。 b) 假设目标机器的流水线是双发射的,将次循环展开足够的次数,使得代码执行没有不必 要的延迟,写出调度后的代码并计算一个元素的执行时间。 c) 自己写一段与题中类似的 C 代码,用 gcc 的不同优化遍编译后,查看汇编代码,对不同 优化遍进行比较,描述 gcc 做的优化。 解: a) L: L.D L.D MUL.D MUL.D L.D L.D ADD.D F0,0(R1) F1,-8(R1) F0,F0,F2 F1,F1,F2 F4,0(R2) F5,-8(R2) F0,F0,F4
29

ADD.D DSUBUI DSUBUI S.D S.D BNEZ NOP 7 拍一个

F1,F1,F5 R2,R2,16 R1,R1,16 F0,16(R2) F1,8(R2) R1,L

b)依赖于哪些指令可以共同发射,定点、浮点和访存各有几个功能部件 c) O0:X[i]和 Y[i]地址放在栈上,每次访问需要两次访存。所有局部变量映射到内存地址 而不是寄存器, 因此每次访问都必须要有 load/store。 没有循环展开, 延迟槽指令 nop。 O2: 局部变量放在寄存器中,延迟槽用了起来但是没有循环展开。

38. 一个 n 发射的处理器,流水线情况如下:取值,译码,重命名到物理寄存器后送入发射 队列,发射队列乱序发射,功能部件乱序执行,乱序写回物理寄存器,最后顺序提交并释放 物理寄存器。已知该处理器有 m 个逻辑寄存器,i 个功能部件(i>n),每条指令从重命名 到写回需要 t1 拍,从重命名到提交需要 t2 拍。为了能让流水线满负荷工作,最少需要多少 个物理寄存器?(提示:并不是每个参数都有用) 解:m+n*t2

39. 设计一个采用如下结构的流水线,画出结构图并写出每个流水阶段的相应操作。 a) 采用物理寄存器堆重命名; b) 保留站后读寄存器; c) 全局保留站; d) 一个定点部件、一个浮点部件、一个访存部件; e) 双发射; f) 流水阶段:取指、译码(包括重命名) 、发射(包括读寄存器) 、执行(包括写回) 、提 交。 解 :

30

31

40. 请简述 Intel 的 Nehalem 处理器核的多发射机制。Nehalem 做了哪些措施来配合高的发 射宽度? 解: 4 发射如图

一条指令翻译成多条 -code,比较+branch 指令融合成一个 -code 28 项 -code 队列维护循环

L1 cache (32KB I + 32KB D), 4 cycle, a 256KB L2 cache (per core, unshared) 10 cycle, and up to an 8MB L3 cache (shared among all cores), 30cycle?

32

33

第七讲 转移猜测

41. 下表是转移猜测的 Yeh 和 Patt 分类中根据转移历史表(BHT)和模式历史表(PHT)的 不同组合形成的转移猜测种类。PC 中用来索引 BHT 表的位数为低 6 位,索引 PHT 表的位数 为低 8 位,BHT 表每项 8 位,请画出 SAs 转移猜测的结构图,说明其基本原理,并计算该结 构使用的存储单元位数。 Global PHT Global BHT FP ALU op Load double 解:BHT 2 *8=512b PHT 2 *2 *2=131072b 共 131584b BHT 根据地址低 6 位选出一个 8 位向量, 和地址低 8 位一起到 PHT 中选取 2 位饱和计数。
8 8 6

Per address PHT Gap PAp SAp

Per set PHT GAs PAs SAs

GAg PAg SAg

42. 考虑下面一段 MIPS 代码,假设开始时 R1 寄存器存放值 a。 BNEZ DADDIU L1: DSUBUI BNEZ ? L2: 假定采用两位分支预测器, 第一位是程序中上一个分支未被执行的预测情况, 第二位是上一 个分支被执行时的预测情况。假设初始预测位 NT/NT,且 a 值以 0,1,0,1 的规律变化,画出 转移预测执行情况表,并统计预测错误的数目。 解: R1,L1 R1,R0,2 R2,R1,2 R2,L2 ;分支 b2 (a!=2) ;分支 b1 (a!=0) ;a==0,a 的值变为 2

34

A a 0 1 0 1

b1

b1 action NT T (miss) NT(miss) T(miss)

New b1 prediction NT/NT NT/T NT/NT NT/T

b2 prediction NT/NT NT/NT NT/T NT/NT

b2 action NT T(miss) NT T (miss)

New b2 prediction NT/NT NT/T NT/NT NT/T

prediction NT/NT NT/NT NT/T NT/NT

因此,总共有 5 次预测错误出现。

43. 一个流水线处理器为条件分支配置了一个分支目标缓冲器 BTB。假设预测错误的损失为 5 个时钟周期,BTB 不命中的开销是 3 个时钟周期,并假设 BTB 命中率为 90%,命中时预测 精度为 90%,分支频率为 20%,没有分支的基本 CPI 为 1,请计算: a) 该程序执行的 CPI。 b) 另外一个处理器没有转移猜测部件,每个分支有固定 2 个时钟周期的性能损失,与 a) 中的处理器比较执行速度。 解: a)20%*((90%*10%*5)+(10%*3))=0.15 b)20%2=0.4 1.4/1.15=1.22

35

44. 分析并列出下列循环中的所有相关,包括输出相关、反相关、真相关。将循环展开,分 析并讨论循环体间的相关。 for (i=2; i<N; i++) a[i] = a[i]+b[i]; { //S1 //S2 //S3 //S4

d[i+1] = a[i]-c[i]; a[i-1] = 1-b[i]; b[i+1] = 1+b[i]; } 解: 循环内: S1 中 a[i]反相关 S2 和 S1 中 a[i]真相关 循环间: S3 和 S1 中 a[i]输出相关 S3 和 S1 中 a[i]反相关 S3 和 S2 中 a[i]反相关 S4 和 S4 中 b[i+1]真相关 S3 和 S4 中 b[i+1]真相关 S1 和 S4 中 b[i+1]真相关
* * * * * *

45. 程序中数组运算一般配合循环使用, 通过数组下标可以判断循环是否可以完全流水, 描 述其原理。 (提示:下标表达式可以作为解析几何中的直线或者平面,可能需要考虑步长) 解: 原理是循环体间使用的数据不交叠(二者至少有一为写操作) 。 GCD: X[a*j+b] = X[c*k+d] GCD(a,c)整除(d-b)则有相关

46. 假设流水线延迟如下表所示,分支延迟为 1 个周期,有延迟槽。 产生结果的指令 FP ALU op FP ALU op Load double Load double 使用结果的指令 Another FP ALU op Store double FP ALU op Store double 延迟周期数 3 2 1 0

a) 下面程序段实现对数组元素增值,R1 存放循环初始次数。 L1: L.D F0,0(R1)
36

ADD.D S.D

F2,F0,F1 F2,0(R1)

DSUBUI R1,R1,8 BNE R1,R2,L1

写出完整的软件流水循环代码, 包括装入代码和排空代码, 并且计算软件流水循环完成 所有操作需要的总时间(时钟周期数)表达式(其中 R1=8n+R2) 。 b) 分析比较软件流水和循环展开两种方案的区别。 解: a)5*n-8 L1: S.D ADD.D L.D BNE F2,16(R1)//循环 i F2,F0,F1//循环 i+1 F0,0(R1) //循环 i+2 R1,R2,L1

DSUBUI R1,R1,8 装入排空省略 b)软流水没有降低分支频率;不需要额外寄存器

47. 请简述动态调度的处理器中在转移指令执行后如何实现转移猜测失败的取消。 解:失败的指令 rob 中来取消。Map 时给出指令的 brqid,转移失败后广播。

37

第八讲

功能部件 张戈

有两个 和

位的二进制数 ,请分别 和 和 和 以及 位的加法器的延迟。 需要 ) 代码。 (产生组间进位) 个且每个门的延迟 ,每一级产生结果的 指令 个且每个门的延迟

说出在下列情况下上述两个数的含义 补码 分别表示 无符号数;分别表示 单精度浮点数;分别表示 一条 指令:分别表示 假设每个“非门” 、 “与非门” 、 “或非门”的扇入不超过 为 ,请给出使用不同算法的 串行进位加法器; 每一级进位传递的延迟为 延迟为 ,因此生成 先行进位加法器 采用组内并行、组间并行, 位一组,参照第五题 延迟共 (产生 、 ) (产生每组 、 ) (产生组内进位) (全加器逻辑) 个 位数相加的延迟。 延迟 级全加器延迟( ) ,然 延 ,因此生成 需要(

假设每个“非门” 、 “与非门” 、 “或非门”的扇入不超过 为 ,请给出使用不同算法把 使用多个加法器; 采用先行进位加法器两两相加,需要 使用加法树及加法器。 使用加法树把四个数相加变成两个数相加,需要 后再使用先行进位加法器( 迟。 )得到最后结果,因此共

证明 补 补 补 假定带符号数 都在 位数表示范围之内,由于求补的本质是取模 运算,则它们的补码可以如下表示: 补 补 补 ,其中第 位舍弃。于是
补 补 补 补

(第 证毕


位舍弃) 写一个 位的先行进位加法器。
38

(硕士)用

39

40

48. IEEE-754 标准定义了四种格式的浮点数据类型:单精度、扩展单精度、双 精度以及扩展双精度。请完成如下列表: 参数 尾数位宽 P 指数最大值 Emax 指数最小值 Emin 指数偏移量 Bias 指数位数 浮点格式宽度 24 +127 -126 +127 8 32 格式 单精度 扩展单精度 32 1023 -1022 unspecified 11 43 53 +1023 -1022 +1023 11 64 双精度 扩展双精度 64 > 16383 -16382 unspecified 15 79

http://babbage.cs.qc.edu/courses/cs341/IEEE-754references.html 参见:IEEE-754 References 49. 下图是包括块间进位生成因子和进位传递因子的四位进位逻辑???, 用该逻 辑??樽榻?64 位先行进位加法器的进位逻辑,并证明其正确性。

41

ci+1 = ai*bi+ai*ci+bi*ci = ai*bi+(ai+bi)*ci = gi+pi*ci = gi + gi-1pi + ci-1pi-1pi = gi + gi-1pi + gi-2pi-1pi+ … + c0p0p1…pi (公式 1) gi=ai*bi 称为进位生成因子, 只要 gi 为 1, 就有进位,pi=ai+bi 称为进位传递 因子, 只要 pi 为 1, 就有把低位的进位向前传递 下面给出了四位进位传递 c1 = g0+(p0*c0) c2 = g1+(p1*g0)+(p1*p0*c0) c3 = g2+(p2*g1)+(p2*p1*g0)+(p2*p1*p0*c0) c4 = g3+(p3*g2)+(p3*p2*g1)+(p3*p2*p1*g0)+(p3*p2*p1*p0*c0) 下图给出了采用四位进位逻辑??槔词迪?16 位的先行进位加法器的逻辑框 图。相应的 64 位加法器根据公式 1 证明是正确的,其可以采用先行进位加法器 实现, 也可以采用把 64 位分为四个组, 每个组分别采用 16 位的先行进位加法器。 组和组之间通过行波进位加法器来互连, 当然也可以采用多级先行进位加法器来 实现,采用组内并行、组间也并行的进位方式。

42

c15-12

c11-8

c7-4

c3-0

c16

c4 p3 p1 g1 P G c3-0 c4 p3-0 g3-0 c0 p3-0 g3-0 g3 c1 P G c3-0 c4 c4 c0 p3-0 g3-0 P G c3-0 c12 P c4 c0 p3-0 G c3-0 c3 p2 g2 c2

c0

c16 c8

c4 c0

g3-0

p15-12 c0

g15-12

p11-8

g11-8

p7-4

g7-4

p3-0

g3-0

50. 采用 Booth 编码和 Wallace 数的乘法器经常需要累加[-X]补和[-2X]补。而[-X]


和[-2X]补涉及到取反加 1 的操作。请问乘法器是怎么避免单独加这些 1? 为了减少这种取反加 1 的开销,有必要找到一种部分冗余的表达,使得正数

和负数有相同的形式,并且很容易从正数产生负数,或者从负数产生正数。通常 采用带偏移量的 Booth 算法。 每个部分积在最终累加之前加上一个偏移量常数 K。 但是最终的结果开始相当于加了零,不会影响到正确性。例如变成 K+0 , K+Multiplicand…,K-2xMultiplicand…。K+multiple+Z = 2K, => Z = K-multiple, 使得 K-multple 容易从 K+multiple 得到。 51. (博士)IEEE-754 标准定义了四种舍入方式。请分别简要介绍这四种舍入 方式。 IEEE 754 标准: 舍入到最接近:将结果舍入为最接近且可以表示的值。 朝+∞方向舍入:将结果朝正无限大的方向舍入。 朝-∞方向舍入:将结果朝负无限大的方向舍入。 朝 0 方向舍入:将结果朝 0 的方向舍入。

52. (博士)用 Verilog 写一个 8 位的补码乘法器,要求采用 2 位 1 乘的 Booth

43

算法,采用先行进位加法器。
modulemul8(opa,opb,result); input[7:0] opa; input[7:0] opb; output[15:0]result; //----BoothEncoder--------------------wire wire wire[3:0] wire[8:0] wire[8:0] PP0_S,PP1_S,PP2_S,PP3_S; PP0_E,PP1_E,PP2_E,PP3_E; SelectM,Select2M; PP0_M,PP1_M,PP2_M,PP3_M; PP0,PP1,PP2,PP3;

assign PP0_S = opb[1]; assign PP1_S = opb[3]; assign PP2_S = opb[5]; assign PP3_S = opb[7]; assign SelectM[0] = opb[0]; assign SelectM[1] = opb[1]^opb[2]; assign SelectM[2] = opb[3]^opb[4]; assign SelectM[3] = opb[5]^opb[6]; assign Select2M[0] = opb[1] & !opb[0]; assign Select2M[1] = (opb[3]^opb[2]) & (opb[3]^opb[1]); assign Select2M[2] = (opb[5]^opb[4]) & (opb[5]^opb[3]); assign Select2M[3] = (opb[7]^opb[6]) & (opb[7]^opb[5]); assign PP0_E = (opa[7]==PP0_S) |(opb[1:0]==2'b0);

assign PP1_E = ( (opa[7]==PP1_S)&(opb[3:1]!=3'b111) ) | (opb[3:1]==3'b0); assign PP2_E = ( (opa[7]==PP2_S)&(opb[5:3]!=3'b111) ) | (opb[5:3]==3'b0); assign PP3_E = ( (opa[7]==PP3_S)&(opb[7:5]!=3'b111) ) | (opb[7:5]==3'b0); assign PP0_M = SelectM[0]? {opa[7],opa} : Select2M[0]? {opa,1'b0} : 9'b0 ; assign PP1_M = SelectM[1]? {opa[7],opa} : Select2M[1]? {opa,1'b0} : 9'b0 ; assign PP2_M = SelectM[2]? {opa[7],opa} : Select2M[2]? {opa,1'b0} : 9'b0 ; assign PP3_M = SelectM[3]? {opa[7],opa} : Select2M[3]? {opa,1'b0} : 9'b0 ;

44

assign PP0 = PP0_S? ~PP0_M : PP0_M; assign PP1 = PP1_S? ~PP1_M : PP1_M; assign PP2 = PP2_S? ~PP2_M : PP2_M; assign PP3 = PP3_S? ~PP3_M : PP3_M; //----------MUL tree,total 16 coloum ------------------------wire[15:0] sum,carry; wire cout0,cout1,cout2,cout3,cout4,cout5,cout6,cout7,cout8, cout9,cout10,cout11,cout12,cout13,cout14,cout15; CSA4_2 W0( .in({2'b0,PP0[0],PP0_S}),.cin(1'b0),.cout(cout0),.s(sum[0]),.c(carry[0]) ); CSA4_2 CSA4_2 W2( .in({1'b0,PP0[2],PP1[0],PP1_S}),.cin(cout1),.cout(cout2),.s(sum[2]),.c(carry[2]) ); CSA4_2 CSA4_2 W4( .in({PP0[4],PP1[2],PP2[0],PP2_S}),.cin(cout3),.cout(cout4),.s(sum[4]),.c(carry[4]) ); CSA4_2 W5( .in({1'b0,PP0[5],PP1[3],PP2[1]}),.cin(cout4),.cout(cout5),.s(sum[5]),.c(carry[5]) ); CSA4_2 W6( .in({PP0[6],PP1[4],PP2[2],PP3[0]}),.cin(cout5),.cout(cout6),.s(sum[6]),.c(carry[6]) ); CSA4_2 W7( .in({PP0[7],PP1[5],PP2[3],PP3[1]}),.cin(cout6),.cout(cout7),.s(sum[7]),.c(carry[7]) ); CSA4_2 W8( .in({PP0[8],PP1[6],PP2[4],PP3[2]}),.cin(cout7),.cout(cout8),.s(sum[8]),.c(carry[8]) ); CSA4_2 W9( .in({!PP0_E,PP1[7],PP2[5],PP3[3]}),.cin(cout8),.cout(cout9),.s(sum[9]),.c(carry[9]) ); CSA4_2 W10( .in({!PP0_E,PP1[8],PP2[6],PP3[4]}),.cin(cout9),.cout(cout10),.s(sum[10]),.c(carry[10] ) ); CSA4_2 W11( .in({PP0_E,PP1_E,PP2[7],PP3[5]}),.cin(cout10),.cout(cout11),.s(sum[11]),.c(carry[11] ) ); CSA4_2 W12( .in({2'b01,PP2[8],PP3[6]}),.cin(cout11),.cout(cout12),.s(sum[12]),.c(carry[12]) ); CSA4_2 W13( .in({2'b00,PP2_E,PP3[7]}),.cin(cout12),.cout(cout13),.s(sum[13]),.c(carry[13]) ); CSA4_2 W14( .in({3'b001,PP3[8]}),.cin(cout13),.cout(cout14),.s(sum[14]),.c(carry[14]) ); W3( .in({2'b0,PP0[3],PP1[1]}),.cin(cout2),.cout(cout3),.s(sum[3]),.c(carry[3]) ); W1( .in({3'b0,PP0[1]}),.cin(cout0),.cout(cout1),.s(sum[1]),.c(carry[1]) );

45

CSA4_2

W15( .in({3'b000,PP3_E}),.cin(cout14),.cout(cout15),.s(sum[15]),.c(carry[15]) );

//-----caculate s+c to get result--------------------------wire[9:0] wire[8:0] high_s; high_c;

assign high_s = sum[15:6]^carry[14:5]; assign high_c = sum[14:6]&carry[13:5]; add16 add16(.opa({high_s,sum[5:0]}),.opb({high_c,PP3_S,carry[4:0],1'b0}),.cin(0),.out(result)); endmodule //-------------------------------------------------------------------------------------module CSA4_2(in,cin,cout,s,c); input[3:0] in; input output output wire CSA3_2 CSA3_2 endmodule //--------------------------------------------------------------------------------------module CSA3_2(in,s,c); input[2:0] in; output s,c; cin; cout; s,c; temp; counter0( .in(in[2:0]),.s(temp),.c(cout) ); counter1( .in({in[3],temp,cin}),.s(s),.c(c) );

assign s = in[0]^in[1]^in[2]; assign c = (in[0]&in[1]) | (in[0]&in[2]) | (in[1]&in[2]); endmodule

46

第九讲

存储层次与 Cache 结构

53. 一个处理器页大小为 4KB, 一级数据 Cache 大小为 64KB, 指出在直接相联、 二路组相联、以及四路组相联的情况下需要页着色(page coloring) 的地址位 数。 解:由于一个页的大小是 4KB,所以需要的页内偏移为 12 位; (1) 直接相联: Cache 的(Index+Block_Offset)的位数为:16 位 从而 page coloring 的位数是:16-12=4 位; (2) 二路组相联: Cache 的(Index+Block_Offset)的位数为:15 位 从而 page coloring 的位数是:15-12=3 位; (3)四路组相联: Cache 的(Index+Block_Offset)的位数为:14 位 从而 page coloring 的位数是:14-12=2 位; (index 实际上就是 组数取对数,着色位可以用来判断实页到 cache 的映射关系, 相同着色位的实页会映射到同组 cache 中)

54. 在一个 32 位的系统中,采用基于字节的内存寻址方式,Cache 访问地址被 分为 13 位的标志(Tag) ,14 位的块索引(Index) ,5 位的字节偏移(Offset) 。 缺路数 a) Cache 容量大小是多少个字节? b) Cache 映射的方式是什么? 假设为两路组相联的 cache。offset 为 5,则 cache 行大小为 2^5=32 字节。 index 为 14,则 cache 行的数目为 2^14=16384。 a)cache 容量的大小为 2*16384*32 = 1024KB。 b)cache 的映射方式为组相联。

47

55. 通过分开指令 Cache 和数据 Cache,能够消除因指令和数据冲突而引起的 Cache 缺失。现有一个由大小都为 32KB 的指令 Cache 和数据 Cache 组成的系统 和另一个大小为 64KB 的一体 Cache 组成的系统相比较。 假设在所有的存储器访 问中数据访问占 26%,取指令占 74%。32KB 指令 Cache、数据 Cache 和 64KB 的一体 Cache 每千条指令缺失率分别为 1.5、38 和 40。Cache 命中时需要 1 个时 钟周期,缺失代价为 100 个时钟周期,在一体 Cache 中,Load 和 Store 命中需要 额外一个时钟周期。 a) 计算并比较哪一个组织方式有更低的缺失率? b)求出每种组织方式下的平均存储器访问时间? Answer: a) 74%*1.5 + 26% * 38 = 10.99。 则分离指令和数据 cache 的组织方式失效率更低。 b) (74%*1.5*100 + 74%*(1000-1.5) + 26%*38*100+26%*(1000-38) )/1000= 2.09 拍 (40*100+(1000-40)*74%+(1000-40)*26%*2) /1000 = 5.21 拍

56. 在一个顺序执行的主频为 1.0GHz 的处理器中,L1 到 L2 为写不分配,并且 写直达;L2 到内存为写分配,并且写回。L1 中指令 Cache 大小为 32KB,块大 小为 32 字节,缺失率为 2%;数据 Cache 大小为 32KB,块大小为 16 字节,缺 失率为 5%, 且数据 Cache 有一个写缓冲, 使所有写操作的停顿时间减少了 95%。 L2 大小为 512KB,块大小为 64 字节,缺失率为 20%,访问时间是 10ns。L2 与 L1 有 200MHz 的数据总线相连,一个总线周期可传输 128 字节(位) ,L2 被 替换出去的块中有 50%为脏块。主存的访问时间为 50ns,有 128 位宽 100MHz 的数据总线与 L2 cache 相连。 a) 试写出指令存取和读数据的平均内存访问时间的表达式。 b) 试写出写数据的平均内存访问时间的表达式。 c) 包含存储器访问在内,总的 CPI 是多少? d) 若要提高该系统运行速度, 存储系统的哪些部分需要改进?假设只提高一个 参数而其它参数保持不变,需要考虑的参数包括 L2 的速度、总线的速度、 内存的速度和 L1 以及 L2 的命中率。

48

Answer: 从内存传输一个 64 字节的 cache 行需要, 1G/100M*4=40 拍。 从 L2 cache 写出一 个脏块传输的时间同样需要 40 拍。从 L2 cache 传输一个 cache 行到 L1 cache 需 要 1G/200M=5 拍。 a)读指令,98%*1+2%*((1-20%)*10+20%*(50+45+20)) = 1.6 拍。读数据(load) 95%*1+5%*((1-20%)*10+20%*(50+45+20))=2.5 拍 b)写数据(store) , 95%*1+95%*((1-20%)*15+20%*(50+45+20))*5%+5%*((1-20%)*15+20%*(50+45 +20)) = 4.36 拍 c)CPI =读指令百分比%*1.6+读数据百分比*2.5+写数据百分比*4.36 = … d)L1 和 L2 cache 之间的时钟频率,L2 cache 和内存的时钟频率和带宽。写回式 L1 cache,非阻塞式 cache 等等。

57. 假定在一个只有 64 个字的内存中,有一个的内存地址访问序列为:0、1、2、 3、4、15、14、13、12、11、10、9、0、1、2、3、4、56、28、32、15、14、13、 12、0、1、2、3。对于某个 Cache 结构,内存访问可以分为 Cache 命中、强制 缺失、容量缺失、冲突缺失,假定下列的 Cache 参数,上述的访问序列中每次 内存访问分别属于哪一类? a) 直接相连,Cache 块大小为 16 个字节,容量大小为 4 个块。 b) 两路组相联,Cache 块大小为 8 个字节,容量大小为 4 个组,采用 LRU 替 换算法。 a) 0 - 3 4 - 7 8 -11 12-15 16-19 32-35 48-51 20-23 36-39 52-55

24-27 40-43 56-59 28-31 44-47 60-63

0(强制缺失) 、1(命中) 、2(命中) 、3(命中) 、4(强制缺失) 、15(强制缺失) 、 14(命中) 、13(命中) 、12(命中) 、11(强制缺失) 、10(命中) 、9(命中) 、0 (命中) 、1(命中) 、2(命中) 、3(命中) 、4(命中) 、56(强制缺失) 、28(强
49

制缺失) 、32(强制缺失) 、15(容量缺失) 、14(命中) 、13(命中) 、12(命中) 、 0(容量缺失) 、1(命中) 、2(命中) 、3(命中) 。 0 - 1 2 - 3 4 - 5 6 - 7 8 - 9 10-11 12-13 14-15 16-17 24-25 32-33 40-41 48-49 56-57

18-19 26-27 34-35 42-43 50-51 58-59 20-21 28-29 36-37 44-45 52-53 60-61 22-23 30-31 38-39 46-47 54-55 62-63

b)0(强制缺失) 、1(命中) 、2(强制缺失) 、3(命中) 、4(强制缺失) 、15(强 制缺失) 、14(命中) 、13(强制缺失) 、12(命中) 、11(强制缺失) 、10(命中) 、 9(强制缺失) 、0(冲突失效) 、1(命中) 、2(冲突失效) 、3(命中) 、4(冲突 失效) 、56(强制失效) 、28(强制失效) 、32(强制失效) 、15(命中) 、14(命 中) 、13(冲突失效) 、12(命中) 、0(冲突失效) 、1(命中) 、2(命中) 、3(命 中)

58. Cache 存储层次中多层 Cache 之间通??梢圆捎冒剑↖nclusion)或者非 包含式(Exclusion)关系,例如 AMD 的 Opteron 的 L1 和 L2 之间采用的非包 含式关系,而 Intel 的 Core 架构的 L1 和 L2 之间采用包含式关系,请比较包含 式 Cache 和非包含式的 Cache 的特点,包括从存储访问路径、硬件实现复杂性、 数据和消息通信量、多核之间一致性的维护等各个角度进行分析。 假定只有 L1 cache 和 L2 cache,两层 cache 层次。 包含式关系(inclusive) ,上层 cache 的数据包含在下一层 cache 中。非包含 式关系(exclusive) ,上层 cache 的数据不包含在下层 cache 中。包含式 cache 层 次关系,可以简化 cache 层次的设计,但是一份数据存在多份拷贝,这样导致片 上 cache 的利用率降低。非包含式 cache 层次关系,cache 行只能存在一份拷贝, 或者在 L1 cache 中或者在 L2 cache 中,可以最大化片上 cache 的利用率。 存储访问路径。包含式 cache,L1 cache 如果没有命中,需要访问 L2 cache, 如果 L2 cache 命中,cache 行送入到 L1 cache。非包含式 cache,如果 L1 cache 没有命中,则访问 L2 cache,如果 L2 cache 命中,cache 行需要送入到 L1 cache, 同时需要无效掉 L2 cache 中的拷贝。如果 L1 cache 和 L2 cache 都不命中,则从 内存直接送到 L1 cache,被替换的 cache 块放置到 L2 cache,因此 L2 cache 相当
50

于 L1 cache 的 victim cache。 对于多处理器或者多核设计。包含式 cache 简化了多处理器中 cache 一致性 问题,如果一个处理器 P1 需要写,则需要无效掉其它处理器 cache 的拷贝,P2 处理器的 L2 cache 侦听到无效命令, 如果在该 L2 cache 中, 则直接无效掉该 cache 行,该 L2 cache 同时发送消息给 P2 的 L1 cache,无效掉 L1 cache 的 cache 行。 当采用非包含式 cache 结构, L1 cache 需要特定的侦听端口, 也就是 P2 的 L2 cache 和 L1 cache 需要同时侦听到 P1 发出的无效命令。这样会增加片上面积的开销以 及增加 cache 访问的延迟。

59. Cache 主要是利用程序中的局部性原理,局部性主要包括时间局部性和空间 局部性两类。描述一个真实的应用程序,其数据访问层现出下列某一种模式,如 果下列模式不可能存在,请阐述理由。 a) 几乎没有空间局部性和时间局部性。 b) 较好的空间局部性,几乎没有时间局部性。 c) 较好的时间局部性,很少的空间局部性。 d) 较好的空间和时间局部性。 空间局部性,一个数据访问之后,邻近数据在一段时间被访问。时间局部性,一 个数据在一段时间内被多次访问。 1)几乎没有空间局部性和时间局部性。mcf in SPEC int2000. linked data structure accesses.

51

2)较好的空间局部性,几乎没有时间局部性。 数组的访问。 for(i=0; i<N; i+=4) { sum[i] = a[i] + b[i]; sum[i+1] = a[i+1] + b[i+1]; sum[i+2] = a[i+2] + b[i+2]; sum[i+3] = a[i+3] + b[i+3]; } 3)较好的时间局部性,很少的空间局部性。 stride 数组的访问。 for(i=0; i<N; i+=4) { sum = a[i] + sum; sum = a[i+10] + sum; sum = a[i+20] + sum; sum = a[i+30] + sum; } 4)较好的空间和时间局部性。
52

60. 试列举 5 种降低 Cache 缺失代价的技术, 说明降低原因; 列举 5 种降低 Cache 缺失率的技术,并说明降低原因。 CA. 3rd. Pape 449, Figure5.26

53

61. 回答以下关于 Cache 的问题: a) 块的放置:在 Cache 中,根据不同的策略一个块能被放置在哪里? b) 块的标志:如果一个块在 Cache 中,如何找到它? c) 块的替换:如果没有命中,哪个块该被替换,列举三种策略? d) 写策略:通常有哪两种基本策略来写 Cache,写缺失时又有哪两种基本策 略? answer:1)块的放置,通常有三种方式,直接相联、组相联和全相联。2) 通常通过 index 来查找 cache 中的块, 例如组相联方式中, 需要比较 cache 的 Tag。 3)cache 行的替换方式,如 LRU,Random,FIFO 等各种方式。4)cache 行的写 策略通常包括写回式和写穿透两种方式, 在写失效的时候有两种分配方式, write allocate 和 no-write allocate 两种。
54

62. 在一个单处理器系统中, 可能存在同一个内存地址的数据存在多个备份引起 的数据一致性问题。请分别说明写缓存(Write Buffer)和数据 Cache 之间一致 性的问题,以及数据 Cache 和内存的数据之间一致性的问题,并给出常见的软 硬件解决方法。 1)数据 cache(两种方式,写回式或者写穿透)和内存之间,通常使用 MSI/MESI 协议来保证一致性。例如写回式数据 cache,写操作,cache 行被置为 Modified,只有该 cache 行被替换时才被写入到内存。 2)当使用 Write Buffer 时,必须保证 Write Buffer 和数据 cache 之间的一致 性,通常 Write Buffer 在数据 cache 的下一层。但是,在 load 和 store 操作的时候 需要同时访问 Write Buffer 和数据 cache,因为在 Write Buffer 和数据 cache 中只 能保存一份拷贝。 3)当采用虚地址 cache,当使用虚地址 index 和虚地址 Tag 时,需要考虑别 名问题。这样采用软件管理 TLB 方式的方式来消除别名问题。 4)I/O 操作尤其是 DMA 传输方式需要考虑数据一致性问题,DMA 和 CPU 相当于多处理器情况下的两个 P。通常采用 uncache 的方式,或者 flush cache 的 方式来维护数据一致性。

63. 请编写两个 1024*1024 大小的矩阵(矩阵元素为 double 类型)相乘的程序。 要求采用分块相乘的技术以提高效率,并分析分块方式和 Cache 容量之间的关 系。 解:程序如下: // 由于参数发生了修改,请修正答案。 #include <iostream.h> #include <time.h> const int block_size=16; //控制矩阵相乘的块的大小 const int array_size=1024; const int subArray_size=(int)array_size/block_size; //求得子数组在每行/列的个数; int temp_array[block_size][block_size];
55

int array1[array_size][array_size]; int array2[array_size][array_size]; int result[array_size][array_size]; void temp_mul(int x1,int y1,int x2,int y2)//结果放到 temp_array[][]中; { for(int i=0;i<block_size;i++) for(int j=0;j<block_size;j++) { for(int k=0;k<block_size;k++) { temp_array[i][j] += array1[x1+i][y1+k] * array2[x2+k][y2+j]; } } } void matrix_mul() { /*分块相乘 for(int i=0; i<subArray_size; i++) for(int j=0; j<subArray_size; j++) { for(int k=0; k<subArray_size; k++) { temp_mul(i*block_size,k*block_size,k*block_size,j*block_size); for(int l=0;l<block_size;l++) for(int m=0;m<block_size;m++) { result[i*block_size+l][j*block_size+m] += temp_array[l][m]; temp_array[l][m]=0; int temp;
56

} } }*/ /*

for(int i0=0; i0<array_size; i0++) //完成 array2 的转置 for(int j0=0; j0<i0; j0++) { temp=array2[i0][j0]; array2[i0][j0]=array2[j0][i0]; array2[j0][i0]=temp; }

for(int i1=0; i1<array_size; i1++) //按行相乘 for(int j1=0; j1<array_size; j1++) { for(int k1=0;k1<array_size; k1++) { result[i1][j1]+=array1[i1][k1]*array2[j1][k1]; } } } */ int temp1; for(int i2=0; i2<array_size; i2++) //完成 array1 的转置 for(int j2=0; j2<i2; j2++) { temp1=array1[i2][j2]; array1[i2][j2]=array1[j2][i2]; array1[j2][i2]=temp1; }

for(int i3=0; i3<array_size; i3++) //按列相乘 for(int j3=0; j3<array_size; j3++) { for(int k2=0;k2<array_size; k2++) { result[i3][j3]+=array1[k2][i3]*array2[k2][j3]; }} } int main(int argc, char* argv[]) { for(int x=0;x<array_size;x++)

57

for(int y=0;y<array_size;y++) { array1[x][y]=1; array2[x][y]=2; result[x][y]=0; array1[0][0]=2; array1[0][1]=4; array1[1][0]=6; array1[1][1]=8; array2[0][0]=3; array2[0][1]=3; array2[1][0]=9; array2[1][1]=27; clock_t start, finish; double duration; start=clock(); matrix_mul(); finish=clock(); duration=(double)(finish-start)/CLOCKS_PER_SEC; cout<<"duration= "<<duration<<endl; cout<<result[4][6]<<endl;//用于验证矩阵计算程序的正确性; cout<<result[7][3]<<endl; cout<<result[5][1]<<endl; cout<<result[2][0]<<endl; } }

运行上面的程序,可以通过其中的 result 矩阵的几个元素 result[4][6]=4096; Result[7][3]=4096; result[5][1]=4122; result[2][0]=4104;从而可以验证了对于 分块相乘,按行相乘,按列相乘的程序代码的正确性。 以上代码运行在:Intel (R)Pentium (R)4, 1400MHZ

58

L1-D cache 64 KB L2-cache 128KB 运行时间是: 按行相乘是:155.77 S 按列相乘是:1183.05 S

分块大小 2 4 8 16 32 64

运行时间(S) 769.77 418.79 252.2 200.77 206.69 918.68

可见:按行相乘的性能最好;按列相乘的性能最差;按块相乘,当块大小是 16 的时候性能最好,而无论块更大还是更小,性能都会差一些。

原因分析: 按行相乘时候,无论对于 array1 还是 array2, miss 一次而从内存中取到 cache 中的数据都会被用到,所以 cache 的使用率最好。 而对于 array2 求转置仅 仅每个元素使用一次, 相对于 2048 的矩阵相乘带来的好处而言, 转置引起的 miss 非常值得。从而总体的 miss 次数最少,从而运行时间最少。 而按列相乘恰好相反,首先对 array1 求转置就需要一定的 miss 开销,同时 转置对于矩阵相乘而言并没有带来任何的好处,它造成了 array1 和 array2 一样, 每次随 miss 元素而取出的元素都没有被用到, 所以造成了 cache 的使用效率是最 低的。从而它总体的 miss 次数最多,这样运行时间也最长。 对于按块相乘而言,当块大小是 16 的时候,子矩阵一行的大小是: 16*4B=64B 恰好是我的机器的 L1 data cache 的块大小,因为 miss 一次所取到 cache 的数据全部立即被用到,因而这时候矩阵相乘 cache 的使用效率是最高的,

59

miss 的次数也是最少的,所以此时运行时间相对于块更大或更小而言是最少的; 但是对于块更小而言,一次取来的数据当时不会立即用到,从而之后再用到的时 候可能已经被剔除了 cache;而当块更大的时候,一次每计算一行都需要造成多 次 cache 的 miss,这样,由于 cache 总大小有限,就会造成计算结果在 cache 和 内存间的频频移动, 所以 miss 次数也是很大的, 而且随着子矩阵的变大, 而 miss 次数也会变大,从而导致了 cache 块更大或更小运行时间都会明显增加。

60

第十讲 存储管理

64. 在如下一段 C 语言程序的 for 循环中, void cycle(double* a) { int i; double b[65536]; for(i=0; i<3; i++) { memcpy(a, b, sizeof(b)); } } a) 程序memcpy函数执行过程中可能发生哪些例外,各多少次; 答: 忽略外部中断(包括键盘,鼠标等输入),内部程序执行例外可能有: ① TLB例外(TLB Miss Exception) ② 缺页异常(Page Fault Exception) ③ 系统调用例外 TLB例外和页大小有关,还和TLB表项以及替换算法有关(分表假设为4K、128项和最近未使 用LUR,不考虑ITLB miss例外),则:65536*8*2 =512*2=256*4k,也就是256次例外 缺页异常具体次数和页大小有关,假设页大小为4K(假设页分配后不会被替换出去,且忽略 临时变量i,以及指令代码段发生的缺页例外,假设内存足够大,页加载入主存后不会被替 换):正常情况下a不会缺页,b缺页可以有128次 Memcpy会引发一次系统调用。 b) 上述循环中,第一遍用了0.5秒,第二遍用了0.35秒,第三遍用了0.36秒,请解释原因。 答: 相对于第二三遍,第一遍可能发生了 cache 冷失效,缺页例外,TLB 例外,转移猜测训练, 第二三遍没有(第二三遍的差别可以认为来了一些外部中断导致,如键盘输入,鼠标点击) 。

65. 请阐述使用虚地址索引 Cache 的优点及不足? 答: 优点:虚地址索引 cache 可以避免地址转换延时问题:

61

引入的不足(问题) : ① 区分进程问题:不同进程的虚地址空间是一样的,需要在进程切换时候刷 Cache 以维护 一致性,增加了冷失效。 该问题可以通过在 TLB 中增加进程号的方式来解决:多进程切换时刷 Cache;多进程用 ID 号来区分虚地址。但前者还是会增加冷失效。 ② 别名(aliases)问题:操作系统有时候(如为了进程间共享)需要不同的虚地址对应 同一物理地址 aliases 别名。该问题随着 cache 块的增大愈显突出。 该问题可以通过 虚 Index 实 Tag 技术 (Virtually indexed, physically tagged , VIPT) 解决。即在用 Index 从 cache 中读 Tag 的同时,进行虚实地址转换,可以使用物理地址 做 tag 比较(但比较需要物理地址算出后才能比较,会增加延时) ;为了保证虚实地址 index 的一致性,当页大小小于 cache 块大小时,需要采用页着色技术。

66. 对于指令 Cache 是否有必要考虑 Cache 别名问题? 答: 有必要,可能会由于 cache 别名导致取错指令。

67. 假定在某一个 CPU 的 Cache 中需要 64 位虚拟地址,8 位的进程标识,而其支持的物理 内存最多有 64GB。请问,使用虚拟地址索引比使用物理地址作为索引的 Tag 大多少?这个 值是否随着 Cache 块大小的变化而发生改变? 答: 由于虚拟地址有 64 位,进程标识为 8 位;而物理地址是 64GB,即需要 36 位物理地址。这
62

样,使用虚拟地址比使用物理地址总共增加的位数为 8+(64-36)=8+28=36 位; 而保持页大小不变化,改变块的大小,增加的位数保持不变。 68. 考虑一个包含 TLB 的当代处理器。 (1)请阐述 TLB、TLB 失效例外、页表和 Page fault 之间的关系。 (2)如果有这样一个机器设计:对于同样的虚拟地址,TLB 命中和 Page fault 同时发生,这样的设计合理么?为什么?(3)现代计算机页表普遍采用层次化的方式,请 解释原因。 答: 1) TLB:Translation lookaside buffer,即旁路转换缓冲,或称为页表缓冲;里面存放的是 一些页表文件(虚拟地址到物理地址的转换表) 。TLB 是页表的一个子集。 TLB 失效例外:假如某个虚地址 VA,在 TLB 中没有找到对应的页表项,则发生 TLB 失效 例外(TLB miss exception)。 页表: 简单的说, 页表是内存块的目录文件, 作用是实现从页号到物理块号的地址映射。 用固定大小的页(Page)来描述逻辑地址空间,用相同大小的页框(Frame)来描述物理内 存空间, 从逻辑页到物理页框的页面映射, 这些页面映射就是一张张页表 (Page Table) . Page Fault:缺页,就是 TLB 中没有虚地址 VA 对应的页表,主存中也没有 VA 对应的物 理地址。这时候发生 Page Fault Exception(缺页例外) ,需要交给操作系统处理,通 常需要消耗很多的时间来处理该例外。 2) 不合理,因为 Page Fault 发生时意味着主存中没有虚地址 VA 对应的页表,这是 TLB 中也应该没有,因为 TLB 里的页表都是主存中换进去的,是主存中页表的子集,应该发 生 TLB miss。倘若没有发生,说明 TLB 不是主存页表的子集,这会导致存储不一致, 也违背了层次化设计的基本要求。 3) 多级页表可以减少页表所占用的存储空间。比如: 一个 32 位逻辑地址空间的计算机系统,页大小为 4KB,那么页表有一百万条目。假设 每个条目占 4B,则需要 4MB 物理地址空间来存储页表本身。 一个虚地址(32 位系统,页大小 4K) 可以被分为 :一个 20 位的页号 +一个 12 位的偏 移。如果对页表进行再分页,那么页号分解为:一个 10 位的页号 +一个 10 位的偏移。 因此,一个逻辑地址表示如下 :p1 是用来访问外部页表的索引, p2 是外部页表的页偏 移。

63

第十一讲 多处理器

69. 对于一个有 p 个处理器的共享存储系统。 a) 请写出一段程序,用 load/store 指令、运算指令和转移指令实现一个自旋锁。 b) 请写出一段程序,用 load/store 指令、运算指令和转移指令实现一个公平的自旋锁。 c) 用 load/store 指令、运算指令和转移指令实现一个公平的自旋锁,最少需要访问多少 个内存地址? 答:a)和 b)请参见 bakery 算法。c)答案是 p。假设只需要 i 个地址,存在某个时刻,p 个 进程都要向这 i 个地址写以表明自己想获得锁。如果 i<p,必然有某个进程 pj 希望获得锁的 意图会被其它进程的写覆盖掉,从而其它进程不知道 pj 希望获得锁。这样就会产生不公平。

70. 请查阅硬件同步原语相关的文献。 a) 请列出 2 种硬件同步原语,并给出它们在哪些处理器上实现。 b) 分析各种同步原语的优劣。 c) 用各种同步原语实现一个公平的自旋锁。 d) 用各种同步原语实现公平的自旋锁,分别最少需要访问多少个内存地址? 答:compare&set 和 ll/sc 是最常见的同步原语。Ll/sc 需要 n 个地址才能实现公平。 Compare&set 只需要两个地址。最主要的是保证每个进程希望获得锁的信息不会被覆盖掉。 Compare&set 可以保证,而 ll/sc 可能会失败。

71. 加速比的定义是:使用增强措施时完成整个任务的性能/不使用增强措施时完成整个任

64

务的性能。 a) 请给出一个例子,使用多线程能获得超线性加速比(即采用多个线程相比单个线程运行 时间减少的倍数超过了线程数) 。 b) 上述例子是否违背了 Amdahl 定律。 答:n 个共享存储处理器,每个有 m 内存。进行 O(nm)个变量排序就可能出现超线性加速比。 一些随机算法也可能出现。 很多搜索算法也会有超线性加速比, 例如通过剪枝使得总的被搜 索数据量少于顺序搜索的情况,此时并行执行将完成较少的工作。 Amdahl: 使用某种较快执行方式获得的性能提高, 受可受这种较快执行方式的时间所占比例 的限制。 无矛盾。

72. 在共享存储多处理器系统中假共享会带来不可忽视的性能损失, 为了尽量减少假共享的 发生,程序员在写程序时应注意些什么? 答:一个 cache 行(如果共享粒度是行的话) ,避免出现同时被多个处理器同时写。

73. 在基于目录的 Cache 一致性系统中,目录记载了 P1 处理器已经有数据块 A 的备份。 a) 哪些情况下目录会在此时又收到了一个 P1 对 A 块访问的请求。 b) 如何正确处理上述情况? 答:可能 P1 已经把 A 替换出去了,而替换请求还没有送到目录,此时 P1 又希望访问 A,因 此向目录发出了 miss 请求。 如果网络不能保证 P1 发出的替换 A 消息和访问 A 消息达到目录 的顺序,就会出现上述情况。解决方法可以是让网络保证点到点消息的顺序。也可以是目录 发现不一致后等待收到了 P1 的替换 A 消息才返回 P1 对 A 的 miss 请求。

74. 假设在一个双 CPU 多处理器系统中, 两个 CPU 用单总线连接, 并且采用监听一致性协议 (MSI) , Cache 的初始状态均为无效, 然后两个 CPU 对内存中同一数据块进行如下操作: CPU A 读、CPU A 写、CPU B 写,写出每次访问后两个 CPU 各自的 Cache 的状态变化。 答: A(I)B(I)->A(S)B(I)->A(M)B(I)->A(I)B(M)

75. 在下面程序段中,A、B、C、D 为进程 P1、P2、P3 的共享变量,且初始值均为 0。该程 序的正确运行解结果是 D=2000。 (1)在一个用可伸缩网络连接、采用基于目录的 Cache 一 致性协议的分布式共享存储系统中运行上述程序得到结果是 D=0,请解释产生上述结果的原 因。 (2)在实现顺序一致性的分布式共享存储系统中,对上述程序施加什么限制可以保证执 行结果的正确性。 (3)在实现弱一致性的分布式存储系统中,采用 barrier 进行同步,请问
65

上述程序如何插入 barrier 操作才能保证执行的正确性? P1 A=2000 B=1 P2 while (B!=1) {;} C=1; D=A P3 while (C!=1) {;}

答:a)P1 对 A 的写被网络阻塞,一直没有传播到 P2 和 P3。b)什么都不用做。c) P1 P2 barrier1 P3 barrier1 barrier2 A=2000 B=1 barrier1 barrier2 while (B!=1) {;} C=1; barrier2 while (C!=1) {;} D=A

76. 有以下 2 个并行执行的进程, 在顺序一致性和弱一致性下, 它各有几种正确的执行顺序, 给出执行次序和最后的正确结果(假设 a 和 b 的初始值为 0) 。 P1 a=1; print b; P2 b=1; print a;

答: 顺序一致性: a=1,b=0;a=0,b=1;a=1,b=1。 弱一致性: a=1,b=0;a=0,b=1;a=1,b=1;a=0,b=0。

77. 用 pthread 库或者 MPI 库在一个多处理器系统上写一个多线程的 1024*1024 矩阵乘法, 并和单线程的矩阵乘法进行性能比较。

66





教学相长。给学生上课,我自己也学到很多东西。每当学生在课间和课后问 我这样那样的问题,经常促使我进行新的思考并有所心得。同时,在整理课件或 讲义的过程中,使我能够从宏观的角度思考计算机系统结构学科的发展,从历史 的角度观察计算机体系结构几十年发展的沉淀, 并从学科的角度对自己的研究进 行深化和系统化。 计算机系统结构是一门实践性很强的学科, 我们研究的问题应该与实践紧密 结合,而不仅仅是跟踪别人从他们的实践中提出的问题。同时,计算机系统结构 研究需要大的研究平台,不同的人在同一个平台上工作可以形成合力,长时间在 同一平台上工作可以形成积累。如果没有结合实践的研究平台,不知道实践的需 求,我们的研究只能基于别人提出的问题,利用别人的技术平台进行增量式的改 进性研究。别人从实践到认识、再从提高了的认识回到实践的时候,我们只能从 别人的认识到我们的认识,却没有机会回到自己的实践中去。在从“从实践到认 识,再从认识到实践”的螺旋上升过程中,每次只能跟着转半圈,不能形成螺旋 式的上升,科研水平就不能螺旋地提高。 计算机系统结构的研究需要在跟实践紧密结合的基础上通过总结归纳以及 思考不断提出新的科学问题。 在花费大量时间和精力做具体繁琐的工程实践及实 验的同时还需要退一步思考的智慧和勇气。例如,进入本世纪以来,低功耗的成 为研究的热点, 但所有的低功耗研究都是基于晶体管级的动态功耗和静态功耗模 型进行结构改进,对结构级或算法级的功耗模型却少有人考虑,或许对一个算法 来说,就像算法的计算复杂度一样,需要一个能量复杂度模型,矩阵乘法的能量 复杂度是什么?排序算法的能量复杂度是什么?有没有可能通过算法优化降低 能量复杂度?又如, 一个算法只有算法的计算复杂度公式, 而在冯诺依曼结构中, 多数程序的主要执行时间不是花在运算部件进行运算过程中, 而是花在从内存到 运算部件的数据搬运以及程序控制引起的转移控制过程中, 那么有没有一个模型 能够综合体现算法的运算、数据搬运以及控制复杂度呢?再退一步,现在计算机 学科的发展是基于人类从认识自然的过程中建立物理学, 从物理学的研究方法中 建立数学,数学经过简化成为离散数学,再归约为加减乘除等基本算子,然后构 造计算机进行加减乘除运算,可以看出现在的计算机学科是建立在十七、八世纪
67

人类认识自然的基础上的,现在人类对物理世界的认识大大提高了,为什么还要 用加减乘除这些老的基本运算解决新的物理问题呢?有没有可能从人类对物理 世界的新认识中(如基因学、智能科学)进行一次新的归约,产生加减乘除之外 的新的算子,构造出新的计算机,解决现在的计算机解决不了的问题呢? 在研究生院讲课,对我来说是很大的负担。尤其是龙芯的工作涉及到产学研 的方方面面,科研及事务性的工作很多,经常要出差。但每到上课的时间,不管 在什么地方都得赶回来出现在教室;不管正在处理多急的事,都得把脑子换过来 先把课上好。但我觉得别人很少有我这种能够从长期的实践中学习的机会,有责 任把自己实践的体验与更多的学生分享。希望能够坚持在研究生院讲满十年。

让思想在科学的天空自由翱翔,不亦说乎? 在实践中学习,做出对国家和人民有用的创新贡献,不亦乐乎? 择天下英才而教之,为国家培养有用的人才,不亦君子乎?

胡伟武 2010 年端午节

68



推荐相关:
曾道免费资料大全正版l | 曾道免费资料大全正版l
All rights reserved Powered by 曾道免费资料大全正版l www.140827.com
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com