System I: The Processor: Basic Principles¶

作者: Li Lu (Zhejiang University)

一、Overview（课程概览）¶

本课程探讨以下三个核心问题：

§ What is the architecture of computers? — 计算机的架构是什么？
§ What is the inside of processor (CPU)? — 处理器（CPU）内部有什么？
§ How to use CPU to solve problems? — 如何使用CPU解决问题？

二、What is the architecture of computers?（计算机的架构）¶

计算机系统的层次结构¶

计算机体系结构包含从底层到顶层的多个抽象层次：

problem → algorithm → program → runtime system (VM, OS, MM) → ISA (architecture) → microarchitecture → logic → circuits → electrons

special system: num-progeammable system
general system: programmable system

冯·诺依曼结构（Von Neumann Structure）¶

"Von Neumann structure: data and programs are in memory."
"CPU takes instructions and data from memory for operation and puts the results into memory."

- 冯·诺依曼结构的特点：数据和程序都存储在内存中

- CPU从内存中取出指令和数据执行操作，并将结果放回内存

三、What is the inside of Processor (CPU)?（处理器内部结构）¶

CPU的核心组成部分¶

Datapath（数据通路）: "performs operations on data" — 对数据执行操作
Control（控制单元）: "sequences datapath, memory, ..." — 对数据通路、内存等进行排序控制
Cache memory（缓存）: "Small fast SRAM memory for immediate access to data" — 小型快速SRAM存储器，用于立即访问数据

CPU的基本目的¶

generate digital system
programme solving

多核处理器示例¶

"AMD Barcelona: 4 processor cores" — AMD Barcelona拥有4个处理器核心

龙芯2号微架构（Microarchitecture of Godson-2）¶

龙芯2号处理器内部包含以下关键组件：

Reorder Queue（重排序队列）
Branch Bus / BRQ（分支总线/分支请求队列）
Fix RS（定点保留站）
BTB（分支目标缓冲器）
Register Mapper / Decoder（寄存器映射器/解码器）
PC + 16 / PC / IR（程序计数器/指令寄存器）
BHT（分支历史表）
ITLB（指令转换旁路缓冲器）
Float RS（浮点保留站）
ICACHE（指令缓存）
Processor Interface（处理器接口）
ALU1 / ALU2（算术逻辑单元）
General Register File（通用寄存器文件）
CACHE / TAG / CP0（缓存/标签/系统控制协处理器）
MEM / TLB（内存/转换旁路缓冲器）
Floating Point Register File（浮点寄存器文件）
FALU1 / FALU2（浮点算术逻辑单元）
Wtbk Queue（写回队列）

流水线技术（Pipelining）¶

"Datapath with Control — Single cycle instruction execution"

经典五级流水线：IF → ID → EX → MEM → WB

IF: 取指令（Instruction Fetch）
ID: 指令译码（Instruction Decode）
EX: 执行（Execute）
MEM: 内存访问（Memory Access）
WB: 写回（Write Back）

"Pipelining — Divide instruction execution into stages" — 流水线将指令执行划分为多个阶段

四、How to use CPU to solve problems?（如何使用CPU解决问题）¶

设计方法一：Common Digital System（通用数字系统）¶

Finite State Machine（FSM，有限状态机）¶

"Finite state machine（FSM）"

FSM由输入（Input）和输出（Output）组成。

示例：检测连续出现"1101"的次数

状态转换：A → B → C → D → E
X=1 → X=1 → X=0 → X=1

Infinite State Machine（无限状态机）¶

"Detection consecutive '0' number" — 检测连续0的个数

当需要检测的状态数量无法预先确定时，状态机变成无限状态：

A[1] → A[2] → A[3] → ... → A[n-1] → A[n]
"Impossible to implement" — 无法实现

设计方法二：Control of Register Transfers（寄存器传输控制）¶

"Register transfers performed on registers control that supervises the sequencing of the register transfers"

三个基本要素（Three essential elements）¶

