没有合适的资源?快使用搜索试试~ 我知道了~
可在www.sciencedirect.com在线获取理论计算机科学电子笔记296(2013)145-161www.elsevier.com/locate/entcs使用CADP的大规模分布式验证:从集群到网格Hubert Garavel1 Radu Mateescu1 Wendelin Serwe1Inria / LIG - CONVECS团队655,avenuedel摘要分布式验证使用多台计算机的资源来加快验证速度,更重要的是,访问超出单台计算机能力的大量内存。在本文中,我们描述了由CADP(构造与分析)提供的分布式验证工具的分布式过程)工具箱,特别关注其最新的工具,用于管理,检查和分布式状态空间的即时探索。我们还报告了大规模的实验,使用这些工具在网格关键词:异步系统,分布式验证,标记转换系统,模型检测,在机验证,进程演算1引言当在基于动作的环境中使用显式状态验证方法分析并发系统时,状态空间的语义模型是标记转换系统(LTS)。一种方法是首先构建所研究的并发系统的LTS;然后可以将该LTS最小化为互模拟关系的模,以增加进一步分析的效率,例如模型检查,等价性检查,视觉检查等。另一种方法是在并行系统上执行这些分析,即,在LTS的构造期间,以便在不首先构造整个LTS的情况下检测错误。后一种方法更适合早期验证步骤,其中错误频繁并且可以快速检测到,而前一种方法在设计过程的后期阶段更有效,必须探索整个LTS以确保其正确性。由于状态爆炸现象(对于包含许多并发进程和/或复杂数据类型的系统,LTS的大小令人望而却步),1{Hubert.Garavel,Radu.Mateescu,Wendelin.Serwe}@ inria.fr1571-0661 © 2013 Elsevier B. V.在CC BY-NC-ND许可下开放访问。http://dx.doi.org/10.1016/j.entcs.2013.07.010146H. Garavel et al. /Electronic Notes in Theoretical Computer Science 296(2013)145可能成为核查过程中的瓶颈。在这种情况下,如果LTS太大而不能在单个机器上构建,则可以求助于分布式计算基础设施,例如集群和网格,其将可用存储器的量增加几个数量级。CADP验证工具箱[11]通过提供多个分布式验证工具(特别是ACTOR和BCG MERGE [13,12])来利用这种可能性这些工具分别使得能够构造分区LTS(即,分成若干片段,每个片段存储在单独的文件中,可能在不同的机器上)并将其转换成单片LTS(即,存储在单个文件中)。为了扩大验证能力,有时避免构建单片LTS并尽可能长时间地使用分区LTS是有益的。在本文中,我们提出了CADP工具(其中一些已被添加)操作分区的LTS。所有这些工具都基于分布式算法,并使用大多数集群和网格上可用的标准网络通信原语来实现我们还报告了大规模的多集群实验分布式LTS生成和上的减少。这些实验是在使用多达512个分布式进程的Grid'5000计算基础设施[ 9 ]上进行的本文的结构如下。第二节简要介绍了CADP中用于处理网络通信的软件第3节定义了分区LTS的PBG格式。第4节和第5节介绍了用于创建和操作PBG文件的新工具。第6节介绍了一种新的工具,可以对PBG文件进行在线探索。第7节给出了在Grid'5000计算基础设施[ 9 ]上使用这些新工具进行分布式发电和大型LTS的在线减少的实验措施第8节简要概述了相关工作。最后,第9节总结了本文,并提出了未来工作的方向。2网络通信库使用CADP开发的典型分布式应用程序包括N+1个POSIX进程,即N个工作进程,可能在远程机器上或多处理器/多核机器的不同处理器/核上运行,以及一个主进程,其监督工作进程的执行,在用户前端机器上运行,并与用户进行交互。(输入/输出)。这些进程之间的通信依赖于一个名为凯撒网络1(或简称网络1)的专用库,该库目前实现了两种通信拓扑:星形(所有工作者仅连接到主机)和全连接(工作者和主机之间的完整图)。网格的配置被描述为GCF(网格配置文件)格式的文本文件[7],它指定了工作者必须执行的计算节点,访问它们的方式(连接协议和文件传输参数),以及工作者必须运行的目录GCF格式是H. Garavel et al. /Electronic Notes in Theoretical Computer Science 296(2013)145147rsh = ssh -qrcp = scp-q连接超时= 30edel-42.grenoble.grid5000.frdirectory=/home/serwe/1edel-42.grenoble.grid5000.frdirectory=/home/serwe/2 stremi-32.reims.grid5000.fr目录=/tmp/3suno-41.sophia.grid5000.frdirectory=/home/serwe/4(a) GCF文件示例PBG1.0# PBG格式由SENOVA团队制作--http://vasy.inria.fr/senva#由经销商创建(C)INRIA/VASY--http://cadp.inria.frgrid:“grid_4.gcf”[0]状态:分区边:传入启动器:1碎片:4个1 : 状 态 : 4582872 片 段 : “clh-1.bcg“[0] 日 志 : “clh-1.log”[0] 2: 状 态 : 4581049片 段 : “clh-2.bcg“[0]日 志 :“clh-2.log”[0] 3 : 状 态 : 4577666 片 段 : “clh-3.bcg“[0] 日志:“clh-3.log”[0] 4:状态:4576262片段:“clh-4.bcg“[0]日志:“clh-4.log”[0](b) 示例PBG文件图1.一、描述分区LTS的GCF和PBG文件示例独立于应用程序,并可用于启动在相同计算节点上运行的若干分布式应用程序。图1(a)显示了一个GCF文件的例子,其中有四个工作者。为了确保最大的可移植性,网络1库特意基于标准操作系统原语(即TCP/IP套接字)和标准远程访问协议(即rsh或ssh),因此CADP的分布式工具不需要在每个远程机器上专门安装额外的通信库(如MPI)此外,网络1库支持无缝的多核、集群内和集群间通信:除了性能方面,最终用户看不到在单个机器的多个核心上运行的应用程序与在属于一个或多个集群的多个机器上运行的应用程序3 PBG格式为了表示LTS,CADP工具箱提供了BCG(二进制编码图) 文件格式及其相关的软件库。BCG文件使用二进制编码和专用压缩方案以紧凑的方式存储LTS的状态、标签和转换,从而实现高效的表示和操作。BCG文件可以使用现有的CADP工具(例如,检查、可视化、标签重命名、互模拟最小化、在线探索等)或使用使用CADP库开发的自定义工具来读取和写入BCG文件。当处理存储在多台机器上的分布式验证工具和LTSPBG(分区BCG图)格式[7,8]解决了这个问题。这种形式是CWI的前SEN2团队和前VASY团队之间因里亚·格勒诺布尔PBG格式专门为分布式验证而设计,实现了[13]中介绍的分区LTS的理论概念,并提供了对分布在一组远程机器上的LTS的统一访问。PBG文件收集BCG文件的集合,称为fragment(每个worker一个fragment),可以存储在worker执行的(可能是远程的)机器上的单独目录中,也可以存储在共享的公共文件系统2请访问http://vasy.inria.fr/senva148H. Garavel et al. /Electronic Notes in Theoretical Computer Science 296(2013)145(e.g.、使用NFS或Samba)。总之,这些片段形成LTS的一个分区,其状态和转换分布在[13]中指定的各个片段中,每个片段存储一组状态和进入这些状态的转换。请注意,单独来看,每个片段都是没有意义的;例如,它可能是一个不连通的图,而LTS表示并发系统的可达状态空间具体地说,PBG文件是一个文本文件,包含对用于构建分区LTS的片段和GCF文件的引用。图1(b)中所示的PBG文件的示例对应于被划分为四个片段的LTS,其中第一个片段包含LTS的初始状态。对于每个片段,PBG文件列出了片段的状态数量以及与该片段相关联的文件(即,BCG文件和日志文件,其中包含构建片段时可能已发出的错误消息)。有一个简单的代码库用于读取和写入PBG文件。值得注意的是,PBG格式使用的片段数量与计算节点数量成线性关系;这优于竞争SVC格式[6],后者的片段数量与计算节点数量成二次关系4PBG创建PBG格式的分区LTS可以使用CADP的CRUTETOR工具[13,12]生成。该工具通过在GCF文件指定的计算节点(本地和远程)上启动几个工作程序来工作。每个worker负责生成LTS的一个片段,该片段存储为BCG文件;静态哈希函数确定哪个worker探索哪个状态。在终止时,CIMTOR产生一个PBG文件,收集所有这些片段。分布式计算的进程可以被实时监控(参见图2)。除了分布式LTS生成带来的明显优势(加快生成速度并增加内存量,远远超过单机可用的内存量)之外,CRIMTOR还提供了在机上的简化(τ-压缩和τ-连通),这些简化保留了分支互模拟,并且在处理无法在顺序机上生成和最小化的大型LTS时可能5PBG检测和操作目前CADP中有几种工具可用于处理PBG文件:• PBG MERGE(以前称为BCG MERGE [12])将以PBG格式表示的分区LTS转换为存储在BCG文件中的单片LTS。LTS片段被合并到一个文件中,其中状态被赋予连续的编号,以提高所产生的BCG文件的紧凑性。• PBG CP、PBG MV和PBG RM是用于复制、移动和重新移动PBG文件的新工具,请记住,这些PBG文件的片段可能分布在多台远程计算机上,这些计算机可能位于不同的位置H. Garavel et al. /Electronic Notes in Theoretical Computer Science 296(2013)145149图二、 Overview选项卡使用分布在Grid'5000的六个集群(adonis、edel、genepi、granduc、sagittaire和suno)的六个节点上的十二个工作者来监控LTS生成,这些集群在地理上位于格勒诺布尔、卢森堡、里昂和索菲亚-安提波利斯。在“变量”列框表示剩余状态的数量正在增加(分别是减少或稳定),红色框表示工作器空闲;框对于adonis-6上的两个工作器和suno-9上的第一个工作器都是红色的,对于edel-71上的第二个工作器是橙色的,对于所有其他工作器是绿色国家这些工具有助于对PBG文件进行标准操作,并在这些操作期间保持一致性。• PBG INFO是一种新的PBG文件检查工具。它目前提供了几种功能,例如一致性检查(即,所有片段文件的存在性和可读性)、计算相应LTS的大小(状态和转换的数量)、显示标签列表以及连接远程日志文件(这是有用的,例如,理解PBG生成失败的原因,并计算关于工作进程的CPU和内存使用的全局统计数据6PBG在线探测现场验证是一种通过在建造LTS期间验证LTS而不是先建造LTS再验证LTS来实现战斗状态爆炸的方法。这样做,即使在存在状态爆炸的情况下,在线验证也可以早期检测错误。CADP的OPEN/CAESAR [10]环境为在线验证工具提供了一个模块化架构,它将语言相关的方面(将并发系统描述转换为LTS)与语言无关的方面(LTS的前向探索,例如,供核查)。OPEN/CAESAR定义了一个通用的API,用于通过转换关系表示LTS。OPEN/CAESAR还包含一组实现各种原语和数据结构的库,这些原语和数据结构专用于在线图探索(哈希表、堆栈等)。CADP目前为几种高级描述语言(LOTOS、LNT和FSP)和低级状态描述语言150H. Garavel et al. /Electronic Notes in Theoretical Computer Science 296(2013)145图三.利用PBG OPEN和CADP机器格式(BCG、EXP和SEQ)。这些编译器实现了OPEN/CAESAR API,以在编译器上探索相应的LTSCADP还提供了一套基于OPEN/CAESAR API的在线验证工具:模型检验MCL公式 ( 振 荡 器 ) , 双 模 拟 检 查 ( BISIMULATOR ) , partial order reduction(REDUCTOR),随机探索(EXECUTOR),正则序列搜索(参展商),稳态马尔可夫链模拟(CUNCTATOR)等。所有这些工具都可以应用于任何输入语言中的描述,对于这些描述,存在符合OPEN/CAESAR的编译器。新开发的PBG OPEN工具是一个符合OPEN/CAESAR标准的PBG格式编译器。PBG OPEN的主要优点是它可以使用多台机器的内存来存储分区LTS的迁移关系。因此,PBG OPEN可以探索使用其他工具组合无法探索的大型分区LTS。PBG OPEN(参见图3)是一个分布式工具,由一个master和几个worker组成,每个worker都与PBG文件中引用的BCG片段相关联每个worker负责打开它的片段,初始化标签信息,并响应master请求来计算属于该片段的状态的传出转换。初始化阶段包括通过在所有工作器上分配唯一的标签号来规范化片段的转换标签。这是必要的,因为相同的标签可能在不同的片段中被不同地编号。在初始化过程中,每个worker将其标签列表发送给master,master为每个标签分配一个唯一的编号,然后将这些标签的全局唯一编号发送回每个worker。如果主服务器必须对所有转换中的标签重新编号,则此初步步骤可避免性能开销每个转换都由三元组s,a,sJ表示,其中s,a和sJ是编码源状态,标签和目标状态的编号;a现在是所有片段共同的全局唯一标签编号。请注意,片段存储传入的转换,即,给定的工作器存储对于给定的s,J的所有三元组s,a,s,J,而对于给定的s的三元组s,a,s,j,j可以在工作器之间分布当一个在线探索工具请求计算从给定状态s出来的所有转换时,主进程将请求转发给所有工作进程。每个worker(使用BCG原语)检索其脱离状态s的转换,H. Garavel et al. /Electronic Notes in Theoretical Computer Science 296(2013)145151例如进程数状态大小(字节)目录状态ect过渡bcg minstates- 分支跃迁TTAS41718,72139,73680224伯恩斯·林奇-4443769,2441,367,3183,02311,244彼得森树41027,205,54512,692,5842,3618,352Szymanski4609,243,65318,859,3303,09010,356Knuth44816,642,36132,614,2826,72127,281CLH44818,317,84931,849,616320848伯恩斯·林奇56339,796,19075,024,55035,734167,747Lamport46278,535,973154,003,17629,71999,850安德森549166,488,027345,843,9751,7124,880彼得森449214,175,671389,640,0616,46021,347MCS590261,064,933500,744,7651,7124,880Dijkstra457289,120,985542,886,00541,513163,538表1状态空间大小把它们送回主人那里主进程按照工作进程的到达顺序(这是不确定的)探索从工作进程考虑到一些在线分析工具(例如,REDUCTOR工具)经常多次探索从同一状态出来的转换,PBG OPEN使用高速缓存实现记忆化。在接收到脱离状态s的转换的列表L之后,主设备将这对转换存储在高速缓存中。 当缓存满时,根据LRU(最近最少使用)策略选择存在于高速缓存中的一对Lj,Lj,并由新的一对Lj,Lj代替。一般来说,L中的跃迁数和L的最大长度都是事先(它们可以使用初步LTS遍历来计算,但这将太昂贵)。在PBG OPEN中使用最初为状态空间缓存开发的缓存1库实现了缓存的两个变体[19]。这些变量在存储对S,L的方式上不同:(a)可变大小的变量存储高速缓存中的源状态s和堆中的转换列表L,在高速缓存外部(b)固定大小的变体将源状态s和转换列表L都存储在高速缓存中;如果L很长,它可以替换高速缓存中的一个、几个甚至所有条目;如果L对于高速缓存来说太长,则s,L将不会存储在高速缓存中。变体(a)实现起来更简单,但变体(b)保证了静态有界的内存量。7应用与实验我们在LNT语言中指定的各种互斥协议[17]的形式化验证和性能分析的案例研究中对这些工具进行了实验。3我们为四个或五个竞争临界区的进程实例化每个协议,并直接生成相应的LTS4:这样做,我们观察到比[17]中描述的组合方法获得的状态空间更大的状态空间(见表1)实验在地理上位于Greno- ble、Luxembourg、Lyon、Reims和Sophia-Antipolis的Grid'5000集群上运行机器或服务器)和相同的操作系统-3 这些规范将作为示例包含在CADP的下一个稳定版本中。4事实上,这些LTS是交互式马尔可夫链[15],可以被视为LTS的特殊形式152H. Garavel et al. /Electronic Notes in Theoretical Computer Science 296(2013)145集群节点处理器核心/程序频率RAM网站阿多尼斯10至强E552042.26 GHz24 GB格勒诺布尔埃德尔64至强E552042.27千兆赫24 GB格勒诺布尔Genepi32至强E5420 QC42.50 GHz8 GB格勒诺布尔格朗杜克22至强L533542.00 GHz16 GB卢森堡射手座65Opteron 25012.40 GHz2 GB里昂斯特雷米44Opteron 6164 HE121.70 GHz48 GB兰斯Suno34至强E552042.26 GHz32 GB索菲娅-安提波利斯表2使用的Grid'5000集群的特征tem(Debian Linux 6.0“Squeeze”)。但是,集群在节点数量、处理器类型、每个处理器的内核数量以及每个节点的RAM数量方面存在差异(有关详细信息,请参见表2在每个集群中,节点通过1 GBit/s链路连接;格勒诺布尔的所有集群都连接到同一个交换机。站点之间的通信使用专用的10 GBit/s链路。每个站点都为该站点的所有群集提供唯一的资源管理器。只要有可能,我们就为主节点使用单独的节点,并为每个工作节点专用一个核心,即,我们在总共有n个核心的节点上启动了最多n个工作进程。执行时间和内存消耗是使用memtime5测量的,如果可能的话,平均几次执行。在执行时,我们包括设置工作器(创建工作目录,复制文件等)。关于内存消耗,我们为每个进程(主进程和工作进程)测量该进程在其执行期间所需的最大内存量;我们称之为总内存消耗。理论上,所有进程的最大记忆量之和,我们称之为峰值记忆所有这些最大量中的最大值。由于对Grid'5000的计算节点的访问此外,由于共享类似特征(例如传出转换的平均数量或标签数量)的示例相当少,这里报告的实验说明了趋势;结果可能会因其他类型的LTS和/或网格配置而异。7.1分布式状态空间生成算法的性能研究对于每个互斥协议的例子,我们使用一个集群,在同一个站点的多个集群,以及在不同的站点的多个集群,我们使用的是EQUIPTOR来生成相应的PBG图4和图5给出了最多512个工作线程的内存消耗和执行时间加速;图4是分布式执行,图5是单个服务器上的多核执行。请注意,图中的许多轴使用对数标度。内存消耗峰值。图4(a)显示,5下载http://www.update.uu.se/~ johanb/memtime/H. Garavel et al. /Electronic Notes in Theoretical Computer Science 296(2013)145153(a) 峰值内存(MB)加速(单集群:genepi)(c) 加速(多个群集,单个站点)(d)加速(多个站点)见图4。 分布式状态空间生成;所有轴均为对数标度worker降低了峰值存储器消耗6,即,master或任何worker所需的最大内存量:当使用两个worker时,我们观察到减少高达40%。在三个最大的示例(“Peterson”、“MCS”和“Dijkstra”)中对于每个示例,都有一个这可以通过CADP通信库(节点表、通信总线、套接字等)的恒定内存需求来解释。图4(a)显示LTS越小,最佳工作者数量越小(对于非常小的示例,分布式验证没有意义,顺序LTS生成执行得更好)。图4(a)是通过对分布在格勒诺布尔三个集群中的工人进行实验获得的;使用单个集群或不同站点上的集群观察到的数字是相同的。加速。 图4(b)至4(d)显示了不同聚类组合的加速。工人使用他们的本地磁盘,而不是共享文件系统。我们将sequential GENERATOR工具作为加速的参考,图4(b)在genepi集群的机器上运行,图4(c)和4(d)在edel集群的机器上运行然而,在图4(b)中,大型示例“Dijkstra”、“MCS”和“Peterson”需要比单个机器上可用的内存更多的内存:因此,6 有关总内存消耗,请参见图5(b)。154H. Garavel et al. /Electronic Notes in Theoretical Computer Science 296(2013)145(a) 加速(b)总内存(GB)图五. Stremi机群单机状态空间生成足够生成LTS的工人数量(即,两个用于观察到的加速依赖于通信成本,但趋势是相似的。所有三个图都显示了几乎线性的加速,只要工人的数量低于上面提到的“最佳”值。如果工作器的数量变得太大,加速下降:对于小的例子和许多工作器,分布式执行甚至变得比顺序执行更长(加速低于1),这是由于设置分布式应用程序的开销(目前通过顺序复制所有必要的文件到远程机器来实现)。关于执行时间(而不是加速):对于给定数量的工人,最慢和最快的例子之间的执行时间差异随着工人数量的增加而减少。例如,对于顺序执行,这种差异超过一个小时,而对于256个工作者,这种差异仅为两分钟。多核执行。图5显示了在一个24核服务器(每个核最多一个worker)上运行MATRIOTOR时观察到的加速比和总内存。关于加速,图5(a)的几乎线性的加速表明,即使DIS-TRIBUTOR使用的基于套接字的网络1库没有针对共享内存架构进行专门优化,DIS-TRIBUTOR也在多核上表现良好。当增加的工作器数量超过核心数量时,加速率会急剧下降;因为这是预期的,所以图5(a)中没有显示。关于总内存消耗,图5(b)显示内存消耗随着工作者的数量线性增加,这可以通过每个工作者的恒定内存成本来7.2τ-连续约化的性能研究简单的τ-连续约化。为了测量PBG OPEN在特别苛刻的在线应用中的整体性能,我们选择了CADP的REDUCTOR工具,该工具使用顺序在线应用执行τ-连续性减少。H. Garavel et al. /Electronic Notes in Theoretical Computer Science 296(2013)145155(a) 峰值内存(MB)(b)执行时间(小时)图6.利用BMPTOR和PBG OPEN/REDUCTOR进行τ-连续约化算法 我们首先使用编译器生成PBG文件,然后应用PBG OPEN和REDUCTOR在隐藏除了临界和非临界部分的进入和离开之外的所有动作之后,相对于τ-连续性在对除了最大例子7之外的所有例子进行的这种“压力测试”中图6总结了使用granduc集群和多达128个工作者的实验结果。图6(a)示出了总体峰值存储器消耗,即,由EXTRACTOR和PBG OPEN/REDUCTOR使用的最大存储器量;图6(b)示出了总执行时间,即,执行时间的总和,因为这些实验涉及在分布式状态空间上操作的顺序算法,所以我们没有计算加速比)对于这些实验,PBGOPEN的缓存机制被停用,因为缓存的影响将在后面的第7.3节中研究。一个worker的数字对应于直接在LNT源语言级别上使用LNT.OPEN/REDUCTOR工具而不使用REDUCTOR进行的顺序执行的执行时间。正如预期的那样,对于中等大小的示例,具有2到128个工作者,峰值内存消耗低于LNT.OPEN/REDUCTOR,因为PBG OPEN每个状态使用8个字节,这小于表1的第二列中提到的LNT的状态大小。因为执行REDUCTOR的顺序on-the-dummy算法的master是瓶颈,所以峰值内存消耗几乎与worker的数量无关;但是,如果worker的数量太高,所有示例的内存消耗都会增加峰值内存的减少是以执行时间的(显著)增加为代价的,这是由于从分布式片段收集传出转换时的通信延迟:我们观察到RE-DUCTOR的CPU使用率从LNT.OPEN的100%下降到PBG OPEN的40%(如果片段位于地理上遥远的站点,甚至下降到1%)。另一种τ-连续约化。我们 然后 相比 上述τ-共轭 减少 使用 发电机, PBG打开, 减少7执行时间长,超过了网格5000个作业的62小时限制156H. Garavel et al. /Electronic Notes in Theoretical Computer Science 296(2013)145例如LNT。时间开放存储器BCG时间开放存储器PBG时间开放存储器彼得森树5492,0763656263,954570Szymanski4,5301,9401,2908428,537750Knuth2,4702,7641,6421,42812,1741,264CLH1,2673,0871,0601,58510,6151,415Lamportoomoom9,2276,93059,9326,015表3不同缩减技术的比较;分布式工具的两个worker;执行时间(秒),峰值内存(MB,完整的工具组合);(a) 峰值内存(MB)(b)执行时间(小时)见 图 7 。 使 用 带 有 τ- 连 续 性 减 少 选 项 的 连 续 性 减 少 器 进 行 两 次 连 续 性 τ- 连 续 性 减 少 , 然 后 使 用PBGOPEN/REDUCTOR与其他两种方法相比,即:• 直 接 在 LNT 源 语 言 级 别 上 顺 序 执 行 REDUCTOR ( 即 , 在 单 个 节 点 上 使 用LNT.OPEN和REDUCTOR),• 使用BCGTOR分布式生成PBG文件,然后使用PBG MERGE进行LTS合并,并在生成的BCG文件上顺序执行REDUCTOR(即在单个节点上使用BCG OPEN和REDUCTOR表3显示了这三种方法的执行时间和峰值内存消耗,证实了第6节的说法:除了最小的例子,PBG OPEN需要的内存量最少。与源语言的直接连接需要最多的内存,因为状态(特别是当LNT程序包含复杂的数据结构时)比PBG或BCG(每个状态由一个数字表示)的探索更大。BCG OPEN将整个LTS加载到内存中,它比PBGOPEN需要更多的内存,在PBG OPEN中,每个工作线程使用自己的内存只加载分区LTS的一个片段。双τ-连续约化。对于一些例子,我们还实验了两个连续的on-the-τ-concilience约化的 组 合 , 将 REDUCTOR 应 用 于 使 用 具 有 激 活 的 on-the-τ-concilience 约 化 的CRUTOR生成的PBG。这种双重减少产生的LTS最多可小1.9倍比仅调用REDUCTOR获得的结果大(但仍比最小化的LTS大约500倍)。图7显示了granduc集群最多64个节点的实验结果。与图6(a)相反,我们观察到,当工作者的数量增加时,峰值内存消耗会降低。然而,高峰H. Garavel et al. /Electronic Notes in Theoretical Computer Science 296(2013)145157(a)以小时为单位的执行时间(b)以MB为单位的峰值内存图8。高速缓存,高速缓存条目数量不断增加:granduc集群,四个工作进程内存消耗高于没有τ-concieruence的REDUCTOR和DIS-TRIBUTOR的组合;唯一的例外是64个或更多工作者的“CLH”。事实上,因为激活DIS-TRIBUTOR的on-the-the-turnτ-concération reduction产生了一个明显更小的PBG,所以关于峰值内存消耗的瓶颈不是运行REDUCTOR的master,而是运行激活了τ-concération reduction的REDUCTOR的worker。 我们观察到对于τ-跃迁的很大分量和很少的工作者,激活的τ-连续约简几乎需要与REDUCTOR的单个顺序执行一样多的存储器,因为完整的组件由(至少)一个工作者探索。注意,尺寸(即,状态和转换的数量)取决于探索状态的顺序;该顺序取决于工作者和通信延迟的数量。7.3PBG OPEN固定大小缓存。图8和图9显示了增加缓存大小的效果在PBG中,当在一个集群(四个工作器)和不同站点上的多个集群(八个工作器)上使用固定大小的缓存实现时,OPEN最多可达一百万个条目;其他数量的工作器的数量显示出相同的趋势。正如预期的那样,如果缓存足够大,可以容纳所有需要的转换,则缓存可以减少执行时间。这可以在一些小的例子中看到,特别是那些通过减少τ-连续性而获得的例子:这些例子的τ-转换分量明显更小,因此可以观察到小缓存大小已经减少了执行时间。另一方面,缓存会增加峰值内存消耗,除了在那些示例中,CRIMTOR比REDUCTOR需要更多的内存。对于小LTS和许多高速缓存条目,存储器消耗可能变得甚至大于顺序执行-即,当高速缓存存储整个LTS时。固定大小和可变大小缓存的比较。比较两个高速缓存实现与严格相同的高速缓存大小是不简单的,因为不同大小的列表传出的转变。很难预测可变大小缓存的内存消耗,以及可以存储在固定大小缓存中的状态数量(因为每个固定大小缓存条目可以存储158H. Garavel et al. /Electronic Notes in Theoretical Computer Science 296(2013)145(a) 执行时间(小时)(b)峰值内存(MB)见图9。缓存条目数量不断增加的缓存:borderline、granduc和suno集群,8个工作线程(a)以小时为单位的执行时间(b)以MB为单位的存储器图10。增加缓存条目状态或过渡)。为了简化比较,我们选择使用相同数量的缓存条目(这只是比较具有相同内存量的缓存的近似值)。图10比较了四个选定示例的两种实现,使用两个工作进程在granduc集群上运行PBG OPEN/REDUCTOR。 我们只在“彼得森树”中观察到了显著的差异8相关工作还有其他并行和分布式验证的方法。例如,DIVINE [4]支持多核架构[3]、集群和网格[20]上的分布式LTL模型检查。Spin [16]的并行扩展还支持多核LTL模型检查,包括部分降阶。另一个例子是PREACH [5],它支持Mur模型的分布式可达性分析PREACH是建立在原始的顺序Mur代码之上的,实现了DIS-分布式函数式编程语言Erlang中的编程和通信。请注意,对于PREACH的可扩展性至关重要的流量控制信用机制内置在我们的通信库中,因为它是由TCP/IP提供的这些方法和我们的方法之间的一个关键区别是,CADP是基于行动的,而不是基于状态的。此外,CADP还提供了用于生成和H. Garavel et al. /Electronic Notes in Theoretical Computer Science 296(2013)145159处理分布式LTS,这使得可以使用广泛的验证技术,包括模型检查和等价性检查(互模拟)。让我们也提一下Eric Madelaine及其同事的工作,他们使用IbraB-UTOR和BCG MERGE来生成和使用PACAGrid8基础设施在线减少大型LTS[14,2,1]。9结论我们介绍了最近添加到CADP工具箱中的最新分布式验证工具,以便操作表示为PBG文件的分区LTS。我们在一个大规模网格上试验了这些新工具,以及CADP中以前提供的CAPTOR和BCG MERGE工具,该网格涉及地理上位于不同地方和不同国家的几个集群。我们的实验旨在通过使用数百名工人将PBG机器推向极限,并研究这如何提高性能和可扩展性。我们的实验证实了[13]的发现,即使用MANUFACTOR的分布式状态空间生成可以很好地扩展到“太多厨师会破坏汤”的程度我们观察到,使用PBG OPEN对分区LTS的在线探索避免了使用单个机器时面临的内存瓶颈,从而能够利用集群和网格来处理更大的问题(因为所需内存的峰值量大致除以计算节点的数量)。相反,我们的实验表明,PBG OPEN可能比顺序实现慢(在2到9倍之间),REDUCTOR)是一种本质上顺序的状态空间探索算法。我们观察到计算节点之间的通信延迟的显著影响,我们通过在PBG OPEN中引入缓存来解决这个问题我们没有测量消耗的(峰值)带宽:与[5]中报告的观察结果类似 集群的异质性明显影响实验。一方面,具有最小可用内存量的worker确定计算是否成功(因为静态哈希函数将状态均匀地分布在worker上)。另一方面,如果一个工作线程运行在比顺序引用执行更快或更慢的处理器上,则测量加速比变得不精确。然而,我们发现实验静态工作分布如何应对这种异质性是很有趣的。这项工作可以从几个方向进行。首先,可以优化CADP的网络通信库,以在初始化期间支持并行(而不是顺序)文件传输,这将消除使用数百个工作器时观察到的其次,静态负载平衡技术可以通过专门化用于分配的静态哈希函数来研究8请访问http://proactive.inria.fr/pacagrid160H. Garavel et al. /Electronic Notes in Theoretical Computer Science 296(2013)145国家对工人。第三,人们可以用真正的并行OPEN/CAESAR应用程序(例如带有τ-concilience reduction算法的REDUCTOR,或分布式版本的REDUCTOR 4.0 [18]on-the-mandatory 模 型 检 查 器 ) 而 不 是 顺 序 应 用 程 序 ( 例 如 本 文 中 使 用 的REDUCTOR)来实验PBG OPEN。致谢。本文中提出的实验进行了使用网格我们也非常感谢Bellicot、Nicola的Descoubes、JeroammeFereyre、YannGenevois和R′emiH′erilie,他们在CADP分布验证工具的测试和构建中提供了高度的一致性。引用[1] Ameur-Boulifa河,R.哈拉莱湖Henrio和E. Madelaine,《容错分布式组件的安全性-URLhttp://hal.inria.fr/inria-00621264/en/[2] Ameur-Boulifa河, L. Henrio和E. Madelaine,Behavioural models for group communications,in:组件和服务互操作性国际研讨会论文集,WICS[3] Barnat,J. ,L. 布林和P。 Rockai,Saa ableMulti-coreLTLModel
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- OptiX传输试题与SDH基础知识
- C++Builder函数详解与应用
- Linux shell (bash) 文件与字符串比较运算符详解
- Adam Gawne-Cain解读英文版WKT格式与常见投影标准
- dos命令详解:基础操作与网络测试必备
- Windows 蓝屏代码解析与处理指南
- PSoC CY8C24533在电动自行车控制器设计中的应用
- PHP整合FCKeditor网页编辑器教程
- Java Swing计算器源码示例:初学者入门教程
- Eclipse平台上的可视化开发:使用VEP与SWT
- 软件工程CASE工具实践指南
- AIX LVM详解:网络存储架构与管理
- 递归算法解析:文件系统、XML与树图
- 使用Struts2与MySQL构建Web登录验证教程
- PHP5 CLI模式:用PHP编写Shell脚本教程
- MyBatis与Spring完美整合:1.0.0-RC3详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功