基于PageRank和基准测试的异构集群节点性能评价算法研究*

2020-03-26胡亚红王一洲毛家发

计算机工程与科学 2020年3期

胡亚红,王一洲,毛家发

(1.浙江工业大学计算机科学与技术学院,浙江杭州 310023;2.中国工商银行,浙江杭州 310000)

1 引言

高效的任务调度是实现集群高性能的基础。现有的大多数研究假设集群中的计算机节点是同构的，即所有节点都具有相同的性能。基于这一假设，在进行任务调度时每个节点会被分配相同的任务量。但是在大多数情况下，集群中各节点的性能差异很大。显然给这些节点分配相同的任务量会导致任务执行时间较长、系统性能较低[1]。研究表明，集群配置应该根据集群中节点的性能进行[2]。目前关于集群节点的负载均衡和任务调度已经有了许多研究[3 - 7]。对节点性能进行精准的评价是进行各种调度的基础。

本文提出了一个新颖的基于PageRank和基准测试的节点性能评价算法。基准测试为评价具有不同架构的计算机系统的性能提供了一种有效的方法，通常一种基准测试着重于计算机某一种性能的测试。很多时候一个集群需要为不同类型的任务提供服务。例如，集群需要处理的任务可能是计算密集型、I/O密集型或者没有明显的特征的任务，仅使用一种基准测试不能全面描述节点的综合能力。本文提出的算法中，每个节点都使用多个基准测试进行评价，再使用PageRank算法处理得到的测试结果。算法基本思想是使用PageRank对这些基准测试进行排序，然后找到每个基准测试在计算节点性能时的权值。该算法从不同的角度考虑影响节点性能的因素，因此可以在较短时间内为集群中的节点提供综合性能指标。

本文的组织结构如下：第2节介绍了与节点性能评价相关的研究工作；第3节详细介绍了基于PageRank和基准测试的节点性能评价算法；第4节给出了1个算法应用的实例；第5节则对全文进行了总结。

2 相关研究工作

大多数文献都使用CPU主频、内存大小、磁盘容量、I/O性能或这些因素的组合来表示计算机的性能。文献[8]设计了1个函数来计算节点性能，函数的输入是从CPU、内存、I/O和网络设备获取的数据。文献[9]使用了静态性能和动态性能来描述节点的性能。文献[10]则是通过节点运行指定程序的时间来计算其性能。文献[11]为合理地进行数据块的分配，使用CPU主频、内存大小和I/O性能等对节点性能进行评价。

基准测试是1组定义好的用以测量计算机性能的程序集合[12,13]，常用的有LINPACK[14]、高性能共轭梯度基准测试HPCG (the High Performance Conjugate Gradients)[15]、NASA 并行基准NPB (NASA Parallel Benchmark)[16]、IDC 平衡评价指标、高性能计算基准测试HPCC (High Performance Computing Challenge)[17]和IOzone等。不同的基准测试从不同的角度对计算机节点进行评价。例如，LINPACK主要评价节点CPU的性能，HPCG 对系统的内存和网络延迟要求较高，IOzone则是1个文件系统的基准测试。IOzone被设计用于分析系统的I/O性能，它对各种文件操作进行测量[18]。IDC平衡评价指标可以测量CPU、内存性能和系统的扩展性。可以看出，使用多个基准测试进行节点评价，可以得到更全面、更合理的节点评价结果。

PageRank是衡量网页重要性的一种算法，Google 的搜索引擎使用它来对网页的搜索结果进行排序[19]。PageRank的基本假设是网站越重要，链接到它的网站会越多，因此PageRank通过计算网站的入链数量和质量来评价其重要性。除了对网页进行排名，PageRank 在其它领域也有很多应用。文献[20,21]应用PageRank寻找有向加权复杂网络中的重要节点。文献[22]提出了一种基于PageRank的关键词提取方法，该方法考虑了词频分享权值和人类语言习惯特性。文献[23] 构建了1个表征微博用户交互行为的模型，并利用PageRank计算用户行为的权值。文献[24]中,PageRank 被用于评价不同书籍的影响。文献[25] 采用基于PageRank的快速筛选方法来识别容易出故障的线路，以防止电网级联停电。PageRank也被用于通过引用网络来衡量学术机构的学术声誉[26]。

调研发现，目前还没有结合基准测试和PageRank算法来评估节点性能的研究。

3 算法描述

PageRank的假设是有着更多入链的网页更重要。类似地，本文所提出的算法的假设是，越多的基准测试对1个节点给出相似的评价结果，那么评价结果越可靠。

为方便读者阅读，表1列出了本文所使用的符号。

Table 1 Symbols used in the paper表1 本文所使用的符号

3.1 性能向量的定义

假设选取M个基准测试进行集群节点的性能评价，集群中节点的个数为N。使用基准测试对节点进行评价后，评价的结果构成节点的性能向量。

令:

其中,i=1,2,…,M，vik(k=1,2,…,N) 表示使用基准测试i对节点k的评价。Bi_o即集群中节点在基准测试i下的性能向量。

节点在不同基准测试下得到的性能向量值的数量级会有很大的差异，需要进行性能向量的预处理。算法1给出了性能向量归一化的步骤。

