计算机组成小记

困啊,困,困到眼皮咀嚼眼珠,下巴亲吻桌面,意识在困倦中被熬成一锅浓粥,试图清醒过来却拔出粘稠的丝。老师破碎的英语断断续续的传来,像深山中精怪的呼唤;屏幕上的 PPT 变幻扭曲出炫光的轮廓,透过公式和图像我恍惚看到了神谕。

COMP2120 Computer Organization 笔记。无聊的课程前轰然倒塌的我。


  This article is a self-administered course note.

  It will NOT cover any exam or assignment related content.


Digital Logic

Boolean Algebra. 该部分与 COMP2121 之前的命题逻辑部分高度重合。值得注意的是逻辑与 \(\land\) 常被表示为 \(\times\),逻辑或 \(\lor\) 被表示为 \(+\),否定 (NOT) \(\lnot A\) 被表示为取补 (complement) \(\overline{A}\)

Functionally complete sets. (三元) AND, OR, NOT. (二元) AND, NOT/OR, NOT. (一元) NAND/NOR.

Implementation of Boolean function. 将真值表转化为布尔表达式。常用 sum of products (SOP) 方法:

  • minterm: 一个包含所有变量的累乘 (AND) 项。
  • 对所有函数值 \(F=1\) 的 minterm,为 0 的变量取反,为 1 的变量不变,再求和得到布尔表达式。

S-R Latch. 有点像 flip flops,作为记忆单元。

Karnaugh Map. 卡诺图,用于化简复杂的布尔表达式。

  • 二元 \(2^1\times 2^1\),三元 \(2^1\times 2^2\),四元 \(2^2\times 2^2\)
  • 为保证变量的连续变化,表头采用格雷码 (Gray code) 排列。
  • 选出 (数量尽量少的) 若干个全 1 矩形。矩形大小必须是 \(2^n\),可以相互重叠或者 wrap around 图的边界。
  • 每个矩形对应一个 minterm,忽略 0 和 1 均取到的变量,其他的变量按照之前的规则取反/保留。


Number Representation

radix-\(10\) to radix-\(r\). 对于十进制数 \(A.B\),分别处理其 integer part 与 fractional part。

  • \(A\): 经典的 quotient remainder 方法。短除后得到的余数记得倒着写。
  • \(0.B\): 不断乘 \(r\),取整数部分直到 \(B=0\)

binary to hexadecimal. 从左到右,四个一组,二进制中的每四个数码对应十六进制中的一个数码。记住 \(A-F\) 对应 \(10-15\)

binary to octal. 从左到右,三个一组。

Excess \(K\) (aka Offset Binary, Biased Representation). 加 \(K\)​ 后再求 bit pattern 表示。

Sign-Magnitude Representation. 难以计算,\(0\) 有两种表示。

One's Complement.

  • 正数:同 unsigned bit pattern。
  • 负数:将 unsigned bit pattern 取反。本质上 \(-x\)\(2^n-1-x\)​ 表示。
  • 仍然存在 \(+0\)\(-0\) 表示,加法实现还是不够直接。

Two's Complement.

  • 正数:同 unsigned bit pattern。
  • 负数:将 unsigned bit pattern 取反后加一。本质上 \(-x\)\(2^n-x\)​ 表示。
  • \(0\) 的表示唯一。由于 \(10...0_n\) 的意义空缺,将其分配给 \(-2^{n-1}\)。因此 2's Complement 的表示范围比之前的两种方法多 \(1\)\([-2^{n-1}, 2^{n-1}-1]\)。加法计算简洁。
  • Range Extension:使用 sign bit 进行填充。

Floating-Point Representation (Chapter 4.2). 与定点数表示 (Fixed-Point Representation) 相对。定点数表示规定了小数点前后 (整数部分与小数部分) 占据的位数,因此无法较精确的表示 large numbers 或 small fractions。浮点数表示则没有这样的限制。

