（计算机应用技术专业论文）网格计算中的任务调度算法研究.pdf

摘要 摘要 网格是近年来信息技术领域的热点研究课题，是支撑未来各类应用的国家信 息基础设施。任务调度问题是网格研究和应用必须解决的一个关键问题。本文对 网格计算中的任务调度模型和任务调度算法进行了探索和研究，主要工作分为如 下四个方面： 1 从应用模型、平台模型和调度目标三个方面对现有任务调度模型进行了研 究，对模型参数的精确性和简单性之间的折衷进行了分析，探讨了更现实任务调 度模型的若干指标。 2 研究了可分任务调度问题，得到如下三个方面的结果。第一，提出了带启 动开销的非阻塞通信模型，解决了基于此模型的大规模可分应用的优化调度问题； 第二，研究了大规模可分应用的周期性任务调度算法，给出了同构平台中各类参 数的最优取值表达式；第三，研究了任意网络拓扑中的可分应用调度问题，提出 两类启发式任务调度算法。 3 研究了独立任务调度问题，得到如下四个方面的结果。第一，针对同构平 台，提出一种基于局部搜索的任务调度算法；第二，针对异构平台同构任务，提 出一种带记忆功能的任务调度算法；第三，研究了异构平台的异构任务调度问题， 提出了任务调度优先级概念，得到一类基于优先级的任务调度算法；第四，提出 了一种针对异构平台异构任务的基于局部搜索的任务调度算法。 4 研究了依赖任务调度问题，提出了一种基于关键路径的列表调度算法。该 算法在构造调度列表时综合考虑了各种任务的影响，在处理机选择时提出了“向 前看的策略，从而使得关键任务能够尽早执行，有效地缩短了调度长度。 关键词：网格计算，任务调度，调度模型，调度算法，可分任务，独立任务，依 赖任务 a b s t r a c t a b s t r a c t t h eg r i di san e wn a t i o n a li n f o r m a t i o ni n f r a s t r u c t u r ef o rm a n yf u t u r ea p p l i c a t i o n s i th a sb e e nar e s e a r c hf o c u si nt h ef i e l do fi n f o r m a t i o nt e c h n o l o g yi nr e c e n ty e a r s i na 鲥dc o m p u t i n ge n v i r o n m e n t ，t h ep r o b l e mo ft a s ks c h e d u l i n gi sv e r yc r i t i c a l i nt h i s t h e s i s ，m o d e l sa n da l g o r i t h m sf o rs c h e d u l i n gt a s k si nt h eg r i da r es t u d i e d t h em a i n r e s u l t sa r e 觞f o l l o w s ： 1 m o d e l sf o rt a s ks c h e d u l i n gi n c l u d i n ga p p l i c a t i o nm o d e l ，p l a t f o r mm o d e la n d s c h e d u l i n go b j e c t i v ea r ei n v e s t i g a t e di nd e t a i l t h et r a d e - o f fb e t w e e nm o d e la c c u r a c y a n dm o d e ls i m p l i c i t yi sd i s c u s s e d s e v e r a lp a r a m e t e r so fm o r er e a l i s t i ct a s ks c h e d u l i n g m o d e la r ei n d u c e d 2 t h ep r o b l e mo fd i v i s i b l et a s ks c h e d u l i n gi ss t u d i e da n dt h ef o l l o w i n gr e s u l t sa r e p r e s e n t e d f i r s t ，o p t i m a la l g o r i t h m sb a s e do nam o r er e a l i s t i cm o d e l ，i e ，n o n - z 凹o s t m t - u pc o s tf o rn o n - b l o c k i n gm o d e lo fc o m m u n i c a t i o n , a r ep r o p o s e df o rs c h e d u l i n g l a r g e w o r k l o a do nh e t e r o g e n e o u ss y s t e m s e c o n d , ap e r i o d i cm u l t i - i n s t a l l m e n t a l g o r i t h m i s p r o p o s e da n dd o s e d f o r me x p r e s s i o n s f o r o p t i m a lp a r a m e t e r s o l l h o m o g e n e o u ss y s t e m sa r ed e r i v e d t h i r d ，t w ok i n d so fh e u r i s t i cs c h e d u l i n ga l g o r i t h m a r ep r o p o s e df o r s c h e d u l i n gd i v i s i b l el o a do na r b i t r a r y t o p o l o g i c a ln e t w o r k 3 t h ep r o b l e mo fi n d e p e n d e n tt a s ks c h e d u l i n gi ss t u d i e da n dt h ef o l l o w i n gr e s u l t s a r ea c q u i r e d f i r s t , al o c a ls e a r c ha l g o r i t h mi sp r o p o s e dt os o l v et h ep r o b l e mo ft a s k s c h e d u l i n g i nh o m o g e n e o u se n v i r o n m e n t s e c o n d , am e m o r yb a s e da l g o r i t h mi s p r o p o s e df o rs c h e d u l i n gs a l l l e - s i z et a s k so nh e t e r o g e n e o u sp l a t f o r m t h i r d ，ac o n c e p to f t a s ks c h e d u l i n gp r i o r i t yi sp r o p o s e da n dac l a s so fs c h e d u l i n ga l g o r i t h mc a nb ed e r i v e d a c c o r d i n gt ot h ep r i o r i t y f o u r t h , al o c a ls e a r c ha l g o r i t h mi sp r o p o s e df o rt a s k s c h e d u l i n gi nh e t e r o g e n e o u ss y s t e m 4 t h ep r o b l e mo fd e p e n d e n tt a s ks c h e d u l i n gi ss t u d i e da n da ne f f i c i e n tl i s t s c h e d u l i n ga l g o r i t h mb a s e do i lc r i t i c a lp a t hi sp r e s e n t e d b ym e a n so fan e wa p p r o a c h f o rc o n s t r u c t i n gt h e t a s kl i s t , a n da ne f f i c i e n tp r o c e s s o rs e l e c t i o np r o c e d u r eu s i n g l o o k i n ga h e a ds t r a t e g y , t h ea l g o r i t h ms h o r t e n st h em a k e s p a ng r e a t l y i i a b s t r a c t 一 k e y w o r d ：g r i dc o m p u t i n g , t a s ks c h e d u l i n g , s c h e d u l i n gm o d e l ，s c h e d u l i n ga l g o r i t h m ， d i v i s i b l et a s k , i n d e p e n d e n tt a s k , d e p e n d e n tt a s k 1 1 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名与叩粤e l 期：1 。眸哼月日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：f 鱼塑竺导师签名：苫过窭 日期：2 。0 7 年，月7 1 7e l 第一章绪论 第一章绪论 网格( g r i d ) 是近年来信息技术领域的热点研究课题，是支撑未来各类应用的 新的国家信息基础设施( i n f r a s t r u c t u r e ) 。任务调度问题是网格研究和应用必须解 决的一个关键问题。本章首先介绍论文的选题依据和研究意义，接着总结国内外 相关研究工作，然后介绍论文的研究内容和主要工作，最后给出论文的组织结构。 1 1 立题背景和意义 1 1 1 网格计算技术 网格计算是近年来兴起的新的技术研究热点，是影响信息技术下一个高潮的 最重要的核心技术。网格被认为是支撑未来各类应用的新的国家信息基础设施， 是第三代因特网应用，是下一代的万维网，是1 9 9 5 2 0 1 0 年时段计算机体系结构、 操作系统、用户界面领域最重要的突破性创新机会。网格技术的研究和应用必将 对我国社会和经济的发展、国防、科学研究、以及人们的生活和工作方式产生巨 大的影响【。 鉴于网格计算的重要性，网格技术已经得到各国政府、学术界和工业界的高 度重视，并投入了大量的资源进行相关技术的研究和开发。为保持制高点，美国 已于2 0 0 5 年启动了赛百基础架构( c y b e r i n f r a s t r u c t u r e ) 计划和t e r a g r i d ( d t f ) 二期 计划【7 1 。欧洲的英国、荷兰、意大利、德国和法国，以及亚洲的日本和韩国都开展 了网格计算的相关研究。除政府外，m m 、s u n 、l i p 、p l a t f o r m 、m i c r o s o f t 、n e c 、 n t r 等也都开展了与网格计算相关的研究【1 4 1 1 。 我国也启动了多项网格计算相关研究项目。国家自然科学基金分别于2 0 0 3 和， 2 0 0 5 年启动了“以网络为基础的科学活动环境研究 重大研究计划【6 】；8 6 3 计划在 2 0 0 2 年“高性能计算机及其核心软件刀重大专项基础上，又于2 0 0 7 年启动了“高 效能计算机及网格服务环境重大项目【5 】；教育部于2 0 0 3 年通过了“c h i n a g r i d 计 划 等。在这些项目的资助下，我国的织女星网格、中国国家网格【8 】、上海网格、 教育网格等已经具有一定的知名度。 网格计算的目标和理想是通过有效整合因特网上的所有资源，包括计算能力、 电子科技大学博士学位论文 存储能力、文件、数据库、科学仪器和设备等，为人们提供他们所需要的任何信 息【l l l l 。在网格计算时代，人们可以通过“网格插座 来使用网格资源【2 】，就如同 使用电力和水力资源那样方便，如图1 1 所示。 厂一一 i i i i i i l i 图l - l 网格系统逻辑视图 由于网格是一种新技术，网格的精确含义和内容仍然在不断变化和发展之中。 i a nf o s t e r 定义网格计算是“在动态的、多机构的虚拟组织中协调资源共享和协同 解决问题”【3 1 。i a nf o s t e r 还提出判断网格的三个标准，即协调非集中控制的资源； 使用标准的、开放的和通用的协议和接口；提供非平凡的服务【1 2 1 。然而，这三个 标准是非常严格的。因此，目前普遍将i a nf o s t e r 的网格观点称为“狭义的网格 观。“广义”的网格观认为网格的本质是共享和服务，即网格就是资源一体化和服 务一体化【2 1 1 1 。 网格计算起源于科学计算中的分布式高性能计算，主要目的在于聚合基于因 特网的计算资源，解决大规模应用的计算问题。后来由于企业界的加入，网格计 算逐步转变为基于服务的计算。目前人们将计算网格( c o m p u t a t i o n a lg r i d ) 1 3 数 据网格( d a t ag r i d ) 、信息网格( i n f o r m a t i o ng r i d ) 、知识网格( k n o w l e d g eg r i d ) 、 以及p 2 p 计算( p e e r - t o p e e rc o m p u t i n g ) 、普适计算( p e r v a s i v ec o m p u t i n g ) 等都 归为网格计算范畴【2 , 9 - 1 1 】。 实现网格计算的宏伟理想需要观念上和技术上的创新。在技术上，网格计算 中必须解决的关键技术还很多，比如网格体系结构和标准、网格安全机制、网格 资源管理、网格任务调度、网格通信技术、网格操作系统、网格用户界面等。这 些关键技术的每一个方面都是重要而复杂的，其中资源管理和任务调度是最基本、 最重要的问题之一。首先，网格必须能够快速确定系统中存在的资源以及资源的 各种状态和属性；其次，网格应用必须能正确部署到网格计算环境，以便提供非 平凡的服务质量【2 ，5 l 。 2 第一章绪论 1 1 2 任务调度问题 由于网格的核心是资源共享【l - 6 , 1 1 ，而任务调度直接决定了资源的有效利用， 因此它就成为网格计算最重要和最关键的问题之一。任务调度问题是一个古老而 又基础的问题，在各行各业都得到广泛的研究和应用，例如计算机操作系统中的 作业或者进程调度、磁盘调度和多处理机调度；制造业中的生产调度；交通运输 中的车辆调度和物品调度等【2 , 1 3 - 2 1 】。 网格系统通常分为若干个层次，而且各个层次都存在任务调度问题，例如， 网格操作系统、网格中间件和应用程序级都存在调度问题1 2 2 - 2 5 】。但系统各个层次 任务调度的目标和方法都有各自的要求，例如，操作系统通常追求系统吞吐量和 公平性，而应用程序通常追求最短完成时间。本文将主要研究网格计算中的应用 ( 程序) 调度问题，目标是最小化应用的完成时间。 通常，一个应用在网格平台的调度过程包括应用程序分析和分解、资源发现 和选择、任务调度、任务执行等几个方面，如图1 - 2 所示。 l 任务调度+ _ 叫任务执行 图1 2 网格系统下的任务调度 应用分析与分解部分主要完成应用程序特征分析并将应用程序分解为一系列 任务。应用程序特征包括应用是否可以分解、分解得到的任务之间是否存在依赖 关系、任务执行时间估计等；应用分解根据应用特征将应用程序分解为若干个任 务。资源建模部分主要完成资源特性分析。资源特征主要包括处理机的系统结构、 指令类型、存储容量、操作系统、计算速度、负载情况，以及互连网络的通信速 度、拓扑结构、路由机制、流控机制等。任务调度部分将根据任务模型、资源模 型和调度目标进行资源选择、分配任务到处理机并安排任务在处理机上的执行时 间 2 - 3 , 1 3 , 1 9 】。 显然，任务调度是一项复杂且困难的工作。任务调度与应用模型、资源模型 和调度目标紧密相关，然而精确地建立任务模型和资源模型是非常困难甚至是不 3 电子科技大学博士学位论文 可能的【2 4 】，所以，任务调度通常需要对任务模型和资源模型进行若干假设【2 6 彩】。 然而，即使在非常简化的模型下，任务调度问题也已经被证明是n p 难题【2 0 】。因此， 任务调度只能依赖于启发式算法，然而启发式算法的各种有用组合方法有限，所 以高性能调度器及其算法研究曾在一段时间进展不大。 虽然任务调度问题已经得到深入和持久的研究，但是由于问题的复杂性，已 经提出的大量调度算法往往基于一些对网格系统不现实的模型假设【1 5 1 6 1 。典型的 假设包括通信无开销、任意处理机通过网络直接相连、处理机具有无限多的端口、 通信链路任何时候可供任意多对结点同时独占网络带宽、网络容量无限、处理机 专用等。因此，基于这些假设而设计的调度算法在现实的网格计算环境应用时将 导致性能急剧下降。 最近，基于更现实的( r e a l i s t i c ) 网格任务调度模型，特别是基于更实际通信 模型的任务调度问题得到人们的极大关注并取得了一定进展 1 5 - 1 8 , 3 0 - 3 5 】。开展这方面 研究的先行单位包括法国的e n s l y o n 和美国的圣地亚哥超级计算中心 ( s d s c ) ，以及波兰技术大学等。主流的国际会议，如i p d p s 、c c g r i d 、i c p p 、 h i p c 、s c 等都设立专题研究更现实模型下的计算技术；权威刊物i e e et r a m o n p a r a l l e l & d i s t r i b u t e ds y s t e m 在2 0 0 6 年2 月出版的专辑主题就是：异构集群( 现实 平台模型) 的算法设计和调度技术。 虽然国内在资源管理和任务调度方面研究也很多，但有突破性创新的成果较 少，和国际最新研究成果的差距是明显的。因此，开展基于更实际网格任务调度 模型以及基于更实际模型的调度算法研究是非常重要的。事实上，2 0 0 6 年国家自 然科学基金重大项目“当代并行机的并行算法应用基础研究 的目标就是：“建立 符合大规模并行系统本质特性的新型并行计算模型，作为算法研究和实现的基础； 在此基础上，研究若干具有典型应用背景的大规模并行算法，并进行高效率的实 现和分析。 l 6 j 1 2 研究现状和发展趋势 由于网格计算中的任务调度问题涉及太多的研究内容，本文不可能对其一一 陈述，因此下面只综述作者所知并与本文内容最密切相关的部分。 1 2 1 任务调度模型 不同文献对于“网格任务调度模型 究竟应该包括哪些内容的理解是不同的。 4 第一章绪论 我们认为“网格任务调度模型是对网格任务调度问题涉及的各种对象的描述和 抽象，这些对象主要包括：( 1 ) 应用程序及其分解而得的任务；( 2 ) 计算平台涉 及的各种资源，包括计算资源、网络资源、存储资源、设备、文件等；( 3 ) 调度 所要达到的目标。 这种定义方法和任务调度理论中著名的口l iy 模型【1 9 有很多共同之处。在 口i iy 模型，口表示处理机环境，表示各种约束条件和特征，y 表示优化标准。 虽然g r a h a m 等早在1 9 7 9 年就提出了此模型，而且在作业调度理论研究方面得到 广泛的使用，然而在网格任务调度领域却几乎没有人使用甚至意识到它。直到论 文快完成时，我们才发现一篇2 0 0 5 年的会议文酬2 8 】提到将口j iy 模型推广以覆 盖网格调度问题。 任务调度模型是任务调度算法设计和分析的基础，因而处于非常重要的地位， 大量文献对任务调度模型及其组成部分进行了广泛而深入的讨论【5 - 7 ；2 5 1 。任务调 度模型的建模目标是为任务调度算法提供一个既能精确描述各种对象而又足够简 单的模型。然而，由于这两个目标是矛盾的，因此各种任务调度模型需要在模型 的精确性和问题的可解性之间取得合适的平衡。 由于网格是从高性能计算发展而来的，因此网格计算受到高性能计算的重要 影响。高性能计算中最重要的部分就是并行分布式计算，它们在描述资源实体， 主要是处理机和网络资源实体时提出了各种计算模型【3 6 】。并行计算模型中非常 知名的模型包括p r a m 模型、b s p 模型【钧】、l o g p l o g g p 模型【4 3 埘】等，在这些模型 基础上已经提出了多种改进模型，典型的代表包括f p r a m 模型、h c g m 模型、 c l u s t e r - m 模型、h b s p k 模型4 1 - 4 2 、i o g g p c 模型3 7 】等。贯穿这些模型发展的一条主 线更实际地反映并行机特有的通信开销，主要体现在资源的异构性、存储器层次 结构、通信竞争等方面。 这些模型主要描述处理机资源和网络资源。对于处理机资源，绝大多数模型 都假设处理机是同构的；对异构的研究主要分为类型异构和速度异构，其中速度 异构主要指计算速度不同。处理机的执行代价一般假定和任务大小成正比。最近 文献 3 3 ，3 4 为计算代价模型增加了非零启动开销；文献【5 1 】采用分段线性函数来计 算任务执行时间；少数文献采用随机过程来描述处理机速度【5 0 】。 对于通信资源，各种模型假设差别很大，而且存在很多不现实的假设。典型 的包括：不存在通信开销、通信网络是同构的、通信开销是恒定的、通信没有冲 突、网络具有无限容量、网络端口无限等【3 6 。4 6 4 钆5 0 1 。在网络通信代价计算中，绝大 部分使用线性开销模型，最近一些文献开始使用非零启动开销的仿射( a f f i n e ) 时 电子科技大学博士学位论文 间开销；部分模型开始考虑通信端口问题、通信竞争问题、通信缓存问题、链路 共享问题等【1 5 - 1 6 , 3 0 = 3 5 】。 对于应用程序模型，目前已经提出了独立任务模型、依赖任务模型、可分任 务模型、独立同构任务模型、并行任务模型【2 9 】等。独立任务模型假设应用由若干 不可划分的任务组成，各个任务之间没有任何关系；依赖任务模型假设任务之间 存在依赖关系；可分任务模型假设应用可划分为任意粒度；并行任务模型假设一 个任务需要几个处理机才能执行。 对于性能模型，目前已经提出并使用了多个性能指标。这些性能模型可以大 致分为基于系统的指标和基于用户的指标。基于系统的指标包括系统吞吐量、资 源利用率、效率和公平性等；基于用户的指标包括作业周转时间、平均延迟和最 短完成时间( m a k e s p a n ) 等。最近也有部分文献开始提出多目标模型【5 3 】和多q o s 约 束【5 4 巧5 1 的性能模型。 1 2 2 任务调度算法 目前已经提出的任务调度算法数目众多，下面我们简单对其分类描述。按照 不同的标准可以对任务调度算法进行多种分类。比如，按照调度算法的运行时间 可将其分为静态调度、动态调度和动静相结合的调度；根据调度算法运行的位置 可分为集中式调度和分布式调度；根据调度发生的时机可分为在线调度和离线调 度等。任务调度还和任务分配、负载平衡等概念存在很多关系。本文主要研究静 怠调度算法，从可分任务、独立任务和依赖任务三个方面进行介绍。 1 2 2 1 可分任务调度 可分任务的研究始于1 9 8 8 年。r o b e r t a z z i 等人在分析传感器网络中的测试数 据时，对分布式计算带来的好处与由此造成的通信开销进行折衷时提出了可分任 务模型【5 9 枷1 。相对属于n p 难题的传统任务调度而言，可分任务模型给出了一种简 单而且可能得到解析优化结果的方法，因此近年来得到广泛关注 s l , 5 9 删。 2 0 0 5 年，b e a u m o n t 等在文献 6 1 e p 全面综述了星型和树网中的可分任务调度 问题的研究现状及存在的问题；2 0 0 3 年r o b e r t a z z i 和b h a r a d w a j 等在文献 5 9 ，6 0 】 中对近年来可分任务理论和应用的相关研究进行了综述和评价，并在c l u s t e r c o m p u t i n g ) ) 组织出版了一期专辑。文献【6 2 对可分任务调度的一些问题进行了讨 论。19 9 9 年d r o z d o w s k i 等在文献 6 3 】中对可分任务理论的相关概念及其在包括线 性阵列、星型网络、总线、超立方体、m e s h 等各种拓扑网络中的调度算法进行了 6 第一章绪论 综述和回顾。关于可分任务理论较全的研究结果列表可参见 6 4 】，它是该理论奠基 人之一r o b e r t a z z i 维护的关于可分任务调度的研究成果列表。 r o b e r t a z z i 和b h a r a d w a j 等提出和研究的可分任务理论采用线性代价模型，即 计算和通信都不存在启动开销。在这个模型假设下，如果网络是同构的，无论处 理机是否同构，都可以得到如下结果：对于任意的问题规模，任务的最优调度需 要所有处理机参与计算且同时完成计算，而且应用的完成时间与任务分配的先后 顺序无关【6 1 1 。这样的模型下，容易得到解析的调度结果，从而完美地解决了可分 任务调度问题。文献 6 8 】研究了异构网络的可分任务调度问题，结果表明，应用的 完成时间取决于特定的任务调度顺序。文献【6 9 】证明了此模型下的优化任务调度应 按照网络带宽从高到低的顺序进行。 没有启动开销的假设是不适合网格计算环境的【3 5 , 4 7 1 ，d r o z d o w s k i 等的研究 主要考虑通信启动时间非零的情形。文献 6 2 提出一个复杂的混合线性规划来刻画 任务最优分配问题，结果表明任务的完成时间依赖于任务的分发顺序，而且，此 时的最优分配不必所有处理机都参与计算。但该文没有得出相应的优化调度顺序。 b e a u m o n t 等在文献 6 1 ，6 9 对 6 2 】中的带宽模型进行了简化，假设带宽相同，结果 表明任务的优化分发顺序应按照启动开销和计算速度乘积非增的顺序进行。 文献 7 0 ，7 1 】同时考虑了非零的计算启动开销和通信启动开销，结果表明，优化 的分配不必所有处理机都参与计算，优化调度密切依赖于任务分配顺序。在一定 条件下，任务的优化分配应按照计算速度非增的顺序进行。 上述文献都假设消息传输是阻塞的，即处理机只有收到全部任务后才能开始 计算。2 0 0 2 年，文献 6 5 】首次研究了非阻塞模式的可分任务调度问题，文献 6 6 】对 其进行了系统化。它们均假设系统同构且无启动开销，通过假定处理机同时完成 计算，从而得到一系列递推关系并求得任务完成时间和各处理机完成任务量。文 献 6 6 】没有表明给出的调度是最优的，也未讨论任务分发顺序问题。文献【6 7 】将 6 6 】 的研究推广到异构网络，即假设计算速度和通信速度可能不同，但通信和计算不 存在启动开销。该文推导了应用的完成时间和各处理机任务数量的解析表达，给 出了任务调度的优化顺序，并对几种特殊情况进行了讨论。 上述文献均采用单趟调度策略。由于单趟调度存在极大的处理机空闲等待时 间，因此人们研究了多趟调度问题。文献 7 7 最早针对同构平台研究了多趟调度算 法，得到很多有意义的结果。但由于它采用线性代价模型，因而是不现实的，且 将其推广到非零启动开销存在很大困难。文献 6 1 ，6 9 ，7 4 7 9 都研究了多趟调度问 题，但都增加了若干其它假设。 7 电子科技大学博士学位论文 大多数可分任务调度研究采用星型或者总线网络平台，文献 6 2 6 3 ，7 3 ，8 3 研究 了其它网络拓扑结构下的可分任务调度问题。文献 8 0 8 1 研究了任意网络拓扑的 可分任务调度问题，它首先得到网络生成树，然后对得到的生成树进行调度。其 它方面的研究包括：多个可分应用【8 2 】、涉及结果返回时间 s s 】，以及其它目标函数， 如同时追求最短时间和最小经济代价【8 4 , 8 6 等。 1 2 2 2 独立任务调度 独立不可分任务一直是作业调度的研究内容【1 3 - 1 4 , 1 9 ，在网格计算领域也对独立 任务调度进行了大量的研究【8 1 6 1 。但这二者的目标是不一样的，前者主要从系统 角度追求吞吐量，而后者的大部分( 我们关注的) 研究主要面向用户，以应用的 最短完成时间为追求目标。 f e i t e l s o n 在文献【1 3 】中回顾了一般的作业调度问题。从实际使用的角度，他认 为目前只有两种主要的调度技术：基于回填( b a c k f i l l i n g ) 和基于成组( g a n 曲。通过对 基本的先来先服务( f c f s ) 算法中使用回填可以获得一系列好处，包括提高处理机 利用率，缩短响应时间等。在回填算法设计时主要考虑的几个问题是：预留任务 数目、任务排队顺序和向前看的任务数量。成组调度类似于使用活动工作集的存 储器页面管理，基于成组调度的算法主要考虑成对( p a i r e d ) 和内存限制，以及接纳 控制机制等。 网格计算中的独立任务调度主要来源于异构计算中的元任务调度。早期的任 务调度考虑同构并行处理机的调度，也就是g r a h a m 表示法中口域取“p ”的情形。 针对并行计算机已经提出大量的任务调度算法。文献 8 6 9 3 1 给出了几个代表算法， 其中【8 6 9 2 】为贪心算法，【9 3 】为基于分支限界方法的精确算法。并行处理机调度多 数采用列表调度技术，典型算法包括l s 算法、l p t 算法等，在它们的基础上也提 出了多种算法变体。大多数算法基于构造的基本思想，文献 8 6 ，8 9 9 1 给出了基于 局部搜索【蚓思想的改进算法。 相对而言，异构平台的任务调度更为复杂，文献 9 5 1 0 4 给出了部分典型算法。 这个问题对应于g r a h a m 表示法中口域取“q 和“尺 的情形。关于异构平台的 独立任务调度问题的研究非常多，文献 9 6 给出了同构任务异构平台的优化调度算 法，文献 9 9 】对1 1 种典型的静态任务调度算法进行了实验对比，结果表明遗传算 法和m i n - m i n 算法较优。基于m i l l m i i l 算法提出了多种改进算法，典型的文献包 括 9 7 9 8 ，10 0 10 2 。 文献 1 0 7 1 1 0 主要研究了动态调度算法，典型的算法包括s s ( s e l f s c h e d u l i n g ) 、 第一章绪论 b s s ( b l o c ks e l fs c h e d u l i n g ) 、g s s ( g u i d e ds e l fs c h e d u l i n g ) 、f s ( f a c t o f i n gs c h e d u l i n g ) 、 t s s ( t r a p e z o i ds e l fs c h e d u l i n g ) 、a s ( a 伍m t ys c h e d u l i n g ) 、s s s ( s a f es e l fs c h e d u l i n g ) 和a a s ( a d a p t a f f i n i t ys c h e d u l i n g ) 等。从任务队列的组织形式上可以把上面介绍的 动态调度算法分为两类：基于集中队列的算法和基于分布队列的算法。在基于集 中队列的算法( 如s s 、b s s 、g s s 、f s 、t s s 、s s s ) 中，每个处理器互斥地从集 中任务队列中取出任务。a s 和a s s 采用分布式队列来管理任务。 由于问题的复杂性，目前很多研究对任务调度模型进行了适当修改，比如文 献 1 6 1 7 ，1 1 3 将任务限定为相同大小、以追求吞吐量的稳态( s t e a d ys t a t e ) 为调度目 标；文献 1 1 2 】的调度目为最大化处理机的最小负载；文献 1 1 4 】将基本的 m a s t e r s l a v e 模式推广到分布式模式；文献 1 1 6 考虑了主存空间大小。 独立任务调度在网格中应用的主要困难是资源的动态性和异构性。对于异构 性的研究已经很多了，然而对于动态性的研究还很不足。由于多管理域的资源可 能动态地加入和退出，但是网格调度器又不能干扰本地调度器的工作，所以无法 得到全局状态信息，从而导致无法进行较好地调度。目前g g f 正在考虑采用提前 预留的方法解决动态性问题，它的思想来源于网络中的资源预留。 1 2 2 3 依赖任务调度 具有依赖优先关系的任务通常用有向无环图( d a g ) 来表示，文献【1 1 7 1 4 7 给 出了部分有代表性的研究工作。 文献 1 1 7 全面总结了d a g 调度问题，它提出一种d a g 算法分类方法，并对 几十种调度算法进行了详细介绍和对比。由于各种算法通常基于不同的模型假设， 文献 1 1 8 提出一套基准测试集，并对1 5 种重要的调度算法进行了测试对比。文献 【1 1 9 1 2 0 对列表调度算法的复杂性进行了分析，对处理机和任务的选择问题提出 了快速算法。文献 1 2 1 提出基于d a g 图解和同构的方法解决机群中的调度问题， 文献 1 2 2 给出一种局部搜索算法。 大多数调度算法基于古典的列表调度思想。列表调度的主要工作在于为处理 机赋予优先级，然后逐个地为任务选择处理机。优先级存在静态优先级和动态优 先级两种，多数算法采用静态优先级【l r 7 1 。文献 1 2 3 1 2 5 给出了基于关键路径构造 优先级列表的算法。 文献 1 2 5 1 3 3 。1 3 7 1 3 8 考虑了计算平台的异构性。多数算法考虑异构性时仅仅 将同构系统中任务的执行时间和通信开销替换成任务的平均执行时间和平均通信 开销【1 2 1 2 7 1 ，文献 1 2 8 采用任务执行时间标准差，文献 1 2 9 1 3 0 不仅考虑了通信延 9 电子科技大学博士学位论文 迟，还考虑了计算延迟，文献 1 3 1 考虑了计算时间的不确定性。文献 1 3 2 - 1 3 3 将 d a g 划分为若干个独立任务集合，然后采用独立任务调度中的m i n m i n 等算法对 各个独立任务集进行调度。 为消除通信开销的影响，部分算法采用了基于复制的技术【1 3 4 3 引。基于复制的 算法可能在较低的复杂度下得到问题的最优解，但可能需要较大的存储空间；部 分算法还采用遗传算法、模拟退火等随机算法来解决调度问题【1 3 9 d 删。遗传算法的 主要优点在于可能得到全局最优，但其选择过程存在随机性，不能确保得到最优 解，同时计算开销也相当大。 早期的d a g 调度模型中很多假设是不现实的，如同构计算平台、任务间无通 信开销、通信无竞争、处理机全互连等，文献 1 4 2 1 4 5 研究更现实的任务调度问 题，主要考虑了异构性和通信竞争。 通过对任务模型的不同假设，已经得到了多种不同的算法，而且还将得到更 多的调度算法，例如，文献 1 4 6 开始研究多个d a g 的调度问题，文献 1 4 7 采用 多个目标函数。 1 2 3 发展趋势 未来应用对于任务调度算法的需求是不容置疑的：我国2 0 0 6 年度国家自然科 学基金立项了重大项目“当代并行机的并行算法应用基础研究”和3 0 余项与任务 调度直接相关的自由申请项目；8 6 3 计划立项了重大专项“高性能计算机及网格服 务环境 ；9 7 3 计划更是将“新型计算机系统的体系结构、算法及其支撑软件的基 础研究 和“大规模、高速、高性能信息网络的基础研究 等作为十五后三年的 重点研究方向。 目前非常明确的发展趋势是研究并提出“更现实 的任务调度模型以及基于 更现实任务调度模型的任务调度算法。最近几年涉及到网格计算、高性能计算和 并行计算的主要学术会议，例如i p d p s 、i c p p 、h i p c 、c c g r i d 等都设立更实际模 型下的计算技术研究主题。i e e et r a m o np a r a l l e l & d i s t r i b u t e ds y s t e m 在2 0 0 6 年 2 月出版专辑的主题就是：异构集群( 现实平台模型) 的算法设计和调度技术。 由于问题的复杂性，未来的研究将在更实际模型假设和问题可求解性之间进 行更好地折衷。在模型方面，考虑资源的异构、分布、竞争和动态共享等将是迈 向更实际模型的第一步；在算法方面，将会基于新的调度模型提出新的调度算法， 并着手解决实际应用问题。 1 0 第一章绪论 1 3 研究内容和主要工作 1 3 1 研究内容 任务调度问题是网格计算的关键问题之一，它直接决定了网格资源是否得到 有效而合理的使用。本文对网格计算中的任务调度模型和任务调度算法进行了研 究，主要包括如下四个方面： ( 一) 更现实的任务调度模型 研究现有任务调度算法涉及的各种模型假设，并对其整理、归纳、分类；对 更现实任务调度模型的各种指标进行分析和讨论，探讨如何在任务调度模型的精 确性和简单性之间取得平衡，期望提出更现实的任务模型。 ( - - ) 可分任务调度问题 研究可分任务的优化调度问题。对现有可分任务调度问题相关文献资料进行 全面搜集、阅读和理解；研究适合大规模可分应用调度的更现实的任务调度模型， 并基于此模型研究相应的调度算法；研究更现实模型下的大规模可分应用的多趟 调度优化问题；研究任意网络拓扑环境中的可分应用优化调度问题。 ( 三) 独立任务调度问题 研究独立任务的优化调度问题。对现有独立任务调度算法进行总结、分析和 讨论；研究现有独立任务调度算法的各种性质和特点，特别是各种基于m i n m i i l 的系列调度算法；研究并提出新的独立任务调度算法。 ( 四) 依赖任务调度问题 研究任务之间具有依赖关系的应用的优化调度问题，以缩短应用的完成时间 为主要目标。由于绝大部分依赖任务调度问题采用基于列表的调度算法，而列表 调度算法需要解决任务优先级构造和处理机选择这两个问题，因此这部分的研究 重点在于：如何构造对于完成时间更加有效的优先级列表；如何将列表中的任务 快速地调度到其具有最早启动时间的处理机。 1 3 2 主要工作 论文对网格计算中的任务调度问题进行了深入研究，是作者部分研究成果的 总结，主要工作为如下四个方面： 电子科技大学博士学位论文 ( 一) 更现实的任务调度模型研究 对现有任务调度模型进行了分析和总结，研究了“更现实的 任务调度模型。 从任务调度模型、计算平台模型和性能指标模型三个方面对现有任务调度模型进 行了讨论，对模型参数的现实性和简单性之间的折衷进行了探讨，特别是在模型 的异构性和共享性方面进行了深入研究。这些工作将有助于研究更现实的网格任 务调度模型，从而更加有效地实现网格理想。 ( 二) 可分任务调度算法 在可分任务调度算法方面，对现有可分任务调度问题相关文献资料进行了全 面搜集、阅读和理解，在如下三个方面取得了成果。 第一，针对大规模计算问题，引入了带启动开销的非阻塞通信模型，并基于 此模型解决了可分任务调度涉及的处理机选择、任务调度顺序、任务分割与分发 等优化问题，得到了大规模可分应用的优化调度算法。由于该模型能更实际地表 达网格计算平台，因此该研究结果不仅具有一定的理论意义，同时也具有一定的 实用价值。 第二，针对大规模应用的计算问题，研究了可分任务的多趟调度问题。在通 信具有启动开销的更实际模型下，提出了简单易行的周期性任务调度算法，并给 出了同构环境的各种参数优化取值，得到包括调度趟数、应用完成时间、处理机 个数等调度参数的优化解析表达式。 第三，研究了任意网络拓扑中的可分任务调度问题。提出两类启发式任务调 度算法：s c f l f 和b f s f l f ，其中s c f l f 算法优于基于最小生成树和基于广度优 先生成树的算法。 ( 三) 独立任务调度算法 在独立任务调度算法方面，分别从任务的异构性和平台的异构性共四种组合 进行了研究，取得了如下研究成果： 第一，研究了同构计算平台的独立任务调度问题。对于异构任务，提出了基 于局部搜索的任务调度算法，该算法在重载处理机和轻载处理机之间进行任务交 换，得到了更好的调度质量。 第二，在异构平台的同构任务调度中，借鉴了带记忆功能的动态规划算法思 想，提出了一个改进的任务调度算法，它对每一个调度实例仅需计算一次，因此 大大加快了调度速度。 1 2 第一章绪论 第三，对于异构