Set of registers（寄存器集合）: "mostly in Datapath with some in Control Unit"
Basic operation (micromanipulation)（基本操作/微操作）: "Register transfers performed"
Control（控制）: "that supervises the sequencing of the register transfers"

Register Transfer Language（RTL，寄存器传输语言）¶

传输状态机处理：检测连续0的个数¶

Reset: L/S:Counter ≤ 0;

X=1: L/S:Counter <= Counter; Den : Disp <= Disp

Hardware Programmable: Detection consecutive "0/1" number¶

"问题改变，控制信号序列改变"

Reset: L/S:Counter ≤ 0; Den: Disp ≤ Counter

X=0/1: L/S:Counter <= Counter+1; Den: Disp<= Counter

X=1/0: L/S:Counter <= Counter; Den: Disp<= Disp

专用系统 vs 通用系统（Specific and general system）¶

Non-programmable System: Specific System（非可编程系统：专用系统）

"The control unit does not deal with fetching and executing instructions"
"But contains all of the information for sequencing register transfers based on inputs and on status bits from the datapath"

Programmable System: General system（可编程系统：通用系统）

"A portion of the input consists of a sequence of instructions called a program"
"Typically stored in a memory and addressed by a program counter"
"The Control Unit is responsible for fetching and executing these instructions"

设计方法三：Program State Machine（PSM，程序状态机）¶

"General system — Program state machine（PSM）"

Component	Description
Memory	—
Control Input	Control unit
Data Input	—
Control Output	—
Datapath	—
Control signals	—
Status signals	—
I/O	—

五、Is there a better way? — Universal Turing Machine thinking¶

Turing Machine（图灵机）¶

基本思想（Basic idea）¶

"Use machine to simulate mathematical computation process of humans by paper and pen"

两个简单操作：

§ Write or delete a symbol from the paper — 在纸上写入或删除符号
§ Move the attention from one position to another of the paper — 将注意力从纸的一个位置移动到另一个位置

下一个操作取决于：

(a) the symbol in one position of the paper that the person pays attention to
(b) the thinking state of the person currently

"Turing constructs a conceptual machine" — 图灵构建了一个概念机器

图灵机的组成部分（Components of Turing Machine）¶

An infinitely long paper tape TAPE（无限长的纸带）

- 纸带被分为多个连续的空白格，每个格子包含一个来自有限集合的符号

- 字母表包含一个特殊符号 □ 表示空白

- 纸带上的格子从左到右编号为0, 1, 2, …，右端可无限延伸

A read/write head HEAD（读写头）

- 可以在纸带上左右移动

- 可以读取当前格子的符号

- 能够修改当前格子的符号

A set of control rules TABLE（控制规则表）

- 根据机器当前状态和当前读写头下的符号决定读写头的下一步操作

- 修改状态寄存器的值，使机器进入新状态

A state register（状态寄存器）

- 用于保存图灵机的当前状态

Turing Model：Marvin • Minsky (1967)

图灵机的指令结构（Instruction structure）¶

典型七元组集合（Typical seven-tuples set）

M = {Q, Σ, Γ, δ, q₀, q_accept, q_reject}

其中 Q, Σ, Γ 均为有限集合：

Q — 状态集合（state set）
Σ — 输入字母表（input alphabet），不包含特殊空符号"□"
Γ — 字母表（alphabet），其中 b∈Γ 为空符号，且 Σ∈Γ
δ — 转移函数（transfer function）：Q × Σ → Q × Γ{L,R}，L和R分别表示读写头向左或向右移动
q₀∈Q — 初始状态（beginning state）
q_accept — 接受状态（accept state）
q_reject — 拒绝状态（reject state），且 q_reject ≠ q_accept

图灵机的程序（Program of Turing Machine）¶

状态转移函数（State Transfer Function） = 程序

δ = { qi Sj Sk R(L or N) ql }

qi — 当前状态（current state of the machine）
Sj — 读到的符号（symbol read by the machine）
Sk — 将要写入替换Sj的符号（symbol waiting to be written）
R, L, N — 分别表示右移一步、左移一步或保持不动
ql — 下一状态（next state of the machine）

