（通信与信息系统专业论文）网格环境中主机负载和任务执行时间预测研究.pdf

重庆邮电大学硕士论文 摘要 摘要 网格计算技术是当前国内外通信领域研究的热点之一。网格将地域上分散的计 算资源连接成为一个相互分工合作的资源集合，而网格资源自身的性能特征又总是 在不断变化，如负载、任务执行时间、网络带宽等。因此，在网格的发展过程中， 网格资源性能指标预测的重要性日益显现出来，它是实现网格任务高效调度的关键 技术之一。 但在已有的网格资源性能监测系统中，关于资源性能预测的研究仍存在着一些 不足。大部分监测系统处于被动监控的状态，更多的工作集中在实时数据采集、统 计分析以及事后决策上，对未来网格资源性能状态走向把握不够清楚，即使在少有 的具有预测功能的监测系统中，采用的数学预测模型均比较简单，各项性能指标的 预测精度有待进一步提高。 本文从网格资源性能预测的实际需要出发，同时根据网格资源特征，选取合适 的预测方法对资源性能进行了预测。首先，总体介绍了网格资源的性能预测系统架 构，总结了设计性能预测系统需要满足的特性，同时对本文重点研究的两大网格资 源性能指标，主机负载和任务执行时间进行了深入分析。 其次，我们在充分了解网格环境中主机负载统计特性的情况下，从主机负载的 自相似性和长相关性出发，采用分形插值方法预测未来主机负载；在此基础上，结 合主机负载和任务执行时间的线性关系，研究分析了一种基于主机负载的任务执行 时间预测算法。 最后，利用仿真实现了主机负载和任务执行时间预测算法，并通过计算相对误 差、平均相对误差以及覆盖率等预测评价指标对算法的预测性能进行了评估。在主 机负载预测方面，将分形插值预测算法与a r ( 1 6 ) 和负载图样图形预测法进行了预测 精度的比较与分析；在任务执行时间预测方面，对基于主机负载实现任务执行时间 预测的可靠性进行了实验论证，并给出了预沏9 精度的评价结果。 除此之外，我们在总结本文所得成果的基础上，指出了下一步工作的研究方向。 关键词：网格，主机负载，任务执行时间，性能预测 a b s t r a c t c u r r e n t l y , g r i dc o m p u t i n gt e c h n i q u e i so n eo ft h er e s e a r c hh o t s p o t si n t h e c o m m u n i c a t i o nf i e l da th o m ea n da b r o a d g r i dc o u l dc o n n e c ta l lo ft h ec o m p u t i n g r e s o u r c e st o g e t h e rt ow o r kc o l l a b o r a t i v ef r o mt h e d i s t r i b u t e de n v i r o n m e n t s ，a n dt h e p e r f o r m a n c ec h a r a c t e r i s t i c so ft h eg r i dr e s o u r c ea r ea l w a y sc h a n g e ，s u c ha sl o a d ，t h e e x e c u t i o nt i m eo ft a s k , n e t w o r kb a n d w i d t ha n ds oo n s o ，i tb e c o m e sm o r ea n dm o r e i m p o r t a n tt op r e d i c tt h ep e r f o r m a n c eo ft h e 面dr e s o u r c ei nt h ed e v e l o p m e n tp r o c e s s e s r e s o u r c ep e r f o r m a n c ep r e d i c t i o ni so n eo ft h ek e yt e c h n o l o g i e si nt h eg r i dc o m p u t i n g ，i t c o u l di m p l e m e n tt a s ks c h e d u l i n ge f f e c t i v e l y h o w e v e r , t h e r ea r es o m ed e f i c i e n c i e sa b o u tt h er e s e a r c ho nr e s o u r c ep e r f o r m a n c e p r e d i c t i o ni ng r i dr e s o u r c ep e r f o r m a n c em o n i t o r i n gs y s t e m am a j o r i t yo fm o n i t o r i n g s y s t e m sa r ei np a s s i v em o n i t o r i n gs h a p e ，f o c u s i n go ng a t h e r i n ga n da n a l y z i n gr e a l - t i m e d a t a , m a k i n gd e c i s i o na f t e rt h e e v e n tm o r ea n dm o r ei no r d e rn o tt oh o l dc l e a r l y d e v e l o p m e n td i r e c t i o no fg r i dr e s o u r c ep e r f o r m a n c e f e wm o n i t o r i n gs y s t e m sh a v et h e a b i l i t yo fp r e d i c t i n gr e s o u r c ep e r f o r m a n c e ，b u td u et ot h ef a c tt h a tm a t h e m a t i c sp r e d i c t i o n m o d e l sa d o p t e dw h i c ha r er e l a t i v e l ys i m p l e ，p r e d i c t i o np r e c i s i o no fp e r f o r m a n c ei n d e x e s w i l lb ei m p r o v e df u r t h e r i nt h i sd i s s e r t a t i o n , w ec h o o s et h ea p p r o p r i a t ep r e d i c t i o nm e t h o dt op r e d i c tt h e p e r f o r m a n c eo f t h eg r i dr e s o u r c eb a s eo nt h ep r a c t i c a lr e q u i r e m e n ta n dt h ec h a r a c t e r i s t i c s o ft h eg r i dr e s o u r c e f i r s to fa l l ，w ei n t r o d u c et h ef r a m e w o r ko ft h i sp r e d i c t i o ns y s t e ma n d s u m m a r i z et h er e q u i r e m e n to fd e s i g n i n g i na d d i t i o n , w ed e e p l ya n a l y z et h et w og r i d r e s o u r c ep e r f o r m a n c ei n d e x e s ：h o s tl o a da n dt h ee x e c u t i o nt i m eo ft a s k s e c o n d l y , a c c o r d i n g t ot h es t a t i s t i c a lc h a r a c t e r i s t i c so fh o s tl o a di nt h e 鲥d e n v i r o n m e n t , w ea d o p tf r a c t a li n t e r p o l a t i o nm e t h o dt op r e d i c tt h ef u t u r eh o s tl o a db yt h e s e l f - s i m i l a r i t ya n dl o n g r a n g ed e p e n d e n c eo fh o s tl o a d b a s e do nt h a t , w es t u d i e da n d a n a l y z e dak i n do fa l g o r i t h ma b o u tp r e d i c t i n gt h ee x e c u t i o nt i m eo ft a s kb yt h el i n e a r r e l a t i o n s h i pb e t w e e nh o s tl o a da n dt h ee x e c u t i o nt i m eo f t a s k f i n a l l y , w es i m u l a t et h ep r e d i c t i o na l g o r i t h ma b o u tt h eh o s tl o a da n dt h ee x e c u t i o n t i m eo ft a s k ，a n de v a l u a t et h ep r e d i c t i o np e r f o r m a n c eb yc a l c u l a t i n gt h ep r e d i c t i o n e v a l u a t i o ni n d e x e s ，s u c ha sr e l a t i v ee r r o r , a v e r a g er e l a t i v ee r r o ra n dc o v e r a g er a t ea n ds o o n i nt h ep a r to fh o s tl o a dp r e d i c t i o n ，w ea n a l y z ea n dc o m p a r ep r e d i c t i o np r e c i s i o no fo u r a l g o r i t h mw i t ha r ( 16 ) a n d “p a t t e m sm e t h o d ”i nt h ep a r to ft h ee x e c u t i o nt i m eo ft a s k i i 重庆邮电大学硕士论文 摘要 p r e d i c t i o n , w ev a l i d a t e dt h er e l i a b i l i t ya b o u tp r e d i c t i n gt h ee x e c u t i o nt i m eo ft a s kb a s e d o nt h eh o s tl o a d ，a n de v a l u a t ep r e d i c t i o np r e c i s i o no fi t i na d d i t i o n , w ec o n c l u d et h i sp a p e ra n dp o i n to u tt h ed i r e c t i o no u rr e s e a r c hg o e si n f u t u r e k e yw o r d s ：g d d ，h o s tl o a d ，t h ee x e c u t i o nt i m eo f t a s k ，p e r f o m a n c ep r e d i c t i o n i i i 重庆邮电大学硕士论文第一章绪论 第一章绪论 1 1 课题研究的背景和意义 计算机、网络技术等信息产业的飞速发展，极大地改变了人类的生活和思维方 式。计算机中的各种资源，如c p u 、内存、硬盘等不断的更新换代，互联网技术的 兴起和广泛的应用，有力地推动了人类科技的发展，为人类的生活和工作提供了很 大的便利，并从不同的角度解决实际处理能力与用户应用需求之间的矛盾。可是， 人们的应用需求也在同时朝着高性能、多样性、多功能方向不停发展，在这之中， 有着许许多多的大规模科学计算应用已经不仅仅是单独的一台高性能计算机就可以 满足要求的，它还同时需要多种设备( 数据采集仪器、图象处理设备、数据存储仓 库等) 、多个系统的协作，才能够顺利完成。为此人们提出网格计算( g r i d c o m p u t i n g ) 1 j 技术，试图构建一种能够联合网络中所有资源，为用户提供一种虚拟的巨型超级计 算机系统。网格技术一经提出，立即引起世界上许多国家和科研组织的广泛关注与 重视【2 】，成为当前计算机技术研究中的一个热点问题。二十世纪末，高性能计算与 当代先进的网络技术相结合，产生了网格技术，网格被称为下一代i n t e r n e t ，成为了 当前的一个研究热点。 目前网格计算经过十几年的发展，在网格的大环境下形成了一些具有针对性的 研究领域，如资源发现【3 】、资源管理【4 】、资源监测【5 】、任务调度【6 1 、安全【7 】与容错【8 】 以及网格应用研究【9 】等，这些子领域作为网格计算的关键技术也是必须解决的。而 本课题研究的主要方向就是网格资源的性能预测【1 0 】【1 1 1 【1 2 】，这个研究方向属于资源监 测的研究范畴。 在网格的发展过程中，由于网格环境自身的特征，使得网格资源性能预测的重 要性日益显现出来，主要体现在以下几个方面： 首先，网格资源的性能预测为高效的任务调度提供支持。网格为用户提供的种 种服务最终要依靠网格任务在资源集上的本地执行来实现，如何对大量的网格任务 进行调度才能既保证任务的执行性能又充分利用可用资源，这些正是网格资源性能 预测所要解决的问题。其次，网格资源的性能预测可以保证网格系统的动态负载平 衡【1 4 】。网格中存在着大量服务，这些服务运行于一个巨大的、异构的、动态的资源 集上，对网格资源的性能预测可实现对这些服务进行合理的调度，避免有些资源过 分空闲而另一些资源过分繁忙的现象出现，保持网格系统的动态负载平衡。第三， 重庆邮电大学硕士论文第一章绪论 网格资源的性能预测可以提高网格服务质量( q o s ) 【1 3 】。不同的网格服务有着不同的 资源需求，这些资源需求制约着网格服务运行性能的发挥。由于网格资源的共享性 以及动态性等特点，需要对网格资源性能做出预测，这样才能保证服务的运行性能， 提高服务质量。 1 2 网格资源性能预测现状分析 随着国内外对网格技术研究的深入开展，作为网格研究的关键技术之一的网格 资源监测技术，已引起不少组织和科研单位的高度关注，g g f ( g l o b a lg r i df o r m ) 的 g m a ( g r i dm o n i t o r i n ga r c m t e c t u i i e ) 1 1 5 j 工作组在这方面进行了开创性的工作。g m a 架 构并没有给如何构建网格监测系统提出具体的实现建议，但是它定义的体系结构和 组件间的交互方式已经被广大研究和工程人员所认可，越来越多的网格资源监测系 统【l6 】的实现都参照这一结构，并力求支持g m a 定义的所有功能。 现有的网格资源监测系统：网络气象服务( n w s ) 【1 9 】是u c s b 开发的一个监测软 件，是一个分布式系统，能够对多种网络和计算资源性能提供定期、动态的预测， 支持测量的数据有：c p u 利用率、t c p 端到端连接时间、端到端网络延迟、端到端 网络带宽等，是少有的在线对网格资源性能进行预测的系统，但是该系统采用的数 学预测模型比较简单，预测精度有待提高；监控和发现服务( m d s ) 系统【1 1 7 】是g l o b u s 项目用来支持网格计算环境下资源信息的发现、选择和优化，它的主要任务是管理 网格中的各种信息，其功能包括信息的发现、注册、查询、修改、注销等，同时提 供一套工具和应用程序接口用于发现、发布和访问计算网格中的各种资源信息； r g m a t l 8 l 是欧洲数据网格项目中开发的一个网格信息服务和监控系统，提供了一个 简单的生产者消费者模型和全局的信息视图，最大的特点是采用了传统强大、灵活 的关系模型来实现；a u t o p i l o t 2q 刃是由u i u c 开发的一个分布式性能测量和资源控制系 统，提供简化进程间数据分布与远程控制的c + + 类库，实现了可以插入应用程序或 监控程序的软件感应器和激励器，感应器和激励器通过注册至l j a u t o p i l o tm a n a g e r 目 录服务实现相互查找，以n e x u s 进行数据传送，通过v i r t u e 实现可视的交互式操作； n e f i o g g c r 2 l 】是一个分布式的应用程序、主机和网络的监测工具，应用程序方面的主 要监测范围有性能及瓶颈分析、选择硬件组件进行升级( 缓解性能瓶颈) 、应用程序 的实时分析、应用程序的性能与系统信息的关联等，而网络方面的监测主要集中在 硬件设备的性能监测。 随着种类繁多的网格应用的出现，能准确掌握未来网格资源性能的变化状态是 使网格应用服务具有实际操作意义的关键所在。当前，在众多资源性能指标研究中， 对主机负载和任务执行时间两个资源性能指标预测研究，逐渐变为网格资源性能预 重庆邮电大学硕士论文第一章绪论 测的研究重点之一。国内外一些专家已经对此进行了研究，但都还不成熟。其中具 有代表性的人物就是美国的d i n d a 2 2 】，他通过收集大量负载样本，并由此提出了基 于时间序列预测的预测理论，建立了主机资源预测系统r p s e 2 3 】，研究内容主要集中 在主机负载和任务执行时间的预测研究，并把r p s 应用于c m ur e m o s 资源管理系统 【2 4 1 和b b nq u o 分布式目标质量服务系统【2 5 】。除此之外，r i c hw o l s k i l 2 6 1 ，s u d h a r s h a n v a z h k u d a i l 2 r l ，l i n 9 3 a my a n 9 1 2 8 1 等人也取得了一定的研究成果，但没有形成完整的预 测体系。因此，本文把网格资源性能指标预测的落脚点放在研究所主机负载以及服 务完成时间的预测研究具有它的积极意义。 根据已有的现状分析，当前网格资源性能监测系统中，涉及资源性能指标预测 的研究与发展仍存在着一些不足： 第一，大部分监测系统( 例女n a u t o p i l o t 和n e t l o g g e r ) 都处于被动监控的状态， 更多的工作集中在实时数据采集、统计分析以及事后决策上，对未来的网格资源的 性能状态走向把握不够清楚。 第二，在少有的具有预测功能的监测系统中( 例如n w s ) ，采用的数学预测模 型较为简单( 如基于中值、基于均值j 线性回归模型、趋势预测法等等) ，各项性能 指标的预测精度有待进一步提高。 1 3 论文内容 在网格计算中，用户面临着网格环境的诸多不确定性，因此无法确知不同时刻 的网格资源状况，预测网格结点性能的动态变化和网格任务的执行情况是影响网格 任务高效调度是否成功的最重要因素之一。 本文的研究工作围绕着网格资源性能指标预测展开，主要进行了以下两个方面 的探讨： 1 ) 主机负载预测 根据主机负载的历史样本空间，预测其未来某个时刻的主机负载值。要准确地 预测主机负载，必须从主机负载变化的内在规律出发，而大量的研究均表明，自相 似性和长相关性是主机负载的固有特征。因此，从其固有特征出发，我们引用分形 插值方法来对主机负载进行预测。 2 ) 任务执行时间预测 任务执行时间与许多网格资源性能的基础参数( 带宽资源、存储资源等) 有密 切联系。但是，对于大多数情况下的复杂应用，需要获得这些运行参数代价是十分 巨大的，而且在实际运用中也难以操作。本文在预测任务执行时间方面，以主机负 载预测为基础，从任务执行时间和主机负载之间的线性关系出发，分析研究了网格 重庆邮电大学硕士论文 第一章绪论 环境中基于主机负载的任务执行时间预测算法。 1 4 论文组织结构 本文共分为6 章，组织结构如下： 第一章为绪论，首先介绍研究的背景、研究意义，研究现状，然后阐述了本文 进行网格资源性能预测的具体工作和内容，最后介绍本文的组织结构。 第二章介绍网格资源性能预测的基本知识以及基本预测方法。 第三章总结、概括一个广义的资源性能预测系统，对将要预测的两个资源性能 指标( 主机负载和任务执行时间) 进行深入分析。 第四章详细分析了基于分形插值的预测方法，从主机负载的自相似性和长相关 性出发，设计了一种基于分形插值的主机负载预测算法，同时将其预测精度与a r ( 1 6 ) 和负载图样图形预测法进行比较，并通过仿真验证理论分析结果。 第五章介绍了任务执行时间和主机负载的内在联系，分析研究了一种基本主机 负载的任务执行时间的预测算法，并利用仿真进行验证。 第六章对全文进行了总结，并给出了进一步研究的方向。 4 重庆邮电大学硕士论文第二章网格资源性能基本预测方法 第二章网格资源性能基本预测方法 预测方法可分为两大类：一类是定性预测，也叫直观预测；另一类是定量预测， 主要采用数学、概率论与数理统计或智能、电子学的方法对历史数据进行处理从而 进行预测。在这里我们采用定量预测方法来对网格资源性能指标进行预测。 2 1 时间序列法 时间序列分为连续时间序列和离散时间序列两种。如果时间序列能够完全准确 的预测则称之为确定的时间序列。但是大多数的时间序列是随机变化的，其未来值 只能部分地通过过去值确定，这种随机序列我们称之为不确定的时间序列。对随机 的不确定性的时间序列来说，完全准确的预测是不可能的。我们只能得到由过去的 观测值限定的具有一定概率分布的未来值四】。 时间序列的预测从数学统计的角度上来讲，就是从一个时间序列的过去的历史 观测数据值来估算整个系统的统计参数，进而推算出时间序列的将来值。而这种估 算出来的统计参数的平均值是会产生误差的。因此时间序列预测的主要任务之一是 如何对统计参数进行估算从而使预测产生的误差最少。我们下面介绍了几种不同的 时间序列预测法。 2 1 1 移动算术平均模型( m e a n ) m e a n 模型是简单的时间序列模型， 的预测值。其数学表示如下： 儿- = 告，羔， 它用历史数据的平均值作为下一个负载点 ( 2 1 ) 它的优点是计算简单，缺点是要保存的数据比较多，而且，2 的大小不易确定。 2 1 2 自回归模型( a r ) a r 模型是一种常见的分析时间序列的模型。尸阶的a r 模型可以记为a r 口) ，用 数学公式表达为： 重庆邮电大学硕士论文第二章网格资源性能基本预测方法 x f = a j x 州+ s f ， r z j = l ( 2 2 ) 其中 五) 称为唧) ，序列口= ( q ，口2 ，唧) r 称为a r ( p ) 模型的自回归系数， 6 t ) 自回归系数口= ( q ，a 2 ，唧) r 决定了a r ) 模型的性质，它可由y u l e - w a l k e r 方程 解出，即有厂= f a ，得到口- - f 。1 厂，其中y = ( 乃儿炜) r ，f 是一个矩阵： r 口吲 亿3 ， 置书置书，五一，来预测五的值。 其中置小五一：，五一p ，是在以某一频率对主机历史负载信息进行采样时所获得 五，五小五一：，墨一川对置+ ，进行预测。由此可见a r ( p ) 模型在预测时，只采样了向 2 1 3 移动平均模型( m ) m a ( q ) 模型描述的是单纯的均值移动随机过程，其数学表示如下： g m = + ( 三) t = + q + 屈乞一1 矽( o ，盯2 ) l 皇1 w n ( o ，仃2 ) 表示白噪声分布。 f l ( l ) = l + f l l l + + p q dp q 学0 ( 2 4 ) ( 2 5 ) 若采用该模型对负载序列进行预测，, 贝l j t + 1 步预测值等于其以为参数的前g 步的所有预测误差之和，而f + 2 步预测值等于其以为参数的f + 1 步预测误差与前 q - 1 步预测误差之和，以此类推。 2 1 4 自回归一移动平均模型( a r m a ) a r m a 0 ，q ) 模型描述的是混合以上两种特性的随机过程，其数学表示如下： 口( 三) 片= 1 9 + p ( l ) e ， 6 ( 2 6 ) 重庆邮电大学硕士论文第二章网格资源性能基本预测方法 只：t 9 + 圭乃m j + t + 圭屈q 一，q r v n ( o ，仃：) = l i = l 口( 三) = 1 一a l l 一一a j 口l pa o 0 | b u j = l + f l l l + + p q 蛩l b q 单0 若采用该模型对负载序列进行预测， ( 2 7 ) ( 2 8 ) ( 2 9 ) 贝l j t + l 步预测值等于其以口为参数的前p 步负载值之和加上其以为参数的前g 步的所有预测误差之和，而f + 2 步预测值等 于其以口为参数的f + 1 步预测值与前p 一1 步负载值之和再加上其以为参数的t + l 步预测误差与前口一l 步预测误差之和，以此类推。 2 1 5 自回归一差分一移动平均模型( a r o m a ) a r i m a 模型描述的是非平稳随机过程。我们可以通过差分转换( 1 一三) d ：v d ” 将它转换为平稳过程，从而可以采用a r i m a 模型。其中d 是获得静态过程的阶次， v 是差分算子，a ( l ) ( 1 - l ) d m = ( 三) 咒，其中a ( l ) = l 一口1 三一一口，口。0 ， f l ( l ) = l + f l l l + + 岛口，属0 。由上可知，非平稳序列转换为平稳序列的关键在于 确定阶数d ，确定阶数d 的方法如下： 先做一阶差分，得到v y , ，v y 2 一v y ，求出它的相关函数和偏相关函数，如果仍 然不属于a r ，m a ，a r m a 序列，则继续差分，直到某个d ，使得v d 咒，v d 儿，v d 以 属于a r ，m a ，a r m a 三种类型之一为止。 2 2 回归分析法 回归分析也称为解释性预测，它假设一个系统的输入变量和输出变量之间存在 着某种因果关系，通过研究输入变量与输出变量之间的关系，建立预测模型，明确 相互关系的密切程度，然后以输入变量为依据预测输出变量的变化。 研究两个变量之间的相关关系称为单相关，与之对应的回归预测称为一元回归 预测，研究若干个变量与另一个变量之间的相关关系称为复相关，与之对应的回归 预测称为多元回归。如果回归模型的因变量是自变量的一次函数形式，则称为线性 回归预测，否则称为非线性回归预测。对于非线性问题可以采用数学方法使之转化 为线性问题。 回归分析预测的步骤为： 1 1 分析确定自变量和因变量； 2 ) 计算各自变量与因变量之间的相关性，确定适合的自变量； 7 重庆邮电大学硕士论文第二章网格资源性能基本预测方法 3 ) 根据历史数据确定回归方程参数，并进行假设检验，检验求得的方程是否 具有实用价值和可行性： 4 ) 判断回归方程的可行以后，由自变量计算预测值和置信区间。 回归分析法的缺点是要收集较多观测值，它的预测准确度与样本含量有关，所 以付出的代价一般比较大。 2 2 1 一元线性回归 设y 为随机变量，x 为自变量，共做甩次试验，对应于五，x 2 ，吒的y 值分别为 m ，奶，咒。根据这些数据，我们要求y 与x 之间的线性回归方程： p = a + b x ( 2 1 0 ) 其中口为常数项，b 为y 对x 的回归系数。由最小二剩原理，要确定口、占的值 使得总误差： q = ( 魄一允) 2 = 【以- ( a + b x k ) 2 ( 2 1 1 ) k = lk = l 达到最小。上述q 达到最小的口和b 记为a 和b 。由微分法，可解： 塑：o 抛 箜：o o b ，占= 【a = 歹一匆 其中 i = 去喜讫 歹= 去喜 = 否( & 一习2 = k - - - i 一吉( 善1t ) 2 = 丢k - - 一厩2 t = l 几七一l 8 ( 2 1 3 ) r 2 1 4 ) ( 2 1 5 ) ( 2 1 6 ) 重庆邮电大学硕士论文第二章网格资源性能基本预测方法 = ( 矗- x ) ( y k - y ) = 童心x k y k 一去c 喜，c 善n 儿，= 砉儿一聆一x y x 和y 之间的关系用相关系数来确定，相关系数定义为： ，= 拱 其中 = ( m 一歹) 2 = 以一去( 坛) 2 - - z y ；一n y 2 ( 2 1 9 ) k = lk = lk = lk = l 可以证明，0 ，1 。r 越接近1 ，z 与y 的线性关系越好。如果，接近0 ，可以 认为x 与y 不具有线性关系。通常给出相关系数检验表，在给定显著性水平口条件 下，计算得到的，大于表中的临界值名时，才能考虑用回归直线描述x 与y 之间的 相关关系。另外，也可以用方差分析的方法来检验。 2 2 2 多元线性回归 这里我们对多元线性回归法也做一些简单介绍，尤其在预测任务执行时间时， 也有部分模型采用此法建立因变量任务执行时间与网络资源( 带宽) 、计算资源( c p u 计算能力) 、存储资源( 内存和辅存) 等自变量之间预测模型。同简单直线回归模 型一样，对获得的，z 组观察值( 玎 所) ( 而，x 2 ， ) 利用最小二剩法原则，可以建 立一个线性方程如下： 夕= a + 反而+ 6 2 而+ + 屯q 2 0 ) 那么每一个观察值点距离这条直线的误差： 岛= y s 一或= m 一( a + b l x a + + )( 2 2 1 ) 同样误差项e ，应当是随机误差，并符合平均值为零，方差等于常数的正态分布， 误差项之间彼此独立。我们用f 检验方法来检验多元回归方程的显著性。 多元回归的主要优点在于它能够通过模型来解释各变量之间的关系，它对因果 关系的处理是十分有效的。同时，它也有缺点，一是在预测因变量y 之前，必须用 时间序列分析方法对每一个自变量都要加以预测；二是计算量大，所需要的历史数 据多；三是要经常评审模型。 9 重庆邮电大学硕士论文第二章网格资源性能基本预测方法 2 3 分形拼贴预测法 分形拼贴p 川是分形理论的基本定理之一。设( x ，d ) 是一个完备度量空间，给定 三矽，切取定占0a 选取一个压缩因子o s l 2 ，用平均的观点来看，过去的增长意味着将来的一个增长 趋势，反之亦然，即过程具有持久性，并且h 越趋近1 0 ，其持久性越强， 运动轨迹越平滑。因此主机负载具有很强的自相似性。 6 ) 主机负载变化具有突变性。负载在较长一段时间( 1 5 0 s - - 4 5 0 s ) 内基本保 持稳定，而在这段时间的边界处存在突发变动。造成这种情况主要是由于 主机创造、撤销或当前进程进入一个新的执行阶段。负载的突变说明负载 预测应具有修正机制。 第6 点表明主机负载存在不稳定性，但是其变化趋势并不是毫无规律可寻，总之 在大部分情况下负载不会突然升高到一个极限或者突然降为0 。上面的第5 点与第6 点并不冲突。 从第4 、5 点得到启发，通过研究主机负载整体和部分之间的自相似性和长相关 性，为利用相似理论中的分形插值预测方法预测主机负载提供了依据。 1 9 重庆邮电大学硕士论文 第四章基于分形插值的主机负载预测算法 4 2 主机负载的分形插值预测 4 2 1 分形插值方法 我们假设：可以构造一个尺2 上的i f s ( 迭代函数体系) ，使它的吸引子恰为插 值于给定主机负载历史数据集 ，z f r 2 ：f = o ，1 ，2 ，n 的连续函数z ：k ，“卜r 图像，通过椰中的仿射变换就可以预测未来时刻的主机负载。b a m s l e y t 3 0 1 3 9 】给出 了利用插值方法构造上述迭代函数体系的过程，称为分形插值方法。 i f s ： r 2 ；，n = l ，2 ， 中每个函数吃是仿射变换，表示其第，2 个仿射变换， 构造为： q 豳= 隆捌+ 豳 并且满足如下条件： 和 吃阱豳 ( 4 1 ) ( 4 2 ) ( 4 3 ) 这表明在大区间的左端点映射到子区间的左端点，大区间的右端点映射到子区 间的右端点，即每一个变化通过式4 2 和式4 3 变换得到： 。( 4 4 ) 4 个方程有5 个参数，因此有一个自由参数。实际上，上述矩阵变化从数学意义 上解释，吃是将垂直线映射成垂直线。设三为一垂直于x 轴的线段，贝uc o ( l ) 也是 一条垂直于x 轴的线段，嚷( 三) 之长与三之长的比为l 以i ，因此称巩为变换的垂 直比例因子。由于以的特殊性，选屯为自由参数。令l 以i 1 ( 否则该臃不收敛) ， 1 ，j 。l = r_j 乇 。，l 彩 妻 重庆邮电大学硕士论文 第四章基于分形插值的主机负载预测算法 取定瓯，解方程组4 4 可得： 2 铃 铲一删名， 2 专学 z = 纽予掣 ( 4 5 ) 此时，即确定了椰中的第r 1 个变换。在求得i f s 的各参数后，就可由确定型 迭代算法或随机型迭代算法得到椰的吸引子。随着迭代次数的增加，插值获得的 曲线与原被采样曲线的拟合程度不断提高，经过多次迭代，将形成一条稳定的不变 的插值曲线。这里以虽然是个自由参数，但其对分形插值的结果影响很大。当以趋 近于0 时，分形插值退化成分段线形插值，当以趋近于l 时，分形插值曲线中不可微 的点越多。 4 2 2 主机负载预测模型 主机负载模型的一般形式为： 会：u k 瓦( z ) ( 4 6 ) 在式4 6 中，z 为负载预测值集合，z 为负载历史数据集合，q 为从历史记录 中确定的统计意义上的i f s 的第n 个仿射变换。因此，负载历史数据通过不同的仿 射变换可以综合得到未来时刻的主机负载值。 4 3 算法流程实现与分析 我们利用分形插值方法来设计的主机负载预测算法的基本原理是采用m 个不 同长度、时间间隔为a t = l s ，2 s ，3 s ，的样本，在每个样本上使用分形插值方法构造 照，根据我们需要预测的未来时间刻度，选i r i f s 中合适的仿射变换来计算该时 刻的主机负载。 为了准确地反映主机负载分形预测模型的预测能力，我们在一条负载图样上运 行了大量的测试用例，具体算法实现步骤如下： 。 1 ) 在已有的一条主机负载图样上随机选择一个时刻t ，t 表示算法中的当前时 2 1 重庆邮电大学硕士论文 第四章基于分形插值的主机负载预测算法 刻o 2 ) 生成一个随机数召【6 0 0 ，1 8 0 0 】( 1 0 分钟至o 5 小时，以秒为单位) ，b 表示 从乞开始向后，在负载图样上所抽样的个数，抽样所得的历史负载值为： 气一b ，气一州，气一。，这个样本属于负载历史空间。 3 ) 生成一个随机数， 6 0 0 ，1 8 0 0 】( 1 0 分钟n 0 5 小时，以秒为单位) ，f 表示 从f c 开始向前( 包括f c ) ，在负载图样上所抽样的个数，抽样所得的负载值为： 气，气小，气+ 川，这个样本属于负载预测空间。负载图样随机抽样示意图如图4 2 所 示。 负载图样 抽样值 采样频率为l h z 随机时刻t c 的负载 t c + f - 1 时间轴 图4 2 负载图样随机抽样示意图 4 ) 设厶为历史| 负载值与当前时刻气的时间间隔气一l 的乙为1 s ，气2 的乙为 2 s ，依次类推) ，以z r 虬+ 。为起点，乙为时间间隔，依次向后取个样本点，针对 不同的乙连续取m 个样本，然后利用章节4 2 1 中的分形插值方法构造不同的 i f s 。 在构造吗，时，必须确定自由参数a ( a o 个样本点的均方差( s d ) ) 小等 ( 4 7 ) f t ，s e 重庆邮电大学硕士论文 第四章基于分形插值的主机负载预测算法 d 。= 1 一面m e a n n ( 4 8 ) m a x 表示该样本中的最大样本值。s d 代表整个样本点的分散程度，越大表示 被抽样的负载图样曲线走势有巨变，因此要选取较大的以来确定i f s ，从而保证预 测精度。 在得到一个腓。： r 2 ；c o 小c o 彬，缈印 后，因为我们的预测属于点预测方式， 如果要预测下一时刻的主机负载，需要选择相应的瓦，根据式4 2 可得： 国。= 国。2 ( 4 9 ) 以此类推。此处的魄为式4 6 中具有统计意义的鹏的第n 个仿射变换。 5 ) 利用式4 6 ，得到下一时刻主机负载的预测值： 皇：m 瓯石。( 乙) ( 4 1 0 ) n = l 根据实际情况，我们还引入了权重因子最来调节历史负载对未来负载的影响程 度。因此，乙越小，相应的最的权重就越大，同时必须满足关系： j n = l 最一 1r 1 1 ， 1 0 叉叉。 1 6 、f o ri = 0t of 一1 把气，气小，气+ ，载入主机负载历史空间中，作为预测其它未来时刻主机 负载的输入值。 f o rt = lt o3 0 2 0 ，是给定的历史负载值气一日，气一m ，z t + ，通过上述方法对毛+ r 的预测 值。同时计算预测误差为： e ：“= k m r 一露f i ( 4 1 2 ) 7 ) 对于不同的未来时间间隔丁= 1 ，2 ，3 0s ，计算乙m r 和2 0 ，之间的相对误差 来表征其预测能力。 8 ) 输出预测误差分析。主机负载预测算法流程图如图4 3 所示。 2 3 重庆邮电大学硕士论文第四章基于分形插值的主机负载预测算法 图4 3 主机负载预测算法实现流程图 重庆邮电大学硕士论文第四章基于分形插值的主机负载预测算法 4 4 仿真及分析 4 4 1 实验环境及参数设置 我们使用d i n d a 采集的主机负载图样作为仿真数据n t 4 l 】来检验本文的负载预测 算法的预测精度。该主机负载图样是u n i x 系统内核以一定的频率采样该就绪队列的 长度，用前几次的采样结果按照一定的算法平均得到主机的平均负载。本文利用的 主机负载数据源为每隔1 s 采样过去5 s 通过指数平均得到的负载数据，此离散样本图 样能完全反映主机负载的变化情况。 在这里我们具体使用4 组主机负载图样，分别为：交互机a x p 0 、批处理机a x p 7 、 服务器s a h a r a 以及台式机t h e m i s 。这4 组负载图样各有特点，可以全面地考察分形插 值预测算法的性能，我们将其还原到坐标轴上进行分析。 a x p 0 是一台重负载主机，抽样次数为1 2 9 6 0 0 0 ，均值为1 ，均方差0 5 4 ，最小值 为0 ，最大值为8 3 9 ，如图4 4 所示。 口 口 j 铝 口 i t i m e ( s ) 0 0 0 图4 4a x p 0 主机负载图样 a x p 7 是一台轻负载主机，但是负载图样具有突变性，抽样次数为11 2 3 2 0 0 ，均值 为0 1 1 ，均方差0 1 4 ，最小值为0 ，最大值为1 6 3 ，如图4 5 所示。 1 8 1 6 1 4 1 2 焉1 0 o _ j 铝0 8 o 工 0 6 o 4 0 2 o o 02 0 0 0 0 04 0 0 0 0 0 8 0 0 0 0 08 0 0 0 0 01 0 0 0 0 0 0 1 2 0 0 0 0 0 t i m e ( s ) 图4 5a x p 7 主机负载图样 s 吐a m 是一台负载适度的服务器，同时也该服务器配置有非常大的内存，抽样 次数为3 4 5 6 0 0 ，均值为o 2 2 ，均方差0 3 3 ，最小值为0 ，最大值为1 9 2 ，如图4 6 所示。 2 o 1 5 口 口 j 苗1 0 o 工 0 5 o 0 06 0 0 0 0 10 0 0 0 015 0 0 0 0 2 0 0 0 0 02 5 0 0 0 03 0 0 0 0 03 5 0 0 0 0 t i m e ( s ) 图4 6s a h a r a 主机负载图样 t h e m i s 是一台负载适度的台式机，抽样次数为3 4 5 6 0 0 ，均值为o 4 9 ，均方差0 5 ， 重庆邮电大学硕士论文第四章基于分形插值的主机负载预测算法 最小值为0 ，最大值为2 7 5 ，如图4 7 所示。 口 o j 一 价 。 工 3 o 2 5 2 0 1 0 0 5 0 o 0 5 0 0 10 0 0 15 0 0 0 0 2 0 0 0 0 02 5 0 0 3 0 0 0 0 03 5 0 0 0 0 t i m e ( s ) 图4 7t h e m i s 主机负载图样 现在再来确定分形插值预测算法的各个环