高速缓存控制器伪最近最少使用均匀替换方法

摘要

本发明公开了一种高速缓存控制器Cache伪最近最少使用均匀替换方法，要解决的技术问题是克服传统LRU替换方法在组相联路数可配置、不固定的情况下各路数据替换几率不同造成替换不均匀的弊病，使组相联数最多分别为8路和4路时各种配置下的每一路数据都能被均匀地替换。技术方案是分别设计组相联数最多为4路时，配置成3路组相联的情况和组相联数最多为8路时，分别配置成3路、5路、6路、7路组相联的情况中的伪LRU变换控制电路。采用本发明解决了Cache的3、5、6、7路组相联的替换均匀性问题，可以确保它们各路的数据块被均匀的替换；可以保证与替换均匀性相关的程序正确的执行，且在某些情况下能减少Cache失效的次数和程序运行的时间。

主权项

1.一种高速缓存控制器伪最近最少使用均匀替换方法，采用伪LRU变换控制电路控制LRU位的变化，伪LRU变换控制电路是一个有限状态机，该状态机发出的信号控制LRU位的变换，由LRU位控制Cache中哪一路的数据被替换出去，其特征在于伪LRU变换控制电路设计成伪LRU均匀性变换控制电路，且伪LRU均匀性变换控制电路的设计因组相联数的不同而不同，具体方法是分别设计组相联数最多为4路时，配置成3路组相联的情况和组相联数最多为8路时，分别配置成3路、5路、6路、7路组相联的情况中的伪LRU变换控制电路：1.1组相联数最多为W0、W1、W2、W3这4路时，配置成3路组相联的情况：当配置成W1、W2、W3 3路Cache时，将LRU位R0R1R2为000、001状态下替换的路数改为W2，其余在R0R1R2为110、100下替换W2和在R0R1R2为010、011下替换W1和在R0R1R2为101、111下替换W3保持不变，W1、W2、W3替换转换过程是：假如开始LRU位R0R1R2为011组合状态，则在此状态下，按替换规则W1被替换，同时修改R0＝1、R1＝0，R0R1R2变为101状态；在101状态下，按替换规则接着替换W3，同时修改R0＝0、R2＝0，R0R1R2变为000状态；在000状态下，按替换规则接着替换W2，同时修改R0＝0，R1＝1、R2＝1，R0R1R2变为011状态，然后如此类推的进行循环替换；如果初始LRU位组合状态不是011，按本发明替换方法也总会落在011、101、000这三个基本状态上，然后在011->101->000->011这个替换环上轮转，使得替换以W1、W3、W2的顺序依次进行，保证了替换的均匀性；1.2组相联数最多为W0、W1、W2、W3、W4、W5、W6、W7 8路时，配置成7路组相联的情况：当配置成W1、W2、W3、W4、W5、W6、W7 7路时，在R0R1R2R3R4R5R6为0000000状态下改为替换W4，同时对LRU位进行相应的修改，将R0R1R2R3R4R5R6修改为0111010，使状态转换到0111010，使得替换按照W4，W2，W6，W1，W5，W3，W7的顺序均匀轮换进行；1.3组相联数最多为W0、W1、W2、W3、W4、W5、W6、W7 8路时，配置成6路组相联的情况：当配置成W2、W3、W4、W5、W6、W7 6路时，在R0R1R2R3R4R5R6为0000000状态下改为替换W4，同时对LRU位进行相应的修改，将R0R1R2R3R4R5R6修改为0111010，使状态转换到0111010；而在R0R1R2R3R4R5R6为0001111状态下改为替换W5，同时对LRU位进行相应的修改，将R0R1R2R3R4R5R6修改为0110101，使状态转换到0110101，使得替换按照W4，W2，W6，W5，W3，W7的顺序均匀轮换进行；1.4组相联数最多为W0、W1、W2、W3、W4、W5、W6、W7 8路时，配置成5路组相联的情况：当配置成W3、W4、W5、W6、W7 5路时，故在R0R1R2R3R4R5R6为0000000状态下改为替换W4，同时对LRU位进行相应的修改，将R0R1R2R3R4R5R6修改为1011110，使状态转换到1011110；在R0R1R2R3R4R5R6为0001111状态下改为替换W5，同时对LRU位进行相应的修改，将R0R1R2R3R4R5R6修改为0110101，状态转换到0110101，使得替换按照W4，W6，W5，W3，W7的顺序均匀轮换进行；1.5组相联数最多为W0、W1、W2、W3、W4、W5、W6、W7 8路时，配置成3路组相联的情况：当配置成W5、W6、W7 3路时，在R0R1R2R3R4R5R6为0000000状态下直接替换W6，同时对LRU位进行相应的修改，将R0R1R2R3R4R5R6修改为0001111，状态转换到0001111；在R0R1R2R3R4R5R6为0001111状态下直接替换W5，同时对LRU位进行相应的修改，将R0R1R2R3R4R5R6修改为1010001，状态转换到1010001，使得替换按照W6，W5，W7的顺序均匀轮换进行。