摘要
粗粒度可重构处理器（CGRA）因兼具通用处理器(GPP)的灵活性和专用集成电路(ASIC)的高能效性，是加速计算密集型应用的理想架构之一。虽然从硬件的角度来看CGRA是高能效的，但实际获得的性能很大程度上依赖于软件映射工具。循环作为计算密集型应用程序中的一部分，通常被映射到CGRA上用以加速。模调度作为循环加速的常用方法之一，它通过减小循环迭代间的启动间隔(Ⅱ)来提升循环的执行性能。而模调度的实际性能很大程度上依赖于从循环中提取的数据依赖图(DDG)的映射能力。因此，循环映射算法的优化对于提升计算密集型应用的性能具有极其重要的意义。 模调度中的映射问题通常涉及三个基本子问题:调度、布局和布线。由于CGRA中硬件资源连接的稀疏性，通常将布局和布线(P&R)同时执行以提高映射能力。一旦布局布线失败，需对DDG进行重调度并继续对重调度后的DDG进行布局布线。为了路由DDG中跨越超过1个时间步的长依赖，CGRA支持三种资源类型的长依赖路由方式，包括处理单元(PE)路由，局部寄存器(LRF)路由和数据存储器路由。但现有方法在调度阶段并未充分、全局地探索路由策略，因而后续布局布线容易失败，导致性能损失。同时，现有方法在布局布线阶段将路由资源类型探索与其完全分离以降低布局布线的搜索空间。但完全分离的路由策略探索无法感知算子的布局位置，容易导致布局布线失败。为解决上述问题并提高循环执行性能，我们采用了基于整数线性规划(ILP)的路由增强调度算法和基于回溯的路由资源类型感知布局布线算法。本文主要研究工作和成果如下: ①针对初始调度阶段路由资源类型探索不充分和重调度阶段路由资源类型探索局部化问题，本文采用了一种基于ILP的路由增强调度算法。它实现了将传统的调度扩展到支持图修改的调度，并能充分挖掘整个DDG的路由策略。同时，通过路由评估目标函数，ILP求解器能找到一个全局优化的初始调度方案。 ②针对现有映射方法在布局布线阶段将路由资源类型探索完全排除在外，从而导致布局布线成功率低的问题，本文提出把部分路由资源类型探索转移到布局布线中以提高其灵活性，使它有更多的机会找到有效映射解。根据以上思路，本文定义了一个紧凑的路由感知资源图(rPEA)，该资源图在不增加太多搜索空间的情况下，支持部分路由策略探索。为了有效地解决该rPEA上DDG的布局布线问题，本文采用了一种基于回溯机制的布局布线算法，以提高映射质量。 ③本文在编译器框架中实现了以上路由增强映射算法(REMap)，并在CGRA模拟器上进行了验证。实验结果表明，我们的映射技术相比于目前先进的BufAware和RAMP映射方法在性能上分别有10.8％和17.4％的提升，并在编译时间上分别缩短32.5％和58.9％。
NETL