必威体育Betway必威体育官网
当前位置:首页 > IT技术

多面体编译基础(二)

时间:2019-10-26 16:46:00来源:IT技术作者:seo实验室小编阅读:69次「手机版」
 

多面体

本章内容

  • 数据依赖
  • 仿射映射(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 直观数据依赖测试算法

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

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

  • 计算W_{a}:当a为写操作时,W_{a} = Image(f_{a}, D_{a}),否则W_{a} = \varnothing
  • 计算R_{a}:当a为读操作时,R_{a} = Image(f_{a}, D_{a}),否则R_{a} = \varnothing
  • 计算W_{b}:当b为写操作时,W_{b} = Image(f_{b}, D_{b}),否则W_{b} = \varnothing
  • 计算R_{b}:当a为读操作时,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

ab存在数据依赖,记作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}})之前执行

相关定义:

  • 相同内存位置:同一数组访存操作的下标函数相同:F_{S} \overrightarrow{x_{S}} + a_{S} = F_{R} \overrightarrow{x_{R}} + a_{R}
  • 优先顺序(Precedence order):每种用例都对应于一个相同的循环深度,称为依赖等级(each case corresponds to a common loop depth, and is called a dependence level)
  • 依赖级别(Dependence Level):

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

相关阅读

淘宝客基础知识一览:不用培训也能轻松入门

其实个人比较喜欢研究落单的淘宝客,即孤军奋战,没有团队配合,没有资金流挥霍,凭的是方法与门道,会建站的早年已通过站群的模式赚了一笔

Ubuntu18.04 Qt编译过程中,“找不到 -lGL”

终端输入 sudo apt-get install libgl1-mesa-dev

C#中(int)、Conver.Toint32()、int.Parse()三种类型转换

自己也是刚学习C#程序设计语言,总结了一点知识点,想分享给大家。毕竟刚学习这门语言,学得不深,哪里如果有错误,请帮个忙指出一下哈,谢谢

GCC编译器

GCC 是由 GUN 组织开发的,最初只支持C语言,是一个单纯的C语言编译器,后来 GNU 组织倾注了更多的精力,使得 GCC 越发强大,增加了对 C+

对于编译原理的理解

#编译原理今天组长教育了一下整个程序的编译过程,感觉自己对于这块了解还是很少,有许多知识之前知道,现在忘记了,还有很多规则只是知

分享到:

栏目导航

推荐阅读

热门阅读