没有合适的资源?快使用搜索试试~ 我知道了~
可在www.sciencedirect.com在线获取理论计算机科学电子笔记327(2016)71-91www.elsevier.com/locate/entcs基于模型转换的Petri网流分析ChristophMüller1PiotrRygielski2SimonSpinner2SamuelKounev2软件工程系德国维尔茨堡大学计算机科学研究所,邮编:97074摘要由于现代IT系统的规模不断扩大,其性能分析成为一项更具挑战性的任务。现有的仿真器无法在合理的时间内分析大型系统的行为,而分析方法则依赖于状态空间爆炸问题。可以使用流体分析技术近似高阶马尔可夫链模型的解决方案,使大型性能模型的时间效率分析。在本文中,我们描述了一个模型到模型的转换,从排队Petri网(QPN)到分层排队网络(LQN)。所获得的LQN模型可以受益于三个现有的求解器:LINE,LQNS,LQSIM。LINE在内部利用了流体极限近似来加速求解过程对于大型模型。我们提出的动机,开发自动化模型到模型的转换,并提出了一个系统的方法,我们遵循其设计。我们展示了使用有代表性的例子。最后,我们评估和比较现有的分析,模拟和流体分析求解器的性能预测。我们分析了求解器的局限性,求解时间和内存消耗。关键词:排队Petri网,分层排队网络,模型转换,流分析1介绍当今IT系统的复杂性计算资源(如CPU)无法再有效地垂直扩展。相反,资源的水平扩展(复制)提供了所需的功能,并满足了用户不断增长的需求由于系统的复杂性通常随着其规模的增长而增长,因此性能分析变得更具挑战性。1电子邮件地址:christoph@raytracer.me2电子邮件:{piotr.rygielski,simon.spinner,samuel.kounev}@ uni-wuerzburg.dehttp://dx.doi.org/10.1016/j.entcs.2016.09.0241571-0661/© 2016作者。出版社:Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。72C. Müller等人/理论计算机科学电子笔记327(2016)71为了能够对这类系统进行性能分析,需要高效、准确的性能模型求解技术。仿真技术通常需要长时间的仿真运行以达到所需的精度。另一方面,精确的分析模型支持状态空间爆炸问题[34],严重限制了实际中可以分析的模型的大小。流体分析是一种连续时间马尔可夫链的近似求解技术,特别适用于具有大状态空间的模型,同时显著减少计算量[32]。因此,流体分析技术为这两个极端提供了一个折衷的解决方案根据[4],已经发展了一种流体分析技术,通过用一组时变实变量来近似状态空间,并通过一组微分方程来描述它们的演化,从而避免与众所周知的通过连续时间马尔可夫链进行分析的方法相反,Hillston [14]提出了一种基于一组耦合的普通微分方程的基本数学表示这允许对具有大量复制组件和用户的系统进行高效的性能分析。我们在第2.1节和第3.1节中简要概述了胶体分析。1.1动机随机Petri网(QPN)[1]是一种功能强大且富有表现力的性能建模形式主义,它是经典随机Petri网(QN)[3]和着色广义随机Petri网(CGSPN)[8]的组合已经表明,即使是表示数据中心基础设施和软件的相对小的架构级模型(例如,如[22]中所示)在转换成QPN时可能导致数百个位置、不幸的是,现有的解析解技术不能应用于这种复杂性的QPN模型。在这些情况下,只能使用时间线性离散事件模拟。在这项工作中,我们利用分层网络(LQNs)的形式主义和它的求解器。LQN可以使用LQNS来求解,LQNS是LQN的标准求解器[11],LQSIM是离散事件模拟,或LINE [25],它利用超流极限近似来加速求解。我们在2.3节提供了更多关于LQN和QPN形式化的背景。我们利用模型到模型转换的能力将现有的QPN模型转换为LQN模型,随后可以使用LQNS,LQSIM和LINE求解我们系统地转换QPN模型,使没有QPN或LQN专业知识的用户能够从LQN表示和QPN求解器无法使用的LQN求解器的功能中获益SimQPN [18])。如果没有自动转换,手动将QPN转换为LQN的能力将仅限于这两个领域的专家此外,大模型的手动转换将是时间效率低且容易出错最后,第三个诱因是目前现有的QPN模型的多样性。存在高级模型,已经开发了向QPN的自动转换。Palladio组件模型(PCM)[2],C. Müller等人/理论计算机科学电子笔记327(2016)7173笛卡尔建模语言(DML)[6]和笛卡尔网络结构(DNI)[27]。DML和DNI支持到QPN的转换,但目前与利用Cubuid分析的求解器不兼容。我们将在3.2节详细介绍PCM、DML和DNI的现有转换功能。本文的目标是使目前现有的QPN模型的分析。我们提供了模型到模型转换的概念,将任何有效的QPN模型转换为可以使用LINE、LQNS或LQSIM求解的等效LQN实例。LINE求解器在内部利用了超流分析[25]。这项工作的主要贡献是自动模型到模型转换的概念我们描述的转换,其特点和局限性。此外,我们提出的规则的转换,通过演示哪些QPN模式被翻译成LQN结构。我们描述的QPN和LQN形式主义之间的语义差距。此外,我们还说明了LINE求解器不支持哪些LQN模型,但可以使用其他现有工具(例如,LQNS或LQSIM,不支持GUID分析)。最后,基于两个有代表性的例子,我们展示了在实践中的转换和评估的性能预测能力,解决时间,和内存消耗的SimQPN,LINE,LQNS,和LQSIM。1.2组织本文的组织结构如下。在第2节中,我们提供了QPN和LQN形式主义的背景,并描述了LINE求解器及其支持LQN模型的特性。随后,在第3节中,我们分析了性能预测中的现有工作,以及涉及QPN和LQN的现有模型到模型转换。第4节致力于描述贡献转换的概念,而在第5节中,我们给出了两个示例,分别使用简单和复杂的情况来演示转换。然后,我们使用四个求解器来评估模型,并量化它们的预测精度和求解时间。最后,在第6节中,我们总结并提出了未来工作的方向。2背景2.1流体分析在本文中,我们专注于超流分析(a.k.a,超流极限),这是一个确定性的实值过程,它近似于给定随机过程的演化,其中所有状态变量都由连续变量近似[14]。流体分析技术已经发展到应付状态空间爆炸问题。根据Tribastone等人[32],如果模型被表示为马尔可夫链,则性能指标(例如,利用率、吞吐量、响应时间)被建模为称为奖励模型的链的实函数。他们的分析的复杂性随着马尔可夫链阶数的增加而增加74C. Müller等人/理论计算机科学电子笔记327(2016)71分析不适用于大规模系统。Hilston [14]证明了高阶3连续时间马尔可夫链可以通过用x(t)代替实值随机过程Xn(t)/n来近似(Xn(t)<$nx(t)),其中Xn(t)是系统参数n的连续时间马尔可夫链参数n描述模型的尺度(例如,用户或组件的数量)。对于n的较高值,近似值更好[32]。这种近似已经被独立地应用于PEPA(性能评估过程代数)[14]和LINE求解器[25]2.2QPN和LQN简介随机Petri网(QPN)[1]是经典随机Petri网(QN)[3]和有色广义随机Petri网(CGSPN)[8]的结合。虽然CGSPN是一个强大的形式主义来描述的同步和定时被-或软件程序,他们缺乏表达能力,很容易描述调度的工作在硬件资源。除了CGSPN中已知的普通位置和转换之外,QPN因此引入了由队列和存放处组成的排队位置。该队列与传统QN中的队列相对应,包括调度策略和服务时间分配。传入的令牌首先在队列中提供,然后放入存储库,在那里它们可以用于传出的转换。使用QPN,可以在单个模型中对软件系统的软件和硬件争用进行建模[16]。为了求解QPN,我们使用SimQPN离散事件模拟器[17]。QPN图形符号如图1所示。队列存放嵌套QPN转换令牌OOOo oOO普通的地方免费WiFi子网位置Fig. 1. QPN图中使用的符号。分层网络(LQN)[10]是一种性能模型,是常规网络(QN)的扩展。与普通QN相比,LQN引入了层、软件服务器的概念,并且它们允许对同时资源占有进行建模。LQN通常用于以统一的方式对软件和硬件争用以及调度规则、同时资源占有、同步和阻塞进行建模[36]。LQN已经被开发为一种领域特定语言(DSL),覆盖广泛的计算机系统,特别关注软件和硬件系统。与此相反,QPN是通用模型,不绑定到给定的域。3.在m阶马尔可夫链中,未来的状态依赖于过去的m个状态。OOC. Müller等人/理论计算机科学电子笔记327(2016)71752.3LQN和QPN之间的语义鸿沟Woodside等人[36]声称“LQNs比竞争模型(Petri网,马尔可夫链,时间进程代数)具有很大的优势,它们可以扩展到具有数十个或数百个合作进程的大型系统。在求解中实现这样的加速通常与抽象所选数据或限制建模能力有关。在本节中,我们分析了QPN的局限性和困难。Heimburger在[13]中分析了QPN(SimQPN [17])和LQNS(LQNS [11])的求解器在基于Java EE的软件的性能预测方面的差异。我们将比较扩展到形式主义的一般水平,并在表1中简要总结了关键的差异。表1比较QPN和LQN形式主义的选定关键参数特征QPNLQN单位:单位:有色令牌电话工作量打开和关闭打开和关闭层次结构是的,你可以去看是的,层,不能重复气流方向任何有过渡的一个活动到一个条目,仅限高层到低层支持循环是 的 , 任 何 类 型 ( 包 括 无限)的循环迭代都可以按概率或确定性建模是的,大多数确定性建模的循 环 ( 例 外 情 况 见 第 4.3.1节),循环迭代次数必须已知(没有无限循环)起点没有明确的起点或过渡。可以计算出最先发生的顶层在QPN中,彩色标记是对行为建模的元素-它们被存放在不同的地方,并通过触发转换从一个地方移动到另一个地方。在LQN中,此功能是通过调用实现的,通常表示为指向一个条目。这两种形式主义都支持开放和封闭工作流的建模,但是LQN可以声称对封闭工作流的支持较少,因为涉及跨越多个层的环路的限制。层用于表示LQN中的层次结构,而在QPN中,网络可以使用子网位置嵌套当转换触发时,QPN令牌可以从一个地方移动到另一个地方。转换可以连接层次结构中给定级别的任意两个位置。然而,令牌可以被转发(通过输入和输出位置)到任何位置或转换,而不管层次结构中的级别76C. Müller等人/理论计算机科学电子笔记327(2016)71与QPN相反,LQN呼叫只能连接不高于呼叫所源自的层的层。这限制了调用的方向并缩小了建模能力。LQN层的层次结构不能被忽略,而QPN可以。另一个不同之处是循环的建模方式。LQN形式主义允许显式地对简单的循环建模,其中循环迭代需要由常数指定,有限值。QPN不直接支持循环,但是可以使用很少的位置,令牌和转换轻松构建循环。以这种方式构建的循环最后,QPN没有预定义的单一起点,而LQN有一个所谓的顶层,执行开始。在第4节中,我们描述了将QPN模型转换为LQN等价模型的转换规则2.4QPN和LQN的求解器及其局限性在本文中,我们分析了四个求解器:用于QPN的SimQPN [17],LINE [25],LQNS[11]和用于LQNs的LQSIM。我们简要描述了当前版本中求解器SimQPN是QPN稳态分析的工具。它基于QPN的离散事件模拟,并可产生吞吐量、利用率和响应时间统计数据(包括置信区间和直方图)。它的能力是有限的免费内存量的模拟几百万(×106) 令牌(令牌可以在分析过程中创建和销毁)。LINE求解器利用流体分析技术的优点来求解LQN。目前,其对LQN的覆盖仍然有限,例如,它不支持<和>节点,限制可以解决的模型集很明显。虽然计划支持此功能,但尚未提供具体的发布日期。根据LINE的开发人员的说法,支持或>节点。LQNS(解析)和LQSIM(模拟)是两种最先进的LQN求解器。LQNS求解器实现了几种分析求解技术,如均值分析(MVA),并结合了其他现有求解器的优点,即SRVN [36]和层方法(MOL)。根据[11],LQNS和LQSIM不支持递归调用(一个调用自己条目的任务),并且只提供对子系统复制的有限支持(关于限制的详细信息在[24]中解释)。LQNS不能处理其分支位于一个任务中而连接到另一个任务中的活动图。 此外,LQNS在求解具有只允许外部到达流。Brosig等人在[7]中评估了使用QPN和LQN的PCM模型分析。与LQNS相比,SimQPN被评估为提供对响应时间分布、可伸缩参数表征和阻塞行为的完全支持。另一方面,分析的LQN模型更紧凑,使用LQNS求解比在SimQPN中求解的相应QPN模型更快。C. Müller等人/理论计算机科学电子笔记327(2016)71773相关工作我们将相关工作分为两个领域:性能建模和基于模型的软件设计(即,模型到模型转换)。首先,我们分析的应用程序中的性能模型求解的流体分析,而随后,我们简要描述了模型到模型转换在性能分析中的应用3.1流体分析在性能模型中的应用承认关于随机Petri网[23]和随机Petri网[33]的工作,我们专注于在第2.1节和工作[14]中定义的随机Petri网分析近似马尔可夫链模型的流体极限首先由Kurtz在1971年的工作中引入[20]。从那时起,在由高阶马尔可夫链组成的性能模型通过扩展随机过程代数PEPA [14]将流体限制应用于性能建模,而[25]的作者在使用LINE求解器求解LQN时利用了流体限制。这些实现允许使用普通微分方程作为用于分析底层马尔可夫链的近似来求解软件和硬件性能模型(其是LQN的域)。LQN和随机代数在性能预测中有许多应用,例如[31,37,7,19]。只要可以应用LINE求解器[25],所有LQN性能模型都可以从流体极限近似中受益(参见第2.4节中的LINE限制)。据我们所知,LINE是迄今为止唯一一个利用了超流分析技术的LQN求解器。此外,我们还分析了其他可转换为LQN和QPN的性能模型,以便它们可以从本文中提供的转换中受益3.2现有的绩效模型转换元模型描述了模型实例中允许的元素以及它们之间的关系模型转换用于在不同元模型的模型之间自动对于性能建模和分析,转换主要用于从高级体系结构级性能模型转换 为低 级预 测模 型。 Koziolek 和Reuss- ner [19] 描述 了从 Palladio 组件 模型(PCM)(这是一个支持在设计时对软件架构进行服务质量分析的元模型)到分层嵌入网络(LQN)的转换,以获得其分析解决方案。Meier等人。[22]描述了从PCM到嵌入Petri网(QPN)的转换,并表明它比转换到LQN具有更高的准确性和更好的PCM元素覆盖率。另一个用于性能建模的描述性元模型是笛卡尔建模语言(DML)[5,15],其针对在线性能和资源管理场景。Brosig [5]实现了与DML不同的转换78C. Müller等人/理论计算机科学电子笔记327(2016)71转型贡献转化求解器模型其他其他其他DNIDMLPCMSimQPNQPN线LQNLQNS提出了一种算法,根据所需的预测精度和速度,自动决定应使用哪种变换笛卡尔网络架构(DNI)[27]填补了DML和PCM在数据中心网络领域DNI模型可以转换为OM- NeT++模拟和两个QPN-具有更精细和更粗糙的细节级别[26,27,28]。即使是小的DNI模型也可能导致大的QPN,因此在DNI的转换中不提取一些数据的情况下,有效和及时的性能分析是困难的。图二、选定的特定领域和通用模型,其可用的转换和求解器。在图2中,我们描述了一些现有的模型、求解器和模型转换。考虑的三个体系结构级模型(PCM、DML、DNI)支持使用相应的QPN模型转换使用SimQPN进行求解。只有PCM支持更多种类的解算器,包括LINE和LQNS。在将QPN模型转换为LQN之后,由于LQN解析求解器,我们期望获得比QPN等效模型更紧凑的模型和更快的求解时间(Brosig等人观察到类似的现象)在[7]中)。4化虚意境在本节中,我们介绍了在设计从QPN到LQN模型的转换时所遵循的系统方法,以便能够对前者进行分析转换由规则组成,这些规则针对源模型(QPN)的每个匹配元素执行,并在目标模型(LQN)中生成相应的元素。在第4.1节中,我们描述了QPN到LQN模型转换的总体方法。在第4.2节中,我们描述了将QPN元素映射到LQN元素的各个转换规则,并考虑了它们使用的上下文我们在4.3节中描述了转换的局限性。C. Müller等人/理论计算机科学电子笔记327(2016)71794.1方法我们的方法是基于一个模型到模型的转换映射QPN模型等价的LQN的,使现有的LQN分析求解器也可以这种转换要求我们定义一组规则,将QPN元素转换为等价的LQN元素。在最简单的情况下,变换规则是上下文无关的,单射函数映射单个QPN元素到相应的LQN元素。然而,当比较这两种形式时,人们可以很快看到,对于我们的QPN到LQN转换,情况并非如此:某些行为(例如,循环、分叉等)是LQN中的显式模型元素,而在QPN中使用位置和转换的组合来建模相同的行为。为了识别这种位置和转换的组合(在下文中我们称之为模式),转换规则还需要考虑模型元素的上下文。这样的上下文信息的示例可以是相邻位置和转变或QPN的拓扑。因此,可能有几个上下文敏感的转换规则适用于QPN中的同一模型元素。为了确定对某个模型元素使用一组上下文敏感的转换规则中的哪一个变换搜索某些模式(例如,循环、分叉、连接等)在QPN模型中。一般来说,图模式匹配是一个NP完全问题[12],但存在许多有效的模式匹配算法(例如,[9])假设任何有色Petri网都可以展开为单色Petri网[21]。LQN形式主义要求我们显式地将请求的起点 在QPN中,我们首先需要确定这些起始点,因为网络可以具有任意图形的形式。为了确定起始位置,需要计算QPN内的位置的可达性,并且可以识别开放或关闭的工作负载位置(例如,使用[35]中描述的方法在封闭工作负载的情况下,整个网络周围的循环被删除,并作为具有用户群体的特殊顶层包含在LQN中。起始位置也是搜索其他模式的起点。4.2转换规则表2给出了我们的转换规则的概述。第4.2.1- 4.2.7节详细描述了规则并附有示例4.2.1地点和地点在QPN中,我们区分了排队位置和队列。排队处由排队处和存放处组成。队列可以在不同的排队位置之间共享。调度用于描述QPN中的调度行为(例如, 硬件资源)。在LQN中,可以使用处理器来描述相同的调度行为。转换直接将队列映射到处理器。关联的嵌入位置映射到LQN中使用相应处理器的任务。在共享队列的情况下,引用队列的每个排队位置80C. Müller等人/理论计算机科学电子笔记327(2016)71QPQPQPQP表2QPN到LQN转换中使用的关键规则。QPN元素/模式LQN表示队列处理器住宿地点具有条目和分配的处理器的寻常地方得看具体情况。 见第4.2.3节代币颜色在各自的任务中为每种颜色单独输入过渡模式活动图为每一个输入颜色,类似的模式布线(见图。第五章)分叉和连接模式活动图环状图案循环符号(见图10)临界区关键区段由标记区段入口的层创建,具有有限的资源并使用具有FCFS调度策略的处理器将被映射到使用相同底层处理器的单独任务。图3说明了不同情况下的映射1Q1:FCFS,失效时间:0.1s1Q1:FCFS,失效时间:0.1sQ1:FCFS,失效时间:0.2s1Q1:FCFS,失效时间:0.1s2Q1:FCFS,失效时间:0.2s(一)图三. 将摆放位置改造为:(a)单位置、队列、颜色;(b)单位置、队列、两种颜色;(c)两个位置、单队列、单一颜色。处理时间采用指数分布建模,给定平均值(秒)。4.2.2地方的颜色QPN中的令牌可以表示单个请求、资源(例如,池中的数据库每个标记都有一个相关的颜色。颜色通常用于对请求的路由进行建模(不同的颜色遍历不同的路径)或表示各种类别的请求(例如,用于读取和写入请求的单独颜色)。虽然颜色有助于减少建模工作量,但它们不会增加QPN的建模能力。通过复制网的一部分,每个有色Petri网都可以转换为无色Petri网,而不会丢失信息[21]。LQN中的调用是相同的,并且不能通过不同的类型(或颜色)来区分。为了区分LQN中任务的不同类型的调用,我们映射e1[1]s=0.1Q1e一e二[1]s=0.1[1] s=0.2Q1(be1[1]s=0.1e1[1]s=0.2Q1(cC. Müller等人/理论计算机科学电子笔记327(2016)7181n每种颜色对应一个单独的条目。图3b中给出了一个示例。如果是预留位置,则使用QPN中指定的服务时间对条目进行参数化在普通场所的情况下,服务时间总是设置为零。4.2.3寻常地方普通的地方在QPN中扮演着特殊的角色。它们积累令牌,但在网络的时间方面的能力有限。我们根据它们出现的背景来改造普通的我们区分以下几种情况。首先,普通位置是模式的一部分,例如临界区,表示有限的资源(参见图11中的池位置)。第4.2.7节中描述的临界截面模式涵盖了这种情况。第二,如果普通场所不影响执行,则可以减少(例如,它只是为了方便建模者而使用)。一个普通的地方可以缩小,即,只有当该位置是前一个变换的唯一后继者和后继变换的唯一前趋者时,相邻变换才可以被合并图4a中描绘了一个示例第三,一个普通的地方也可以用作同步点。当后续的转换消耗多个令牌时,就会发生这种情况,并且令牌被保存在普通位置,直到存入所需的金额。根据LQNS文档[11],LQN使用可以指定为实变量的calls-mean参数来支持这种情况一个普通的地方,后面跟着一个转换,消耗n和产生m个令牌将导致调用平均值=m在LQN。一个图4b中描绘了示例。最后,一个普通的地方(这同样适用于一个存储的地方)可以在一个分支之前,在那里存入的令牌被随后的一个转换消耗我们在图4 c中描述它,其中位置p1的令牌具有相等的概率= 0。5将被转变t1或t2消耗。 概率可以根据转换的优先级来计算(默认情况下,所有转换的优先级相同)。QPN转换t1被转换为LQNLQN任务t1和t2的内容取决于图中抽象的QPNp1t1p2t2p32p1 t1+t2p3(一)(b)第(1)款(c)第(1)款见图4。依赖于上下文的普通位置的转换:(a)冗余位置减少;(b)标记的减少;(c)工作流中的分支21p1t1ep1(0.5分)t1p1t2ep10.5或0. 5个单位的t0(一)(一et1t2的1一个2p82C. Müller等人/理论计算机科学电子笔记327(2016)71(c111t1p311p2p11t1p1ep1&t1(一)(一ep3p2(一p3t2t3Cp11ep1ep211ep1ep21t1t2p1p3&1(一(一11t1p3ep31不1不3t1(一)eP2(一)eP3p2(bp2p4t2不3(d的p2一个p3的p2一个p34.2.4转换和模式在QPN中,转换从传入位置消耗令牌,并在传出位置产生新过渡可以以不同的模式(也称为颜色)触发,以模拟不同的动态行为。关联函数定义了一个触发模式消耗和产生的代币的数量和颜色。连接到同一模式的多个传入位置是一个同步点或一个联接(对于单个模式)。来自同一模式的多个传出位置表示分叉。在LQN中,转换被映射到活动图。Fork和join表示为<和>活动图中的节点。 包含多个模式的转换可以理论上分解为多个跃迁,每个跃迁具有单个模式。因此,它们可以被视为对任务的同一条目的独立调用。图5描述了可能的过渡配置。图五.转换:(a)join-and;(b)join-or;(c)fork;(d)join-fork。 QPN转换(表示为t1)包含消耗和产生给定数量的令牌的模式(菱形)当火。为了简洁起见,LQNs表示被简化(没有处理器)4.2.5分叉和连接模式QPN中的fork和join模式(如图6所示)是通过在转换中定义一种模式来构建的,该模式消耗令牌并将令牌转发到多个后续位置。在LQN中,分叉是用活动图建模的和>节点用于并行执行调用,并在完成后加入(同步)它们。我们在图6中描述了QPN中的一个简单fork-join模式,在图7中描述了转换后的LQN模型。找到分叉过程的开始和结束是一个挑战。虽然开始(fork)是由一个模式标记的,它接受一个令牌并将其转发到多个地方,但匹配的结束(join)必须通过处理图来找到。由于颜色可以在通过图的过程中改变,因此如何将fork与相应的join匹配并不简单。为了解决这个问题,我们利用以下可能性。 首先,我们尝试在单个LQN的任务中使用fork-join模式,以便可以使用更多的求解器。用于求解此类模型(参见第2.4节中的求解器限制)。QPN中的非平凡fork-join模式的分析(例如,其中颜色在分叉和连接之间改变)是使用用于图形分析的算法来进行的(例如,[29])。第二,我们可以跳过处理QPN拓扑以找到匹配的转换并且忽略QPN拓扑。ep1e p2t1ap3C. Müller等人/理论计算机科学电子笔记327(2016)7183C cLC CC cLC输入1-to-num-loop-iterC循环停止loop-c开始不t转发-生成业务子工作负荷变换规则通过这种方式,fork和join对可以被分离并放置在不同的任务上。虽然这限制了兼容的求解器集(LQNS不支持分离的fork-join),但转换的输出是一个有效的LQN模型,并且可以由求解器求解Q3:测定20见图6。包含分叉和连接模式的示例性QPN。见 图 7。 包 含 图6所 示 的 QPN 的 分 叉 和 连 接 表 示 的 示 例 性LQN。 转换t1和t2在这里表示为fork和join元素()。4.2.6环状图案QPN形式主义不支持直接对环路进行建模,但可以间接对环路进行建模。在QPN中建模的环路示例如图所示8和9。图中所示的循环8基于循环退出转换的关联函数中定义的概率进行迭代需要在转换中计算预期的迭代次数,因为LQN需要指定确切的迭代次数。在图9中,迭代次数由1-to-num-loop-iter转换产生的令牌数量LQN直接支持循环,因此一旦正确识别了循环模式并计算了迭代次数,转换就很简单了。在LQN中的一个循环的图形表示如图所示10.左回路控制loop-iter-done数字循环迭代到1输出见图8。具有概率建模迭代次数的QPN循环表示示例。[7]引自《论语》见图9。具有确定性建模的迭代次数的QPN循环表示的示例。”[26]引自。循环的QPN表示被视为需要由转换(或转换预处理库)发现以便进行转换的模式。在不受支持的循环模式的情况下(可能存在图8和图9中所示的两种模式之外的其他模式),循环的变换将由剩余的变换规则覆盖,然而,LQN循环的紧凑符号(如图9所示)将被用于表示循环的变换(10)不会被使用。Q1:测定5qp1开始t2qp3第二个问题:qp2测定12客户入口&(一(一qp2_entry[12]qp2_task {inf}&CPU 2 *客户任务(一)qp3_entry[20]qp3_task{inf}qp1_entry[5]qp1_task {inf}CPU_3*CPU_1*QP3[0]qp1[0]qp2[0]开始[0]我我我我我我我84C. Müller等人/理论计算机科学电子笔记327(2016)71开始t1任务1t3任务2t2见图10。具有确定性建模迭代次数的LQN循环表示。4.2.7临界区模式池见图11 。 包含临界 区的QPN 示例。 池包含,因此最多可以有三个令牌进入子网。临界区是一个只能同时处理有限数量对象的区域LQN和QPN都可以模拟临界截面。图11显示了QPN中的临界截面。它是用进入部分转换建模的,该转换从开始和从池位置开始消耗一个令牌。池中初始令牌的数量定义了同时进入该部分的令牌数量。在结束时,离开部分过渡将令牌进一步传递到结束位置,同时将另一个令牌存入池中,以便开始的下一个令牌可以进入该部分。LQN表示一个临界区,其层包含定义数量的FCFS队列。LQN中FCFS队列的数量对应于QPN的池令牌,该池令牌限制临界区中令牌的最大数量。每个队列中的每个任务都将执行一个同步调用来执行临界区中的工作。只有当这个调用结束时,下一个元素才会被出队和处理。我们在图中以图形方式描绘了LQN临界截面。12个。池的大小用任务关键部分的数量表示[3]。图十三.包含第二个内部环路的QPN示例。见图12。与图11中的QPN对应的临界截面的LQN表示。4.3转换的局限性在本节中,我们将描述QPN到LQN转换的限制。 本节涵盖LQN形式主义的一般限制,并不关注求解器特定的限制(LQN和QPN求解器的限制在第2.4节中介绍)。转换中最具挑战性的部分是:e1数位器CPU母环路后子工作负荷前回路开始输入section子网1休假部分端开始e1e1点击进入[0]call_subnet[0]离开[0]critical_section [3]e1子网e1端C. Müller等人/理论计算机科学电子笔记327(2016)7185需要调用LQN中的更高层,以及找到顶层(也称为参考层)的问题。我们将在本节讨论这两个问题4.3.1支持特定循环目前,LQN只支持一个循环节点,它执行定义数量的循环迭代,假设循环迭代的数量是预先已知的。不幸的是,不可能构建具有未知迭代次数的QPN环路的LQN模型,例如,如图13所示。这种限制来自于LQN不支持调用层次结构中更高的层。像LINE这样的求解器会遇到递归问题(超过最大深度)。对完整LQN模型的闭合工作负载进行建模的一般循环是一种特殊情况,其迭代次数可以是无限的或未知的。4.3.2寻找顶层LQN使用特殊的层(称为参考层或顶层)来启动工作负载周期。顶层的任务将根据思考时间参数周期性地执行。QPN不一定有明显的起点。找到首先触发或模拟已关闭工作负载的思考时间的转换也可能具有挑战性。为了解决这一限制,我们分析输入QPN并估计哪些转换将首先发生。我们的目标是找到对封闭工作负载的开始进行建模的过渡。不幸的是,QPN允许以多种方式表示系统,并且不能保证找到的转换负责表示闭合工作负载循环的思考时间。Walter等人在[35]中解决了这个问题。对于每个找到的过渡,我们创建一个在LQN中特别处理的顶层。我们构造LQN任务,通过从QPN的第一个触发转换的后继位置开始遍历下一个QPN元素来继承顶层5验证45.1示例1:简单QPN模型我们验证了转换的基础上两个例子。首先是一个简单的QPN模型,如图14所示,有三个重叠位置。每个排队位置都有一个单独的队列,具有确定的处理时间。循环执行以表示没有思考时间的封闭工作负载我们将其转换为LQN,如图15所示。根据起始位置的初始标记,转换t1转换t4在LQN中没有表示,因为它仅用于对已关闭的工作负载进行建模。该示例使用四个求解器求解:QPN 的SimQPN,LQN 的LQNS,LQSIM,LINE。在这个实验中,我们想表明,变换-4所有QPN和LQN模型使用在这纸是可用在线 下URL:http://go.uni-wuerzburg.de/aux86C. Müller等人/理论计算机科学电子笔记327(2016)71利用CPU1CPU2CPU3SimQPN0。3240。1350。541线0。324320。135130。54054LQNS0。324320。135130。54054吞吐量CPU1CPU2CPU3SimQPN0。02700。02700。0270线0。0270270。0270270。027027LQNS0。0270270。0270270。027027Q1:测定12第二个问题:测定5Q3:测定20开始t1 qp1 t2 qp2 t3 qp3t4见图14。 示例#1 QPN表示。图15. 示例#1 LQN表示。对于简单的情况,操作行为是正确的。我们研究的利用率的嵌入式的地方/处理器和吞吐量。结果见表3。表3实施例1利用率和吞吐量的预测几乎是相同的所有examined求解器。以SimQPN的预测为基准,LQSIM解决了具有最高误差的模型,该模型最大错误预测了3%的利用率。结果表明,该变换对简单情况是正确的我们预计LINE的不准确性会更高,因为预计使用超流体极限近似的求解方法对较大的模型效果更好,对较小的模型提供更高的误差。LINE的作者似乎已经解决了这个问题,因为小型模型的结果也很好。我们在第二个例子中研究了一个更复杂的5.2示例2:SPECjAppServer2001第二个示例中表示的系统基于Java 企业版(Java EE)服务器应用程序基准(SPECjAppServer2001)。该应用程序是仿照一个由四个域组成的业务:客户域(客户订单和交互),制造域(“及时”制造操作),供应商域(与供应商的交互)和公司域(客户,产品和供应商域)。据称,工作负载足够大和复杂,可以代表真实世界的企业系统[30]。在我们的场景中,模型关注于客户域,包括四种事务类型:NewOrder、ChangeOrder、OrderStatus和CustomerStatus。 该系统部署在两台独立的机器上,一台承载应用程序逻辑,另一台运行关系数据库。该模型除了包含两台机器(数据库的CPU和磁盘子系统)的物理资源外,还包含应用服务器的线程池、数据库服务器的连接和进程池等对模型及其客户入口客户任务(一[第12话]CPU_1_任务{inf}CPU_1*(一CPU_2_entry[5]CPU_2_task {inf}CPU 2 *(一[20]第二十话CPU_3_task {inf}CPU_3*CPU_3_调用[0]CPU_2_call[0]CPU_1_call[0]开始[0]C. Müller等人/理论计算机科学电子笔记327(2016)7187C利用DBS-CPUDBS-I/OWLS-CPUSimQPN0。7570。1711线0。757140。171421LQNS0。757420。171491 .一、00013LQSIM0。755250。175080。9828吞吐量DBS-CPUDBS-I/OWLS-CPUSimQPN0。0140。0140。014线0。01428570。01428570。0142857LQNS0。01429340。01429340。0142877LQSIM0。014590。014250。01404客户端_7客户端_7 [80](一(一(一WLS-T_6WLS-T_6 [60]DBS-C_2DBS-C_2 [40](一)DBS-C_1[12个][30] DBS-C_1 {inf}DBS-C_1*(一(一WLS-T_6[60]DBS-C_2[40]DBS-I_3[53]DBS-I_3 {inf}WLS-C_5[70]WLS-C_5 {inf}DBS-I_3*WLS-C_5*DBS-P_4[30]DBS-I_2[0]DBS-P_3[0]WLS-T_2[0]DBS-C_1[0]DBS-C_1[0]WLS-T_4[0]DBS-P_4[0]DBS-C_2[0]DBS-C_1[0]开始[0]DBS-P_3[0]公司简介[0]在我们以前的工作中可以找到对真实系统的验证[16]。不tt t tWLS线程池WLS-CPUxxxt1t2数据库服务器Xt5pDBS-工艺-池cc cc cxDB-Conn-PoolXxX客户端图16.示例#2的QPN表示。WLS代表数据库服务器,DBS代表数据库服务器。”[16]引自《论语》。图17. 示例#2的LQN表示。转换后的LQN模型如图17所示。 参考层 基于转换t1和客户端的位置来选择。位置Client表示关闭工作负载的思考时间(LQN中客户端7任务中的参数Z= 200),初始客户端数量设置为80(LQN中客户端7任务中的参数[80])。接下来,我们观察三个层,它们代表三个嵌套的临界区,这些临界区受到线程池、数据库连接池和数
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 新代数控API接口实现CNC数据采集技术解析
- Java版Window任务管理器的设计与实现
- 响应式网页模板及前端源码合集:HTML、CSS、JS与H5
- 可爱贪吃蛇动画特效的Canvas实现教程
- 微信小程序婚礼邀请函教程
- SOCR UCLA WebGis修改:整合世界银行数据
- BUPT计网课程设计:实现具有中继转发功能的DNS服务器
- C# Winform记事本工具开发教程与功能介绍
- 移动端自适应H5网页模板与前端源码包
- Logadm日志管理工具:创建与删除日志条目的详细指南
- 双日记微信小程序开源项目-百度地图集成
- ThreeJS天空盒素材集锦 35+ 优质效果
- 百度地图Java源码深度解析:GoogleDapper中文翻译与应用
- Linux系统调查工具:BashScripts脚本集合
- Kubernetes v1.20 完整二进制安装指南与脚本
- 百度地图开发java源码-KSYMediaPlayerKit_Android库更新与使用说明
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功