本以为cache的设计并不复杂，但实际设计过程中，我遇到了不少问题，哪怕稍微考虑一下性能问题，cache的设计的复杂度就会提高很多。cache的复杂与cpu指令解码级的复杂不同，CPU指令解码级的信号较多，但这些信号之间并没有太多的关联，更多的是一种纵向的逻辑关系，一条指令对应一种信号组合，因此在设计和分析过程中并没有太多复杂问题。但cache中的信号的逻辑关系更复杂，更难理清，因此我花费了大量的精力去设计。我引入cache的本意并不是单纯为了性能，最主要的原因是cpu内部采用类似哈弗架构，需要分离的指令和数据存储，引入cache可以在CPU视角构成分离的指令和数据存储。但人的野心总是越来越大，当你了解了简单的cache如何设计之后，总是想能不能再一次提高性能，哪怕提高一点点。于是我原本计划的直接映像的cache就变成了现在设计的2路组相联cache。Cache的设计是目前我在整个系统设计过程中遇到的最有挑战性的工作。
Cache 设计时遇到的问题
Altera片上存储接口上隐含的寄存器
我在cache设计中遇到的问题之一是关于FPGA片上资源的问题，Altera片上存储中几条输入的地址线和数据线都是必须registered的，这就意味着如果使用片上的存储实现cache，IF级PC寄存器实际上应该隐含在I-cache模块内部，EXE和MEM级的流水线寄存器中包含内存地址、数据和控制的部分也应该隐含在D-cache的内部，这实际上给模块化设计带来了困难。（Quartus II Handbook Version 9.1 Volume 1: Design and Synthesis, Chapter 6: Recommended HDL Coding Styles, Inferring Memory Function from HDL Code）如果在cpu设计的过程中忽略这隐含的寄存器，会额外引入至少一个周期的时延。但cache的设计目标是要求在命中的情况下，必须在一个周期给出数据和指令，所以隐含的寄存器必须加入考虑。
Cache的一致性问题
另外Altera的片上存储不支持清零（Quartus II Handbook Version 9.1 Volume 1: Design and Synthesis, Chapter 6: Recommended HDL Coding Styles, Inferring Memory Function from HDL Code），这给实现cache清零指令带来了困难：如果使用片上存储来实现cache，不能清零使得实现cache清零指令有困难，而如果没有cache清零指令，缓存同步的问题就需要完全由硬件解决。这又让我思考是否引入总线监听（bus snooping）。有人认为我这样一个单核心单级cache的系统不需要考虑cache一致性的问题，实际上这样的想法不完全正确。考虑这两种情况：一是自修改代码（Self-Modifying code）问题，设想有一操作系统在系统上运行，将某个程序指令从硬盘加载到内存，执行一系列LW操作。操作系统从硬盘读取一串指令，放入内存的某一位置，恰好覆盖了之前内存中的指令。此时若I-cache已经缓存过这一区域，I-cache根本不知道LW指令已经修改了这部分内存数据，这就会引起cache一致性的问题。当CPU跳转到这个区域，I-cache认为命中，实际执行的是旧指令而不是我们通过LW载入的新指令。二是DMA问题，当总线上有DMA请求发生时，DMA设备直接修改某些区域的内存，而Cache并不知道，这同样会引起缓存一致性问题。
对于DMA
第二种情况，MIPS处理器采取一种简单粗暴的办法来解决，就是在内存地址空间中单独划出来一部分不被cache索引，每当处理器试图获取这个地址范围内的数据或指令时，都绕过cache，从内存上请求。但是第一种情况要麻烦一些，因为操作系统要频繁的将程序的指令写入内存，我们不能总是把能自我修改的指令部分放入这个绕过cache的地址空间内，这样的话大部分程序都得不到cache的速度优势，还不如不引入cache。
自修改代码 （Self-Modifying Code）
如何搞定这第二种情况？是直接在硬件上提供缓存一致性的支持？还是加入一些缓存同步指令在必要的时候由系统软件编写者对cache进行管理，如在操作系统加载新进程的时候手动清空I-cache？我参考了一些资料。
显然不同平台对自修改代码带来的缓存不一致问题的处理方式不同。
X86平台的cache一致性机制比较复杂，从某种意义上讲，只要使用者正常使用处理器，cache对程序员完全透明。
osdev上有人讨论这一点：
Everything (including DMA) on 80x86 is cache coherent; except for the following cases >(where you have deliberately “weakened” cache coherency for performance reasons or broken cache coherency):
- You’re using the “write-combining” caching type in the MTRRs and/or PAT. In this case writes that are sitting in a CPU’s write-combining buffer won’t be seen by other hardware.
- You’re using non-temporal stores. In this case writes that are sitting in a CPU’s write-combining buffer won’t be seen by other hardware.
- You’ve seriously messed things up (e.g. used the “INVD” instruction at CPL=0).
All hardware trickery (e.g. eDRAM caches, etc) is designed to uphold this.
在看minix代码的时候我就意识到了这一点。我看完整个启动器的代码，里面配合BIOS中断进行了大量DMA操作，从磁盘读取数据到内存，从来没有在代码上下文中出现管理cache的指令。自修改代码在Bootloader中也是随处可见，第一处就出现在master boot record的开头，将BIOS从MBR磁盘第一扇区的主启动记录（Master boot record）512字节的代码通过BIOS中断拷贝到内存后，这段代码将自身复制到其他的区域，并跳转到这里。这事很典型的自修改代码。
1 | ! Code from minix 3.1 master boot record: masterboot.s (line 46-53). |
可以清楚的看到，在编写X86汇编程序的时候，程序员不需要考虑这段代码是自修改代码而引起的缓存问题。可是事实上，在rep movs执行时，后续的指令已经加载进入流水线了。显然流水线中的旧指令需要被废弃。
查看X86系统编程手册（Intel software developer’s manual Volume 3A: System Programming Guide 11-18） 11.6 Self-Modifying Code , 可以看到从奔腾四开始，x86处理器已经在流水线和cache硬件上做了一致性机制，只要是使用同一物理地址访问的内存，硬件提供一致性支持。X86不仅在cache中实现了写请求监听，而且还在流水线中废弃已经预取的指令。
11.6 Self-Modifying Code
A write to a memory location in a code segment that is currently cached in the processor causes the associated cache line (or lines) to be invalidated. This check is based on the physical address of the instruction. In addition, the P6 family and Pentium processors check whether a write to a code segment may modify an instruction that has been prefetched for execution. If the write affects a prefetched instruction, the prefetch queue is invalidated. This latter check is based on the linear address of the instruction. For the Pentium 4 and Intel Xeon processors, a write or a snoop of an instruction in a code segment, where the target instruction is already decoded and resident in the trace cache, invalidates the entire trace cache. The latter behavior means that programs that self-modify code can cause severe degradation of performance when run on the Pentium 4 and Intel Xeon processors.
In practice, the check on linear addresses should not create compatibility problems among IA-32 processors. Appli- cations that include self-modifying code use the same linear address for modifying and fetching the instruction. Systems software, such as a debugger, that might possibly modify an instruction using a different linear address than that used to fetch the instruction, will execute a serializing operation, such as a CPUID instruction, before the modified instruction is executed, which will automatically resynchronize the instruction cache and prefetch queue. (See Section 8.1.3, “Handling Self- and Cross-Modifying Code,” for more information about the use of self-modifying code.)
各个平台对自修改代码的支持不同。
这篇博客对路由器中广泛使用的MIPS处理器进行了测试，发现其并没有实现自修改代码的缓存同步机制。由Stackoverflow上的讨论,PowerPC也没有实现这个机制，要求系统软件设计者从软件层面维护缓存的一致性。
3.3.1.2.1 Self-Modifying Code
When a processor modifies any memory location that can contain an instruction, software must ensure that the instruction cache is made consistent with data memory and that the modifications are made visible to the instruction fetching mechanism. This must be done even if the cache is disabled or if the page is marked caching-inhibited.
我打算如何对自修改代码的缓存进行处理？
如果不增加总线监听、流水线回退等机制，只引入清空cache的指令，那就需要系统程序员对自修改代码加以限制，如限定在关中断的情况下修改代码，并在修改代码后引入若干空指令填充流水线，然后使用指令cache清零指令清零cache。这样做降低了硬件设计的难度，但对所有的自修改代码无论其是否在缓存中都需要用控制令填充流水线、清空cache，带来了额外的性能开销。
总线监听实现起来不复杂，但是由于cache变化引起的流水线回退机制和中断的相互作用分析起来有点复杂。是否增加流水线回退机制，取决于能否联合中断，分析清楚处理器的工作状态。当然引入这个cache一致性机制会带来一些额外的好处，比如可以拓展DMA的地址空间，只把单纯的IO放在不经过cache的地址空间即可。
但是，当总线监听、中断、异常和流水线结合起来后，事情变得有点复杂。解决方案是要综合分析自修改代码引起的流水线和cache变化以及其他的一场和中断的组合，设计电路。
精确中断有两种实现方法，一是无论什么时刻中断发生，cpu立刻暂停当前工作，进入终端流程。这个要求较高，需要分析中断发生时ID级的三种情况:
- ID级是转移指令–中断保存跳转指令的地址，中断返回重新执行
- ID级是处在延时槽中的指令–中断保存当前PC，让延时槽中的指令执行完，当前PC就是之前的跳转计算出的地址。
- 其他情况–中断保存当前PC，与上一种情况类似。
之所以需要考虑这些情况，是因为中断响应过程处理器取指的地址发生变化，而是否是转移指令、是否处在延时槽中对于CPU下一周期取指的地址有影响。
也可以选择等到CPU处在较为稳定的状态时在响应中断。上面可以看到，若发生中断时ID级是转移指令，则流水线中要取消两条指令，待中断返回后再次重新执行。这样做实际上造成了额外的性能开销，我更倾向于等待CPU进入稳定状态时响应中断请求，在ID级是转移指令或延时槽时不响应中断请求。这样做需要在中断控制器中增加一个中断响应机制，在收到响应后应立刻撤销中断请求。
异常的情况要比中断复杂，因为异常往往需要立即处理。一个复杂的CPU应当可以处理多种异常，例如保护模式引入的异常，在取指、读取、存储数据时都可能发生的超过范围，算数运算溢出，指令未实现、syscall指令、还有分页模式引入的异常如tlb缺失，缺页等。目前我尚未打算在我的CPU中实现保护模式和分页，因此目前支持的异常时算数运算溢出、指令未实现和syscall指令。第一个异常是发生在EXE级，后两个是发生在ID级。这三个异常EXE级的异常优先级最高，因为其发生在流水线内较深的位置，而异常处理往往需要重新执行造成异常的指令，所以当多种异常同时出现在流水线的不同阶段中，按照其发生的位置安排优先级处理时得当的方法。异常处理的硬件电路和中断一样，在设计时需要分析不同阶段的异常EPC中要保存的地址，流水线中需要废弃的指令，nPC中的下一个指令地址。具体分析的方法可以看李亚民的书。
其实这里我认为李的书中所描述的CPU工作起来应该有BUG。李并没有设计中断请求和响应的相应机制，默认中断到来就立刻进入中断处理程序。但在其代码中可以清楚看到，中断的优先级是低于异常的，因此当异常和中断同时发生时，由于缺乏中断请求和响应机制，CPU可能在处理异常时错过外部中断，造成IO设备数据丢失。另外，如上文所述，选择立刻处理中断会引入额外的性能开销，使流水线性能下降，因此我倾向于选择等待时机处理中断。
由此可以发现，在流水线系统里实现中断和异常处理并不是一个简单的任务。当你引入额外的硬件提供的cache同步支持时，事情就变得更加复杂。当MEM级发生一次cache写入，若这次写入的地址是已经预取、在流水线中执行着的指令，需要清除Icache中的某行，同时将被影响的指令及其之后的指令从流水线中废弃；若不影响已经预取的指令，则只需要在Icache中清除某行即可。可以将这样的事件当作异常处理，但与异常不同的是，某个引起自修改代码的LW指令，不会产生转移，只是需要在流水线中废弃某些指令。若采用李的书中做法，情况就会变得非常复杂。我若实现硬件cache同步，一定会选择等待时机（处理器无异常、ID无跳转、ID不是延时槽、cache不需要同步）响应中断，这样流水线控制设计只需要分析异常和cache同步即可。
现分析异常和cache同步：如果按照性能考虑，cache同步事件可以在EXE级就计算出来，可以使用旁路将lw指令写入的目标与IF ID 级指令的地址进行比较，判断是否废弃流水线中的指令。由于lw指令不是跳转指令，因此发生cache同步事件时，ID级一定不处在延时槽。如果不考虑性能，可以选择无论IF、ID那个指令需要废弃，只要有一个需要废弃，就直接将IF、ID中的指令作废，重新执行。如果考虑性能，事情就变得复杂了.如果此时ID级是一个跳转指令，那么延时槽中的指令受到cache同步的影响，如果只废弃IF级指令就会引起错误，因为处理器丢弃了ID级的跳转指令计算出的跳转结果，等于ID级跳转指令没有起到作用，所以如果Cache同步影响IF级中的指令，应当判断ID级是否是跳转指令（或syscall），如果是，则不仅要废弃IF还要废弃ID。
这样看来，硬件支持的cache同步机制配合等待时机的中断响应机制，以及立刻处理的异常机制在硬件上可以实现。但是我不打算实现它。为什么呢？
在之前的设想中，我将原本发生在MEM级的cache事件，前推到EXE级，这很大程度上避免了更多的流水线性能损失。但是这仅仅可以在无分页机制的情况下实现。如果实现分页，则在指令中的地址都是虚地址，EXE级的地址也是虚地址，不能用于前面级流水寄存器中指令地址的比较，而实地址实在查找MEM级中的TLB后才能得到。也就是说上述设计在实现TLB后，就失效了，而设计TLB是本项目的远期计划之一。因此不妨等到完成MMU设计之后，存储控制系统定型，再加入硬件的cache同步支持。
因此得出结论，目前的设计采用软件控制的cache同步，提供硬件Cache清空指令。系统软件编写者在编写自修改代码时，应先关闭中断，在修改完代码后手动清空cache，并使用紧随其后的若干空指令消除cache不同步引起的流水线错误。