final-exam/计算机系统结构/重点复习/大题3-非线性流水线调度.md

---
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-流水寄存器的作用]]