Index Set Splitting
Index Set Splitting
复制标题
索引集分割
DOI：
--
复制
发表时间：
2000
影响因子：
1.5
通讯作者：
C. Lengauer
中科院分区：
文献类型：
--
作者：
M. Griebl;P. Feautrier;C. Lengauer
嵌套环的时空映射有许多算法。他们中的一些人甚至在他们的框架内做出最佳选择。我们提出了多层模型中算法的预处理阶段，该阶段扩展了模型并产生时空映射，其时间表在某些情况下是更快的数量级。在这些情况下，依赖图具有较小的不规则性。基本思想是将循环巢的索引集分为具有规则依赖性结构的部分，并将现有的时空映射算法分别应用于这些部分。这项工作基于在代码级别循环并行化的更有限上下文中的开创性思想。我们将想法提升到模型级别（我们的模型是多层模型），该概念通过以可接受的分析成本提供更清晰，更广泛的选择来提高其适用性。索引集拆分是努力扩展多层模型的功能并实现竞争目标代码的生成的一个方面。
There are many algorithms for the space-time mapping of nested loops. Some of them even make the optimal choices within their framework. We propose a preprocessing phase for algorithms in the polytope model, which extends the model and yields space-time mappings whose schedule is, in some cases, orders of magnitude faster. These are cases in which the dependence graph has small irregularities. The basic idea is to split the index set of the loop nests into parts with a regular dependence structure and apply the existing space-time mapping algorithms to these parts individually. This work is based on a seminal idea in the more limited context of loop parallelization at the code level. We elevate the idea to the model level (our model is the polytope model), which increases its applicability by providing a clearer and wider range of choices at an acceptable analysis cost. Index set splitting is one facet in the effort to extend the power of the polytope model and to enable the generation of competitive target code.