原创 3.4 预读机制1

随着处理器制造工艺的提高，处理器主频越来越高，存储器和外部设备的访问速度虽然也得到极大的提升，但是依然不与处理器主频的提升速度成正比，从而处理器的运行速度和外部设备的访问速度之间的差距越来越大，存储器瓶颈问题愈发严重。虽然Cache的使用有效缓解了存储器瓶颈问题，但是仅使用Cache远远不够。

因为不管Cache的命中率有多高，总有发生Cache行Miss的情况。一旦Cache行出现Miss，处理器必须启动存储器周期，将需要的数据从存储器重新填入Cache中，这在某种程度上增加了存储器访问的开销。

使用预读机制可以在一定程度上降低Cache行失效所带来的影响。处理器系统可以使用的预读机制，包括指令预读、数据预读、外部设备的预读队列和操作系统提供的预读策略。本章将简要介绍指令预读，并重点介绍CPU如何对主存储器和外部设备进行数据预读。并以此为基础，详细说明PCI总线使用的预读机制。

3.4.1 Instruction Fetch

在一段程序中，存在大量的分支预测指令，因而在某种程度上增加了instruction fetch的难度。如何判断程序的执行路径是指令预读首先需要解决的问题。

在CPU中通常设置了分支预测单元(Branch Predictor)，在分支指令执行之前，分支预测单元需要预判分支指令的执行路径，从而进行指令预取。但是分支预测单元并不会每次都能正确判断分支指令的执行路径，这为指令预读制造了不小的麻烦，在这个背景下许多分支预测策略应运而生。

这些分支预测策略主要分为静态预测和动态预测两种方法。静态预测方法的主要实现原理是利用Profiling工具，静态分析程序的架构，并为编译器提供一些反馈信息，从而对程序的分支指令进行优化。如在PowerPC处理器的转移指令中存在一个“at”字段，该字段可以向CPU提供该转移指令是否Taken[1]的静态信息。在PowerPC处理器中，条件转移指令“bc”表示Taken；而“bc-”表示Not Taken。

CPU的分支预测单元在分析转移指令时可以预先得知该指令的转移结果。目前在多数CPU中提供了动态预测机制，而且动态预测的结果较为准确。因此在实现中，许多PowerPC内核并不支持静态预测机制，如E500内核并不支持这种机制。

CPU使用的动态预测机制是本节研究的重点。而在不同的处理器中，分支预测单元使用的动态预测算法并不相同。在一些功能较弱的处理器，如8b/16b微控制器中，分支指令的动态预测机制较为简单。在这些处理器中，分支预测单元常使用以下几种方法动态预测分支指令的执行。

(1) 分支预测单元每一次都将转移指令预测为Taken，采用这种方法无疑非常简单，而且命中率在50%以上，因为无条件转移指令都是Taken，当然使用这种方法的缺点也是显而易见的。

(2) 分支预测单元将向上跳转的指令预测为Taken，而将向下跳转的指令预测为Not Taken。分支预测单元使用的这种预测方式与多数程序的执行风格类似，但是这种实现方式并不理想。

(3) 一条转移指令被预测为Taken，而之后这条转移指令的预测值与上一次转移指令的执行结果相同。

当采用以上几种方法时，分支预测单元的硬件实现代价较低，但是使用这些算法时，预测成功的概率较低。因此在高性能处理器中，如PowerPC和x86处理器并不会采用以上这3种方法实现分支预测单元。

目前在高性能处理器中，常使用BTB(Branch Target Buffer) 管理分支预测指令。在BTB中含有多个Entry，这些Entry由转移指令的地址低位进行索引，而这个Entry的Tag字段存放转移指令的地址高位。BTB的功能相当于存放转移指令的Cache，其状态机转换也与Cache类似。当分支预测单元第一次分析一条分支指令时，将在BTB中为该指令分配一个Entry，同时也可能会淘汰BTB中的Entry。目前多数处理器使用LRU (Least recently used)算法淘汰BTB中的Entry。

在BTB的每个Entry中存在一个Saturating Counter。该计数器也被称为Bimodal Predictor，由两位组成，可以表示4种状态，为0b11时为“Strongly Taken”； 为0b10时为“Weakly Taken”；为0b01时为“Weakly not Taken”；为0b00时为“Strongly not Taken”。

