使用随机自动机网络的主从并行程序性能评估模型

理论计算机科学电子笔记128（2005）101-121www.elsevier.com/locate/entcs性能模型主从并行程序1卢卡斯·巴尔多2莱昂纳多·布伦纳3路易斯·古斯塔沃·费尔南德斯4保罗·费尔南德斯5阿方索销售6如果我不是我的话，Pontif′ciaUniversidadeCato′licadoRioGrandedoSulPortoAlegre，Brazil摘要本文提出了使用随机自动机网络（SAN）开发的模型，可以有效地应用于一个大类的并行实现：主/从（M/S）程序。我们专注于我们的技术在主节点和从节点之间的通信的描述考虑两个标准的行为：同步和异步交互。虽然SAN模型可能有助于实现的预分析，但本文的主要贡献是 指出所提出的建模技术的优点和问题关键词：性能评估，分析模型，随机自动机网络，并行编程，传播算法。1介绍性能评估是，或者至少应该是，并行程序开发人员的主要关注点。不幸的是，大多数这类问题在开发过程中出现得不够早。执行跟踪技术和可视化工具[23，13，22]关于性能的更重要的信息1这项工作是与惠普巴西研发部合作开发的2电子邮件：lbaldo@inf.pucrs.br3电子邮件：lbrenner@inf.pucrs.br4电子邮件：gustavo@inf.pucrs.br5电子邮件：paulof@inf.pucrs.br（通讯作者）6电子邮件：asales@inf.pucrs.br1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.01.015102L. Baldo等人理论计算机科学电子笔记128（2005）101一个现有的并行实现，但是如果你有一个执行的痕迹，那么大部分的实现已经完成了。基准[2，10]提供了关于执行平台的通用但有用的信息然而，在没有一个正式的方法来模拟设计的并行程序的相互作用，它可以是很难正确地估计其实现的行为开始之前的编程阶段。为了解决这个问题，我们提出了使用建模形式来描述和分析设计的实现及其平台。我们相信，这样的建模可以提供很好的估计的实现行为在相当早期的并行程序开发阶段。这样做的主要困难是开发性能模型的复杂性（通常很大）。事实上，开发一个精确的模型需要对并行程序和性能问题一样多的理解。因此，这将是非常有趣的，以减轻并行程序员从这个per-task分析技能的负担。虽然远离性能模型的自动生成器[21]，但我们提出了一些建模技术，可以有效地应用于一大类并行实现：主/从（m/s）程序，例如。，任务解决方案包[1]。我们专注于我们的技术在主节点和从节点之间的通信考虑两个标准的行为：同步和异步交互的描述。我们在这方面的经验表明，适当的建模的通信是关键问题，开发模型，这样的并行程序。本文的贡献是基于一个经典的并行应用程序的真实案例研究，希望以同样的方式描述任何M/S并行程序的实现。下一节非正式地介绍了随机自动机网络（SAN）的形式主义[17]，并提供了最少的细节。第三节简要介绍了m/s程序的概念和主从节点之间可能的交互方式，并给出了基于SAN的一般m/s模型。为了说明我们的方法，第4节提出了一个实际的案例：并行版本的Prop- agation算法的实现选择。第5节显示了SAN模型，描述了传播算法的可能实现。第6节给出了所提出的模型的性能指标的分析。最后，在结论中总结了本文的工作，并对今后的工作提出了建议.2随机自动机网络SAN形式主义由Plateau [16]提出，其基本思想是通过具有独立子系统的子系统集合来表示整个系统。L. Baldo等人理论计算机科学电子笔记128（2005）101103行为（局部转换）和偶尔的相互依赖性（功能速率和同步事件）。Plateau提出的框架定义了一种描述连续和离散时间马尔可夫模型的模块化方法[17]。然而，只有连续时间的SAN将在本文中考虑，虽然离散时间的SAN也可以采用不失任何一般性。SAN形式主义将一个完整的系统描述为相互交互的子系统的集合。每个子系统被描述为随机自动机，即。一种自动机，其中的转换标记有概率和定时信息。因此，可以建立与SAN相关的连续时间随机过程，即，SAN形式主义与马尔可夫链（MC）形式主义具有完全相同的应用范围[20，6]。SAN模型的状态称为全局状态，它是由所有自动机的局部状态的有两种类型的事件可以更改模型的全局状态：本地事件和同步事件。本地事件将SAN全局状态从一个全局状态更改为另一个仅由一个本地状态区分的全局状态。另一方面，同步事件可以同时改变多于一个本地状态，即，两个或多个自动机可以同时改变它们的局部状态。换句话说，同步事件的发生迫使所有相关的实际上，本地事件可以被看作是同步事件的一个特殊情况，只涉及一个自动机。每个事件都由一个标识符和一个发生率表示，它描述了给定事件发生的频率。每个转换都可以由于任何数量的事件的发生而一般情况下，可能的不同事件之间的非决定性是根据马尔可夫行为，即处理。，任何事件都可能发生，其发生率定义了每个事件发生的频率。然而，从一个给定的本地状态，如果一个给定的事件的发生可能导致一个以上的状态，那么一个额外的路由概率必须被告知。如果给定局部状态的事件只能触发一个转换，则自动机之间相互作用的另一种可能性是使用函数速率。任何事件的发生率都可以用一个常数值（正实数）或其他自动机状态的函数来表示。与同步事件相反，功能速率是自动机之间的单向交互，因为它只影响它出现的自动机。图1展示了一个SAN模型，它有两个自动机、四个本地事件、一个同步事件和一个功能速率。在本文的上下文中，我们将使用罗马字母来识别事件和函数的名称，使用希腊字母来描述速率和概率的常数值。104L. Baldo等人理论计算机科学电子笔记128（2005）101e10（1第一A（1）e2A类（2）0（2）e4e2（π1）e2（π2）e5第二条第（二）款e3- 是的ΣΣ-是的ΣΣf=stA（2）==0（2）λ+stA（2）==2（2）γFig. 1. SAN模型在图1的模型中，事件的速率e1不是恒定速率，而是由PEPS工具[4]采用的SAN符号7描述的功能速率f功能率f定义为：⎧如果自动机A（2）处于状态0（2），则为⎨如果自动机A（2）处于状态1（2），则f=0如果自动机A（2）在状态2（2）中，如果自动机A（2）处于状态0（2），则从0（1）到1（1）的状态转换的触发以速率λ发生，或者如果自动机A（2）处于状态2（2），则以速率γ发生。 如果自动机A（2）处于状态1（2），则不发生从0（1）到1（1）的状态转换（速率等于0）。函数表达式的使用不限于事件速率。事实上，路由概率也可以表示为函数。函数的使用是SAN形式主义的一个强大的基础，因为它允许以非常紧凑的格式描述非常复杂的行为。随着SAN模型数值解的发展，处理功能速率的计算成本显著降低，例如：，广义张量积的算法[4]。图2显示了图2中SAN1.一、重要的是要注意，在这个MC模型中，6个状态中只有5个是可达的。为了表达SAN模型的可达全局状态，有必要定义一个（可达性）函数。对于图中的模型1号可达性函数必须排除全局状态1（1） 1（2），因此：- 是的可达性=！Σ第一个A（1）==1（1）&&.ΣΣ标准A（2）== 1（2）7函数的解释可以被看作是对非类型化编程语言的表达式的求值，例如：、C语言编写。每次比较的值为1（true）和0（false）。类型事件发生率位置1fsyne2µ位置3σ位置4δ位置5τ⎪L. Baldo等人理论计算机科学电子笔记128（2005）101105λ0（1）0（2）1（1）0（2）δµπ2τδµπ1τσ σ0（1） 2（2）0（1） 1（2）1（1） 2（2）1（1） 1（2）γ图二、图中SAN模型的等效马尔可夫链13并行程序的主/从模式在m/s范例中，一个主节点生成并分配工作，通常称为任务，到N个从节点。每个从节点接收任务，计算它们，并将结果发送回去。因此，主节点负责接收和分析从节点的计算结果（求和）。这种范例通常适用于共享内存或消息传递平台，因为交互自然是双向的。m/s范式的主要问题是主服务器可能成为瓶颈。 如果任务太小，或者有太多的从机连接到一个主机，就会发生这种情况。每个任务中工作量的选择称为粒度。并行编程中的主要性能问题之一是在许多小任务（细粒度）或少数大任务（粗粒度）之间进行选择。根据主机如何分配任务并从从机收集结果，我们提出了两种不同类型的M/S实现：同步或异步交互的程序8。当任务需要分阶段执行时，程序被称为具有同步交互，即，、每一阶段的任务必须完成后才能分配下一阶段的任务。相反，当主设备每次从设备完成计算时都会分配新任务时，主设备和从设备之间的交互被称为异步考虑到从属请求的非确定性分布（任务具有未知的计算成本），这样的交互可以减少等待时间。在这种情况下，主节点通常实现一个等待缓冲器，以便处理来自从节点的结果的同时到达3.1M/S并行程序的通用模型无论交互类型如何，m/s并行程序的SAN通用模型都由每个节点的自动机组成。主自动机（见图3）由三种状态组成：8.读者必须注意，我们并不是在讨论程序原语层面的同步性106L. Baldo等人理论计算机科学电子笔记128（2005）101下来我上SPR做RpiTX• ITx：表示任务到从节点的初始传输;• Tx：表示新任务到从节点的传输;以及• Rx：表示从从节点接收计算结果。硕士r1.. RN图三. 主自动机每个自动机Slave（i）（参见图4），其中i = 1.. N也由三个状态组成：• I：表示没有任务要处理的从节点（空闲）;• Pr：表示从节点正在处理任务;• Tx：表示从节点将结果发送回主节点。奴隶（一）下来WNi（1 −π）ri（π）见图4。 从属自动机在由这些1 +N自动机组成的通用模型中有六个不同的事件：up，s，pi，ri，c和down。程序执行从事件up开始。事件s对应于向从机发送任务。事件pi表示第i个从机停止处理任务。在此停止之后，事件ri指示将结果从第i个从设备发送回主设备。如果第i个从机需要继续任务执行，则事件pi和ri（π）将相继发生，直到任务执行结束。另一方面，当没有更多的点要被评估时，从设备通过事件ri（1-π）的发生，并返回空闲状态。 数值π的值必须根据并行程序员已知的信息来估计。在从从节点之一接收到结果之后，主节点执行由事件c表示的求和。 当所有需要工作的时候TXCsRX起来下来ITXL. Baldo等人理论计算机科学电子笔记128（2005）101107事件down表示并行应用程序结束并返回到初始状态。请注意，即使从机处于Pr或Tx状态，也可能发生事件down。根据每个建模应用程序的具体特征，必须向该通用模型添加一些额外的功能。例如，在异步模型中，事件s必须被分割成N个事件s i（i = 1.. N），每一个表示向第i个从机发送任务。同步模型只有一个事件，因为所有的从机都同时接收任务。此外，从从设备到主设备的结果传递通常使用缓冲器来执行在这种情况下，可以包括一个额外的自动机，并且事件ri和c将不会直接使主设备与从设备同步，而是分别使从设备与缓冲器以及缓冲器与主设备同步（参见第5.1节中的异步模型）。每个事件发生率的数值将取决于各种特征，例如：问题大小、粒度、节点处理能力、通信速度等。这种将真实情况信息映射到数值的过程称为参数化，是模型开发中的关键点。不幸的是，这样的映射似乎非常依赖于每个实现的特殊性。在第5节中，我们提供了参数化的两个实际案例，一个考虑同步实现，另一个考虑同一应用程序的类似异步版本。4案例研究：传播算法基于图像的插值是一种在两个原始视点之间创建平滑、逼真的虚拟视图的方法。该方法的主要计算成本阶段之一是与原始场景之间的密集匹配映射的构建相关的计算成本阶段[5]。在本节中，我们将简要讨论有关称为传播[14]的区域生长算法的实现的一些相关细节。最后，本文还简要介绍了该算法的并行实现。4.1基本传播算法传播算法基于用于图像分割的经典区域生长方法[15]，该方法使用像素均匀性。然而，代替使用像素均匀性属性，采用基于匹配相关性得分的类似度量[14]。这种传播策略也是合理的，因为种子对由感兴趣的点组成，这些点是纹理的局部最大值。因此，这些匹配的邻居也是强纹理的，这允许良好的传播，即使它们不是局部最大值。108L. Baldo等人理论计算机科学电子笔记128（2005）101算法1. Propagation算法1：当Sed/=0时，2：从种子中提取最佳匹配（a，A）3：本地←4：{存储在本地新候选匹配项中}5： 对于所有（x，y）∈ N（a，A），6：if（（x，x），（x，y）∈M ap）andd（s（x）>t，s（y）>t）andd（ZNCC（c，d）>0. （5）n7：本地←（x，y）8：如果结束9：结束10：{存储在种子和映射良好的候选匹配中}11： 当Local/=do时12：从本地提取最佳匹配（x，y）13：if（x，y），（x，y）∈/Mapthenn14：映射←（x，y），种子←（x，y）15：如果结束16：结束时第17章：结束兴趣点[12，19]自然是很好的种子点候选者，因为它们代表图像中具有最高纹理的点。在每个分离的图像中检测这些点。接下来，使用ZNCC（零均值归一化互相关）测量来匹配它们。在该阶段结束时，一组种子对准备用于引导区域生长型算法，该算法将种子点附近的匹配从纹理最多的像素传播到纹理较少的像素。像素a和A的邻域N5（a，A）被定义为以这两个点为中心的5x5窗口内的所有像素（每个图像一个窗口）。对于第一图像中的每个相邻像素，匹配候选者的列表是构建了该列表由第二图像中的相应邻域中的3x3窗口的所有像素组成。像素匹配（a，A）的邻域N（a，A）的完整定义由下式给出：N（a，A）={（b，B），b ∈ N5（a），B ∈ N5（A），（B-A）-（b-a）∈ {− 1，0，1}2}.算法的输入是包含当前种子对的集合Seed。这个集合由堆数据结构实现，以便更快地选择最佳对。输出是一个单射置换映射Map，其中包含通过传播算法找到的所有良好匹配设s（x）为像素x的亮度粗糙度的估计，其用于停止传播到不光滑的纹理区域。并且令t为表示在纹理化区域上接受的较低亮度阈值简单地说，所有初始种子对都是并发传播的起点在每个步骤中，从种子对的当前集合中移除具有最佳ZNCC分数的匹配（a，A）。然后，该算法在其匹配邻域中寻找新的匹配。当它找到一个匹配时，它被添加到当前的种子对集合中，同时也被添加到正在构建的已接受匹配集合L. Baldo等人理论计算机科学电子笔记128（2005）101109顺序传播程序执行的示例可以在图5上观察到。两个图像中的方形区域示出了从种子匹配获得的匹配区域的扩展。图五. 使用House对的4.2并行实现为了在实际情况中使用这种新算法，开发了本节讨论的传播算法的并行实现。因此，有必要在不使用面向非常昂贵（但不经常使用）机器的并行编程模型的情况下实现更好的性能。该算法的有用的并行版本应该分布在由快速网络连接的多个处理器上运行。因此，自然的选择是具有消息传递编程模型的集群。如前一节所述，传播算法通过比较源图像中的相邻像素来推进。从一些种子对，它可以在两个图像上形成大的匹配区域。事实上，单个种子对可以开始在图像上的大区域中生长的传播。这种进化的自由度保证了算法在匹配表面方面取得良好的结果。该算法的另一个特点是基于全局最佳优先策略来选择下一个种子对，该种子对将开始新的传播，这也直接影响最终匹配质量。这两个特点是很难处理，如果一个人想提出一个并行分布式版本的算法，而不会失去质量在最终匹配。最佳优先策略实现基于种子对集合的全局知识，这不适用于非共享内存上下文。此外，整个图像的进化自由这可能会造成一种情况，即几个处理器同时在相同的区域上传播，从而产生计算冗余（图11）。6）。此外，不可能提前知道种子对将生成多少新匹配。因此，从并行的角度来看，传播算法是一个不规则和动态的问题，表现出不可预测的110L. Baldo等人理论计算机科学电子笔记128（2005）10135切片选择堆切片1切片112切片2堆切片2全局种子对堆切片34图像表面Redundant种子点匹配曲面见图6。 冗余问题负载波动因此，它需要使用一些负载平衡策略，以实现更高效的并行解决方案。[9]中提出的解决方案基于主从模式。一个处理器（主处理器）将负责分配工作并集中最终结果。其他（从机）将运行传播算法，每个算法使用种子对的子集，并知道图像上的一对对应切片（目标切片的坐标）。主节点考虑种子对在切片上的位置将种子对分布在节点上（参见图7）。这个过程用几个局部最优策略代替全局最优策略.每个本地种子对子集仍然被实现为堆，该堆由ZNCC得分对排序。这种策略最大限度地减少了在最后一场比赛中质量下降的问题堆切片3见图7。 种子对在切片一旦解决了全局最优优先策略的问题，仍然存在图像上进化的算法限制问题。如前所述，每个节点可以仅在其相关联的切片的表面上传播，以避免计算冗余。但是，禁止相关切片的进化会产生两种损失。首先，有些匹配没有完成，因为它们只是在一个切片的边界上，而它的一个点被放在外面。其次，一个切片中的某些区域可能无法到达L. Baldo等人理论计算机科学电子笔记128（2005）101111通过由位于其表面内部的种子对开始的任何传播，但是相反，它们可以通过在相邻切片处开始的传播到达这种限制部分地通过称为可伸缩切片的技术来解决[9]。该技术允许传播算法以受控方式扩展通过其相邻切片的表面。如图8所示，每个处理器在其自己的关联切片上工作，但它也知道其相邻切片，并且它具有在它们上传播的许可。但是，让Propagation算法自由地计算其邻居整个曲面并不有趣。这可能会导致计算太多的重复匹配。为了避免这种情况，每个处理器都有权计算其相邻表面的百分之一以上。此百分比称为重叠，与切片数有关。大量的切片意味着更薄的切片。在这种情况下，允许处理器在其相邻表面的大百分比上前进是可接受的。另一方面，少量的切片意味着较大的切片。这里，算法不能在邻居的表面上传播太多图像表面切片1切片2切片3切片4切片5}50%延伸}Slice 6种子点匹配曲面见图8。 弹性切片法在传播算法的并行化中要处理的最后一个问题是负载平衡。如果源映像被划分为比可用节点数更多的切片，则采用的负载均衡策略(i) 主设备基于种子对在切片上的位置将种子对的集合划分为子集(ii) 每个从设备接收一个切片及其相关联的子集;(iii) 每个从设备计算其自己的种子对子集;(iv) 当没有更多的种子对要计算时，从设备向主设备发送信号;(v) 如果剩余可用切片，则主设备将其发送给可用的从设备;112L. Baldo等人理论计算机科学电子笔记128（2005）101r1.. RNC下来K−1下来r1.. RNC.下来Cr1.. RN0下来syn起来λsyn down µ synCσsyns iδsynr iαlocπγ实际上，主服务器有一个切片队列，按切片在图像上的位置进行组织。要选择哪个切片将被发送到可用的从机，主机只需获取此队列的第一个切片。实际上，主设备向从设备发送新的种子对子集（切片的坐标）。最后，需要强调的是，master必须接收所有由slave生成的匹配，并且必须过滤不可避免的重复匹配。为了将这些最终匹配发送到主设备，每个从设备都有一个通信缓冲器，随着传播算法的进展，该缓冲器逐渐填充。一个缓冲器，当它是满的，被发送到主和从立即返回到其执行。所有从机都执行相同的过程，以强制主机具有接收队列的方式。当从设备到达其种子对子集的末尾时，它向主设备发送不完整的缓冲器。当master收到一个不完整的buberger时，它知道sender已经完成了它的工作，并向它发送一个新的slice（种子对子集）（如果有可用的子集）。5建模示例本节提出了两种不同的模型，以两种完全不同的方法来并行化前面介绍的传播算法。我们对顺序传播算法的分析表明，使用主设备和从设备之间的异步交互，即，主设备不分阶段地分发和收集来自从设备的结果。在本节中，我们使用SAN对同步和异步m/s实现进行建模，以确认（在第6节中）我们对传播算法的实现前分析是否正确。5.1异步实现模型图 9给出了SAN异步模型，该模型包含一个主自动机、一个缓冲器自动机和N个从（i）（i = 1.. N）自动机。硕士布·布海尔奴隶（1）奴隶（一）从机（N）TXK下来我下来我下来我类型事件发生率c（g下来下来r 1（1−π） .. .下来下来r i（1−π） .. .下来向下rN（1−π）r1（π）ri（π）rN（π）g1=（nb[Slave（1）.. Slave（N）]I== 0）g2 =（nb[Slave（1）..从（N）]I> 0）见图9。 SAN异步模型的传播算法c（g2）s 1..SN第一章RX起来下来ITX上S1PRp1TX向上PRpNTX上SIPRpiTXL. Baldo等人理论计算机科学电子笔记128（2005）101113主自动机负责将切片（任务）分配给从机，并分析由它们评估的最终匹配（结果）。该自动机具有三个状态（ITx、Tx和Rx），其分别意味着：所有种子对到从设备的初始传输;新切片到从设备的传输;以及由从设备评估的最终匹配的接收。同步事件向上发送初始切片到所有从机，开始新的程序执行。另一方面，向下同步事件结束应用程序的一次执行。该事件的发生表明所有自动机必须将其实际状态改变为初始状态。同步事件si表示向第i个从设备发送新切片。AutomatonMaster通过同步事件c消耗由从机评估的最终匹配，消耗来自存储库的结果（AutomatonBuyer）。由于该SAN模型具有异步特性，因此从节点生成的结果存储在该存储库中。因此，主节点不需要同步接收从节点发送的结果。当同步事件c发生时，主节点可以具有两个同步器。在第一种情况下，由函数概率9g1表示，master停留在接收和分析结果上。在第二种情况下，函数概率g2指示从节点处于空闲状态，因此主节点必须向其发送新切片。最后，自动机Slave（i）表示第i个从机，它有三种状态：I（空闲）、Pr（处理）和Tx（传输）。Slave（i）通过本地事件p i的发生完成最终匹配。 同步事件r i表示Buffer从Slave（i）接收最终匹配。从设备发送一个包（最终匹配），并以概率π返回到Pr状态，此时仍有存在待评估的点另一方面，当没有更多的点需要评估时，从设备以1-π的概率发送一个包，并返回到空闲状态。π的数值和所有事件的速率必须是根据并行程序员已知的信息估计。在下一节中，我们将介绍如何将这些信息映射到模型参数中。5.1.1试验参数本节说明如何为事件发生率和概率分配数值。一些参数由开发人员给出（模型的输入值），而其他参数则使用这些输入值进行评估我们将描述这些值的选择，考虑到图中图像的处理5和9使用由PEPS工具[ 4 ]采用的SAN符号，命令nb[Slave（1）. Slave（N）]计算Slave（i）（i=1. N）处于空闲（idle）状态。114L. Baldo等人理论计算机科学电子笔记128（2005）101具有Pentium III 1.0 GHz和Myrinet网络的同构COW（工作站集群）的特性。显然，其他环境或其他工作负载将具有不同的输入参数。创建了一些变量来帮助参数定义。设BL为从缓冲器长度，其固定为64 KB大小的相应值（5. 500分）。 一个从节点在其邻域（PS）上的切片扩展百分比也固定为0。5. 另一个固定值是输入图像上的点数（NP）：230。000点10.显然，预测的质量在很大程度上取决于这种输入参数最后，切片数（NS）描述了问题将被拆分的任务数量（粒度）。从这些输入值中，我们可以计算出要评估的实际点数（RNP）（NP加冗余）：RNP=Σ ΣNP2（1 +PS）+（NS−2）（1 + 2PS） ∗NS（一）因此，很容易估计平均购买者人数（NB），每个切片：NB=、、、RNPB.L.（二）事件ri（自动机Slave（i））的概率π由下式给出：NB−1π=NB（三）事件ri、pi、si和c的发生率通过在目标体系结构上通过一些示例程序执行的一些统计测量获得同步事件的速率si（δ）和ri（α）分别对应于向从机发送新任务（TT）和发回包含最终匹配的结果包（TP），由下式给出：δ=1TT1而α=TP（四）以类似的方式，事件率pi（γ）和c（σ）分别对应于计算最终匹配（CM）和评估结果（ER）所花费的时间这些事件发生率定义如下：γ=1CM所以σ=1儿（五）[10]这个点的数目取自图1所示的真实图像五、L. Baldo等人理论计算机科学电子笔记128（2005）101115下来我上SPR做Rp1TX下来我上SPR做RpNTX下来我上SPR做RpiTX同步事件下降（µ）的时间不显著，因此采用任意高速率（µ= 1000）。最后，同步事件up与将任务发送到从机所花费的时间相关联，类似于事件si。因此，其速率（λ）可以通过下式获得：λ=1TTN ，其中N=从机数量（6）5.2同步实现模型图10示出了用于传播算法的并行实现的SANSAN同步模型与SAN异步版本非常相似。然而，没有必要考虑仓库缓冲器（自动缓冲器），因为主节点强制所有从节点在开始新的任务分配之前完成任务硕士奴隶（1）下来奴隶（一）下来从机（N）下来r1.. RNWN1（1−π）. . .WNi（1−π）. . .WNN（1−π）r1（π）ri（π）rN（π）f c =（nb[Slave（1）..从机（N）]I == N）<$σ见图10。SAN同步模型的传播算法由于没有缓冲器来存储从结果，这是异步模型的特征因此，事件r1.. r N（自动机主）描述了这种新的行为。此外，同步模型使每个阶段中的所有任务在分配下一阶段任务之前完成该行为由本地事件c指示，其具有功能速率（fc），该功能速率（f c）指示仅当所有从机处于空闲状态时才必须开始新的任务分配。同步事件描述了一个新的任务分配，即：一个新阶段的开始5.2.1试验参数从异步模型到同步模型没有任何变化的所有事件都保持其速率（up、down、s和pi）。对于其他人来说，已经做了最小的改变。事件c现在是本地事件，并且它具有功能速率（图10中指示的函数fc），表示等待新阶段任务的同步分配。TXCsRX起来下来ITX类型事件发生率syn起来同步停止洛克同步信号合成ri禄比λµfcδαγ116L. Baldo等人理论计算机科学电子笔记128（2005）101事件s1..仅为一个同步事件% s替换了% s %N。由于事件s与新任务的广播有关，并且由于广播的时间与单播相似，因此其速率被保留。由于主节点集中接收所有包结果，因此两个或多个从节点可以同时将其结果发送到主节点。因此，奴隶的发送时间急剧下降。因此，事件速率r1. r N（α）现在定义为：α=1TP P.N.（七）6性能指标为了验证使用SAN选择和建模的实施策略，一些模型被制作成改变一些参数，例如。、自动机缓冲器大小、切片（任务）数量和从机数量。 利用这些模型的结果，可以进行三种分析：同步与异步;小块与大块;细颗粒与粗颗粒。尽管毫无疑问哪种方法（同步或异步）更适合，但这两种模型都得到了解决，并比较了它们的理论结果最后，分析了自动售货机的规模和粒度6.1同步与异步图图11给出了同步和异步模型之间的比较，观察从机处于Tx状态的概率。首先对同步模型进行了分析，发现随着从机数量的增加，从机发送（或尝试发送）的概率也随之增加。该分析表明，从节点停留更多的时间发送，这是一个相干的结果，而主节点集中所有的接收。异步模型中的行为多达五个从机，增加从机数量不会导致Tx概率增加。这表明了异步实现的优势，因为从机可以有效地并行工作更多的时间。我们认为，这是由于结果包传输中的损失较小。这种分析可以通过查看从站处于Pr状态的概率来确认。如图12（b）所示，在异步实现中，Pr此外，性能增益再次保持增加到5个从站。这个分析并没有表明我们有一个更差的执行时间与超过五个奴隶，但在这一点上的速度开始下降。L. Baldo等人理论计算机科学电子笔记128（2005）101117粗细粒粗细粒从机处于Tx状态的概率从机处于Pr状态的概率0.4同步模型0.4异步模型0.35 0.350.3 0.30.25 0.250.2 0.20.15 0.150.11 2 3 4 5 6 78从节点数0.11 2 3 4 5 6 7 89从节点数奴隶数量（一）粗粒细粒0.1967 0.1604 0.1417 0.1395 0.1725 0.23000.1769 0.1499 0.1355 0.1336 0.1651 0.2253（b）第（1）款见图11。 从机处于Tx状态的概率0.7同步模型0.85异步模型0.650.60.550.50.80.750.70.45 0.650.40.350.30.250.60.550.50.21 2 3 4 5 6 78从节点数0.451 2 3 4 5 6 7 89从节点数数量的奴隶234567粗粮0.58400.45940.37900.33220.29290.2609细晶粒0.56430.43980.36200.31280.27310.2503数量的奴隶234567粗粮0.77800.80530.81260.80930.76920.7052细晶粒0.78980.80540.80490.79580.74920.6938(a)（b）第（1）款见图12。 从站处于Pr状态的概率基于SAN模型的性能评估表明，传播算法的异步实现效果更好。因此，接下来的实验将只考虑异步实现。6.2小型缓冲器与大型缓冲器对于异步模型，一个重要的参数是自动机排队器（主节点等待队列）的大小。图13示出了具有细晶粒和粗晶粒的异步模型的曲线。在这两种情况下，小缓冲器（少于10个位置）显示从机在Tx状态中保持太多时间另一方面，无限期地增加缓冲器的大小不会导致更好的性能。最佳缓冲器大小直接取决于所使用的从服务器数量。一个20大小的缓冲器似乎使用2个、3个和4个从站就足够了。然而，使用更多的从机，可能需要更大的缓冲器，粗细粒粗细粒从机处于Tx状态的概率从机处于Pr状态的概率数量的奴隶234567粗粮0.1746 0.2042 0.2225 0.2416 0.2533 0.2609细晶粒0.1687 0.1954 0.2125 0.2275 0.23620.2503118L. Baldo等人理论计算机科学电子笔记128（2005）1012 奴隶3 奴隶4 奴隶5 奴隶6 奴隶7 奴隶从机处于Tx状态的概率0.55粗粒度异步实现0.55细粒度异步实现0.50.450.50.450.4 0.40.35 0.350.3 0.30.25 0.250.2 0.20.15 0.150.10 5 10 15 20 25 30 3540缓冲区大小0.10 5 10 15 20 25 30 3540缓冲区大小布氏尺寸2从3奴隶4奴隶5奴隶6奴隶7奴隶10.36960.37290.39400.42640.46430.502550.29350.24430.24040.27990.34230.4061100.27630.21900.19560.22660.29630.3680200.24770.19530.16680.17650.23800.3103400.20990.16960.14920.14340.17610.2341布氏尺寸2从3奴隶4奴隶5奴隶6奴隶7奴隶10.36300.36520.38460.41760.45420.495450.27600.22800.22370.26720.33080.3999100.24930.19690.17540.21160.28300.3703200.21290.17080.14780.16260.22490.3017400.17690.14990.13550.13360.16510.2253(a)（b）第（1）款图十三. 异步模式例如，一个40号的大喇叭似乎最适合7个奴隶。因此，在接下来的实验中，我们将考虑一个40大小的缓冲器。从图13中可以看出，对于1大小的缓冲器呈现的概率几乎与同步模型相同。这是一个连贯的结果，因为同步模型可以近似为异步模型与1大小的缓冲器。6.3细颗粒与粗颗粒在并行应用中，粒度是最重要的特征之一。在我们的研究中，粒度表示的切片数（NS），其中输入图像被分割。我们使用两种不同的颗粒，通过每个节点允许的切片数量来定义：粗颗粒（每个节点2个切片）和细颗粒（每个节点3个切片）。查看图11（b）和12（b），不可能指出哪个粒度更好。使用细粒度，从站花费更少的时间计算（Pr状态）和更少的时间传输（Tx状态）。另一方面，使用粗晶粒时，情况正好相反。实际上，确定最佳粒度的主要方面与自动化Master有关。对于第4.2节中描述的传播算法的并行实现，很明显，如果主设备花费太多时间传输，它很快就会成为应用程序的瓶颈。基于该断言，最佳粒度将是其中主设备大部分时间保持在Rx状态的粒度。增加从节点的数量（参见图14（a）），主节点保持更多的时间接收具有粗粒度的信息这种分析可以在图中得到证实14（b）其中船长从机处于Tx状态的概率2 奴隶3 奴隶4 奴隶5 奴隶6 奴隶7 奴隶L. Baldo等人理论计算机科学电子笔记128（2005）101119粗细粒主机处于Tx状态的概率异步模型异步模型0.98 0.140.96 0.120.94 0.10.92 0.080.9 0.060.881 2 3 4 5 6 7 89从节点数0.041 2 3 4 5 6 7 89从节点数数量的奴隶234567粗粮0.90300.93200.93500.92950.91900.9074细晶粒0.92020.93480.92820.91520.89700.8940数量的奴隶234567粗粮0.08870.05950.05640.06200.07250.0843细晶粒0.07130.05660.06330.07640.09470.0978(a)（b）第（1）款见图14。 异步模型处于Tx状态。因此，从我们的异步模型，我们可以假设使用粗粒度将导致更好的并行实现的速度。7结论SAN形式主义原语极大地促进了这种并行程序的建模然而，任何其他结构化的形式主义，例如，、随机Petri网[7]、随机活动网络[18]和进程代数[11]。因此，根据程序员以前的经验，可以考虑使用另一种形式而不失一般性。例如，Balbo，Donatelli和Franceschinis使用了一种非常类似的方法，使用SPN形式主义[3]。事实上，选择SAN作为建模形式主义在某种程度上是由我们自己对以前的建模示例的经验所驱动的[8]。我们的主要观点是表明，并行程序的建模可以根据一个给定的结构化形式主义，这是随机自动机网络本文推广。使用自动机来描述每个处理节点（主节点或从节点）和缓冲器自动机（对于异步模型）或单个同步事件（对于同步模型）似乎非常直观。这种简单性是我们建模技术的更大优势。这种方法的主要缺点是留给参数化阶段的重要性，即，，到模型事件的速率的选择。模型的准确性主要依赖于用户已知特征到事件的速率数值的映射。事实上，建模技术可能只是通过提出应该告知什么事件率的问题来帮助程序员。程序员仍然肩负着考虑所有重要参数的重任。粗细粒主机处于Rx状态的概率120L. Baldo等人理论计算机科学电子笔记128（2005）101我们的技术的最大优点是为应用程序提供正式模型的正常好处。可能的瓶颈的指示可以帮助程序员在实现过程中更多地关注这些特定点。结果如前一节所示，可以清楚地指出，根据处理节点的数量，任务的数量更好。关于最佳粒度的这种信息对于调度器或处理节点提供者可能是有用的，以自动选择集群或网格中的多少节点应当被分配给给定应用。传播算法模型获得的结果尚未通过与实际实现的直接比较得到证实。然而，我们的结果符合算法程序员的期望。因此，与实际实现的比较，以及其他建模经验，是自然的未来工作追求。同样，我们可以预见到一个用户友好的工具，以促进模型的建设，很少或根本没有，性能评估技能的程序员的发展。尽管缺乏更广泛的实