调度网格计算

收稿日期:2008唱09唱27;修回日期:2008唱11唱30基金项目:湖南省自然科学基金资助项目(07JJ6107);湖南省教育厅科研资助项目(07C724,07C723)作者简介:李盛欣(1981唱),男,湖南郴州人,硕士研究生,主要研究方向为网格计算、并行处理(lsxstar12@163.
com);段盛(1964唱),男,湖南隆回人,教授,主要研究方向为嵌入式系统、数据库、信息处理.
一种基于神经网络的网格实时调度算法倡李盛欣1,2,段盛1(1.
湘南学院计算机系,湖南郴州423000;2.
湖南大学计算机与通信学院,长沙410082)摘要:提出一种在指定的最终期限内,利用队列技术来模拟调度动态资源,构建一个数学神经模型调度应用的子任务,使用GridSim工具测试的调度算法,通过大约90%的模拟实验说明了模型调度任务是成功和高效的.
关键词:调度;网格计算;神经网络;并行计算中图分类号:TP301畅6文献标志码:A文章编号:1001唱3695(2009)06唱2095唱03doi:10.
3969/j.
issn.
1001唱3695.
2009.
06.
028Gridreal唱timeschedulingalgorithmbasedonneuralnetworkLISheng唱xin1,2,DUANSheng1(1.
Dept.
ofComputerScience,XiangnanUniversity,ChenzhouHunan423000,China;2.
SchoolofComputer&Communication,HunanUniversity,Changsha410082,China)Abstract:Withinspecifieddeadlines,thispapermodeledperformancedynamismofresourceswiththehelpofqueuingtech唱niques.
Employedamathematicalneuralmodelafterwards,toschedulesubtasksoftheapplication.
ImplementedtheproposedmodelonGridSimtoolkittoevaluatetheperformanceofschedulingalgorithms.
Simulationexperimentsshowthatinapproxi唱mately90%ofcases,thismodelschedulestaskssuccessfullyandefficiently.
Keywords:scheduling;gridcomputing;neuralnetworks;parallelcomputing0引言网格计算是利用硬件和软件资源来提供可靠的、可调节的和方便的接口来完成高端计算量[1].
一个共享环境的实现包括可提供持久稳固的和标准的服务配置,这些配置支持更新、资源共享和分布的群体[2].
真正的难题是在网格环境下对于同等资源的共享和动态地解决问题及多制度的虚拟组织[3].
对于大多数分布式计算平台,一个要求就是利用可用资源充分调度分布的申请以达到高的执行效率.
在传统的并行和分布式系统中,调度算法集中将这些作为一个基本问题来研究,而传统的调度模式在实践中通常提出单一的网格调度,原因如下[4]:所有的资源均按照一个单一的管理模式,提供单一系统模型,调度控制所有的资源并且资源池是不变的.
现在问题的焦点是加入的申请能够根据某一方法调度管理,但是对于能够提供每一个申请都被很好执行的固定点的性能有影响.
设计基于网格的调度算法要考虑很多独特性,包括异构自治、动态执行、资源选择、计算数据分离,重点就是实时应用的调度.
实时应用通常定义为在有限的时间内响应,大多是指队列中紧急请求.
一个紧急请求有一个最终期限通常认为是:最终期限直到服务开始和最终期限直到服务结束.
前者,消费者停留在系统中直到完成服务需求;后者,消费者可以取消服务因为超过了最终期限.
分别处理两种消费者:通过网格调度的实时应用的最终期限为直到服务结束,来自于本地调度的紧急请求的最终期限为直到服务开始.
网格中实时应用的调度作为在并行队列的一种路由实时应用,每种资源看做是一服务队列,假设实时应用对象由几个独立的任务组成,每个任务有最终期限直到服务结束,以最终期限均满足的方式来调度这些任务.
首先根据队列技术模拟动态资源的执行,接着使用神经网络的数学模型来调度应用的子任务.
当前的一些研究只是在非紧急应用中,对于紧急应用的情况很少涉及,本文提出了一种在网格调度中包括了紧急和非紧急应用的模式,其优点如下:在非专用的分布式系统中调度执行考虑了紧急任务;在时间约束和异构资源下提出了有效和快速的并行调度算法,在并行机中执行时间复杂度为O(1).
1神经网络实现网格调度神经网络应用于组合优化问题首先是由Hopfield等人[5]在1985年提出.
他们使用了事先定义的能量函数E,二次方程式如下:E=钞Ni=1钞Nj=1WijViVj+钞Ni=1ViIi(1)其中:Wij表示第i个神经元到第j个神经元间的突触连接长度,并且Wij=Wji总是满足;Ii是第i个神经元的常量斜线.
Hopfield给出了第i个神经元的动作方程式如下:dUi/dt=-Ui/τ-矪E/矪Vi(2)随着持续的非递减的输出,可微函数叫做S型函数如下:Vi=f(Ui)=1/2(tanh(λ0Ui)+1)(3)λ0是常量,叫做腰槽,决定S型函数的斜面.
1畅1神经网络数学模型虚拟的神经网络数学模型由两部分组成[6],即神经元和第26卷第6期2009年6月计算机应用研究ApplicationResearchofComputersVol.
26No.
6Jun.
2009突触连接.
输出信号传输从一个神经元到其他的神经元通过突触连接.
一个神经元输入信号的决定来自其他神经元的输入信号的线性权值和,各自的权值是突触连接的长度.
每个虚拟的神经元有输入U和输出V,第i个神经元的输出为Vi=f(Ui),f叫做神经元的输入或输出函数.
第i个神经元与被确定的其他神经元的互相联络通过一个动作方程式,第i个神经元输入状态的变化被提出通过部分与第i个神经元输出有关的计算能量函数E,E是一个N个变量函数:E(V1,V2,…,Vn).
第i个神经元的动作方程式为dUi/dt=-矪E(V1,V2,…,Vn)/矪Vi=-dE/dVi(4)通常神经网络计算的目标是优化构造的计算能量函数.
能量函数不仅决定了有多少神经元可被用于系统而且还指定了在神经元之间突触连接的长度,甚至可根据给出问题的信息来进行构造,考虑了必需的限制及价值函数.
能量函数定义为E=∫dE=-∫dUi/dtdVi(5)基于欧拉第一理论U(t+1)的值确定为U(t+1)=U(t)+ΔU(t)*Δt(6)ΔU(t)在式(4)中给出,终止条件为ΔU(t)=0(7)式(7)的条件意味着限制均满足.
1畅2用数学神经模型描述问题因为数学神经模型是一个受限制的模型,首先所有的限制必须都被指定,接着需要一个合适的模型来包含这些限制,最后提出方法包含所有的限制.
就像前面提到的,处理问题包括了对于某些资源涉及紧急任务的调度.
因此,第一个限制是对于每个任务i需要最终期限(di),第二个是候选资源的数量,调度模型考虑了N个任务被调度在一些资源和关于问题域的下述假设,对于每个资源每个任务的执行时间是预知的,出于简单考虑,一个任务不能被分派在不同的资源,也就是不允许在资源间移动任务,调度参数包括任务列表、需要的资源和时间变量如图1所示.
X轴表示任务变量为1~N(被调度的任务总数),Y轴表示资源变量为1~M(候选资源总数),Z轴表示时间变量,K表示一个具体的时间小于或等于T(所有最终期限的和).
一个变量Vijk表示为任务i在某个时间k执行在资源j上.
假设Vijk=1,表示任务i在时间k执行在资源j上;否则,Vijk=0.
每个Vijk相当于提出的神经网络模型中的神经元.
1畅2畅1映射限制到动作方程式为了执行调度的限制,两类因素使用到动作方程式,即兴奋和抑制因素.
抑制因素阻止神经元当它将要违反问题条件时,兴奋因素激励神经元当所有的需求和条件均满足时[7].
合并限制在动作方程式有以下六个抑制因素如下:a)dUijk/dt=-A倡钞Ni1=1i1≠iVijkVi1jkb)-B倡钞Mj1=1j1≠j钞Tk1=1VijkVij1k1c)-C倡L(2倡(钞Tk1=1Vijk1-Pij))d)-D倡K(2倡(钞Ni1=1Vi1jk-1))e)-E倡H(k-(di-1))f)-F倡H(Pij-di)(8)全部的抑制和兴奋因素在动作方程中的影响归结为:第一个抑制状态是一个资源j在某个时间k只能提供给任务i,如果任务i在时间k执行在资源j并且在同一时间一些其他的任务例如i1也执行在同一资源上,Vijk和Vi1jk一定等于1,所以第一个抑制因素将会拒绝,结果神经元Vijk是失败执行,任务i在时间k不能执行在资源j.
第二个抑制因素是不允许移动,任务i只能执行在资源j或资源j1在任何时间,如果任务i执行在两个资源j和j1上,那么Vijk和Vij1k1必须等于1对于时间k1,因此第二个抑制因素将会拒绝,神经元是失败执行.
第三个抑制因素或第一个兴奋因素是任务i在资源j上的时间花费应该等于Pij,Pij是任务i在资源j上的估计完成时间.
实际上,如果ΣTk1=1Vijk1也就是任务i在资源j上总共花费的时间小于Pij,那么任务i必须在资源j上执行长一点的时间,所以神经元Vijk鼓励执行;相反,如果总共时间长于Pij,神经元就失败.
相似于第一个抑制因素,第四个抑制因素是一个任务只能在某个时间执行在一个指定的资源上,但不像第一个,该抑制因素阻止神经元执行不管Vijk的状态,如果Vijk的值是0,阻止是可以的.
由于其他任务在时间k执行在资源j上,而在第一个抑制因素如果Vijk是0,没有阻止发生.
第五和六个抑制因素是不允许超过最终期限.
首先考虑第五个抑制因素,如果时间k大于任务i(di)的最终期限,那么对于调度是不合适的时间,所以这个因素被拒绝.
同样的在第六个抑制因素,如果任务i在资源j上的执行时间Pij大于任务的最终期限,资源不允许调度并且神经元Vijk对所有的时间k阻止执行.
函数L、K和H的定义如下:L(α)=1ifα>00ifα=0-1ifα00ifα≤0(9)在动作方程式中抑制系统的振动行为插入滞后因素,使汇聚时间变得相当短,针对McCulloch唱Pitts的神经模型插入了滞后因素,给出了第i个神经元的输入或输出函数如下:Vi=f(Ui)=1ifUi>UTP0ifUij0otherwise(11)1畅2畅2调度算法根据以上数学神经模型,本文设计了如下算法:begininitializeUijkrandomlywhile(asetofconflictsisnotempty)dobeginfori:=1toNdoforj:=1toMdofork:=1toTdobeginUijk=Uijk+ΔUijkVijk=f(Uijk)·6902·计算机应用研究第26卷endfori:=1toNdobeginfindthemaximumUijk.
determineasegment(j)inwhichthemaximumUijkexists.
Ifthereistieremoveitrandomly.
theoutputoftheothersegment′sneuronsissettozero.
endendend.
其中:i表示任务变量为1~N;j表示资源变量为1~M;k表示时间变量为1~T;U和V分别为神经元的输入与输出函数,Vijk相当于提出的神经网络模型中的神经元.
算法用了异步的方法来更新处理,当用N.
M.
T处理元素时,算法执行所需的时间复杂度接近O(1),因此调度的需求时间是可以忽略不计的.
2测试环境使用GridSim工具模拟所提出的方法,执行调度算法在一个单一的机器上:Pentium4处理器和512MB内存.
改变GridSim一些类来提供支持对于紧急、非紧急和本地任务,重写SpaceShared类,定义了一些新类,如ImpatientGridlet、Patient唱Gridlet和LocalGridlet分别对应于紧急、非紧急和本地任务.
在SpaceShared类检查了在任务队列中每个紧急任务的最终期限,如果已到期,那么它将从队列移除.
对于每个资源都有紧急的、非紧急的和本地任务来使用,这些任务基于它们的时间范围和每天的时间状态都有一个预先到达率.
一个资源的所有节点是同一的,除了不同资源可以有不同的节点类型,每个资源有多个任务,每个任务有多个节点,每个节点服务率μ是预先确定的,根据资源历史调度情况可以完成.
考虑了不同的测试环境,如图2所示.
每个高速主干网的带宽在图2中描述了,延迟设为10ms,每个资源的使用平台对于非紧急的、紧急的和本地任务根据泊松方法分别为λp、λi、λ1,这些任务有一个最终期限直到服务结束.
3模拟实验及分析表1描绘了预测每个资源的任务响应时间,这些值输入到调度算法;表2显示了调度结果,调度算法的执行时间可以忽略不计(少于1s).
比较了表1和2,再一次验证了调度的正确性.
表1预测任务对资源的响应时间预测响应时间/sR#0R#1R#2R#3R#4task#02766989810015324213470task#1202796087263243313311task#2101192113487132313094task#35259020167779112989task#45299022169179512990task#5110692483837142613114表2每个任务的调度和响应时间响应时间/sR#0R#1R#2R#3R#4task#03231task#12001task#23198task#34026task#44936task#513144为了显示带宽在模型中的影响,改变了对于任务3的连接带宽为0.
0001~2.
0GB.
在表3中对于资源每个任务的响应时间是减少的,在表4中对于R#3有四个任务被调度而在表2中只有两个任务被调度,说明了在网格环境中调度带宽的重要性.
表3预测任务对资源的响应时间预测响应时间/sR#0R#1R#2R#3R#4task#02766989810015281413470task#1202796087263212613311task#2101192113487118213094task#35259020167773012989task#45299022169173312990task#5110692483837127013114表4每个任务的调度和响应时间响应时间/sR#0R#1R#2R#3R#4task#04746task#12001task#21224task#311581task#41921task#55225表5中显示了全面的结果,在不同的例子中使用了不同的网络技术、资源、任务及参数,每个例子重复了10次,调度算法总是汇聚于一点,从表中可以看到大约90%的例子对于调度任务是成功的.
表5全面结果任务数申请资源数调度算法执行时间/s成功调度率/%65<110012459820737962064692302041944结束语在大多数分布式计算平台,利用可用资源对于分布应用的调度进行高性能计算是必要的.
基于队列理论提出了一种实时应用的并行调度算法,实时应用包含了几个独立的任务,并且每个任务有一个最终期限直到服务结束,对每个任务在每个资源上响应时间预测的执行使用了资源的动态运用模型.
在这个模型中,考虑了带宽、延迟和通信背景的影响.
本文提出的方法主要集中在最佳的解决方法与被给的最终期限,调度能够执行在并行机构,算法执行的时间复杂度为O(1),模拟实验证明了提及的模型特别是对于大资源服务率的任务预测响应时间是正确和可行的.
在这个工作中,假设非紧急的、紧急的和本地任务的到达率也就是节点的服务率对于每个资源是预先确定的,而在网格调度中是很难预测的,特别是对于新资源,下一个目标是证明假设任务的泊松到达,考虑新增的资源和资源失败的问题.
参考文献:[1]FOSTERI,KESSELMANC.
Thegrid,blueprintforanewcomputinginfrastructure[M].
SanFrancisco:MorganKaufmannPublishers,2004.
(下转第2103页)·7902·第6期李盛欣,等:一种基于神经网络的网格实时调度算法!
*+,)-.
/0)-1&"()图0三维立体模型234034034034534034034.
603478&1$%.
6034234图2测试环境从而定义5中的二元关系退化成为容差关系.
若0<β<1时,定义5中的二元关系退化成为限制容差关系.
3畅3"*"值不完备信息系统在一个IIS中,若所有的未知属性值既有缺席型""和丢失型"倡"时,此时β的取值为1,因此分类的结果不受β的影响,从而定义5中的二元关系退化成为特征关系.
定理4设S为一IIS,对于A彻AT,由A决定的新二元关系表示为Rβ(A),特征关系为K(A).
当β=1时,则K(A)=R1(A).
证明对于任意x和y,总有|MAT(x,y)|/|AT|≤β=1成立,故K(A)=R1(A).
定理5设S为一IIS,对于A彻AT,由A决定的新二元关系表示为Rβ(A),对于任意X彻U,当0<α≤β≤1时,则AβR(X)彻AαR(X)(1)ⅩAαR(X)彻ⅩAβR(X)(2)证明(1)对任意x∈AβR(X),有RβA(x)彻X,由定理1,RαA(x)彻RβA(x),有RαA(x)彻X,即x∈AαR(X),故AβR(X)彻AαR(X).
式(2)对任意x∈ⅩAαR(X),有RαA(x)∩X≠碬,由定理1,RαA(x)彻RβA(x),有RβA(x)∩X≠碬.
即x∈ⅩAβR(X),故ⅩAαR(X)彻ⅩAβR(X).
定理6设S为一IIS,对于A彻AT,由A决定的新二元关系表示为Rβ(A),特征关系为K(A).
对于任意X彻U,则AK(X)彻AβR(X)(3)ⅩAβR(X)彻ⅩAK(X)(4)证明由定理2、3可易证.
4实例分析在表1所示的不完备信息系统中,根据定义3所示的特征关系,可以得到表2中KA(xi)所示的分类结果.
表1不完备信息系统Uabcd13210232113321倡4320532倡6倡2107倡倡108倡倡1倡932倡倡103210表2分类结果xiKA(xi)RβA(xi)1{1,3,6,7,8,9,10}{1,3,6,9,10}2{2,3,8,9}{2,3}3{1,2,3,6,7,8,9,10}{1,2,3,10}4{1,3,4,6,7,8,9,10}{1,3,4,6,9,10}5{1,2,3,5,6,7,8,9,10}{1,2,3,5,9,10}6{1,3,6,7,8,9,10}{1,6,10}7{1,3,6,7,8,9,10}{1,6,7,10}8{1,2,3,6,7,8,9,10}{8}9{1,2,3,6,7,8,9,10}{1,2,3,9,10}10{1,3,6,7,8,9,10}{1,3,6,9,10}根据特征关系分类是不尽合理的,如对象7与9没有任何已知相等的属性值,但对象9却被分入到特征类KA(7)中了,对象8与9也存在类似的情况,再者,对象7与8仅具有一个相同的属性值,但是对象8却有三个未知属性值,因此从直觉上来看,这两者之间不可分辨的可能性不大,对象8与6,7与10等也是同样的道理.
此时若假设β=0.
25,根据定义5,可以得到如表2中RβA(xi)所示的分类结果.
可以看出,这样的结果较好地解决了根据特征关系分类所产生的不合理情形,较为符合人类处理数据的直观感觉.
5结束语粗糙集理论由于其坚实的数学基础,近年来在知识获取、人工智能等众多科研领域得到了广泛的应用.
传统的粗糙集只能处理具有完备属性值的信息系统,然而在现实世界中由于各种原因,需处理的信息系统往往是不完备的.
建立IIS中的拓展粗糙集模型进行数据分析已成为粗糙集理论研究的一个热点问题.
以往很多学者所讨论的IIS中的未知属性值仅具有一种可能的解释,而本文所处理的IIS同时具有缺席型和遗漏型未知属性值,并且为了使得这种IIS中的分类结果更加符合客观实际和人在数据处理过程中的直观感觉,提出了一种新的带有参数的二元关系.
从文中的分析可以看出,只要合理地设置阈值β,新建立的粗糙集模型优于以往的各种拓展粗糙集模型.
在本文工作的基础上,下一步的工作就是在IIS中根据新的二元关系讨论知识约简等相关问题.
参考文献:[1]PAWLAKZ.
Roughsets[J].
InternationalJournalofComputerandInformationSciences,1982,11:341唱356.
[2]张文修,吴伟志.
粗糙集理论与方法[M].
北京:科学出版社,2001.
[3]王国胤.
Rough集理论在不完备信息系统中的扩充[J].
计算机研究与发展,2002,39(10):1238唱1243.
[4]杨习贝,杨静宇,吴陈,等.
不完备信息系统中基于特征关系的粗糙集模型[J].
模式识别与人工智能,2007,20(4):450唱457.
[5]KRYSZKIEWICZW.
Generationofrulesfromincompleteinformationsystems[C]//KOMOROWSKIHJ,ZYTKOWJM.
Procofthe1stEuropeanSymposiumonPrinciplesofDataMiningandKnowledgeDiscovery.
Berlin:Springer唱Verlag,1997:156唱166.
[6]STEFANOWSKIJ,TSOUKIASA.
Ontheextensionofroughsetsun唱derincompleteinformation[C]//ZHONGNing,SKOWRONA,OHSUGAS.
Procofthe7thInternationalWorkshoponNewDirec唱tionsinRoughSets,DataMining,andGranular唱SoftComputing.
Ber唱lin:Springer唱Verlag,1999:73唱81.
[7]GRZYMALA唱BUSSEJW.
Characteristicrelationsforincompleteda唱ta:ageneralizationoftheindiscemibilityrelation[C]//Procofthe3rdInternationalConferenceonRoughSetsandCurrentTrendsinComputing.
Uppsala,Sweden:[s.
n.
],2004:244唱253.
(上接第2097页)[2]谷清范,吴介一.
网格调度机制研究综述[J].
计算机应用研究,2006,23(5):1唱4.
[3]FOSTERI,KESSELMANC,TUECKES.
Theanatomyofthegrid:en唱ablingscalablevirtualorganizations[J].
InternationalJournalonSupercomputerApplications,2001,15(3):200唱220.
[4]BERMANF.
High唱performanceschedulers[C]//ProcofChapterintheGrid:BlueprintforaFutureComputingInfrastructure.
SanFrancis唱co:MorganKaufmannPublishers,1998.
[5]HOPFIELDJJ,TANKDW.
Neuralcomputationofdecisioninoptimi唱zation[J].
JournalofBiologicalCybernetics,1985,52:141唱152.
[6]CHANGCY,JENGMD.
Experimentalstudyofaneuralmodelforschedulingjobshop[J].
IEEEInternationalConferenceonSys唱tem,ManandCybernetics,1995,1:536唱540.
[7]HUANGYM,CHENRM.
Schedulingmultiprocessorjobwithresourcesandtimingconstraintsusingneuralnetworks[J].
IEEETransonSystem,ManandCybernetics,1999,29(4):490唱502.
[8]TAKEFUJIY.
Neuralnetworkparallelcomputing[M].
Norwell:Kluw唱erAcademicPublishers,1992.
·3012·第6期申锦标:不完备信息系统中一种拓展粗糙集模型