2016 年冬《计算组成原理》期末试卷

考试日期为 2016 年 1 月 21 日，源文件名为 2015.pdf。扫描件上直接写有作答，我把题目放在外面，把能够可靠辨认的手写内容放入折叠区；手写答案只作原卷记录，不对其中可能存在的错误作改写。电路图改写为等价连接说明或状态集合，避免贴整页扫描件。

一、选择题（每题 1 分，共 10 分）

1. 多数函数

函数 $F=AB+BC+AC$ ，使 $F=1$ 的输入组合为（　）。

A. $ABC=000$

B. $ABC=010$

C. $ABC=101$

D. $ABC=100$

2. 竞争冒险

组合逻辑电路的竞争—冒险是由（　）引起的。

A. 电路不是最简

B. 构成电路的逻辑元件存在传输延迟

C. 电路有多个输出

D. 电路使用不同的门电路

3. 十二进制计数器

已知 $Q_3Q_2Q_1Q_0$ 是同步十二进制计数器的触发器输出。若以 $Q_3$ 作进位 C，则 C 的周期和正脉冲宽度为（　）。

A. 12 个 CP 脉冲，正脉冲宽度为 4 个 CP 周期

B. 10 个 CP 脉冲，正脉冲宽度为 4 个 CP 周期

C. 8 个 CP 脉冲，正脉冲宽度为 2 个 CP 周期

D. 6 个 CP 脉冲，正脉冲宽度为 2 个 CP 周期

4. 触发器电路

以下四个候选触发器电路中，哪个能实现

Q^{n+1}=\overline{Q^n}+\overline{A}Q^n

的功能？

原卷的 A、C 是带组合输入和反馈的 D 触发器电路，B、D 是带组合输入和反馈的 JK 触发器电路；四图均为下降沿触发。由于扫描电路线条无法在纯文本中无歧义复原，具体连线应以源卷第 2 页为准。

5. 2114 芯片扩展

用 2114（ $1024\times4$ 位）芯片组成 8 KB 内存储器，需要（　）片。

A. 2

B. 4

C. 8

D. 16

6. 存储容量

某存储器芯片有 16 条地址线、32 条数据线，其存储容量为（　）位。

A. $16\mathrm{K}\times5$

B. $64\mathrm{K}\times32$

C. $64\mathrm{K}\times5$

D. $32\mathrm{K}\times16$

7. 分支地址

下列代码存于内存中，起始地址为 0x00001230。寄存器 $s0 初值为 -1，分支指令执行完后 PC 为（　）。

0x1230 loop: addi $s0, $s0, 1
0x1234       bgez $s0, loop

A. 0x00001230

B. 0x00001234

C. 0x00001238

D. 0x00001232

8. Cache 的目的

在主存储器和 CPU 之间增加 Cache 的目的是（　）。

A. 扩大主存储器容量

B. 扩大 CPU 通用寄存器数量

C. 解决 CPU 与主存储器之间的速度匹配问题

D. 既扩大主存容量，又增加通用寄存器数量

9. MIPS 的 I/O 编址

MIPS CPU 的内存和 I/O 采用（　）。

A. 独立编址

B. 统一编址

C. 混合编址

D. 以上都不是

10. 系统总线

计算机中的系统总线是（　）。

A. CPU、主存、I/O 部件之间传递信息的总线

B. 计算机系统与打印机之间的总线

C. 连接 CPU 内部各组件的总线

D. 用于计算机系统之间或计算机系统与其他系统之间通信的总线

查看扫描卷手写选择

二、简答题（每题 5 分，共 20 分）

1. 逻辑函数化简

推导下式的最简与或式：

F=\overline{AB+BC}+A\overline{C}.

查看扫描卷手写作答

手写推导最终化为：

F=\overline{C}+\overline{B}.

2. 磁盘与 DMA

某机 CPU 主频为 1 GHz。磁盘有 8 个盘面、512 个柱面，每磁道 100 个扇区，每扇区 512 字节，转速为 12000 RPM。

计算磁盘总容量，单位为 Bytes。（1 分）
计算磁盘数据传输率，单位为 Bytes/s。（2 分）
若磁盘采用 DMA，每次 DMA 传送块大小为 ______ KB，DMA 预处理和后处理总开销为 300 个时钟周期，CPU 用于该磁盘 I/O 的时间占整个 CPU 时间的百分比是多少？假设 DMA 与 CPU 无访存冲突。（2 分）

查看扫描卷手写作答

手写计算为：
$8\times512\times100\times512=100\times2^{21}\ \mathrm{Bytes}.$
转速为 $12000/60=200$ 转/s，手写计算传输率为：
$200\times100\times512=10{,}240{,}000\ \mathrm{Bytes/s}.$
空格中手写填入 10 KB，最终写出的占比为 $0.10003\%$ 。

3. `jr` 与 `j`

指令 jr 和 j 有什么不同？哪一条指令可以跳转的范围更大？两者的跳转范围分别是多少？

查看扫描卷手写作答

