中期报告V31

Report
龙芯编译器中多面体优化技术的研究与实现
胡士文
指导老师:冯晓兵 连瑞琦
大纲
1. 学位论文研究情况和已完成的研究内容
2. 已取得的阶段成果
3. 与预期计划不符情况及原因
4. 下一步工作计划
5. 其他情况介绍
大纲
1. 学位论文研究情况和已完成的研究内容
2. 已取得的阶段成果
3. 与预期计划不符情况及原因
4. 下一步工作计划
5. 其他情况介绍
学位论文研究情况和已完成的研究内容
学位论文研究情况和已完成的研究内容
学位论文研究情况和已完成的研究内容
设计并实现龙芯编译器中的多面体优化模型
• 解决多面体模型在编译器内部的交互问题
• 通过POLYBENCH所有测试用例
多面体模型的调优
• 利用Pluto优化并分析结果
• 指导SIMD优化
扩展多面体模型的适用范围
• 扩展多面体模型支持的循环表示
大纲
1. 学位论文研究情况和已完成的研究内容
2. 已取得的阶段成果
3. 与预期计划不符情况及原因
4. 下一步工作计划
5. 其他情况介绍
龙芯编译器中的多面体模型
WHIRL
SCoP分析:WRaP-IT
程序分析和变换:PLuTo
代码生成:CLooG
WRaP-IT
w2pscop
SCoP_Cvt
clan_scop
PLuTo
.cloog文件
CLooG
clast
WLooG
WHIRL
龙芯编译器中的多面体模型

w2pscop转换成clan_scop
语句的迭代域存在对应关系,直接转换
 调度函数的转换

# i j n
1 1 0 0
1 -1 0 1
1 0 1 0
1 0 -1 1
S1的迭代域
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
S1:
a[i][j] = b[i][j];
#
0
0
0
0
0
p0 p1 p2 p3 p4 i j n
1 0 0 0 0 0 0 0
0 1 0 0 0 -1 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 -1 0
0 0 0 0 1 0 0 0
w2pscop中S1的调度函数
1
0
0
0
0
0
1
0
-1
0
-1
# i j n 1
[ 0 0 0 0 0]
[ 0 1 0 0 0]
[ 0 0 0 0 0]
[ 0 0 1 0 0]
[ 0 0 0 0 0]
clan_scop中S1的调度函数
龙芯编译器中的多面体模型

for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
S1:
a[i][j] = b[i][j];
w2pscop转换成clan_scop

仿存函数的转换
a
0
1
b
0
1
1
0
0
0
0
0
Accessed array strings: a b
#
i j n 1
[ 1 1 0 0 0]
[ 0 0 1 0 0]
1
0
0
0
0
0
[
[
w2pscop中S1的仿存函数形式
2
0
1
0
0
1
0
0
0]
0]
clan_scop中S1的仿存函数形式
龙芯编译器中的多面体模型
CLooG中生成AST的地方,生成相应的WHIRL
 变换前后WHIRL的对应问题

程序的多面体表示形式没有原来的中间表示的符号信息以
及循环中语句的信息
 变换结果可以用符号的对应关系来表达
 变换之前,我们需要收集循环变量和循环参数的信息
 变换之后,将符号变换的赋值语句和原来的循环语句插入
循环中


多面体模型在编译器内部的交互问题

