基于超完美图着色的存储分配算法  

Super-perfect Graph Coloring Based Memory Allocation Algorithms

作　　者：邓宇[1] 汪黎[1] 晏小波[1] 王桂彬[1] 唐滔[1] 

机构地区：[1]国防科技大学计算机学院并行与分布重点实验室,长沙410073

出　　处：《计算机科学》2008年第9期233-236,257,共5页Computer Science

基　　金：国家自然科学基金60621003和60633050

摘　　要：为了提高性能,一些应用需要在编译时对主存进行针对性的管理。提出了基于超完美图的主存分配方法,其基本思想是通过生命周期分割将一般的相干图转换为超完美图,从而可以使用已有的线性时间的区间着色算法完成主存的分配。分别基于自底向上的积极生命周期分割策略和自顶向下的被动生命周期分割策略,实现了两个分配算法。初步评测表明,我们的分配算法是有效的编译时管理主存手段。In some special applications, the main memory needs to be managed by the compiler to improve the performance. Memory allocation algorithms based on super-perfect graph coloring are proposed. The basic idea is to tutti the general interference graph into super-perfect graph by live-range splitting and then use an existing linear time interval coloring algorithm to allocate the memory. Two allocation algorithms are implemented according to different live-range splitting strategies., a top-down aggressive strategy and a bottom-up passive strategy. Preliminary modeling tests show that they are efficient approaches for compile-time memory allocation.

关 键 词：编译时存储分配 主存管理 区间着色 超完美图 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术] TN929.533[自动化与计算机技术—计算机科学与技术]