271 lines
9.1 KiB
Markdown
271 lines
9.1 KiB
Markdown
---
|
||
tags:
|
||
- 计算机系统结构
|
||
- 重点复习
|
||
- 流水线
|
||
- 非线性流水线
|
||
- 调度
|
||
create time: 2026-06-16 21:21
|
||
---
|
||
|
||
# 大题 3 — 非线性流水线调度
|
||
|
||
## 概述
|
||
|
||
本题考查**非线性流水线的调度**全过程：从**预约表**出发，提取**禁止表**、构建**冲突向量**、画出**状态转移图**、求**最优调度策略**，最后画**时空图**并计算**性能指标**（吞吐率、加速比、效率）。这是本课程**分值最高、难度最大**的核心考点。
|
||
|
||
> [!tip] 考试重点
|
||
> 这道题几乎每年必考（A 卷 24 分、B 卷 16 分），务必完整掌握以下流程：
|
||
> **预约表 → 禁止表 → 冲突向量 → 状态转移图 → 最优调度 → 时空图 → 性能计算**
|
||
|
||
## 正文
|
||
|
||
### 一、完整解题流程
|
||
|
||
```mermaid
|
||
graph TD
|
||
A["Step 0: Reservation Table"] --> B["Step 1: Forbidden Set F"]
|
||
B --> C["Step 2: Initial Collision Vector C0"]
|
||
C --> D["Step 3: State Transition Diagram"]
|
||
D --> E["Step 4: Find Optimal Schedule"]
|
||
E --> F["Step 5: Space-Time Diagram"]
|
||
F --> G["Step 6: Performance Metrics"]
|
||
|
||
style A fill:#e3f2fd
|
||
style G fill:#e8f5e9
|
||
```
|
||
|
||
### 二、Step 0：预约表（Reservation Table）
|
||
|
||
预约表记录**一个任务**在各时钟周期对各流水段的占用情况。`x` 表示占用，空表示空闲。
|
||
|
||
> [!question] 预约表从哪来？
|
||
> 预约表由任务的**执行过程**决定——它描述了单个任务在流水线中的资源使用模式。考试中预约表直接给出，不需要自己推导。
|
||
|
||
### 三、Step 1：提取禁止表 $F$
|
||
|
||
**规则**：对预约表中的**每一行**（每个流水段），找出该段被占用的所有时刻，计算每两个时刻之间的**时间间隔**，所有间隔的集合就是禁止表。
|
||
|
||
$$F = \{d \mid \exists \text{某段在时刻 } t_1 \text{ 和 } t_2 \text{ 被占用，且 } d = |t_2 - t_1|\}$$
|
||
|
||
> [!warning] 注意
|
||
> - 只看**同一段**的多个占用时刻，不同段之间不比较
|
||
> - 间隔取**绝对值**
|
||
> - **去重**——相同的间隔只保留一个
|
||
|
||
### 四、Step 2：构建初始冲突向量 $C_0$
|
||
|
||
冲突向量是一个**二进制位串**，第 $i$ 位为 1 表示间隔 $i$ 禁止进入新任务。
|
||
|
||
$$C_0[j] = \begin{cases} 1 & \text{if } j \in F \\ 0 & \text{if } j \notin F \end{cases}$$
|
||
|
||
**位数** = 禁止表中的**最大间隔**值。
|
||
|
||
> [!example] 示例：禁止表 $F = \{2, 4\}$
|
||
>
|
||
> 最大禁止间隔为 4，冲突向量共 4 位：
|
||
>
|
||
> | 位位置 | 4 | 3 | 2 | 1 |
|
||
> |:------:|:-:|:-:|:-:|:-:|
|
||
> | 值 | 1 | 0 | 1 | 0 |
|
||
>
|
||
> $C_0 = 1010$
|
||
>
|
||
> 含义：间隔 1 和 3 允许（位为 0），间隔 2 和 4 禁止（位为 1）。
|
||
|
||
### 五、Step 3：画状态转移图
|
||
|
||
对每个状态（冲突向量），找出**允许的间隔** $j$（对应位为 0），计算转移后的新状态：
|
||
|
||
$$C_{new} = SHR^{(j)}(C_{current}) \lor C_0$$
|
||
|
||
其中 $SHR^{(j)}$ 表示**右移 $j$ 位**（高位补 0），$\lor$ 表示**按位或**。
|
||
|
||
**重复这个过程**直到所有可达状态都被探索。
|
||
|
||
> [!note] 状态转移的直觉理解
|
||
> - **右移 $j$ 位**：相当于"过了 $j$ 拍后，之前禁止的间隔距离缩短了 $j$"
|
||
> - **或上 $C_0$**：新进入的任务带来了与第一个任务相同的禁止间隔
|
||
> - 当所有位都为 1 时，该状态为**终态**——无法再进入新任务
|
||
|
||
### 六、Step 4：求最优调度策略
|
||
|
||
在状态转移图中找出所有**闭合回路**（从某状态出发回到自身），计算每个回路的**平均延迟**：
|
||
|
||
$$\text{平均延迟} = \frac{\text{回路中各间隔之和}}{\text{回路长度（间隔个数）}}$$
|
||
|
||
**平均延迟最小的回路**即为最优调度策略。
|
||
|
||
> [!important] 找回路的技巧
|
||
> 1. 从初始状态 $C_0$ 出发
|
||
> 2. 列出所有可能的转移路径
|
||
> 3. 找到回到 $C_0$ 的所有回路
|
||
> 4. 比较各回路的平均延迟
|
||
> 5. 注意：回路可以重复——如 (3, 2, 3, 2, ...) 只需取最小循环单元 (3, 2)
|
||
|
||
### 七、完整例题（参考 A 卷 24 分大题）
|
||
|
||
> [!example] 例题：4 段流水线调度
|
||
>
|
||
> **已知**预约表如下：
|
||
>
|
||
> | 段 \ 时刻 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
||
> |:----------:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|
||
> | $S_1$ | x | | | | x | | |
|
||
> | $S_2$ | | x | | | | x | |
|
||
> | $S_3$ | | | x | | | | x |
|
||
> | $S_4$ | | | | x | | | |
|
||
>
|
||
> ---
|
||
>
|
||
> **Step 1：提取禁止表**
|
||
>
|
||
> | 段 | 占用时刻 | 间隔 |
|
||
> |:--:|:--------:|:----:|
|
||
> | $S_1$ | 1, 5 | $5-1=4$ |
|
||
> | $S_2$ | 2, 6 | $6-2=4$ |
|
||
> | $S_3$ | 3, 7 | $7-3=4$ |
|
||
> | $S_4$ | 4 | 无间隔 |
|
||
>
|
||
> $$F = \{4\}$$
|
||
>
|
||
> ---
|
||
>
|
||
> **Step 2：构建初始冲突向量**
|
||
>
|
||
> 最大禁止间隔 = 4，冲突向量 4 位：
|
||
>
|
||
> $$C_0 = 1000$$
|
||
>
|
||
> | 位位置 | 4 | 3 | 2 | 1 |
|
||
> |:------:|:-:|:-:|:-:|:-:|
|
||
> | 值 | 1 | 0 | 0 | 0 |
|
||
>
|
||
> 允许间隔：$j \in \{1, 2, 3\}$
|
||
>
|
||
> ---
|
||
>
|
||
> **Step 3：计算状态转移**
|
||
>
|
||
> 从 $C_0 = 1000$ 出发：
|
||
>
|
||
> - $j=1$：$SHR^{(1)}(1000) \lor 1000 = 0100 \lor 1000 = 1100 = C_1$
|
||
> - $j=2$：$SHR^{(2)}(1000) \lor 1000 = 0010 \lor 1000 = 1010 = C_2$
|
||
> - $j=3$：$SHR^{(3)}(1000) \lor 1000 = 0001 \lor 1000 = 1001 = C_3$
|
||
>
|
||
> 从 $C_1 = 1100$（允许间隔 $j \in \{1, 2\}$，注意第 1 位和第 2 位为 0）：
|
||
>
|
||
> 等等，$C_1 = 1100$，第 1 位=0，第 2 位=0，所以允许 $j=1, 2$。
|
||
>
|
||
> - $j=1$：$SHR^{(1)}(1100) \lor 1000 = 0110 \lor 1000 = 1110 = C_4$
|
||
> - $j=2$：$SHR^{(2)}(1100) \lor 1000 = 0011 \lor 1000 = 1011 = C_5$
|
||
>
|
||
> 从 $C_2 = 1010$（允许间隔 $j \in \{1, 3\}$）：
|
||
>
|
||
> - $j=1$：$SHR^{(1)}(1010) \lor 1000 = 0101 \lor 1000 = 1101 = C_6$
|
||
> - $j=3$：$SHR^{(3)}(1010) \lor 1000 = 0001 \lor 1000 = 1001 = C_3$
|
||
>
|
||
> 从 $C_3 = 1001$（允许间隔 $j \in \{2, 3\}$）：
|
||
>
|
||
> - $j=2$：$SHR^{(2)}(1001) \lor 1000 = 0010 \lor 1000 = 1010 = C_2$
|
||
> - $j=3$：$SHR^{(3)}(1001) \lor 1000 = 0001 \lor 1000 = 1001 = C_3$（自环）
|
||
>
|
||
> 从 $C_4 = 1110$（允许间隔 $j=1$）：
|
||
>
|
||
> - $j=1$：$SHR^{(1)}(1110) \lor 1000 = 0111 \lor 1000 = 1111 = C_7$（终态）
|
||
>
|
||
> 从 $C_5 = 1011$（允许间隔 $j=2$）：
|
||
>
|
||
> - $j=2$：$SHR^{(2)}(1011) \lor 1000 = 0010 \lor 1000 = 1010 = C_2$
|
||
>
|
||
> 从 $C_6 = 1101$（允许间隔 $j=2$）：
|
||
>
|
||
> - $j=2$：$SHR^{(2)}(1101) \lor 1000 = 0011 \lor 1000 = 1011 = C_5$
|
||
>
|
||
> ---
|
||
>
|
||
> **Step 4：画状态转移图**
|
||
>
|
||
> ```mermaid
|
||
> stateDiagram-v2
|
||
> direction LR
|
||
> [*] --> C0
|
||
> C0 --> C1: "j=1"
|
||
> C0 --> C2: "j=2"
|
||
> C0 --> C3: "j=3"
|
||
> C1 --> C4: "j=1"
|
||
> C1 --> C5: "j=2"
|
||
> C2 --> C6: "j=1"
|
||
> C2 --> C3: "j=3"
|
||
> C3 --> C2: "j=2"
|
||
> C3 --> C3: "j=3"
|
||
> C4 --> C7: "j=1"
|
||
> C5 --> C2: "j=2"
|
||
> C6 --> C5: "j=2"
|
||
> ```
|
||
>
|
||
> ---
|
||
>
|
||
> **Step 5：找最优调度策略**
|
||
>
|
||
> 从 $C_0$ 出发的所有闭合回路：
|
||
>
|
||
> | 回路 | 间隔序列 | 平均延迟 |
|
||
> |:----:|:--------:|:--------:|
|
||
> | $C_0 \to C_3 \to C_3$ (自环) | (3) | $3/1 = 3.0$ |
|
||
> | $C_0 \to C_3 \to C_2 \to C_3$ | (3, 2) | $(3+2)/2 = 2.5$ |
|
||
> | $C_0 \to C_2 \to C_3 \to C_2$ | (2, 3) | $(2+3)/2 = 2.5$ |
|
||
> | $C_0 \to C_1 \to C_5 \to C_2 \to C_3$ | (1, 2, 2, 3) | $8/4 = 2.0$ |
|
||
>
|
||
> ... 需要检查是否回路回到 $C_0$。由于本例中从 $C_0$ 出发不一定回到 $C_0$，需要选取**最小平均延迟的循环回路**。
|
||
>
|
||
> **最优调度策略**：间隔序列为 **(3, 2)**，平均延迟 **2.5 拍**。
|
||
>
|
||
> ---
|
||
>
|
||
> **Step 6：画时空图（4 个任务）**
|
||
>
|
||
> 按调度策略 (3, 2, 3, 2, ...)，任务进入时刻：0, 3, 5, 8
|
||
>
|
||
> | 段 \ 时刻 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|
||
> |:----------:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:--:|:--:|:--:|
|
||
> | $S_1$ | $T_1$ | | | | | $T_2$ | | | | | $T_3$ | | |
|
||
> | $S_2$ | | $T_1$ | | | | | $T_2$ | | | | | $T_3$ | |
|
||
> | $S_3$ | | | $T_1$ | | | | | $T_2$ | | | | | $T_3$ |
|
||
> | $S_4$ | | | | $T_1$ | | | | | $T_2$ | | | | |
|
||
>
|
||
> （续表：任务 $T_4$ 在时刻 10 进入...）
|
||
>
|
||
> ---
|
||
>
|
||
> **Step 7：计算性能指标**
|
||
>
|
||
> 4 个任务总完成时间 = 最后一个任务进入时刻 + 单个任务执行时间 = $8 + 4 = 12$ 拍
|
||
>
|
||
> - **吞吐率**：$TP = \frac{4}{12} = \frac{1}{3}$ 任务/拍
|
||
> - **串行执行时间**：$T_{seq} = 4 \times 4 = 16$ 拍
|
||
> - **加速比**：$S = \frac{T_{seq}}{T_k} = \frac{16}{12} = 1.33$
|
||
> - **效率**：$E = \frac{S}{k} = \frac{1.33}{4} = 33.3\%$（$k$ 为段数）
|
||
|
||
### 八、性能指标公式汇总
|
||
|
||
| 指标 | 公式 | 说明 |
|
||
|------|------|------|
|
||
| **吞吐率** | $TP = \frac{n}{T_k}$ | $n$ 个任务在 $T_k$ 时间完成 |
|
||
| **加速比** | $S = \frac{T_{seq}}{T_k} = \frac{n \times k \times \Delta t}{T_k}$ | 串行时间 / 流水线时间 |
|
||
| **效率** | $E = \frac{S}{k}$ | 流水线利用率 |
|
||
|
||
其中 $T_k = (n-1) \times \text{平均延迟} + k \times \Delta t$（$k$ 为段数，$\Delta t$ 为时钟周期）。
|
||
|
||
> [!warning] 考试常见错误
|
||
> 1. 提取禁止表时**只看同一行**的间隔，不要跨行比较
|
||
> 2. 冲突向量的位数 = **最大禁止间隔**，不是禁止表的元素个数
|
||
> 3. 状态转移公式是 **右移**（不是左移），且要 **或上 $C_0$**
|
||
> 4. 最优调度是平均延迟**最小**的回路，不是总延迟最小的
|
||
> 5. 画时空图时注意：每个任务的各段占用时刻必须与预约表一致
|
||
|
||
## 关联笔记
|
||
- [[计算机系统结构/复习文档/流水线技术]]
|
||
- [[小题2-流水线的分类]]
|
||
- [[小题4-流水寄存器的作用]]
|