额外调用一次Pre_Optimizer来维护du和别名信息
龙芯编译器中的多面体模型
for (k=0; k<N; k++) {
for (j=k+1; j<N; j++)
a[k][j] = a[k][j]/a[k][k];
原程序
#define S1(k,j) a[k][j]=a[k][j]/a[k][k];
for (t0=0;t0<=floord(N-1,90);t0++)
for (t1=0;t1<=floord(N-1,90);t1++)
for (t2=max(2,90*t1);t4<=min(N-1,90*t1+89);t4++)
for (t3=max(2,90*t2);t5<=min(N-1,90*t2+89);t5++)
S1(t2,t3);
Pluto优化后的结果
龙芯编译器中的多面体模型
for (k=0; k<N; k++) {
for (j=k+1; j<N; j++)
a[k][j] = a[k][j]/a[k][k];
原程序
for (t0=0;t0<=floord(N-1,90);t0++)
for (t1=0;t1<=floord(N-1,90);t1++)
for (t2=max(2,90*t1);t4<=min(N-1,90*t1+89);t4++)
for (t3=max(2,90*t2);t5<=min(N-1,90*t2+89);t5++) {
k = t2; j = t3;
S1(k, j);
}
多面体模型优化后的抽象表示
多面体模型的优化

强大的tiling
在polybench的17个程序上,平均加速2.2倍
 优化mgrid的最热循环,加速7.2%(166 -> 178)


缺乏一个好的loop fusion模型


对swim优化效果不佳
缺乏自动计算最优tile size的算法
180
175
170
165
160
155
16
32
64
80
90
100
POLYBENCH上的优化效果
6
5
4
3
O3 -poly,-tile
2
1
0
O3
多面体模型的优化

指导SIMD优化
 在多面体中识别可向量化的循环
 循环迭代间依赖分析
 迭代和仿存的步长分析
 按照SIMD宽度tile一次,并在LOOP
INFO中标记,为后
续代码生成做准备
 Jacobi等用例可被向量化
for (i = 0; i < 1024;
i++)
B[i] = A[i];
for (i = 0; i < 1024; i += 4)
for (ii = i; ii <= i + 3; ii++)
B[ii] = A[ii];
SIMD优化的三个步骤
for (i = 0; i < 1024;
i += 4)
B[i : i + 3] = A[i :
i + 3];
扩展多面体模型的适用范围
循环形式
复杂仿存1
复杂仿存2
典型代码
for {
…
hmm->xsc[XTN][MOVE];
…
}
for{
...
ar= a->e[i][0].real; ai= a->e[i][0].imag;
...
}
目前是否能
处理
是
否
扩展多面体模型的适用范围
循环形式
典型代码
Union domain
if (incx.eq.1.and.incy.eq.1)go to 20
do 10 i = 1,n
zy(iy) = zy(iy) + za*zx(ix)
ix = ix + incx
iy = iy + incy
10 continue
否
非仿射的条件
语句
tpim = hmm->tsc[TIM];
for (i = 1; i <= L; i++)
for (k = 1; k <= M; k++) {
......
if ((sc = …tpim[k-1]) > ...)
ic[k] = sc
......
}
否
目前是否已
扩展
大纲
1. 学位论文研究情况和已完成的研究内容
2. 已取得的阶段成果
3. 与预期计划不符情况及原因
4. 下一步工作计划
5. 其他情况介绍
与预期计划不符情况及原因

原计划
 2011.7~8
实现龙芯编译器中的
多面体优化
 2011.9~10

解决多面体优化在编
译器中的交互问题
 2011.11~2012.2

分析性能并改进多面
体程序变换算法
 2012.3~2012.5

技术改进,撰写论文

实际情况

多面体模型不能处理很
多大型程序(如spec)
中的循环结构的表示形
式

发现除多面体变换算法
以外的影响性能的因素
(tile size的选择)

大纲
1.学位论文研究情况和已完成的研究内容
2. 已取得的阶段成果
3. 与预期计划不符情况及原因
4. 下一步工作计划
5. 其他情况介绍
下一步工作计划

多面体模型的进一步调优
Tile后tile size的选择算法
 SIMD优化跟后端代码生成的集成


增强模型的实用性
提高正确性
 支持spec06中复杂的循环表示形式,为优化奠定基础


向open64提交
为开源社区做出贡献
 测试X86上的性能

大纲
1. 学位论文研究情况和已完成的研究内容
2. 已取得的阶段成果
3. 与预期计划不符情况及原因
4. 下一步工作计划
5. 其他情况介绍
科研项目的完成情况
时间
科研项目
承担任务
2009/09-2010/5 863龙芯项目子课题-龙 •提升编译器正确性
芯3号编译器研制
•Conditional move优化模块
2010/5-今
核 高基专 项课 题-支 持 •设计实现多面体优化模型
国产CPU的编译系统及 •LQ优化模块
工具链
•编译gcc和linux kernel
课程完成情况
课程名称
自然辩证法与科技
革命
分数
学分
学位课
课程名称
通识案例必修
课
分数
学分
学位课
92
3.0
是
通过
1.0
否
硕士学位英语(免
修)
数理逻辑
70
3.0
是
知识产权法
87
1.0
否
90
3.0
是
77
2.0
否
89
3.0
否
英语B
西方社会历史
文化面面观
(中)
高性能计算机系统
通过
0.5
否
编译程序高级教程
89
3.0
是
并行处理
97
3.0
是
形式语言与自动机
理论
85
3.0
是
高性能并行计
算
87
2.0
否
高性能计算的新发
展——基于图形处
理器的并行计算及
CUDA编程
86
1.0
否
先进计算机和
软件技术系列
讲座
通过
0.5
否
中国特色社会主义
理论与实践
79
1.0
是
体育类公共选
修课
通过
0.5
否
通过
1.0
否
云计算系列讲座
通过
0.5
否
近世代数
96
3.0
否
视觉圣经-西
方艺术中的基
督教
总学分
35
谢谢!
祝各位老师、
同学新春愉快!

similar documents