多面体模型中的调度表示

发布网友发布时间：2024-10-12 21:18

共1个回答

热心网友时间：2024-10-21 02:53

多面体模型中，调度表示（schele）对应于一个可静态预测的循环片段（static control parts, scop），它通过整数规划的仿射表示，确定了执行顺序。本文将深入探讨调度表示的关键概念。

首先，调度表示的核心是调度树（schele tree），这是一种自顶向下的全局表示，通过将每个语句实例按照sequence与for的层次逐层分配，实现从根节点开始的全局映射。这种表示方式易于直接变换，且引入了辅助节点，作为多面体编译过程中的中间表示。它能够完整地回答与调度相关的数学表示话题。

接着，我们讨论了几种历史上的调度表示，包括Kelly表示、union-map表示和2d+1表示。这些表示在数学形式上差异仅在于值域，但都以语句为粒度，为每个语句提供仿射函数，映射到时间戳。时间戳的维度含义不同，但其序（字典序）定义一致，使得codegen过程中的算法基本相同。

尽管如此，区分这些基于statement-wise affine function的调度表示并非必需，重要的是在具体场景中灵活应用。个人理解，可以将某个维度理解为seqcomp或并行for，但这种理解与codegen过程无关。在手动构造调度变换时，这种区分可能有实际意义，但使用如pluto等工具自动生成合法的新调度，将使使用者较少关注标量维度的概念。

在调度表示转化为结构化循环代码的过程中，生成代码（codegen）算法起着关键作用。算法通过递归生成每一层循环结构，每次递归对应相邻一组seqcomp和for的生成（2d+1意义上），直至子多面体为空。具体实现来自Verified code generation for the polyhedral model | Proceedings of the ACM on Programming Languages，该文提供了codegen算法的概览。