「多面体」多面体编译基础（二）

多面体

本章内容

数据依赖
仿射映射（Affine MAPPing）
像的仿射映射
多面体的笛卡尔积（Cartesian Product of Polyhedra）

一、仿射

1.1 像（Image）

定义多面体 $P \in Z^{n}$ 经过仿射函数 $f: Z^{n} \rightarrow Z^{m}$ 得到的像为：

$P^{'}=\{f(\overrightarrow{x}) \in Z^{m} | \overrightarrow{x} \in P \}$

1.2 逆像（Preimage）

定义经过仿射函数 $f: Z^{n} \rightarrow Z^{m}$ 得到的多面体 $P \in Z^{n}$ 的逆像为：

$P^{'} = \{ \overrightarrow{x} \in Z^{n} | f(\overrightarrow{x}) \in P \}$

若仿射函数f是可逆的，则有：

$Image(f^{-1}, P) = Preimage(f, P)$

为了说明像、逆像的概念，不妨举个例子：

Compute the set of cells of A accessed

for (i = 0; i < N; ++i)
    for (j = i; j < N; ++j)
        A[2i + 3][4j] = i * j;

迭代域（多面体）为：

$D_{S}: \{ i, j | 0 \leq i \leq N-1, i \leq j \leq N-1 \}$

仿射函数为：

$f_{A}: \{ 2i + 3, 4j | i, j \in Z \}$

迭代域（多面体）的像为：

$Image(f_{A}, D_{S}) = \{ i^{'}, j^{'} | 0 \times 2 + 3 \leq i^{'} \leq (N-1) \times 2 + 3, i \times 4 \leq j^{'} \leq (N-1) \times 4 \}$

$Image(f_{A}, D_{S})= \{ i^{'}, j^{'} | 3 \leq i^{'} \leq 2N+1, 4i \leq j^{'} \leq 4N-4 \}$

因为

$i^{'}=2i+3$

所以有

$Image(f_{A}, D_{S})= \{ i^{'}, j^{'} | 3 \leq i^{'} \leq 2N+1, 2(i^{'}-3) \leq j^{'} \leq 4N-4 \}$

二、数据依赖

2.1 伯恩斯坦条件（Bernstein Conditions）

给定两个访存操作，如果它们同时满足以下三个条件，那么将会发生数据依赖：

它们访问同一数组（数据块）
至少一个操作为写操作
两个操作对应的语句都会被执行

2.2 三种数据依赖类型

RAW（Read-After-Write, aka flow）：写后读，或称流依赖
WAR（Write-After-Read, aka anti）：读后写，或称反依赖
WAW（Write-After-Write, aka output）：写后写，或称输出依赖

2.3 直观数据依赖测试算法

此算法可以判断两个访存操作之间是否存在数据依赖。

给定两个访问同一数组的操作和：

计算 $W_{a}$ ：当为写操作时， $W_{a} = Image(f_{a}, D_{a})$ ，否则 $W_{a} = \varnothing$
计算 $R_{a}$ ：当为读操作时， $R_{a} = Image(f_{a}, D_{a})$ ，否则 $R_{a} = \varnothing$
计算 $W_{b}$ ：当为写操作时， $W_{b} = Image(f_{b}, D_{b})$ ，否则 $W_{b} = \varnothing$
计算 $R_{b}$ ：当为读操作时， $R_{b} = Image(f_{b}, D_{b})$ ，否则 $R_{b} = \varnothing$

若 $W_{a}$ 、 $R_{a}$ 、 $W_{b}$ 、 $R_{b}$ 满足：

$a \delta b = W_{a} \cap R_{b} \neq \varnothing \vee W_{a} \cap W_{b} \neq \varnothing \vee R_{a} \cap W_{b} \neq \varnothing \neq \varnothing$

则与存在数据依赖，记作 $a\delta b$ 。

2.4 数据依赖图

简称DDG（Data Dependence Graph），DDG是一种有向多重图，记为G=(V,E)，它的每个顶点表示一个循环语句S，每条有向边 $e_{(S_{s}, S_{t})} \in E$ 表示从语句 $S_{s}$ 到 $S_{t}$ 之间存在一个依赖关系。

2.5 数据依赖关系

一致性依赖（Uniform Dependences）：两个存在依赖关系的迭代之间的步长为常量，例如 $i \rightarrow i+1; i, j \rightarrow i+1, j+1$
非一致性依赖（Non-uniform Dependences）：两个存在依赖关系的迭代之间的步长随着程序执行而发生改变，例如 $i \rightarrow i+j; i \rightarrow 2i$
参数依赖（Parametric Dependences）：依赖关系中至少包含一个可变参数，例如 $i \rightarrow i+N; i+N \rightarrow j+M$

三、依赖多面体

3.1 语句依赖（Dependence of statement instances）

语句S依赖于语句R仅当存在访存操作 $S(\overrightarrow{x_{S}})$ 和 $R(\overrightarrow{x_{R}})$ 和内存位置m，并满足：

$S(\overrightarrow{x_{S}})$ 和 $R(\overrightarrow{x_{R}})$ 访问同一内存位置m，且至少一个操作为写操作
$x_{S}$ 和 $x_{R}$ 都属于R和S的迭代域
$S(\overrightarrow{x_{S}})$ 在 $R(\overrightarrow{x_{R}})$ 之前执行

3.2 笛卡尔积

参见百度百科：https://baike.baidu.com/item/%E7%AC%9B%E5%8D%A1%E5%B0%94%E4%B9%98%E7%A7%AF/6323173?fromtitle=%E7%AC%9B%E5%8D%A1%E5%B0%94%E7%A7%AF&fromid=1434391&fr=aladdin

笛卡尔乘积是指在数学中，两个集合X和Y的笛卡尓积（Cartesian product），又称直积，表示为X×Y，第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员。

假设集合A={a, b}，集合B={0, 1, 2}，则两个集合的笛卡尔积为{(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}。

3.3 依赖多面体构造算法

以下面的代码为例，说明依赖多面体的构造过程。

for (t = 1; t <= T; t++)
    for (i = 1; i <= I; i++)
        A[i] = 0.5 * (A[i] + A[i + 1]);

为了便于区分符号，我们将上述代码第3行中左边的A[i]记作A1、右边的A[i]记作A2，A[i + 1]记作A3。

我们先来构造一个数据依赖图：

第一步，画上依赖图的各个节点（数组元素）：

第二步，根据访存操作（至少有一个写操作，本例中仅有A1是写操作）访问内存同一区域时迭代变量的情况判断节点两两之间的依赖关系、依赖类型，计算距离向量 $\overrightarrow{d} = \overrightarrow{i_{t}} - \overrightarrow{i_{s}}$ ，画出依赖边 $e_{Al, Ak}$ ：

$e_{A1,A1}$ ：类型为输出依赖（写后写），源迭代向量 $\overrightarrow{i_{s}} = (t,i)$ 、目标迭代向量 $\overrightarrow{i_{t}} = (t+1,i)$ ，表示目标节点A1相对于源节点A1在t方向上的后1步与源节点A1访问相同的内存位置，距离向量 $\overrightarrow{d} = (1,0)$ 。
$e_{A1, A2}$ ：类型为流依赖（写后读），源迭代向量 $\overrightarrow{i_{s}} = (t, i)$ 、目标迭代向量 $\overrightarrow{i_{t}} = (t+1,i)$ ，表示目标节点A2相对于源节点A1在t方向上的后1步与源节点A1访问相同的内存位置，距离向量 $\overrightarrow{d} = (1, 0)$ 。
$e_{A1, A3}$ ：类型为流依赖（写后读），源迭代向量 $\overrightarrow{i_{s}} = (t, i)$ 、目标迭代向量 $\overrightarrow{i_{t}} = (t+1, i-1)$ ，表示目标节点A3相对于源节点A1在t方向上的后1步、i方向上的前1步与源节点A1访问相同的内存位置，距离向量 $\overrightarrow{d} = (1,-1)$ 。
$e_{A2,A1}$ ：类型为反依赖（读后写），源迭代向量 $\overrightarrow{i_{s}} = (t,i)$ 、目标迭代向量 $\overrightarrow{i_{t}} = (t+1,i)$ ，表示目标节点A1相对于源节点A2在t方向上的后1步与源节点A2访问相同的内存位置，距离向量 $\overrightarrow{d} = (1,0)$ 。
$e_{A3,A1}$ ：类型为反依赖（读后写），源迭代向量 $\overrightarrow{i_{s}} = (t,i)$ 、目标迭代向量 $\overrightarrow{i_{t}} = (t,i+1)$ ，表示目标节点A1相对于源节点A3在i方向的后1步与源节点A3访问相同的内存位置，距离向量 $\overrightarrow{d} = (0,1)$ 。

第三步，根据第二步的结论，补全数据依赖图（懒得画了，直接从论文上截图吧）：

第四步，根据第二步的结论，为每条边构造依赖多面体：

$\small P_{e_{A1,A1}} = \{ t_{s}, i_{s}, t_{t}, i_{t} | t_{s} - t_{t} + 1 = 0, i_{s} - i_{t} = 0, 1 \leq t_{t} \leq T-1, 1 \leq i_{t} \leq I \}$ ，用矩阵形式表示，即为 $\tiny P_{e_{A1, A1}} = \{t_{s}, i_{s}, t_{t}, i_{t} | \begin{bmatrix} 1 & 0 & -1 & 0 & 1 \\ 0 & 1 & 0 & -1 & 0 \end{bmatrix} \begin{pmatrix} t_{s} \\ i_{s} \\ t_{t} \\ i_{t} \\ 1 \end{pmatrix} = 0, \begin{bmatrix} 1 & 0 & 0 & 0 & -1 \\ -1 & 0 & 1 & 0 & -1 \\ 0& 1 & 0 & 0 & -1 \\ 0 & -1 & 0 & 1 & 0 \end{bmatrix} \begin{pmatrix} t_{t} \\ i_{t} \\ T \\ I \\ 1 \end{pmatrix} \geq 0 \}$ 。
$\small P_{e_{A1,A2}} = \{ t_{s}, i_{s}, t_{t}, i_{t} | t_{s} - t_{t} + 1 = 0, i_{s} - i_{t} = 0, 2 \leq t_{t} \leq T, 1 \leq i_{t} \leq I \}$ ，用矩阵形式表示，即为 $\tiny P_{e_{A1, A2}} = \{t_{s}, i_{s}, t_{t}, i_{t} | \begin{bmatrix} 1 & 0 & -1 & 0 & 1 \\ 0 & 1 & 0 & -1 & 0 \end{bmatrix} \begin{pmatrix} t_{s} \\ i_{s} \\ t_{t} \\ i_{t} \\ 1 \end{pmatrix} = 0, \begin{bmatrix} 1 & 0 & 0 & 0 & -2 \\ -1 & 0 & 1 & 0 & 0 \\ 0& 1 & 0 & 0 & -1 \\ 0 & -1 & 0 & 1 & 0 \end{bmatrix} \begin{pmatrix} t_{t} \\ i_{t} \\ T \\ I \\ 1 \end{pmatrix} \geq 0 \}$ 。
$\small P_{e_{A1,A3}} = \{ t_{s}, i_{s}, t_{t}, i_{t} | t_{s} - t_{t} + 1 = 0, i_{s} - i_{t} - 1 = 0, 2 \leq t_{t} \leq T, 1 \leq i_{t} \leq I-1 \}$ ，用矩阵形式表示，即为 $\tiny P_{e_{A1, A3}} = \{t_{s}, i_{s}, t_{t}, i_{t} | \begin{bmatrix} 1 & 0 & -1 & 0 & 1 \\ 0 & 1 & 0 & -1 & -1 \end{bmatrix} \begin{pmatrix} t_{s} \\ i_{s} \\ t_{t} \\ i_{t} \\ 1 \end{pmatrix} = 0, \begin{bmatrix} 1 & 0 & 0 & 0 & -2 \\ -1 & 0 & 1 & 0 & 0 \\ 0& 1 & 0 & 0 & -1 \\ 0 & -1 & 0 & 1 & -1 \end{bmatrix} \begin{pmatrix} t_{t} \\ i_{t} \\ T \\ I \\ 1 \end{pmatrix} \geq 0 \}$ 。
$\small P_{e_{A2,A1}} = \{ t_{s}, i_{s}, t_{t}, i_{t} | t_{s} - t_{t} + 1 = 0, i_{s} - i_{t} = 0, 1 \leq t_{t} \leq T-1, 1 \leq i_{t} \leq I \}$ ，用矩阵形式表示，即为 $\tiny P_{e_{A2, A1}} = \{t_{s}, i_{s}, t_{t}, i_{t} | \begin{bmatrix} 1 & 0 & -1 & 0 & 1 \\ 0 & 1 & 0 & -1 & 0 \end{bmatrix} \begin{pmatrix} t_{s} \\ i_{s} \\ t_{t} \\ i_{t} \\ 1 \end{pmatrix} = 0, \begin{bmatrix} 1 & 0 & 0 & 0 & -1 \\ -1 & 0 & 1 & 0 & -1 \\ 0 & 1 & 0 & 0 & -1 \\ 0 & -1 & 0 & 1 & 0 \end{bmatrix} \begin{pmatrix} t_{t} \\ i_{t} \\ T \\ I \\ 1 \end{pmatrix} \geq 0 \}$ 。
$\small P_{e_{A3,A1}} = \{ t_{s}, i_{s}, t_{t}, i_{t} | t_{s} - t_{t} = 0, i_{s} - i_{t} + 1 = 0, 1 \leq t_{t} \leq T, 1 \leq i_{t} \leq I - 1 \}$ ，用矩阵形式表示，即为 $\tiny P_{e_{A3, A1}} = \{t_{s}, i_{s}, t_{t}, i_{t} | \begin{bmatrix} 1 & 0 & -1 & 0 & 0 \\ 0 & 1 & 0 & -1 & 1 \end{bmatrix} \begin{pmatrix} t_{s} \\ i_{s} \\ t_{t} \\ i_{t} \\ 1 \end{pmatrix} = 0, \begin{bmatrix} 1 & 0 & 0 & 0 & -1 \\ -1 & 0 & 1 & 0 & 0 \\ 0& 1 & 0 & 0 & -1 \\ 0 & -1 & 0 & 1 & -1 \end{bmatrix} \begin{pmatrix} t_{t} \\ i_{t} \\ T \\ I \\ 1 \end{pmatrix} \geq 0 \}$ 。

文章最后发布于: 2019-04-08 11:23:20

多面体编译基础（二）

多面体