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

“Black Magic” of Polyhedral Compilation

基于多面体模型的编译技术发展近30年,已经在多个开源编译器和商业编译器中得到了应用和实现.与传统的编译优化模型相比,多面体模型具备应用范围广、表示能力强、优化空间大等优点,代表了程序自动并行化领域众多方向最先进的水平,成为国际上多个编译研发团队的研究热点;同时,多面体模型抽象程度高、实现难度大、面临问题多的特征,阻碍了基于该模型的编译技术在发展相对滞后地区的普及,形成国内专门从事该问题研究的团队屈指可数的现象.为了打开多面体模型的"黑盒子",首先描述了多面体模型的原理,揭示了基于多面体模型的编译流程,并指出了该领域的主要研究内容;接下来,从程序并行性、数据局部性和其他领域上的扩展应用这3个方面对该领域上的研究进展进行了介绍;最后,对该研究领域当前面临的挑战和潜在的研究方向进行了总结.研究目的是通过回顾和总结基于多面体模型的编译技术研究进展,为国内编译研发团队提供重要参考,以期推动我国在该领域上的发展.

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 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.