浮点数表示本质上是二进制下的科学记数法。以 32 位为例,一个浮点数表示分为三部分:

  • Sign of Significand (1 bit) \(S\):符号位。
  • Biased Exponent (8 bits) \(E\):幂数位,通常采用 excess-127 表示。
  • Significand (23 bits) \(M\):又称 mantissa,有效数字位。类似科学记数法,有效数字被 normalize 为 \(1.\text{xx...x}\)。由于 \(1\)​​ 总是出现在首位,它将会被省略。

浮点数表示的实值 (actual value) 计算。

  • 一般来说,实值的计算符合公式 \((-1)^S\times 1.M \times 2^{E-127}\)
  • IEEE 标准下的特殊值 (special values):exponent 为全 \(0\) 或全 \(1\)
    • subnormal values:被 exponent 全 \(0\) 标记,公式变为 \((-1)^S\times 0.M\times 2^{-126}\)
    • infinity and Not-a-Number (NaN):被 exponent 全 \(1\) 标记。若 \(M\) 为全 \(0\),表示 \((-1)^S \infty\);若 \(M\) 非全 \(0\),表示 Not-a-Number。
  • 由此可见,有效的 exponent range 在 \([1,254]\) 间。这代表 normal values 的幂数范围在 \([-126,127]\)​ 间。

浮点数表示中精确度 (precision) 与表示范围 (range) 的 tradeoff。精确度与 significand 的位数正相关,范围与 exponent 的位数正相关。


Number Arithmetic

虽然很佩服研究出这些繁琐规则的人,但对这一部分是真的感不起兴趣。

[具体参见 Tutorial-2 slides 与 Chapter 4.3-Number Representation and Arithmetic Part III]

Addition/Subtraction. (1-4 tutorial, 5 lecture)

  • Excess-\(b\)​ Representation.
  • 2's Complement Addition/Subtraction. add bit patterns directly and ignore the carry out.
  • 1's Complement Addition/Subtraction. \(\text{a+b carry out ? (ignore carryout) add 1 back : do nothing}\)​.
  • 2's Complement Range Extension. Fill with copies of the sign bit.
  • Floating-point Addition/Subtraction.
    • align the significands to make two exponents equal (larger one)
    • add/sub on the significand and determine the sign of result
    • normalize (truncate) and rounding

Multiplication/Division. (lecture)

  • 2's Complement Multiplication. 规则很复杂,总的来说是被乘数进行 sign extension,按照乘数的符号位分类讨论,列出竖式进行计算。[见 Chapter 4.3 p.3 multiplication in 2's complement]
  • Floating-point Multiplication/Division.
    • Exponent 部分回到 Excess-\(b\) 表示的加减法。
    • Significand 部分相乘/相除并确定符号。
    • normalize 然后 rounding。


Instruction Execution Cycle

详见 From NAND to Tetris 课程笔记,内容基本重合。

