（计算机科学与技术专业论文）事务存储系统中冲突检测算法的研究与改进.pdf

国防科学技术大学研究生院工学硕士学位论文 摘要 随着传统单核处理器的局限性越来越突出，人们将目光逐渐转向多核体系结 构，通过多核技术来开发线程级并行。然而，传统的基于互斥锁的并行编程模式 存在死锁等各种缺陷，使得并行程序的开发变得非常低效。在这种情况下，事务 存储系统应运而生，为并行程序设计提供了一个简洁高效的编程环境。 冲突检测作为事务存储系统的三大功能之一，其检测算法的优劣对事务存储 系统的整体性能有着重要的影响。基于s i g n a t u r e 的冲突检测算法能利用有限的位 数组表示无限的地址集合，是事务存储系统中一种很有前景的冲突检测方案，而 误判率的大小又直接影响着该类算法的性能，本文主要针对如何降低s i g n a t u r e 误 判率的问题进行研究。 文章首先对现有的基于s i g n a t u r e 的冲突检测算法进行深入的分析，并改进了 h a s h b l o o m 算法，删减了该算法中一个冗余的步骤，从而缩短了插入和查询地址 信息的时间；然后基于改进后的h a s h - b l o o m 算法提出了两个新的算法- v h b 算法和g h b 算法，并通过蒙特卡罗方法进行验证。实验结果表明，v h b 算法在 地址数量较少的时候的误判率较h a s h b l o o m 算法有了明显的降低，g h b 在地址 数量较多和较少的时候相对于其他算法的误判率都较低：最后，文章从硬件开销 的角度对g h b 算法进行优化，提出了两种p g h b 算法，并使用h p 的c a c t i 对 硅片占用面积进行了定量的评估。 主题词：并行编程，事务存储系统，冲突检测算法，s i g n a t u r e ，误判率 第1 页 国防科学技术大学研究生院工学硕士学位论文 a b s t r a c t w i t ht h el i m i t a t i o n so ft r a d i t i o n a l p r o m i n e n t ，p e o p l e l o o k t o w a r d s s i n g l e - c o r ep r o c e s s o r sb e c o m em o r ea n dm o r e t om u l t i - c o r e a r c h i t e c t u r et o d e v e l o p a d l e v e l p a r a l l e l i s m ( t l p ) h o w e v e r , t h e r ea r em a n ys h o r t c o m i n g ss u c ha sl o c k d e a d l o c ki nt h et r a d i t i o n a lp a r a l l e lp r o g r a m m i n gm o d e lb a s e do nm u t u a l l ye x c l u s i v e l o c k ，m a k i n gt h ed e v e l o p m e n to fp a r a l l e lp r o g r a m m i n gv e r yi n e f f i c i e n t i nt h i sc a s e ， m a t t e r sc a m ei n t ot r a n s a c t i o n a lm e m o r ys y s t e m ，w h i c hp r o v i d sas i m p l ea n de f f i c i e n t p r o g r a m m i n ge n v i r o n m e n tf o rp a r a l l e lp r o g r a md e s l g m n g c o n f l i c td e t e c t i o ni so n eo ft h et h r e em a j o rf u n c t i o n so ft r a n s a c t i o n a lm e m o r y s y s t e m a n dt h ee 伍c i e n c yo ft h ea l g o r i t h mh a sa ni m p o r t a n ti m p a c to np e r f o r m a n c e s i g n a t u r e b a s e dc o n f l i c td e t e c t i o na l g o r i t h m sc a n u s eal i m i t e da r r a yt or e c o r du n l i m i t e d a d d r e s sc o l l e c t i o n s oi ti sap r o m i s i n ga p p r o a c hi nt r a n s a c t i o n a lm e m o r ys y s t e ma n d i t sr a t eo ff a l s ep o s i t i v eh a sm u c hi n f l u e n c eo nt h ep e r f o r m a n c e t h i sa r t i c l ef o c u s e so n h o wt or e d u c et h er a t eo ff a l s ep o s i t i v eo fs i g n a t u r e i nt h i sp a p e r ，w ef i r s ta n a l y z et h ep r e s e n t e ds i g n a t u r e - b a s e dc o n f l i c td e t e c t i o n a l g o r i t h m sa n di m p r o v e dt h eh a s h - b l o o ma l g o r i t h mb yo m i t t i n ga r e d u n d a n ts t e p ，a n d t h e nw ep r o p o s ev h ba l g o r i t h ma n dg h ba l g o r i t h mb a s e d o nt h e i m p r o v e d h a s h 。b l o o ma l g o r i t h m e x p e r i m e n t a lr e s u l t sb ym o n t ec a r l om e t h o da r ep r e s e n t e d w h i c hs h o wv h ba l g o r i t h mo f f e r sl o w e rf a l s ep o s i t i v er a t ew h e nt h ea d d e r s sn u m b e ri s l o wa n dg h ba l g o r i t h mo f f e r sl o w e rf a l s ep o s i t i v er a t ei nm o s tc a s e s a f t e rt h a tw e o p t i m i z et h eg h ba l g o r i t h mf r o mt h ev i e w p o i n to ft h eh a r d w a r ec o s t ，p r o p o s i n gt o w p g h ba l g o r i t h m sa n du s i n gh p sc a c t it oe v a l u a t et h es i l i c o na r e a k e y w o r d s ：p a r a l l e lp r o g r a m m i n g ， c o n f l i c td e t e c t i o na l g o r i t h m ，r a t eo ff a l s e t r a n s a c t i o n a l m e m o r ys y s t e m ， p o s i t i v e 第1 i 页 国防科学技术大学研究生院工学硕士学位论文 表目录 表2 1b l o o mf i l t e r 集合的操作1 0 表3 1 误判率降低比例3 0 表3 2 常用测试用例读写集合大小3 0 表5 1 三种算法s r a m 的硅片占用面积对比4 0 第i i i 页 国防科学技术大学研究生院工学硕士学位论文 图目录 1 1h y d r a 处理器结构3 1 3t m 按策略分类6 2 1b l o o mf i l t e r 例子1 0 2 2t r u e b l o o m 设计结构图1 4 2 3t r u e b l o o m 硬件实现图1 4 2 4s i g n a t u r e 误判率与h a s h 函数的数量k 的关系1 4 2 5c u c k o o 设计结构图1 5 2 6c u c k o o 硬件实现图1 6 2 7 a d a p t i v e b l o o m 设计结构图1 6 2 8a d a p t i v e b l o o m 硬件实现图1 7 2 9a d a p t i v e b l o o m 算法的理想误判率1 7 2 1 0h a s h b l o o m 设计结构图1 8 2 1 1h a s h b l o o m 硬件实现图1 8 2 1 2h a s h b l o o m 算法数据插入流程图1 9 2 1 3 使用h a s h b l o o m 算法进行插入的例子2 0 3 1v h b 算法设计结构图2 2 3 2v h b 算法插入地址流程2 3 3 3v h b 算法向s i g n a t u r e 中插入数据例子2 4 3 4v h b 算法硬件实现图一2 4 3 5 位选h a s h 函数结构图2 5 3 6h 3 函数结构图2 5 3 7h a s h b l o o m 算法改进2 6 3 8v h b 算法误判率1 2 9 3 9v h b 算法误判率2 2 9 4 1g h b 算法设计结构图3 2 4 2g h b 算法插入数据例子3 3 4 3g h b 算法硬件实现3 4 4 4g h b 算法误判率1 3 5 4 5g h b 算法误判率2 3 5 5 1p g h b s 算法的硬件实现图3 7 5 2p g h b e 算法的硬件实现图3 8 5 3p g h b 算法误判率1 3 9 5 4p g h b 算法误判率2 3 9 第i v 页 图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目： 壹签壶篮歪统主壁塞拴型簋鎏盟盟壅多改造 ，么 学位论文作者签名：垄魁日期：2 g 年他月斗日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名：歪扯 作者指导教师名：丝奁 日期：硼g 年n 月7 明 日期：捌年，乞月7 日 国防科学技术大学研究生院工学硕士学位论文 第一章绪论帚一早三百下匕 在过去的几十年中，随着制造工艺的不断提高，人们通过提升处理器的主频 和增加集成的密度来制造复杂高效的系统。通过开发指令级并行( 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 ) 和使用c a c h e 进行时延隐藏等各种新技术，使得处理器的性能按 照摩尔定律以每两年翻一翻的速度高速增长。近些年，指令级并行度开发己达到 了其应用极限，高主频的设计也已逼近了其物理极限，继续沿用传统思路来设计 更高性能的处理器将变得十分困难。在这种情况下，人们将目光转向多核体系结 构，通过多核来开发线程级并行( t h r e a d l e v e lp a r a l l e l i s m ，t l p ) 。 现有的大部分程序都是针对单核体系结构所编制的，虽然能够正确运行于多 核系统中，但是多核系统的并行优势并没有得到充分发挥，为了能够充分利用系 统的资源，必须采用并行编程。然而，传统的并行编程模型不仅复杂易错，而且 调试起来非常困难，导致并行程序的开发效率很低。于是，人们提出了事务存储 系统【1 1 ( t r a n s a c t i o n a lm e m o r y ，t m ) 来取代传统的并行编程模型，这种全新的模型 为人们提供了一个简洁高效的并行编程环境。 1 1 传统体系结构的局限 过去的3 0 年中，高性能通用微处理器芯片主要采用冯诺依曼结构，以开发单 处理器指令流中的指令级并行度和提高芯片主频为设计指导，处理器性能以每年 5 0 - - 6 0 的速度攀升。 从流水线结构的角度看，目前指令级并行性的开发有两种基本思路：一是采 用超流水结构，通过深度切分逻辑操作的流水线来提高主频，从纵向角度增加流 水线上每个时钟周期执行的指令数；另一种是采用超标量或超长指令字( v l i w ) 结 构增加指令发射和执行的并行度，每个周期发射多条指令到多个功能部件上执行， 从流水线横向角度来提高每个时钟周期执行的指令数。其中，超标量结构用硬件 动态地从指令窗口中调度相互独立的指令，发射到空闲的功能部件执行；v l i w 结 构则是依靠编译器找出程序指令流中存在并行度，静态地调度这些相互独立可同 时处理的指令执行1 2 j 。 对指令级并行度的开发在9 0 年代后期和2 1 世纪初达到了巅峰，在此期间出 现的p e n t i u m 4 、a l p h a 2 1 2 6 4 和i t a n i u m ，普遍了采用超标量超流水技术、前瞻推测 技术、增强取指和转移预测技术、踪迹c a c h e 技术等，共同的特点是组织发射度 更宽的实现结构，设置更多的功能部件，芯片内安装多级大容量缓存，显著提高 内存带宽，强化转移预测功能，增加多媒体指令和专用电路，以激进的数据和控 制预测来实现高效的指令乱序并发执行。然而，指令级并行度的开发也存在诸多 的问题【3 】： 第1 页 国防科学技术大学研究生院工学硕士学位论文 首先，从硬件实现角度来看，超标量等指令级并行技术使得处理器核越来越 向复杂化方向发展。指令级并行度的提高要求在流水线上同时执行更多的指令， 需要硬件支撑更宽的指令窗口、更长的发射队列以及更大且端口更多的寄存器堆 等。由于多功能部件的控制复杂度与部件数目成平方关系增长，其资源利用率低， 电路延时大。更高指令级并行度使得微结构复杂度和芯片规模( 包括功能和晶体管 数) 不断上升，由此带来的设计和验证的难度不断增加，这都大大限制了更高指令 级并行性和资源利用率的开发。 其次，应用程度中存在的指令级并行度依赖于程序运行时的控制与数据相关 行为，而已有的大量研究表明，在硬件可实现的指令调度窗口之内，单进程指令 流中存在的指令级并行度有限，在己有结构基础上通过进一步增加处理器核的复 杂度来挖掘指令级并行度的效果己经十分困难。 这些问题的出现表明，继续沿用传统思路来设计更高性能的处理器将变得十 分困难。 1 2 单芯片多核处理器 为了有效依托摩尔定律进一步构建更高性能的微处理器，需要依赖能挖掘和 开发更高层次并行度的设计思路与方法。从前节论述结构本身特性来看，过去流 行的不断提高主频、结构日趋复杂的处理器结构设计已经很难再提高系统的性能。 未来的微处理器芯片需要一种简单的、分布式控制的结构，即芯片的体系结构越 来越强调结构的层次化、功能部件的模块化和分布化，让每个功能部件都相对地 简单，部件内部尽可能保持连线的局部性【2 1 。传统的单核处理器的局限性主要表 现在如下几个方面： ( 1 ) 仅靠提高频率的办法，难以实现性能的突破。当c p u 提高到4 g h z 时，几 乎接近目前c p u 的工艺极限。 ( 2 ) 并行化的要求提高，单一线程中已经不太可能提高更多的并行性，主要有 以下两个方面的原因：一是不断增加的芯片面积提高了生产成本；二是设 计和验证所花费的时间变得更长。 ( 3 ) 通过通用x 8 6 处理器构建大规模集群遭遇到前所未有的障碍，而目前应用 对集群的需求急剧增加，特别是对集群的处理能力的需求，通过单核处理 构建l0 万亿或更大规模的集群基本上没有可能。 ( 4 ) 功耗与性能比问题日渐突出。 在这种情况下，更高并行度的片上多核结构应运而生。片上多核处理器( c h i p m u l t i - p r o c e s s o r ，c m p ) 是在2 0 世纪9 0 年代出现的一种体系结构设计，最初是由美 国斯坦福大学的研究人员提出，其思想是在单个芯片上利用丰富的晶体管资源集 成多个处理器核，通过多核并行执行的方式开发指令级、线程级等各个层次并行 第2 页 国防科学技术大学研究生院工学硕士学位论文 度来提高性能。s t a n f o r d 大学研制的h y d r a 4 】多核处理器，其结构如图1 1 所示。 h y d r a 处理器在片上集成了4 个单发射的m i p s 处理器核，4 核共享1 m 的片上- - 级c a c h e ，采用了基于监听的一致性协议来维护多核间数据的一致性。 图1 1h y d r a 处理器结构【4 】 c m p 结构是利用海量集成度构造新型高性能处理器的重要探索之一。c m p 采用单线程微处理器作为处理器核心，在实际使用中体现出了很多优点p j ： ( 1 ) 易扩展：由于c m p 结构已经被划分成多个处理器核来设计，在整体芯片 架构下，基本的处理器核可以比较复杂也可以比较简单，有利于优化设诈， 是一种具有随工艺水平发展灵活伸缩的结构。 ( 2 ) 设计可复用：c m p 一般采用现有的成熟单处理器作为处理器核心，从而可 缩短设计和验证周期，降低研发风险和成本。 ( 3 ) 低功耗：由于传统技术需要通过提高处理器主频来改善性能，而处理器的 功耗与主频成正比关系，提高主频会带来严重的功耗问题；而c m p 主要 依靠集成多个c p u 核来提高性能，具有明显的低功耗优势。c m p 还可以 实时监控各核的负载分配情况并对其进行调度优化，通过动态调节电压 频率，来有效降低功耗。 ( 4 ) 容忍线延迟：c m p 中绝大部分信号局限于处理器核内，只有少量的全局信 号，因此线延迟对微结构的影响比较小，可以较容易地实现设计要求的主 频。 ( 5 ) 软件兼容性好：c m p 的实现不需要对i s a 做出修改，体系结构也与传统 的对称多处理器( s m p ) 系统接近，应用软件几乎可以不经任何修改从传统 的单处理器或s m p 平台移植到c m p 环境中。 第3 页 国防科学技术大学研究生院工学硕士学位论文 c m p 以其良好的可扩展性、可重用性、兼容性、低功耗和容忍线延迟等优点 被学术界和工业界所广泛看好和接受，已经成为目前高性能微处理器体系结构的 发展趋势。进入2 1 世纪后，主要微处理器制造厂商开始开发基于多核微架构的处 理器。工业界典型的单芯片多处理器包括：i b mp o w e r 4 【o j 、i b mp o w e r 5 【，j 、a m d o p t e r o n i s 、s u nu l t r a s p a r c + 【8 1 、s u nm a j c 9 、s u nt 1 10 1 、i n t e lm o n t e c i t o l 8 1 、 c o m p a qp i r a n h a 1 l 】、c e l l 处理器【1 2 】等。i b mp o w e r 4 芯片上集成了2 个1 g h z 主频的双发射超标量处理器；c e l l 处理器片上集成了9 个处理器核；s u nt 1 在片 上集成了8 个处理器核。学术界典型的c m p 项目包括：s t a n f o r d 大学的h y d r a 系 统【4 1 、c m u 大学的t l s 1 3 1 ，m i tm m a c h i n e 【1 4 1 ，w i s c o n s i nm s s p t l 5 】等。 1 3 传统并行编程模式的局限 在c m p 中，由于多个处理器内核共享一个存储器，所以需要利用同步机制来 解决数据竞争的问题，其中最简单策略的就是使用互斥锁。每一个需要访问共享 数据片的任务在访问数据前必须申请得到锁，然后执行计算，最后要释放锁，以 便其他任务可以对这些数据执行别的操作。不幸的是，尽管锁在一定程度上能避 免数据竞争，但它也给并行软件开发带来了严重问题。 最主要的问题是，锁不具有可组合性。不能保证由两部分以锁为基础、能正 确运行的代码合并得到的程序依然正确。而现代软件开发的基础恰恰是将小程序 库合并为更大程序的组装能力；因此，无法做到不考察组件的具体实现，就能在 它们基础上组装大软件。 造成组装失败的祸首是死锁( d e a d l o c k ) 。考虑最简单的情况，当两个任务以相 反顺序申请两个锁时，死锁就出现了：任务t 1 获得了锁l 1 ，任务t 2 获得了锁 l 2 ，然后，t 1 申请获得锁l 2 ，同时t 2 申请获得l 1 。此时，两个任务将永久阻塞。 除了死锁之外，锁机制还可能导致锁护送效应( c o n v o y i n g ) 和优先级反转 ( p r i o r i t yi n v e r s i o n ) 。锁护送效应是指一个占用临界资源的进程由于消耗尽系统对其 所分配的资源或者由于页错误等原因造成中断，从而使其他本可以运行的进程由 于得不到临界资源而无法运行。优先级反转是指临界资源被低优先级任务占用而 导致高优先级任务阻塞。 同时，在负载较轻的情况下，频繁的加锁和解锁也会对系统的性能产生一定 的影响。 1 4 事务存储系统 针对传统并行编程模式所存在的局限，人们提出了事务存储系统。事务的概 念最早出现在数据库领域，通过事务所具有的基本特性来保证对数据库并发访问 的正确性。t m 发展了数据库中事务的概念，并将其引入并行计算领域。随着近年 第4 页 国防科学技术大学研究生院工学硕士学位论文 来多核c p u 桌面应用的普及，t m 逐渐成为研究的热点。 1 4 1t m 的定义 m a u r i c eh e r l i h y 和j e l i o tb m o s s 在文献【l 】中对事务做了如下定义： 一个事务是由单一进程所执行的机器指令的有限序列，并满足以下两个属性： 1 原子性：一个事务或者被完成且提交( c o m m i t ) 对存储器的所有修改：或 者被q b 1 2 ( a b o r t ) ，并且丢弃该事务执行期间对存储器所做的所有修改。 2 。可串行性：虽然事务的执行可能是并发的，但是事务好像一个接着一个那 样串行执行。事务的执行不会交叠，事务的提交顺序对于所有的处理器单元是相 同的序，多个事务的并发执行与按某一顺序串行地执行它们时的结果相同。 一个事务存储模型为了满足事务的两大特性必须具备以下三大基本功能： ( 1 ) 冲突检钡j j ( c o n f l i c td e t e c t i o n ) 当两个并发的事务同时访问同一个项( 字、块、对象等等) ，并且至少有一个事 务是进行写操作时，我们称这两个事务发生访问冲突。访问冲突的检测策略可以 分为两种： e a g e r ：在对数据进行读写的时候立即进行检测。 l a z y ：在提交阶段才进行检测。 ( 2 ) 数据版本管理( v e r s i o nm a n a g e m e n t ) 为了保证事务在发生访问冲突时可以回退，必须同时保存新的修改后的数据 和原来未更改的数据。版本管理策略同样也分为两种； e a g e r ：修改后的数据放在需要存储的位置，未修改的数据放在其他位置。 由于在事务中止的时候需要将未修改的数据重新拷贝回原来的位 置，提交时不用进行数据的移动，直接清除原始数据即可。所以 采用这种策略的系统的特点是快速提交( f a s tc o m m i t ) ，缓慢中止 ( s l o wa b o r t ) 。 l a z y ：未修改的数据放在原来的位置，修改后的数据放在其他位置。与 e a g e r 相反，采用这种策略的系统的特点是快速中止( f a s ta b o r t ) ， 缓慢提交( s l o wc o m m i t ) 。 ( 3 ) 冲突解决策略 事务间发生访问冲突时，必须采用一定的策略来化解冲突。这种冲突解决策 略包括提交者获胜( c o m m i t t e rw i n ) 、请求者获胜( r e q u e s t e rw i m 、请求者暂停 ( r e q u e s t e rs t a l l ) 等等。 t m 在实现这三大功能时采用策略的不同将对整个系统的性能产生不同的影 响。b o b b a ，m o o r e 等人在文献【1 6 】中详细分析了这些影响，将其归类，并提出了 相应的解决方案。 第5 页 国防科学技术大学研究生院工学硕士学位论文 1 4 2t m 研究现状 根据冲突检测策略和数据版本管理策略的不同，我们可将事务存储模型划分 为四大类型，如图1 2 所示。 v e r s i o nm a ra g e m e n t o l a z ye a g e r o 了 鲁 2 l a z y l ll e o o o g 石。 e a g e r e le e 3 图1 2t m 按策略分类【1 叼 近些年来，国外学者已经提出了许多t m 模型并在不断地加以完善，其中比 较有代表性的有： t c c ：h a m m o n d 等人于2 0 0 4 年提出的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 d c o n s i s t e n c y 1 。7 】属于l l 型系统。该系统为每个c a c h e 行增加重命名标志位， 读标志位和写标志位，使用写缓冲来保存所有的被修改的数据直到相应的 事务提交或者是终止。提交一个事务的时候，t c c 将一个事务对共享内 存所做的所有修改打成一个包，然后广播给其他所有的处理器。 b u l k 1 8 j ：伊利诺伊大学和i b m 研究人员于2 0 0 6 年提出，同样属于l l 型。 b u l k 模型首次引入了s i g n a t u r e 的概念，将每一个事务的访问( 读和写) 的 地址信息记录在一个位数组中，这个数组就称之为s i g n a t u r e ，每个事务有 读和写两组s i g n a t u r e 。当一个事务提交的时候，将它的写s i g n a t u r e 提交 给其他活动的事务，这些事务将该s i g n a t u r e 与自己的读和写s i g n a t u r e 进 行比较，如果发现重合则产生冲突。 l o g t m ：w i s c o n s i n 大学于2 0 0 6 年提出的l o g b a s e dt r a n s a c t i o n a l m e m o r y l l 9 j 属于e e 型系统，引入了l o g 的概念。该系统将l o g 保存在一 个可高速缓存的虚拟存储空间中。当事务创建的时候，每个线程为l o g 分配相应的存储空间，并通知系统所分配空间的起始和结束位置。事务进 行写操作的时候就将旧的数据保存到l o g 中，在事务被终止( a b o r t ) 的时 候，又将l o g 中的数据从新拷贝回原来的位置，进行回退，保证程序执行 的正确性。 l o g t m s e ：w i s c o n s i n 大学于2 0 0 7 年提出的l o g t ms i g n a t u r ee d i t i o n 2 0 属于l o g t m 的改进版，同样属于e e 型系统。该系统结合了l o g t m 和 b u l k 的优点，s i g n a t u r e 和l o g 对操作系统和运行时程序可见，使得它们 可以被任意的保存和重新加载，从而使其能够支持无限嵌套、线程切换和 迁移以及页操作等。由于l o g t m s e 结合了多个系统的优点，所以本课题 第6 页 国防科学技术大学研究生院工学硕士学位论文 的研究就基于该系统。 此外，比较著名的t m 模型还包括、u t m 2 1 1 、l t m t 2 1 1 、d s t m 2 2 1 、 o s t m 2 3 】、v t m l 2 4 1 、h s t m l 2 5 1 、r t m t 2 6 1 等等。 目前，t m 系统的研究已经逐步进入产品化阶段，s u n 公司在2 0 0 8 年i s s c c 会议上展示了第一款支持事务存储的高性能微处理器芯片“r o c k ”。 1 4 3t m 的优势 对于事务存储系统来说，程序员能够独立运行一段并行代码，而无需考虑对 其他线程的影响，这对于并行编程的调试来说至关重要。同时，系统中还能够同 时运行多个事务。 数据库采用面向事务的思想已经有很多年了，而且一直都很成功。事务存储 系统将这一思想引入c + + ，j a v a 这样的主流编程语言，所产生的新语言将成为并 行计算的基础。在使用互斥锁机制时，程序员经常面临着易于使用和可扩展性之 间的矛盾。如果太简单，用起来会很方便，但在同步时会成为瓶颈，影响程序的 可扩展性；为了削除瓶颈，又很容易引入死锁和数据冲突等新问题。 更为重要的是，在如今的软件业中占据重要地位的构件中，互斥锁没有用武 之地。这是因为互斥锁不能用于开发构件，在更换环境之后使用原先的互斥锁， 很有可能会引入新的问题。 事务存储系统最大的好处就是能够将一段代码申明为一个事务，并可以独立 运行调试。独立运行的环境是由系统负责的，这样，同步控制难题的压力就由应 用程序开发者转移到了系统设计者身上，从而提高了程序员的效率。 在运行时，代码直接调用事务存储系统库中的资源，而由库来统一管理内存 资源。只要还没有事务写入的内存位置，其他并行的事务就可以对它进行读写。 和使用互斥锁一样，程序员依然需要自行控制高层次的数据冲突，以确保数 据安全。这和多线程编程一样，应用程序中的高层数据关系是系统无法感知的， 只有人为解决同步冲突与协作的问题。 但与使用互斥锁不同的是，程序员无需处理互斥锁瓶颈的问题，而可以专心 优化所开发的组件，以避免事务之间的冲突。他们依然需要关心程序内在的可扩 展性问题和底层的算法与数据结构，但是，最困难的使用互斥锁的问题就交给编 译器和事务存储系统去解决了。 1 5 论文工作 事务存储系统作为一种全新的并行编程模型，为人们提供一个了简洁高效的 并行编程环境，冲突检测作为事务存储系统的三大功能之一，对事物存储系统 有着重要的影响。基于s i g n a t u r e 2 0 】的冲突检测算法是事务存储系统中很有前景 的一种冲突检测方法，其误判率的大小直接影响系统性能。本课题首先对现有的 第7 页 国防科学技术大学研究生院工学硕士学位论文 基于s i g n a t u r e 的冲突检测算法进行深入分析，详细对比了各自的优缺点并提出了 多个改进的算法。文章详细介绍了改进算法的设计方案和硬件实现，通过蒙特卡 罗方法对改进的算法的误判率进行了评估，并使用h p 的c a c t l 4 2 【2 8 1 对改进的设 计的硅片占用面积进行了定量的分析。 1 6 论文结构 本文第一章主要阐述了本课题的研究背景，并介绍了论文的结构。 本文第二章介绍了现有的基于s i g n a t u r e 的冲突检测算法，分析对比了其各自 的优缺点。 本文第三章至第五章分别介绍了三种改进的冲突检测算法v h b 、g h b 和 p g h b 算法，详细说明了各自的设计方案和硬件实现，并对性能进行了评估。其中， 第三章还提出了对h a s h b l o o m 算法的改进并介绍了性能评测的方法。 本文第六章是对全文的总结和未来工作展望。 第8 页 国防科学技术大学研究生院工学硕士学位论文 第二章冲突检测算法研究 第一章我们提到，冲突检测作为事务存储系统的三大功能之一，对系统的性 能有着重要的影响。为了能准确地进行冲突检测，必须正确记录事务完整的读写 地址集合。 一种解决方案就是将所有的读写集合地址全部记录下来。然而，一个事务在 执行过程中，可能会对大量的地址进行读写操作，要完全的记录这些地址信息不 仅将占用大量的存储空间，而且查找也将变得非常低效。同时，在进行线程切换 的时候必须保存未提交的事务的读写地址集合，保证该线程在重新被调度的时候 能够继续正确的被执行。如果信息过于庞大，不仅大量占用c p u 宝贵的堆栈资源， 而且将耗费大量c p u 节拍来处理保存过程，这将严重影响系统的性能。 另一种很有前景的解决方案就是使用借鉴了b l o o mf i l t e r t 2 9 1 思想的s i g n a t u r e 来进行冲突检测。本章首先对b l o o mf i l t e r 进行简要的介绍。 2 1b l o o mf i l t e r b l o o mf i l t e r 是b u r t o nb l o o m 于1 9 7 0 年首先描述并以其名字命名的。 b l o o mf i l t e r 是一种紧凑的数据结构，用以表示某一元素x 是否属于集合s 。b l o o m f i l t e r 对数据集合采用一个位数组表示并能有效支持集合元素的h a s h 查找操作。 由于其h a s h 查找的常数时间和少量的存储空间开销，使得它具有非常的实用价值。 b 1 0 0 mf i l t e r 自1 9 7 0 年提出以来，被广泛应用到各种计算机系统【3 0 , 3 1 1 之中表示庞 大数据集及提高查找效率。 2 1 1 基本原理 b l o o mf i l t e r 使用长为m 的位数组v 表示数据集合a = x l , x 2 ，x n ，设有k 个具有均匀分布特性的h a s h 函数h ，且v x a ，忽( x ) 1 ，2 ，所 ，则对集合的操 作如表2 1 所示。 对集合元素测试是直接的，如果要测试元素x 是否存在于集合中，我们需要 利用k 个h a s h 函数对x 进行映射，如果v 中对应的所有映射位置都是1 ，集合的 成员测试将返回t r u e ，但如果任何一个是0 ，集合的成员测试将返回f a l s e 。 在集合元素测试中，如果元素x 已经被加入b l o o mf i l t e r ，那么我们将保证： l - j - k ：v e h j ( x ) = l ，也就是说如果一个元素被插入到b l o o mf i l t e r 中， 那么测试该元素的时候一定返回真值【3 2 1 。 根据表示算法，某位可能被多次置为1 ，但仅第一次设置真正起作用。b l o o m f i l t e r 在节约空间的同时，引入了这个问题，也正是由于这个问题，导致了某个元 素不属于集合而被判断为属于的问题，即误判。 第9 页 国防科学技术大学研究生院工学硕士学位论文 表2 1b l o o mf i l t e r 集合的操作【2 j b i t s t r i n gb f _ r e p r e n t ( s e ta ，i n tm ) 对数据集合a ，采用长为m 的位串v 表示 集合表示算法 b i t s t r i n gv 1 一m 】- o ； f o r 0 = l ；j n + l ；j + + ) f o r ( i = l ；i k + 1 ；i + + ) v 【h i ( a 【j 】) 】_ l ； r e t u r nv b o o l e a nb f _ l o o k u p ( b i t s t r i n gv , e l e ) 返同0 ，i fe e 仨a ；返回1 ，i fe e 仨a i n t i = 1 ： 查找算法 w h i l e ( ( v h i + + ( e l e ) 】一1 ) & & ( i k + 1 ) ) ； i f ( i = k ) r e t u r no ； e l s er e t u r n1 ； ) b i t s t r i n gb f _ u n i o n ( v l ，v 2 ) 集合合并r e t u r nv = ( v 1lv 2 ) ；两个内量的按位或 ) b i t s t r i n gb f _ a d d ( v e l e ) 集合元素增加， f o r ( i n ti _ 1 ；i k + 1 ；i + + ) v h i ( e l e ) = l ； v 的更新算法 r e t u r nv ： ) ( a ) 初始状态 ( b ) 插入元素 ( c ) 查询元素 图2 1b l o o mf i l t e r 例子 图2 1 给出了向b l o o mf i l t e r 中插入并查询元素的例子。( a ) 图为b l o o mf i l t e r 初始状态，全部为o ；( b ) 图中向b l o o mf i l t e r 中插入两个元素x l 和x 2 ，映射到的 相应位置被置1 ；( c ) 图中查询三个元素y l 、y 2 和y 3 是否属于该集合，其中y l 有 一个映射的位置为0 ，所以判断y l 不属于这个集合，y 2 和y 3 映射的位置全部为1 ， 所以判断这两个元素属于这个集合。但从( b ) 图中可以看到实际上我们并没有向集 第1 0 页 国防科学技术大学研究生院工学硕士学位论文 合中插入y 3 这个元素，但是我们却得出y 3 属于这个集合的结论，这就是我们所 说的误判。 在日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在 一个集合中。比如在字处理软件中，需要检查一个英语单词是否拼写正确( 也就是 要判断它是否在已知的字典中) ；在网上通缉中，一个嫌疑人的名字是否在嫌疑名 单上；在网络爬虫里，一个网址是否被访问过等等。最直接的方法就是将集合中 全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即 可。一般来讲，计算机中的集合是用h a s h 表来存储的，它的好处是快速准确，缺 点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，h a s h 表存储效率低的问题就显现出来了。比如说，一个公众电子邮件提供商，总是需 要过滤来自发送垃圾邮件的人的垃圾邮件。一个办法就是记录下那些发垃圾邮件 的e m a i l 地址，由于那些发送者不停地在注册新的地址，将他们都存起来则需要 大量的网络服务器。使用b l o o mf i l t e r 不仅可以节约大量的存储空间，而且在遇到 任何在黑名单中的电子邮件地址，我们都能准确地发现。对于误判的情况，常见 的补救办法是在建立一个小的白名单，存储那些可能别误判的邮件地址1 3 引。 在这里，我们需要说明一下h a s h 表和b l o o mf i l t e r 的区别： h a s h 表存储的是真正的数据，利用h a s h 函数作映射的目的只是为了便于大量 数据的查找，冲突时会采取相应的策略，可以获得所存储的数据。 b l o o mf i l t e r 是将数据的信息通过h a s h 函数将位数组相应的位置映射为1 ，节省 大量存储空间，不考虑冲突问题，只能判断一个数据是否被存储( 可能存在误判) ， 而不能重新获取所存储的数据信息