算法1性能向量归一化

步骤1输入:Bi_o。

步骤2获取Bi_o中的最大元素和最小元素

maxBi=max{vi1,vi2,…,viN}

minBi=min{vi1,vi2,…,viN}

步骤3对每1个vik使用式(1) 计算其归一化数值vik-less:

(1)

其中,k=1,2,…,N。

步骤4输出:归一化性能向量:

3.2 图模型的建立

为了使用PageRank 计算节点的性能，需要建立1个图的模型，图中的节点是各归一化的性能向量，节点之间有1条边表示这2个节点需要进行比较，所以建立的图是1个完全图。边的权值是此边所关联的2个顶点的相似度，相似度使用欧氏距离计算。2个归一化性能向量Bi和Bj的相似度类似于经典PageRank中页面间链接的相关性。

(2)

因为共有M个不同的基准测试，所以归一化性能向量也有M个，即B1,B2,…,BM。性能距离矩阵D定义如下：

(3)

其中,dij是归一化性能向量Bi和Bj的相似度。

显然，dij越大表示基准测试i和j对节点的评价结果差异越大。在经典PageRank算法中，概率转移矩阵中元素表示的是所有入链的加权得分，其值越大表示网页越重要。为使D的含义与经典PageRank 算法一致，使用式(4)对其进行处理，得到矩阵U。可以看出，U中元素越大，表示不同的基准测试得到的评价结果越相近。

U=(uij)M×M

(4)

类似于经典PageRank算法，在矩阵U的基础上定义概率转移矩阵W：

WT=(wij)M×M

(5)

3.3 基准测试排名的计算

矩阵A采用经典PageRank算法中的定义，如式 (6) 所示:

(6)

其中,q是阻尼系数,eeT是M×M的全1矩阵。

基准测试排名矩阵R可以用式 (7) 算出:

R=lims→∞AsX

(7)

其中,M×1向量X表示每个基准测试的初始排名。

算法2给出了R的计算方法。

算法2基准测试排名计算

步骤1输入:归一化性能向量Bi(i=1,…,M) 和阈值δ。

步骤3使用式 (3) 计算D。

步骤4使用式 (4) 计算U。

步骤5使用式 (5) 计算W。

步骤6使用式 (6) 计算A。

步骤7R=AX。

步骤8计算欧氏距离|R-X|。

步骤9如果|R-X|≤δ,返回R的值，算法结束。

步骤10X=R。

步骤11转至步骤7。

步骤12输出:基准测试排名向量R。

3.4 节点性能计算

利用基准测试排名向量R和每个基准测试i的性能向量Bi，使用算法3就可以得到集群中每1个节点的综合性能评分。

算法3节点综合性能评分计算

步骤2使用式 (8) 计算每1个基准测试i的权值：

(8)

步骤3使用式 (9) 计算综合性能向量:

(9)

其中，k=1,2,…,N。

步骤4输出:节点综合性能向量CB。

3.5 算法复杂度分析

假设有M个基准测试对N个节点进行性能评价，则算法1的复杂度为(MN);由于需要计算DM×M,算法2的复杂度为O(M2N)；算法3的复杂度为O(MN)。因此本文算法的复杂度为O(M2N)。通常M的数值不会很大，因此本文算法的复杂度很低。

4 算法实例

本节通过1个实例对算法进行解释。实例中使用 LINPACK、IOzone 和NPB对4个节点进行性能评价。LINPACK主要考察节点的浮点运算能力，因此适合于CPU性能评价。IOzone则适合评价系统的I/O性能。评价结果如表2所示。

Table 2 Performance evaluation results表2 性能评价结果

从表2中可以得到各个原始的性能向量。

进行归一化计算后，得到的性能向量为：

两两比较基准测试得到的评价结果，可得:

进一步计算WT为：

根据WT得到概率转移矩阵W：

使用式 (6) 计算矩阵A，其中阻尼系数q取值为0.85,阈值δ取值为0.000 1,与大多数文献中使用的一致。

假设所有基准测试的初始排名均为1，即:

仅执行了10步，算法2就得到了最终的基准测试排名向量R:

通过R很容易计算得到每1个基准测试的权值:

类似地可以得到RB2=0.21，RB3=0.39。

根据上面的计算结果，可以得到每1个节点的综合性能。

CB=0.40×BLinpack+0.21×Biozone+

向量CB给出了各节点综合性能的比值，此例中节点1，2，3，4的性能比为0.61∶0.51∶0.54∶0.18，或者表示为1∶0.84∶0.89∶0.30。在进行任务分配或数据部署时，可以使用这个比例进行分配，从而最小化任务执行时间。

一般情况下初始化向量X取全1向量,当处理不同类型任务时，可以调整X的值以反映不同基准测试的重要程度。例如，如果集群需要处理一批计算密集型任务，在进行节点性能评价时，可以调高X中LINPACK 对应的数值；若处理I/O密集型的任务，可以调整 IOzone 对应的数值。可以看出，本文提出的算法不但能够对节点性能进行有效的评价，还可以在评价时考虑任务的特点。