共享主存多SIMD结构编译优化及结构研究

论文摘要

共享主存多SIMD结构是指N×N的处理单元（PE-Processing Element）按一定的拓扑结构连接组成的阵列结构，同行/列各PE之间以SIMD方式工作，多行/列之间并行执行。随着多媒体应用的日益普及和多样化，这些应用对处理器的速度提出了越来越高的要求。传统的采用单独的SIMD结构作为多媒体加速部件或者为专门的应用设计ASIC的方法无法同时满足这些应用处理速度和多样性的要求。共享主存多SIMD结构由于其较强的运算能力和可编程性不仅受到学术界的广泛关注，许多公司，如Mortorala、Intrinsity、Morphotech和Folsom都推出了采用共享主存多SIMD结构作为多媒体加速部件的SOCs。在这些芯片的设计过程中，出于节能和芯片面积的考虑，大部分都对共享主存多SIMD结构加入了多行/列SIMD功能单元共享数据总线和各PE寄存器较少的限制。虽然这些限制简化了芯片设计，但是却给针对共享主存多SIMD结构的编程设置了极大的障碍，也给针对共享主存多SIMD结构的优化技术的研究提出了极大的挑战。目前虽然针对共享主存多SIMD结构作为多媒体加速部件得到了越来越广泛的应用，但是针对共享主存多SIMD结构编译技术的研究却远远滞后于结构的普及。这种情况造成的直接后果是目前程序员只能用手写汇编的方式为共享主存多SIMD结构编写代码。这种编程方式不仅要求程序员熟悉应用程序，也要求程序员对底层结构有深入了解。程序员不仅要为新的应用编写代码，又要为已有的应用重新编写可在共享主存多SIMD结构上运行的代码，这极大增加了程序员的负担。同时由于没有有效编译优化技术的支持，目前针对共享主存多SIMD结构的研究也不够深入，共享主存多SIMD结构的各种特性与结构整体性能的关系的研究都没有展开。这些都给共享主存多SIMD结构的更广泛应用设置了障碍。这种情况下，针对共享主存多SIMD结构优化技术的研究就显得十分迫切。虽然共享主存多SIMD结构中，存在SIMD指令级别的并行，但是由于共享数据总线的限制，很多情况下多SIMD功能部件无法并行执行，如何有效减少共享数据总线的竞争对于提高共享主存多SIMD结构的并行性就显得尤为重要。传统的数据复用的算法虽然可以解决类似的问题，但却不能解决共享主存多SIMD结构的问题，主要由于以下几方面的原因：1．传统的数据复用的算法针对的是标量操作数，而共享主存多SIMD结构的操作数主要是向量。2．传统数据复用的算法在提高数据复用的时候，只是在一定程度上减少了数据总线的竞争，如何提高数据总线的利用率并没有解决。3．传统的数据复用的算法主要研究对象是cache，而要减少共享主存多SIMD结构中多SIMD功能单元对总线的竞争，只能提高寄存器的数据复用。而在共享主存多SIMD结构中，每个SIMD功能单元的寄存器数量很少，如何有效解决这个问题，减少数据的换入换出对于提高性能也显得至关重要。本文在充分分析共享主存多SIMD结构编译优化的障碍的基础上，提出了一种优化方法的框架，该框架通过利用共享总线的广播特性提高共享总线的利用率，通过提高SIMD单元本地寄存器的Locality特性来减少各SIMD功能单元对共享总线的竞争。针对单个SIMD单元寄存器少的特点，提出了一种寄存器分配算法，在满足计算资源利用率的前提下，也尽量满足寄存器分配的需求。针对共享主存多SIMD结构多SIMD单元之间的互连的特性，提出了一种流水线调度的策略，该策略可以有效发掘多媒体程序的流水线级并行。该算法在有效提高并行的同时，极大减少了多SIMD单元对共享数据总线的竞争和本地寄存器的压力。本文介绍的算法已在我们实验室开发的C编译器Agassiz中实现。实验数据显示，这些算法对共享主存多SIMD结构获得很好的加速效果。同时，在编译器的帮助下，我们对共享主存多SIMD结构的一些特性与整体性能的关系进行了深入的分析，如共享主存多SIMD结构的队列规模，执行模式等，并根据实验结果，对共享主存多SIMD的结构设计提出了一些建议。总而言之，本文的主要贡献在于：1．从软硬件两个角度对共享主存多SIMD结构编译优化的重点和主要困难进行了系统阐述。从而使得共享主存多SIMD结构编译优化算法有的放矢。针对共享主存多SIMD结构结构提出了有效的自动编译优化的算法。2．针对共享主存多SIMD结构共享数据总线的特点，提出了一种调度算法，该调度算法利用共享数据总线的特点，在有效减少共享主存多SIMD结构共享数据总线竞争的同时，也极大提高了共享数据总线的利用率。3．针对共享主存多SIMD结构各SIMD功能单元寄存器少的特点，提出了一种新的寄存器分配算法，该算法极大减少了数据换出的数量，减少了数据总线的竞争。4．针对共享主存多SIMD结构多SIMD功能单元之间互连的特性和一些多媒体应用程序的特点，提出了一种数据流水线的调度策略，该方法在充分利用流水线并行的基础上，极大的降低了多SIMD功能单元对共享总线的竞争和SIMD功能单元本地的寄存器压力。5．针对共享主存多SIMD结构的特点，提出了一种基于软件流水线的指令预取策略，该策略可以有效提高数据传输的效率。6．在进行自动编译优化技术研究的同时，针对共享主存多SIMD结构的特点，对共享主存多SIMD结构进行了深入的结构研究，并根据实验结果，给出了一些针对结构设计的建议。