示例: δ = {q0 0 0 R q0; q0 1 0 R q0}

向右移动并擦除读写头经过的所有空白格
永不停止且不向后移动

Turing Machine Program δ: Consecutive 1 Detection（连续1检测）¶

7个内部状态（除初始状态q₀外）

q0 B B R q1    // 起始状态，读写头指向左边缘，次态为q1

q1 1 C L q2    // 状态1，检测到"1"，标记C，开始计数

q1 0 C L q7    // 状态1，检测到"0"，标记C，开始清零

q1 B B N q1(STOP) // 状态1，检测到右边缘停机，左边是检测结果

q2 0 1 L q4    // 状态2，计数。从右（低位）向左（高位）计数

q2 1 0 L q2    // 状态2，计数。从右（低位）向左（高位）计数

q2 B 1 L q4    // 状态2，到左边缘计数结束，次态是q4

q4 1 1 L q4    // 状态4，读写头移到左边缘

q4 0 0 L q4    // 状态4，读写头移到左边缘

q4 B B R q3    // 读写头到左边缘，开始计数值右移1位

q3 1 0 R q5    // 计数值将右移1位，左边填"0"

q3 0 0 R q6    // 计数值将右移1位，左边填"0"

q3 C 0 R q1    // 右移结束，清计数标志

q5 1 1 R q5    // 状态5，右移"1"

q5 0 1 R q6    // 状态5，右移"1"

q5 C 1 R q1    // 右移"1"并结束右移，清计数标志

q6 1 0 R q5    // 状态6，右移"0"

q6 0 0 R q6    // 状态6，右移"0"

q6 C 0 R q1    // 右移"0"并结束右移，清计数标志

q7 1 0 L q7    // 状态7，清零

q7 0 0 L q7    // 状态7，清零

q7 B B R q3    // 检测到左边缘，清零结束。转到状态3，计数值右移一位

Universal Turing Machine Implementation（通用图灵机的实现）¶

理想图灵机无法实现（Ideal Turing Machine cannot be implemented）¶

"Cannot find an infinite long tape" — 找不到无限长的纸带
"Not universal computing system neither"
"Only fixed and mechanical computing system"

通用（Universal）图灵机（Universal Turing Machine）¶

"Long enough tape with head and tail connected, to replace the infinite long paper tape"

- 用首尾相连的足够长的纸带代替无限长的纸带

"Any Turing machine instruction code"

- 将任意图灵机指令编码写在纸带的起始部分

- 在纸带的其余部分操作输入

- 仍然效率低下（Still low efficiency）

两个核心问题¶

Carrier（载体）
Efficiency（效率）

Practical Turing Machine — A Real Computer（实用的图灵机——真正的计算机）¶

用大容量存储替换纸带（A large enough storage to replace the tape）¶

Magnetic storage for replacement — 磁存储
Semiconductor storage for replacement — 半导体存储

存储内部状态（Storing the inner state）¶

"Inner state does not store immediate, downgrading the efficiency" — 内部状态不立即存储，降低效率
"Register to store the immediate (i.e., subset of tape)" — 用寄存器存储立即数（即纸带的子集）
"Can significantly simplify computational structure and improve computing efficiency" — 可以显著简化计算结构并提高计算效率

增强HEAD的处理能力——CPU（Enhance the processing capability of HEAD--CPU）¶

"Require a stronger HEAD" — 需要更强大的HEAD
"Can be implement by Control of Register Transfer Technique: CPU" — 可以通过寄存器传输控制技术（CPU）实现
"Satisfactory Universal Turing Machine" — 令人满意的通用图灵机

Programable Register Transfer Technology to Implement the Universal Turing Machine¶

"问题改变，程序状态机改变"

Reset: add R2, R0, R0;

Input: lw R3, InPort(X);

X=0: addi R2, R0, 1;

X=1: nop;

Disp : sw R2, Disp(R0);

Disp : sw R2, Disp(R0);

