基于结构化的自动性能建模骨架的应用程序

理论计算机科学电子笔记190（2007）167-183www.elsevier.com/locate/entcs一种基于结构化Gagarine Yaikhom1，2Murray Cole1，3 Stephen Gilmore1，4Jane Hillston简·希尔斯顿1，5爱丁堡大学信息学院，爱丁堡-EH 9 3 JZ，英国摘要在本文中，我们讨论了一种结构化的方法，自动性能建模的骨架为基础的应用程序。这使用了性能评估过程代数（PEPA）和面向模式的层次表达方案的合成。这样的方法在并行和分布式系统中是重要的，其中性能模型必须基于资源的当前状态定期更新。保留字：性能评估，模式，数学模型。1引言使用高级构造设计系统具有明显的优势。这一点在结构化并行和分布式编程中早已被认识到，其中（通常是顺序的）子任务被结构化用于并行组装[1][2][3][4]。最近的一个例子是BPEL语言，它将Web服务的组合结构化为一个编排，在编排中，更简单的服务被聚合成一个组合[5]。这些描述风格背后的技术议程是对计算结构进行高层次、简洁的描述，这些描述可以很容易地重新塑造，以便找到任务到计算资源的良好映射应对程控仪进行1本 文 得 到 了 EPSRC 项 目 ENHANCE （ “Enhancing the Performance Predictability of Grid Applications withPatterns and Process Algebras” （ GR/S21717/01 ） ） 和 EU FET-IST Global Computing 2 项 目 SENSORIA（“Software Engineering for Service-Oriented Overlay Computers”（IST-3- 016004-IP-09））的支持。 JaneHillston还获得了EPSRC高级研究奖学金EP/c543696/01的支持。2电子邮件地址：gyaikhom@inf.ed.ac.uk3电子邮件地址：mic@inf.ed.ac.uk4 电子邮件地址：stg@inf.ed.ac.uk5 电子邮件地址：jeh@inf.ed.ac.uk1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2007.07.010168G. Yaikhom等人理论计算机科学电子笔记190（2007）167LL涉及在满足对诸如服务器和其他执行环境之类的组件的利用的然而，允许子任务被组合的组合语言通常不提供用于评估新版本是否可能改进前一版本的性能的机制。此外，适合于性能建模的语言，例如随机过程代数，通常不是我们意义上的结构，并且不具有表达子任务组成的语言装置本文的目的是通过从结构化应用程序描述中自动生成进程代数模型来弥合这一差距，从而允许设计人员将其应用程序编译成适合于通过稳态或瞬态分析进行性能评估的进程代数模型，或通过概率模型检查进行验证。在本文中，我们专注于可以得到的结果我们使用算法框架[6]作为结构化组合语言的范例，并使用性能评估过程代数（PEPA）[7]作为我们的过程代数。我们的例子来自结构化并行和分布式编程领域。2背景在本节中，我们将简要描述所使用的随机过程代数以及基于算法框架的结构化并行和分布式编程方法。欲了解更多详情，请参阅[7]和[6][8]。2.1绩效评估过程代数（PEPA）PEPA是一个马尔可夫过程代数，其中一个指数分布的随机变量，代表持续时间，与每个活动相关联。在所有的进程代数中，模型都是由通过活动交互的组件构建的。该语言的语法如下：S：：=（α，r）.S|S + S|CS（前缀、选项和组件名称）P：：=PD P| P/L|C（并行、隐藏和组件名称）这里，S表示顺序组件，P表示并行执行的模型组件C代表一个常数，表示由定义引入的序列成分或模型成分。CS代表常数，表示顺序分量。prefix（α，r）.S为组件指定了第一个活动：它将具有动作类型α和由参数r的指数分布控制的持续时间。选择操作符（+）启用其两个操作数的活动。第一个要完成的活动区分了其中一个：另一个被丢弃。系统将表现为导数结果从所选组件的演变中使用协作组合子（D）将结构引入 中没有补充操作，PEPA，这捕获了一个CSP风格的并行组合：组件在协作集合L中同步由两个组件启用的那些动作G. Yaikhom等人理论计算机科学电子笔记190（2007）167169这种同步尊重有限容量的概念，这意味着不能通过同步使组件运行得更快。因此，共享活动的持续时间由与每个贡献活动相关联的随机变量的最小值决定在某些情况下，组件对于同步活动是被动的，这意味着它将以任何速率参与其合作伙伴组件的期望。 这用特殊的符号T表示，即（α，T）。当合作集L为空时，我们使用简写符号- 是的最后，有一个抽象运算符hiding，表示为P/L，它允许类型在L中的活动的类型被可区分的类型τ替换，它表示私人或隐藏的活动。语言定义在[7]中通过将pepa模型映射到连续时间马尔可夫链（CTMC）的小步结构化操作语义来表达。然后可以使用标准技术分析CTMC2.2算法骨架并行编程系统设计的骨架方法提出了通过限制机制来包含并行编程的复杂性，每个骨架规范都捕获了并行计算的常见模式的逻辑行为，同时打包和隐藏了其具体实现的细节。提供一个基于XML的编程方法，同时提高了程序员操作的抽象层次，并为调度系统提供了关于应用程序所表现出的时间和结构交互模式的关键信息。利用此信息的责任从程序员传递到编译器和/或运行时系统。在一般情况下，从等效的ad-hoc消息传递程序中获得这样的详细信息是在本文中，我们展示了如何使用结构信息来构建应用程序的PEPA性能模型3用骨架为了自动生成性能模型，必须首先以捕获其本质的形式表示给定的应用程序。在本文中，我们采用了一种面向模式的方法，这是基于算法的概念，一个系统，旨在丰富和简化，分布式和并行应用程序的结构开发。必须理解的是，尽管引入的构造可以直接由人类性能建模者使用，但它们旨在用作从基于分布式对象的应用程序自动生成性能模型的内部接口为了便于对自动化进行全面的处理，我们将重点关注以下三个基本框架。66这些基本形式的扩展可在工具http://groups.inf.ed.ac.uk/enhance/。170G. Yaikhom等人理论计算机科学电子笔记190（2007）167任务12任务10任务7任务6任务9输入流输出流任务8任务11Fig. 1. 具有嵌套管道和任务复制的应用程序的数据流程图。管道骨架管道骨架顺序排列一组组件，以便在最终结果离开之前，进入管道的数据单元依次在这些组件中的每个组件中进行处理（以组件指定的顺序管道。在我们的方法中，我们将使用以下构造来指定管道：pipe（组件数>）;骨架构造中包含的组件可以是骨架组件（导致分层嵌套），也可以是任务组件（处理数据单元的位置）。在后一种情况下，任务组件指定为以下结构：task（component name>，rate>）;这里，速率>是在对任务的计算性能进行建模时处理-使用交易框架交易框架并行复制给定的任务组件，以便在最终结果离开交易之前，进入交易的数据单元可以由其中一个复制组件处理。该任务组件接收给定的数据单元是由循环数据分发策略选择的我们使用以下结构来指定交易：deal（number of replications>，component name>，rate>）;场骨架场骨架类似于交易：并行复制给定的任务组件，以便进入场的数据单元由其中一个组件处理。然而，不同的是，选择应该接收给定数据单元的任务组件是不可预测的，在完成较早的计算时是动态需求驱动的。因此，非确定性是概率性的，其中下一个数据单元被发送到已经完成处理先前分配给它的数据单元的后续任务之一。我们使用以下构造来指定场：farm（复制次数>，组件名称>，速率>）;现在我们将通过一个具体的例子来说明这些结构的用法。想象一个类似于图1所示的系统。 在这里，我们有一个六阶段7管道在最高级别。这些阶段中的一些是任务组件（例如，阶段1和6），而另一些是分层框架嵌套（例如，阶段2是农场，而阶段3是交易）。7流水线的组成部分通常被称为任务2任务0任务1任务3任务5任务4G. Yaikhom等人理论计算机科学电子笔记190（2007）167171管农场交易农场交易0123456789101112系统基于JSON的表达式显示在右侧。这种描述是分层的，每个子树都是在同一个子树级别上从左到右从深到深地描述的。只有在前面的所有子树都被完全描述之后，我们才进入同一级别的下一个子树;即，没有带有不充分任务分配的骨架嵌套。pipe（6）; task（“task”，1.0）;farm（3，“task”，3.0）;deal（2，“task”，2.0）;farm（3，“task”，3.0）;deal（3，“task”，3.0）;task（“task”，1.0）;把整个工作看作是对《公约》的逐步完善系统描述，我们在最高层次上构思系统，并继续进行改进，直到最低层次的描述仅由任务组件组成图二、对应于图1所示的示例系统的骨架层次树1.一、根据下面的讨论，在这里谨慎地提到，对于每个结构化应用程序，层次树数据结构由模型生成工具在内部维护。我们将把这个数据结构称为骨架层次树（如图2所示）。框架层次树封装了描述中提供的大部分信息（系统的整体结构和组件细节在需要时，会自动从该树中导出其他信息（例如，连接任务的数据依赖关系图）。我们现在将详细讨论这些问题。4性能模型从结构化应用程序的给定描述生成PEPA性能模型可以分为三个阶段。在第一阶段，有向无环图（表示任务组件之间的数据依赖关系）从骨架层次树中导出然后在以下阶段中使用该图。在第二阶段，确定每个任务组件的过程定义最后，在第三阶段，整个系统的建模相结合的任务组件，骨架组件，基于他们的层次结构。最后阶段很重要，因为它通过建立同步集来完成性能模型，模型求解器将在同步不同组成级别的任务组件时使用这些同步集172G. Yaikhom等人理论计算机科学电子笔记190（2007）167i=0时我算法1GS（节点）：从骨架层次树n：=node.nchildren//子节点数node.slist：=parent.slist//从父节点继承源列表node.stype：=parent.stype//继承源模式类型对于i：=0 to（n-1），GS（node.childi）//递归生成子源列表如果node.type是task，那么//Node是一个task组件v：={x：wherex =node.index}如果parent.type是deal或farm，那么// Parent是一个可复制骨架临时节点：=v其他parent.slist：=vparent.stype：=pipe//更新源模式类型elseifnode.typeispipe then// Node is a pipeline skeletal如果是父类，则输入deal或farm，然后// Pipeline within replicable临时节点：=node.slist其他parent.slist：=node.slistparent.stype：=node.type//更新源模式类型else ifnode.typedealorfarm then// Node是一个可复制的骨架m：=n−1temp//合并子节点上的临时列表如果parent.键入deal或farm，则//replicable内的Replicable临时节点：=m其他parent.slist：=mparent.stype：=node.type//更新源模式类型4.1有向无环图的判定令有向非循环图G（T，E）表示数据，其中T是任务组件的集合，E是连接任务组件的有向边的集合依赖关系图，其对应于骨架层次树。为了从给定的骨架层次树导出这样的图，我们使用递归前序树遍历算法，描述如下：对于T中的每个任务，分配唯一的索引i，其中0 ≤ i<|不|. 我们将使用符号ti来表示：为了具体实现图G，将每个任务ti与两个有序的任务索引集相关联：（1）源列表Si，它给出了T中任务i可以从其接收数据的任务集;（2）目的列表Di，它给出了任务i可以向其发送数据的任务集。它们的正式定义如下：Si={j：（tj，ti）∈E，ii = j}和Di={j：（ti，tj）∈ E，ij}。当从上下文中可以清楚地看出我们指的是哪个任务时，我们可以选择去掉Si和Di中的下标。在此需要注意的是，这些集合G. Yaikhom等人理论计算机科学电子笔记190（2007）167173仅列出任务的所有可能的前导（或后继）-通过应用相应的源（或目的）交互方式，从这些集合中确定任务最终与之通信的有效集合，我们将很快讨论这一点。例如，给定一个包含两个连续交易的管道，一般情况下，第一个交易中的所有任务都将在第二个交易的源列表中。然而，如果交易的规模相同，那么事实上，第二个交易中的任务只会从第一个交易中具有相同交易内兄弟排名的任务接收数据（有效集因此是单例集）。可以观察到，这两个集合与任务集合T相结合，完全定义了有向无环图G。因此，我们使用递归树遍历算法从骨架层次树生成这些集合。在算法1中，我们展示了从骨架层次树导出源列表的过程。在该算法中，每个节点维护以下数据：指向骨架层次树中其父节点的指针parent;其子节点的数量nchildren;任务索引列表slist，该列表可用于该节点作为源（实际上，这是算法将确定的）;源模式类型stype;节点类型type（这可以是骨架节点或任务节点，参见图2）。除此之外，每个节点还维护一个临时列表temp，该临时列表由其父节点使用，同时终止父节点的源列表。这里注意，对于一些涉及任务复制的骨架节点，这些节点上的源列表不能最终化，直到它的所有子树也最终化了它们的源列表。类似的算法用于导出目的地列表。4.2任务组件一般来说，结构化系统中的任务组件是一个重复经历接收→计算→发送转换的过程。根据包含任务的更高层次结构，这三个基本活动是专门化的，相应地。例如，在某些情况下，这些活动中的一些活动被跳过（如在生产者任务中，它不执行接收活动;或在消费者任务中，它从不执行发送活动）。如4.1节所述，当一个任务与其他任务通信时，执行通信的任务基于S（或D）的有效子集，由交互方式确定这种交互方式基于此任务之前（或之后）的骨架这种方式比较容易定义，作为源（或目的地）列表的函数的交互，其从相应的列表中选择本质上，该函数因此为每个任务概述了该任务应该如何与骨架层次树中的其余任务交互：源函数定义了应该如何接收数据;目标函数定义了应该如何发送数据。给定任务的交互方式对应于任务在骨架层次树中的位置。正如我们在算法1中所看到的，源模式类型（stype）是相对于包含任务的骨架组件设置的;目标模式类型的设置类似。如果我们分别代表174G. Yaikhom等人理论计算机科学电子笔记190（2007）167def发送（β（D），d′）21d′=Compute（d）0接收（α（S），d）图三. 一种转换图，它给出了系统中任何一个任务所执行的一般活动的顺序。 在模型生成过程中，这些活动根据其中任务与其前置任务和后继任务交互。源和目的地交互函数与α和β，我们可以总结一个任务，如图所示3 .第三章。从这个抽象的表示中，很明显，任务组件的PEPA过程定义由子集α（S）和β（D）确定;以及接收→计算→发送转换所需的α和β之间的关系。由于任务可以有不同的α和β，我们必须为所有可能的模式组合确定过程定义模板为了简洁起见，让我们用{α（S）→ti→β（D）}表示这样的组合;这意味着目的地函数β当两个函数中的任何一个没有定义时（如本节开始时所讨论的），我们用一个来表示（如生产者任务的{→ti→β（D）}此外，由于列举所有的情况可能相当复杂，我们将通过对不同的相互作用函数之间的关系进行一些观察来进一步压缩情况调查（基于骨架结构的定义，见第3节）。这些观察结果是：（a）交易交互功能是场的特殊情况，其中场中的概率非确定性通过强制执行循环数据分发策略来消除。(b)流水线交互功能是交易的特殊情况，其中源（或目的地）列表是单例集。根据后面的观察，将忽略涉及Pipeline的案例的讨论，因为它在Deal的案例中有所涉及。但是，我们将介绍交易和场交互功能的组合。案例{B →ti→Deal（D）}在这种情况下，ti是生产者任务。该任务产生数据单元，然后将其发送到D中根据循环策略选择的任务之一。相应的PEPA过程定义，其中n=| D|λi是与t i相关的计算活动，表示如下：ti=（λi，T）. （移动i0，T）。（λi，T）。（移动i1，T）。···（λi，T）。（movei（n-1），T）.ti;这里moveij表示从任务i到第j个任务的数据通信，D. 我们选择这种表示法而不是sendij，因为这些活动将被在后面定义同步集时再次使用。如果采用后一种符号，我们需要定义一个系统来匹配相应的发送ij和接收ji对（实际上这是不必要的）。在{Deal（S）→ti→n}的情况下，ti是一个共同的问题。它从S中的一个任务中接收数据单元，然后消耗这些数据单元。通过遵循类似于前一种情况的符号，我们有以下过程定义：G. Yaikhom等人理论计算机科学电子笔记190（2007）167175defdefdefdefti=（move0 i，T）. （λi，T）。（移动1 i，T）。（λi，T）。···（move（n-1）i，T）. （λi，T）.ti;这里n = |S|源列表中的任务索引数。 基于argu-与上一个案例中使用的部分类似，我们使用moveji表示从S中的第j个任务到任务i的数据通信。情况{Deal（S）→ti→Deal（D）}在这种情况下，ti是中间任务：从S中的任务之一接收的数据单元被处理，并且结果被发送到D中的任务之一。在发送和接收通信的每个实例中，有效任务是根据循环分配独立选择的政策当源列表和目标列表的基数相同时，p=|为|D|，流程定义很简单，如下所示：|, the process definition is simple, as shownbelow:ti=（move0 i，T）. （λi，T）。（移动i0，T）。（移动1 i，T）。（λi，T）。（移动i1，T）。···（move（p−1）i，T）. （λi，T）。（movei（p−1），T）.ti;当|S|为|D|然而，两者之间并不存在直接的对应关系。源任务和目标任务。因此，有必要解决这一不匹配问题直到我们找到一个可重复的活动序列如果我们将周期性p定义为重复开始之后的不同接收→计算→发送转换的数量，则很容易看出周期性是以下各项的最小公倍数：|S|和|D|.基于此，我们有以下过程定义：ti=（移动Xi，T）。（λi，T）。（移动Iy，T）。···（重复p次，在每次迭代中递增k）.ti;其中0 ≤k< p，x = k mod |S|y = k mod |D|.当|S|= 3和|D|= 2，例如，稳态活动序列为32R1S1λr10的s0λR2S14λs0R2λS1r10的λs0λ1R150它给出了以下过程定义：ti=（move0 i，T）. （λi，T）。（移动i0，T）。（移动1 i，T）。（λi，T）。（移动i1，T）。（移动2 i，T）。（λi，T）。（移动i0，T）。（移动0 i，T）。（λi，T）。（移动i1，T）。176G. Yaikhom等人理论计算机科学电子笔记190（2007）167（移动1 i，T）。（λi，T）。（移动i0，T）。（移动2 i，T）。（λi，T）。（movei1，T）.ti;以上三种情况可用于完整定义Pipeline和Deal任意组合的任务组件。现在我们将通过引入解释与农场骨架相关的非决定论的情况来扩展这一点。G. Yaikhom等人理论计算机科学电子笔记190（2007）167177def在这种情况下，任务是生产者。然而，主要的区别是非确定性，我们用PEPA的choice（+）运算符来捕获。这在以下过程定义中显示：defJti=（λi，T）.ti;J定义ti=（movei0，T）.ti+（movei1，T）.ti+···+（movei（n−1），T）.ti;其中n = |D|.在一个数据单元产生之后，它被发送到D中的任何一个任务，这使任务回到数据产生状态。在{F arm（S）→ti→n}的情况下，该情况下的tas k是一致的。这种情况下的定义与前一种情况类似，如以下定义所示defJ J Jti=（move0i，T）.ti+（move1i，T）.ti+···+（move（n−1）i，T）.ti;J定义ti=（λi，T）.ti;其中n = |S|. 在从中的任何一个任务接收到数据单元之后，S，它被消耗;因此将任务带回到接收状态。情况{农场（S）→ti→农场（D）}在这种情况下，ti是中间任务。这类任务的过程定义可以通过结合前面两种情况来实现，如下所示：defJ Jti=（move0 i，T）. （λi，T）.ti+···+（move（x−1）i，T）. （λi，T）.ti;J定义ti=（movei0，T）.ti+（movei1，T）.ti+···+（movei（y−1），T）.ti;其中x = |S|和y = |D|. 中的任何一个任务接收数据单元，S中的任何一个任务进行处理，并将结果发送到D中的任何一个任务。情况{交易（S）→ti→农场（D）}在这种情况下，ti是中间任务。此任务的独特之处在于，对于以循环方式接收的每个数据，处理结果都按概率发送给已完成的任务之一处理先前分配给它的作业。这里需要注意的是，由于在这个任务之前的源函数是Deal，所以任务i必须根据循环方式接收下一个数据，因为可以推断S中的任务以循环方式接收它们的数据。一旦数据被接收和处理，结果就被发送到一个场;因此，使用了一个选择组合在调度结果时，如以下流程定义所示t=（移动，T）。（λ，T）.t0;我0我我t0d=ef（移动e，T）.t1+（移动，T）.t1+···+（移动，T）.t1;我我我···i1ii（y−1）itx−1d=ef（move，T）。（λ，T）。tx;i（x−1）iiitxd=ef（移动e，T）.t+（移动，T）.t+···+（移动，T）.t;我我我i1ii（y−1）i其中x = |S|-1且y = |D|.情况{农场（S）→ti→交易（D）}这种情况与前一种情况类似，除了选择组合的位置颠倒之外。因此，我们有以下过程定义：178G. Yaikhom等人理论计算机科学电子笔记190（2007）167deft=（移动，T）.t0+（移动，T）.t0+···+（移动，T）.t0;i0ii1ii（x−1）iit0d=ef（λ，T）. （movee，T）. t1;我我···i0ity−1d=ef（move，T）.ty+（移动，T）.ty+···+（移动，T）.ty;i0ii1ii（x−1）iityd=ef（λ，T）. （movee，T）. t;我我我其中x = |S|和y = |D|-1。在算法2中，我们结合了上述所有情况，以便为任务层次树中的每个任务生成过程定义。为了简化表示，为这些情况中的每一种情况指定一个情况编号，如右侧表格所示。在这里，列列出目的地-国家模式;而行枚举源模式。此外，在算法2中，表达式S（j）给出S中的第m个任务索引，其中m= j mod |S|目的地列表的相应表达式D（j）的定义类似。我们使用接口Output：来发出生成的流程定义的片段。对于此接口的每次调用紧接着，直到行尾，作为过程定义的一部分发出。还要注意，调用Output：的顺序对生成的流程定义的有效性很重要为了生成骨架层次树中所有任务的所有过程定义，我们遍历层次树并为所有节点调用算法2，这些节点是任务节点。一旦完成，我们就完成了性能模型生成的第二阶段。因此，我们进入最后阶段，在那里我们定义同步集。在我们继续之前，值得回顾的是，在定义这些同步集时，将使用与任务之间的通信相对应的moveij和moveji4.3系统建模在第二阶段结束时生成的所有过程定义仅对每个任务组件的性能进行建模，而与其他组件无关。由于结构化的应用程序是这些任务的合作表现，它们必须相应地同步相对于层次组成的水平这是在模型生成的最后阶段完成的，我们现在将讨论。在骨架层次树的每一级，每个子树对应于封闭子系统，其中仅任一侧上的边界任务组件与它们的相邻兄弟子树交互。该子系统内的任务组件（中间组件）与同一子系统内的因此，模型生成的最后阶段通过定义层次树的每个级别中的相邻子树之间*管交易农场*0123管4567交易891011农场12131415G. Yaikhom等人理论计算机科学电子笔记190（2007）167179def我我我我我我我我我算法2GP（i）：为任务i生成过程定义输出：ti=01- 02 - 2016刘晓波（|S|、|D|）//最小公倍数，如果其中一个为零，则求和如果case是1或2，则// Predecessor pipe、successorPipe或Deal对于0 ≤j< l，执行输出：（λi，T）。（移动i、D（j）、T）。else ifcase is 4 or 8then//PredecessorPipe orDeal，successorpipe对于0 ≤ j 1）（j<）|D|− 1）然后输出：tielse ifcase is 12then//PredecessorFarm，successorFarm输出：（移动S（0），i，T）.tJ对于1 ≤j<|S|做输出：+（移动S（j），i，T）.tJ输出：;tJd=ef（λ，T）。我我否则，如果case是7或11，则//PredecessorPipe或Deal，successorFarm对于0 ≤j<|S|做输出：（移动，T）。（λ，T）。tj;tjd=ef（移动e，T）。S（j），i我我我i，D（0）如果j<|S| −1 then Output：tj+1else输出：ti对于1 ≤k<|D|做输出：+（移动i，D（k），T）。如果j<|S| −1 then Output：tj+1如果j<|D| − 1 then Output：ti否则，如果case是13或14，则//PredecessorFarm，successorPipe或Deal对于0 ≤ j <|D|-1，初始化x = 0，并在每一步中递增2。输出：（移动S（0），i，T）.tx对于1 ≤k<|S|做输出：+（移动S（k），i，T）.tx输出：;txd=ef（λ，T）。（move，T）。iii，D（j）国际法委员会<|D|−1则输出：tx+1;tx+1d=ef我我else ifcase is 15then//前趋场和后继场输出：（移动S（0），i，T）。（λi，T）.tJ对于1 ≤j<|S|做输出：+（移动S（j），i，T）。（λi，T）.tJ输出：;tJd=ef（m 〇 vei，D（0），T）。对于1 ≤j<|D|做180G. Yaikhom等人理论计算机科学电子笔记190（2007）167输出：ti+（移动i，D（j），T）。输出：ti;G. Yaikhom等人理论计算机科学电子笔记190（2007）167181LL算法3GM（node，nchild）：生成系统模型i：=node.indexr：=node.rank//节点在兄弟节点如果node.type为task，则输出：ti如果r nchild-1，则如果parent.type=（交易或场），则输出D，其中L ={移动i，j：j= Di（k），0 ≤k<|Di|}其他其他输出量：||输出：（对于0≤jnode.nchild，GM（childj，node. nchild）//重新定义模块Output：）如果r nchild-1，则如果parent.type/=（交易或场），则输出 D 哪里L ={移动x，y：y = Di（j），x = Sy（k），0 ≤j<|Di|，0 ≤k<|Sy|}其他输出量：||直到所有任务组件同步。我们使用算法3来执行这个最终阶段。在这个算法中，我们再次使用深度优先的前序树遍历。由于两个子树之间的同步集可以相对于这些子树之一表示，我们选择了一个前向表达方法，其中子树的同步集是在对应于该子树的子系统被同步之后确定的 我们可以在算法中看到：每当节点是任务时，我们发出该任务，并生成同步集，该任务利用该同步集与其所有后继任务同步;当节点是骨架组件时，我们通过考虑该子系统的“发送”边界上的任务来生成同步集，该子系统与后继子树的“接收”边界上的任务交互。引入计算和通信速率到目前为止，我们生成的模型在两个方面是不完整的。虽然我们有任务定义和它们的交互结构，但计算和通信速率都是被动的。由于在执行同步时，活动速率是必要的，因此我们通过将相关的活动速率引入模型来完成模型。由于这里开发的模型生成方法主要针对分布式应用程序，因此下面的讨论将集中在此上下文中。在分布式系统中，确定任务速率的主要因素是任务被分配执行的处理元件的速率（例如，182G. Yaikhom等人理论计算机科学电子笔记190（2007）167//计算率。Processor_0=（comp_0，1.0）.Processor_0;Processor_1=（comp_1，3.0）.Processor_1;Processor_2=（comp_2，1.0）.Processor_2;Processor_3=（comp_3，2.0）.Processor_3;Processor_4=（comp_4，1.0）.Processor_4;//通信速率。网络=（move_0_1，1.0）.网络+（move_1_2，1.0）.网络+（move_2_3，1.0）.网络+（move_3_4，1.0）.网络;//任务定义。t_0 =（comp_0，infty）.t_01;t_01=（move_0_1，infty）.t_0;t_1 =（move_0_1，infty）。(comp_1，infty）。(move_1_2，infty ） .t_1; t_2 = （ move_1_2 ， infty ） . (comp_2 ， infty ） 。(move_2_3 ，infty ） .t_2; t_3 = （ move_2_3 ， infty ） .(comp_3 ， infty ） 。 (move_3_4 ，infty ） .t_3; t_4 =（move_3_4，infty）. (comp_4，infty）. t_4;//系统模型。网络move_0_1、move_1_2、move_2_3、move_3_4>（t_0 move_0_1> t_1t_2 t_3 t_4）（Processor_0||处理器_1||处理器_2||处理器_3||处理器_4）//返回表达式。T1 = 1.0 * {**||（t_01 ||t_1||--||--||**）||（**）||--||--||--||（**）};见图4。 从骨架表达式自动生成的PEPACPU频率）。另一方面，任务间通信速率主要由连接这些处理元件的底层网络的通信延迟确定。因此，为了完成这个模型，我们引入了另外两个部分。基于处理元件的速率μ，引入与计算活动相关联的任务速率λ作为前导：def def处理器0=（λ0，μ0）.处理器0;处理器1=（λ1，μ1）.处理器1;···注意，计算活动λi必须与任务i的定义中所用的相同。类似地，我们通过添加从表示通信链路的邻接矩阵确定的部分来引入通信速率。同样，这里使用的移动ij有关性能模型的示例，请参见Fig. 四、4.4业绩结果我们现在将讨论性能结果的数值分析，其展示了所生成的模型与没有自动性能建模支持的朴素系统相比的实际优势在这些分析中，我们大量借鉴了自动模型生成方法的一个实际应用：并行和分布式应用程序中任务的动态调度[9][10]。许多这样的应用程序展示了一个高级结构，其中最外层的骨架是一个管道。图5，我们绘制了具有五个阶段的流水线应用程序的预测性能8。性能以吞吐量来衡量，8.为了将我们的分析集中在任务速率上，我们为所有任务间通信设置了相同的通信速率。这是必要的，以便在我们对比由于不同任务速率而实现的性能时，最大限度地减少通信对相对吞吐量的影响。G. Yaikhom等人理论计算机科学电子笔记190（2007）167183250200均匀瓶颈150100500100 150 200 250 300 350 400 450 500率图五.瓶颈级对流水线性能的影响。在这里，我们有一个三阶段的管道。 除中间阶段外，所有阶段的作业处理率都是均匀增加的。 的 中间阶段的作业处理速率保持在每单位时间50个作业的恒定值140120100瓶颈2交易3负责2农场3农场80604020100 150 200 250 300 350 400 450 500速率（中间阶段速率固定为50）见图6。通过复制瓶颈任务，图5 复制通过两种方式完成：使用交易和场。 复制任务的数量也各不相同 （重复2次和3次）。其中，稳定状态下的吞吐量是单位时间内完成作业的期望数量正如我们所看到的，只要每个阶段处理数据单元的速率均匀增加，流水线的吞吐量就会线性增加。然而，当流水线的某些阶段成为瓶颈时（在图5中，我们将中间阶段作为瓶颈，其任务速率保持在恒定值50），通常情况下，流水线的整体性能会下降，即使在其他阶段的速率增加时，也几乎保持在相同的水平（因为吞吐量由执行最差的任务决定）。这表明，为了提高流水线应用的整体性能，必须保证统一的任务速率。确保任务速率一致性的一种方法是复制性能最差的任务，以便相同类型的多个任务可以分担负载。作为吞吐量吞吐量184G. Yaikhom等人理论计算机科学电子笔记190（2007）167我们在第3节中讨论过，这可以通过两种方式来实现。首先，我们使用一个交易，其中瓶颈阶段以一种方式复制，以便以循环方式处理数据。其次，我们使用一个农场，其中数据分布不是固定的，而是概率性的。在图6中，我们显示了复制的五种变体的吞吐量：（1）具有中间阶段瓶颈的Pipeline应用程序（与图6所5）;（2）中间任务作为交易复制两次的情况，（3）作为交易复制三次的情况;（4）中间任务作为场复制两次的情况，(5)三是农场。正如我们所看到的，当瓶颈阶段被复制时，流水线的性能得到了提高。我们还看到，吞吐量取决于与瓶颈阶段的速率与其他阶段的速率的偏差程度有关的重复次数;即，当复制任务的组合速率更接近于其他任务的速率时，吞吐量的增加比当统一速率高于组合速率时更急剧。这可以在饱和曲线中看到，因为我们在其他阶段中朝着更高的均匀速率前进。我们还注意到，基于场的复制的吞吐量高于交易复制的我们认为，这是对交易复制实施的严格循环策略的结果;而场复制的策略是根据给定的费率相应地确定的5结论在本文中，我们已经讨论了一种自动化的方法，从基于pepa的应用程序中生成PEPAper-center模型这种自动方法在必须根据资源的当前状态定期和动态更新模型的系统中非常重要我们已经证明了在一个practi-cal设置所产生的模型的优势，通过对比不同的任务复制方案实现的引用[1] M. Aldinucci和M.丹尼路托MECHANIC EQUATIONS会议