（计算机系统结构专业论文）一个支持事务存储的多核处理器结构设计.pdf

中国科学技术大学硕士学位论文 摘要 单芯片多处理( c h i pm u l t i p r o c e s s i n go rc h i pm u l t i p r o c e s s o r ，c m p ) 通过 在单块芯片上集成多个处理单元，在芯片内部共享缓存，提高了缓存利用率， 简化了芯片设计的复杂度。但是，在c m p 结构上采用由用户显式制导的共享存 储并行程序编程模型，使用锁和同步变量来实现同步的方法存在很大的局限性。 事务存储( t r a n s a c t i o n a lm e m o r y , t m ) 模型通过事务执行的原子性和可串行性， 为c m p 结构提供了程序并行执行和同步的方法，编程模型简单，有利于程序并 发性的发掘。 为了进行c m p 结构上t m 模型的研究，我们设计了一个支持t m 的c m p 结构t m c m s ( t r a n s a c t i o n a l m e m o r yb a s e dc h i pm u l t i p l e s u p e r s c a l a r ) ，并设计实 现了t m c m s 的模拟器o p e n c m p 以及软件支持。本文详细介绍了t m c m s 结 构模型设计和模拟器以及软件支持的设计实现。 本文主要的研究内容和成果包括以下几个方面：( 1 ) 详细分析了t m 模型 技术的现状和发展，提出了t m 模型分类方法，深入比较了些主要的硬件事 务存储模型实现的优缺点；抽象了事务存储模型最基本的特征，提出了四个基 本组成模块。( 2 ) 以简化硬件设计和可扩展性为目标，围绕四个核心事务存储模 型组成模块，定义了事务的执行控制过程，划分了软硬件支持，设计了一个支 持事务存储的c m p 结构t m c m s ，包括基本结构、执行模型、编程模型和线程 划分方法。( 3 ) 为验证t m c m s 结构设计，设计和实现了模拟器o p e n c m p 。在 模拟器设计过程中，解决了事务存储模型基本组成模块的实现、多核处理器扩 展、事务存储性能评价模型三个关键问题。此外，还设计了t m c m s 的软件支 持部分，包括事务初始状态数据结构和事务相关中断处理程序。( 4 ) 选取f f t 程序作为基准测试程序评估了t m c m s 设计方案。从以下两个方面进行性能评 价：处理单元个数和指令c a c h e 共享对于性能影响：q t m c m s 的软件模型 实现的开销。 初步实验表明，t m c m s 性能随着处理单元个数增加而增加，具有良好的 可扩展性，可以发掘程序潜在的并行性。 关键词：处理器体系结构；单芯片多处理；事务存储模型；处理器模拟器；性 能评估；事务执行模型 v l a bs t r a c t c m pi sa l m o s tal i n e a ri n t e g r a t i o no fe a s yt od e s i g n ，v e r i f ya n dd e b u g c o e s c o m p l e x i t yd o e s n ts c a l ee x p o n e n t i a l l y w h e nm o r ec o r e sa n dm o r et h r e a d sa r ea d d e d b u t i ti sd i 伍c u l tt ow r i t ec o n c u r r e n tp r o g r a m s f o rc m pw i t hl o c k s ，f o rt h e c o m p l e x i t yo fe n s u r i n gp r o p e rs y n c h r o n i z a t i o n t r a n s a c t i o n a lm e m o r y ( t m ) g i v e s a s o l u t i o nt os i m p l i f yp a r a l l e lp r o g r a m m i n gb ye x e c u t i n gc o d ew i t h i n t r a n s a c t l o n s f o rs u p p o r t i n gt h er e s e a r c ho nt r a n s a c t i o n a lm e m o r yf o rc m p , w ed e s i g n e d t m c m s ac m pa r c h i t e c t u r ew i t ht r a n s a c t i o n a lm e m o r ys u p p o r ta n di m p l e m e n t e d t h es o f 帆a r ea n dh a r d w a r es u p p o r t t h i sp a p e ri n t r o d u c e st h et m c m s a r c h i t e c t u r e ， t h eo p e n c m ps i m u l a t o ra n ds o f t w a r es u p p o r t t h er e s e a r c hc o n t e n ta n da c h i e v e m e n to ft h i s t h e s i si n c l u d et h ef o l l o w i n g a s p e c t s ：( 1 ) s u m m a r i z e dt h et e c h n o l o g yo ft m m o d e l ，c l a s s i f i e dt h et mt e c h n o l o g y a n da j l a l y z e da l lk i n d so ft ma r c h i t e c t u r e i nd e t a i l ；p u tf o r w a r df o u 。m a m c o m p o n e n t sb ya b s t r a c t i n gt h ek e yf e a t u r e so ft m m o d e l ；( 2 ) d e f i n e dt h ec o n t r o lo f t h r e a de x e c u t i o n ；d e v i d e dd e s i g ni n t oh a r d w a r ea n ds o f t w a r es u p p o r t ；d e s i g n e dt h e t m c m sa r c l l i t e c t u r e ，i n c l u d i n gt h e e x e c u t i o nm o d e l ，p r o g r a m m i n gm o d e ia n d t 1 1 r e a dd i v i d i n gm e t h o di nc o n s i d e r a t i o no fe a s yt od e s i g na n ds c a l a b l eb a s eo nt h e f o u rm a i nt mc o m p o n e n t s ；( 3 ) d e s i g n e da n di m p l e m e n t e dt h eo p e n c m ps i m u l a t o r a n dt h es o r w a r es u p p o r tf o rv e r i f y i n gt h ed e s i g no ft m c m s ；s o l v e d t h r e ei m p o r t a n t d r o b l e m si ns i m u l a t o rd e s i g n ：d e s i g no fm a i nc o m p o n e n t so ft m ，t h em u l t i 。c o r e s u p p o r t a n dp e r f o r m a n c ee v a l u a t i o n o ft m ；a n dt h es o f t w a r es u p p o r t w a s i m p l e m e n t e db yb o 也t h ei n t e r r u p ts e r v e rp r o g r a ma n dl i bf u n c t i o n ；( 4 ) t h e f f t p r o g r a mi s s e l e c t e da st h eb e n c h m a r kt oe x p e r i m e n t a n dv e r i f yt h ed e s i g no f t m c m s e x p e r i m e n t e d f r o mf o l l o w i n ga s p e c t s ：t h e e f f e c to fi n c r e a s i n g p r o c e s s o ru n i t ( p u ) n u t u b e ra n ds h a r i n gi n s t r u c t i o nc a c h e ； t h eo v e r h e a do f t h e s o f t w a r es u p p o r t o u re v a l u a t i o ns h o w e dt h a tt m c m s i ss c a l a b l e ，p e r f o r m a n c ei si n c r e a s e dw i t h m en u m b e ro fp u ，t h ea p p l i c a t i o nc a na c h i e v eh i g hp a r a l l e l i s m w i t ht h es i m p l e p r o g r a m m i n g m o d e l k e v w o r d s ：p r o c e s s o ra r c h i t e c t u r e ；c h i pm u l t i p r o c e s s o r ；t r a n s a c t i o n a l m e m o r y ； p r o c e s s o rs i m u l a t o r ；p e r f o r m a n c ee v a l u a t i o n ；t r a n s a c t i o n a le x e c u t i o n 中国科学技术大学硕士学位论文 图目录 图1 1 h y d r ac m p 结构4 图1 2 事务执行生命周期6 图2 1t l r 的实现方法1 2 图2 2u t m 结构1 3 图2 3x s t a t e 数据结构和冲突检测一1 4 图2 4v t m 系统的具体实现1 5 图2 - 5 t c c 系统结构一1 7 图2 - 6 h y d r a 的微体系结构2 0 图3 1 t m c m s 单个节点结构一2 3 图3 2 t m c m s 执行模型一2 6 图3 3 t m c m s 处理缓存溢出一2 8 图3 4 串行编程模型和t m c m s 编程模型3 4 图3 - 5 t m c m s 执行的静态调度划分一3 5 图3 - 6 循环并行化源到源转换3 7 图4 1 目标平台可执行二进制代码的生成流图3 9 图4 2 指令添加功能实现4 4 图4 - 3 c a c h e 模拟状态转换图4 8 图5 1 初始状态注册( 1 0 9 ) 模块实现51 图5 2v i o l a t i o ni n t 中断处理程序实现示例一5 4 图6 1 处理单元个数对于i p c 的影响5 8 图6 2 指令c a c h e 对于i p c 的影响5 9 图6 3 控制软件的开销5 9 一个支持事务存储的多核处理器结构设计 表目录 表1 1 现有处理器体系结构3 表3 1t m c m sc a c h e 一致性维护一3 3 表4 1 事务处理指令集描述4 3 表4 2 事务处理寄存器4 5 表6 1 模拟器配置参数：5 6 v 一 一个支持事务存储的多核处理器结构设计 1 1 课题的研究背景 第1 章绪论 上个世纪8 0 年代，c p u 设计的主要转变是从c i s c 指令集体系结构转向 r i s c 指令集体系结构，使得c p u 单核的设计更加简单、高效。9 0 年代的c p u 设计主要致力于努力提高c p u 单核的指令级并行性( i n s t r u c t i o n l e v e l p a r a l l e l i s m ，i l p ) 和主频。最终导致单核的复杂性和功耗急剧上升，线延迟问题 开始限制这种集中控制的单核结构继续发展，设计和验证的复杂度越来越成为改 变结构的主导因素 1 】。 近年来，我们目睹了商业c p u 设计正在由仅开发i l p 的单线程单核结构转 向利用线程级并行性( t h r e a d l e v e lp a r a l l e l i s m ，t l p ) 的单芯片多处理器( c h i p m u l t i p r o c e s s i n go rc h i pm u l t i p r o c e s s o r ，c m p ) 和多线程( m u l t i t h r e a d i n g ，m t ) 结构。例如，i n t e l 己在其p e n t i u m4 中采用了同时多线程( s i m u l t a n e o u s m u l t i t h r e a d i n g ，s m t ) 2 技术，命名为超线程( h y p e r t h r e a d i n g ) 技术 3 】。i b m 的p o w e r4 芯片采用的是单芯片多处理器结构 4 ，在单个芯片上集成了两个4 发 射超标量处理器；p o w e r 5 进一步引入了s m t 技术，基于s m t 核构建c m p 结 构 5 】。c m p m t 结构将多个较简单的核集成到单个硅片上，在每个核上执行一 到多个线程应用，通过增加核数和线程数，使得芯片随处理器核的增加具有更好 的可扩展性，有效地控制功耗，大大降低芯片系统设计和验证的复杂度。 但是，在c m p 结构上采用由用户显式制导的共享存储并行程序编程模型， 使用锁和同步变量来实现同步的方法存在很大的局限性。事务存储( t r a n s a c t i o n a l m e m o r y , t m ) 模型通过事务执行的原子性和可串行性，为c m p 结构提供了程序 并行执行和同步的方法，简化了编程模型，有利于程序并发性的发掘 6 。 本课题在充分调研当前c m p 结构和事务存储模型的基础上，抽象c m p 结 构和事务存储模型结构关键特性，设计了一种支持事务存储模型的c m p 结构一 - - t m c m s ( t r a n s a c t i o n a l m e m o r yb a s e dc h i pm u l t i p l e s u p e r s c a l a r ) ，并通过修改广 泛使用的超标量体系结构模拟器s i m p i e s c a l a r 7 8 】实现了t m c m s 的模拟器 o p e n c m p ，同时对c m p 上事务存储模型进行了深入地研究。 1 1 1 处理器体系结构研究的发展 2 1 世纪，计算机系统的核心评价指标由高性能转向高效能，设计驱动由计 中国科学技术大学硕士学位论文 算为中心的应用转向以数据为中心的应用，实现技术由深亚微米工艺转向纳米工 艺，这些变化将对微处理器体系结构技术的未来发展产生深刻的影响。 微处理器性能的提高主要依靠两条途径：一是半导体工艺的进步，二是处理 器体系结构的发展。在下一个十年，半导体工艺技术仍将继续推动处理器的时钟 频率和集成度稳步提高。多年以来，芯片产业一直按照摩尔定律在飞速发展，即 单位面积芯片上的晶体管数量大约每1 8 个月增加一倍。到2 0 1 0 年，高性能处理 器在单芯片上将集成1 0 亿只晶体管。对于处理器体系结构设计人员而言，采用 什么样的策略来充分利用这样充裕的硬件资源，实现更高的性能将是微处理器体 系结构研究面临的一个巨大的机遇和挑战【9 。 传统的通用微处理器芯片设计主要采用冯诺依曼模型，利用指令级并行性 开发资源集中的单处理器单指令流的芯片。7 0 年代，微处理器的进步主要是提 高数据通路的宽度和对存储管理提供硬件支持。8 0 年代，工艺和集成电路技术 的发展，允许将大型机上的很多体系结构技术，如：超标量、多级存储、推测执 行等指令级并行处理技术在微处理器芯片上实现。进入9 0 年代，人们继续为提 高微处理器的指令级并行度做不懈的努力，但实际的商用微处理器性能的提高越 来越多地得益于时钟频率的提高。在9 0 年代的1 0 年中，微处理器的主频由9 0 年的3 3 m h z 提高到2 0 0 1 年的2 g 以上，仅由时钟频率带来的性能提高就占4 5 。 时钟频率的提高一方面源于工艺的进步提供了开关速度更快的晶体管；另一方面 更多地源于深度流水的结构设计 1 。过去c p u 速度的增长遵循摩尔定律，目前， 通过使用传统技术的途径，c p u 速度改善正在趋缓。在9 0 年代，c p u 速度以每 年增加6 0 速度改善；从2 0 0 0 到2 0 0 4 年，以每年增加4 0 的速度改善；而2 0 0 5 年只改善了2 0 。 传统上，开发i l p 主要有两种方法：一是采用超流水结构提高主频，增加每 秒钟执行的指令数。另一是采用超标量或超长指令字结构增加指令发射和执行的 并行度，每个周期发射多条指令到多个功能部件上执行，从而提高每个时钟周期 执行的指令数。但是，硬件复杂度、应用中固有的指令级并行性、长延迟事件等 限制着传统的处理器开发i l p 。同时随着工艺的发展，最终导致单核的复杂性和 功耗急剧上升，线延迟问题开始限制这种集中控制的单核结构继续发展，设计和 验证的复杂度越来越成为改变结构的主导因素。 为了能够充分利用数目众多的晶体管，需要设计与巨大规模芯片相适应的计 算机体系结构。针对这个问题的研究，如表1 1 所示，现有的处理器体系结构研 究主要包括了超大超标量处理器体系结构( l a r g e s c a l es u p e r s c a l a r ) ，同时多线程 处理器体系结构，单芯片多处理器体系结构，智能存储芯片体系结构( p r o c e s s o ri n m e m o r y ，p i m ) ，以及多型处理器体系结构。 一个支持事务存储的多核处理器结构设计 表1 1 现有处理器体系结构 体系结构优点缺点相关研究 超大超标因为该结构只是开发指令级功耗急剧上升，线延迟问题 参见【9 1 0 量处理器并行性，所以不需要修改现有制约集中控制的单核结构 结构 软件。继续发展，设计和验证复 杂。 同时多线隐藏指令级并行方法中、出现功耗问题依然严重，因为还 s m t 2 ， 程处理器的各种情况的延迟。开发和利是使用了超标量核的结构， h y p e r t h r e a d 3 】 结构用应用中粗粒度并行性，提高 设计和验证依然复杂。 处理器的资源利用率。 单芯片多多个简单的核在片上互联，设软件需要并行化，并行程序 h y d r a 11 】， 处理器结计和验证简单，功耗小且均衡 设计模型复杂。 p o w e r 4 4 ， 构分配，可以开发细粒度并行 p o w e r 5 5 】 性，解决线延迟问题。 智能存储将处理器与存储器做在同一任务需要被分为多个块，分 p i m 1 2 】， 芯片体系块芯片上，这样可使访存延时配给各个p i m 及节点。存储 结构减少5 1 0 倍以上，存储器带配置很复杂。处理器与存储 宽增加5 0 1 0 0 倍以上。器结合设计复杂。 多型处理特点：解决应用的多样性问题。专用化的体系结构匹配于 r a w 1 3 ， 器体系结 特定应用领域的并行性特征，达到高性能。降低了芯片设计 s m a r t m e m o r y 14 ， 构 难度。 t r i p s 15 】 1 1 2c m p 技术 当前主流商用处理器体系结构已经由开发指令级并行技术的超标量体系结 构转向c m p 结构。如图1 1 所示，c m p 技术将多个处理单元( 核) 放置在同一个 芯片上，多个处理单元( 核) 都有完整的系统结构资源。处理器可以共享或者不共 享片上c a c h e 。片上的多个处理单元( 核) 并行地执行多个线程。c m p 结构有以下 几个优势： 中国科学技术大学硕士学位论文 o r 埘删nt d e m a t y1 1 0n e v t 船 图1 1 h y d r ac m p 结构 ( 1 ) 线延迟问题 随着深亚微米工艺技术条件的应用和芯片工作频率的不断提高，芯片互连线 越来越成为一个限制芯片性能提高和集成度提高的关键因素：互连线延迟正逐渐 超过器件延迟。当线延迟使得芯片中信号的传递超过一个时钟周期，则相应的大 型单核处理器设计如何提供部件之间的快速通信，以及如何设计更深的流水线使 得有足够的时间来传递信号将成为一个很大的问题。这个问题很难解决，则需要 很多的缓存来在一个周期的结尾缓存结果，设计问题复杂化。相反，c m p 结构 中每个处理单元( 核) 只占用芯片上很小的一块区域，减小了关键路径的长度，只 有对于周期不敏感的非关键路径才使用长连线。 ( 2 ) 开发细粒度线程级并行性 现有的多处理器系统能够很好的开发应用的粗粒度并行性，例如现有的一些 并行编译器能够很好的挖掘一些科学计算应用中的潜在并行性。粗粒度并行性要 求每个线程是一个很好的自治域，线程之间的通信尽量少，一般几千条指令才进 行通信。此外，现有的多处理器系统也能够很好地提供操作系统级别的并行性， 每个系统进程就是一个单个运行的实例占用处理器，在这种情况下由操作系统来 负责调度。 由于线程之间的通信延迟太大，现有的多处理器结构不能很好的开发细粒度 并行性。c m p 结构能够提供快速和高效的同步方法，所以同步时间减少，大量 的时间用在计算处理上面。将所有的处理器做到同一个芯片上面能够减少通信代 价，使得 0 0 指令左右做一次通信仍然能够提高系统的速度成为可能。c m p 的 出现为开发应用的线程级细粒度并行性提供了可能。 ( 3 ) 设计验证容易 处理器设计和验证的复杂度在不停的增加，设计和验证一个商用处理器是一 个艰巨的任务。因此，设计者希望能找到一种既能够提供简化的设计又能够提供 高性能的方案。c m p 处理器是一种高性能并能够提供简单硬件设计的方案。 一个支持事务存储的多核处理器结构设计 c m p 处理器利用相对简单的多个超标量处理器核来组成多核结构，多个处 理器核的可复用性大大降低了设计的复杂性。简单的控制逻辑可以更容易获得高 主频，由于主频的增加和多个线程同时运行，能够在降低设计的复杂度的同时提 高系统性能。 ( 4 ) 功耗 芯片密度的增加、电路工作速度的提高使得集成电路功耗明显增加。处理器 的晶体管数目越来越多、速度越来越快，同时功耗也是越来越大。传统的处理器 芯片有一个单独的执行单元( 核) ：一个核是一个或多个线程以及执行资源的集 合。计算机的主频的加快集中在单个核上面进行。c m p 处理器在芯片内部有多 个用于并行执行的速度较慢的核。c m p 单个核的速度较慢，处理器消耗较少的 热能，产生较少的热量。同时，原来单核处理器里增加的晶体管可用于增加多核 处理器的核。这样，c m p 单个处理器的速度下降使得芯片功耗下降，同时，由 于采用了多个处理器核，通过负载优化分布可以均匀分布产生的热量。 1 1 3 事务存储模型技术 但是，在c m p 结构上采用由用户显式制导的并行程序设计模型，使用锁和 同步变量来实现同步的方法存在很大的局限性。锁机制会导致死锁、优先权倒置、 编程困难等种种问题。同时，粗粒度锁可以同步大量的数据，但是粒度过大，造 成互相不相关的代码串行执行，不利于开发并行性。细粒度锁带来了系统的额外 开销，而且放置细粒度锁使得共享存储多线程程序设计变得异常艰难【6 。如何 利用c m p 结构提供的硬件资源来提供更好的并行化方案是一个研究的重点。 事务存储模型提供了一种在c m p 结构上程序并行执行和同步的方法，能够 解决由锁机制带来的这些问题，提高程序的并发性【6 】。在事务存储模型中，事 务是并行处理和调度的基本单位。一个事务就是一段连续的指令流，这段指令流 中所有读写共享存储空间的操作作为一个整体被原子性地提交到共享存储空间 中 6 】。事务存储模型使得程序在发生数据冲突时才串行化执行，最大限度地挖 掘程序中潜在的并行性。使用事务存储模型可以简化并行编程，使得程序设计简 单高效。事务存储模型中的事务有如下特性： ( 1 ) 原子性：一个事务要么被完成且提交了对存储空间的所有修改；要么被取 消，并且丢弃该事务执行期间对存储空间所做的所有修改。 ( 2 ) 可串行性：虽然事务的执行可能是并发的，但是事务好像被一个接着一 个那样串行执行。事务的执行不会交叠，事务的提交顺序对于所有的处理单 元( 核) 是相同的序。多个事务的并发执行与按某一次序串行地执行的结果相 同。 中国科学技术大学硕士学位论文 事务的概念最早出现于数据库领域，通过事务来保证对数据库并发访问的正 确性。事务存储模型发展了数据库中事务的概念，文献 1 6 】将事务引入了并行计 算领域。硬件事务存储模型( h a r d w a r et r a n s a c t i o n a lm e m o r y ，h t m ) 6 1 提出使用 硬件的支持来实现原子性和可串行性，利用c a c h e 及其一致性来实现无锁 f l o c k f l e e ) 的同步。h t m 是由h e r l i h y 和m o s s i 6 在1 9 9 3 年最早实现的。s t a n f o r d 大学的t c c ( t r a n s a c t i o n a lm e m o r yc o h e r e n c ea n dc o n s i s t e n c y ) 结构 17 18 ，以 及 u n b o u n d e d t m ( u t m ) 1 9 ，t h r e a d l e v e lt m ( t t m ) 2 0 ， v i r t u a l i z e d t m ( v t m ) 2 1 】也都是使用硬件支持事务存储模型的实现方案。 检测到 数据冲 突 测到 据冲 图1 2 事务执行生命周期 事务存储模型中，一个事务的生命周期分为4 个阶段，如图1 2 所示：( 1 ) 初 始化阶段。一个事务在执行前需要初始化，包括初始化事务执行所需要的上下文 等信息。( 2 ) 执行阶段。一个事务执行的时候，需要缓存访问共享存储空间的读 写集合( r e a d w r i t es e t s ) ，并侦听其余处理单元上事务提交的写集合的信息。如果 一个事务在执行的过程中监听到发生了数据依赖冲突，则该事务就要回退 ( r o l l b a c k ) ，重新执行。( 3 ) 等待提交阶段。事务经过执行阶段后就进入等待提交 阶段，此阶段要判断事务是否可以提交。如果事务可以提交，则进入提交阶段： 如果在等待提交的过程中发生了数据依赖冲突，则取消本次执行，回退重新执行。 ( 4 ) 提交阶段。事务的写集合被广播到其余事务，并且提交到共享存储空间。至 此，一个事务完成了它的生命周期。 1 2 研究内容和主要工作 事务存储模型是目前体系结构研究中的热点。本文以一种支持事务存储模型 c m p 结构的设计为基础，对于事务存储模型在c m p 结构上的扩展作了深入研究。 在深入分析现有c m p 结构和事务存储模型的基础上，设计了支持事务存储 模型的c m p 体系结构t m c m s 。为了支持对于c m p 上事务存储模型研究，在广 一个支持事务存储的多核处理器结构设计 泛使用的超标量体系结构模拟器s i m p l e s c a l a r 基础上，我们设计实现了支持事务 存储模型c m p 体系结构模拟器o p e n c m p 。 本文主要包括如下研究内容： ( 1 ) 深入地分析和研究了c m p 结构，总结了c m p 结构的特点，适当地 抽象了c m p 结构：全面分析了现有的事务存储模型，从软硬件划分角度， 给出了事务存储模型分类，比较了各种硬件事务存储模型实现的优缺点， 通过抽象给出硬件事务存储模型基本特征和组成部分；同时，简要分析 了与事务存储技术相关的推测多线程技术。 ( 2 ) 提出了t m c m s 结构，以可扩展性和简化硬件设计为目标，定义了 t m c m s 执行模型和结构模型，包括软硬件支持。提出了支持事务存储 模型c m p 结构的主要模块的设计思路，区分了模块的软硬件设计，提出 了用软件实现初始注册模块和取消回退执行模块的方案。 ( 3 ) 设计和实现了个支持事务存储模型的单芯片多处理器结构模拟器 o p e n c m p 。建立要模拟的事务存储c m p 处理器体系结构模型，并确定需 要模拟的关键结构特性。确定了模拟器设计的关键问题：加入了事务存 储模型基本模块，扩展了c a c h e 及总线的模拟、事务相关中断的模拟和 内存地址空间等。设计和实现了t m c m s 的软件支持，给出了事务相关 中断的实现等。 ( 4 ) 提出了性能评估方法。从以下几个方面进行性能评价：处理单元个 数和指令c a c h e 共享对于t m c m s 结构性能影响：t m c m s 的软件模型 实现的开销。 1 3 本文的结构 本文是对我们研究工作的一个总结，全文分为七章。 本章为绪论，综合介绍课题的选题背景和意义，同时简要介绍了事务存储模 型的基本性质。 第二章讨论了事务存储模型技术的现状和发展，详细阐述了事务存储模型的 分类，并深入分析了一些主要的事务存储模型结构和各自的优缺点。通过分析现 有的事务存储模型，介绍了目前学术界事务存储模型研究方面的最新成果。 第三章介绍了本文所设计的支持事务存储的c m p 结构t m c m s 。详细描述 了t m c m s 的基本结构，执行模型，事务存储模型组成模块设计，以及c a c h e 一致性、存储同一性。同时，本章还讨论了t m c m s 编程模型和线程划分。 第四章介绍了t m c m s 结构模拟器o p e n c m p 的设计和实现。详细描述了多 核多线程模拟器的开发目标，阐述了整个模拟器开发的方法和策略。基于超标量 中国科学技术大学硕士学位论文 体系结构模拟器s i m p l e s c a l a r ，介绍了t m c m s 的模拟器o p e n c m p 对于事务模 型支持的实现，包括事务存储模型组成模块实现，事务指令集扩展，中断模拟， c a c h e 及其一致性的实现。 第五章介绍了t m c m s 结构的软件支持的设计和实现。t m c m s 采用了软硬 件结合实现对事务存储模型的支持。本章介绍了x i t 结构，详细描述了初始状 态注册模块和取消回退模块的实现。并描述了t m c m s 中事务相关中断的实现。 第六章选取了测试程序，对于t m c m s 进行了性能分析。 第七章给出了全文的总结和下一步工作的展望。 本文的最后列出了参考文献。 一个支持事务存储的多核处理器结构设计 第2 章相关研究现状 本章介绍了本文的研究背景，综述了事务存储模型技术，给出了事务存储模 型技术的分类。首先详细描述了硬件事务存储模型的特征和主要实现，分析了现 有研究工作的优缺点：然后简略描述了软件事务存储模型的特征和一些主要实 现；最后，进一步介绍了与现代事务存储模型技术密切相关的线程级推测 ( t h r e a d l e v e ls p e c u l a t i o n ，t l s ) 技术的概念以及主要实现。 2 1 事务存储技术简介及分类 事务的概念最早出现于数据库领域，提供数据库处理的a c i d 属性。通过事 务来保证对数据库并发访问的正确性。与下面讨论的事务不同，数据库中的事务 可以是几百万条指令，这些指令中还可能存在i o 操作，这些指令对一种特殊的 结构( 如关系) 进行操作。 事务存储模型发展了数据库中事务的概念，将事务引入了并行计算领域来支 持并发操作的处理 6 】 2 2 】。事务存储模型中的事务不同于数据库中的事务，事务 可能是很短的一段指令。事务存储模型按照实现的方式不同，可以被分为两类： - s e e 是提供硬件支持的硬件事务存储模型 6 】 1 7 】 1 9 】 2 0 1 1 2 1 】 2 3 1 1 2 5 2 7 ，另一 种是通过软件支持来实现，只需要硬件方面很少的支持和修改，这一类被称为软 件事务存储模型( s o f t w a r et m ，s t m ) 2 8 2 9 1 1 3 0 3 1 3 2 】。 2 2 硬件事务存储模型 l a m p o r t 1 6 在1 9 7 7 年最早提出利用无锁的同步方法来实现多线程程序的并 发控制。其后，k n i g h t 2 2 1 开发了一种可以同时对多个字进行同步的体系结构， 这种结构利用c a c h e 一致性协议和一些硬件方面的支持来实现。基于共享存储的 l l s c 指令也提供了原子修改的属性 3 3 】。h t m 6 提出使用硬件的支持来实现原 子性和可串行性，利用c a c h e 及其一致性来实现无锁的同步。 h t m 是由h e r l i h y 和m o s s i 在1 9 9 3 年最早实现的 6 】，h e r l i h y 将其作为一种 无锁的同步算法实现。这种方法通过缓存事务所做的访存操作，将所有的访存操 作的结果保存在一个特殊的c a c h e 中，使用写无效c a c h e 一致性协议来实现数据 依赖冲突检测。为了不修改传统的程序设计模型，提供对于使用锁作为同步方法 的程序的支持，r a j w a r 和g 0 0 d m a n 【2 3 】 2 4 2 5 【2 6 】提出s p e c u l a t i v el o c ke l i s i o n 和t r a n s a c t i o n a ll o c kr e m o v a l ( s l e 和t l r ) ，s l e 提供一种在程序执行时消除 锁的技术，可以消除锁带来的假相关。 上述的这些解决方案都不能解决缓存访存操作溢出带来的问题，这样程序的 中国科学技术大学硕士学位论文 设计者就必须知道硬件所提供的缓存大小，程序的移植也存在一定的问题。后期 很多的解决方案都集中在如何为了给用户提供一个抽象一致的硬件平台，使得程 序员在编写程序的时候能够得到的是一个抽象的一致的平台，u n b o u n d e d t m ( u t m ) 1 9 ，t h r e a d - l e v e lt m ( t t m ) 2 0 ，v i r t u a l i z e dt m ( v t m ) 2 1 都是这类解 决方案。 以上的硬件实现都是通过扩展c a c h e 一致性协议来实现数据依赖的冲突检 测。s t a n f o r d 大学的t c c 结构 1 7 1 8 3 4 3 5 1 ，引入了一个不同的视角。t c c 提 出了种全新的c a c h e 一致性和存储一致性协议。 下面将这些技术进行了仔细的分析。 2 2 1h t m 基本方案( h e r i l h y 方案) h t m 是由h e r l i h y 和m o s s i 在1 9 9 3 年最早实现的 6 】，通过对多处理器高速 缓存一致性协议进行简单扩展实现的，t m 提供了事务方式访问共享内存单元的 指令集。这种方法将所有的访存操作的结果保存在一个特殊的c a c h e 中，使用写 无效c a c h e 一致性协议来实现数据依赖冲突检测。h t m 是l o c k f r e e 的硬件支持 方案。 h e r l i h y 提出的t m 方案主要针对需要进行同步访问临界区的很短的一段指 令，此种方案提供了两种c a c h e ，普通c a c h e 保存普通l o a d s t o r e 操作，而事务 c a c h e 则保存由事务执行l o a d s t o r e 操作所产生的结果。事务c a c h e 保存了事务 中所有的写操作，直到事务提交了才将事务对存储空间的修改通知其余的处理单 元或者写回共享存储空间中。如果一个事务被取消了，那么所有在事务c a c h e 中被修改的数据都将被失效，如果一个事务能够提交，则这些修改的c a c h e 行可 以被其余的处理器访问，也能够在行换出的时候写回内存中。 对于冲突检测，当一个事务发出一个读请求，如果发现该数据不被缓存在本 地的事务c a c h e 中，这时请求就被放到总线上，如果其余处理器的事务c a c h e 中包含了这份数据，那么那个处理器就发出一个b u s y 总线信号，当本处理单 元接受到了此信号，就把自己的状态置位为取消状态。这样就达到了对于数据依 赖的运行时判断。 对于事务的取消和提交，则相应的把状态位置为取消或者提交，然后将事务 c a c h e 中的行作变换，取消状态下，则无效所有的c a c h e 行，如果是在提交状态 下，则将所有的行认定为提交。 但是，作为第一个实现h t m 的方案，此方法是一个理想的模型，存在很多 的实际问题： 一个支持事务存储的多核处理器结构设计 ( 1 ) 首先，对于事务c a c h e 的大小问题，此方案只是在事务c a c h e 溢出 的情况下取消执行，因此，此方法实现的时候程序员编写程序需要对底 层的实现非常清楚，对c a c h e 大小了解，给编写程序带来了一定困难， 而且在不同平台之间移植程序的时候常常会发生问题。 ( 2 ) 其次，对于中断，这种方案显得无能为力，如果在事务执行的过程 中发生了中断，那么事务不h j f i 应，如果响应，则此中断处理可能会在 提交的时候被取消掉，所以作者就没有对中断作特殊的处理，不支持中 断。再次，对于i 0 操作，同样，这种方案也不能实现。 由于此中方案存在过多的问题，使得其只能使一种理想的模型，而不能在实 际中真正被使用。以后的很多h t m 的工作都是在对此几种限制作改进。 2 2 2t l 刚s l e 锁同步技术会降低系统性能，带来系统的不稳定性，这些通常都是由于获得 锁和释放锁造成的，而锁的获得和释放操作经常都不是必需的。为了不修改传统 的程序设计模型，提供对于使用锁作为同步方法的程序的支持，r a j w a r 和 g o o d m a n 提出s l e 和t l r 结构 2 3 2 4 2 5 1 1 2 6 1 ，动态的去除锁的获得和释放操 作来消除锁，获得事务性执行的效果。 s l e 厂r l r 消除锁的技术，可以消除锁带来的假相关，提高性能，而且不需 要对指令集或系统做大的修改，也不需要程序员作额外的工作，只需要对为体系 结构做少量修改和高速缓存一致性协议的支持，容易实现。 s l e ( s p e c u l a t i v el o c ke l i s i o n ) 是提供一种硬件实现的结构，在程序执行过 程中，用一个特定的预测器从指令流中动态的预测所遇到的一些l o a d s t o r e 是获 得锁的访存操作，并预测已经获得锁了，然后开始推测的执行其后的操作。推测 执行的过程中要把执行的结果缓存起来，使用高速缓存一致性协议进行冲突检 测，如果检测到一个冲突，就认为推测执行失败，退回到显式获得锁的指令带着 锁开始重新执行；直到遇到对应的释放锁的操作，则这次预测正确且临界区已经 原子地执行完了，提交推测执行的结果，即将缓存的结果写回到主存中。如果没 遇到释放锁的操作，则认为对锁获得操作的预测失败，仍然回到开始预测的指令 重新执行。s l e 不完全是一个l o c k f l e e 的结构，因为在s l e 中，当遇到数据访 问冲突时，要回到传统的锁技术，所以在有数据冲突时，仍然遇到锁技术带来的 限制。 t