Elastic(灵活的) Instruction Fetching

摘要：
- 背景：
  - 分支预测（生成取值的地址）和指令缓存访问不应该紧密耦合，从而当指令取值阶段由于Icache发生miss或者back-pressure（不确定）而停止时，分支预测器可以提前运行并生成之后的取值地址。利用这些地址可以进行不同的优化，例如指令预取，并且可以隐藏跳转分支会产生的流水线空泡
  - 指令取值和分支预测解耦和的缺点：会增加流水线深度，导致流水线刷新的成本增加；需要更大的BTB保存分支的目标地址，并且如果BTB未命中，也会增加额外的流水线空泡
- 论文工作：
  - 提出了ELF（elastic fetching，灵活/弹性取值），一种混合的机制，能够解耦和分支预测和指令取值，并且最小化流水线刷新和BTB缺失而产生的额外的空泡
  - 提供了两种ELF的具有不同复杂度和性能的实现，性能相对于基准解耦和取值单元的设计提高了3.7%和5.2%
介绍：
- 在高频率的设计中，一个周期无法足够用于访问大的BTB和BP，处理BTB表项内容，映射BP预测结果到BTB表项和最终计算下一个PC的地址
- 解耦的BP在遇到I-cache未命中或者其它长延迟事件时，会将生成的取值地址放入一个解耦的队列中
- 解耦和BP和Fetcher的优点：
  - 提前执行BP和BTB得到的取值地址可以用于提供更加精确的指令预取器
  - 在某些实现中，由于高频率的设计，如果BP预测分支跳转，则需要在流水线中插入一个或者多个空泡（在BTB命中的情况下也需要），来计算得到分支跳转的目标地址。通过解耦和BP和fetcher，分支地址可以被提前计算得到，从而掩盖一些空泡
- 解耦和BP和Fetcher的缺点：
  - 需要一个更大的BTB结构，以获取预测跳转的分支的目标地址。如果使用解耦结构进行指令预取，此时BTB的覆盖范围需要比I-cache更大，即需要更大的BTB结构
  - 解耦会增加流水线深度（预测的时间更长了）。因此在解耦结构中，取值PC需要首先通过BP，然后在传递给I-cache。在耦合结构中，两者并行发生。这种情况下，分支预测错误代价也会增加
  - 流水线深度的增加也会发生在BTB发生缺失的关键路径上，这种情况下，在相关目标地址被译码/计算得到后，译码（或者之后的）阶段需要重新引导BP
- 论文工作：ELF（elastic fetching）
  - 在稳定的状态时，解耦和BP和指令取值（Decoupled mode）；在流水线刷新之后，重新耦合两者，以隐藏由于解耦和而增加的额外的延迟（Coupled mode）
  - L-ELF（limited elastic fetching）：硬件成本较低，IPC提升3.7%
  - U-ELF（unlimited elastic fetching）：硬件成本更高，IPC提升5.2%
解耦的取值设计
- 解耦的要求：BP能够在不访问I-cache的情况下跟踪（follow）发生跳转的分支。即需要一个BTB结构，能够提供分支跳转的目标地址
- BTB表项
  - 表项内容：参照AMD Zen处理器的设置，每个表项可以追踪最多16条顺序指令（以cache line位单位），其中两个是之前观察到发生了跳转的分支
  - 每个BTB可以保存两个分支，如果这两个分支在同一个64B对齐的cache line中，并且第一个分支是条件分支。如果第一个分支是非条件分支，意味着会直接跳转
  - 索引：当前fetch block的取值地址
  - 建立表项的时机：在指令提交之后建立BTB表项，从而限制了复杂性，因为BTB表项不会再被刷新
    - 当遇到非条件分支时
    - 当条件分支发生了3次跳转之后
    - 该表项跨域了16条顺序指令
- 前端操作（frontend operation）：Coupled，耦合的
  - 在论文中，假设使用了相对于L1更小的L0 I-cache，能够单周期取值
  - 在取值时，使用取值PC访问I-cache和预测器，获取N个指令字，并且对每个指令都进行分支预测
  - 对于被预测为跳转的分支，需要在decode阶段才能够译码得到分支目标地址，即会插入一个空泡，此时可以使用BTB或者Next line predictor消除
