论文部分内容阅读
多核处理器的快速发展给软件带来机遇的同时,巨大的挑战也随之而来。我们熟悉的串行软件在多核系统上很难得到性能的提升,只有并行应用或被并行化的应用可以充分利用多核带来的丰富的运算资源。依赖编译器的并行化可以解决某些程序的问题,对于那些不规则的并行表示,必须由程序员使用适当的并行表示模型和语言来完成。现有的显式并行模型对粗粒度并行有较好的支持,而对细粒度并行的表示及同步支持还不够。另一方面,现有的并行编程工具很少有实现经典的数据流分析与优化,实际上,并行程序的分析与优化本身就是个挑战,其运行时的不确定性使得准确的静态分析比较困难,优化也很难有效进行。因此在显式并行模型中增加细粒度并行的表示及支持、在并行编译器中加强对并行程序的分析与优化就成为当前多核编译研究领域的一个热点。OpenMP是共享内存结构上编程接口的事实标准,目前也已广泛应用于多核结构上。本文深入研究了适用于多核结构的OpenMP程序的数据流分析、优化技术以及细粒度并行模式的实现技术,主要贡献及创新点包括:1.提出并构建了针对OpenMP程序存储模型的并行控制流图OMPCFG,它与一般的并行控制流图比较,OMPCFG具有较少的冲突边,并且待刷新集概念的引入减少了数据流分析时的不确定性,在OMPCFG流图上进行的到达-定值分析也更为准确。2.在构建的OMPCFG流图上建立了OpenMP并行静态单赋值(SSA)形式,并在其上有效实现了四项优化算法:拷贝传播、死代码删除、稀有条件常量传播、以及循环不变代码外提,实例分析表明在一般编译器中不能或错误优化的问题在本文提出的中间表示上可正确进行优化。另一方面,对OpenMP程序的分析与优化为细粒度并行提供了有利条件。3.针对工程技术领域中常见的迭代算法,提出了一种源程序级的流水并行模式,以及一种利用循环队列的流水线程间的同步方式,实验表明它比空间并行模式及计数同步方式有一定的优势。4.分析和研究了线程级推测并行(TLS)的三种实现,提出了在OpenMP上实现TLS的框架性方案。5.对现有多核上的Cache结构与策略进行了分析,提出了一种优化的选择性复制策略以及一种结合基于目录与总线侦听两者优点的混合Cache结构和相应的一致性协议,它充分利用了并行程序中相邻通信较多的特点,降低了Cache一致性开销,模拟实验表明它比单纯的基于目录的Cache协议有更好的性能,同时对程序执行性能的提高有一定帮助。