指令级并行 ILP

多种并行度手段是现在计算机体系结构设计、编译器优化设计和应用程序设计等角度的重要手段。主要包括指令级并行（ILP, Instruction Level Parallelism）、数据级并行（DLP, Data Level Parallelism）、线程级并行（TLP, Thread Level Paprallelism），本文介绍ILP基本知识。

ILP一般有两种手段或者两种手段的结合：

1. 硬件动态发现和实现并行
2. 软件在编译时静态发现和实现并行

首先介绍流水化处理器的思想。

Pipelining

流水化的思想是将一个复杂指令拆解成一系列独立的操作，这些独立的操作使用不同的资源，这样这些操作将可以被掩盖起来。

Pipelined instruction Units

假设一条指令可以分解成以下步骤：

1. IF：instruction fetch
2. ID：instruction decode
3. EX：execute
4. MEM：memory access
5. WB：write back

所不同的是不同体系结构可能分解的步骤有所差异。

如上图，每个Pipeliing的阶段会使用不同的硬件资源，因此后续指令的不同阶段可以被掩盖。在不考虑流水线启动的时间消耗，理想情况下一条指令在一个机器时钟就可以完成。

Pipelined Execution Uinits

对于更复杂的指令，其EX可以再分解成不同的执行阶段，只要这些执行阶段使用不同的硬件资源，也一样可以流水起来。

比如浮点计算，其执行阶段可能需要几个机器周期才能完成。典型地，先从内存中取两个操作数，然后将指数部分normalize成一样，接着尾数部分相加，最后再把结果renormalize回去，如下：

这些执行阶段也是使用不同的硬件资源，同样可以流水化，如下：

Parallel Functions Units

有的体系结结构中，存在并行的功能单元。这样，只要功能单元空闲，对应功能的指令就可以执行，如下：

假设有$n$个并行功能单元，每个功能单元需要$m$个cycles完成对应指令，则每个cycle平均可以完成$n/m$次操作。

Compiling for Scalar Piplines

在流水化体系结构中，流水打断是非常影响性能。常见以下打断流水的风险类型如下：

• structural hazards：当硬件资源不足以满足指令掩盖的需求。
• Data hazards：前后指令存在数据依赖。
• Control hazards：遇到分支语句。

structural hazards

假设硬件只有一个内存端口，则取指令和取数据不能同时进行，如下：

Data hazards

考虑下面的指令序列：

ADD R1,R2,R3
SUB R4,R1.R5
1
2

ADD的结果不需要写回，直接可以用于SUB指令。

再考虑以下指令序列：

LW  R1,0(R2)
ADD R3,R1,R4
1
2

LW在访存之后，才能执行SUB指令，产生了一个cycle的打断：

这种情况下，编译器可以调度可以在这两条指令之间插入一条不使用正在加载寄存器的指令来消除这个问题。

对于Parallel Fuction Units结构的机器，也会遇到数据依赖情况，比如：

A+B+C+D
1

编译器可以调度成：

（A+B）+ (C+D)
1

Control hazards
当分支条件满足时候，紧跟的指令的流水会被打断。有的编译器可以通过谓词优化来解决分支打断的流水。

以上提供的例子，尤其是Data Hazards，基本原则是通过指令调度重排指令序列来解决流水打断。

Multiple Issue

通过时钟发射多条指令，处理器可以在每个时钟周期处理不同指令，就是多指令发送。和流水线技术类似，多指令发送既可以通过软件方式也可以通过硬件方式进行管理。

通过软件管理的指令并发行的机器称为超长指令字（VLIW，Very Long Instruction Word）机器。VLIW比一般指令字更长，这样的指令字可以在同一个时钟周期内发送多条指令编码。编译器可以判断哪些指令可以并行执行，将它们编码在一起，组成VLIW进行发射（也可以提供给用户）。

通过硬件进行管理指令并发性的机器称为超标量（Superscalar）机器。这些标量指令呈现给用户是顺序执行的语义，机器自动判断指令间的依赖关系，然后将没有依赖的运算分量并行发射。

参考

• [1] optimizing compilers for modern architectures a dependence-based approach
• [2] [龙书]编译原理技术与工具