- 前端操作（frontend operation）：Decoupled，包括BP1，BP2，FAQ三个阶段
  - 每个周期，BP1阶段，使用当前分支预测的PC访问L0和L1 BTB，同时访问BP，以获取N个分支预测器（N是每个BTB表项最多可以追踪的条件分支的个数，论文中为2）。在访问结束之后，根据BTB的表项中的分支信息和分支预测信息，下一个BPred PC将可能是N个条件分支中的一个，或者是BTB表项中跟踪的间接分支目标，或者是BTB表项跟踪的非条件直接分支的目标，或者是失败的BTB表项（没找到）
  - 如果L0 BTB命中，通过使用TAGE的双模组件的预测，能够在同一个周期得到下一个BPred PC，否则，如果L0 BTB未命中，而L1 BTB命中，并且预测跳转，此时需要插入一个空泡，重新引导BP1阶段的预测。如果TAGE预测器中的其它带有tag的组件的预测结果和双模组件不同，则需要重新BP2阶段给出的预测结果，并且插入气泡
  - 在ARMv8中间接分支都是非条件的，并且利用BPred PC查询BTB也只会得到一个预测，因为这种分支会终止BTB表项
  - 论文实现了具有可变延迟的2级间接分支目标预测器，如果L0或者RAS命中，则需要增加一个空泡，但是如果未命中，则需要增加3个空泡
  - 如果BTB miss，对于直接非条件分支和预测为跳转的条件分支都需要等待到译码阶段才能够重新引导前端，对于间接分支需要等待实际的目标地址得到之后才能够重新引导
  - 相对于耦合的取值器，DCF（decoupled fetcher）在发生流水线刷新和BTB缺失时，需要额外的开销
- 耦合和解耦和的前端流水线的设计，每个阶段一个周期
- 耦合和解耦和中的时序逻辑（取决于BTB内容和指令类型）。绿色代表着分支和目标地址预测的推测地址，红色是等待预测或修正时丢弃的推测生成的顺序地址
ELF（elastic fetching）
- 乐观的思想：一旦流水线发生刷新时（BTB的miss被解决时），则可以知道正确的下一个PC。因此当DCF的取值引擎从BP1阶段开始启动时，立即使用这个地址探测Icache，从而缩短分支预测阶段，减少流水线刷新的损失
- 思想中的问题：这种做法意味着出现了两个不同步的取值地址生成引擎，因此必须提供一种机制能够在分支预测追赶上时，重新同步分支预测和fetcher
- 解决：论文为fetcher提出了两种模式
  - coupled模式：fetcher自己完成PC的生成，类似于耦合的fetcher。这种模式是一种暂态，即处理器只会处于该状态很短的一段时间。当流水线刷新或者是BTB未命中被解决时（decode阶段），处理器会进入该模式
  - decoupled模式：解耦的fetech和BTB完成PC的生成。这种模式是一种稳定的状态。当解耦fetcher追上耦合模式中的fetcher时，进入该模式
L-ELF的实现（limited ELF）
- 如果处理耦合模式，取值器只会顺序取值，一旦需要做出控制流决定，取值器就会停止。（在非条件直接分支之后的指令并不存在控制相关）。最简单的实现，不需要分支预测
- 重新同步DCF和fetcher：在实际中，耦合模式下取到的指令保证是DCF最终生成的FAQ块的子集，因此fetcher需要记录耦合模式下获取的指令数，并且和FAQ中生成的地址数进行比较。
- 每次当FAQ块可用时，fetcher需要将当前记录的取值的指令数和如果在解耦模式中本已经取的数量加上FAQ的大小，此时会出现三种情况：
  - 两者数量相同：即fetcher已经将所有FAQ块的指令取到，该块已经可以被pop。解耦模式可以从下一个FAQ块开始，或者继续执行耦合模式直到下一种情况的2.b或者第三种情况满足
  - 耦合模式的数量更多：可能是以下两种情况
    
    a) DCF尚未追赶上fetcher，因此没有转换
    
    b) 由于每周期盲目的获取fetchwidth的指令，fetcher越过了控制流决策并且取了其它的指令（the fetcher overshot and fetched past a control-flow decision）。通过嵌入在每个FAQ块中的终止条件，可以很容易地检测到这种情况下，即如果终止原因是跳转分支而不是顺序到下一块，则耦合模式的数量不能大于L-ELF中的解耦模式的数量。在这种情况下，耦合模式可以在下一个FAQ块开始执行，同时译码阶段必须强制扔掉overshot的指令
  - 耦合模式的数量少于解耦模式的数量，即DCF已经追赶上fetcher，并且/或者fetcher遇到了控制流决策，并且停顿了。此时需要调整新生成的FAQ块中的数量，并且从修改之后的FAQ开始执行解耦模式（因为当前取值的指令少于解耦模式应该取到的指令数，因此需要调整解耦模式的取值数）
- 如果当前处于耦合模式，则每个周期如果有一个FAQ块需要处理，则fetcher都会试图切换到解耦模式
  - 当I-cache开始访问时，耦合模式的计数器都会推测取到了fetchwidth的指令，然后和解耦计数器进行比较（已经通过FAQ表项中包含的计数器进行了调整）
  - 目的：能够使得解耦模式从下周期开始执行，并且此周期仍旧可以取值（尽早的确定是否可以切换）
