What We Need in a Scheduling Model

Posted on

Posts in This Series·

  1. Understanding In-Order Pipelines and Pipeline Stalls
  2. What We Need in a Scheduling Model
  3. Scheduling Model: GCC and LLVM Perspectives
  4. Tuning Your Scheduling Model for Better Performance(TODO)

Recap·

第一篇文章中，我们已经说过，调度器主要是用来解决三类冲突，

  • 汇编解码出的微操作数过多，无法在一个周期内发射出去所导致的发射阻塞
  • 指令争夺相同运算单元导致流水线暂停的结构冲突
  • 指令间存在寄存器读写依赖导致流水线暂停的数据冲突

这一节我们将详细展开，并且说明如果我们想要解决这些导致流水线暂停的冲突，我们需要哪些具体的流水线信息。

Model it·

假设我们现在不知道调度模型需要包含什么信息，目前先构建一个空的结构体定义struct Pipeline，后面我们将逐渐完善这个结构体内的变量定义。

这个调度模型定义，即不是 LLVM 中的用法，也不是 gcc 中的用法，在这里是用更简单的方式表述，后面我们才会延伸到 LLVM 和 gcc 中的用法。

1
2
3
4
struct Pipeline {
  // Contains nothing.
  // We don't yet know what we need to model a pipeline.
};

Scheduling Model and Scheduling Algorithm·

在讨论调度模型需要哪些信息之前，我们先简单介绍一下目前最广泛使用的调度算法，列表调度算法（List Scheduling Algorithm）。它通常是在基本块内部进行的，通过在满足依赖关系的前提下，重排指令顺序，以尽可能提升流水线的利用率。

整个列表调度的基本流程可以概括为，

  • 首先，扫描基本块中的所有汇编指令，构建一张有向无环图（DAG）。图中的每个节点代表一条指令，边代表指令之间的依赖关系（如 RAW、WAW）。
  • 接着，对 DAG 进行调度，调度的过程就是使用一系列启发式策略对就绪指令进行拓扑排序的过程。

就绪指令的意思是，这条指令在不存在任何冲突，即所有依赖都已满足的指令，可以“安全”地发射出去。

那么问题来了，如何判断一条指令是就绪指令呢？

比如上一节中我们作为例子的汇编代码，

1
2
3
4
5
6
7
mul a0, a1, a2
mul a3, a4, a5
add t0, a0, a3
add t0, t2, 1
add t1, t1, 1
add a0, a0, 1
add t3, t3, 1

它对应的 DAG 图如下，

graph TD
    A0[mul a0, a1, a2]
    A1[mul a3, a4, a5]
    A2[add t0, a0, a3]
    A3[add t0, t2, 1]
    A4[add t1, t1, 1]
    A5[add a0, a0, 1]
    A6[add t3, t3, 1]

    A0 -- RAW --> A2
    A1 -- RAW --> A2
    A2 -- WAW --> A3
    A0 -- RAW --> A5

显然，刚开始我们有四条就绪指令，即四条入度为 0 的指令，

1
2
=== Ready List ===
[mul a0, a1, a2], [mul a3, a4, a5], [add t1, t1, 1], [add t3, t3, 1]

假设调度器选择mul a0, a1, a2指令进行调度以后，就绪指令会如何变化？

graph TD
    A0[mul a0, a1, a2]
    A1[mul a3, a4, a5]
    A2[add t0, a0, a3]
    A3[add t0, t2, 1]
    A4[add t1, t1, 1]
    A5[add a0, a0, 1]
    A6[add t3, t3, 1]

    A0 ~~~ A2
    A1 -- RAW --> A2
    A2 -- WAW --> A3
    A0 ~~~ A5

add a0, a0, 1已经入度为 0，它是否可以直接加入就绪队列，或者什么时候它可以被加入就绪队列？mul a3, a4, a5是否与上一条被调度的指令有结构冲突，它是否需要被剔出就绪队列？

显然这个问题，我们在没有任何信息的情况下，是无法判断的，因为这是平台相关的信息，是由硬件流水线决定的。所以，我们就需要调度模型来解决这些问题了，我们需要给流水线进行建模，在建立的模型中包含以上信息，提供给调度算法查询，基于这些信息，调度算法才能做出更优的判断。因此，调度器可以认为是调度算法与调度模型共同组成的。如果没有调度模型，调度算法就无法获取流水线信息，只能基于默认的假设值来做调度，那么自然调度的效果就不会太好。

因此，我们可以这样定义调度模型（Scheduling Model）：调度模型是一组用于抽象目标架构中流水线行为的参数集合，它描述了指令在硬件上的资源需求、延迟特性、执行约束等信息，供调度算法参考与查询，从而生成更符合硬件实际的指令排列方案。

