您的位置: 首页  >  文章  >  Two Level Bulk Preload Branch Prediction

Two Level Bulk Preload Branch Prediction

分类: 文章 • 2022-11-07 23:20:19

Two Level Bulk Preload Branch Prediction

  1. 摘要（IBM systems and technology group）

    • 论文介绍了在IBM的5.5GHz的在zEnterprise EC12处理器（大端机器）中使用的大容量的层级结构的分支预测器。并且通过在仿真模型和zEC12的真实硬件上实验，发现这种预测器比单层更小的预测器更好
    • 论文提出了两级分支预测的一种新结构和算法，在BP检测到第一级感知缺失（perceived miss），会将多个分支的预测信息从第二级批量转移到第一级，即第二级不会直接用于分支预测器
    • 当BP的第二层不太可能产生效果时，将会限制对第二层的访问。访问第二级时，会按照每个顺序系统的搜索第二级，以尽早的提供结果
    • 结果：在仿真模型中，最大的核心性能提升为13.8%，在实际zEC12硬件上的结果，两种工作负载，系统性能分别提高了3.4%和5.3%

  2. 介绍：

    • 对于非常大的工作负载，它们的性能会受限于BP的容量而不是BP的预测算法的准确率，而论文提出的就是结果容量问题的方案
    • 真实实践中，访问实践，硅面积和功耗能限制了BP使用更大的结构。而论文提出的二级BP能够提供非常大的容量，并且对延迟和功耗的硬件非常小。该结构是一个半独占（semi-exclusive）的二级结构，其中大的第二级预测器用于反向填充容量较小和较低延迟的第一级预测器。第二级只会在第一级发生内容缺失时才会加电和访问

  3. 论文提出的预测器结构
    Two Level Bulk Preload Branch Prediction

    • BTB1：第一级BTB，带有标签的缓存结构，用于保存分支预测的信息，使用分支指令的地址作为索引和标签。对于每一个BTB1中的表项包括一个两位的饱和计数器和目标跳转地址。BTB1共4K的表项，使用四路组相连的结构，利用SRAM实现，指令地址中的49：58位作为BTB1的索引
    • BTBP：BTB预加载表（preload），每个表项包含和BTB1同样的信息，并且BTB1和BTBP会被并行访问以做出预测。（BTBP和BTB1，以及一些额外的结构被认为时第一级分支预测器）。BTBP包含768条分支，6路组相连，使用指令地址的52：58位进行索引。BTBP利用寄存堆实现，并且具有多个写端口，因为会有多个来源同时写入。当分支预测最终由BTBP决定时，BTBP中相应的内容会被移动到BTB1，此时从BTB1中替换出来的表项将会写入BTBP和BTB2
    • 意外的分支（surprise）：没有在第一级分支预测器中被预测（命中）。这种分支是否跳转将会由一个无标签的一位BHT表进行预测（32K表项）
    • BTB2：包含着和BTB1和BTBP相同的信息。当发生意外分支需要插入到分支预测器时或者是在BTBP转移到BTB1时，从BTB1替换出表项时，需要写入BTB2。BTB2包含24K条表项，6路组相连，使用SRAM实现，利用指令地址的47：58位索引
    • 辅助结构：PHT和CTB（changing target buffer）处于第一级分支预测器，用于解决那些具有多个跳转方向和地址的分支。这两个结构使用到达当前分支的路径进行索引，并且使用分支地址作为标签。BTB1和BTBP中包含着指示当前预测是否采用PHT/CTB的信息
      • PHT包含4096个表项，使用前12条预测的分支结果和前六个发生跳转的分支地址作为索引
      • CTB包含2048个表项，使用前12条发生跳转的分支地址作为索引

  4. 分支预测的搜索过程（异步前瞻分支预测器）

    • 当流水线前端处于restart条件时，例如分支预测错误之后
      • 取值和分支预测都从同一个指令地址开始
      • 取值正常顺序取值，同时预测器逻辑从该地址开始搜索第一条分支指令
      • 当在第一级分支预测器中发现一条分支指令时，预测是否跳转，如果预测跳转，则给出目标地址，并且将预测器的起始地址重定向到该目标地址；如果预测不跳转，则继续寻找下一个分支
      • 分支的预测结果将会发送给取值和译码逻辑，然后用于重定向取值
      • 分支预测器给出的一些预测信息需要保存到对应的分支提交/完成（completion）之后，然后更新分支预测器。在更新发生之前，将使用推测的BHT和PHT更新结果将会被用于预测
    • 异步前瞻预测的好处：能够高效的引导指令取值，最小化目标重定向的开销，同时通过提前预取必要的指令能够减少I-cache缺失的次数
    • 遇到循环的情况（单个分支组成的循环）：增加64条分支的快速索引表（Fast index table，FIT），加速BTB1中的64个分支子集的分支预测

  5. 最大化BTB1和BTB2之间的互斥性/排他性（exclusivity）

    • 理论设计中希望BTB1和BTB2是完全互斥的，以最大化不同表现的个数。但是在实际中，BTB1和BTB2之间总会存在潜在的重复，因此这种设计也称为“semi-exclusive”（半互斥）。
    • 为了实现理想的互斥性，需要的代价太大。理想的互斥，需要在BTB2的表项写入BTB1时，将BTB2中的表项被替换或者清除掉。当BTB2中发生hit，此时命中的表项将会被发送到BTB1，同时BTB1中被替换的表项将会写回BTB2。如果这两个表项在BTB2中的同一个位置，则只需要1次写入，否则需要两次写入（无效命中的表项，写入替换的表项）。如果增加BTBP，则为了保证互斥性，将会更加复杂
    • semi-exclusive：当BTB2的表项要被复制到BTBP时，BTB2中的表项将成为LRU（最近最少使用的表项）。当BTBP写入BTB1时，BTB1中被替换的表项写入BTB2中LRU的表项，同时变成MRU（最近使用的表项）。BTB2中的LRU表项很有可能被之后的BTB1命中或者意外分支表项插入，此时也可以避免完美互斥所需要的额外的写入

  6. 第一层分支预测器的分支缺失（miss）

    • 在异步前瞻分支预测器中，如果在预定义的搜索次数内没有在BTB1和BTBP中发现任何预测，则认为一级BP发生了缺失行为。这种确定一级BP miss是一种推测性行为，因为没有找到预测有可能是由于搜索的范围内确实没有分支
    • 另一种定义：在流水线的译码阶段遇到了分支指令，但是该分支没有在第一级BP中获取预测，则定义为BTB1缺失（需要是基于操作码和指令内容猜测会发生跳转的分支）。这种定义中，缺失行为会发生在流水线中从译码到完成中的任意阶段。当预测BTB1发生缺失越早，预测的推测性越大；当预测BTB1发生缺失越晚，预测的推测性越小

  7. 基于I-cache的缺失过滤BTB2的传输转移

    • 由于BTB1 miss的判断带有一定的推测性，因此如果可以过滤掉其中一些不是由于一级BTB容量而引起的缺失行为将能够获得一定的好处（减少更新操作）
    • 论文的方法：判断检测到的BTB1 miss是否会有一个相应的I-cache miss。如果有，认为该BTB1 miss更可能是由于BTB1的容量大小造成的缺失行为（应该是指的分支指令是否在I-cache中命中/缺失）
    • 如果判断当前BTB1 miss不太可能是由于容量而造成的，则可以被阻止访问BTB2或者限制为仅搜索BTB2的一部分

  8. BTB2的搜索过程

    • 论文利用3个BTB2的搜索跟踪器（tracker）来记录BTB1 miss和I-cache miss的信息，并且用于启动对BTB2的读访问，每个tracker只负责4KB的地址范围（即指令地址的52：63位，大端）
    • 每个tracker包含的信息
      • 块指令地址（0：51）
      • BTB1缺失的有效性（是否发生BTB1的缺失）
      • I-cache缺失的有效性
      • 用于跟踪的块中128个32B的BTB2行的优先级和搜索状态信息
    • Tracker当发生BTB1缺失和I-cache缺失时启动。首先和之前的trackers，比较新发生的缺失行为。例如对于一个BTB1缺失，如果发现已经存在于一个tracker则被忽略，如果发现和一个tracker相匹配但是只记录了一个有效的I-cache缺失行为，则设置该tracker的BTB1 miss有效位。如果未发现有效的匹配则试图启动一个新的tracker
    • 论文使用一个8表项的队列记录BTB1发生的缺失行为和一个分开的4表项队列记录最近已经完成的BTB2搜索行为。当新发生的BTB1缺失行为和两个队列发生了配置，则会被忽略
    • 启动新tracker：利用一个已经完成的无效tracker；如果没有替换一个只记录了有效的I-cache缺失信息而没有BTB1缺失信息的tracker；如果仍旧没有，则忽略
    • 完全搜索BTB2：如果一个tracker中包括了I-cache和BTB1的有效缺失行为，则启动读取BTB2的一个4KB块中的128个行（表项），所有标签相匹配的预测信息称为BTB2命中，并且会被写入BTBP。读取的顺序取决于优先级逻辑
    • 部分搜索BTB2：如果一个tracker只包括了BTB1的有效缺失行为，则启动部分搜索，即只会搜索其中的128B。如果搜索完成时，I-cache缺失位仍旧处于无效状态，则该tracker处于完成状态，即无效

  9. BTB2的搜索指导/转向（steering）

    • 从BTB2传输内容时，会搜索一个4KB的顺序寻址空间块，从中找到匹配的表项传递到BTBP。但是这种将4KB地址内的所有分支都传递的方式并不是最有效的
    • 解释：在4KB的代码中，可能会存在多个分支，但是这些分支并不是顺序的（执行顺序），因此应该尽可能的传输那些最先被使用的部分
    • 解决：论文增加一个顺序表（ordering table）来追踪分支的返回顺序
      • 512个表项，2路组相连，每个表项代表4KB块。跟踪的单位为扇区（sector），128B。每个4KB块被分为32个扇区，4等份（quartile）。每等份使用8的1位的扇区标记和三个标记用于指示和其它三个等份的引用。
      • 当执行时遇到一个不同的4KB代码块，刚进入的代码属于的那一等份被定义为需求等份块，当进入另一个等份时，需求等份会记录一个标记代表该进入了哪一个等份。在执行过程中，任意一个扇区被执行都会将相应的bit设置为1。当代码进入下一个4KB块，则重新记录
      • BTB2和顺序表会被并行访问，如果顺序表命中，则表项内容用于指示BTB2的搜索顺序。首先搜索需求等份中被标记为1的扇区，然后搜索需求等份指示的下一个等份中的扇区，最后搜索剩下的被标记为1的扇区。如果没命中，则从需求等份顺序搜索

  10. 实验

    • zEnterprise EC12的芯片配置
      Two Level Bulk Preload Branch Prediction

  11. 结果

    • BTB2的配置：24K个表项（4K*6路）。大的BTB1配置：24K，六路，低延迟（假设情况，不可能存在）
      Two Level Bulk Preload Branch Prediction
    • BTB2的大小对性能的提升
      Two Level Bulk Preload Branch Prediction

相关推荐