如何处理cache miss问题以提高加速器效率呢？

引言
带宽是影响fpga加速器的重要因素，因为大量的并行计算对数据量要求很大。如果加速器对数据的访问是不规则的，那么cache miss就会大大影响加速器性能。这篇来自fpga2019会议的报告，向我们展示了如何来更好的处理cache miss问题，提高对缓存的利用率以及提高加速器效率。
01
cache miss的问题
假设ddr可以提供12.8gb/s的带宽，fpga上的并行加速器的数据输入带宽为0.8gb/s，可以并列16个这种加速器。这些加速器通过arbiter来直接访问ddr。如果它们访问的数据是连续规则的，那么ddr的带宽可以被充分利用。但是这些加速器需要的数据在ddr中并不是规则排列的，如图1.1。这样就会造成频繁的访问ddr，这样ddr的带宽就不够用，造成的结果就是加速器会受到延迟，效率无法得到提升。就如同图1.1所示，实际上有效利用的ddr带宽只有0.8gb/s。
图1.1 不规则数据需要造成频繁访问ddr
一种解决问题的方法是使用blocking cache，将还没有用到的数据缓存起来以便之后使用。然而这样存在两个问题：一个是如果缓存中没有需要的数据，那么就需要从ddr中获取数据，这就会有很大延迟，因为对ddr的数据进行随机访问是非常耗时的；另一个是缓存的使用效率很低，内部大部分数据都不能被及时消耗，以便等待被利用到。
图1.2 blocking cache的使用
另外一种解决的办法是non-blocking cache，这正是本文提出的方法。这种方法的关键是加速器可以允许一定数量的cache miss。cache miss不会阻塞对后面数据的获取。这就要求前后的数据没有依赖关系，而且允许的cache miss数量足够多，能够允许在这些时间可以从ddr中获取miss的数据，否则一样会造成加速器等待喂数。
图1.3 non-blocking cache
02
传统的non-blocking cache结构
图2.1是一个基本的non-blocking cache结构，它主要由cache array以及mshr组成。cache array中含有tag和数据，tag用来表示加速器请求的数据的在外存中的地址。通过tag可以判定请求的数据在cache中是否存在。mshr首先被kroft使用，它含有数据未被命中需要去外存获取的具体信息：包括外存地址，用于判定加速器是否会再次命中相同的数据。还有cache的地址，用于决定从外存获取的数据存储到cache的位置，给哪个加速器使用。还有输入请求确认标志，表示这个缺失的数据是否从外存读取到。
基本操作是：当加速器第一次从cache中获取数据没有命中，那么就在mshr中记录下相应的信息和状态，当第二次相同数据miss发生，除了在mshr中记录信息外，则启动从外部存储器获取数据，并更新到cache中。取回来的数据会根据mshr中的信息将需要的数据发送给加速器。所以一个包含n个表项的mshr有n个比较器用于比较数据地址，是否属于同一个miss的数据等。使用non-blocking cache能够提高运算效率，减少等待时间，提高带宽利用率。但是这种传统的mshr消耗很多逻辑资源，不利于规模扩展。
图2.1 non-blocking cache的基本结构和操作
图2.2 更新cache
图2.3 mshr逻辑结构
03
对non-blocking cache的改进
为了能够有效扩展mshr，可以使用多个mshr，每个mshr有n个表项，这样相比于使用一个mshr能节省逻辑资源。但是这涉及到一个问题，如果一个配置mshr的请求在多个mshr表都有冲突，那么就造成配置mshr表的等待。这样就导致了加速器运算的等待，不能够执行下一条指令。
图3.1 两个mshr被请求表项都被占用
解决办法就是cuckoo hashing算法。假设有两个mshr表，t1和t2。每个r个表项。每个元素通过函数h1和h2来确定表项位置，即：t1[h1(x)]，t2[h2(x)]。为了插入表项内容x，检查t1对应位置是否空，如果空，就插入。如果非空就检查t2，如果t2也非空，这就是冲突的情况，那么就插入到t2中，将原来的内容z替换。然后z再去查询t1表，如此循环进行。这样就不会造成阻塞。
图3.2 cuckoo hashing
还有一个问题是，mshr中的表项subentries大小是固定的，如果要扩展表项的subentries，那么所有的内容都是同等扩展，这样可能有一些内容并不需要那么大。所以为了能够有效利用存储资源，论文作者提出了动态可扩展subentries内容的方法。将tag和subentries分隔开分别存储，这样如果有更多加速器miss相同的数据，那么就可以在一个subentries表后再扩展需要的subentries。这样就是在需要级联的subentries中增加指针来级联到下一个subentries表。
图3.3 可扩展subentries
图3.4 表项扩展
图3.5 整体结构
结论
本文主要总结了non-blocking cache的设计框架，以及在fpga上如何使用。介绍比较简略，更详细的资料还需要了解cpu体系中non-blocking cache的具体结构。