它通常会回答如下问题：

  • 同一个周期内最多能发射几条指令？
  • 发射一条指令时，会占用哪些资源？资源是否冲突？
  • 一条指令的输出什么时候可被下一条使用？

这些信息对顺序核调度尤为关键，因为这些核心无法自动乱序调度、规避冲突，只能依赖静态调度器的来尽可能高效地填满流水线。

About Dispatch Stalls·

我们首先来回答第一个问题，

假设我们现在有个 n 发射的流水线，我们先不考虑它的功能单元种类和数量，一个简化的流水线就如下图所示，

flowchart LR
    %% Issue Paths
    Issue0[Slot 0]
    Issue1[Slot 1]
    Issue2[Slot 2]
	Issue..[...]
    Issuen[Slot n]
    
    %% Pipelins
    EX[EX Stage]
	...[...]

    %% Connections
    Issue0 --> EX
    Issue1 --> EX
    Issue2 --> EX
    Issuen --> EX
    EX --> ...

既然这个流水线只有 n 个 Slot 可以使用，那么在同一个周期，它最多只能发射 n 个微操作，如果微操作的数量多于 n 个，则会在发射阶段阻塞，导致前端流水线暂停。

那么，我们就需要告诉调度器，我们这个流水线有 n 个发射通路。当然，只有发射通路的数量是不够的，我们还需要告诉调度器，每条指令会被解码成多少个微操作。因此，我们需要在struct Pipeline中添加issue_width来表示发射通路数量，并且新创建一个struct Ins，并添加num_micro_ops变量来表示这条指令会被解码成多少个微操作。

1
2
3
4
5
6
7
struct Pipeline {
  int issue_width;
};

struct Ins {
  int num_micro_ops;  
};

调度器在拿到这两个信息以后，就可以控制在一个周期内发射的指令，让其num_micro_ops的总和不超过issue_width，就可以防止流水线在实际运行中发生发射阻塞了。

当然这里说的是理想情况。真实情况下，由于调度模型可能存在不准确性，无法百分百契合对应硬件流水线，以及调度器中存在复杂的启发式算法，会根据不同情况选择不同的指令进行调度，比如，一个可能导致三个周期停顿的数据依赖和只导致一个周期停顿的发射停顿，调度器理应选择后者优先调度。

About Resource Conflicts·

资源冲突的例子在第一篇举过很多，这里就不再赘述。如果想要调度器能够在调度时候充分考虑到资源冲突的情况，自然需要告诉调度器，流水线有哪些功能单元，对应的功能单元有多少个，以及什么指令使用什么功能单元。

1
2
3
4
5
6
7
8
9
10
11
12
13
struct FuncUnit {
  int num_units; 
};

struct Pipeline {
  int issue_width;
  struct FuncUnit* func_units[];
};

struct Ins {
  int num_micro_ops;
  struct FuncUnit* used_unit;
};
flowchart LR
    %% Issue Paths
    Issue0[Slot 0]
	Issue1[Slot 1]

    %% Pipelines
    ALU0[ALU0]
    ALU1[ALU1]
    MUL[MUL]

    %% Connections
    Issue0 --> ALU0
    Issue0 --> ALU1
    Issue0 --> MUL

对于上图流水线，我们可以构建对应FuncUnit，Pipeline，Ins，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// FuncUnit ALU
struct FuncUnit* ALU = malloc(...);
// FuncUnit MUL
struct FuncUnit* MUL = malloc(...);

ALU->num_units = 2;
MUL->num_units = 1;

// Pipeline _Pipeline
struct Pipeline* _Pipeline = malloc(...);
_Pipeline->issue_width = 2;
_Pipeline->func_units[0] = ALU;
_Pipeline->func_units[1] = MUL;

// Ins Add and Mul
struct Ins* Add = malloc(...);
struct Ins* Mul = malloc(...);
Add->num_micro_ops = 1;
Add->used_unit = ALU;
Mul->num_micro_ops = 1;
Mul->used_unit = MUL;

这里只是为了讲解调度模型里面的内容，就不纠结 c 的语法了～

So，当调度器拿到这些信息以后，就可以在对汇编调度时考虑到资源冲突了。

比如当遇到如下汇编，

1
2
3
4
add a0, a0, a1
add a2, a3, a2
mul t2, t3, t4
mul t0, t0, t1

当处理前两条add时，调度器可以知道，它们的num_micro_ops都为 1，因此双发不会导致发射阻塞，并且它们需要使用ALU单元，并且ALU单元剩余两个也不会发生资源冲突，因此，两条add可以在第一个周期发射。

