未来智库 > 神经网络论文 > 一种基于神经网络的网格实时调度算法

一种基于神经网络的网格实时调度算法

发布时间:2018-05-29 01:07:00 文章来源:未来智库    
    关键词:调度;网格计算;神经网络;并行计算
    中图分类号:TP301.6文献标志码:A
    文章编号:1001-3695(2009)06-2095-03
    doi:10.3969/j.issn.1001-3695.2009.06.028
    
    Grid real-time scheduling algorithm based on neural network
    LI Sheng-xin��1,2,DUAN Sheng��1
    (1.Dept. of Computer Science, Xiangnan University, Chenzhou Hunan 423000, China;2.School of Computer & Communication, Hunan University,Changsha 410082,China)
    Abstract:Within specified deadlines,this paper modeled performance dynamism of resources with the help of queuing techniques.Employed a mathematical neural model afterwards, to schedule subtasks of the application.Implemented the proposed model on GridSim toolkit to evaluate the performance of scheduling algorithms.Simulation experiments show that in approximately 90% of cases,this model schedules tasks successfully and efficiently.
    Key words:scheduling; grid computing; neural networks; parallel computing
    
    0 引言��
    
    网格计算是利用硬件和软件资源来提供可靠的、可调节的和方便的接口来完成高端计算量[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(tan h(λ0Ui)+1)(3)
    λ0是常量,叫做腰槽,决定S型函数的斜面。��
    1.1 神经网络数学模型��
    虚拟的神经网络数学模型由两部分组成[6],即神经元和突触连接。输出信号传输从一个神经元到其他的神经元通过突触连接。一个神经元输入信号的决定来自其他神经元的输入信号的线性权值和,各自的权值是突触连接的长度。每个虚拟的神经元有输入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≠iVijkVi1jk��
    b)-B��Mj1=1j1≠j ��Tk1=1VijkVij1k1��
    c)-CL(2(��Tk1=1Vijk1-Pij))��
    d)-DK(2(��Ni1=1Vi1jk-1))��
    e)-EH(k-(di-1))��
    f)-FH(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(α)=1 if α>0
    0if α=0
    -1if α<0, K(α)=α if α≥0
     0 if α<0, H(α)=1 if α>0
    0 if α≤0(9)��
    在动作方程式中抑制系统的振动行为插入滞后因素,使汇聚时间变得相当短,针对McCulloch-Pitts的神经模型插入了滞后因素,给出了第i个神经元的输入或输出函数如下:��
    Vi=f(Ui)=1if Ui>UTP
    0if Ui<LTP
    unchangedotherwise(10)��
    这是一个改进的Maximum神经模型的形式,UTP和LTP分别表示上行点和下行点。Maximum神经模型能保证得到满意的解决方法,由M个集群组成,每个集群包括了N个神经元[8]。在改进的Maximum神经模型中“winner-take-all”函数是内含的,预示着在每个集群中的N个神经元有且只有一个最大值鼓励执行,相应地给出了第M个集群中第i个神经元输入或输出函数如下:��
    Vmi=1 if Umi=max{Um1,…,Umn}and
    Umi≥Umj for i>j
    0otherwise(11)��
    1.2.2 调度算法��
    根据以上数学神经模型,本文设计了如下算法:��
    begin��
     initialize Uijk randomly��
     while (a set of conflicts is not empty) do��
     begin��
    for i:=1 to N do��
    for j:=1 to M do��
    for k: =1 to T do��
    begin��
     Uijk =Uijk+ΔUijk��
     Vijk =f(Uijk)��
    end��
     for i:=1 to N do��
     begin��
    find the maximum Uijk.��
    determine a segment (j) in which the maximum Uijk exists. If there is tie remove it randomly.��
    the output of the other segment′s neurons is set to zero.��
    end��
     end��
    end.
    其中:i表示任务变量为1~N;j表示资源变量为1~M;k表示时间变量为1~T;U和V分别为神经元的输入与输出函数,Vijk相当于提出的神经网络模型中的神经元。算法用了异步的方法来更新处理,当用N.M.T处理元素时,算法执行所需的时间复杂度接近O(1),因此调度的需求时间是可以忽略不计的。��
    
    2 测试环境��
    
    使用GridSim工具模拟所提出的方法,执行调度算法在一个单一的机器上:Pentium 4处理器和512 MB 内存。改变GridSim一些类来提供支持对于紧急、非紧急和本地任务,重写SpaceShared类,定义了一些新类,如ImpatientGridlet、Patient-Gridlet和LocalGridlet分别对应于紧急、非紧急和本地任务。在SpaceShared类检查了在任务队列中每个紧急任务的最终期限,如果已到期,那么它将从队列移除。对于每个资源都有紧急的、非紧急的和本地任务来使用,这些任务基于它们的时间范围和每天的时间状态都有一个预先到达率。一个资源的所有节点是同一的,除了不同资源可以有不同的节点类型,每个资源有多个任务,每个任务有多个节点,每个节点服务率μ是预先确定的,根据资源历史调度情况可以完成。考虑了不同的测试环境,如图2所示。��
    每个高速主干网的带宽在图2中描述了,延迟设为10 ms,每个资源的使用平台对于非紧急的、紧急的和本地任务根据泊松方法分别为λp、λi、λ1,这些任务有一个最终期限直到服务结束。��
    3 模拟实验及分析��
    表1描绘了预测每个资源的任务响应时间,这些值输入到调度算法;表2显示了调度结果,调度算法的执行时间可以忽略不计(少于1 s)。比较了表1和2,再一次验证了调度的正确性。��
    为了显示带宽在模型中的影响,改变了对于任务3的连接带宽为0.000 1~2.0 GB。在表3中对于资源每个任务的响应时间是减少的,在表4中对于R#3有四个任务被调度而在表2中只有两个任务被调度,说明了在网格环境中调度带宽的重要性。��
    表5中显示了全面的结果,在不同的例子中使用了不同的网络技术、资源、任务及参数,每个例子重复了10次,调度算法总是汇聚于一点,从表中可以看到大约90%的例子对于调度任务是成功的。��

         
    4 结束语��
    
    在大多数分布式计算平台,利用可用资源对于分布应用的调度进行高性能计算是必要的。基于队列理论提出了一种实时应用的并行调度算法,实时应用包含了几个独立的任务,并且每个任务有一个最终期限直到服务结束,对每个任务在每个资源上响应时间预测的执行使用了资源的动态运用模型。在这个模型中,考虑了带宽、延迟和通信背景的影响。本文提出的方法主要集中在最佳的解决方法与被给的最终期限,调度能够执行在并行机构,算法执行的时间复杂度为O(1),模拟实验证明了提及的模型特别是对于大资源服务率的任务预测响应时间是正确和可行的。在这个工作中,假设非紧急的、紧急的和本地任务的到达率也就是节点的服务率对于每个资源是预先确定的,而在网格调度中是很难预测的,特别是对于新资源,下一个目标是证明假设任务的泊松到达,考虑新增的资源和资源失败的问题。
    
    参考文献:
    [1]FOSTER I,KESSELMAN C.The grid,blueprint for a new computing infrastructure[M].San Francisco:Morgan Kaufmann Publishers,2004.
     [2]谷清范,吴介一.网格调度机制研究综述[J].计算机应用研究,2006,23(5):1-4.
    [3]FOSTER I,KESSELMAN C,TUECKE S.The anatomy of the grid:enabling scalable virtual organizations[J].International Journal on Supercomputer Applications,2001,15(3):200-220.
    [4]BERMAN F.High-performance schedulers[C]//Proc of Chapter in the Grid:Blueprint for a Future Computing Infrastructure.San Francisco:Morgan Kaufmann Publishers,1998.
    [5]HOPFIELD J J,TANK D W.Neural computation of decision in optimization[J].Journal of Biological Cybernetics,1985,52:141-152.
    [6]CHANG C Y,JENG M D.Experimental study of a neural model for scheduling job shop[J].IEEE International Conference on System, Man and Cybernetics,1995,1:536-540.
    [7]HUANG Y M,CHEN R M.Scheduling multiprocessor job with resources and timing constraints using neural networks[J].IEEE Trans on System, Man and Cybernetics,1999,29(4):490-502.
    [8]TAKEFUJI Y.Neural network parallel computing[M].Norwell:Kluwer Academic Publishers,1992.

转载请注明来源。原文地址:https://www.7428.cn/vipzj18932/
 与本篇相关的热门内容: