水平分解的单类闭合分叉汇集排队网络性能的分析方法

摘要

本发明公开了水平分解的单类闭合分叉-汇集排队网络性能分析方法，通过水平分解方法，将一个单类闭合分叉-汇集排队网络模型分解成若干个乘积类型的排队网络模型，从而可以使用平均值分析方法快速地求解该模型，而且对于包含嵌套分叉-汇集操作的排队网络也只需要进行一次水平分解，不需要像层次分解方法那样进行递归的分解，大大降低了计算复杂度，提高了计算机的计算、分析单类闭合分叉-汇集排队网络模型的效率，提升了计算性能。

说明书

技术领域

本发明涉及排队网络性能分析领域，主要是一种基于水平分解的单类闭合分叉-汇集排队网络性能分析方法。

背景技术

排队网络（Queueing Network）模型是一种经典的系统性能分析方法，它用一个服务中心（Service Center）来描述一个软硬件资源， 整个系统可以看成是有若干个服务中心按照一定关系组合而成的网络。服务中心可分为队列型和延时型两种类型：队列型服务中心由一个队列和若干个服务器组成，服务器用于执行操作，队列则用于缓存等待服务的请求；而延时型服务中心主要用于模拟延时操作。队列网络模型根据负载类型不同，又可分为开放式模型（Open Model）和闭合式模型（Closed Model）。

排队网络模型在复杂度和精确度之间具有较好的均衡效果，被广泛应用于各种计算机软硬件系统的性能分析中。然而，随着并行计算、分布式计算等技术的出现，简单的排队网络模型无法适用于此类大规模复杂系统的性能分析。一种包含分叉-汇集（Fork-Join）操作的排队网络模型被广泛地应用于并行计算、分布式计算和流程管理等系统的性能分析。分叉-汇集操作可以用于描述并行处理场景：一个请求（或称为任务）到达分叉操作节点后将被分解成若干子任务，这些子任务可以由不同的服务中心并行处理；而汇集操作节点必须等待相关的子任务都执行完成后，将它们的结果聚合成一个新的请求发送给下一个服务中心。分叉-汇集操作使该类排队网络模型无法使用乘积形式（Product-Form）的方式计算，从而增加了该类模型分析的难度，特别是对于闭合类型的网络。

目前，关于分叉-汇集排队网络模型的精确算法只有基于马尔可夫链（Markov Chains）的分析方法，但是该类算法只适用于规模较小的模型。因此，对于大规模的分叉-汇集排队网络模型通常采用近似的分析方法。而大多数方法都是利用一种层次分解（Hierarchical Decomposition）的方法。该方法首先将大型的排队网络模型分解成多层次的子网络，每个子网络在其上层网络中用一个负载相关的服务中心表示，然后自底向上分别求解每个子网络模型。如果一个包含N个请求的单类闭合分叉-汇集排队网络模型通过层次分解方法分成L层，每层包含1个子网络，则对于每个子网络需要求解N次（请求数从1到N的情况），而整个网络至少需要求解N^L个闭合排队网络模型。因此，对于大规模的分叉-汇集排队网络模型使用基于层次分解的分析方法具有较高的计算复杂度。

发明内容

本发明针对现有技术所存在的缺陷，提出了一种基于水平分解的单类闭合分叉-汇集排队网络模型性能分析方法。

为了解决上述技术问题，本发明的技术方案包括以下步骤：

1）对仅有一类请求且包含分叉-汇集操作的系统中，根据系统的负载规模设定请求数N，并获取对应计算资源的历史记录中的服务时间D_i；对所述系统在计算机中建立单类闭合排队网络模型，其中每个计算资源对应一个服务中心，将请求数N和每个服务中心的服务时间D_i作为该模型的两个输入参数；

2）计算机对所述建立的模型使用水平分解，将分叉-汇集之间并行处理的                                                子任务分解得到1个主干和个分支乘积类型的排队网络；

3）根据所述的系统请求数N和每个服务中心的服务时间D_i，使用平均值分析方法计算闭合的主干的系统吞吐量，以及每个服务中心的响应时间；

4）  将所述主干的系统吞吐量作为其它分支的请求到达率，使用平均值分析方法计算其它个分支中每个服务中心的响应时间；

5）根据步骤3）和步骤4）计算得的每个服务中心的响应时间，根据重新计算主干及各个分支中的每个服务中心响应时间；

6）判断步骤4）的最长响应时间，如果在步骤3）中选择的主干具有最长的响应时间，则说明之前的选择是正确的，流程结束；否则，将响应时间最长的分支选择为主干，并重新分解原有的模型，然后返回步骤3）重新执行，直到选择的主干具有最长的响应时间；

所述主干为闭合排队网络模型；所述分支为开放排队网络模型。

作为可选方案，所述步骤2）中，主干的确定方法是为每个服务中心的平均队列长度提供一个合理的初始值，从而估算出每个子任务的响应时间，并将响应时间最长的子任务执行路径设定为主干；所述N为闭合排队网络模型中请求的总数，K为闭合排队网络模型中服务中心的总数 。

作为可选方案，所述闭合排队网络模型中使用估算每个服务中心的平均队列长度时，每个服务中心的响应时间可以通过以下公式计算：

所述是请求到达时刻的队列长度，是队列平均长度。

作为可选方案，所述主干和所述各个分支的响应时间可以通过以下公式计算得到：

所述是分支B_i包含的服务中心数。

作为可选方案，所述服务中心的其它参数是基于所述系统吞吐量和所述每个服务中心的响应时间计算出来的。

本发明有益的效果在于：

通过水平分解方法，可以将一个单类闭合分叉-汇集排队网络模型分解成若干个乘积类型的排队网络模型，从而可以使用平均值分析方法快速地求解该模型。对于每个分解后的模型最多只需求解N_B次，而如果使用传统的层次分解方法，每个分解后的子系统都需要求解N次。在真实系统中，N的值通常远远大于N_B；对于包含嵌套分叉-汇集操作的排队网络也只需要进行一次水平分解，而不需要像层次分解方法那样进行递归的分解，大大降低了计算复杂度，提高了计算机的计算、分析单类闭合分叉-汇集排队网络模型的效率，提升了计算性能。

附图说明

图1水平分解示意图；

图2基于水平分解的单类闭合分叉-汇集排队网络模型求解流程。

具体实施方式

下面结合附图和实施例对本发明作进一步介绍：

本发明首先对仅有一类请求且包含分叉-汇集操作的系统建立单类闭合排队网络模型，其中每个计算资源对应一个服务中心。分析该模型所需的两个输入参数分别为请求数N和每个服务中心的服务时间D_i。请求数N可以根据系统负载规模设定，服务中心的服务时间D_i可以由对应计算资源的历史记录中获得。接着计算机使用水平分解的方法将一个单类闭合分叉-汇集排队网络模型分解成若干乘积类型的排队网络模型。如图1所示，一个包含2对分叉-汇集操作（F₁-J₁和F₂-J₂）的单类闭合排队网络模型使用水平分解后得到的一个闭合模型1和两个开放模型2和3。其中，闭合模型1是由操作F₁-J₁的主干（包含任务S2，S3，S4和S6）和F₁-J₁以外的服务中心（包含S1和S9）组成；开放模型2是由F₂-J₂的分支（S5）组成；开放模型3是由操作F₁-J₁的分支（包含任务S7和S8）组成。主干是并行处理子任务中具有最长响应时间的分支。因此，对于分叉-汇集排队网络模型，其整体性能是由主干决定的。由于任务S5的请求到达率等操作F₂的吞吐量，操作S7的请求到达率等于任务F₁的吞吐量，所以可以使用闭合模型1的吞吐量作为开放模型2和3的输入即和。

然而，在模型求解之前每个服务中心的响应时间是未知的，也无法确定哪个分支是主干。本发明使用以下步骤估算每个分支的响应时间，从而找到可能的主干：

1）对于每个分支，将其与分叉-汇集操作以外的服务中心组成一个闭合的排队网络模型。设N为原模型中请求的总数，K为该闭合排队网络模型的服务中心总数，D_i为每个服务中心的服务时间。

2）对于上述闭合模型，使用估算每个服务中心的平均队列长度，则每个服务中心的响应时间可以计算如下：

其中，是请求到达时刻的队列长度，是队列平均长度。

3）根据上述结果，可以计算每个分支的响应时间：

其中，是分支B_i包含的服务中心数。

4）从所有分支中选出具有最长响应时间的作为主干。

图2描述了基于水平分解的单类闭合分叉-汇集排队网络模型求解流程：

1. 对单类闭合分叉-汇集排队网络模型使用水平分解，从而得到1个闭合和个开放的乘积类型的排队网络模型。

2. 根据已知的系统请求数N和每个服务中心的服务时间D_i，使用MVA方法计算闭合模型的系统吞吐量，以及每个服务中心的响应时间。

3. 将闭合模型的系统吞吐量作为其它开放模型的请求到达率，从而可以使用MVA方法计算其它个开放模型中每个服务中心的响应时间。

4. 根据计算所得的每个服务中心的响应时间，根据现有技术重新计算每个分支（包括主干）的响应时间。

5.如果在第一步中选择的主干具有最长的响应时间，则说明之前的选择是正确的，求解流程结束。

6. 否则，将响应时间最长的分支选择为主干，并重新分解原有的模型，然后返回第二步重新执行，直到选择的主干具有最长的响应时间。

通过上述步骤，可以近似计算出单类闭合分叉-汇集排队网络模型的系统吞吐量和每个服务中心的响应时间，服务中心的其它参数（如利用率、队列长度等）都可以基于以上2个值计算出来。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员，在不脱离本发明构思的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围内。