当CPU第一次预测一条转移指令的执行时，其结果为Strongly Taken，此时CPU将在BTB中为该指令申请一个Entry，并置该Entry的Saturating Counter为0b11。此后该指令将按照Saturating Counter的值，预测执行，如果预测结果与实际执行结果不同时，将Saturating Counter的值减1，直到其值为0b00；如果相同时，将Saturating Counter的值加1，直到其值为0b11。目前Power E500内核和Pentium处理器使用这种算法进行分支预测。

使用Saturating Counter方法在处理转移指令的执行结果为1111011111或者0000001000时的效果较好，即执行结果大多数为0或者1时的预测结果较好。然而如果一条转移指令的执行结果具有某种规律，如为010101010101或者001001001001时，使用Saturating Counter并不会取得理想的预测效果。

在程序的执行过程中，一条转移指令在执行过程中出现这样有规律的结果较为常见，因为程序就是按照某种规则书写的，按照某种规则完成指定的任务。为此Two-Level分支预测方法应运而生。

Two-Level分支预测方法使用了两种数据结构，一种是BHR(Branch History Register)；而另一种是PHT(Pattern History Table)。其中BHR由k位组成，用来记录每一条转移指令的历史状态，而PHT表含有2k个Entry组成，而每一个Entry由两位Saturating Counter组成。BHR和PHT的关系如图3‑10所示。

假设分支预测单元在使用Two-Level分支预测方法时，设置了一个PBHT表(Per-address Branch History Table)存放不同指令所对应的BHR。在PBHT表中所有BHR的初始值为全1，而在PHT表中所有Entry的初始值值为0b11。BHR在PBHT表中的使用方法与替换机制与Cache类似。

当分支预测单元分析预测转移指令B的执行时，将首先从PBHT中获得与转移指令B对应的BHR，此时BHR为全1，因此CPU将从PHT的第11…11个Entry中获得预测结果0b11，即Strongly Taken。转移指令B执行完毕后，将实际执行结果Rc更新到BHR寄存器中，并同时更新PHT中对应的Entry。

当CPU再次预测转移指令B的执行时，仍将根据BHR索引PHT表，并从对应Entry中获得预测结果。而当指令B再次执行完毕后，将继续更新BHR和PHT表中对应的Entry。当转移指令的执行结果具有某种规律(Pattern)时，使用这种方法可以有效提高预测精度。如果转移指令B的实际执行结果为001001001….001，而且k等于4时，CPU将以0010-0100-1001这样的循环访问BHR，因此CPU将分别从PHT表中的第0010、0100和1001个Entry中获得准确的预测结果。

由以上描述可以发现，Two-Level分支预测法具有学习功能，并可以根据转移指令的历史记录产生的模式，在PHT表中查找预测结果。该算法由T.Y. Yeh and Y.N. Patt在1991年提出，并在高性能处理器中得到了大规模应用。

Two-Level分支预测法具有许多变种。目前x86处理器主要使用“Local Branch Prediction”和“Global Branch Prediction”两种算法。

在“Local Branch Prediction”算法中，每一个BHR使用不同的PHT表，Pentium II和Pentium III处理器使用这种算法。该算法的主要问题是当PBHT表的Entry数目增加时，PHT表将以指数速度增长，而且不能利用其它转移指令的历史信息进行分支预测。而在“Global Branch Prediction”算法中，所有BHR共享PHT表，Pentium M、Pentium Core和Core 2处理器使用这种算法。

在高性能处理器中，分支预测单元对一些特殊的分支指令如“Loop”和“Indirect跳转指令”设置了“Loop Prediction”和“Indirect Prediction”部件优化这两种分支指令的预测。此外分支预测单元，还设置了RSB(Return Stack Buffer)，当CPU调用一个函数时，RSB将记录该函数的返回地址，当函数返回时，将从RSB中获得返回地址，而不必从堆栈中获得返回地址，从而提高了函数返回的效率。

目前在高性能处理器中，动态分支预测的主要实现机制是CPU通过学习以往历史信息，并进行预测，因而Neural branch predictors机制被引入，并取得了较为理想的效果，本节对这种分支预测技术不做进一步说明。目前指令的动态分支预测技术较为成熟，在高性能计算机中，分支预测的成功概率在95%~98%之间，而且很难进一步提高。

3.4.2 数据预读

数据预读是指在处理器进行运算时，提前通知存储器系统将运算过程中需要的数据准备好，而当处理器需要这些数据时，可以直接从这些预读缓冲(通常指Cache)中获得这些数据。[Steven P. Vanderwiel and David J. Lilja] 总结了最近出现的各类数据预读机制，下文将以图3‑11为例进一步探讨这些数据预读机制。

