基于多核架构的线程级并行关键技术研究

《基于多核架构的线程级并行关键技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、东南夫学硕I：学位论义图2-2由间接访存弓I起的模糊依赖图2-2给出了存在模糊依赖的一段示例代码。其中i∈【0，MAXl，idx[i】∈【0，MAX]，且i到idx[i]是【O，MAX]至IJ[0，MAX]的一一映射。首先不考虑这段代码的存在是否有意义，事实上，这段代码改白2．2节将要介绍的Hydra的一个经典例子【11'231。由于idx[i]的随机性，很难确定hash中的某个元素是先执行自增1存储器写操作，还是先执行存储器读操作。基于程序止确性考虑，这段代码虽然简单，但难以划分为多个线程并行加速。如果不关心依赖关系和程序正确性，

2、假设MAX等于16，随机生成一串乱序的idx序列，同时将原程序按MAX均分成为两个子任务分别在ThreadA和ThreadB中并行执行，ThreadA执行前一j卜负载【0，MAX／E)，ThreadB执行后一半负载[MAX／2，MAX)，其实际运行时的依赖关系如图2．3所示。ThreadAThreadB图2．3运行时依赖关系图2-3中线1表示hash【9】本虑按照先写后读的顺序，却发生了先读后写的访存错误。线2表示hash[6】本应先读后写，但发生了先写后读错误。线3表示hash[7]可能发生先写后读错误，也可能发生先读后写错误，取

3、决于当前时刻CPUL1cache写总线的竞争情况。这16个数据包含48个读写操作，但只有3个数据的存储器操作发生了错误的依赖关系。虽然利用现6第_二章具仃模糊依赖的程序自动并行技术研究有的编译手段，无法对图2-2的例子进行线程划分，但如果按图2．3的方法任意划分线程，推测、投机让线程执行，在执行过程记录各个线程对变量的访存历史，根据这些历史及时检测并纠止错误依赖，那么带来的性能加速比还是1卜常可观的。2．2基于推测和事务的线程级并行技术线程级推测和事务存储即是研究如何让任意划分的线程推测地并行执行，在运行时检测并纠错的方法。为了便丁

4、讨论基丁．多核架构的线程级并行技术，本节有必要对已有的几种典型的线程级并行模型进行分析对比。2．2．1HydraHydra是斯坦福大学研究小组丁：1999年发布的一套完整的线程级推测方案[231。如图2．4，Hydra将4个高性能的MIPS处理器内核集成丁一个单芯片上。其中每个处理核内部私有Ll指令和数据cache，处理核之间采用共享L2cache进行通信。DRAMflailm硼。哆图2-4Hydra处理器结构Hydra使用推测度(speculationdegree，SPD)米表示多个线程之间的串行关系。所谓推测度是指推测执行的线程

5、在程序串行序列中的相对位置【23，矧。推测度数值越大，说明推测结果越不可信；发生依赖时，优先考虑推测度小的线程执行结果。Hydra在私有的L1cache中为每个数据附加了一个状态位，用于检测推测执行引起的错误依赖问题。连接L1与L2cache的是一条读／替换总线(read／replacebus)和一条写直达总线(writethroughbus)。写直达总线负责将处理核的写数据传送至L2cache，并使用失效协议维护L1cache的一致性。由丁．推测写结果在提交确认前不能直接写入后级存储，冈此在写直达总线和1,2cache之间，Hyd

6、ra为每个处理器增加了一个名为L2写缓冲(L2writebuffer)的部件，用于暂存推测执行的写操作结果。L2写缓冲收集一定窗口大小内所有推测执行的写操作。总是由推测度最小的线程进行任务提交，如果待提交的数据没有发生错误的访存依赖，则线程成功提交，缓冲区中的相应内容永久写入L2cache；否则线程卷回重启，缓冲区中的cache行将被丢弃。基于性能考虑，Hydra为每个处理器内核配备了一个推测控制协处理器以负责运行时系统的运行。“运7东南人学硕I：学位论文行时系统”是一组运行丁推测控制协处理器的软件控制程序的集合。推测控制协处理器包

7、含若干个控制寄存器、一个二级cache标志位的副本集合、一个有限状态机、以及一个中断逻辑。有限状态机用以跟踪当前处理器相对于其他处理器的推测顺序。中断控制逻辑负责处理中断，当发生如数据错误引用事什时，中断逻辑根据中断向量列表启动相应的处理程序。Hydra有以下5个方面值得探讨：1)cache一致性协议基于cache行，粒度较大。一般而言，一个cache行可表达16B，32B，甚至64B的数据。因此对位于cache行中的某个变量推测读写，容易扩人推测状态剑同一cache行中的其他确定变量。如图2．5，Hydra采用了细粒度的状态描述，

8、以字长为单位，1个状态位描述1个字长数据的状态，有一定的存储开销。机器内部以字节为存储的基本单位，对于“字”长度以下的变量类型，仍然存在推测状态粒度过粗的问题。图2-5Hydra对L1cache的状态扩展2)推测度的表示。cache必