高效可重构阵列计算：体系结构,设计方法与程序映射技术研究

摘要

随着应用领域的服务质量改进和标准的提高，人们不断对硬件提出了更高的性能和灵活性需求。以软件无线电为例，目标应用既要求硬件处理平台能够提供强大的计算能力以保证实时性，也要求硬件处理平台支持一定程度的可重构，以适应多种协议共存并快速发展的现状。粗粒度可重构阵列计算结构（CGRA）就是能够同时满足这两种需求的一类硬件，既可以通过大量的处理单元（PE）开发程序中各种粒度的并行，也能够通过功能单元字级的重构满足一定程度灵活性。虽然传统粗粒度可重构阵列结构能够对性能和灵活性提供较好的支持，但这种支持是以硬件的效率为代价的，无论是硬件开销还是功耗，CGRA都与专用集成电路（ASIC）存在不小的差距。从CGRA的设计实现到应用，面向特定应用的设计方法以及程序在CGRA上的并行执行对硬件性能的发挥有着至关重要的影响。因此，研究高效的粗粒度可重构阵列计算体系结构、设计方法和相关支撑技术成为当前可重构计算领域的重要课题。
　　本文立足于二维网格连接的粗粒度可重构阵列的计算平台，从新型高效的体系结构、面向特定应用程序的设计方法、程序在粗粒度可重构阵列上的指令级并行和循环级并行以及可重构硬件加速部件五个方面展开研究工作，并进行了详细的评测与性能分析。本文的主要研究成果和创新性体现在以下几个方面：
　　1）提出一种分簇的粗粒度可重构阵列计算结构，实现了CGRA在面积效率和功耗效率上的提高。针对功能单元利用率低的不足和数据传递的特点，本文提出了一种新型分簇的CGRA结构。在分簇CGRA中，根据功能单元的特点，将硬件功能单元分为两种类型：一类是简单的、操作时间短的PE；另一类是复杂的，操作时间长的PE。若干复杂的PE和若干个简单的PE可以组成一个可重构计算簇，簇内的数据传递由共享寄存器完成。复杂PE中还可以包含可定制的特殊功能单元，用户能够针对特定的应用程序特征进行定制。与传统的CGRA结构相比，该分簇结构由于资源的共享，复杂PE的数量减少，节省了硬件面积，提高了硬件利用率，在提高计算效率的同时保持了灵活性。由于簇内资源之间相互连接紧密，可以方便地交换数据，若在映射应用程序时充分利用数据通信的局部性，可以减少复杂的路由过程，提供更多的资源用于计算。实验结果表明，这种形式的CGRA结构具有更高的面积效率和功耗效率，基于簇的映射过程更加简单有效。
　　2）针对面向特定应用领域的功能单元定制，提出采用蚁群算法对应用程序自动进行分析并生成对应硬件结构的设计方法。本文分析了特定应用程序的特征提取和功能单元生成两个问题的现有方法，指出在传统设计方法中，应用程序特征识别和硬件功能单元生成两个过程相互独立的不足。本文进一步发现这两个问题都等价于确定程序数据流图DFG中两个节点之间的关联度，二者之间存在相互约束和限制。采用这种新的问题定义，本文提出了一体化的识别应用程序特征和硬件功能单元生成的自动化设计方法。在所提出的设计方法中，程序分析和硬件结构生成两个过程在算法中迭代交替进行，从而避免陷入局部优化的解，保证最终结果的全局优化性。基于蚁群优化的算法很好地融合了程序特征识别与硬件生成这两个过程，在全局启发因素和局部启发因素的共同作用下，自动地确定两个节点之间的关联度，优化效果明显。所提出的优化策略能够以较小的硬件代价实现较大程度的应用程序加速。
　　3）针对CGRA上的指令级并行，提出一种基于蚁群算法将无环数据流图DAG映射到CGRA的方法，在此基础上提出了在分簇CGRA上进行映射的优化策略。本文给出了将DAG映射到CGRA上的整数规划问题模型，指出DAG的映射实际上是将节点与PE单元一一对应，优化的目标是所有节点完成执行的时间。进而提出采用蚁群算法，在局部上采用尽早可能执行的策略，通过Maze Route过程确定节点在指定PE上的最早可执行时间，以此作为分配节点到PE的评价指标；在整体上通过蚂蚁残留的信息素，依靠蚁群算法的全局优化能力进行程序映射结果的全局优化。在蚁群映射算法基础之上，本文还发现某些具有特殊亲缘关系的节点对在很大程度上制约了最终结果质量，提出父子关系和共子关系的节点应该尽可能地映射到距离相近的计算簇上这一原则。通过定义和计算节点之间亲缘关系，算法在映射的过程中加入了节点对的亲缘关系、所在簇之间距离的考虑，以此作为将节点分配PE另一重要指标。加入这一指标增强了搜索的指向性，基于最大—最小蚁群算法所获得的映射结果质量有所提高。此外，以这个指标作为限制条件，适当地淘汰部分不合理的解能有效地减少搜索空间的范围，同时保证解的质量。与其他迭代优化的方法相比，该映射算法运行时间短、结果质量高并且质量稳定，为开发CGRA上的指令级并行提供了良好的支持。
　　4）针对CGRA上的循环级并行，提出一种基于遗传算法并考虑路由共享的模调度方法，根据分簇CGRA结构提出一种更快速、有效的模调度方法。本文提出了一种基于遗传算法的模调度方法，该方法中定义了数据依赖关系的优先级，以优先级顺序进行路由，保证路由时重要的数据依赖先得到满足。当循环核心中存在生产者相同、消费者不同的多个数据依赖关系时，路由采用Steiner树进行优化，在调度节点的同时寻找最优路由资源的共享方案。采用一种快速、近似的方法解决求解Steiner树的问题，较好地实现了路由节点的共享。此外，本文通过分析循环间数据依赖和循环内数据依赖的数量，提出利用分簇CGRA体系结构的局部紧耦合特性，将一个迭代限定在一个簇上运行，相邻的迭代在相邻簇上运行的分簇CGRA上模调度算法。这种基于簇的模调度策略通过循环展开和扩展循环体，能够很好地在CGRA的各个簇之间开发循环级并行。所采用的贪心调度算法能快速高效地完成循环核心在一个簇上的调度。这种方式的模调度无需进行复杂的路由映射过程，很好地解决了路由优化过程过于复杂这一难题，实验表明，这种基于簇的模调度方法极大地节省了映射时间。相比其他已有的算法，本文所提出的方法在分簇CGRA结构上能够更好地实现循环流水，更大程度地实现程序加速。
　　5）在可重构加速部件方面，针对不适合在可重构结构上实现的Turbo乘积码算法，设计并实现灵活可配置的VLSI加速部件结构；分析了FFT和Viterbi算法的共性，设计并实现了可重构的算法加速部件。本文对信道编解码中常用的Turbo乘积码的解码算法的过程和计算进行了优化，相对于原算法，优化后的算法在性能上有一定提升，并且更适合高效的硬件实现。所设计的Turbo乘积码解码器不仅面积效率高，而且支持多种码型，能满足不同通信标准的需要。此外，本文针对FFT和Viterbi这两种无线通信中频繁使用的算法，分析二者的算法过程，发现他们在计算结构和访存模式上存在相似性，因而两个加速部件的ASIC实现可以共享部分硬件单元。本文设计并实现了可重构的Viterbi和FFT加速部件，相对于两种分立的加速部件资源开销之和，可重构结构的加速部件面积节省了20％。通过重构，可以完成两种不同的功能，增强了灵活性的同时保持了ASIC加速部件的高效率，更适合于软件无线电平台对于性能和灵活性的要求。

