本毕业设计的主要目的在于对开源项目PPCG进行二次开发。使其生成的代码具有更优的性能。

PPCG（Polyhedral Parallel Code Generation）是一款开源的源码到源码编译器（以下简称源源编译器），能够对串行源码生成对应的OpenCL或CUDA版代码。开发并行程序如OpenCL和CUDA对开发者能力的要求高于串行程序，源源编译器能够减少开发者的工作，将代码的并行化交给编译器来做。类似的技术还有OpenACC和OpenMP。

OpenACC和OpenMP提供基于制导的并行化编程方案。OpenMP能够在共享内存的计算平台上（如多核CPU平台）实现并行化。OpenACC是一个编译器指令集合，用于指示C/C 或Fortran代码通过加速器（如GPU）加速。它与OpenMP的设计理念是一样的，允许开发者在不了解面向加速器的编程语言的情况下创建并行程序。

PPCG运用了多面体模型来分析代码，基于多面体模型的编译优化技术是程序自动并行化领域的一个研究热点，是解决程序自动并行变换的一种有效手段，与传统的并行化编译器中所采用的幺模矩阵模型相比，多面体模型具备以下几个方面的优点1、应用范围广：幺模矩阵只能处理完美循环嵌套，而多面体模型对输入程序的约束更少，不仅能够处理完美循环嵌套，而且对非完美循环嵌套的支持也比价完善；2、表示能力强：幺模矩阵只能表示循环交换、倾斜和反转等优化，而多面体模型除了能处理上述循环变换之外，还能够自动实现包括循环分块、合并、分布等在内的几乎所有循环变换技术；3、优化空间大：幺模矩阵一次只能实现一种循环变换，而多面体模型允许同时实现多个循环变换，大大提升了并行化编译器优化程序的能力，得益于这些优点，基于多面体模型的编译优化技术代表了程序自动并行化领域众多方向最先进的水平，成为国际上多个编译研发团队的研究热点。

然而，多面体模型兼备几个难点。首先，多面体模型的抽象程度高，涉及集合与映射、谓词逻辑等多个抽象解释领域的理论，多面体模型论文中的大量公式和抽象描述使研究人员很难理解；其次，多面体模型的实现难度大，当前，几乎所有基于多面体模型实现的优化编译技术在实质上都是线性整数规划问题，不仅难以实现，时间和空间复杂度也都很高。

在国外，多面体模型已经广泛应用在了程序自动优化和程序自动并行化领域，诞生了很多源源编译器如PoCC、Pluto和CHiLL,它们利用多面体框架来实现循环变换。传统的编译器，例如GCC、LLVM和IBM XL运用多面体框架为多核架构计算机生成代码。Benabderrahmane在2010年将多面体技术拓展到数据依赖分析，动态控制流方面。

在国内，对编译技术以及编译器实现的研究相对比较落后，导致专门研究多面体模型的团队屈指可数。

对现有并行代码生成器做出改进，对并行代码生成器的发展有重要意义。

2. 研究的基本内容与方案

基本内容：

对串行程序并行化的一个重要方式是将串行的循环代码映射为并行代码。由于GPU具有大量的硬件并行性，将循环分段能够利用GPU的并行性。分段因子不能整除循环次数时，需要做额外的处理保证对数组的访问不越界。现有处理方式有1、在循环体内生成if控制，使得线性化后索引量不超出原来的循环界；2、生成尾循环，为不整除的尾块单独生成一个小循环；3、强制用户选择能整除的因子。其中方法1具有通用性，但是性能开销比较大；方法2只适合2级分段；方法3缩小了分段因子和并行映射的调优空间而且不具备通用性。