一个基于图着色的CACHE优化方法

A cache optimizing method based on graph coloring

提出了一个编译时的Cache管理优化方法。该方法根据访存行为将程序中的数据划分成若干数据对象,根据数据对象的大小将Cache划分为一个带有别名的伪寄存器文件,每个伪寄存器由若干Cache行组成,可以容纳一个数据对象;使用一个经过改进的图着色寄存器分配算法来决定这些对象在Cache中的位置以及发生冲突时的替换关系。数据对象的划分将Cache的管理分为两个层次,一个是编译时编译器对粗粒度的数据对象的管理,另一个是运行时硬件对细粒度的Cache行的管理,这样编译器和硬件的优势都得到发挥。基于GCC进行了方法实现,并通过simplescalar构造了支持Cache Coloring的硬件模拟平台。实验结果表明Cache Coloring能较好地开发程序的局部性,降低Cache失效率。

A graph coloring based management optimizing algorithm for cache, namely Cache Coloring, has been proposed. This algorithm first partitions the data into several data objects according to their memory accessing behaviors. Then it partitions the cache into a pseudo register file with alias according to the size of the data objects. Each pseudo register in this register file can hold one of the data objects. Finally, it uses an extended graph coloring register allocation algorithm to determine the position of each data object in the cache and their replacement relationship. The data object partitioning divides the management of cache into two levels, one for the coarse-granularity management of the data objects in the compile-time and the other for the fine-granularity management of the cache lines in the run-time. So the advantages of both compiler and hardware are exploited. Cache Coloring is implemented in GCC. A hardware simulation platform which supports Cache Coloring is built based on the Simplescalar processor simulator. The primary experimental results show that Cache Coloring can exploit the locality well and reduce the cache miss rate.