论文目录

• 目录
• 摘要
• Abstract
• 第一章 引言
• 1.1 多媒体应用
• 1.2 共享主存多SIMD结构
• 1.2.1 多SIMD结构
• 1.2.2 共享主存多SIMD结构
• 1.3 共享主存多SIMD结构编译优化的意义
• 1.4 共享主存多SIMD结构面临的主要问题
• 1.4.1 共享主存多SIMD结构编译发展滞后的原因
• 1.4.2 共享主存多SIMD结构编译需解决的主要问题
• 1.5 已有研究
• 1.6 本文的贡献及结构安排
• 第二章 底层结构
• 2.1 Morphosys概述和特征
• 2.1.1 Morphosys概述
• 2.1.2 基本特征
• 2.2 Morphosys组件的设计与实现
• 2.2.1 TinyRisc
• 2.2.2 多SIMD功能单元
• 2.2.3 指令缓冲器
• 2.2.4 共享主存
• 2.2.5 DMA控制器
• 2.3 Morphosys的物理设计
• 第三章 多媒体程序特性分析
• 3.1 程序包简介
• 3.2 多媒体程序运行时特点
• 3.3 代码形式特点
• 3.3.1 广泛使用指针进行运算
• 3.3.2 大量的循环展开
• 3.3.3 多媒体典型操作的变体很多
• 3.3.4 使用映射数组替代复杂计算
• 3.3.5 普遍使用宽数据类型
• 第四章 问题分析
• 4.1 并行性分析
• 4.1.1 共享数据总线对并行的限制
• 4.1.2 基于广播的并行
• 4.1.3 基于数据复用的并行
• 4.1.4 数据流水线并行
• 4.2 有限寄存器对并行的限制
• 4.3 结构的问题
• 第五章 优化算法
• 5.1 预备优化
• 5.1.1 SIMD优化
• 5.1.2 代码划分
• 5.1.3 向量数据重用信息的计算
• 5.2 仿射划分
• 5.2.1 仿射划分基本概念
• 5.2.2 仿射划分算法
• 5.2.3 只读数组复制的计算
• 5.3 数据流水线信息识别
• 5.3.1 实时数据分析
• 5.3.2 数据流水方向的确定
• 5.3.3 冗余通信的消除
• 5.4 划分循环选择
• 5.4.1 划分循环选择
• 5.4.2 计算-通信的转换
• 5.4.3 数据重用空间的构造
• 5.5 资源分配
• 5.5.1 寄存器分配
• 5.5.2 平均指令级并行性计算
• 5.5.3 资源分配
• 5.6 调度算法
• 5.6.1 指令调度
• 5.6.2 针对共享主存多SIMD结构的调度算法
• 5.7 调度实例
• 5.8 总结
• 第六章 其他优化算法
• 6.1 规约操作
• 6.1.1 规约变量的SIMD优化的额外处理
• 6.1.2 规约变量的调度优化的额外处理
• 6.2 数据预取
• 6.2.1 数据预取概述
• 6.2.2 基于软件流水线的数据预取
• 第七章 实验结果
• 7.1 SimpleScalar模拟器
• 7.1.1 SimpleScalar模拟器简介
• 7.1.2 SimpleScalar模拟器工具集概述
• 7.1.3 SimpleScalar模拟器工具集概述
• 7.2 共享主存多SIMD结构模拟器的实现
• 7.2.1 模拟器的实现
• 7.2.2 模拟器GCC工具链的调整
• 7.3 测试程序
• 7.4 实验结果
• 第八章 性能分析
• 8.1 阵列大小
• 8.2 GPPC执行模式
• 8.3 寄存器个数
• 8.4 互联
• 8.5 共享数据总线
• 8.6 VLIW指令缓冲区
• 8.7 总结
• 第九章 总结
• 9.1 结论
• 9.2 将来的工作
• 参考文献
• 发表文章目录
• 致谢