本文转载自：FPGA的现今未微信公众号
在前面的文章中，介绍了FPGA的设计中cache的作用和使用场景，本文重点介绍下cache在FPGA中的实现方案。实现一个cache，究竟要满足哪些最最基本的需求呢？或者说要做一个什么样的cache才能满足提升外部缓存访问效率的目标呢？
基本需求
1、支持查询，返回查询结果（命中或者不命中）；
2、支持cache回写；
3、支持cache内容老化更新；
4、支持cache的深度可配置（深度越大，资源消耗也越多）；
实现原理
我们知道，FPGA中cache的基本功能是对其输入一个key，cache输出该key对应的内容。整个cache的结构主要分成2个部分，一个是cache line，一个content。如下图所示。
cache line：实现对输入的key值的比较，确认key值是否命中，cache line的功能相对比较简单，一般直接用寄存器实现，存放的就是key。当输入一个key时，输入的key和cache line中存放的key值同时比较。其中cache的深度就是cache line中存放key的个数。
content：存放的就是该key对应的数据结构，通常用一个ram来实现。每一个cache line和ram的地址一一对应。如果key命中，就会从对应的content中读出数据返回给用户。
方案设计
整个cache的逻辑设计方案如下图所示。主要分为查询逻辑、读逻辑、更新逻辑和RAM。
1、查询
查询就是cache line，主要是对输入的key进行比较，确认是否命中，如果命中，需要把从ram中读出的信息反馈给用户；如果不命中，则返回为命中。
查询还有一个功能，就是当cache被命中后，如果key值对应的内容被修改后，需要回写cache。
2、读逻辑
这部分比较简单，就是当cache line被命中后，根据命中的结果读取RAM中对应的内容。
3、写逻辑
写逻辑主要完成2个功能，一个是命中后cache的回写，这部分比较简单。第二个功能就是如果不命中，则需要从DDR中读出其内容，然后也写回到cache中，如果cache中还有空间，则写入即可，如果cache中已经没有空间，则需要将cache中的某一个cache line老化，写逻辑要时时计算出需要老化的cache line，当有新的内容需要写入cache的时候，就替换需要老化的cache line，被老化的cache line的内容，要写回到DDR中。
这里重点介绍下老化的方法。老化最常用的算法是LRU（Least recently used，最近最少使用）算法。简单理解就是cache line中被命中的就是经常使用的，我们期待的也是一个高命中的cache，所以相反，经常不命中的，也就没有留在cache中的必要。那在逻辑里如何实现呢？
计数器法
这种方法就是给每个cache line分配一个计数器。当某个cahce line被命中后，其对应的计数器就清零，而没有被命中的cache line对应的计数器就加1。当需要替换的时候，直接替换掉计数器的值为最大值对应的cache line即可。
移位法
为每个cache line进行编号，假如cache的深度为8，则将它们分别编号为cache line0到cache line7，也就是为每个cache line分配一个固定的编号。将编号组成一个队列，如下图所示：
当某个cache line被命中中，对应对的编号就提到队列的头，比如cache line5被命中后，5这个编码就提到队列的头部，原来对头到5之间的编码右移一个位置，编码5之后的编码位置保持不变。经过不断地移位后，在需要替换的时候，永远替换在队列尾的编码所对应的cache line。
其他
上述老化的方案都是常见的“标准”方案，当然还有一些非标准方案。以cache的深度等于8为例，当cache还没有满的时候，如果不命中，则逐个cache line填充。当cache line全部填充满了以后，如果需要替换，不是像上面一样替换某一个cache line，而是先把cache中的内容全部写入DDR中，然后再将新的内容填充。
4、RAM
一个简单双口RAM，深度为cache line的个数，宽度取决于用户需要缓存数据的内容。这部分逻辑相对比较简单，只需要进行ram的读写即可。
总结
FPGA中cache的设计难点在cache的更新，如下图所示。需要说明的是，FPGA中的cache效果如何，和具体的应用场景是强相关的，需要case by case的分析，寻找性价比最好的方案。
