没有合适的资源?快使用搜索试试~ 我知道了~
--可在www.sciencedirect.com在线获取理论计算机科学电子笔记296(2013)127-143www.elsevier.com/locate/entcs符号可达性Tom van Dijk1、Alfons Laarman1和Jaco van de Pol1正式的方法和工具,部门。特温特大学- Box 217,7500 AEEnschede,荷兰摘要本文提出了现代多核硬件的可扩展并行BDD操作。我们的目标是提高性能的可达性分析的背景下,模型检查。现有的方法专注于执行多个独立的BDD操作,而不是并行化BDD操作本身。 在过去,由于共享内存中的通信成本,并行化BDD操作的尝试一直不成功。我们通过扩展现有的无锁哈希表来支持BDD和垃圾收集,并通过实现无锁记忆表来解决这个问题。使用这些无锁哈希表和工作窃取框架Wool,我们实现了一个名为Sylvan的多核BDD包我们提供的实验结果,使用这个多核BDD包的框架中的模型检查器LTSmin。我们在48核机器上测量了BEEM模型数据库中几个模型的可达性算法的运行时间,证明某些模型的加速比超过30,这与早期的工作相比是一个突破。此外,我们改进了标准的符号可达性算法,使用修改的BDD操作,在一个步骤中计算关系乘积和变量替换。我们表明,这种新的算法提高了性能的符号可达性,并减少了高达40%的内存需求关键词:多核,BDD,符号可达性,并行模型检测,无锁哈希表,垃圾收集,LTSmin,WOOL,Sylvan1介绍在模型检查中,我们创建复杂系统的抽象,以验证它们是否根据某些属性运行。系统被建模为一组可能的状态,系统可以在这些状态之间的一组转换。状态和转换构成了描述系统行为的转换系统。模型检测的核心是可达性算法,它计算所有可达状态,即,基于初始状态和转换,系统可能处于的所有可能状态。模型检查中的一个主要问题是转换系统的大小。即使是小系统,存储所有探索状态所需的内存也会增加1电邮地址:tdijk,a.w.laarman,cs.utwente.nl。第一作者由NWO项目MaDriD支持,grant nr。612.001.1011571-0661 © 2013 Elsevier B. V.在CC BY-NC-ND许可下开放访问。http://dx.doi.org/10.1016/j.entcs.2013.07.009128T. van Dijk等人/Electronic Notes in Theoretical Computer Science 296(2013)127呈指数增长处理这个问题的一种方法是使用布尔函数表示所有状态,而不是单独存储它们这被称为符号模型检查[7]。布尔函数可以使用二元决策图(BDD)有效地存储在内存中[1,6]。为了操作使用BDD存储的布尔函数,存在各种各样的BDD算法。要计算所有可达状态,只需要四个算法,常见的BDD实现还包括一个特殊的算法来计算结合了BDD和BDD的关系乘积。本文的第一个贡献是一个新的算法,结合了变量替换的关系产品。通过实验,我们表明,该算法是更快,需要高达40%的内存比单独执行这两个操作。由于模型检测具有巨大的计算需求,因此不断开发提高模型检测工具性能的技术。直到最近十年,提高性能的常用方法是提高CPU频率。算法针对单个处理器进行了优化,处理器实现了各种硬件优化,如乱序执行和流水线。硬件的最新发展引入了多核和多处理器架构的必要性,以获得未来的性能增益。为了使用所有核心的计算能力,我们需要并行化我们的软件,即,将算法划分为可以由多个工作者并行执行的较小部分,以实现最大加速。在文献中,有限的加速BDD操作已被归因于不规则的内存访问模式。由于负载不平衡和许多小计算的调度,符号状态空间生成导致高并行开销。此外,符号数据结构[16]上的同步会产生额外的开销。为了最大化加速,我们需要通过开发新的数据结构和算法来最小化这种开销本文的第二个贡献是Sylvan,它是一个多核的BDD算法实现,使用了我们开发的基于任务的工作窃取框架Wool和可扩展的数据结构。这些数据结构基于无锁范式,它避免了互斥并依赖于原子操作。我们已经使用扩展的LTSmin工具集[4]对BEEM数据库[31]中的几个模型进行了状态空间生成实验,以支持我们的实验性BDD软件包Sylvan。我们在48核上获得了高达32的加速比具有相对于1个核心上的运行时的最佳基准模型(平均5次运行)我们比较了结果的性能相同的可达性算法使用流行的BDD包BuDDy作为后端的符号模型检查。结果表明,与优化的顺序封装相比,我们的方法在48个核心上仍然提供了高达12倍的显着加速本文件的结构如下。 我们总结了BDD的基本原理, 和可达性,并在第3节提出了一个新的BDD算法ReleksS,它减少了符号模型检查的内存需求。第4节讨论了并行化BDD操作的两种方法,我们提出了一个无锁的记忆表和一个支持垃圾收集的无锁哈希表T. van Dijk等人/Electronic Notes in Theoretical Computer Science 296(2013)127129第5节中的引用计数。在第6节中,我们介绍了我们的实验结果。我们在第7节和第8节中完成了相关的工作和结论。2预赛2.1使用布尔函数的设S=Bn是所有状态的集合,由n个布尔向量组成。转换关系是一个二元关系RS×S,表示状态之间的转换。给定向量大小为n的转移系统是一个对(SI,R),其中SI<$S是一组初始状态,R<$S×S是一个转移关系。可达状态集是R应用于SI的自反传递闭包。一般来说,状态集合或者被显式地存储,即,每个状态被单独地或象征性地存储,即,状态的集合由布尔函数表示[7]。一个子集V<$S可以用布尔函数F:Bn→B表示,使得给定一个状态s,F(s)惠s∈V。转移关系RS×S可以用布尔函数T表示:Bn×Bn→B,使得给定状态s和sJ, T(s,SJ)惠(s,SJ)∈R.给定布尔函数F(s)和T(s,SJ),得到F的T-后继为FJ(s)=<$SJ.F(SJ)<$T(SJ,s).可达状态的集合是用符号广度优先搜索计算的,作为以下系列的固定点F i+1(s)= F i(s)(sJ. F i(sJ){T(sJ,s)}(1)给定状态向量s,对于等于s的向量,我们写s[i←v],除了si=v。我们用si表示si=0。我们将函数的限制(也称为余因子)定义为Fi=v(s)d=efF(s[i←v])。下面的思想被称为香农F(s)(siFi= 1(s))(siFi= 0(s))(2)2.2二元决策图二元决策图(Binary Decision Diagrams,BDDs)是由Akers [1]提出并发展起来的[6]梁启超。它们的主要优点是状态集通常被简洁地表示。此外,由于约简有序BDD是规范的,测试两个集合的相等是平凡的。BDD是一个有向无环图,其叶子为0和1,以及一组内部顶点V,配备有可变标签和两条传出边。所以BDD被定义为元组(V,high,low,var),其中high,low:V→V{0, 1}是表示节点的高边和低边的函数,var表示与顶点关联的变量。BDD中的每个节点根据其香农展开表示布尔函数(2)。特别地,如果var(B)=x,high(B)=B1,low(B)=B0,则130T. van Dijk等人/Electronic Notes in Theoretical Computer Science 296(2013)127JXX1∧ X2X1∨ X2(x1x2)∨ (x1)x2)XX1X2X1X2X2X1X210101010图1.一些布尔函数的二元判定图。内部节点绘制为带有变量的圆,叶子绘制为框。高边绘制为实线,低边绘制为虚线。B表示函数F,使得Fx=1表示B1,Fx=0表示B0。图1给出了简单BDD的示例。给定变量的全序,有序BDD是其中变量沿着从根到叶的所有路径以递增顺序出现的BDD。<一个有序的BDD被称为简化的,如果它没有冗余节点(有两个相同的孩子),也没有重复的节点(有相同的变量,高和低边缘)。图1中的所有示例都是有序和简化的。约化和有序BDD是布尔函数的规范实施. BDD节点使用存储器阵列存储。BDD的边或引用是该存储器阵列中的索引[22]。单个BDD节点由三个整数组成,代表变量和传出边。BDD包必须确保BDD始终是约简和有序的不变式。为此,BDD实现通常包含方法MK(x,T,F),该方法返回具有变量x的唯一BDD节点、到BDDT的高外出边缘和到BDDF的低外出边缘。这个函数保证返回的BDD是一个简化的BDD。要实现MK,需要一个唯一表,通常使用哈希表实现。或者,也可以将节点存储在这个哈希表中,从而消除节点数组。这简化了执行。垃圾收集对于BDD至关重要。修改BDD中的子图通常意味着修改所有祖先,因为BDD节点通常是不可变的。因此,BDD操作修改整个BDD。其结果是,用于存储BDD的数据结构需要支持垃圾收集,例如使用引用计数或标记和扫描方法。然而,Somenzi提到,未使用的BDD节点通常在以后被重用,并且只有当有足够的未使用的BDD节点来证明垃圾收集和重新创建在垃圾收集期间删除的节点的成本时,才应该执行垃圾收集[36]。2.3关系产品等式(1)中的后继集合FJ(s)=F(sJ)<$T(sJ,s)通常分两步计算。起始点是BDDF(X)和T(X,X)。首先,BDD算法RelProd有效地结合了合取和存在量化,T. van Dijk等人/Electronic Notes in Theoretical Computer Science 296(2013)127131∧∨∃∧.Σ←∈ ← ∨←←⟨ ⟩ ← ⟨ ⟩ ⟨⟩←⟨ ⟩ ← ⟨ ⟩ ⟨⟩以获得表示X的BDD。F(X) T(X,XJ). 注意这个BDD是用变量Xj来表达的。在第二步中,变量X被替换为XJ。因此,BDD被创建两次,使用不同的变量集定义2.1[RelProd算法]给定一组变量Xn ={x1,.,x n}、集合XX n以及BDD F(X)和G(X),则RelProd算法返回BDD R(X n\X),表示R(Xn\X<$)=<$X <$F(Xn)<$G(Xn)该算法的简化(非优化)实现在Al-出租m 1中给出。这里x是一个变量,X是一个变量的集合。在洛9,当x∈X 时 ,我们将 取 Rx=0<$Rx= 1 来 计 算 <$x R. 当nx∈/X时,结果被计算为具有变量x的根节点的BDD。算法1RelProd:计算X(FG)输入:BDD F、BDD G、集合X一曰: 如果F= 1G= 1,返回12:如果F= 0G= 0,返回03:如果memo.get(F,G,X,R),则返回R4:xfirst(var(F),var(G))5:F0,F1如果x=var(F)则低(F),高(F)否则 F,F6:G0,G1如果x=var(G)则低(G),高(G)否则G,G7:R0 RelProd(F0,G0,X)8:R1RelProd(F1,G1,X)9:ifx XthenR R0R1elseRMK(x,R1,R0)10:memo.put(F,G,X,R)11:返回R动态规划用于使算法在输入BDD的大小上是多项式的。为此,memo.get和memo.put(l。3,10)操纵记忆表,该记忆表用于存储所有中间结果以供以后参考。low和high跟随BDD节点的低边和高边,var返回BDD节点的变量,first根据返回第一个变量,MK是创建或检索唯一BDD节点的方法<3使用ReleksS提高可达性我们提出了一个新的算法,结合关系的产品和替代,消除了不必要的创建BDD在XJ。它是原始RelProd算法的修改。 我们使用变量替换(单射函数S:X→X),在创建结果的BDD节点时直接应用请注意,在SMART [11]中基于MDD的模型检查中,如其他[13]所述,通过将转换关系中的正常变量和初始变量存储在一起并在一个步骤中评估它们,已经避免了创建这些不必要的BDD节点。我们的解决方案更一般,允许任何替换S,只要它保持。定义3.1【Reliance S算法】Reliance S以BDDF和G、变量集合X、变量集合X→X和单射函数S:X→X作为输入,132T. van Dijk等人/Electronic Notes in Theoretical Computer Science 296(2013)1271F=1G=1RPSx∈XRPSx=0x=1算法2Religious S:计算ReligiousX(F<$G)并应用替换S输入:BDD F,BDD G,集合X,替换S1:如果F= 1<$G = 1则返回 1第二章: 如果F= 0<$G = 0<$F =complement(G)则返回03:如果G= 1,则返回Reliance S(1,F,X,S)4:如果F=G,则返回Reliance S(1,G,X,S)5:如果F > G,则6:returnReliance S(G,F,X,S)7:如果memo.get(F,G,X,S,R),则返回R8:x←first(var(F),var(G))9:<$F0,F1<$←ifx=var(F)then<$low(F),high(F)<$else<$F,F<$10:<$G0,G1<$<$←ifx=var(G)then<$low(G),high(G)<$else<$G,G<$11:ifx∈Xthen12:R0←Relative S(F0,G0,X,S)13:如果R0= 1,则14:R←115:其他16:R1←Relatives S(F1,G1,X,S)17:R←R0<$R118:其他19:R0←Relative S(F0,G0,X,S)20:R1←Relative S(F1,G1,X,S)21:R←MK(S(x),R1,R0)22:备忘录(F,G,X,S,R)二十三: 返回R其保持变量排序。RelationsS返回函数的BDDRd=ef.X设xF∈X和xG∈X是F的根BDD节点的变量, G,并设x为xF和xG中按序的最小值.令RPSx=v表示计算Rx=v且v∈ {0, 1}的Reliance S的递归执行。然后,我们定义Religious S算法如下:Reliance S(F,G,X),S)=100F= 0100G = 0以其它方式,RPSMK(S(x),RPSx=1,RPSx=0)算法2中给出了Reliance S的完整算法。该算法与RelProd的算法相同(简化版本见算法1),除了l。21、变量被替换。为了保证结果仍然是按照排序的,排序必须在S下保持。<这里>可以是任何总排序,例如哈希表中的索引我们使用一个记忆表(l。7,22)记住结果。规范化规则被添加(l.3-6 ),所以类似的操作使用记忆表中的相同条目我们还插入了一个捷径优化,省略了计算R1时,R0= 1(1。14)。T. van Dijk等人/Electronic Notes in Theoretical Computer Science 296(2013)127133表1RelProd+S和RelProd S的比较(数字四舍五入为106)模型国家数量#transs单位RP+S的 工作RPS(·106)Decr.BDDRP+S节点RPS(·106)Decr.面包店41.5 1054.1 10554百分之十八点三21百分之三十八点一面包店82.5 1089.8 1081,18899714.0%35321938.0%碰撞。54.3 1081.6 1091,187983百分之十八点二470297百分之三十六点九iprotocol.79.8 1062.0 108759601百分之二十点八34420440.8%电梯41.1 1052.4 10541388.1%85百分之三十六点五电梯75.1 1061.4 107533489百分之八点二1076539.0%sched world.21.6 1061.4 1071514百分之十点四5332.4%sched world.31.7 1082.0 10920017811.0%6848百分之二十九点七我们比较了使用RelProd和一个单独的变量替换的RelProd S的可达性的计算和内存需求我们的RelProd实现包括与RelProd S相同的优化。这两种实现都使用互补边[27,5],这是一种使用相同图形表示F和<$F的技术,并允许在恒定时间内对F和<$F进行求反和比较。在这个实验中,我们使用了BEEM数据库的一个子集[31]。我们从这个数据库中选择了各种尺寸表1显示了非平凡BDD子操作的总数。这些子操作是RELPROD、RELPROD和Substitute,它们不会立即返回结果,而是查询存储表或基于香农分解计算结果。我们只计算了可达性算法每次迭代中计算后继者所需的子操作数表1还示出了在执行可达性算法之后BDD表中的BDD节点的总数。我们禁用了垃圾收集来计算这个数字。对于iprotocol.7,工作量减少了20%,BDD节点的数量减少了40%。4BDD操作的我们并行化了Religious和Religious,这是可达性所需的BDD操作。本节介绍我们应用的两种并行化方法。我们将使用以下术语:算法由许多操作组成,这些操作可以分解为小任务或子操作。任务需要其他任务的结果这可以在任务依赖图中可视化。另见图2。任务由多个工作者执行。通常,工作者的数量等于可用的图2.任务依赖图处理器核心。加速比是对并行化算法的性能增益的度量如果一个算法有20个工作者134T. van Dijk等人/Electronic Notes in Theoretical Computer Science 296(2013)127的执行速度是1个工作者的5倍,我们说20个工作者相对于1个工作者的加速比是5。在这种情况下,理想的加速比是20。在这个例子中,效率是5/ 20 = 25%。T. van Dijk等人/Electronic Notes in Theoretical Computer Science 296(2013)127135算法3将Religion S(Alg. 2)使用羊毛19:SPAWNReliance S(F0,G0,X,S)20:R1←CALLReliance S(F1,G1,X,S)21:R0←同步22:R←MK(S(x),R1,R0)4.1使用工作窃取的算法并行化的主要目标是加速。理想情况下,工作在工人之间均匀分配,并且获得等于工人数量的加速比。均匀分配工作的问题称为负载平衡。一种方法是将子任务存储在队列中,并让工作者在执行被盗任务后,必须将结果返回给原始任务所有者。一些框架实现了基于任务的并行性,例如基于编译器的框架Cilk和OpenMP以及基于库的框架Wool [17]。这些框架支持创建任务(spawn)并等待它们完成(sync)以使用结果。我们选择Wool进行符号可达性的并行化有几个原因。根据[32],与Cilk和OpenMP相比,Wool操作系统在细粒度基于任务的并行性方面具有更好的可扩展性还有一个博客报告了使用Cilk [20]并行化BDD包BuDDy,并使用Wool我们预计会得到类似的结果。最后,使用Wool框架实现并行性非常简单。我们通过创建新的任务来并行化Religious和Religious,每当算法2中有两个递归调用时。为此,我们使用Wool提供的C宏SPAWN,后面跟着匹配的宏SYNC来检索结果。当SPAWN后面紧跟着SYNC时,则使用宏CALL请注意,CALL会导致所有者立即执行任务,而SPAWN将向任务队列添加新任务。特别地,为了并行化Reliance S,我们替换l。图19-21中 所示的算法3中的行。第19行的子任务被放在任务队列中,这样它就可以被窃取,第20行的子任务由当前工作者执行注意,我们也可以在算法2的第12和16行使用SPAWN和SYNC。但是,这将禁用快捷方式优化,从而增加总工作量性能增益仅适用于那些没有足够工作来窃取的模型与算法2一样,使用记忆表来存储子操作的结果。此表是全局共享的,即,每个操作只有一个存储表4.2使用结果共享和随机负载平衡的我们还考虑了并行BDD操作的简化方法。它避免了基于从任务队列窃取工作的显式负载平衡相反,所有工作者都从同一个任务开始,并以随机顺序执行子任务。工人之间唯一的同步是子操作的结果存储在共享的记忆表中。这将阻止工作进程计算子操作136T. van Dijk等人/Electronic Notes in Theoretical Computer Science 296(2013)127已经被一些工人完成了。当然,也可能有多个工作者启动相同的子操作,初始任务总是如此。然而,由于处理子操作的顺序是随机的,工作者将很快地分支到不同的子任务。所以负载平衡完全依赖于随机化。例如,如果一个任务有两个子任务,则工作者以50%的概率开始不同的子任务。随着子任务数量的增加,这种情况会迅速增加5用于BDD的在并行BDD操作中,工作者之间的大部分通信发生在包含BDD节点的哈希表和记忆表中。这些数据结构的设计必须具有最佳的可扩展性。传统上,像数据竞争这样的并发冲突是通过锁来解决的,锁提供了互斥。由于阻塞的进程必须等待,锁对并行程序的加速有负面影响最近的研究一直致力于开发非阻塞数据结构和算法。Herlihy和Saught [21]区分了无锁算法、无等待算法和无锁算法。我们的算法属于最后一类。在这里,通过使用原子处理器指令(如比较和交换)来避免显式锁。compare and swap(ptr,old,new)指令原子地比较值将*ptr的值设置为old,如果等于,则将*ptr设置为new。如果成功,则返回true;如果 *ptr不等于old,则返回false。在后一种情况下,*ptr的值保持不变。下面,我们讨论一个有损记忆表和一个支持通过引用计数进行垃圾收集的哈希表的无锁实现5.1无锁有损存储表无锁有损记忆表是由两个数组组成的哈希表。一个数组包含键的散列值加上一个位,用于存储桶上的本地短期锁另一个包含数据,由一个密钥组成,即,每个任务的参数的表示和结果值。主要要求是不能从表中获得未放入表中的结果 这是通过使用哈希数组中的本地锁控制对哈希表中特定桶的访问来保证的。这个锁是使用比较和交换指令设置的,并使用正常的内存写入来释放。由于记忆表是有损的,结果可能会被覆盖。哈希冲突的结果新条目将覆盖现有条目。由于在我们的例子中重新计算单个任务的结果并不昂贵,因此偶尔重新计算结果应该不会导致显著的性能损失。算法4中给出了put的算法。该算法被设计为在其他工作进程使用该存储桶时立即中止操作。如果存储桶上有锁,或者比较和交换失败,那么已经有一些相关的T. van Dijk等人/Electronic Notes in Theoretical Computer Science 296(2013)127137⟨ ⟩ ←←←⟨ ⟩ ⟨⟩← ⟨⟩← ⟨⟩← ⟨⟩/⟨ ⟩ ⟨⟩←⟨ ⟩ ←←算法4put:在memoization表输入:key,data(注:key是data的子集1:hash计算hash(key)2:索引哈希% tablesize第三节:curhash,curlockhasharray[index]4:如果curlock = 1,则返回5:如果curhash = hash,则如果key与数据数组中的key,则返回第六章: 如果不比较和交换(hasharray[index], curhash, 0, hash, 1),则返回7:将数据写入数据阵列8:hasharray[index]hash, 09:返回算法5:从记忆表输入:键1:hash计算hash(key)2:索引哈希% tablesize第三节:curhash,curlockhasharray[index]4:如果curhash = hash或 curlock = 1,则返回NOTHING5:如果不是compare and swap(hasharray[index], hash, 0, hash, 1),则返回NOTHING6:如果key与数据数组中的key,则7:从数据阵列读取结果8:hasharray[index]hash, 09:返回结果10:其他11:hasharray[index]hash, 0第12章:什么都不返回找到那个桶然后我们马上回来等待锁被释放,然后用新结果替换相关结果可能是不明智的。此外,始终允许不存储数据,因此不需要保护第5行。get的算法在算法5中给出。该算法比较散列,获取锁,比较参数并返回结果值。如果这些步骤中的任何一个失败,则不会返回任何内容。我们不会等到锁被释放。这些算法遵循这个要求,因为返回的数据只有在桶上有锁时才被读取,在这种情况下,另一个工作者不可能修改数据。5.2带引用计数的无锁哈希表为了存储BDD节点,我们实现了一个无锁哈希表,它支持使用引用计数的垃圾收集。我们扩展了单调增长共享哈希表的数据结构[24],可以删除节点并允许垃圾收集。[24]中的无锁哈希表基于开放寻址。它支持一个操作,find或put,它会通知是否存在某些数据,如果是新的,则插入它。它的工作原理如下。当插入数据时,其哈希值存储在哈希数组中,根据探测序列存储在第一个空桶中。这是一些固定的桶列表,从数据的哈希值确定性地计算数据存储在数据数组中的相同索引处;数据数组由哈希数组中的短期锁位当检索数据时,同一探针138T. van Dijk等人/Electronic Notes in Theoretical Computer Science 296(2013)127垃圾墓碑等待(h)⟨ ⟩ ←CAS写入数据+、− :casCAS收集图3.哈希表桶的状态转换序列,直到具有正确哈希值和数据的索引或者遇到空桶,这表明数据不存在。请注意,不能简单地删除散列值,因为这会破坏探测序列,可能导致两次插入相同的数据并报告这是新的。我们通过用一个特殊的值替换数据来解决这个问题,而不是删除它。对于垃圾收集,我们还向哈希数组添加了一个引用计数。因此,哈希桶假定以下值之一• EMPTY:空桶,探测序列结束• TOMBSTONE:空桶,但探测序列继续• hash_WAIT:在这个索引• 完成,哈希,计数完成:完整的数据,具有给定的哈希和引用计数我们将这些值编码为32位:15位用于哈希,1位用于锁,16位用于锁。位用于引用计数。引用计数被阻止为整数,通过保留一个特殊值SATURATED。当引用计数饱和时,它将不再增加或减少。图3显示了存储桶可以执行的转换到WAIT的转换应该获得一个排他锁,因此它们是用比较和交换实现的。对引用计数的修改也是如此,因为它们必须以原子方式发生。从DONE到TOMBSTONE的转换仅在单独的垃圾收集阶段允许(并且仅当count =0时)。find或put的扩展版本称为lookup或insert。算法(Alg. 7)由探针序列上的两个环组成第一个循环检查数据是否已经在表中。第二个循环将数据插入第一个可用的bucket中,标记为EMPTY或TOMBSTONE。由于我们假设垃圾收集发生在单独的阶段,因此在执行查找或插入期间不会出现新的TOMBSTONE桶。算法6增加:增加给定bucket输入:桶1:重复2:完成,哈希,计数桶3:如果count =SATURATED,则返回4:untilcompare and swap(bucket,bucket_DONE, hash,count_bucket,bucket_DONE,hash,count+1_bucket)完成(h,计数)空T. van Dijk等人/Electronic Notes in Theoretical Computer Science 296(2013)127139∈←←⟨⟩∈⟨⟩⟨⟩← ⟨⟩⟨⟩算法7查找或插入:确保数据在表中输入:数据1:hash计算hash(数据)2:对于i 探头序列(数据)执行3:如果bucket[i]=EMPTY,则中断4:如果bucket[i] =...,hash,.然后5:whilebucket[i] =WAIT, hash不做任何事情6:如果数据与数据数组中的数据,则7:增加(bucket[i])8:返回i9:对于i 探头序列(数据)执行10:value bucket[i]11:如果value =EMPTY或 value =TOMBSTONE,则12:ifcompare and swap(bucket[i], value,WAIT, hash)then13:在i处将数据写入数据阵列14:bucket[i]DONE,hash, 115:返回i16:如果bucket[i] = hash,则17:whilebucket[i] =WAIT, hash不做任何事情18:如果数据与数据数组中的数据,则19:增加(bucket[i])20:返回i21:returnTABLE FULL算法增加(Alg. 6)并减少修改引用计数。它们的前提条件是桶的形式为:DONE,hash,count。它们可以在外部调用(例如由BDD包调用),也可以在内部通过查找、插入和垃圾收集来调用。6结果我们使用LTSmin工具集[4]中的dve 2-reach符号BFS可达性算法,从BEEM数据库[31]中 选 择 代 表 性 模 型 进 行 试 验 。 实 验 在 48 核 机 器 上 运 行 , 该 机 器 由4 个 AMDOpteronTM 6168处理器组成,每个处理器具有12个核。这台机器有一个NUMA体系结构与8个内存域和6个核心每个域。我们首先通过实现一个实验性的并行BDD包Sylvan,使用Wool的工作窃取(参见第4.12我们通过将每个工作者绑定到内存域并在本地分配每个工作者的任务队列,即,在选定的域上。在少于48个worker的情况下,我们计算了NUMA库报告的最小距离处的内存域的最小子集,并以循环方式将worker分配给每个内存域。例如,对于10个工作者,我们会将5个工作者分配给2个域,每个域以最小距离选择。我们使用预分配的BDD哈希表和记忆表,它们在所有选定的内存域上交错分配。我们还修改了LTSmin以运行两次符号可达性:在第一次运行中,迁移关系组被在线学习并存储为BDD。第二次运行重用此预先计算的转换关系来计算2Sylvan是LTSmin2.0的一部分,http://fmt.cs.utwente.nl/tools/ltsmin/140T. van Dijk等人/Electronic Notes in Theoretical Computer Science 296(2013)127表2以秒为单位的运行时间以及Sylvan和Buddy的可达性加速模型124Sylvan8163248Sp.伙计Sp.面包店411.46.85.44.54.44.44.72.41.90.4面包店81370.0681.5348.1184.7102.462.049.827.5517.710.4碰撞。51828.4920.8505.6256.5138.676.657.232.0623.310.9iprotocol.71012.2507.9261.1137.276.046.337.427.1351.9 9.4电梯434.117.810.06.35.05.05.85.912.42.1电梯7473.1239.0123.467.340.228.927.617.2194.6 7.1sched world.217.89.55.63.62.72.42.47.46.52.7sched world.3260.1131.467.535.619.711.89.527.4114.312.0302520151050 10 20 30 40工人图4.在48核机器上使用Sylvan加速可达性可到达状态的集合。我们只测量了第二次运行所花费的时间,因为我们只对BDD操作的加速感兴趣。表2和图4显示了几种代表性模型的结果从这些结果中,我们可以看到模型的大小和所获得的加速比之间的明确关系。将结果与表1进行比较,我们可以看到较小的模型(少于100,000,000个工作单元,总共创建的BDD节点少于10,000,000个)具有非常有限的加速,而最大的模型表现出最好的加速。较小的sched world.3模型是一个例外,它仍然显示出不错的加速。请注意,这些数字是在一个完整的可达性分析,因此单个较大的BDD操作可能扩展得更好,因为初始BFS级别中的BDD很小。模型bakery.4bakery.8collision.5iprotocol.7lifts.4lifts.7sched world.2sched world.3加速比T. van Dijk等人/Electronic Notes in Theoretical Computer Science 296(2013)127141虽然在48个核心上32的相对加速已经非常好了,但我们进一步调查了这个数字不高的原因当运行Wool的基准测试时,并行化Fibonacci算法而不存储,即,每个任务只包含两个子任务的结果,我们发现Wool本身在48个核心上的加速比约为34这可能会在未来的工作中通过重新设计工作窃取算法来增加,而不是像[38]那样在任务队列我们还尝试了在N个变量水平中仅每隔1个使用记忆表在N值较低的情况下,这导致了一些性能的提高(高达10%)和记忆表使用的显着减少,但相对加速几乎没有改善[15]。我们使用并行实现Sylvan将LTSmin工具集的可达性算法的运行时与流行的顺序BDD包BuDDy [25]进行了比较。与Buddy相比,我们见证了高达12倍的加速(表2)。在Buddy中的实现和在Sylvan中的实现之间存在一些差异,这使得比较性能变得困难。BuDDy不实现Reliance S或补边。Sylvan使用引用计数进行垃圾收集,而BuDDy使用标记和清除。但是,预分配的表足够大,因此Sylvan和BuDDy都不会进行垃圾收集。Sylvan仍然更新引用计数,因此BuDDy有一个优势,因为标记和扫描需要更少的簿记。BuDDy还使用了其他几种优化,例如通过将相关的BDD节点存储在哈希表中彼此靠近来增加内存局部性作为哈希表中的哈希。最后,BuDDy不是线程安全的,只使用正常的内存传输,而我们用更昂贵的比较和交换操作来取代一些正常的内存传输,以确保线程安全。我们还尝试使用随机负载均衡(参见第4.2节),并在其他地方报告了不错的性能和可伸缩性[15]。结论是,这种替代方法是可行的,但使用Wool的方法目前提供了略高的性能和更大的加速比。7相关工作在文献中,有一些早期的工作,在2000年之前,并行BDD操作大规模并行SIMD机器和分布式架构。最近还没有关于现代多核共享内存架构的工作来并行化实际的BDD操作。在90年代早期,一些研究人员试图通过并行处理来加速BDD操作。第一篇论文[23]将BDD视为自动机,并通过计算乘积自动机然后最小化来组合它们。并行处理独立的子公式产生了并行性:扩展和约简算法本身不是并行的。这个时代的大多数其他工作都实现了向量机[28]或大规模并行SIMD机器[8,18]的BFS算法实验是在超级计算机上进行的,比如连接机。其他解决方案基于分布式共享内存142T. van Dijk等人/Electronic Notes in Theoretical Computer Science 296(2013)127抽象,以实现标准的深度优先算法[30,9],或混合深度/广度优先方法[39]。注意力转向基于消息传递库的工作站网络。其动机是将通过快速网络连接的计算机的集体记忆结合起来。深度优先[2,37,3]和广度优先[34]遍历都已经提出。在后一种情况下,BDD按不同的水平分布一个工人只能在其级别有一个回合时才能继续,所以这些算法本质上是实验表明,可以操纵非常大的BDD,但没有观察到加速。最后,BDDNOW [26]是第一个分布式BDD操作系统,声称在物理内存耗尽之前有一定的加速。在2000年之后,研究的注意力从BDD操作的并行实现转向使用BDD在分布式[19,10]或共享内存[16,12]中的符号可达性。基于BDD划分策略,可以获得
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功