探索基于PageRank的计算机性能评价方法
摘要：
现有选择性计算机性能评价方法主要使用基准程序评价方法，基准程序中各子程序的输出往往因为单位不同而无法进行进一步数据处理，同时基准程序评价方法广泛采用的权重和评分方法缺乏理论依据。针对该问题，提出基于佩奇排名(PageRank)的计算机性能评价方法，采用比较数据序列间相似性的方法产生邻接矩阵从而为各项评估功能计算PageRank得分。实验结果表明，该方法能客观反映目标计算机系统的性能。
关健词：佩奇排名；基准程序；性能评价
1 概述
计算机性能评价对计算机系统的设计和选择，以及现有系统的分析都是至关重要的。历史上，最初只有计算机硬件的性能被评价，后来随着编程系统成为计算机集成系统的一部分，软件和硬件一起作为计算机系统评价的对象。性能评价一般都是出于特殊的目的并且评价过程必须客观。
性能评价的目的一般有3个：选择性评价，性能映射以及性能监测。选择性评价中一种最常见的情况是评估者希望通过性能评价结果决定他们所要选择的产品。性能映射则面向设计一种新的软件或硬件产品，目的在于通过性能评价对还不存在的产品的性能做出预测。性能监测提供了现有系统的实际性能评测数据。这些数据将被用来预测在系统某一部分的软件或硬件配置改变后，系统性能可能出现的问题。
主要的系统评价方法包括指令混合、基准程序和仿真等。
不同的评价方法对于各种评价目的有着不同的适用性。基准程序是一种执行严格定义的操作的计算机程序，这些操作称为工作量，输出的结果称为度量值，度量值衡量了被测试计算机的性能表现。采用基准程序评价方法时，计算机的表现通常有速度和吞吐量2种衡量方式。同样的基准程序在不同的计算机上运行可以达到比较各个计算机对应性能的目的。
2 基准程序评价方法及PageRank算法
2．1 基准程序评价方法
广泛使用的基准程序如SPEC(Standard PerformanceEvaluation Corporation)被设计为由一些有针对性的测试程序构成，每个子程序对应于一个测试项。
在实际的评估过程中需要在目标机器上运行基准程序，输出结果分项列出。根据文献，基准程序完全能达到选择性评价的要求。
SPEC评价数据的计算步骤如下：
(1)使用参考的机器的相应数据对目标机器所得数据进行归一化，得到各项的比率数据。
(2)对第(1)步所得的各项比率数据采用几何平均的方式进行平均。
基准程序评价方法如SPEC适用于计算机系统的两两比较，而实际的产品生产往往涉及一个系列不同型号的产品，通常新型号产品在软件硬件上都会有所提升。基准程序不能对整个系列的产品性能做出纵向评价。这对于系列产品的开发来说显然是不够的。并且通常因为基准程序评价中各项输出数据单位不同，使得进行进一步评估变得困难。
本文从产品功能验证和产品用户的角度出发，在使用基准程序的基础上，根据同一系列不同型号的产品在不同硬件配置下基准程序测试的表现，利用PageRank算法对所得数据进行分析，提出了基于PageRank的性能评价方法。把各测试项在不同配置情况下的输出序列抽象为基本的数据单元，计算出各项输出数据的相关性，这样根据PageRank算法，就能发现所有测试项的总体规律，以及哪些测试项有较多的总体特征和哪些测试项呈现出特殊的其他特征。这不仅提供了传统基准程序评价方法所没有的产品系列纵向评价能力，而且也克服了以往因各测试项数据输出单位不一致而造成的数据分析困难。
2．2 PageRank算法
PageRank是在搜索引擎技术发展的初期，网络和用户网络搜索需求高速增长，而当时缺乏有效的网络信息检索技术这一背景下被提出的 J。网络上各个网页之间的链接结构构成一个图。这个图跟学术文献之间的相互索引构成的图很类似。网页之间的链接关系好比学术文献之间的索引关系。
PageRank最终要为图中所有的节点，即网页，计算它的PageRank得分，得分较高的说明该网页的重要性较高，它将作为首选搜索结果返回给搜索弓i擎用户。直观上，一个网页被其他网页链接得越多它的重要性越大；一个网页被越重要的网页链接，它的重要性也越大。某个页面的PageRank得分，通过指向它的所有其他页面的重要性计算出来。在计算每个网页的PageRank得分时，每个链入链接对该网页重要性的贡献将用它的链出链接总数进行归一化。对于页面尸，它的PageRank得分将由下式来计算：
其中， 代表所有指向P的页面的集合；J9l代表页面Q所有链出的链接个数。这是个递归的定义，因而需要迭代计算。
如果有gt个页面 ， 的话，首先随机给每个页面一个转到 的概率。这里A是一个行随机矩阵，PageRank的迭代过程代表了一个马尔科夫链的演化过程。在矩阵A为非周期并不可消减的情况下，这一迭代过程最终会收敛。第1个条件对于网络应用以及本文的问题一般都是满足的。正是第2个收敛条件即不可消减性保证了马尔科夫链最终会有一个稳定的分布向量。矩阵A必须被调整以满足第2个条件，更多的细节见文献[3]。PageRank在搜索引擎的成功应用，以及近10年来搜索引擎对人们生活带来的变化都说明它是有效而可靠的。随着网路技术的发展，越来越多的多媒体信息被放到了网上，对这些多媒体信息的有效检索向搜索引擎提出了新的要求。近年来，研究者通过首先对多媒体信息的特征进行提取，在此基础上应用PageRank，从而有效提高了搜索引擎的多媒体信息检索能力，改善了多媒体信息检索服务的质量 。
3 基于PageRank的计算机性能评价方法及实验
随着技术的发展和用户越来越高的需求，3D图形处理能力渐渐地被加入到嵌入式计算机产品中。选择同一制造商同一系列不同型号的2款SoC产品，以它们的3D图形处理能力作为评价目标。出于对商业信息的保护，简称2款产品为SoC—A和SoC·B，其中，SoC—B为SoC—A的新一代产品。SoC—A和SoC—B的图形处理和窗口管理都采用了DirectFB图形和窗口管理系统。DirectFB是一个提供硬件图形加速、输入设备抽象及处理，同时集成窗口管理系统的轻量级函数库。它提供了一个完整的硬件抽象层，对于底层硬件不支持的图形操作都提供了对应的软件实现。DirectFB从设计之初就考虑了嵌入式系统应用，它使用尽可能少的系统资源提供尽可能多的硬件加速能力。
DirectFB自身包含基准程序DF DOK，DF DOK共有23个测试子程序，即23个测试项，分为字符显示、区域填充、图形绘制、缓冲区拷贝4个模块，对应图形处理的各典型操作。
本文的实验为测试某一特殊的系统模块，这里为3D 图形处理能力，对于DF— DOK基准程序，选择速度衡量方式。
SoC—A和SoC—B都支持3种共同的显示分辨率，不同分辨率下DF DOK的测试数据是不同的。同时DF— DOK 自身可以被设置为有无硬件加速2种运行方式。这样DF—DOK的运行总共有2x3x2=12种配置方案。DF— DOK由于各个模块测试的侧重不同因而输出的数据单位不同，见表1，直接的数据比较没有意义。现代的图形处理系统普遍采用可编程管线架构，SoC—A与SoC—B同样如此。对于正常的产品开发过程，大多数的测试项在这12种配置下的测试结果应表现出类似的数据波动特征。目标一方面在于验证产品开发中图形处理性能是否被稳步地提高，另一方面在于发现产品开发过程中图形处理不稳定的环节，以在未来的开发过程中解决问题。
各列问数据问的相关性类似于网页中页面问链接的相关性。作为嵌入式系统，图形处理系统没有自己专有的存储单元。图形处理能力的提高往往通过处理频率的提高，或图形处理系统内部处理单元的增加而实现，本文评价的2款产品即为这种情况。处理速度间理想情况应为线性关系。采用相关系数作为数据相关性的衡量，出于本文处理问题的特点及PageRank本身的特性，相关系数为负数时将被置为0。
(4)使用PageRank对DF— DOK各测试项计算出PageRank得分。得分高的测试项表明该项较多地反映了大多数测试项的数据变化特征，得分较低的项说明该项具有较多跟其他测试项不同的数据变化特征。通过对比表2中每个测试项的PageRank得分和平均的硬件加速比，可以看出PageRank得分较高的测试项正是硬件加速稳定的测试项，得分低的测试项正是那些硬件加速不成功或不稳定的测试项。这也就说明了PageRank算法应用于系列计算机系统评价的有效性，而这一功能是以往的数据分析手段所不能提供的。表2给出了详细的对应数据。
SpiderWorker根据从本节点URL队列读取到的URL下载页面，来解析页面的HTML，提取出其中包含的URL。将提取出来的URL链接按照预先定义的统一的格式补充完整。对这些URL进行过滤，然后用Rabin算法计算URL的指纹。最后，根据指纹判断应该向哪个节点的协调器报告发现的URL并发送。
在这样的结构策略下，待采集的URL都是从本节点的队列中读取的，要比中心节点的通过网络分派速度快得多。各个SpiderWorker向不同的节点报告URL，这样就能有效避免中心节点那样集中的网络传输压力。
3．4 P·Spider2．0主要类的实现
p-Spider2．0的SpiderWorker类主要算法如下：
public class SpiderWorker {
public IntWrapper startwork(){int count=0；1
1统计下载的URL数while((curUrl=dequeue(uRLQueue))!=nul1)par—do{／／各个节点并行工作page=downloadPage(formatUrl(curUr1))；foundUrls=extracturls(page)；／／发现页面中URLrabincode=rabinfunction(foundUrls)；／／用Rabin算法计算URL的指纹reportUrl(foundUrls，rabincode)；／／根据指纹向不同的协调器报告发现的URLcount++；}
return new lntWrapper(count)；／／ProActive异步调用条件，要求返回包装类型 ，))
4 实验及分析
本次实验是在相同的实验环境下，用p-Spider1．0和P—Spider2．0对lntemet各采集10 h。
实验环境如下：4台CPU为Pentium4 2．4 GHz、内存5l2MB的计算机，通过百兆局域网链接到Internet。软件环境为Linux Red Hat9、JDK1．5和ProActive3．1。实验结果如表1所示。
实验结果表明，p-Spider2．0具有更高的采集效率。这主要有以下4个方面的原因：
(1)得益于去掉了中心节点的节点对等结构，此结构没有负担过重的节点，整个系统不存在瓶颈。
(2)得益于URL检索模块采用了效率更高的RP算法，有效地节省了URL的检索时间，提高了整个系统的采集效率。
(3)得益于URL检索采用了分布式并行策略，要比中心节点单机运算速度更快。
(4)得益于相同计算机数的情况下，比原结构多了一个爬行器节点，同时也多了相应的网络接口。
5 结束语
本文介绍了对带中心节点的结构的Web Spider的2点改进：(1)为URL检索模块设计了更高效的检索算法——RP算法；(2)采用了新的节点对等结构。这样的改进不但去除了原系统中的中心节点瓶颈，提高了采集效率，而且增强了系统的可扩展性。