- 在这种实现中，如果fetcher能够取到足够多的顺序指令，而没有遇到条件/间接分支，则L-ELF可以隐藏部分或者全部的DCF在流水线flush或者BTB miss时产生的额外的延迟
U-ELF实现
- BP的基础结构：
  - 在简单实现中的耦合模式中，因为直觉上认为这种模式的时间很短，因此为了减少开销，没有使用分支预测。在不考虑开销的情况下，可以实现针对一些在译码阶段无法预测的分支的预测器，用于停止耦合模式下的取值
  - 论文考虑了四种预测器：RET-ELF（32表项的RAS，只用于预测返回指令）；IND-ELF（64表项，直接映射的分支目标缓存，用于预测所有间接分支除了返回指令）；COND-ELF（2K表项，3位计数器，双模预测器，预测条件分支）；U-ELF（以上所有）
- 分歧（divergence）：耦合和解耦和模式使用了不同的控制流推测策略意味着会导致不同的执行路径，此时硬件必须能够监视两个控制流，以便以后的恢复。论文使用bitvectors和target queues进行监视
- bitvectors：在fetcher中实现两个长度有限的位向量，分别用于跟踪耦合模式的指令流和解耦和模式
  - 位向量的表项内容：3位，taken，branch，valid。taken=0，代表着非跳转分支和非分支指令，taken=1，代表跳转的分支指令。branch位对所有的分支指令设置。valid位用于防止未分配的表项造成错误匹配（使用）
  - 位向量不使用循环缓冲的形式管理（过于复杂），并且每个表项在另一个位向量中都有对应的兄弟表项，可以直接比较
  - 位向量只在耦合模式下填充
  - 第一个位向量在译码阶段之后填充，用于跟踪译码的指令；第二个位向量跟踪会在解耦模式下被取的指令，并且当FAQ表项可用时，在Fetch阶段填充
  - 每个周期位向量之间会进行比较，如果两个兄弟表项不一样，则代表着分歧。在这种情况下，必须决定信任哪一个模式的控制流决策，并且flush另一个的控制流
- 利用位向量进行控制流选择：DCF的BP更复杂，应该更可信，但是在以下情况下中，必须应该耦合模式
  - 在BTB未命中时，BTB表项跟踪的指令块中包含的任何无条件分支将不会在BTB中具有目标地址，此时DCF将会继续按序取值。但是fetcher将会在decode阶段检测到该非条件分支，此时之后的控制流将会产生分歧，但是fetcher应该是对的
  - 在自修改的代码中，可能会出现两种模式下，branch位不同，即耦合模式中为0，解耦为1，此时应该选择fetcher的路径
- Target queues：
  - 位向量无法检测的情况下：间接分支在fetcher和DCF中预测的结果不同。此时如果模式切换将可能产生错误
  - 为了检测这种情况下，在直接和间接分支发生跳转时（DCF在fetch阶段，fetched在译码阶段），需要将目标地址压入分别对应的target队列中。在每周期的位向量比较时，也需要同时比较两个队列中的内容，以检测上述的分歧
  - 普通情况下遇到分歧点，相对于Fetcher，更愿意相信DCF的结果，此时会flush耦合模式中的取值。但是如果出现了：在发生跳转的直接分支时，fetcher获取到了译码的目标，并且是正确的，且和DCF不同。这种情况下，DCF需要flush，并且继续在耦合模式下取值
  - 为了减少由于上述情况，带来的DCF刷新，需要在target Queue中保存分支的类型：如果分歧发生在间接分支，选择DCF；如果分歧发生在直接分支（条件/非条件），选择fetcher
- 重新同步DCF和fetcher
  - 由于U-ELF允许推测跨越控制相关，因此精确的耦合模式下的指令数只能够在指令译码并且分支识别之后才能够得到，即只有DCF追赶上指令译码之后，再开始使用FAQ信息，此时在切换之后会增加fetch-to-decode延迟的空泡
  - 为了避免增加的空泡，使用两个指令计数器：decode coupled count, fetch coupled count。前者是精确非推测的，用于验证切换是否正确。即仍旧使用L-ELF中的方式判断切换，但是需要使用译码的计数器判断是否切换正确
  - 注意：在切换到解耦模式后，仍旧需要跟踪少量的在耦合模式下取到的但是没有译码的指令。即位向量和目标队列在切换之后不能够重设，直到所有的耦合模式下的指令都已经译码之后
实验
- 测试程序：
  - spec2k6+spec2k17
  - server1：基于事务处理的服务器工作负载，指令占用很大
  - server2：计算密集型内核，用于测试分支预测和data-side memory
- 模拟器：工业级，内部的时钟级模拟器

Elastic(灵活的) Instruction Fetching

Elastic(灵活的) Instruction Fetching

相关推荐