分片式处理器体系结构上的超块优化技术

摘要

在过去的十年中，微处理器的性能以每年大约50-60％的速度提升。然而．随着芯片制造工艺逐步接近硅原子的尺寸，微处理器学术界和工业界面临着诸多尚待解决的问题：比如处理器功耗快速增长导致散热量快速增加，芯片内部线延迟加长导致信号在单个时钟周期内所能到达的功能部件数目减少等一系列问题，处理器性能提升的两架马车——时钟频率和IPC(Instructions Per Cycle)正在失去以往的前进动力。种种迹象表明传统的处理器体系结构已经不能适应新的制造工艺的发展，各研究团队相继开发了新的处理器体系结构来取代传统的处理器体系结构，比如分片式处理器体系结构等。与此同时，新的分片式处理器体系结构对编译技术也提出了新的要求，超块形成和优化技术与分片式处理器体系结构之间的无缝融合成了值得研究的领域。
　　 本文研究了分片式处理器体系结构的优点和潜力以及它和超块形成和优化技术之间的结合性，探讨了分片式处理器体系结构上指令之间的自接数据传送问题，提出了基于剖析信息和关键路径长度的软件扇出树生成算法与基于基本块特征的MOV指令精简启发式算法，给出了它们的理论分析，在TRIPS编译器和调度器上实现了算法并对其进行了实验性能测试。基于剖析信息和关键路径长度的软件扇出树生成算法利用了程序剖析信息和块的静态特征，改进了Huffman算法并创新性地把它运用到了软件扇出树生成领域，该算法可以优化软件扇出树的结构，优先给执行概率高和处于关键路径上的指令播送数据，因而可以提高程序块的ILP。基于基本块特征的MOV指令精简启发式算法利用程序基本块的特征信息，比如依赖链首尾宽度比、依赖链长度以及分支指令的跳转概率等信息来指导谓词化过程，该算法可以有效地减少块内MOV指令数，提高块内有效指令比例，降低由谓词化所带来的执行延迟。
　　 本文的研究表明分片式处理器体系结构和超块技术之间可以很好地融合，分片式处理器体系结构可以利用超块结构宋暴露程序中的ILP给硬件执行基底，块内指令之间的直接数据通信也可以在分片式处理器体系结构上作为全局命名空间机制的补充得到应用。块内指令之间直接通信模式的代价可以通过基于基本块特征的MOV指令精简算法和基于剖析信息和关键路径长度的软件扇出树生成算法来有效降低。此外，本文的研究也说明了剖析信息可以在调度器中得到很好地应用。

目录

文摘

英文文摘

论文说明：图表目录

声明

第1章 绪论

1.1 课题研究背景

1.2谓词执行技术相关工作

1.3本文的研究工作

1.4本文的组织结构

第2章 分片式处理器体系结构介绍

2.1 Raw处理器体系结构介绍

2.1.1 微型可复制单元

2.1.2可编程的整合互联网络

2.1.3控制

2.1.4多粒度操作

2.1.5 可配置性

2.2 EDGE处理器体系结构介绍

2.2.1 TRIPS的超块编译

2.2.2 TRIPS编译

2.2.3 超块形成

2.2.4谓词执行

2.2.5生成合理的超块

2.2.6物理调度

2.2.7对并行性的支持

2.3本章小结

第3章 超块形成和优化技术

3.1 Scale编译器介绍

3.2 TRIPS后端

3.3块选择

3.4 代码转换

3.4.1 尾复制

3.4.2循环剥离技术

3.4.3 节点分裂

3.5 If转换

3.5.1支配者和反支配者

3.5.2 RK算法

3.6谓词化相关的优化

3.6.1 指令提升

3.6.2重命名和提升

3.6.3 指令合并

3.7谓词层次图

3.8 传统优化

3.9调度

3.10本章小结

第4章 MOV指令精简启发式算法

4.1 MOV指令的产生

4.2 MOV指令比例

4.3 相关工作

4.3.1 传统谓词化方法

4.3.2隐式谓词方法

4.3.3推测提升方法

4.4 基于基本块特征的MOV指令精简启发式算法

4.4.1 影响谓词化过程的基本块特征信息

4.4.2启发式表达式

4.5 实验性能

4.5.1 MOV指令比例

4.5.2执行周期数

4.6 本章小结

第5章 基于剖析信息和关键路径长度的软件扇出树生成算法

5.1 研究背景

5.2相关工作

5.2.1 Huffman编码算法

5.2.2 Hartley和 Casavant算法

5.3 基于剖析信息和关键路径长度的软件扇出树生成算法

5.3.1 算法思想

5.3.2算法复杂度分析

5.3.3软件扇出树的生成过程

5.4实验结果

5.5本章小结

第6章 论文总结

6.1 研究成果与创新

6.2进一步研究工作

致 谢

在读期间发表的学术论文与取得的研究成果

参考文献

在读期间参与的科研项目