目录

封面

声明

目录

中文摘要

英文摘要

第一章 绪 论

1.1 研究背景

1.2 相关研究工作

1.3 本文的主要工作

1.4 论文结构

第二章 新型粗粒度可重构阵列体系结构研究

2.1 引言

2.2 CGRA的缺陷和不足

2.3 分簇的CGRA体系结构

2.4 实验与结论

2.5 本章小结

第三章 面向特定应用的可重构阵列设计方法

3.1 引言

3.2 问题描述与分析

3.3 面向特定应用程序的可重构阵列设计方法

3.4 实验与结果分析

3.5 小结

第四章 可重构阵列计算中的指令级并行

4.1 引言

4.2 现有指令级并行方法的局限性

4.3 采用蚁群优化算法的映射方法

4.4 实验结果与分析

4.5 小结

第五章 可重构阵列计算中的循环级并行

5.1 引言

5.2 CGRA中循环级并行问题的现有方法及其局限

5.3 基于遗传算法的模调度

5.4 分簇CGRA上的模调度

5.5 实验与结果分析

5.6 小结

第六章 可重构加速部件研究与实现

6.1 引言

6.2 可配置Turbo乘积码解码器研究与实现

6.3 可重构FFT和Viterbi解码器研究与实现

6.4 小结

第七章 结束语

7.1 论文工作总结

7.2 课题研究展望

致谢

参考文献

作者在学期间取得的学术成果