基于桌面网格的自调度算法的.研究与应用

《基于桌面网格的自调度算法的.研究与应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于桌面网格的自调度算法的研究及应用第l章绪论1．1选题背景和意义第l章绪论随着互联网技术的迅速发展，在网络上聚集了大量空闲的计算资源、存储资源和信息资源，这些资源的闲置使得大范围地理分布的异构计算机系统和资源整合在一起，形成一个大规模的计算平台成为日益迫切的要求。因此，网格(Grid)Iml应运而生。网格的概念最早于90年代中期提出，用于表述在高端科学和工程分布式计算中的一种基础构造形式。美国的资深科学家IanFoster将网格描述为：网格是构筑在互联网上的一组新兴技术，它将高速互联网、高性能计算机、大型数据库、传感器和远程设备等融为一体，为科技人员和普通

2、用户提供更多的资源、功能和交互性。由于网格能提供如此强大的功能，目前，包括中国在内，全世界很多国家都对网格投入巨大的人力物力，产生了很多具有里程碑意义的研究成果。在网格的诸多研究方向之中，对调度问题的研究无疑是最重要、最有挑战性的方向之一。桌面网格是网格的一种，其中的计算资源主要是由一台台的桌面PC机所组成，这些资源是异构的，有自己的存储资源和软件资源。桌面网格的调度问题是根据各节点的资源状态，把任务以合理的方式分配到相应的节点去执行。为了发挥出各节点的潜在计算能力，一个主要的问题就是怎样把任务分配给各节点以使各节点的负载达到平衡并使总的完成时间最小。循环是

3、科学计算领域中一个常见的、需要花费大量资源的问题【31，因此比较适合于在网格环境下进行并行计算。如果一个循环的各次迭代之间没有任何关系，各次迭代就可以看作是一个任务并可被独立的调度。传统模式上对这种并行循环的调度分为静态调度和动态调度14]两种。静态调度是指在编译时进行任务的分配，因而在程序执行前任务的大小已经是确定的，如OpenMP、MPI等。当循环的各次迭代拥有相等的工作量时静态调度可以发挥较高的性能，但是在处理以下几种情况时就会显示出不足：(1)循环的模式是不规则的；(2)循环的工作量在编译时是不可知的；(3)系统是异构的。第1章绪论基于桌面网格的自调

4、度算法的研究及应用动态调度则是为了解决以上问题而提出来的一种可在执行时调整具体任务的调度方式。动态调度可以实现不同节点间的负载平衡，因此适合于迭代次数不定以及每次迭代都花费不同时间的情况。自-N]／3芝(Self-Scheduling)ISl是一种动态、自适应的调度模式，比较适合于并行循环的调度。它是一种在应用层的调度技术，指一个任务可以分解成多个子任务，然后每个子任务分配到各个节点并行执行，从而减少完成时间的技术。在自调度中，各个执行服务的节点根据自己的资源状况主动向调度节点索取任务，而不是被动地等待调度节点分配任务。在有独立循环的计算中，如矩阵相乘、图像

5、渲染等，自调度都取得了比较理想的效果。而在桌面网格环境下，由于其系统的异构性和动态性，使得在这之上的自调度变得复杂。总体来说，具有以下特点：(1)自调度是基于异构环境的。由于桌面网格系统是由分布在网络上的各种PC机组成，这些资源的结构、速度或操作系统是异构的，因此桌面网格环境下的自调度必须面向异构环境；(2)自调度不干涉网格节点内部的调度。自调度只是负责把任务以合理的方式、合理的大小分配给网格节点执行，至于网格节点何时调度该任务及使用何种方式来调度是由节点内部调度策略决定的；(3)自调度能够动态自适应。网格中的资源不但是异构的而且网格的结构总是不停的改变：有

6、新资源加入、有资源出现故障等，因此自调度必须适应网格的这种动态性；(4)自调度必须具有通用性。提交给网格的作业依据占用CPU的时间及数据量的大小可以分为计算密集型、数据密集型、计算和数据均密集型三种，因此桌面网格环境下的自调度必须能满足这三种应用的要求。桌面网格环境下自调度的目标就是以最优的方式分割任务，在最短的时间里完成用户的请求。具体的目标包括负载平衡、完成时间短等。(1)完成时间短。完成时间指用户把任务提交给网格到网格把最终结果返回给用户的这段时间。这是调度领域里一个最常见、虽普遍的目标，完成时间越短，说明调度算法越好，用户的满意度也越高；(2)负载平

7、衡。由于桌面网格环境是异构的，各节点的性能不同，因此分配任务时避免给一个性能比较差、负载比较重的节点分配过多的任务，否则会严重影响任务2基于桌面网格的自调度算法的研究及应用第1章绪论总体的完成时间。1．2研究现状早期的自调度算法都是基于集群系统的。文献[6】中介绍的PSS(PureSelf-Scheduling)算法每次分配一个单位的工作量给计算节点，而CSS(ChunkSelf-Scheduling)算法每次分配k个单位的工作量给计算节点，这两种算法在整个程序的执行过程中每次分配的任务量都是不变的。文献【3】中的GSS(GuidedSelf-Schedul

8、ing)算法、文献【7】中的FSS(Factorin