基于置换图的便笺存储器分配

在当今的嵌入式系统中,广泛地将片上存储器组织为软件管理的便笺存储器(SPM).Li等研究发现,对于很多嵌入式应用,其相干图中的数组生存期满足包含性.他们证明了满足生存期包含性的数组相干图为超完美图,并提出了一个基于超完美图的SPM分配算法.他们的算法在面向嵌入式应用的SPM分配上获得了当前最好的性能.本文进一步证明满足生存期包含性的数组相干图为置换图.置换图是超完美图的一个子类.在现有技术的情况下,置换图在判定及区间着色方面比超完美图有优势,如存在线性时间的识别算法,存在线性时间的最优区间着色算法.基于此理论结果,我们将Li等的算法在保留原算法逻辑的基础上,改进为基于置换图.实验表明,改进后的算法在很多不满足生存期包含性的相干图上仍能取得最优SPM分配,获得比基于超完美图的分配算法更好的分配结果.

Scratchpad memory allocation for arrays in permutation graphs

In modern embedded systems, on-chip memory is generally organized as software-managed scratchpad memory （SPM）. Li et al. discovered that in many embedded applications, the array interference graphs tend to be superperfect graphs. Based on this, they presented a superperfect graph-based SPM allocation algorithm, which is the best in the literature. In this paper, we make further progress in proving that the array interference graphs they focused on are permutation graphs; that is, a subclass of a superperfect graph. Compared to the latter, the permutation graph has certain advantages, such as linear time recognition and linear time optimal interval coloring. Based on our theoretical results, we improve their algorithm by transforming it into a permutation graph-based one by means of simple plug-in revisions. The experiments confirm that the improved algorithm achieves optimal coloring, and therefore, better allocation than the original superperfect graph-based algorithm for a broader scope of array interference graphs.