手写答案称：jr 跳转到寄存器中保存地址对应的位置，j 跳转到立即数字段对应的 PC 地址；并判断 jr 的范围更大。手写范围为：

jr：00000000H—FFFFFFFFH
j：00000000H—0FFFFFFFH

4. 页表与 TLB

某页式虚拟存储系统按字节编址，逻辑地址 36 位，页大小 16 KB，物理地址 32 位。页表包含有效位和修改位各 1 位，且所有虚拟页都在使用。

每个进程的页表大小至少为多少 bits？（2 分）
若 TLB 共 512 项，以 4 路组相联 Cache 实现，则 TLB 大小至少为多少 bits？（3 分）

查看扫描卷手写作答

手写答案先求得虚页号 22 位、实页号 18 位，随后把一个表项写为 $18+22+1+1=42$ bits。

第 2 小题写出：TLB 有 $512/4=128$ 组，Tag 为 $22-7=15$ 位，每项按 $42+15=57$ bits 计算，因此总大小为：

57\times512=29184\ \mathrm{bits}.

三、组合逻辑（共 10 分）

一个四人表决电路由与非门构成，A、B、C、D 表示四个人， $L=1$ 表示决议通过。原图可等价描述为：

第一只与非门输入 C、D；
第二只与非门输入 B、C；
第三只与非门输入 A、B、D；
三只门的输出共同送入最后一只与非门，输出 L。

分析电路，写出 L 的表达式并化简，再写出真值表。（6 分）
指出四人中投票权值最大和最小的人，并说明原因。（4 分）

查看扫描卷手写作答

手写答案令：

\alpha=\overline{CD},\; \beta=\overline{BC},\; \gamma=\overline{ABD},

并得到：

L=\overline{\alpha\beta\gamma}=CD+BC+ABD.

手写真值表转录如下：

A	B	C	D	L
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	1
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0
1	1	0	1	1
1	1	1	0	1
1	1	1	1	1

手写统计认为 C 的投票权值最大，A 的投票权值最小。

四、时序逻辑（共 10 分）

设计一个二进制序列检测器。输入是无限二进制序列，检测到完整的“1001”时输出 1，否则输出 0。例如：

输入 1001010，输出 0001000；
输入 1001001，输出 0001001。

原图给出了 S_0/0、S_1/0、S_10/0、S_100/0、S_1001/1 五个状态，但要求考生补全转移条件和箭头。S_1001/1 表示在 S_1001 状态输出为 1。

补全状态转移条件和箭头。（6 分）
判断状态机类型并说明原因。（1 分）
以试卷给出的 Verilog HDL 框架为基础，补完整个设计。（3 分）

查看扫描卷手写作答

手写状态转移为：

状态	输入 0	输入 1
S_0	S_0	S_1
S_1	S_10	S_1
S_10	S_100	S_1
S_100	S_0	S_1001
S_1001	S_10	S_1

第 2 小题判断为 Moore 型，因为输出只与当前状态有关。

手写补全的核心代码转录如下：

case (state)
  S_0:    if (x == 0) state <= S_0;    else state <= S_1;
  S_1:    if (x == 0) state <= S_10;   else state <= S_1;
  S_10:   if (x == 0) state <= S_100;  else state <= S_1;
  S_100:  if (x == 0) state <= S_0;    else state <= S_1001;
  S_1001: if (x == 0) state <= S_10;   else state <= S_1;
endcase
result <= (S_1001 == state) ? 1'b1 : 1'b0;

五、主存储器（共 10 分）

采用 $1\mathrm{M}\times8$ 位 DRAM 芯片，构建按字节编址、容量为 $4\mathrm{M}\times32$ 位的存储器。

共需多少 DRAM 芯片？用于产生片选信号的地址有多少位？可采用哪种译码器？（3 分）
DRAM 芯片的刷新地址计数器是多少位？（2 分）
若采用分布式（异步）刷新，且存储单元最长刷新间隔为 8 ms，刷新周期是多少？（2 分）
若改用 $256\mathrm{K}\times8$ 位 SRAM 构建该存储器，并按字（32 位）访问，共需多少 SRAM 芯片？用于片选的地址有多少位？可采用哪种译码器？（3 分）

查看扫描卷手写作答

手写答案为 16 片；用高位地址 $A_{21}$ 、 $A_{20}$ 产生片选，可用 2—4 译码器。
芯片内 $2^{20}$ 个地址按二维均分为 $2^{10}$ 行，刷新地址计数器为 10 位。
手写计算为 $8\ \mathrm{ms}/2^{10}$ 。
手写答案为 64 片；芯片内地址占 18 位，片选使用 $A_{21}$ 到 $A_{18}$ ，可用 4—16 译码器。

六、Cache（共 10 分）

某机字长 32 位，主存 1 MB。Cache 为 4 路组相联，容量 16 KB，块大小 256 字节；每块有 1 位有效位，块内每个字有 1 位修改位。替换策略为 LRU，初始为空。程序依次按字访问：

A60F8H, B50F8H, C40D4H, D30C2H,
E20B0H, C40B0H, F10D4H, B50A8H