Conversion of thinking: from digital systems turn to computer systems（思维转换：从数字系统到计算机系统）¶

用CPU实现图灵机的基本思想¶

"General digital system — A good implementation of Turing Machine"

关键要素：

§ Storage control sequence: solving the infinite tape — 存储控制序列：解决无限纸带问题
§ Triple let Instruction: Basic operation of HEAD — 三操作数指令：HEAD的基本操作
§ Control flow instructions: More control rules TABLE — 控制流指令：更多的控制规则表
§ Register: More state storage and immediate — 寄存器：更多的状态存储和立即数

Computation Thinking: Program solving（计算思维：程序求解）¶

转向使用CPU进行数字信息处理：

§ Algorithm design: Computing thinking — 算法设计：计算思维
§ Program design: Software thinking — 程序设计：软件思维
§ Program rules: Instruction → Rule and processing → Control of instructions

- Define instruction format: Design DataPath and Controller — 定义指令格式：设计数据通路和控制器

- Define data structure: Allocate storage space (Memory, I/O) — 定义数据结构：分配存储空间

Software-Hardware Cooperation Processing Thinking — 软硬件协同处理思维

六、Implementation of CPU（CPU的实现）¶

CPU的本质¶

"General digital system" — 通用数字系统
"A Turing Machine" — 一台图灵机

通过寄存器传输控制技术实现¶

Datapath（数据通路）: "The component of processor that performs arithmetic operations" — 执行算术运算的处理器组件
Control（控制单元）: "The component of processor that commands the datapath, memory, and I/O device according to the instructions of the program" — 根据程序指令指挥数据通路、内存和I/O设备的处理器组件

七、Components in CPU（CPU中的组件）¶

Multiplexer（多路选择器）
Adder（加法器）
ALU（算术逻辑单元）

八、Logics in CPU（CPU中的逻辑）¶

Unlocked vs. Clocked（无时钟 vs. 有时钟）¶

"Clocks used in synchronous logic" — 时钟用于同步逻辑

关键概念：

"when should an element that contains state be updated?" — 包含状态的元件何时应该更新？
cycle time（周期时间）
rising edge（上升沿）
falling edge（下降沿）

九、State Elements（状态元件）¶

State Storage in CPU（CPU中的状态存储）¶

Temporary register（临时寄存器）

WE: write an enable data in data out
General registers（通用寄存器）

Sequential Logic in CPU（CPU中的时序逻辑）¶

clk（时钟）
D-Flipflop（D触发器）

帮我讲解一下这个的实现模式### Sequential Lo...

边沿触发方法（An edge triggered methodology）¶

典型执行流程：

- read contents of some state elements

- send values through some combinational logic

- write results to one or more state elements

读取某些状态元件的内容
通过组合逻辑发送值
将结果写回一个或多个状态元件

十、Sequential Logic in CPU（CPU中的时序逻辑）¶

Register（寄存器）¶

"State element" — 状态元件
"Can be controlled by Write signal" — 可以通过写信号控制

十一、CPU we will be doing（我们将实现的CPU）¶

RISC-V指令集实现¶

"We'll look at an implementation of RISC-V"

简化为仅包含以下指令：

内存引用指令（memory-reference instructions）: lw, sw

- lw（load word）：从内存加载字

- sw（store word）：将字存储到内存

算术逻辑指令（arithmetic-logical instructions）: add, sub, and, or, slt

- add（加法）

- sub（减法）

- and（与运算）

- or（或运算）

- slt（set less than，小于则置位）

控制流指令（control flow instructions）: beq, jal

- beq（branch if equal，相等则分支）

- jal（jump and link，跳转并链接）

[[sys汇编# 十二、指令编码格式总结]]

十二、What are the steps?（执行步骤）¶

对于每条指令，前两步是相同的：

Fetch the instruction from the memory — 从内存中取出指令
Decode and read the registers — 解码并读取寄存器

后续步骤取决于指令类别：

§ Memory-reference（内存引用类）
§ Arithmetic-logical（算术逻辑类）
§ branches（分支类）