第二个周期，在处理两条mul指令时，由于它们的num_micro_ops都为 1，因此双发不会导致发射阻塞，但是它们都需要使用MUL单元，而MUL单元只有一个，因此在同一周期发射会导致资源冲突。

那么，新的问题来了，何时能发射第二条mul指令呢？

问题的答案自然很简单，在第一条mul指令释放MUL单元以后，第二条mul指令就能发射了，那么第一条mul指令何时会释放其占据的功能单元呢？

不知道你是否想到第一篇中所提到的内容，如果一个功能单元是流水线化的，那么它每个周期都能进入一条新的指令，如果它不是流水线化的，那么它可能就会被占据多个周期再释放。

因此，如果MUL单元是完全流水线化的，那么，第二条mul指令即可以在第三个周期被发射，如果MUL单元是非流水线化的，那么，我们就需要告诉调度器，这个功能单元会被占用多久了。

最终，一个可以详细描述流水线中的资源使用情况的结构体定义如下所示，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct FuncUnit {
  // How many does it have?
  int num_units; 
};

struct Pipeline {
  int issue_width;
  struct FuncUnit* func_units[];
};

struct Ins {
  // How many mirco_ops does it have?
  int num_micro_ops;
  // Which FuncUnit does it take?
  struct FuncUnit* used_unit;
  // How many cycles does it take?
  int taken_cycles;
};

About Data Conflicts·

所谓数据冲突，自然是体系结构常说的，写后读，读后写，以及写后写，对应数据依赖，反依赖，以及输出依赖。其中反依赖和输出依赖称之为假依赖，可以通过寄存器重命名技术完全消除指令间的这两种依赖关系，而数据依赖是真依赖，是无法消除的。

寄存器重命名技术通常使用在乱序 CPU 中，因此对于乱序 CPU，需要主要关注的是数据依赖。而顺序 CPU 为主要为了节省资源，很少会使用寄存器重命名技术，因此三种依赖关系都是需要考虑在内的。

假设两条存在数据冲突的汇编分别为A和B，如下图所示，它们之间的边Latency = n表示它们需要间隔 n 个周期发射，才能保证流水线正常运行。

graph TD
    A -- Latency = n --> B

对于反依赖来说，这是一种最简单的依赖关系，因为它只影响调度顺序，即使两条存在反依赖的指令被排布在一起，也不会导致流水线暂停。

1
2
addi a1, a0, 1
mul a0, a2, a3

如上汇编，addi读a0，mul写a0，这构成一条 WAR 反依赖。

在大多数顺序CPU中，这类依赖并不会引起流水线暂停，因为读取和写回发生在不同的流水线阶段，并且读取阶段通常在写回阶段之前，如下图所示，addi如果和mul一起进入流水线，addi的读取发生在 ID 阶段，而mul的写回发生在 WB 阶段，前者是一定可以读取到正确的a0的值，而后者的写回也不会受到任何前者读取的影响。

flowchart LR
    IF[IF]
    ID[ID]
    EX[EX]
    MEM[MEM]
    WB[WB]

    IF --> ID
    ID --> EX
    EX --> MEM
    MEM --> WB

因此，我们认为两条存在反依赖的汇编之间的延迟为 0。

graph TD
    A0[addi a1, a0, 1]
    A1[mul a0, a2, a3]

    A0 -- WAR: Latency = 0 --> A1

再看稍微复杂一些的输出依赖，如下，addi和mul均写a0寄存器，这构成一条 WAW 输出依赖。

1
2
addi a0, a1, 1
mul a0, a2, a3

对于这两条指令，我们依然可以像分析反依赖一样，假设两条汇编同时进入五级流水线，它们就会同时到达 WB 阶段。由于它们请求写入同一寄存器，而在没有复杂的优先级仲裁的情况下，一个寄存器同一周期只能允许一个值的写入。因此addi会在当前周期成功写入a0值，而mul指令则要等待下一个周期才能写入，因此如果两条存在 WAW 输出依赖的指令同时进入流水线，会发生一个周期的停顿。

这里“没有复杂的优先级仲裁”说的主要也是顺序 CPU，顺序 CPU 的设计一般都会尽可能的降低功耗，节省资源，因此不会引入复杂的硬件机制，因此 WAW 输出依赖通常都会有一个周期的延迟，而乱序核是可以在一个周期发射存在 WAW 输出依赖的汇编指令的。

因此，我们认为两条存在输出依赖的汇编之间的延迟为 1。

graph TD
    A0[addi a0, a1, 1]
    A1[mul a0, a2, a3]

    A0 -- WAW: Latency = 1 --> A1