计算 Cache 组数、主存组数、每个主存组内的块数，并给出主存地址格式。（3 分）
Cache 的 Tag 有多少位？（2 分）
Cache 的实际总容量是多少？（2 分）
程序结束后，Cache 第 0 组中所有 Tag 是什么？命中率是多少？（3 分）

查看扫描卷手写作答

手写答案：Cache 共 $2^6$ 块、16 组；主存有 $2^{12}$ 块、16 组，每个主存组有 $2^8$ 块。地址格式写为 8 位组内块地址、4 位组号、8 位块内偏移。
Tag 为 8 位。
每行含 64 位修改位、1 位有效位、8 位 Tag 和 256 字节数据，手写计算总容量为 16.5 KB。
第 0 组的 Tag 写为 E2、F1、C4、B5；命中率为 $1/8=12.5\%$ 。

七、指令系统与汇编（共 15 分）

1. 用 MIPS 装入数值（6 分）

用一条指令把 0xB33C 存入 $t0。（2 分）
用不超过两条指令把 0xF78C033C 存入 $t0。（2 分）
用不超过两条指令，从地址 0xF78C000C 装入一个字到 $t0。（2 分）

查看扫描卷手写作答

# (1)
ori $t0, $0, 0xB33C

# (2)
lui $t0, 0xF78C
ori $t0, $t0, 0x033C

# (3)
lui $t0, 0xF78C
lw  $t0, 0x000C($t0)

2. 汇编翻译为 C（4 分）

寄存器 $s0 存变量 f，$s1 存变量 g，$s2 存数组 A 的基地址。把下面 MIPS 代码翻译为一行 C；若 g=8，A={1,2,3,4,5,6,7,8,9,10}，求 f。

lw   $s0, 8($s2)
add  $s0, $s0, $s1
addi $s0, $s0, 9
add  $s0, $s0, $s0

查看扫描卷手写作答

手写把各行解释为 f=A[2]、f=f+g、f=f+9、f=f+f，最终得到 f=52。

3. 跟踪循环（5 分）

$t0、$t1 初值分别为 0x00000002 和 0x00000005。执行后 $t0 是多少？写出简要过程。

LOOP: slt  $t2, $t0, $t1
      beq  $t2, $zero, ELSE
      addi $t0, $t0, 2
      j    LOOP
ELSE: addi $t0, $t0, 1
EXIT: addi $t0, $t0, 5

查看扫描卷手写作答

手写跟踪 $t0 为 2、4、6；比较 6 与 5 后转入 ELSE，再加 1、加 5，最终为 0x0000000C。

八、CPU（共 15 分）

给定指令序列：

lw  $5, -16($5)
sw  $5, -10($5)
add $5, $1, $5

五个阶段的延迟为：

IF	ID	EX	MEM	WB
300 ps	400 ps	350 ps	500 ps	100 ps

题目另给出的时钟周期为：

无转发	充分转发
200 ps	250 ps

根据阶段延迟，分别给出流水线处理器和单周期处理器的时钟周期。（4 分）
假设流水线没有转发，指出冒险并插入 nop 消除冒险。（4 分）
假设有充分转发，指出冒险并插入 nop 消除冒险。（3 分）
根据第二张表，分别计算无转发和充分转发时的总执行时间，并计算后者相对前者的加速比。（4 分）

查看扫描卷手写作答

流水线周期写为 500 ps；单周期周期写为 $300+400+350+500+100=1650$ ps。
手写答案在 lw 与 sw 之间插入两个 nop。
手写答案在 lw 与 sw 之间插入一个 nop。
手写计算无转发为 $8\times200=1600$ ps，充分转发为 $7\times250=1750$ ps，加速比为 $0.9143$ 。

A	B	C	D	L
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	1
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0
1	1	0	1	1
1	1	1	0	1
1	1	1	1	1

A	B	C	D	L
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	1
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0
1	1	0	1	1
1	1	1	0	1
1	1	1	1	1

2016 年冬《计算组成原理》期末试卷

一、选择题（每题 1 分，共 10 分）

1. 多数函数

2. 竞争冒险

3. 十二进制计数器

4. 触发器电路

5. 2114 芯片扩展

6. 存储容量

7. 分支地址

8. Cache 的目的

9. MIPS 的 I/O 编址

10. 系统总线

二、简答题（每题 5 分，共 20 分）

1. 逻辑函数化简

2. 磁盘与 DMA

3. jr 与 j

4. 页表与 TLB

三、组合逻辑（共 10 分）

四、时序逻辑（共 10 分）

五、主存储器（共 10 分）

六、Cache（共 10 分）

七、指令系统与汇编（共 15 分）

1. 用 MIPS 装入数值（6 分）

2. 汇编翻译为 C（4 分）

3. 跟踪循环（5 分）

八、CPU（共 15 分）

评论

3. `jr` 与 `j`

A	B	C	D	L
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	1
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0
1	1	0	1	1
1	1	1	0	1
1	1	1	1	1