预测网格计算

第13卷第9期计算机集成制造系统Vol.
13No.
92007年9月ComputerIntegratedManufacturingSystemsSep.
2007文章编号:1006-5911(2007)09-1805-06收稿日期:2006-06-09;修订日期:2007-01-15.
Received09June2006;accepted15Jan.
2007.
基金项目:国家杰出青年基金资助项目(60225009).
犉狅狌狀犱犪狋犻狅狀犻狋犲犿:ProjectsupportedbytheNationalScienceFundforDistinguishedYoungScholars,China(No.
60225009).
作者简介:栾翠菊(1974—),女,吉林梅河口人,上海海事大学信息工程学院讲师,浙江大学工程与科学计算研究中心博士,主要从事网格计算研究.
Email:cuijuluan@zju.
edu.
cn.
一种网格并行任务执行时间预测算法栾翠菊1,2,宋广华2,郑耀2,张继发2(1.
上海海事大学信息工程学院,上海200135;2.
浙江大学工程与科学计算研究中心,浙江杭州310027)摘要:广泛研究了网格环境中并行任务执行时间的预测方法,提出了一种基于案例和人工神经网络的预测算法.
该算法充分利用了历史有效信息,尤其是对于同一个任务的多次求解而获得的相似记录,通过建立任务特征模板,将历史任务,即案例进行分类,并利用指数平均值或者线性回归方法进行预测.
但是由于网格环境的复杂性,以及有限元求解器在求解问题时的复杂性,导致相似性很难定义,在无法根据模板找到相似性案例的时候,利用人工神经网络预测方法进行预测.
该算法在面向多学科应用的模拟与可视化环境中进行了实验,证明该方法具有较好的预测性能.
关键词:网格;性能预测;人工神经网络;特征模板中图分类号:TP301.
6文献标识码:A犚狌狀狋犻犿犲狆狉犲犱犻犮狋犻狅狀犪犾犵狅狉犻狋犺犿犳狅狉狆犪狉犪犾犾犲犾犼狅犫狊犻狀犵狉犻犱犔犝犃犖犆狌犻犼狌1,2,犛犗犖犌犌狌犪狀犵犺狌犪2,犣犎犈犖犌犢犪狅2,犣犎犃犖犌犑犻犳犪2(1.
SchoolofInformationEngineering,ShanghaiMaritimeUniversity,Shanghai200135,China;2.
CenterofEngineering&ScienceComputation,ZhejiangUniversity,Hangzhou310027,China)犃犫狊狋狉犪犮狋:Extensivestudiesonpredictingtheruntimeofparalleljobsinthegridenvironmentwereconducted,andaCaseandBackPropagation(BP)neuralnetworkbasedPrediction(CBPP)algorithmwasproposed.
TheCBPPalgorithmmadefulluseofvalidhistoryinformation,especiallysimilarruntimerecordsforthesamejob.
Byconstructingthetemplateofjobcharacteristics,historyjobsorcaseswereclassified,andthentheruntimewaspredictedbyexponentialaverageorlinearregressionmethod.
Becauseofthecomplexityofthegridenvironmentandtheparalleljobs,itwasdifficulttodefinethesimilarity.
Theneuralnetworkwasusedtopredicttheruntimewhentherewerenosimilarcasesinthetemplatelibrary.
ExperimentalresultsintheMultidisciplinaryApplicationSorientedSImulationandVisualizationEnvironment(MASSIVE)showedthattheCBPPalgorithmhadsatisfactorypredictionperformance.
犓犲狔狑狅狉犱狊:grid;performanceprediction;artificialneuralnetwork;characteristicstemplate0引言网格作为一种基础设施,能够大规模地共享计算资源、存储资源、数据资源、软件资源及设备资源等,为高性能科学计算提供了一种新的计算平台.
面向多学科应用的模拟与可视化环境(MultidisciplinaryApplicationSorientedSImulationandVisualizationEnvironment,MASSIVE)[1]项目正是出于计算机集成制造系统第13卷这种考虑而发起的.
MASSIVE集成了几何建模、几何网格划分、问题求解、科学可视化及后处理等模块,而这些模块通过网格平台协作来进行大规模计算问题的求解.
目前,其求解的对象主要是计算流体力学和计算固体力学领域的高性能计算问题,这些问题的都具有较高的复杂度,需要大量的计算时间并占用大量的计算资源.
在网格环境中,研究人员已经证明,任务执行时间的预测能够用于辅助任务调度,改善调度算法的性能[2],以及预测一个请求等待资源的时间[3].
本文认为任务执行时间预测还能够用于确保和改善服务质量(QualityofService,QoS),即在任务被提交的时候,系统提供预测的任务执行时间信息,使用户获知何时能够得到计算结果.
此外,可以评定系统能否满足用户提出的QoS中关于执行时间性能的要求.
在能够满足用户需求的前提下,可以不必选择最优的资源,为系统能够满足更多的服务提供了保证.
可见,性能预测在网格服务中起到非常重要的辅助作用.
本文的预测对象是MASSIVE环境中用于计算流体力学与计算固体力学模拟的并行求解器.
考虑到MASSIVE系统进行科学计算的模式,在将任务限定于单一资源执行的前提下,提出一种任务执行时间预测的算法.
实验证明,该算法具有优良的预测能力.
1问题描述MASSIVE并行求解器采用有限元方法和有限体积法对计算流体力学及计算固体力学问题进行数值仿真求解.
利用求解器求解是个非常复杂的过程,针对不同问题,求解器输入的几何网格单元形状、剖分方法和精度都会有差异,而且求解器提供了多种求解方法,每种方法涉及不同的参数.
另外,使用的编译器不同,求解器的执行速度差异也较大,求解器的编程实现进一步引入了一些不确定的复杂性.
作为基于网格的并行求解器,网格平台中计算资源及网络资源的不确定性、异构性和动态性进一步增加了该问题的复杂性.
因此,影响其执行时间的因素包括网格资源性能及求解器本身的性能,很难构建一个通用的数学模型来对求解器的执行时间进行预测.
针对并行应用程序性能的预测已有很多研究,预测方法主要有利用分析模型预测[4-5]和利用历史相似信息预测[23,67].
前一种方法是在对并行应用程序及系统分析建模的基础上预测性能,但是随着系统和并行应用程序实现复杂性的增加,这种建模非常困难,而且性能往往不理想;后一种方法是运用特征模板,对历史记录按照相似性进行分类,然后运用简单的统计或者数学方法进行预测,这种方法通过文献[2]和文献[3]验证是可行的,而且在相似性定义理想的情况下,预测误差比较小[67].
MASSIVE任务管理系统[8]的特点之一是任务定义可重用.
由于在MASSIVE环境中,为了获得一个满意的结果,同一个求解的问题往往需要计算多次,这样就产生了很多相似的任务记录,这种情况尤其适合用第二种方法来预测性能.
但是由于求解器的复杂性,导致很难定义该问题的相似性.
目前,在利用历史相似信息进行预测的诸多研究中[2,7,910],针对并行程序运行时间预测方法存在一个共同点,即都没有针对应用程序进行深入分析,只是从系统的角度来分析,这对于运行时间受输入参数及其规模影响的应用来说可能不适用.
此外,解决找不到相似历史记录的方法,有的是由用户提供预测的执行时间,有的是提供了相似性定义过于宽泛的模板.
这两种解决方法的效果都不理想,因为:①绝大多数情况下,对于没有执行过的应用,用户无法估计其执行时间,结果所提供的估计执行时间偏差过大;②如果模板定义的相似性过于宽泛,得到的预测值就会象毫无根据的预测情形一样误差很大.
以上两个问题在本章提出的任务执行时间预测方法中要合理地解决.
2网格环境中并行任务执行时间预测方法针对MASSIVE系统采用的并行求解器的算法及应用,笔者进行了细致的分析和大量的实验,最终确定影响求解器执行时间的因素主要是输入参数及系统性能.
输入参数主要包括求解方法、几何网格单元形状、几何网格单元数量、进程数量;系统性能主要是中央处理器(CentralProcessingUnit,CPU)速度、支持的编译器和工作负载.
在预测求解器执行时间的方法中采用以上几个特征.
21基于案例和人工神经网络的预测算法对于难于建立精确数学模型,具有多种不确定性和非线性的系统,应用人工神经网络[11]往往可以处理传统方法难以解决的问题.
人工神经网络技术本质上是一个信息非线性变换系统,通过对数据样6081第9期栾翠菊等:一种网格并行任务执行时间预测算法本的学习,神经网络会自动地逼近那些能最佳地逼近样本数据规律的函数,在使用时不需要建立任何数学物理模型和人工干预,就能自动地建立预测模型,并能较精确地映射任意非线性的输入输出关系.
尤其是基于误差反向传播算法的多层前馈网络(BackPropagation,BP)的神经网络,可以以任意精度逼近任意的连续函数,所以被广泛应用于非线性建模、函数逼近、模式分类等.
鉴于此,本文采用基于案例和BP神经网络的预测算法(CaseandBPneuralnetworkbasedPredictionalgorithm,CBPP)是可行的.
CBPP的策略为:使用特征模板对历史任务(即案例)进行分类.
如果当前任务所属类别的集合不空,则利用特征模板对应的预测类型计算预测时间;如果当前任务所属类别的集合为空,则利用BP神经网络来预测时间,如图1所示.
CBPP预测算法为:(1)初始化任务模板集合犜,案例集合犑,利用犜对犑进行分类得到案例分类集合犆;犃为经过训练的BP神经网络.
(2)当任务犼需要进行预测:1)利用犜对犼的特征判断其所属类别犆犼.
2)如果犆犼不空,则计算犼的预测运行时间.
3)如果犆犼为空,则取犼的相应属性值输入犃,获得犃的输出就是预测运行时间.
(3)当犼运行结束:1)如果犆犼不空,将犼加入到犆犼中.
2)如果犆犼为空,则新建只有一个元素犼的集合犆犼,并将犆犼加入到犆中.
22基于案例预测基于案例预测的方法是将历史相似性任务作为相似案例,使用其运行时间信息来预测当前任务的运行时间,而相似性是通过特征模板确定的,因此特征模板的定义是此类方法的关键问题.
2.
2.
1特征模板的定义特征模板由任务执行时所涉及到的特征来定义,它的确定通常有静态方式和动态方式两种方式.
在文献[2]和文献[3]中使用的都是固定的模板,即采用静态方式确定模板;而文献[6]和文献[7]采用了不同的算法来动态确定模板,其中文献[6]采用贪心算法和遗传算法,文献[7]采用粗糙集算法.
这些动态方法都需要一定的搜索时间,并且这种搜索是没有指导的,对于求解器这样复杂的具有特殊性质的并行应用程序,未必能够获得理想的结果,而利用对于求解器并行程序的理解及分析而获得的先验知识来引导分类是比较可靠的,因此本文仍采用静态方式确定模板.
基于前文对求解器进行分析,确定执行文件、参数文件(数据文件)、参数(主要是求解方法)、进程数量、所用的资源统一资源定位器(UniformResourceLocator,URL)作为构成模板的特征,并且确定了两个模板:(1)执行文件、参数文件、求解方法、进程数量、所用资源URL.
(2)执行文件、参数文件、求解方法、所用资源URL.
这里的执行文件指的是求解器执行文件,参数文件是用于求解的输入的几何网格数据文件.
通过对求解器和任务执行实际数据的分析表明,当上面列出的模板属性(除了进程数量)有一个不相同,任务执行时间的差别就很大,不适宜定义相似性任务,因此本文只定义了两个模板.
2.
2.
2预测类型对于上面两个模板,模板(1)定义了相似性案例,模板(2)定义的是具有不同进程数量的相似案例,因此两个模板需要采用不同的预测类型.
类似模板1的特征模板在文献[2]、文献[3]、文献[6]和文献[7]中的预测类型是平均值法,在本文中采用指数平均值方法,公式为τ狀+1=α狋狀+(1-α)τ狀.
(1)其中:狋狀是第狀个任务的实际执行时间,τ狀+1是当前任务的预测执行时间,α(0≤α≤1)可以看成是狋狀的权值.
该公式展开的形式为τ狀+1=α狋狀+(1-α)α狋狀-1+…+(1-α)犼α狋狀-犼+…+(1-α)狀+1τ0.
(2)7081计算机集成制造系统第13卷由于α和(1-α)都小于或等于1,在时间上距当前任务最近的历史任务的执行时间对当前任务的预测时间影响最大,而时间上越久远的任务对当前任务的影响就越小.
这一趋势符合系统的实际规律,对性能预测是有利的.
模板(2)的预测类型采用文献[7]中提出的线性回归法,公式为犜=犪+犫犖.
(3)其中:犜是预测的时间,犖是任务进程数量.
在进行预测的时候,利用特征模板对案例进行分类,如果当前任务所属的分类不空,则利用相应的预测类型来计算预测时间.
可以定义一个分类空间的大小,如果历史任务过多,则将旧的任务去除,以保证用于预测的都是近期执行的任务的信息.
23利用前馈神经网络预测由于上面定义的两个模板只对执行过的任务(可能进程数量不同)能够找到相似案例集合,对于没有执行过的任务就无法找到,这样利用上述方法就无法进行预测.
针对这种情况,本文利用人工神经网络进行预测.
目前用于预测功能的主要是BP神经网络模型,它具有自学习、自组织、自适应和容错性等一系列优点,因此有强大的映射功能,能够从大量的历史数据中进行训练,找出某些行为的变化规律.
2.
3.
1前馈网络结构BP神经网络具有多层网络结构,由输入层、一个或多个隐层和输出层组成,各层之间全互连,但同一层单元之间不互连.
理论已证明,三层BP网络可以逼近任何复杂的非线性函数,因此文中采用三层BP网络模型建模,即选取单隐层进行建模.
图2所示为一个三层BP神经网络结构.
2.
3.
2前馈网络输入和输出的确定根据对求解器的分析,确定影响求解器执行时间的参数主要有几何网格单元形状、几何网格单元数量、求解方法、进程数量.
此外,不同资源支持的编译器可能不同,而采用不同编译器的可执行文件的速度有时相差很大,因此将使用的编译器也作为影响性能的一个参数.
CPU速度、系统负载对于可执行文件性能的影响也是不能忽略的.
这样,确定以上7个属性作为BP神经网络的输入.
BP网络的输出即预测的时间.
因此,本文采用的BP网络具有7个输入节点,1个输出节点.
合理的隐层节点的数量由于没有可靠的算法来确定,本文通过实验的方式确定.
通过多次实验将隐层节点数量从5变化到25,然后对比误差,发现当隐层节点数量为19的时候误差最小,从而确定本文BP网络的隐层节点数量为19.
2.
3.
3前馈网络中有关算法传递函数均采用下面形式的Sigmoid(犛)型函数:犳(犪犻)=1/(1+犲-犪犻).
(4)其中,网络中间层的神经元传递函数采用犛型正切函数,输出层神经元传递函数采用犛型对数函数.
学习函数采用列文伯格马夸尔特法(LevenbergMarquardt,LM)来提高网络训练速度.
LM算法是最速下降法和牛顿法相结合的一种方法,既可提供牛顿法的速度又可保证最速下降法的收敛.
性能函数采用典型的均方误差犕犛犈,即犕犛犈=1犖∑犖犻=1(犲犻)2.
(5)为了加快网络的训练速度,需要对神经网络的输入和输出数据进行预处理.
在训练前需要对样本数据进行归一化处理,训练结束后将仿真输出再反映射到原数据范围.
3实验分析31特征模板1两种预测类型的对比实验首先针对特征模板1分别采用了指数平均值方法和平均值方法进行实验,其中指数平均值方法将式(1)中的α取值为0.
5,性能如图3所示.
从图中的曲线可见,两种方法的性能相近,但是从表1的性能分析可以看出,指数平均值方法性能要优于平均值法.
8081第9期栾翠菊等:一种网格并行任务执行时间预测算法表1模板1两种预测类型性能比较平均相对误差/%最小相对误差/%最大相对误差/%指数平均值方法0.
740.
022.
65平均值方法0.
780.
043.
4832基于案例预测与神经网络预测方法的对比实验BP神经网络的训练集和测试集的数据都来自MASSIVE的任务管理系统所记录的相关任务执行的历史信息.
利用特征模板1定义的相似案例和BP神经网络对同一组任务进行预测的相对误差对比如图4所示,其中模板1的平均相对误差为0.
58%,BP神经网络的平均相对误差为2.
21%.
可见,基于案例预测方法中的模板1针对相似性任务进行预测的性能要优于BP网络.
图5是利用特征模板2定义的具有不同进程数量的相似案例和BP神经网络对同一组任务进行预测的相对误差的对比,其中模板2的平均相对误差为25.
13%,BP神经网络的平均相对误差为8.
72%.
可见,利用模板2进行预测的性能远不如BP神经网络,并且模板2的预测结果都偏大.
基于以上两种实验的结果,本文最终取消了特征模板2,模板集中只采用模板1.
因此,用于预测MASSIVE环境中求解器执行时间的模型就确定为:由对案例定义相似性的特征模板1和经过训练的BP神经网络共同构成.
33基于案例和人工神经网络的预测算法的实验利用本文提出的CBPP预测算法得到的预测相对误差如图6所示,平均相对误差为5.
59%.
但是相对误差在最大的时候将近18%,大于平均值近13个百分点.
分析发现,导致任务预测时间相对误差过大的主要原因是,该任务输入属性中的网格单元数量的值在训练集中处于稀疏区,这是由训练集不充足所导致的.
针对这一情况,在训练集中增加了该任务相应的网格单元数量附近的数据,重新训练9081计算机集成制造系统第13卷网络,然后用于预测该任务,结果相对误差降到了7.
54%.
但是要完全避免这种情况是困难的,因为输入属性中的网格单元数量的值域跨度很大,理想的情况是从个位到数十亿个,如果要做到训练集全面、均匀分部是很难的.
解决方法是将需要使用BP网络预测的新任务的信息加入到BP网络训练集的增补集中,等到该集合达到一定规模后,重新训练BP网络,如图1所示.
但是这样多次重新训练网络导致训练集过于庞大,会增加训练时间,可以考虑去除部分训练集中处于稠密区的早期数据,同时保证训练空间数据分布的均匀.
这种改进方法有待于进一步验证.
从实验及CBPP预测算法分析可知,获得案例分类集合和确定一个任务所属类别,相对而言比较耗时,但是前者只在初始化的时候需要执行,而后者最坏的时间复杂度是犗(犿),其中犿为类别数量.
此外,训练BP神经网络相对比较耗时,但是一旦神经网络建立完成,用它做预测的运行时间非常短.
最耗费内存空间的步骤是分类集合的存储,在最坏情况下,该算法的空间复杂度为犗(狀),狀为案例的数量.
4结束语本文提出的将基于案例预测和BP神经网络预测两种方法相结合,来预测网格中任务执行时间的方法,实现简单,从实验结果来看性能较好.
比单独的基于案例进行预测和单独使用BP神经网络进行预测的效果都好.
但是也存在一些问题,如由于某些输入属性值域跨度大,BP网络的训练集不均匀,导致训练空间稀疏区域的任务预测误差大.
对于这个问题,本文提出了相应的解决方法,并将在以后的研究工作中对其展开专题研究,力争获得更加精确的预测结果.
参考文献:[1]ZHENGYao,SONGGuanghua,ZHANGJifa,etal.
Anenablingenvironmentfordistributedsimulationandvisualization[C]//Proceedingsofthe5thIEEE/ACMInternationalWorkshoponGridComputing(GRID'04).
LosAlamitos,Cal.
,USA:IEEEComputerSociety,2004:2633.
[2]GIBBONSR.
Ahistoricalapplicationprofilerforusebyparallelschedulers[C]//ProceedingsoftheJobSchedulingStrategiesforParallelProcessing.
London,UK:SpringerVerlag,1997:5877.
[3]DOWNEYAB.
Predictingqueuetimesonspacesharingparallelcomputers[C]//Proceedingsofthe11thInternationalSymposiumonParallelProcessing.
LosAlamitos,Cal.
,USA:IEEEComputerSociety,1997:209218.
[4]BADIARM,ESCALEF,GABRIELE,etal.
Performancepredictioninagridenvironment[C]//ProceedingsoftheEuropeanAcrossGridsConference.
London,UK:SpringerVerlag,2004:257264.
[5]MARING,MELLORCRUMMEYJ.
Crossarchitectureperformancepredictionsforscientificapplicationsusingparameterizedmodels[C]//ProceedingsoftheJointInternationalConferenceonMeasurementandModelingofComputerSystems.
NewYork,N.
Y.
,USA:ACMPress,2004:213.
[6]KRISHNASWAMYS,LOKESW,ZASLAVSKYAB.
Applicationruntimeestimation:aqualityofservicemetricforWebbaseddataminingservices[C]//Proceedingsofthe2002ACMSymposiumonAppliedComputing.
NewYork,N.
Y.
,USA:ACMPress,2002:11531159.
[7]SMISHW,FOSTERI,TAYLORVE.
Predictingapplicationruntimesusinghistoricalinformation[C]//ProceedingsoftheWorkshoponJobSchedulingStrategiesforParallelProcessing.
London,UK:SpringerVerlag,1998:122142.
[8]LUANCuiju,SONGGuanghua,ZHENGYao,etal.
Userorientedjobmanagementinagridenvironment[C]//Proceedingsofthe5thInternationalConferenceonComputerandInformationTechnology(CIT'05).
LosAlamitos,Cal.
,USA:IEEEComputerSociety,2005:346350.
[9]BYONGDAIL,JENNIFERMS.
Runtimepredictionofparallelapplicationsonsharedenvironments[C]//ProceedingsofIEEEInternationalConferenceonClusterComputing.
LosAlamitos,Cal.
,USA:IEEEComputerSociety,2003:487491.
[10]DOWNEYAB.
Predictingqueuetimesonspacesharingparallelcomputers[C]//Proceedingsofthe11thInternationalParallelProcessingSymposium.
LosAlamitos,Cal.
,USA:IEEEComputerSociety,1997:209218.
[11]SHIHongbao.
Theneuralnetworkanditsapplication[M].
Xi'an:Xi'anJiaotongUniversityPublishingHouse,1993:2045(inChinese).
[施鸿宝.
神经网络及其应用[M].
西安:西安交通大学出版社,1993:2045.
]0181