《SpMT WaveCache开发数据流计算机中的推测多线程》由会员分享，可在线阅读，更多相关《SpMT WaveCache开发数据流计算机中的推测多线程（15页珍藏版）》请在金锄头文库上搜索。
1、计算机学报2009 年 7 期SpMT WaveCache:开发数据流计算机中的推测多线程裴颂文, 吴百锋 (复旦大学 计算机科学技术学院, 上海市 200433)摘摘 要要推测多线程技术(Speculative Multithreading, SpMT)通过推测地执行多个线程来开发线程级并行性,是提高超标量处理器性能的一种有效方法.该文增加了额外的硬件单元,比如线程同步单元(Thread Synchronization Unit, TSU),线程上下文表(Thread Context Table, TCT)和线程内存历史表(Thread Memory History, TMH),扩展了事务性
2、内存系统,提高了基于波标量指令集系统结构(WaveScalar ISA)实现的 WaveCache 模拟器的性能.同时,该文还提出了一种新的两级线程级事务提交机制.最后,采用了 6 个来自 SPEC,Media 和 Mibench 测试程序集的真实测试程序,评估了推测多线程 WaveCache(SpMT WaveCache)的性能.实验表明, SpMT WaveCache 比超标量系统结构提高了 2-3 倍的性能,是一种有效的开发动态数据流计算机性能的方法.关键词关键词动态数据流计算机; 推测多线程; 事务性内存; 波标量指令集中图法分类号中图法分类号TP391 SpMT WaveCache:
3、 Exploiting Speculative Multithreading for Dataflow ComputerPEI Song-Wen, WU Bai-Feng(School of Computer Science, Fudan University, Shanghai 200433)AbstractSpeculative Multithreading(SpMT) increases the performance by means of executing multithreads speculatively to exploit thread-level parallelism.
4、 We expanded the transactional memory system of WaveCache by adding extra hardware components, such as Thread Synchronization Unit(TSU), Thread Context Table(TCT) and Thread Memory History(TMH), to improve the performance of SpMT WaveCache which is built on WaveScalar instruction set architecture(IS
5、A). Furthermore, a novel two-levels commit method was proposed to support submitting thread-level transactions. Finally, we evaluated the SpMT WaveCache with 6 real benchmarks selected from SPEC, Mediabench and Mibench benchmarks. According to the experimental results, the SpMT WaveCache outperforms
6、 superscalar architecture ranging from 2X to 3X, and it also performs greater gain over original WaveCache and Transactional WaveCache. Therefore, the SpMT WaveCache is a good way to exploit thread-level parallelism of dynamic dataflow computer.Key words dynamic dataflow computer; speculative multit
7、hreading(SpMT); transactional memory; WaveScalar本课题得到上海市重点学科建设项目基金(B114)和 AMD 大学合作计划基金的资助. 裴颂文, 男, 1981 年生, 湖南省邵东县人, 博士, 主要研究领域为计算机系统结构, 嵌入式系统设计, 软件自动化测试. E-mail: . 吴百锋, 男, 1964 年生, 教授, 博士生导师, 主要研究领域为计算机系统结构, 计算机辅助设计, 嵌入式系统设计.计算机学报2009 年 7 期1 引言随着单核心处理器频率的不断提高,由此带 来的负面影响如线延迟,通信开销,设计复杂性, 功耗等也越来越严重.目前
8、,大多数研究机构和 生产厂商一致认为多核处理器或者片上多处理 单元将取代超标量单核心处理器.因此,摩尔定 律的有效性得到了延续.但是,在过去几十年里, 处理器的设计主要是针对 von Neumann 系统结 构,开发指令集并行 (ILP),数据级并行 (DLP)和 线程级并行 (TLP).然而,这些传统技术在目前阶 段受到了极大的约束.从根本上讲,这些约束源 自于存储墙 (Memory Wall)、功耗墙 (Power Wall)和指令级并行墙 (ILP Wall). 单片多核处 理器(CMP)和 Many cores 的提出,使现代计算机 系统的功耗墙问题变得日趋缓和;而存储墙问题 根源于广
9、泛采用的 von Neumann 计算机系统结 构中日益扩大的微处理器和主存在处理速度上 的差距.有研究表明:目前复杂的微处理器架构 在 ILP 性能上的提升将变得十分有限,而数据流 计算机模型不但突破了存储墙问题,而且它也很 自然地迎合了当前多核心系统架构的发展趋势. 因此,我们针对一种典型的动态数据流系统结构 波标量系统结构(WaveScalar)1,2,开发其潜在 的推测多线程并行性. 波标量系统结构设计了一种顺序内存机制- -有序波内存(wave-ordered memory),保证了强制 性语言在内存系统中的顺序执行.因此,我们的 工作主要是通过增加新的内存管理与控制模块, 研究多线
10、程在事务性内存支持下的推测执行.本 文的贡献主要有:(1)设计了有效的多线程编程与 产生机制;(2)为多线程推测执行设计了新的硬件 结构,如线程同步单元(Thread Synchronization Unit, TSU),线程上下文表(Thread-Context-Table, TCT)和线程内存历史表(Thread-Memory- History, TMH);(3)采用真实程序测试了推测多 线程 WaveCache (Speculative Multithreading WaveCache, SpMT WaveCache)的性能,并与超 标量多线程系统,波标量系统以及事务性波标量 系统进行了
11、详细的对比.实验结果表明,SpMT WaveCache 比超标量系统结构提高了 2-3 倍的 性能,对于初级的 WaveCache 和事务性 WaveCache 都获得了较高的加速比.2 波标量 WaveScalar 系统结构波标量(WaveScalar)系统结构是一种动态的 数据流指令集计算机系统结构,采用非集中式方 式执行,具有良好的扩展性.Swanson 等1,2实现 了 WaveScalar 指令集系统结构的模拟平台 WaveCache. WaveCache 不同于其他数据流计算 机的重要特点在于,它支持传统的强制性语言 (如 C,C+,Java 等)的编程和执行模型.对于程序 员来说
12、,无须学习新的数据流程序编程语言(如 Brook3, ImpulseC4等),减轻了程序员的学习压 力和适应能力,促进了这类新型数据流计算机系 统的发展.2.1 初级的初级的WaveScalar系统结构系统结构2.1.1 波(Wave)和波号(Wave-Number) 数据流计算机模型没有程序计数器(PC)完 成取指功能,也没有寄存器文件负责传递相关指 令之间的数据.在数据流计算机模型中,计算机 程序用数据流图来表示.数据流图中的一个节点 表示一条指令,连接节点的有向边传递指令间的 执行顺序,也隐含了指令之间的数据依赖关系. 当一个节点的所有输入边上的数据都准备就绪 后,该节点所表示的指令就会
13、被点火. WaveScalar 系统结构为了表达指令执行的 顺序关系和访存顺序关系,定义了波(wave)及其 顺序编号.波是由基本块组成的有向无环图,类 似于超标量系统结构中的超级块.但是,波跟超 级块不同的是它具有多入口和多出口并且可以 包含控制流合并指令,而超级块只允许单入口和 单出口.在每个波的入口处,用 Wave-Advance 指 令产生一个该波的唯一顺序号,即为波号(wave number).一个波内的所有数据值都带有波号 (wave number)标签,以区分相同数据值属于不同 的波.带波号标签和数据值组成一个令牌(token). 比如波号为 W,数据值为 v 的数据可以表示成令
14、 牌 W.v.2.1.2 控制指令 WaveScalar 数据流执行模型能显式表示数 据流路径间的并行性.其分布式的执行方式不需 要单独设置程序计数器或其他集中式的结构来 控制程序的执行顺序.因此,如何将控制依赖关 系转化为数据依赖关系是数据流计算机的一项 基本任务.计算机学报2009 年 7 期WaveScalar 设计了 STEER 指令控制数据进 入正确的数据流管道.STEER 指令对应于传统的 分支(Branch/Split)指令,它也可以用来描述循环 程序段 该指令也可以和普通的算术运算指令组合 成新的指令.比如 ADD-AND-STEER 指令有三个 输入,一个选择子(select
15、or),两个输入操作数,分 支结果依赖于选择子. 指令为选择指令,包括 两个输入操作数和一个选择子,选择子控制分支 输出结果为两个输入操作数中的某一个, 指 令对应于传统的条件分支转移指令.-1是 的 反向操作,用选择子选择一个输入操作数进入两 个可选的输出通道中的一个. 指令和 -1指令 为波标量系统建立了控制指令逻辑,这样就能用 它们表达基本的循环过程.2.1.3 有序波内存(Wave-ordered Memory) WaveScalar 用有序波内存系统(Wave- ordered Memory)规范动态数据流计算过程中的 所有内存操作顺序.用三元组表 示前一个内存操作指令的顺序号,当前
16、内存操作 指令的顺序号和后继内存操作指令的顺序号.这 样,就能为一个波内的所有内存操作指令表达执 行顺序关系,并建立一个指令链.WaveCache 中 实现的有序波(Wave-ordered)内存机制,解决了 数据流计算机中的顺序存储(memory ordering) 问题,从而保证了该系统具备支持强制性编程语 言的能力. 每个波也被设置一个有序的标识符号,从而 保证波在 WaveCache 中的顺序执行性.有序波 标识(wave-ordering annotations)的设置需要满足 两个性质:(1)必须保证在一个波内的存储操作满 足正确的执行顺序.这主要是通过给每个波内的 存储操作设置一个顺序号(Sequence number),经 过一个波的所有路径上的顺序号都要递增.从而,如 果有一个内存操作指令的顺序号大于另一个内 存操作指令的顺序号,那么具有较大顺序号的内 存操作指令要放在较小内存操作指令的后面执 行;(2)有序波内存必须检测所有的内存操作何时