我们前面提到的两种数据依赖关系 —— 反依赖（WAR） 和 输出依赖（WAW） —— 本质上是与具体指令无关的。只要两条写相同寄存器的指令被安排在同一个周期发射，都会触发 WAW 冲突，不管它们是不是 addi 还是 mul。所以这类依赖在顺序核中，我们可以认为它们的延迟是定值，因此无需在调度模型中额外建模。

但真正复杂的，是 RAW 数据依赖。这种依赖是和具体的指令、甚至是具体的操作数位置绑定在一起的，也就是说，看似相似的 RAW 依赖，所带来的延迟也不尽相同。

例如我们来看下面这两段汇编：

1
2
3
4
5
6
7
---1---
addi a0, a1, 1
mul a2, a0, a3

---2---
mul a0, a2, a3
addi a1, a0, 1

它们都存在一个从 a0 读写之间的 RAW 依赖，但情况不一样：

  • 第一组中，mul 依赖的是 addi 的输出，它得等 addi 把结果写完，才能开始执行。
  • 第二组则是 addi 依赖 mul 的输出，由于 mul 通常比 addi 要慢，这种依赖导致更长的停顿。

所以我们可以总结为，RAW 依赖的关键在于，前一条指令写出来的值，什么时候可以被后续指令读取？这个“什么时候”其实就是一个变量，而这个变量的值显然依赖于前一条指令。

由于现代流水线会存在数据前推（Forwarding），它同样会影响两个汇编序列之间的实际延迟，这点也是需要在调度模型中进行建模的，但是本篇不讨论这个问题，我们将会下一节讨论 LLVM 和 gcc 的调度模型写法时再详述。

为了让调度器能在建 DAG 图的时候考虑这些数据依赖延迟，我们需要在每条指令的调度信息中显式建模它。为此，我们给调度器使用的Ins结构体新增一个变量latency，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct FuncUnit {
  int num_units; 
};

struct Pipeline {
  int issue_width;
  struct FuncUnit* func_units[];
};

struct Ins {
  int num_micro_ops;
  struct FuncUnit* used_unit;
  int taken_cycles;
  // How many cycles does its written-reg can be read after it issued. 
  int latency;
};

假设addi指令的latency为 1，mul指令的latency为 3，则上述两对汇编构建的 DAG 如下图所示。

graph TD
    A0[addi a0, a1, 1]
    A1[mul a2, a0, a3]

    A0 -- RAW: Latency = 1 --> A1
    
    A2[mul a0, a2, a3]
    A3[addi a1, a0, 1]

    A2 -- RAW: Latency = 3 --> A3

Summarize·

万万没有想到，三个简单的结构体，就基本能把流水线的结构、资源使用和数据依赖描述清楚了。

对于下面这样一个简单的流水线，

flowchart LR
    %% Issue Paths
    Issue0[Slot 0]
    Issue1[Slot 1]

    %% Connections
    Issue0 --> ALU0
    Issue0 --> ALU1
    Issue0 --> LDST
    Issue0 --> FP
    Issue0 --> MUL
    Issue0 --> DIV

我们将指令简单地分为五类，然后用我们定义的结构体来描述一下，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
struct FuncUnit ALU = { .num_units = 2 };
struct FuncUnit LDST = { .num_units = 1 };
struct FuncUnit FP   = { .num_units = 1 };
struct FuncUnit MUL = { .num_units = 1 };
struct FuncUnit DIV = { .num_units = 1 };

struct Pipeline Simple_Core = {
  // 2 slots -- dual-issue pipeline.
  .issue_width = 2,
  .func_units = { &ALU, &LDST, &FP, &MUL, &DIV }
};

struct Ins ALU_ins = {
  .num_micro_ops = 1,
  .used_unit = &ALU,
  .taken_cycles = 1,
  .latency = 1
};

struct Ins MUL_ins = {
  .num_micro_ops = 1,
  .used_unit = &MUL,
  // assuming MUL is pipelined.
  .taken_cycles = 1,
  .latency = 3
};

struct Ins DIV_ins = {
  .num_micro_ops = 1,
  .used_unit = &DIV,
  // assuming DIV is not-pipelined.
  .taken_cycles = 12,
  .latency = 12
};

struct Ins FP_ins = {
  .num_micro_ops = 1,
  .used_unit = &FP,
  // assuming FP is not-pipelined.
  .taken_cycles = 5,
  .latency = 5
};

下一篇我们将讲解 LLVM 和 GCC 中究竟是如何描述一个调度模型的，并且看一下与我在本节定义的结构体分别有哪些对应关系。

Peace~ ✌️