与 Hack computer 的不同之处见 assignment 中提供的 sim.py 和作业描述中的示意图。CPU 中有:

  • PC (program counter)。在 byte addressing 模式下每轮隐式的 \(+4\)
  • Register File。由少量快速寄存器组成,储存 CPU 经常访问的数据。RFIN 写入,RFOUT1RFOUT2 输出。
  • MAR (memory address register),存储地址。
  • MBR (memory buffer register),存储从 memory 中提取的数据。常用 MBR <- Mem[MAR] (operand fetch)。
  • IR (instruction register),存储 PC 指向的具体指令内容。常用 IR <- Mem[PC//4] (instruction fetch)。
  • 以上的寄存器被若干 data bus 连接起来。

关于指令也有少许不同之处;细节还是参考 sim.py

  • 1-word instruction. ADD, SUB, OR, AND 等指令均在 1 word (4 bytes) 中指定了两个源地址与一个目标地址。
  • 2-words instruction. LD (load), ST (store) 均是 2-words 指令。第一个 word 指定了 operation code,CPU 地址 (寄存器地址,在 LD 中为目标,在 ST 中为源) 与 addressing mode (总是 0xFF)。第二个 word 指定了需交互的 memory 的地址。
  • 2-word instruction. BR (unconditional), BZ (zero flag is true), BNZ (zero flag is not true) 这些 branch 指令也是 2-words 指令。 第一个 word 指定了 operation code,condition code 与 addressing mode (总是 0xFF)。第二个 word 指定了 jump 的目标地址。


Memory Hierarchy

memory 一直是性能瓶颈的主要来源。memory hierarchy 在成本与性能间找到了一个平衡点。从金字塔的顶端到底端,memory 的成本越来越低,容量越来越大;同时所需的 access time 增加,被 CPU (直接) 访问的频率越来越低。

  • registers of the CPU.
  • on-chip cache memory [inside CPU chip].
  • cache memory [on the motherboard].
  • main memory [on the motherboard].
  • external memory [secondary memory].

对需要频繁访问的数据,例如 temporal locality 与 spatial locality;将它们从 lower level 复制到 higher level 中。

关于 memory byte ordering - 对于 multi-byte data 有两种存储顺序:Big Endian Mode 与 Little Endian Mode。

关于 memory 的种类。

Semiconductor Memory Type

memory 的性能 (performance) 评估。access time,memory cycle time 与 transfer rate [见 Chapter 6 Memory Hierarchy pp.21-22]

传输时的 error detection & correction。对 a block of data 添加一位 parity bit (校验码),标识数据中 \(1\) 的个数的奇偶性。correction 则需要更多 bits,如 Hamming code。


Cache Memory

其实并不是很绕的东西,看 PPT 硬是看了很久才搞清楚。笔记写了挺多,后来一看只觉杂乱无章。想了很久,发现通过伪代码描述 address mapping 是一个最佳的选择。

把 cache memory 与 main memory 想成两个数组 cachememorymemory 的空间远远大于 cache,因此可以当作哈希表来用;但代价是访问 memory 的速度极慢。为了最小化 CPU 访问数据的平均速度,把访问次数较多的数据存入 cache;具体存入 cache 的什么位置?这个问题就是 address mapping 所要解决的。

cachememory 储存的都是 data block,每个 block 中有 \(b\)​ 个 bytes (若 word-addressed 就是 words)。

single-level cache 的 principle 与 multi-level cache 是一致的。

Fully associative. 灵活,多对一,但效率低下。

1
2
3
4
5
6
7
8
9
10
11
def read(addr, cache):
# BLOCK_SIZE: the number of bytes within a block
# tag: aka block number
tag, offset = addr // BLOCK_SIZE, addr % BLOCK_SIZE
for cache_line in cache:
if cache_line.tag == tag:
return cache_line.data[offset] # search hit
data = memory[tag]
# write data in cache with some append/replace policy
write(data, cache, some_append_policy)
return data[offset]

Direct-Map Organization aka 1-way Set Associative.

  • 若 cache 大小为 \(m\)memory[0], memory[m], memory[2m]... 均对应 cache[0]
  • 大大提升了读取速度,但如果 CPU 同时需要 memory[0]memory[m],一对一就成了诅咒。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def read(addr, cache):
block_number, offset = addr // BLOCK_SIZE, addr % BLOCK_SIZE
# CACHE_SIZE: the number of cache lines in the cache, one block per line
tag, line_number = block_number // CACHE_SIZE, block_number % CACHE_SIZE
if line_number in cache: # memory[line_number] not empty
cache_line = cache[line_number]
if cache_line.tag == tag:
return cache_line.data[offset]
else:
data = memory[block_number]
write(data, tag, line_number, cache)
return data[offset]
else:
data = memory[block_number]
write(data, tag, line_number, cache)
return data[offset]

def write(data, tag, line_number, cache):
cache[line_number].tag, cache[line_number].data = tag, data

K-way Set Associative. 引入 cache sets 综合了前两种地址映射机制。体现了读取效率和灵活性的 tradeoff。核心关系 \(m=k\times v\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def read(addr, cache):
block_number, offset = addr // BLOCK_SIZE, addr % BLOCK_SIZE
# K-way: the number of cache lines in a cache set
# SET_SIZE: the number of sets, SET_SIZE = CACHE_SIZE / K
tag, set_number = block // SET_SIZE, block_number % SET_SIZE
if set_number in cache:
cache_set = cache[set_number]
for cache_line in cache_set:
if cache_line.tag == tag:
return cache_line.data[offset]
data = memory[block_number]
write(data, tag, set_number, cache, some_append_policy)
return data[offset]
else:
data = memory[block_number]
write(data, tag, set_number, cache, some_append_policy)
return data[offset]

常用的 replacement policy (direct map organization 的 set size 为 \(1\),不需要 replacement policy):FIFO (first-in-first-out),LRU (least recently used) 与 RR (random replacement)。

两种 write policy。

  • write through - cache 与 main memory 的写入是 consistent 的。问题:main memory 的写入较慢 (但指令的执行并不会被其阻塞),如果在写入完成之前,下一个指令要求访问该 memory slot,就会产生冲突。
  • write back - 仅仅在 cache 中的某个 memory block 被替换时更新 main memory。写入效率显著高于 write through。当存在 I/O operations 时,cache 与 main memory 的 inconsistency 会引发冲突。

从 direct-map organization,到 k-way associative,再到 fully associative,hit ratio (\(1-\)miss ratio) 越来越高,读写速率越来越慢。重要公式 \(\text{average access time }=\text{ hit time }+\text{ miss ratio }\times\text{ miss penalty }\)

  • hit time: 在该 cache layer,一次 search hit 所需的时间。
  • miss ratio: search miss 发生的概率。
  • miss penalty: 若该 cache layer 是 L1,miss penalty 是 L2 的 average access time。若该 cache layer 是 L3,miss penalty 是 main memory 的 average access time。[见 Chapter 7.2 p.8 multi-level caches]


External Storage

这一节主要讲外部存储器。

首先是一些名词。

  • Magnetic disks (磁盘)。储存数据。
    • Cylinder - Sector - Track 结构。
    • Sector: Gap - Sync - Address mark - Data - ECC (error correction code) 结构。
  • Disk access 评估的三个重要时间参数。Seek (读写头在 cylinder 间移动),Rotational delay (指定的 sector 移动到读写头处),Data transfer time [公式见 Chapter 8 External Storage pp.8]
  • HDD (Hard Disk Drive, 硬盘驱动器)。各种磁盘是 HDD 的媒介。

关于 RAID (Redundant Array of Independent/Inexpensive Disks, 独立磁盘冗余阵列),是一种多个磁盘的组织形式。关键概念:Data striping 把连续的数据分成小段分散在多个磁盘中以促进并行读/写。

课上共介绍了 6 个 standard RAID levels [Chapter 8 External Storage pp.11-23]:

  • RAID 0:应用 striping。I/O 效率高 (并行读写),无冗余。
  • RAID 1:多了一个镜像磁盘 (mirrored backup)。
  • RAID 2:采用 Hamming code 作为 ECC,冗余磁盘的数量是 \(\log\) 数据磁盘的数量。
  • RAID 3:使用额外的一个冗余磁盘储存其他所有数据磁盘的 parity bit。\(X_r=\oplus_{i}^n X_i\)
  • RAID 4:采用 block-level striping,这意味着每次读取的数据总是在一个磁盘内。(RAID 0-3 通常采用的是 byte-level 或 bit-level striping,读取一个 block 需要访问所有磁盘)
  • RAID 5:采用 block-level striping,且 parity strips 分散在所有磁盘中 (RAID 3-4 的 parity strips 统一存储在一个额外的冗余磁盘中)。
  • RAID 6:使用两个 parity stripes,应对两个 HDD failures。

关于 SSD (Solid State Disks/Drives, 固态硬盘/驱动器)。与 HDD 相比,I/O 效率,访问速率都高,耗能少,耐久高。


Input and Output

关于 I/O。

学到这里越来越发现计组知识本身不难,关键在于找到其中的逻辑联系。可惜的是,课件中所展现出来的逻辑非常的 unorganized (我本来想说课件简直是答辩,但其实它对于知识的描述和总结是很详实的,还是有其可取之处)。

开场陈述:I/O Modules 可视作是外部设备 (External Devices, aka Peripherals) 的接口;CPU (aka processor) 通过和 I/O Modules 交互对外部设备进行操纵。

CPU - I/O Modules interactions (direct)。

  • CPU 通过读写 I/O Modules 中的两种 registers 来完成交互。
    • The Control and Status Register CSR - 存储了外部设备的状态信息 (读),对外部设备的操作 (写),可分散在同一个 register 的多个 bits 中。
    • The Data Register - 存储了其他数据,例如向外部设备的输入等 (读/写)。使用了 Data Buffering 机制的 Data Register 常被称为 Buffer Register BR
  • I/O Modules 的种类。
    • Port-mapped I/O。I/O Modules 中的 registers (如 CSR, BR) 作为独立的 dedicated I/O ports 的一部分,CPU 需要通过特定的指令对它们进行访问。
    • Memory-mapped I/O。I/O Modules 中的 registers 是 memory map 的一部分,CPU 能通过普通的 memory read/write 指令直接访问。

CPU - External Devices interactions (indirect);有三种交互方式。

Programmed I/O。特征是 CPU 在空循环中等待 External Device 完成 I/O operations。以 read operation 为例:

  • CPU 向 I/O Modules 中的 CSR 发送一个 read 命令。
  • CPU 从 CSR 中获取外部设备的状态。
  • OK ? 从 BR 中读取数据 : 返回第二步继续循环。

Interrupt-Driven I/O。减轻 Programmed I/O 的 CPU 资源浪费。[见 Chapter 9 Input and Output pp.16-20] 这里只讲几个值得注意的细节。

  • CPU 收到 interrupt signal 后并不立即悬置程序,而是在当前指令执行完毕后再转向 interrupt attention。这是为了减少需要保存的 register 数量。
  • 需要保存到栈中的 registers:
    • Processor Status Word PSW, aka flag register,即前一个 ALU 的 result。当下一个指令是 branch 时将会用到这个值。
    • Program Counter PC
    • 所有在 interrupt routine 中被用到的 registers,在使用之前都将被 push 到栈中进行保存。
  • interrupt routine 的最后一个指令是 Return from Interrupt RETI,它将会恢复 PSW, PC 与所有备份在栈中的 registers (in a reverse order that they were saved)。

Direct Memory Access (DMA)。在 I/O Modules 中引入 Input-Output Processor (IOP)。它无需 CPU 的直接干预,能够直接访问 memory。需要解决的问题是 IOP 与 CPU 的冲突:例如,它们需要同时访问同一块 memory。

引入 Cycle Stealing (周期挪用) 机制。即 IOP 向 CPU 发送信号请求 CPU 将 memory bus 的占用解除;如果 CPU 接下来的 cycle 无需访问 memory,它将同意请求,IOP 则会取得 memory bus 的控制。IOP 每次请求通常只占用一个或几个 cycles。


Reference

  This article is a self-administered course note.

  References in the article are from corresponding course materials if not specified.

Course info: COMP2120, Prof. Zhao Qi

Course textbook: William Stallings, Computer Organization and Architecture (10th edition)

-----------------------------------そして、次の曲が始まるのです。-----------------------------------