基于语句迁移的循环变换在多核SIMD架构上的研究与实现

摘要

当代的计算机应用程序大部分是多媒体应用，包括音视频处理，图像处理，3D绘图，语音识别等，这就对处理器提出了更加严格的实时性要求。因此，多媒体SIMD扩展结构，已经逐渐为通用微处理器所采用，以获取更高的多媒体处理速度。为了最大化的并行处理，当前许多片上多核处理器都开始采用了SIMD扩展结构。一方面，为了执行SIMD操作，向量寄存器中的数据必须先将位置调整对齐，从而妨碍性能的提高,也影响SIMD编译器中自动向量化的效率。另一方面，许多常见的以循环为主的应用程序都是单线程的。以前的研究工作都没能很好的解决这样一个问题，即如何在考虑SIMD硬件的限制下，挖掘循环体结构中的粗粒度并行度以应用到多核环境中。 本文研究了多媒体应用中常见嵌套循环的变换框架，包含了依赖关系的抽象和建立、分析和变换，以及最后变换代码的生成。本文提出了一种基于语句迁移的循环变换，主要是通过语句迁移的方式，在考虑原有依赖关系的情况下，对每层循环中的语句进行迁移。该变换对外层循环进行基于依赖图的分析和变换，提高并行度，从而可以划分成多个线程在多核环境下并行的执行。对内层循环，变换过程抽象出偏移集合，建立出相应的数学模型，并提出了最优解和近似解两种解法，不仅实现SIMD化，也减少所需要的数据对齐操作。内外层循环变换过程是相互影响和制约的，对此本文中也做了详细的研究。最后本文根据有无数据依赖环，分情况详细研究了SIMD代码的生成问题。该策略已在Cell SDK仿真工具上实现，并进行了大量的测试。实验结果显示，本文提出的循环变换方法可以有效的减少数据对齐操作，同时外层的循环变换可以显著的提高并行度。在Cell上的实验结果显示，通过减少数据对齐操作，可以获得1.1x的加速比。另外由于进行多核并行处理，平均加速比达到6.14，因此，变换后的循环体整体上可以获得6.67的平均加速比。