（计算机软件与理论专业论文）并行异构系统任务调度问题研究.pdf

中国科学技术大学硕士学位论文 并行异构系统任务调度问题研究 摘要 并行分布计算是当前计算机科学的热点之一。而并行系统中的任务调度算法是 影响分布式计算效率的关键因素，也是一个具有挑战性的课题。并行系统中任务调 度是指把一个应用中有先后关系的任务合理地分配到并行机的处理器上，使得整个 应用完成时间最短。已经证明，这是一个n p 难的问题，现阶段主要的研究是提出 近似算法，提高调度的效率。本文研究了并行异构系统中的任务调度问题，在经典 的任务模型和有通信冲突的模型上分别提出了新的算法。本文的主要贡献包括： ( 1 ) 经典模型上的任务调度算法 本文调研了现有的任务调度算法，在经典的并行异构环境任务调度模型上，对 已有的基于任务复制的排序调度算法进行改进，改变了任务复制的策略，并且引入 了区间插入的概念，设计出新的任务调度算法，并且通过模拟程序对算法的性能进 行测试，新算法的性能比已有算法有了明显提高。 ( 2 ) 有通信冲突模型上的任务调度算法 考虑到有通信冲突模型的自身特点，本文在现有的有通信冲突模型算法中引入 任务复制的方法，从而设计出更有效的新算法，通过模拟程序产生随机任务图和高 斯迭代任务图，快速傅立叶变换任务图，将新算法与现有的算法相比，新算法的平 均性能比已有算法提高了2 9 以上。 本文主要内容为：任务调度的背景介绍，包括并行计算，一般情况下的调度问 题，主要解决办法；并行异构环境下调度问题的模型和研究现状；经典任务调度模 型下的任务调度算法研究；有通信冲突的并行异构环境下的任务调度算法研究；以 后的研究方向。 关键词：任务调度，异构系统，启发式算法，通信冲突，任务复制。 a b s t r a c t n o w ，p a r a l l e la n dd i s t r i b u t e dc o m p u t i n gi sah o ts p o ti n c o m p u t e rs c i e n c e e f f i c i e n t a p p l l c a t l o ns c h e d u l i n ga l g o r i t h mi sc r i t i c a lf o ra c h i e v i n gh i g hp e r f o r m a n c ei nd i s t r i b u t e d c o m p u t i n ge n v l 。o n m e n t ，m e a n w h i l e ，i ti saq u i t ec h a l l e n g ep r o b l e m t h ea p d l i c a t i o n s c n e d u “n gp r o b l e mh a sb e e ns h o w nt ob en p - c o m p l e t e r e c e n t l y , t h i sp r o b l e mh a sb e e n e x t e n s l v e l ys t u d i e da n dv a r i o u sh e u r i s t i c sh a v eb e e np r o p o s e d i nt h i sp a p e r ，w ef o c u so n t a s k s c h e d u l i n gp r o b l e mo np a r a l l e l h e t e r o g e n e o u ss y s t e m ，a n dw ep r o p o s a ln o v ej a i g o n t h m so nb o t ht h ec l a s s i cp r o b l e mm o d e la n dc o m m u n i c a t i o nc o n t e n t i o n a w a r e m o d e l e s p e c t i v e l y b e l o ww eg i v ea 。b r i e fd e s c r i p t i o no f m a j o rc o n t r i b u t i o n si nt h ep a p e r ( 1 ) t a s k s c h e d u l i n ga l g o r i t h mo nc l a s s i cm o d e l a8 e r l e 8o fc u ”e n tt a s ks c h e d u l i n ga l g o r i t h m sa r e i n t r o d u c e d ，a na l g o r i t h mb a s e do n t a s kd u p i i c a t l o nw a si m p r o v e d w ec h a n g e dt h et a s k s c h e d u l i n gs t r a t e g y ， a n da d da s e c t l o n1 n s e t l o n s t e p t ot h ea l g o r i t h m b a s e do nt h es i m u l a t i o n p r o g r a m ，t h en e w a l g o r i t h mh a sm a d es u b s t a n t i a li m p r o v e m e n to np e r f o r n l a n c e ( 2 ) t a s ks c h e d u l i n ga l g o r i t h mo nc o m m u n i c a t i o n c o n t e n t i o na w a r em o d e l c o n 8 1 d e m gt h ec h a r a c t e r i s t i co fc o m m u n i c a t i o nc o n t e n t i o na w a r em o d e l ，w eu s e d t a s kd u p l i c a t i o nm e t h o do nt h i sn e w m o d e la n d d e s i g n e dan e wt a s ks c h e d u l i n ga i g o r i t h m l na d d i t i o n ，w ee v a l u a t e dt h en e w a l g o r i t h mo nt h i sm o d e lo nr a n d o m l yg e n e r a t e dt a s k g 。a p h sa n dg a u s s i a ne l i m i n a t i o nt a s kg r a p h s t h en e w a l g o r i t h mo u t - p e r f o r m e de x i s t i n g a l g o r i t h mb ya tl e a s t2 9 o ns i m u l a t i o n 。 t h em a i nc o n t e n to ft h i s p a p e ra r e ：b a c k g r o u n di n t r o d u c t i o n o ft a s ks c h e d u l i n g 1 n c j u d l n gp a r a l l e lc o m p u t i n g ，s c h e d u l i n gp r o b l e mi nn o r m a lc a s ea n dt h em a i ns o l u t i o n ： t h em o d e lo f t a s ks c h e d u l i n gi np a r a ll e l h e t e r o g e n e o u ss y s t e m sa n di t sr e s e a r c h a c h i e v e m e n t ；r e s e a r c ho ft a s k s c h e d u l i n ga l g o r i t h m si nt h ec l a s s i cm o d e l ：t a s k s c h e d u l l n g 引g o r i t h m sr e s e a r c hi nc o m m u n i c a t i o nc o n t e n t i o n a w a r em o d e la n dt h e d i r e c t i o no ff u t u r ew o r k s k e yw o r d s ：t a s ks c h e d u l i n g ，h e t e r o g e n e o u ss y s t e m ，h e u r i s t i c s ，c o m m u n i c a t i o n c o n t e n t i o na w a r e ，t a s kd u p l i c a t i o n 中国科学技术大学硕士学位论文并行异构系统任务调度问题研究 第1 章绪论 本章摘要：并行计算是在并行计算机或者分布式计算机等高性能计算系统上所 做的超级计算，是为了解决大规模、大数据量的大型计算而正在蓬勃发展的一门学 科，而并行系统上的任务调度问题是并行于分布式计算领域中的最基本且最具有挑 战性的问题之一。本章首先阐述了并行计算及并行任务调度基本概念，并行系统上 任务调度的一些基本问题和研究方法；然后提出了本文的研究内容，并综述了文中 取得的研究成果；最后给出了本文的梗概。 1 1 研究背景： 现代计算机时代从1 9 4 5 年开始到现在，经历了半个多世纪。从8 0 年代开始，微 处理器技术有了巨大的发展，处理器的时钟频率从大约4 0 m h z 增加到超过3 g h z ，同 时处理器能够在一个时钟周期里执行多条指令，这使得处理器的峰值浮点运算执行 速度增加了几个数量级。但是，这还是不能满足人们日益增加的对计算速度的需求， 随着高速有效的局域网的发展，人们可以通过网络把许多处理单元连接起来构成一 个计算系统，这种系统通常被称为并行系统或者分布式系统，现在，并行分布式系 统的研究已经成为计算机领域研究的热点。 1 1 1 并行计算 并行计算【1 】( p a r a l l e lc o m p u t i n g ) ，简单地讲，就是在并行计算机上所做的 计算，它和常说的高性能计算、超级计算是同义词，因为任何高性能计算和超级计 算总离不开使用并行技术。随着计算机和计算方法的飞速发展，几乎所有的学科都 走向定量化和精确化，从而产生了一系列诸如计算物理、计算化学、计算生物学、 计算地质学和计算材料学等的计算科学，在世界上逐渐形成了- f 计算性的学科分 支，即计算科学与工程，简称为c s e ( c o m p u t a t i o n a ls c i e n c e & e n g i n e e r i n g ) 。如今， 中国科学技术大学硕士学位论文并行异构系统任务调度问题研究 计算科学已经和传统的两种科学，即理论科学和试验科学，并列成为第三门科学， 它们彼此相辅相成地推动科学发展和社会进步。在许多情况下，或者是理论模型复 杂甚至理论尚未建立，或者实验费用昂贵甚至试验无法进行，此时计算就成为求解 问题的唯一或主要手段。计算极大地增强了人们从事科学研究的能力，大大地加速 了把科技转化为牛产力的过程，深刻地改变着人类认识世界和改造世界的能力。 然而，设计一个高效的并行算法并非易事，其过程比较复杂，很难归结为一个 单一的过程而一步到位，往往需要几经反复才能达到要求。一般情况下，并行算法 的设计可分为四步：即任务划分( p a r t i t i o n i n g ) 、通信( c o m m u n i c a t i o n ) 分析、任 务组合( a g g l o m e r a t i o n ) 和处理器映射( m a p p i n g ) ，简称为p c a m1 2 1 设计过程， 它是种设计方法学，是实际设计并行算法的自然过程，其基本要点是：首先尽量 开拓算法的并发行和满足算法的可扩放行：然后着重优化算法的通信成本和全局执 行时间，同时通过必要的整个过程的反复回溯，以期达到一个满意的设计选择。该 设计过程的最后阶段时映射，也就是将经过优化的各进程指派给具体的处理器去执 行。p c a m 设计方法的各阶段可简述如下： 划分：所谓划分，就是使用域分解或功能分解的办法将原计算问题分割成一些 小的计算任务，以充分揭示并行执行的机会，这犹如细小的沙粒比大块的砖瓦易于 灌注样，划分以充分开拓算法的并发性和可扩放性为目的，其方法是先做数据的 分解( 称为域分解) ，然后是计算功能的分解( 称为功能分解) ，两者互为补充； 划分的要点是力图避免数据和计算的复制，应使数据集和计算集互不相交。 通信：由划分所产生的诸并行执行的任务，一般而言都不能完全独立执行，一 个任务中的计算可能需要用到另一个任务中的数据，从而就产生了通信要求。所谓 通信，就是为了进行并行计算，诸任务之间就所需进行的数据传输。在讨论通信时， 可将通信分为以下四种模式： 局部全局通信：局部通信时，每个任务只与较少的几个近邻通信；全局通 信中，每个任务与很多别的任务通信。 结构化非结构化通信：结构化通信时，一个任务和其近邻形成规整结构； 非结构化通信中，通信网则可能是任意图。 静态动态通信：静态通信，通信伙伴的身份不随时间改变，动态通信中， 中国科学技术大学硕士学位论文 并行异构系统任务调度问题研究 通信伙伴的身份则可能由运行时所计算的数据决定且是可变的。 同步异步通信：同步通信中，接收方和发送方协同操作；异步通信中，接 收方获取数据无需与发送方协同。 组合：在划分和通信阶段，由于没有考虑算法在特定并行机上的执行效率，所 得到的算法仍然是抽象的，在组合阶段，将从抽象到具体，即重新考察在划分和通 信阶段所作的抉择，力图得到一个在某一类并行机上能有效执行的并行算法。组合 的目的是通过合并小尺寸的任务来减少任务数，但它仍可能多于处理器的数目，理 想的情况是：在组合时就将任务数减少到恰好和处理器数目相同，从而得到一个 s p m d 的程序，这样映射工作也宣告完成；另外，组合时我们也要考虑是否值得进 行数据和或计算的重复。 映射：在设计的最后阶段，我们要指定每个任务到哪里去执行，此即映射 ( m a p p i n g ) 。映射的主要目的是减少算法的总的执行时间，其策略有二：一是把 那些能够并发执行的任务放在不同的处理器上以增强并行度；二是把那些需频繁通 信的任务置于同一个处理器上以提高局部性。这两种策略有时会冲突，这就需要权 衡。在进行映射时，对于许多用域分解技术开发的算法，有固定数目的等尺寸任务， 有结构化全局通信，此时映射很简单；对于更复杂的域分解算法，每个任务的工作 量可能不一样，通信也许是非结构化的，有效地组合就不那么容易，此时可能要采 用负载平衡的办法。在基于功能分解的算法中，常常会产生一些有短暂任务组成的 计算，它们只在执行与结束时需与别的任务协调，此时我们可以用任务调度算法来 分配任务给那些可能处于空闲的处理器。 1 2 并行任务调度 并行系统上的任务调度问题是并行算法和应用研究中的一个关键问题，有效地 解决该问题可以大幅度地提高并行系统的利用率，同时也可以降低单独应用的执行 时间。下面介绍并行任务调度的一些背景和概念。 中国科学技术大学硕士学位论文并行异构系统任务调度问题研究 1 2 1 调度问题的一般模型 调度问题在不同的领域有许多不同的描述方法，生产管理中的生产作业安排问 题就是一个最为经典的调度问题【3 】。一般地，构成调度问题的基本元素有三个， 即资源集、消费者集及这些资源为这些消费者服务所依据的一定规则。调度问题就 是在满足资源集和消费者集约束条件的基础上，设计一个有效的调度系统来管理消 费者如何高效地使用这些资源，并使得一些体统性能指标达到最优或近似最优，它 的一般模型如图1 1 所示。 _ _ 1 _ 。_ _ 一_ r 消费 l ( 并行应 l j u 、 , 1 - - 3 ，飞 、 ，调度程序 、。 图1 1 调度问题的一般模型 组成一个并行程序的子任务、多用户系统下的作业、工厂中的生产作业或银行 中的顾客相当于消费者，并行分布系统中的处理单元、工厂中的机器或银行中的出 纳相当于资源。调度规则和策略多种多样，其中先来先服务是一个典型的调度策略， 但它只适合与某些情形，如银行服务可以使用，但未必适用于工厂车间中的生产作 业。 调度性能和调度效率是评价一个调度系统优劣程度的两个方面，每个调度问题 都有自己特定的一些性能测试指标( 有时也称为系统性能指标) ，如生产车间的产品 产量、并行分布计算中的一个并行应用程序的执行时间、多用户系统下作业的平均 响应时间或系统吞吐率等，作为调度系统，它的目标就是要尽量优化这些指标。调 度性能也就是通过这些指标的取值来反映，它直接体现了调度结果的好坏。例如， 如果把并行应用程序的执行时间长度作为性能指标，那么能产生较短执行时间的调 度系统较优。调度效率只要指调度系统本身的复杂度，如果两个不同的调度系统产 生相同的调度结果，那么复杂度小，简单明了的调度系统较优。在并行分布计算中， 调度系统的复杂度主要是指调度算法的时间复杂度，调度问题一般都有n p 完全难 度【4 ，5 】，各种取得最优或者近似最优的调度算法必须具有多项式时间复杂度时， ， q 统 | | 集繇 渊沛 继鼢 一 肼 l u n 、尽， 中国科学技术大学硕士学位论文并行异构系统任务调度问题研究 才是有效的调度算法。 1 2 2 并行计算中的任务调度 并行分布计算中的任务调度问题就是根据一定的调度规则和调度策略，把组成 并行程序的一组任务或构成工作负载的一组作业，按照一定执行时序分配到并行分 布系统的多个计算节点上，以期取得较好的系统执行性能【6 】。目前许多基于并行 分布处理的高性能计算中心的计算坏境是由多种并行机或网络工作站机群系统构成 的异构多应用系统，并且某些并行机的内部计算节点也可能是异构的( 如p a r a g o n 系统中有些节点的内存为1 6 m b ，有些节点的内存为3 2 m b ；或者有些节点为单c p u ， 有些节点为双c p u ) ，这时不同的应用层次对任务调度有不同的要求。下面就从作 业调度、任务划分与一般任务调度概念的区别出发，介绍并行分布计算中的任务调 度问题。 1 任务调度与作业调度 般地，按照不同的应用层次，并行分布计算中的调度问题可以分为两大类： 任务层调度和作业层调度，虽然有时把它们两者统称为并行分布计算中的任务调度 问题，但两者的调度着眼点( 或调度对象) 不同，前者主要针对某个用户的单一并 行应用程序构成的一组任务( 子任务) ，而后者主要针对若干个用户的多个并行应用 程序构成的一组作业，所以它们的调度策略及系统性能评价指标均有很大差别。在 此，我们把前者简称为任务调度，把后者简称为作业调度，一个并行应用程序相当 于一个作业，一个作业由多个任务组成，整个系统负载由若干个用户作业组成。 任务调度所面向的一般是单应用程序系统，它的调度实体是任务，调度目标一 般就是求得某个作业的最短执行时间。任务调度必须了解该作业的具体结构，如以 任务图形式表示的结构信息；它所考虑的问题也要具体些，如任务分解，任务间的 优先关系以及任务聚类等。作业调度所面向的一般是多应用程序系统，它的调度实 体是传统批处拌意义下的作业，即把每个作业作为一个调度单位，这时调度程序一 般不太了解作业的具体结构信息，它的调度目标有很多，如最短的平均作业响应时 间，最大的资源利用率或最大的系统吞吐率等，这些不同的调度目标有时是相互冲 中国科学技术大学硕士学位论文并行异构系统任务调度问题研究 突的。 从用户角度出发，每个用户关心的是自己的作业能否在较短的时间内得以完成， 他们比较注重的是构成自己作业的多个任务之间的任务调度策略，并且比较倾向于 同构的计算环境，即每个节点的性质( 包括处理速度，内存大小等) 相同。从系统 角度出发，它更关心的是如何通过有效的作业调度方案，获得整个计算资源与不同 用户作业的多种资源需求之间的最佳匹配，从而提高整个并行系统的执行性能。 事实上，作业调度是任务调度的一种特殊形式，这是因为一个作业的所有进程 可以组合成一个任务，另外，调度相互独立的一组任务也可视作为作业调度。 2 任务调度与任务划分 目前许多文献把任务调度与任务划分这两个术语互用，虽然在并行分布计算中 的任务划分是任务调度的一种特殊形式，但对两者不加区别有时会带来误解。 一般来说，在分布系统中一组任务相互间发生关系得方式有多种多样，其中有 一种是通信关系，在此情况下，如果两个任务被分配到不同的处理器上，那么就产 生以通信成本形式表示的通信开销，反之，如果两个任务被分配到相同的处理器上， 那么就不产牛任何的通信开销，我们把这种特殊的任务调度称作任务划分。 对于任务划分，通常用任务作用图t i g ( t a s ki n t e r a c t i o ng r a p h ) 来表示并行应 用程序模型，其中t i g 中的节点表示任务，当且仅当两个任务节点间相互作用时， t i g 中的这两个节点间存在一条无向边。因此，进行任务划分的一组任务不需要指 定各任务之间的执行次序，也就是说，任务之间相互作用时不存在优先关系，而丰 要考虑如何把各个任务分配到合适的处理器上。另外，任务划分所面向的分布系统 一般是异构的，即各处理器的执行性能不同。 对于任务调度，通常用带权有向图( w e i g h t e dd i r e c tg r a p h ) 来表示并行程序模 型，任务间相互作用所发生的关系是优先关系，调度这些任务有时也称为优先的约 束调度( p r i o r i t yc o n s t r a i n ts c h e d u l i n g ) 。任务调度问题除了考虑每个任务的执行处 理器外，还必须考虑每个任务的执行时序，因为每个任务只有当比它优先级高的所 有任务执行完毕后，才有可能开始执行。 中国科学技术大学硕士学位论文 并行异构系统任务调度问题研究 1 2 3 并行计算中任务调度的分类 任务调度问题是并行分布计算中最为基本的一个问题，它涉及到并行分布计算 环境及实际并行应用程序的各个方面，因此，它从各个不同侧面影响着并行程序的 设计及并行分步计算环境的整个系统执行性能。从不同的角度出发，并行分布计算 中的任务调度问题有不同的分类方法【7 】，下面所述的各种分类方法同时也比较全 面地反映了设计一个任务调度算法时需要考虑的各种因素。 静态调度、动态调度和混合调度 按照何时决定每个任务的执行处理器号，并行分布计算中的任务调度方法主要 可分为静态调度、动态调度和混合调度这三类。静态调度( s t a t i cs c h e d u l i n g ) 是指 在并行程序编译时，就决定每个任务的执行处理器及执行顺序，它经常用于任务图 比较确定的情况。而动态调度( d y n a m i cs c h e d u l i n g ) 则是在并行程序运行过程中， 根据当前任务调度及系统运行情况，临时决定每个任务的执行处理器及起始执行时 刻。动态调度丰要用于任务图不确定的情况下，但它不可避免地会带来额外的开销。 混合调度( h y b r i ds c h e d u l i n g ) 是介于静态调度和动态调度两者之间的调度方法， 它在编译时先静态调度部分任务，而剩余部分则采用动态调度方法在系统运行时来 给它们分配处理器。 最优调度和启发式调度 按照调度目标的实现要求来划分，并行分布计算中的任务调度可分为最优调度 ( o p t i m a ls c h e d u l i n g ) 和近似最优调度( s u b - o p t i m a ls c h e d u l i n g ) ，后者也经常被称 为启发式调度( h e u r i s t i cs c h e d u l i n g ) 。最优调度一般是指静态调度，如果一个调度 算法能在多项式复杂度的时间内获得最佳调度结果，那么称之为有效的最优调度算 法。但是，只有在极少数情况下才存在有效的最优调度算法，大部分最优调度算法 所需的执行时间随任务数或处理器数的增加而成指数增长。因此，经常采用启发式 任务调度方法来把各任务调度分配到各处理器上，它虽然不能确保获得最优解，但 可以获得最优调度的近似解。 中国科学技术大学硕士学位论文并行异构系统任务调度问题研究 共享存储结构调度和分布存储结构调度 按照并行分布计算模型的存储器结构，主要可分为基于共享存储的任务调度和 基于分布存储结构的任务调度这两大类。在共享存储( s h a r e dm e m o r y ) 的计算模型 上进行任务调度时，一般不需要考虑通信延迟，这时任务调度的着重点在于如何最 大限度地获得并行程序任务间的并行性。而在分布存储( d i s t r i b u t e dm e m o r y ) 的计 算模型上进行任务调度时，通信延迟的存在使得任务调度更为复杂，如果无视通信 延迟的存在，而只考虑尽量增大并行执行时间，那么有可能在较多处理器上的执行 效率还不如在较少的处理器上的执行效率；同样，如果没有完全开发任务之间的并 行性，那么并行系统中处理器就没有得到充分利用，因此，调度程序必须在尽可能 利用各任务之间的并行性和尽量减少通信开销之间进行折衷。 集中式调度和分布式调度 按照调度程序的结构或调度程序所收集调度信息的范围，并行分布计算中的任 务调度方法可划分为集中式调度和分布式调度两大类。在集中式调度( c e n t r a l i z e d s c h e d u l i n g ) 方法中，由一个叫做中心调度器的处理器来收集全局调度信息，其他处 理器把它们的状态信息传送给中心调度器，并由中心调度器做出调度决定。而分布 式调度( d i s t r i b u t e ds c h e d u l i n g ) 则是由各自处理单元的调度程序根据局部范围内的 一些调度信息来进行任务调度，它的最大优点在于具有良好的可扩放性。集中式调 度的主要优点在于实现比较简单，但在节点数较多的大规模并行分布系统中，由于 各节点与调度服务器的通信成为瓶颈，所以调度开销比较大。分布式调度一般都是 动态的。 抢占式调度和非抢占式调度 按照调度程序执行调度操作时是否允许任务抢占执行，可分为抢占式调度 ( p r e e m p t i v es c h e d u l i n g ) 和非抢占式调度( n o n - p r e e m p t i v es c h e d u l i n g ) 。如果一个 任务一旦占有处理单元，它就不能被中断执行，而是必须一直运行完毕后才释放该 处理器，这种情形即为非抢占式方式；相反，如果允许任务被中断执行而把它所有 的处理单元让给其他任务执行，这种情形即为抢占执行方式，当然这必须假定被抢 占任务最终还能获得它所要求的执行时间。由于抢占式执行方式所引起的环境切换 会增加系统开销，所以一般情况下不常采用，用的较多的地方还是以分时方式实现 中国科学技术大学硕士学位论文并行异构系统任务调度问题研究 的群调度( g a n gs c h e d u l i n g ) ，有时也称为联合调度( c o s c h e d u l i n g ) 方案中。与抢 占执行调度操作类似的还有任务是否允许迁移执行，一般地，编译时对任务进行的 处理器分配方式有时也被称为初始分配，如果应用程序任务启动执行后，某些任务 可以重新移到其他处理器上执行，这也是可抢占执行方式的一种形式。 自适应调度和非自适应调度 按照调度程序的调度策略是否随系统状态信息变换而自动调整，并行分布计算 中的任务调度可分为自适应调度和非自适应调度这两大类。自适应调度的基本思想 就是根据调度程序在以前一段时间内的执行效果，以及当前系统状态信息( 主要包 括系统资源和任务负载情况) 自动修正调度程序的执行机制，由于它们是通过收集 当前系统状态信息来动态修正调度策略，所以一般都是动态的。而非自适应调度方 法则一旦确定任务调度算法的调度策略，那么在并行执行过程中就固定地按照这些 调度策略来进行任务调度，即使某些不确定因素( 如动态产生的任务) 使得调度效 率比较低，那么也必须等到非执行状态时，再来修正调度策略。 1 3 研究内容及主要成果 本文研究了在经典的并行任务调度模型和考虑通信冲突的调度模型上的基于排 序调度的任务调度算法，在两个调度模型上都提出了新的调度算法，改进了现有的 结果。这些结果从调度算法的实际应用的角度具有一定的意义。 ( 1 ) 经典模型上的任务调度问题：在该模型上，任务用带权的有向无环图表 示，并行计算平台为全相连的处理器。我们分析了现有的几种调度算法 的特点，提出了新的调度算法，在算法在执行性能上比现有的算法有了 较大的改进。 ( 2 ) 有通信冲突的任务调度问题：该模型与经典模型相似，但是，在该模型 上处理器在任意时刻都只能和一个处理器进行通信，它更能准确地反映 某些特定的并行机的特点。在该模型上，我们同样提出了新的调度算法， 在不增加任务复杂度的基础上，极大地提高了调度算法的性能。 中国科学技术大学硕士学住论文 并行异构系统任务调度问题研究 1 4 论文的组织 我们将按照研究内容的先后次序进行论文的撰写和安排，全文共5 章，各章节 的内容安排如下： 第一章：绪论首先给出了任务调度问题研究的背景，然后介绍了一些基本概念 和调度问题的基本分类，接着介绍了整个论文所做的工作，最后给出了全篇论文的 组织结构。 第二章：模型和研究现状。首先介绍了并行任务调度的模型的一般表示方法， 给出了静态调度的n p 完全性介绍，最后介绍了常用的启发式调度的方法。 第三章：并行异构环境下的任务调度。主要介绍了经典模型下的任务调度，首 先介绍了经典的任务调度模型，然后给出了一些已经出现过的任务调度算法，接着 给出了我们新提出来的经典模型下的任务调度算法，最后给出了新算法与已有算法 的性能对比。 第四章：有通信冲突环境下的任务调度。首先介绍了本章所采用的用通信冲突 的任务调度的模型，然后证明了在任务图是f o r k 图时该问题的n p 完全性，接着在 该模型上提出了新的调度算法，最后给出了新算法与已有算法的性能对比。 第五章：总结全文。综述全文的研究内容和研究方法，对于未来研究工作的安 排和展望。 中国科学技术大学硕士学位论文并行异构系统任务调度问题研究 第2 章模型和研究现状 本章摘要：分布式和并行系统上的任务调度是并行分布式计算中最为基本的一个问 题。本章主要介绍并行计算中任务调度的模型，静态任务调度的复杂性分析和解决 任务调度问题的一些近似方法。 2 1 并行计算中的任务调度模型 在研究分布式计算中调度问题的过程中，我们需要把该问题从实际的并行程序 和并行机中抽象出来，抽象出来的结果就是并行计算中的任务调度模型。它主要包 括以下几个部分： 。 1 应用程序任务 一个并行应用程序的性质可用四元组似， 0 ) 表示任务a 。 传送给任务a j 的数据量；w = w ( a o ) ，其中w 向) 表示任务a ，的工作负载的大小， 在同构的并行分布系统中，由于每个节点的计算能力( 包括运算速度、内存大小等) 相同，所以也可以直接用w 向) 的执行成本，而在异构的并行分布计算环境下，相 同负载在不同节点行的执行成本也是不同的；“ ”定义了任务间的的偏序关系， “a ， a j ”表示任务a j 的执行依赖于任务口，的执行。 在并行分布计算中，偏序关系“ ”一般用任务图g 三( k 目来表示，其中 睁 a l ，a 2 ，a 。) 为表示n 个任务的有权节点，任务a r 的工作负载w 向为该节点的权 重；庐 向。矽j 回”为表示任务间通信关系的带权有向边集，任务a ，与a j 之间 的通信量办为这些有向边的权。i m p ( a r ) = a ki ( a k , 口i ) e e ) 表示任务图中节点a 。的 直接前驱集，i m s ( a j ) = 吼i ( a k ) e e 表示任务图a j 中节点的直接后继集。如果 i m p ( a i ) = d p 那么节点讲称为入口节点；如果i m s ( a j ) = d p ，那么节点a j 称为出口节点。 用p a t h ( a , q ) 表示g 中节点a r 到节点a j 的一条路径，它本身就是包含节点a ，和节点 a j 在内的该条路径上所有节点集合。在后面的讨论中，节点和任务是可以互用的， 中国科学技术大学硕士学位论文并行异构系统任务调度问题研究 并且有时直接用任务节点下标来表示任务。 2 目标机器 一般地，目标机器假定有m 个处理单元组成，该m 个处理单元可以是同构的， 也可以是异构的，它们通过任意的互联网络进行连接。每个处理器某一时刻只能处 理一个任务，每个任务可在任何一个处理器上运行。一般地，可用6 元组 t m = ( p ， 尸c ，】， 剐， 明，【b 小 r 扩】) 来刻画目标机器的特征： 尸= 尸l ，p 2 ，p m 为构成并行分布系统的一组处理器 【尸 ，】为m m 的互连网络拓扑矩阵 s ( 1 s i s m ) 为处理器尸f 的执行速度 i i ( 1 i s m ) 表示在处理器只上启动一个消息所需的时间 b ，( 1 s f 蜘) 表示在处理器p ，上启动一个进程执行所需的时间 r o ( 1 i _ m ，1 9 蜘) 为两个相邻处理器之间的消息传输率，即每单位时间传送的 数据量。 在以后的讨论中，为了简明起见，我们对目标机器这6 个参量进行了不同程度 的假设。 3 执行成本与通信成本 如果用白来表示任务a i 在处理器弓上的执v r 时f b q ，那么 巧= 半+ 局 设c i 2 j 2 表示处理器p j ，上的任务翻一与处理器p j z 上p 2 任务a t ：之间的通信开销，如 果这两个处理器相邻，那么 c 。i 2 ，j 。2 煮“t + 西” 其中兄。，：表示这两个处理器间的传输率，o 表示b 。与疗：之间的通信线路的 竞争开销。 如果b 。与p ，：之间不相邻，为了表达简单起见，假定每两个相邻处理器之间的 消息传输率均为r ，每个处理器的消息传递启动时间均为，用岛m 表示处理器片。到 处理器尼：的线路条数( 也称之为中继段数) ，那么 中国科学技术大学硕士学位论文并行异构系统任务调度问题研究 q z2 = ( 等+ ，) 木局+ o 以后如无特别指出，并行应用程序的一个调度其实就是对其对应的任务图g 到 目标机器的一个映射f ： p l ，p 2 ，p m x o ，叫，肋= 囟，砂表示任务a ，被调度到 编号为f 的处理器上，起始执行时刻为，。一般地，可用g a n t t 图g c ( g a n t tc h a r t ) = p ( 口j ，t ( a ，) ) ia ，啊来直观地表示调度结果，其中函数p ( a r ) 表示分配给任务a ，的 处理器号，f ( 口i ) 表示任务a ，的起始执行时刻。 一般入口节点任务的起始执行时刻以零计算，那么所有任务执行完的那个时刻 称为调度长度( m a k e s p a n ) ，它也反映了整个并行程序任务的执行时间，显然， m a k e s p a n = m a ，x t ( a , ) + w ( a i ) s j ) ，其中卢p ( 口i ) 。一般来说，任务调度的目标就是 要获得最短的整个应用程序的执行时间，也即上述的调度长度。在许多启发式任务 调度中，有时直接以调度长度为目标函数来进行操作非常困难，所以经常以保持负 载平衡、减少任务间通信量或减短关键路径长度等为目标函数来执行调度操作，但 最终还是以获得较短的调度长度为目标。 ( a ) 任务图( b ) 目标机器( c ) 调度结果的g a n t t 图表示 图2 1 调度实例 中国科学技术大学硕士学位论文并行异构系统任务调度问题研究 图2 1 ( a ) 是一个示例任务图，每个圆圈表示一个任务，其中横线上面为任务名 ( 任务号) ，横线下面为该任务的计算负载的单位时间数量，圆圈间的有向边表示任 务问的执行关系，有向边旁边的数字代表通信延迟的单位时间数量。图2 1 ( b ) 所示 的是目标机器模型，该目标机器模型由三个处理器组成，它们之间是全相连的，并 且每个处理器的性能相同。图2 k c ) 所示就是图2 1 ( a ) 所示的任务图在图2 1 ( b ) 所示 的目标机器上的一种调度方案，该调度结果用g a n t t 图来表示，其中顶部为处理器 编号，左边的数字为时间轴。由于任务口i 和砚被分配到同一处理器上，因此它们之 间的通信延迟忽略为0 ，而由于任务a l 和a 3 、a 4 被分配到不同的处理器上，所以a l 到a 3 和a l 到m 的通信延迟不能忽略，分别为一个时间单位和2 个时间单位。 2 2 静态任务调度的n p 完全性及其最优算法 静态任务调度问题是并行分布计算中最具有挑战性的问题之一，它的一般形式 和几种受限形式都是n p 完全问题。如要取得多项式时间复杂度的有效最优调度算 法，那么必须对表示并行程序的任务图或并行分布算法模型附加一些限制条件，本 节主要讨论静态任务调度问题n p 完全性及其最优算法。 2 2 1 静态任务调度的n p 完全性 静态任务调度的问题同样也需要考虑不同的调度模型，本节主要从是否考虑通 信延迟这一角度来讨论其n p 完全性。 l 不考虑通信延迟 在不考虑通信延迟的静态任务调度问题中，问题1 是最为一般的任务调度问题， 其定义如下： 问题1 给定一组任务a = a i ，a 2 ，。，a n ，这组任务相互之间满足偏序关系“ ”，每 个任务对应的权重为w ( a ，) ，另外给定m 个处理器及一时间限制h ，是否存在一个从 a n o ，1 ，h 1 ) 的全函数，该函数必须满足三个条件： 如果a i a j ，那么以口f ) + w ( 口f ) 欢a j ) 对a 中的每个任务a i ，满足苁口，) + w 0 d 劲 中国科学技术大学硕士学位论文 并行异构系统任务调度问题研究 对区间 0 ，h ) z 的任何一点t ，至多存在m 个i 值满足条件以日f ) t f l a ，) + w ( 口j ) 。 问题1 的第一个条件规定了各任务在时序上必须满足的约束条件；第二个条件 规定了每个任务必须不迟于h 时刻完成，即限制了调度长度不超过h ；第三个条件 限制了某一时刻最多只能有m 个任务处于执行状态。问题1 的n p 完全性由r i c h a r d m k a r p 于1 9 7 2 年给出了证明。 问题l 是一般性的任务调度问题描述，在问题1 的基础上可以延伸出许多具有 n p 难度的受限任务调度问题，下面几个受限的任务调度问题是在问题l 的基础上， 通过对任务模型或处理器模型附加一些限制条件而产生的，但它们仍然都是np 完 全问题。 问题2 限制问题1 中的w ( a ，) = l ( 1 s f 如) ，即每个任务的执行长度相同，均为一 个时间单位。 问题3 限制问题1 中的w ( 的= 1 或者w ( 研) = 2 ( 1 f 勤) ，m = 2 ，即每个任务的执行 长度为一个时间单位或2 个时间单位，处理器数目为2 。 问题4 限制问题l 中的任务偏序关系满足区间有序，m = 2 。 问题5 限制问题l 中的w ( a ，) = l ( 1 f 9 ) ，任务间的偏序关系是一个对向树。 在上面所描述的问题中，w ( 的= 1 ( 1 s f 勤) 表示每个任务的执行时间相同，不失 般性，可令它们均为单位时间l 。问题5 中的对向树是出树与入树的不相交并集， 其中出树是每个节点的前驱唯一，后续不唯一的树；入树是每个节点的前驱不唯一， 后继唯一的树。对于入树或出树，当w ( a - ) = 1 ( 1 s f 9 ) 时，最优算法是存在的。 j e f f r e yd ，u l i m a n 在1 9 7 5 年证明了问题2 与问题3 的n p 完全性，c h r i s t o sh p a p a d i m i t r i o u 在19 7 9 年证明了问题4 的n p 完全性，m g a r e y 和d j o h n s o n 等于1 9 8 3 年证明了问题5 的n p 完全性。虽然有许多方法来求解或证明两个处理器上的任务 调度问题，但它与一个任务图的补图的最大匹配问题有着非常密切的关系，m v u j j i 等建立的这样关系，而且这种关系还可以扩充到考虑通信开销在内的情形。 2 考虑通信延迟 处理器之间的通信开销是并行分布计算中不能获得线性加速比的主要因素，一 般来说，在考虑通信延迟的情况下，调度复杂度与选择的通信代价模型有很大的关 系。首先，可对任务图和目标机器施加一些限制条件，主要是任务图中任意两个任 中国科学技术大学硕士学位论文 并行异构系统任务调度问题研究 务间的数据通行量西为常数c l ，每个任务的工作负载为一常数c 2 ；目标机器除了 全连接假设外，限定相邻处理器之间的传输率为常数r ；即处理器速度为s ，并且 假定旦：竺，臣l j 任务执行时间和通信时间延迟相同，设都为单位时间l 。在此基础 sr 上，常用的通信代价模型有下列三种： ( 1 ) m o d e l a 在该代价模型中，表示调度结果的g a n t t 图不反映通信延迟，但必 须保持任务间的有限关系。完成一个并行程序的整个代价t c = e c + c c ，其中e c 表 示执行代价，表示通信代价的c c 为集合 ( 口。a ，) l ( a u , a 。) e 但p ( a 。) 劫( 口，) ) 的元素个 数。 ( 2 )