CMP结构下基于Cache感知线程级并行优化研究

摘要

多核时代的到来，处理器的运算能力得到了很大的提升.但由于处理器和主存之间的发展速度的不均衡，“存储墙”的问题越来越严重，成为影响系统性能的瓶颈。在多核体系结构下，多级存储器的出现缓解了这种压力。
　　在典型的CMP(Chip Muti-Processors)体系结构中，多个核共享Cache，不但改善了存储的性能，而且减小了硬件的使用面积。但在此结构下，由于Cache空间小，多个线程共享Cache，将会造成对Cache空间的竞争，使得共享线程的Cache缺失数增加，对系统的性能是非常不利的。本文的主要工作如下:
　　(1) Cache缺失数是衡量系统访存性能的重要指标，为了有效的利用Cache空间，本文通过收集各个线程的访存信息，使得共享线程的Cache空间的需求总和与共享Cache的空间大小相等并合理的划分线程组，在此问题上本文首先将线程的划分模型抽象为求解子集和的问题，并用快速求解子集和的方法求解子集，将其运用到本文的线程优化划分算法TOP(Thread Optimization Partition)中，获得优化的线程组，减少Cache的缺失数。最后通过simple-scalar仿真工具收集线程的数据信息，执行本文的划分算法，实验结果表明，本文提出的线程划分的优化算法(TOP)在程序的总的缺失数百分比相比贪婪的线程划分算法greedy平均减少了17.48％，相比于随机的线程划分算法Random平均减少了14.26％。
　　(2)在已划分的线程组的基础上，分析线程上的数据在程序执行时访存信息，建立数据分配的执行模型，通过一个实例分析并定义本文多核的数据分配问题，以此来描述线程上的数据优化分配，通过本文提出的多核结构下贪婪数据分配算法(M_GDA)和多核的动态规划算法M_DPA对数据进行优化分配，使得同时执行的线程的访存时间最短，减小程序执行时访存时间。最后在本文的数据分配优化模拟器上运行了10个标准的benchmark测试程序来进行验证。实验结果表明，通过多核的动态规划算法(M DPA)对数据进行优化分配后的访存开销相较于随机数据分配算法(Random)平均提高了16.11％，相较于多核贪婪数据(M GDA)分配算法的访存开销提高了14.08％，在能量开销上相较于随机数据分配算法提高了28.02％，相较于贪婪数据分配算法提高了14.40％。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 研究背景及意义

1．2 国内外研究现状

1．2．1 基于硬件控制Cache的优化研究

1．2．2 基于软件控制Cache的优化研究

1．3 本文的研究内容

1．4 论文组织结构

第2章 相关理论

2．1 多核环境下存储墙问题

2．2 多核的硬件结构

2．2．1 多核处理器分类

2．2．2 本文处理器体系结构

2．3 任务抽象模型

2．4 体系结构软件模拟

2．5 本章小节

第3章 CMP结构Cache感知的线程划分

3．1 问题描述

3．2 线程划分模型

3．2．1 线程划分问题的基本定义

3．2．2 子集和问题

3．2．3 线程划分模型

3．3 求解最优划分

3．3．1 线程划分实例

3．3．2 线程划分的优化算法TOP

3．4 实验分析

3．4．1 SimpleScalar简介

3．4．2 实验配置

3．4．3 线程划分算法比较

3．5 本章小结

第4章 并行执行线程的数据分配

4．1 数据分配问题概述

4．2 数据分配的执行模型

4．2．1 程序分段

4．2．2 多核系统内数据分配执行模型

4．2．3 数据分配的基本定义

4．3 简单实例介绍

4．4 数据分配算法比较

4．4．1 多核贪婪数据分配算法(M_GDA)

4．4．2 多核动态规划数据分配算法(M_DPA)

4．5 实验分析

4．5．1 实验配置

4．5．1 HP CACTI简介

4．5．2 数据分配优化模拟器

4．5．3 不同算法访存时间开销对比分析

4．5．4 不同算法访存能耗对比分析

4．6 本章小结

结论

参考文献

致谢

附录A (攻读硕士学位期间参与科研项目目录)