The Polyhedral Model of Nonlinear Loops
The Polyhedral Model of Nonlinear Loops
复制标题
非线性环的多面体模型
DOI：
10.1145/2838734
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
P. Clauss
中科院分区：
文献类型：
--
作者：
Aravind Sukumaran;P. Clauss
在当前多核时代，运行时代码优化和投机执行越来越重要。但是，这种技术的更广泛，更有效的利用主要受到集中数据竞赛检测，动态代码行为建模和代码生成引起的刺激性时间间接费用。现有的大多数线程级别投机（TLS）系统都依赖于将目标循环切成块的天真稳定，并试图借助集中的绩效验证模块，并试图在负责处理数据种族的集中式绩效验证模块的帮助下并行执行块。由于缺乏数据依赖模型，这些投机系统无法进行高级转换，更重要的是，回滚的机会很高。多面体模型是一个著名的数学模型，用于分析和优化环巢。当前的最新工具限制了多面体模型在静态控制代码中的应用。因此，这些工具通常都无法使用循环，间接内存访问或指针来处理代码。 Apollo（自动多面体环路优化器）是一个框架，该框架超越了一个步骤，并使用TLS动态应用多面体模型。 Apollo可以在运行时预测代码是否线性行为，并且它可以正常应用多面体转换。本文提出了一个新型系统，该系统使Apollo能够处理其内存访问和循环界限不一定是线性的代码。更一般而言，此方法将运行时多面体模型的适用性扩展到更广泛的代码类别。将线性和非线性访问插入依赖性预测模型，即使在非线性代码内核中也可以应用多面体回路优化转换，同时也允许进行低成本的推测验证。
Runtime code optimization and speculative execution are becoming increasingly prominent to leverage performance in the current multi- and many-core era. However, a wider and more efficient use of such techniques is mainly hampered by the prohibitive time overhead induced by centralized data race detection, dynamic code behavior modeling, and code generation. Most of the existing Thread Level Speculation (TLS) systems rely on naively slicing the target loops into chunks and trying to execute the chunks in parallel with the help of a centralized performance-penalizing verification module that takes care of data races. Due to the lack of a data dependence model, these speculative systems are not capable of doing advanced transformations, and, more importantly, the chances of rollback are high. The polyhedral model is a well-known mathematical model to analyze and optimize loop nests. The current state-of-art tools limit the application of the polyhedral model to static control codes. Thus, none of these tools can generally handle codes with while loops, indirect memory accesses, or pointers. Apollo (Automatic POLyhedral Loop Optimizer) is a framework that goes one step beyond and applies the polyhedral model dynamically by using TLS. Apollo can predict, at runtime, whether the codes are behaving linearly or not, and it applies polyhedral transformations on-the-fly. This article presents a novel system that enables Apollo to handle codes whose memory accesses and loop bounds are not necessarily linear. More generally, this approach expands the applicability of the polyhedral model at runtime to a wider class of codes. Plugging together both linear and nonlinear accesses to the dependence prediction model enables the application of polyhedral loop optimizing transformations even for nonlinear code kernels while also allowing a low-cost speculation verification.