SRFColoring一种基于图着色的流寄存器文件分配方法.PDF

Yang XJ, Deng Y, Wang L et al. SRF coloring: Stream register file allocation via graph coloring. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 24(1): 152-164 Jan. 2009 SRF Coloring: 一种基于图着色的流寄存器文件分配方法 1．本文的创新点 流处理器在众多领域表现出巨大的应用潜力。FT64 流处理器是一个面向科学计算的 64 位流处理器，流寄存器文件 (Stream Register File, SRF)是FT64 上的大容量局部存储器。 由于存储墙的存在，SRF 的有效管理对FT64 的性能至关重要。本文提出了一种编译方法， 称为SRF Coloring，来自动分配SRF 空间。本文的创新点在于：1. 第一次将图着色寄存器 分配算法有效地应用于流处理器的 SRF 的分配。2. 提出了基于 FT64 体系结构的 SRF coloring 算法框架，该框架基于一个被广泛理解的图着色寄存器分配算法框架，并针对SRF 的访问特点进行了扩充，提高了分配SRF 的效率。3. 在SF95Compiler 编译框架下实现了该 算法。 2 ．实现方法 本文的基本想法是按照程序中流的长度将 SRF 划分为一个带有别名的伪寄存器文件， 然后采用一个从一个经典的图着色寄存器分配算法扩充而来的分配算法进行分配。由于SRF 的访问方式与传统的标量寄存器、向量寄存器以及便签存储器(scratchpad memory)存在本质 的区别，已有的图着色寄存器分配算法不能有效的应用于SRF 的分配。针对SRF 访问的特 点，本文对经典的图着色寄存器分配算法进行了两点扩充：1. 积极的生命周期扩充。2. 基 流与派生流共享 SRF 空间。以经典的图着色寄存器分配算法框架为基础，通过修改少量步 骤和增加部分步骤来实现SRF Coloring 算法。首先，对Build 步骤进行了扩充，增加了一些 相干边的构造条件，实现了积极的生命周期扩充；然后在原 Coalesce 步骤后增加一个 Coalesce2 步骤，用于合并基流及其派生流对应的结点，实现其空间共享；其次，在Coalesce2 后面增加了一个Relax 步骤，在相干图不可化简时，取消某些由于生命周期扩充引入的相干 边。在实现SRF Coloring 算法的同时，还保持了原算法的简洁和高效。 3 ．结论及未来待解决的问题 我们在SF95Compiler 编译框架中实现了SRF Coloring 算法。从fft 等8 个测试程序的初 步测试结果来看，我们的分配方法确实是一种有效的方法。 在这方面还有很多富于挑战的工作要完成。例如，由于寄存器到寄存器的 streamcopy 操作涉及访存操作，开销很大（而一般的寄存器到寄存器的 move 操作开销很小），因此我 们可以考虑采取一个先积极合并再考虑溢出（但不是任何地方）的算法框架。当前我们的分 配方法还没有考虑对长流（例如超过SRF 大小的流）的支持。解决长流问题的方法有两个， 一个是程序级的 strip-mining，另一个是运行时的双缓冲技术。我们将考虑把这两个步骤都 纳入我们的框架，从而更有效的管理 SRF。SRF 的分配结果与流操作在控制流图上的顺序 有很大关系，我们还将考虑变换语句的顺序，寻找一种能够得到最优分配方案的方法。 4 ．实用价值或应用前景 本文的工作完成了FT64 流处理器的一个重要的编译环节，即在编译时对FT6 的片上存 储器 SRF 的管理。现有的流编程语言向程序员暴露了存储层次细节，这种编程风格增加了 程序员的负担，不利于继承已有代码，因此不易被程序员接受。FT64 的解决思路是向程序 员隐藏存储层次细节，由编译器来完成片上存储器的管理。随着工艺的进步，片外访存延迟 相对处理器速度不断加大，越来越多的处理器采用了大容量片上存储器。本文所提出的方法 不仅针对FT64 中的SRF，对其它处理器的片上存储器的编译时管理同样也具有指导意义。