CRIMSON: Compute-Intensive Loop Acceleration by Randomized Iterative Modulo Scheduling and Optimized Mapping on CGRAs
CRIMSON: Compute-Intensive Loop Acceleration by Randomized Iterative Modulo Scheduling and Optimized Mapping on CGRAs
复制标题
DOI：
10.1109/tcad.2020.3022015
复制
发表时间：
2020-11
影响因子：
2.9
通讯作者：
M. Balasubramanian;Aviral Shrivastava
中科院分区：
文献类型：
--
作者：
M. Balasubramanian;Aviral Shrivastava
粗粒度可重新配置阵列(CGRA)是一种新兴的加速器，可在应用程序中承诺对计算密集型循环进行低功耗加速。CGRA实现的加速依赖于CGRA编译器将计算密集型循环高效地映射到CGRA体系结构上。CGRA映射问题是NP完全的，分两步进行，即调度和映射。调度算法将时隙分配给数据流图中的节点，映射算法将调度后的节点映射到CGRA的处理单元上。在映射失败时，增加启动间隔(II)，并为增加的II获得新的调度。大多数先前的映射技术使用迭代模调度(IMS)算法来寻找给定II的调度。由于IMS生成资源受限的越快越好(ASAP)调度，即使在II增加的情况下，它倾向于生成不可映射的类似调度。因此，IMS没有有效地探索调度空间。针对这些问题，本文提出了CRIMSON算法，利用随机化IMS算法加速计算密集型循环，优化映射技术，通过探索调度空间来生成随机模调度，从而在给定和增加的II上生成不同的模调度。Crimson还采用了一种新的调度后保守性测试来剪除不可映射的有效调度。从我们对MiBtch、Rodinia和Parboil的前24个性能关键循环(运行时间超过应用程序时间的7%)进行的研究中，我们发现以前使用IMS的最先进方法，如RAMP和GraphMinor，无法分别将5个和7个循环映射到$4\x 4$CGRA上，而Crimson能够映射它们。对于以前的方法映射的循环，Crimson获得了类似的II。
Coarse-grain reconfigurable arrays (CGRAs) are emerging accelerators that promise low-power acceleration of compute-intensive loops in applications. The acceleration achieved by CGRA relies on the efficient mapping of the compute-intensive loops by the CGRA compiler, onto the CGRA architecture. The CGRA mapping problem, being NP-complete, is performed in a two-step process, namely, scheduling and mapping. The scheduling algorithm allocates timeslots to the nodes of the data flow graph, and the mapping algorithm maps the scheduled nodes onto the processing elements of the CGRA. On a mapping failure, the initiation interval (II) is increased and a new schedule is obtained for the increased II. Most previous mapping techniques use the iterative modulo scheduling (IMS) algorithm to find a schedule for a given II. Since IMS generates a resource-constrained as-soon-as-possible (ASAP) scheduling, even with increased II, it tends to generate a similar schedule that is not mappable. Therefore, IMS does not explore the schedule space effectively. To address these issues, this article proposes CRIMSON, compute-intensive loop acceleration by randomized IMS and optimized mapping technique that generates random modulo schedules by exploring the schedule space, thereby creating different modulo schedules at a given and increased II. CRIMSON also employs a novel conservative test after scheduling to prune valid schedules that are not mappable. From our study conducted on the top 24 performance-critical loops (run for more than 7% of application time) from MiBench, Rodinia, and Parboil, we found that previous state-of-the-art approaches that use IMS, such as RAMP and GraphMinor could not map five and seven loops, respectively, on a $4\times 4$ CGRA, whereas CRIMSON was able to map them all. For loops mapped by the previous approaches, CRIMSON achieved a comparable II.