图3‑11列举了三个实例说明数据预读的作用。其中实例a没有使用预读机制；实例b是一个采用预读机制的理想情况；而实例c是一个采用预读机制的次理想情况。我们假设处理器执行某个任务需要经历四个阶段，每个阶段都由处理器执行运算指令和存储指令组成。而处理器一次存储器访问需要5个时钟周期。其中每一个阶段的定义如下所示。

(1) 处理器执行4个时钟周期后需要访问存储器。

(2) 处理器执行6个时钟周期后需要访问存储器。

(3) 处理器执行8个时钟周期后需要访问存储器。

(4) 处理器执行4个时钟周期后完成。

实例a由于没有使用预读机制，因此在运算过程中需要使用存储器中的数据时，不可避免的出现Cache Miss。实例a执行上述任务的过程如下。

(1) 执行第一阶段任务的4个时钟周期，之后访问存储器，此时将发生Cache Miss。

(2) Cache Miss需要使用一个时钟周期[2]，然后在第5个时钟周期启动存储器读操作。

(3) 在第10个周期，处理器从存储器获得数据，继续执行第二阶段任务的6个时钟周期，之后访问存储器，此时也将发生Cache Miss。

(4) 处理器在第17~22时钟周期从存储器读取数据，并在第22个时钟周期，继续执行第三阶段任务的8个时钟周期，之后访问存储器，此时也将发生Cache Miss。

(5) 处理器在第31~36时钟周期从存储器读取数据，并在第36个时钟周期，继续执行第四阶段任务的4个时钟周期，完成整个任务的执行。

采用这种机制执行上述任务共需40个时钟周期。而使用预读机制，可以有效缩短整个执行过程，如图3‑11中的实例b所示。在实例b中在执行过程中，都会提前进行预读操作，虽然这些预读操作也会占用一个时钟周期，但是这些预读操作是值得的。合理使用这些数据预读，完成同样的任务CPU仅需要28个时钟周期，从而极大提高了程序的执行效率，其执行过程如下。

(1) 首先使用预读指令对即将使用的存储器进行预读[3]，然后执行第一阶段任务的4个时钟周期。当处理器进行存储器读时，数据已经准备好，处理器将在Cache中获得这个数据然后继续执行[4]。

(2) 处理器在执行第二阶段的任务时，先执行2个时钟周期之后进行预读操作，最后执行剩余的4个时钟周期。当处理器进行存储器读时，数据已经准备好，处理器将在Cache中获得这个数据然后继续执行。

(3) 处理器执行第三阶段的任务时，先执行4个时钟周期之后进行预读操作，最后执行剩余的4个时钟周期。当处理器进行存储器读时，数据已经准备好，处理器将在Cache中获得这个数据然后继续执行。

(4) 处理器执行第四阶段的任务，执行完4个时钟周期后，完成整个任务的执行。

当然这种情况是非常理想的，处理器在执行整个任务时，从始至终是连贯的，处理器执行和存储器访存完全并行，然而这种理想情况并不多见。

首先在一个任务的执行过程中，并不易确定最佳的预读时机；其次采用预读所获得数据并不一定能够被及时利用，因为在程序执行过程中可能会出现各种各样的分支选择，有时预读的数据并没有被及时使用。

在图3‑11所示的实例c中，预读机制没有完全发挥作用，所以处理器在执行任务时，Cache Miss时有发生，从而减低了整个任务的执行效率。即便这样，实例c也比完全没有使用预读的实例a的任务执行效率还是要高一些。在实例c中，执行完毕图3‑11中所示的任务共需要34个时钟周期。

但是在某些特殊情况下，采用预读机制有可能会降低效率。首先在一个较为复杂的应用中，很有可能预读的数据没有被充分利用，一个程序可能会按照不同的分支执行，而执行每一个分支所使用的数据并不相同。其次预读的数据即使是有效的，这些预读的数据也会污染整个Cache资源，在大规模并行任务的执行过程中，有可能引发Cache颠簸，从而极大地降低系统效率。

什么时候采用预读机制，关系到处理器系统结构的每一个环节，需要结合软硬件资源统筹考虑，并不能一概而论。处理器提供了必备的软件和硬件资源用以实现预读，而如何“合理”使用预读机制是系统程序员考虑的一个细节问题。数据预读可以使用软件预读或者硬件预读两种方式实现，下文将详细介绍这两种实现方式。