没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记109(2004)17-29www.elsevier.com/locate/entcs用于模型仿真的并行图变换在时间变迁Petri网中的应用J. de Laraa,1,C. Ermelb,2,G. Taentzerb,3,K. Ehrigb,4aEscuelaPolit'ecnicaSupreiorIngenier'ıaInform'aticaUniversidadAut'onomadeMadrid西班牙马德里b柏林理工大学Institutfur?rSoftwarete chnikundTheoretischeInformatikBerlin,Germany摘要这项工作讨论了使用并行图转换系统(多形式主义)建模和仿真及其在元建模工具AToM3中的实现。作为一个例子,时间变迁Petri网(TTPN)的模拟器建模使用并行图转换。关键词:模型仿真,并行图变换,时间变迁Petri网1介绍复杂系统的建模必须考虑性质非常不同的组件。这些组件应该使用不同的形式来描述,每个形式都足以描述视图。问题是分析和/或模拟这样的异构模型。多形式建模1Juan. ii.uam.es,2lieske@cs.tu-berlin.de网站,3 gabi@cs.tu-berlin.de网站,第karstene@cs.tu-berlin.de1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi:10.1016/j.entcs.2004.02.05318J. de Lara等人/理论计算机科学电子笔记109(2004)17允许软件开发人员使用最适当的形式主义来对系统的每个组件进行建模,并通过识别每个组件被符号化地转移到其中的单个形式主义(称为语义形式主义)来解决模拟问题。因此,如果语义形式主义允许适当的形式分析和模拟技术,则可以验证整个系统的属性。一个很好的候选人,这样的语义形式主义是Petri网,因为它们配备了一个正式的语义,并允许一个正式的分析,以及系统行为的可视化仿真由于建模形式主义今天通常是基于图表或图形(例如,软件工程的UML图类型或设计可编程控制器的功能框图),我们的方法使用图转换[15]将不同的形式主义转换为语义形式主义,并对转换后的模型进行模拟。通过元建模的方法,将不同的形式定义为视觉语言。在用于多形式建模和Meta建模的工具环境AToM3[3]中,这样的元模型由可视化部分(对可视化语言中使用的符号进行建模的类图)和文本约束(OCL中的格式良好规则)组成,以将模型集限制为有意义的模型。AToM3允许为指定的可视化语言[3]的模型生成模型编辑器和模拟器,以及基于不同元模型和图形转换规则[4]的形式主义之间的模型转换在本文中,重点在于模拟一个特殊的变种的Petri网并行图形转换的功能最近已在AToM3中实现,并允许灵活的仿真规范。并行图变换的本质是,具有一定规律性的规则集(可能是有限的),即所谓的规则方案,可以由一组有限的规则来描述,这些规则对基本动作进行建模例如,当对Petri网变迁的触发进行建模时,基本动作将是从变迁的前域中的一个位置删除一个令牌,并将一个令牌添加到后域位置。为了描述这样的规则方案,使用了在子规则处合并规则的概念。因此,Petri网变迁的触发可以用一般的方式来描述,尽管它没有固定一个变迁有多少输入或输出位置。这对于AToM3来说尤其重要,因为在这里,仿真语法是基于元模型定义的,即独立于特定模型,并且可以应用于所有有效模型(例如Petri网)。因此,通过并行图变换来定义Petri网行为的方法与将Petri网映射到图文法的通常方法显著不同[2],其中考虑特定网,其令牌被映射到由位置标记的离散节点,并且每个J. de Lara等人/理论计算机科学电子笔记109(2004)1719←→转换被映射到图形规则。其他用于规则应用程序的同步机制在基于图重写的分布式系统建模工作中进行了讨论,如[6]([14]中开发合并概念的动机)以及用于系统重构的同步超边替换系统[11]的相关最新方法。有一些相关的基于工具的方法支持基于元模型的视觉语言定义和基于图语法的视觉模型模拟,例如DiaGen [5]或GenGED [9],但它们都没有实现并行图转换。另一个相关的方法是MetaEnv [1],一个定义视觉模型语义的环境。一个模型是从外部的CASE工具,使用图形语法的高级时间Petri网的语义域翻译。该语义模型可以模拟和翻译成C代码。与AToM3方法相比,MetaEnv中的语义模型是固定的,而AToM3中的语义模型是可变的。第2节回顾了并行图变换的概念在第三节中,时间变迁Petri网的模拟器作为一个并行图转换系统。第4节概述了AToM3的扩展,以便为合并规则的定义和应用提供工具支持2并行图变换并行图转换对并行状态转换进行建模,其中状态由一个图形来描述,该图形可以通过执行几个动作来改变并联由于图转换是基于规则的,没有限制性的执行规定,它提供了大规模并行执行的可能性。并行规则应用程序的同步由公共子规则描述。在本节中,我们回顾了并行图变换的主要概念[14],并展示了如何使用并行图文法以简洁的方式对任意位置转换网(从现在开始的P/T网)中的转换的触发进行建模。这为第3节讨论的时间变迁Petri网(P/T网的扩展)的仿真提供了基础。使用图文法作为建模技术,对象由节点表示,它们之间的相互关系由边表示。动作通常由图规则描述,并通过图转换(将规则应用于给定的图,从而产生一个新的图,用于模拟更改后的系统状态)进行模拟。一个图形规则r = L K双推出(DPO)方法中的R到图变换[15]由三个属性图L、K和R以及它们之间的图态射(对于L和R中的映射图对象,通过相等的数字可视化)组成。L和R分别是左右图20J. de Lara等人/理论计算机科学电子笔记109(2004)17K是它们的公共接口。作为绘图惯例,我们省略K。所有在L和R中具有相同数量的对象也包含在K中,并且在应用该规则时被保留。规则r可以包含一个或多个否定应用条件(NAC),表示规则适用时必须不存在的情况。形式上,这是由属性图表示N ACi和态射ni:N ACi←L。 一个规则适用于图G在匹配m:L→G处,如果不存在图态射nJi:N ACi→G使得对所有i∈I,m=nJi<$ni.规则r在图G引导中的应用图H的导出。通常,导子G=H是DPO在属性图和图态射范畴中的构造最简单的并行操作类型是独立操作。如果它们在不同的对象上操作,它们显然可以并行执行。如果它们只是在读取共同对象上的动作时重叠,情况本质上不会改变。在图变换中,这由并行规则反映,并行规则是规则的不相交联合。重叠部分,即在多个规则的匹配中出现的对象,由并行规则的匹配隐式地处理。由于并行规则的应用只能对独立操作的并行执行进行建模,因此它等效于以任何顺序应用如果动作不是相互独立的,如果它们可以通过子动作同步,它们仍然可以并行应用。如果两个操作包含删除或创建相同的节点,则此操作可以封装在单独的操作中,该操作是原始操作的公共子操作一个共同的子动作是通过应用所有原始规则(称为基本规则)的子规则来建模的然后,通过将基本规则粘在其子规则处来执行由子规则同步的规则的应用,这导致 相应的合并规则。这种规则的应用被称为合并图变换。图1中给出了合并规则的示例。这里,两个基本规则er1和er2具有加法一个循环到一个共同的节点。这个公共接口被建模为一个子规则。合并规则包含公共操作,此外,还包含来自基本规则的不重叠的所有操作。图1中的虚线箭头指示规则态射,垂直箭头是子规则到基本规则的对应实例中的嵌入,以及基本规则到合并规则中的嵌入。注意,每个基本规则可能有任意多个实例,它们都粘在一个子规则上。实例的数量取决于规则方案与特定图的匹配。形式上,动作的同步可能性由交互方案定义。注意,合并规则的形式构造J. de Lara等人/理论计算机科学电子笔记109(2004)1721Fig. 1.一种融合图规则在[14] 中 描述 了DPO 方 法。 对 于将 此形 式基 础扩 展 到单 推出 方法(SPO)中的属性图转换,其中规则由负应用条件增强,请比较[10]。定义2.1(交互方案)一个交互模式IS=(E,S,SE)由一个基本规则集E、一个子规则集S和一个嵌入到基本规则中的子规则集SE组成,其中s∈S,e∈E.具有NAC的子规则只能嵌入到包含至少与子规则相同的NAC的基本规则中。此外,每个基本规则可以具有除子规则之外的其他NAC。一个交互方案也可以看作是一个二分图(IS-图),其节点由基本规则和子规则标记。边由子规则嵌入标记。除了指定基本规则应该如何同步之外,我们还必须决定一组基本规则应该在哪里应用以及多久应用一次同步复杂并行操作的基本方法是允许在给定图中的所有不同匹配处应用规则。这表示动作的大规模并行执行。为了本文的目的,我们将G的覆盖(G中基本规则实例的所有不同匹配的图像)限制为在其公共子规则的匹配中重叠的所有不同基本匹配。对于其他更复杂的覆盖结构,请参见[14]。对于G的限制覆盖,IS-图总是连通的。一个图H可以通过一个交互方案IS=(E,S,SE)从图G直接并行导出,如果存在一个由下式构造的合并规则r:将基本规则ei:Lei→Rei∈E的实例粘在它们相应的子规则s∈S中的一个上,如SE所定义的,并且如果所有匹配mi:Lei→GR在它们子规则中的重叠匹配ms:Ls→G使得G=H。这规则合并也可以看作是一个二分图Gr,其节点是子规则和基本规则的实例,并且其边是子规则嵌入。表示有效规则合并的每个Gr在IS-图上被类型化,例如,存在从Gr到IS-图的同态映射。22J. de Lara等人/理论计算机科学电子笔记109(2004)17∈→定义2.2(并行图形转换系统)一个并行图变换系统PGTS=(G0,I)由一个起始图G0和一组相互作用方案I并行图变换系统的语言L(PGTS)由所有图给出,这些图可通过有限个直接并行推导步骤从G0中并行推导出,应用从I构造的合并规则。定义2.3(P/T网络模拟器作为PGTS)我们将P/T网[13]建模为具有两种节点类型(用于位置和转换)的属性图,两种边类型(用于从位置到转换的弧,反之亦然)以及用于标记数量和弧权重的类型N的属性作为PGTS的起始图N,允许任意的P/T网。相互作用方案是seq(如图1左上角的图表2)描述了任意转换的顺序触发。子规则transglue将基本规则get和put的实例连接在一起(参见图1中 的 规 则 transl , 规 则 get 的 实 例 get1 和 get2 以 及 规 则 put 的 实 例put1)。2)的情况。在Def.2.3中定义为PGTS的P/T网模拟器只导致构造有效的顺序P/T网触发规则。这意味着,对于P/T网N中的每个变迁t N,由模拟器PGTS构造一个合并规则L R,其中L和R包含变迁及其环境。在L中,前域位置的标记由表示大于相应弧铭文值的数字的变量表示。在R中,新的标记是通过从前域标记中减去前弧值并将后弧值添加到后域标记来计算的。子规则transs确保基本规则的所有副本在同一个转换节点中重叠。基本规则get从对应于弧权重的前域位置中删除标记的数量,规则put在后域位置上生成正确数量的标记。在每个合并的触发规则中,get和put的副本数量与N的不同匹配一样多,前提是它们在同一个转换节点中重叠。因此,转换的前域和后域将被相应的合并规则完全覆盖。由于子规则transs(以及所有基本规则)删除了转换并重新构建它,如果不是转换的前域和后域的所有位置都被覆盖,则不满足dangling条件图图2示出了合并规则的构造,其中变迁与P/T网N的上变迁相匹配。在transition的predomain中有两个get请注意,标记号和弧权重的变量被实例化为规则实例中的不同变量。J. de Lara等人/理论计算机科学电子笔记109(2004)1723图二. P/T网多个转换的并行触发可以类似地由并行图变换系统表示。不同之处在于,基本规则不必都粘在单个子规则上,而是可以粘在子规则的不同实例上。此外,我们需要两个子规则(定义2.3中的转移粘合规则和空规则),并需要一个稍微不同的覆盖结构(见[14])。3时间变迁Petri网的模拟器TTPN [12]就像P/T网,但是转换被分配了延迟,以这种方式,它们必须在该时间内启用才能触发。图3的左侧示出了TTPN的元模型。类Timer、EventQueue和Event不用于建模阶段,而是用于模拟。在模拟过程中,唯一的Timer对象跟踪当前模拟时间(当前属性)和最终时间(最终属性)。每次启用转换时,都会调度一个事件并将其插入(有序)事件队列(对象EventQueue)中。该事件计划在过渡点火时发生。转换保持一个指向它通过关系火生成的事件的指针。一旦转换触发,事件将从队列中删除,模拟时间将提前到事件发生的时间。这种事件驱动的模拟是离散事件模拟中的标准技术,避免了在没有系统状态变化时增加时间[8]。图的右边图3显示了一个简单的模型,它是前面的元模型的一个实例它是一个令牌模型,其中令牌在到达间隔时间为6时到达,并由两个并行服务器之一以速率7和8提供服务。模拟电流(0)和最终时间(100)显示在左上角的“挂钟”图标中。事件队列显示在底部,其中第一个模拟事件实际上是第二个(调度在6),它从产生它的转换中接收指针。调度在-1的事件被保留,以便使模拟器的规则更简单。最后一24J. de Lara等人/理论计算机科学电子笔记109(2004)17队列中的事件在模拟最终时间被调度,以这种方式,当前模拟时间永远不会到达该点。图3.第三章。TTPN的元模型(左)。一个嵌入式系统的TTPN模型(右)。在本节中,我们将使用并行图形转换系统来说明TTPN的模拟器。我们使用原子触发(token停留在某个地方,直到transition触发),单服务器语义(transition只提供一个计时器)和启用内存(即由于transition触发而禁用的transition计时器被重置)。模拟器由两个交互方案和一个规则组成。第一个相互作用方案如图4所示。它的目的是检查是否启用了转换(如果其输入位置至少具有与连接弧的权重一样多的标记,则会出现这种情况)。则事件被调度为在转换启用时间之后发生。该方案被分解为两个基本规则由一个子规则粘合。按照惯例,我们在基本规则中省略子规则的条件和NAC。它们被每个基本规则隐含地采用。图四、检查启用的交互方案可以为每个predomain位置实例化一次enablepre规则要检查的过渡。应用此规则,过渡必须没有预定事件,并且地点应该有适当数量的令牌。该规则还确定新事件将在其中发生的事件J. de Lara等人/理论计算机科学电子笔记109(2004)1725−放置.对于被检查的转换的每个输出位置,启用post规则被实例化一次。sync enable子规则为enable pre和enable post的实例化提供了公共上下文:transition和events。如果转换的某个predomain位置没有足够的令牌,则无法在该位置实例化enable pre类似于定义2.3,转移被删除并由子规则重构,使得在这种情况下,如果在前域位置上没有足够的令牌,则由于悬挂条件而不能应用该方案。图中显示了相互作用方案5和模型的过渡点火和时间推进在一起。基本规则get被应用于转换的前域位置,其关联事件是队列中的第一个真实事件。队列中的第一个事件(时间等于1)和最后一个事件(时间等于最终模拟时间)用于简化事件的插入和删除。第一个事件的时间是可以触发转换的最早时间。此外,当前模拟时间提前到已处理事件的时间。规则get删除与连接弧的权重一样多的标记,并擦除事件。规则put与之类似,但它应用于输出位置,从而生成令牌。子程序syncfire用于通过公共上下文同步put和get请再次注意,如果传入的位置没有足够的令牌,则不满足悬空条件,并且无法应用该方案。过渡点火时间应少于最终模拟时间,以便可应用合并方案。图五. 火灾相互作用方案26J. de Lara等人/理论计算机科学电子笔记109(2004)17在冲突情况下(两个转换的预域中的一个位置),转换触发可能会禁用其他转换。在这种情况下,应擦除禁用转换的计划可能事件。这是由右侧所示的规则约束对于执行,我们将优先级1分配给规则冲突,优先级2和3分别启用和触发交互方案检查,并使用AToM3的控制结构,即根据规则的优先级(从较低值到较高值)按顺序评估规则当应用规则时,控制将在具有最高优先级的规则处继续。见图6。示例的推导顺序图6示出了图3中的队列示例的导出序列。开始时,当前时间curr为0,两台并行服务器空闲。为了调度到达,应用启用的交互方案检查,并将时间6添加到事件队列。交互方案FIRE的应用将模拟时间提前到6,并将令牌放入队列中。在图6的第二行中,启用了三个转换,并且它们的触发时间以正确的顺序添加到事件队列在我们这里,J. de Lara等人/理论计算机科学电子笔记109(2004)1727属于零时间转换的时间可能已经以相反的顺序被调度。触发事件队列中的第一个转换会导致在placebusy-1上的令牌。在图6的第三行中,必须解决冲突情况。上零转换仍在事件队列中,但不再启用。因此,规则冲突会从队列中删除此事件4AToM3中的并行图变换AToM3允许通过元模型定义视觉语言。模型操作既可以用Python程序来表示,也可以用属性图语法来表示。AToM3为了在AToM3中实现并行图文法,图重写处理器只需要稍微修改。我们利用AToM3的元建模功能定义了一个用于仿真方案的元模型,并为它生成了一个建模工具。然后,该建模工具被集成到AToM3内核中。图图7显示了AToM3在交互方案火灾建模过程中的情况。左侧窗口中显示了一个包含已定义的子规则和基本规则的列表,而交互方案显示在背景窗口中(这是通过元建模获得的工具)。在前窗口中,正在编辑规则get的LHS。一些可见属性被标记为与节点和链接相关的数字表示规则左侧和右侧之间的常见态射。此外,规则可能有额外的条件(用Python表示),必须满足这些条件才能应用规则,并在应用规则时触发操作。一旦定义了所有的交互方案,就可以将它们放入一个列表(也可能包含常规规则)并分配优先级。然后,AToM3当考虑应用交互方案时,AToM3在内部构建合并规则(可能根据当前匹配的需要使用基本规则的几个实例),然后应用它(如果满足所有规则的条件)。请注意,在条件的Python表达式中,用户可以使用左侧或右侧显示的数字访问节点和链接的属性。由于合并规则可以具有基本规则的许多实例,如果节点和链接的数量不是从基本规则的任何子规则的任何态射的一部分,则它们在内部改变。这意味着条件的Python表达式可能必须更改为28J. de Lara等人/理论计算机科学电子笔记109(2004)17见图7。AToM3中一个并行图转换系统的定义the5结论本文提出了并行图文法作为建模和仿真的一种有价值的手段。它们通过允许同步基本规则的并行执行来扩展正则图文法的能力。这对于为其中发生并行动作的形式主义指定模拟器是有用的,例如Petri网和其他离散事件模拟形式主义。Paragraph变换对于在不同形式之间转换模型的形式变换也很有用。在这种情况下,并行图转换简化了模型转换,因为它们允许在可变上下文中嵌入新创建的元素。否则,必须为每个不同的上下文复制转换规则。在AToM3工具中实现了并行图变换在马德里的小组中,并行和分布式图形语法目前被应用于并行离散事件系统中的仿真协议建模[7]。在未来,我们将应用到其他TTPN语义,Petri网的变种和离散事件形式主义的方法。其他覆盖结构的实施也在考虑之中。J. de Lara等人/理论计算机科学电子笔记109(2004)1729确认这项工作得到了SEGRAVIS网络和西班牙科学技术部的部分赞助(TIC2002 -01948)。作者也感谢匿名推荐人提供的有价值的提示和评论。引用[1] 巴雷西湖Pezze,M.,2002. 自动化可视化软件工程的方法,Proc. FASE'02,Springer LNCS2306,pp. 189-202.[2] Corradini,A.,蒙塔纳里大学,1995. Specification of Concurrent Systems:From PetriNets to Graph Grammars,Proc. Workshop on Quality of Communication Based Systems,Berlin,Germany,Kluwer Academic Publishers。[3] de Lara,J.,Vangheluwe,H.,2002年。 AToM3:一个多形式主义建模和Meta建模的工具。 在proc FASE174 - 188。另请参见AToM3主页,http://atom3.cs.mcgill.ca[4] de Lara,J.和Taentzer,G.,2004年自动模型转换及其验证AToM3和AGG,Proc.图表2004,已接受。[5] 迪亚根主页,http://www2-data.informatik.unibw-muenchen.de/DiaGen[6] Degano,P.,蒙塔纳里大学,一九八七年一种基于图重写的分布式系统模型。ACM杂志,卷。34/2,pp.411-449[7] Ferscha,A.,1995. 离散事件系统的并行与分布式仿真。以. Y. Zomaya,编,并行和分布式计算手册,McGraw Hill,pp。1003-1041[8] Fishman,G.美国,2001. 离散事件模拟建模、编程和分析。Springer系列在运筹学。[9] GenGED主页,http://tfs.cs.tu-berlin.de/genged[10] He ckel,R.,Müller,J., Tae ntzer,G. 和Wagner,A.,一九九五年一种具有规则控制应用的语法转换。Proc. Coll. 图变换及其在计算机科学中的应用,马略卡,第41[11] Hirsch,D.,2003年。软件架构风格的图形转换模型。布宜诺斯艾利斯大学博士[12] Ramchandani,C.,1973. 异步并发系统性能的时间Petri网评价。博士论文,麻省理工学院,剑桥。[13] Reisig,W.,一九八五年Petri网Springer,EATCS Monographs on Theoretical ComputerScience,Vol.四、[14] Taentzer,G.,一九九六年。 并行和分布式图形转换。形式化描述及其在通信系统中的应用博士论文,Shaker Verlag。[15] Taentzer,G.,费希尔岛,Koch,M.,Volle,V.,1999. 分布式系统的可视化设计图变换。图形文法与图形变换计算手册,第3卷,世界科学第269
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- C++多态实现机制详解:虚函数与早期绑定
- Java多线程与异常处理详解
- 校园导游系统:无向图实现最短路径探索
- SQL2005彻底删除指南:避免重装失败
- GTD时间管理法:提升效率与组织生活的关键
- Python进制转换全攻略:从10进制到16进制
- 商丘物流业区位优势探究:发展战略与机遇
- C语言实训:简单计算器程序设计
- Oracle SQL命令大全:用户管理、权限操作与查询
- Struts2配置详解与示例
- C#编程规范与最佳实践
- C语言面试常见问题解析
- 超声波测距技术详解:电路与程序设计
- 反激开关电源设计:UC3844与TL431优化稳压
- Cisco路由器配置全攻略
- SQLServer 2005 CTE递归教程:创建员工层级结构
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功