基于多面体模型的编译“黑魔法”-赵捷 , 李颖颖 , 赵荣彩.pdf

上善若水

550

26页

3次

2022-05-19

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2018,29(8):2371−2396 [doi: 10.13328/j.cnki.jos.005563] http://www.jos.org.cn

基于多面体模型的编译“黑魔法”

∗

赵

捷

1,2

李颖颖

1,3

赵荣彩

1,4

(解放军信息工程大学,河南郑州 450001)

(Département d'Informatique, École Normale Supérieure, Paris 75005, France)

(数学工程与先进计算国家重点实验室(解放军信息工程大学),河南郑州 450001)

(中原工学院,河南郑州 450007)

通讯作者: 赵捷, E-mail: zjbc2005@163.com

摘要: 基于多面体模型的编译技术发展近 30 年,已经在多个开源编译器和商业编译器中得到了应用和实现.与

传统的编译优化模型相比,多面体模型具备应用范围广、表示能力强、优化空间大等优点,代表了程序自动并行化

领域众多方向最先进的水平,成为国际上多个编译研发团队的研究热点;同时,多面体模型抽象程度高、实现难度大、

面临问题多的特征,阻碍了基于该模型的编译技术在发展相对滞后地区的普及,形成国内专门从事该问题研究的团

队屈指可数的现象.为了打开多面体模型的“黑盒子”,首先描述了多面体模型的原理,揭示了基于多面体模型的编译

流程,并指出了该领域的主要研究内容;接下来,从程序并行性、数据局部性和其他领域上的扩展应用这 3 个方面对

该领域上的研究进展进行了介绍;最后,对该研究领域当前面临的挑战和潜在的研究方向进行了总结.研究目的是通

过回顾和总结基于多面体模型的编译技术研究进展,为国内编译研发团队提供重要参考,以期推动我国在该领域上

的发展.

关键词: 多面体模型;并行性;局部性;依赖;调度;代码生成;循环分块;数组压缩

中图法分类号: TP314

中文引用格式: 赵捷,李颖颖,赵荣彩.基于多面体模型的编译“黑魔法”.软件学报,2018,29(8):2371−2396. http://www.jos.org.

cn/1000-9825/5563.htm

英文引用格式: Zhao J, Li YY, Zhao RC. “Black magic” of polyhedral compilation. Ruan Jian Xue Bao/Journal of Software,

2018,29(8):2371−2396 (in Chinese). http://www.jos.org.cn/1000-9825/5563.htm

“Black Magic” of Polyhedral Compilation

ZHAO Jie

1,2

, LI Ying-Ying

1,3

, ZHAO Rong-Cai

1,4

(PLA Information Engineering University, Zhengzhou 450001, China)

(Département d'Informatique, École Normale Supérieure, Paris 75005, France)

(State Key Laboratory of Mathematical Engineering and Advanced Computing (PLA Information Engineering University), Zhengzhou

450001, China)

(Zhongyuan University of Technology, Zhengzhou 450007, China)

Abstra ct : Polyhedral compilation has evolved for nearly three decades, being implemented as a building block or an optional extension

of numerous open-source and/or commercial compilers. On the one hand, the polyhedral model is equipped with wider range of

applications, more powerful expressiveness and greater optimization space when compared with those traditional models adopted for

parallelizing compilers, thus representing the state of the art of almost each domain of parallelizing compilers and becoming a hot topic to

∗ 基金项目: 国家自然科学基金(61702546)

Foundation item: National Natural Science Foundation of China (61702546)

收稿时间: 2017-10-22; 修改时间: 2017-12-08; 采用时间: 2018-01-29; jos 在线出版时间: 2018-03-13

CNKI 网络优先出版: 2018-03-14 09:18:11, http://kns.cnki.net/kcms/detail/11.2560.TP.20180314.0917.001.html

2372

Journal of Software 软件学报 Vol.29, No.8, August 2018

a great number of international research teams working on compilers. On the other hand, the polyhedral model is also characterized as

being difficult in theory, complex for manipulation, and diverse with challenges, hampering its adoption in underdeveloped countries and

areas and drawing few researchers working on this topic from the domestic compiler community. Aiming at opening the “black-box” of

the polyhedral model, this paper conducts a survey on the “black magic” of polyhedral compilation. First, the underlaying theory behind

the polyhedral model is introduced along with a desciption of the general compilation process and an overview of the research directions.

Next, the research progress of the polyhedral compilation targeting on parallelism, data locality, and extensions in various application

domains is presented. Last but not least, open challenges faced by the polyhedral community and potential research directions on this

topic are disussed. The purpose of this work is to provide an important reference for the domestic compiler community by reviewing and

summarizing current trends on the polyhedral compilation, and to promote Chinese compiler researchers in making progress on this topic.

Key words: polyhedral model; parallelism; locality; dependence; schedule; code generation; loop tiling; array contraction

随着多核时代的来临,多核架构已成为当今处理器市场的主流.然而,由此引发的多核架构上的并行程序开

发也变得异常困难;对于传统的面向单核处理器开发的应用程序,如何将其移植到这些多核架构上,成为一项艰

巨的任务.与此同时,多核架构的出现为编译优化和代码生成提出了巨大的挑战,编译程序不仅要考虑如何发掘

程序的并行性,而且还要考虑如何提升程序的数据局部性.

除此之外,不同处理器厂商针对各自的处理器架构设计并实现了相应的编程模型,无论是在多核架构上直

接开发并行应用程序还是实现传统单核应用程序的移植任务,程序开发人员除了要深入了解目标架构的细节

之外,还要越过处理器厂商设计的编程模型“门槛”.

这些因素导致了并行应用程序的开发远远落后于处理器架构发展的这一事实,加之程序员固有的思维逻

辑使得串行程序的开发显得非常直观和自然.因此,直接在多核架构上开发并行应用程序的技术往往只被少数

人掌握.即便是专业人员,也不可能同时实现不同架构的并行应用程序开发.自动并行化工具是在多核架构上开

发并行应用程序的一种行之有效但非常具有挑战性的方法,这种方法通过将串行程序自动转换为并行程序,能

够让应用程序开发人员从复杂的并行代码编写任务中解脱出来,因此受到了广泛的关注.

1 引言

基于多面体模型(英文翻译还可以对应为 polytope model、polyhedron model 等)的编译优化技术

[1]

是程序

自动并行化领域的一个研究热点,是解决程序自动并行变换的一种有效手段.与传统的并行化编译器中所采用

的幺模矩阵模型

[2]

相比,多面体模型具备以下几个方面的优点.

(1) 应用范围广:幺模矩阵只能处理完美循环嵌套,而多面体模型对输入程序的约束更少,不仅能够处理

完美循环嵌套,而且对非完美循环嵌套的支持也比较完善.

(2) 表示能力强:幺模矩阵只能表示循环交换、倾斜和反转等优化,而多面体模型除了能够处理上述循环

变换之外,还能自动实现包括循环分块、合并、分布等在内的几乎所有循环变换技术.

(3) 优化空间大:幺模矩阵 1 次只能实现 1 种循环变换,而多面体模型允许同时实现多个循环变换,极大地

提升了并行化编译器优化程序的能力.

得益于这些优点,基于多面体模型的编译优化技术代表了程序自动并行化领域众多方向最先进的水平,成

为国际上多个编译研发团队的研究热点.

然而,在这些优点的背后是多面体模型兼备的难点:首先,多面体模型的抽象程度高,涉及集合与映射、谓词

逻辑等多个抽象解释领域的理论,多面体模型论文中的大量公式和抽象描述使研究人员很难理解;其次,多面体

模型的实现难度大,当前,几乎所有基于多面体模型实现的编译优化技术在实质上都是线性整数规划问题,不仅

难以实现,时间和空间复杂度也都很高;再次,多面体模型面临的问题多,考虑到多面体模型在发掘程序并行性

和数据局部性方面的能力,越来越多来自不同领域的应用程序对多面体模型提出了更高的要求,这给多面体模

型的扩展带来了许多挑战.

上述问题阻碍了基于多面体模型的编译技术在发展相对滞后地区的普及,而我国在编译程序方面的研究

相对薄弱,最终形成了多面体模型发展至今已有约 30 年的历史,而国内专门从事多面体模型研究的团队屈指可

of 26

免费下载

软件学报计算机技术

关注

评论