Research On Graph Coloring Based Optimization Technologies For Memory Hierarchies

The performance gap between processor and memory causes the problem known as "Memory Wall", which makes the memory system become the bottleneck of the computer system. The developing trends of current semiconductor and computer architecture techniques show that this gap will keep increasing. Consequently, the optimization to the memory system will be one of the key technologies to improve the overall performance of the computer system in the visible future.This thesis focuses on applying the graph coloring theory to the management optimizing problem of the memory hierarchies. Novel management approaches in compile-time have been presented in the aspects of cache, large on-chip register files represented by Stream Register File (SRF) and the main memory. Primary innovative works in this paper could be summarized as follows:(i) 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. The conflict matrix which contains more information about interference than the traditional live-range interference graph is constructed as a guide to deal with the conflicts of register allocation. Cache Coloring is implemented in GCC. A hardware simulation platform which supports Cache Coloring is built based on simplescalar. The primary experimental results show that Cache Coloring can exploit the locality well and reduce the cache miss rate.(ii) A graph coloring based SRF allocation algorithm, namely SRF Coloring, is proposed. This algorithm formulates the problem of SRF allocation into a register allocation problem which can be solved by a well understood graph coloring algorithm by partitioning the SRF into a traditional register file with fixed position and length. The existing graph coloring algorithm is extended and modified to address the unique aspect of the SRF allocation problems. A reusing-first double-buffering strategy is presented to address the uncoloralbe problem caused by very long streams. The SRF Coloring algorithm is implemented in the compiler framework of SF95Compiler, which is developed for FT64 stream processor and its programming language SF95. The experimental results demonstrate that SRF Coloring represents a promising compiler approach for the SRF management.(iii)An interval coloring based allocation algorithm for main memory, namely MM Coloring, is proposed. The main memory allocation problem is mapped to an interval coloring problem by taking arrays as candidates for memory allocation. As the general interval coloring problem is NP-complete, a property of the program, namely the containment of arrays' live-ranges, is used to decrease the hardness of interval coloring and simplify it as an interval coloring problem for superperfect graph. Based on this, a judgment theorem for optimal interval coloring together with the implementation algorithm is proposed. Live-range splitting can be used to make the graph satisfy the optimal interval coloring condition. Two strategies for live-range splitting are proposed. One is a top-down aggressive strategy which first splits the live-ranges into minimum and then merges them gradually when the coloring condition is satisfied. The other one is a bottom-up passive strategy which keeps the live-ranges as long as possible and splits some of them only when the coloring condition is not satisfied. MM Coloring with both aggressive and passive strategies is implemented in GCC. Modeling tests show that it is an efficient approach for compile-time memory allocation.