（计算机软件与理论专业论文）unc模型上模拟退火遗传调度算法研究及并行化.pdf

上海大学硕一l 学位论文 摘要 多处理机调度问题是并仃处理叶 的一个著名j 司题。调度的主要目的是优化 并行程序在系统中运行的一些指标，本文中调度的主要目标是缩短调度后并行 程序的执行时间和提高多处理机系统的利用效率。在一般情况下调度问题的复 杂性是n p - - c o m p l e t e 的。对于规模比较大的调度问题，由于任务图的规模太 大，一般调度算法将会由于内存的限制而不能胜任。一种途径是采用动态调度 算法，但是由于动态调度算法是在程序运行时进行的，并且程序中的一些参数 可以是预先未知，直到运行时才确定的，而且动态调度一般要对并行程序加一 些前提上的约束，故算法设计比较复杂、困难：另一种途径是将比较好的调度 算法并行化。 本文首先介绍了一些背景知识，然后介绍了目前常用的各种调度模型和一 些代表性的调度算法。再详细介绍两种典型调度模型b n p 和u n c ，阐明了设纠 u n c 模型上的调度算法的理由。在结合已有的模拟退火算法和遗传算法的基础 上，我们改进了现有的遗传调度算法，自适应地保存最优个体，并对其进行模 拟退火，提出了在u n c 模型上的自适应塌优保存的模拟退火遗传凋度算法 s a m o a g s a a 最后将该算法并行化，并在自强2 0 0 0 上高性能计算机上实现。本 文采用香港科技大学y u k w o n gk w o k 提供的b e n c h m a r k s 图集对本文算法和其 它算法进行了比较分析。算法的比较结果显示算法对规模适中的任务图有较好 的搜索效果，并且对于不同粒度的任务图而言，粗粒度的任务图的调度效果优 于细粒度的任务图。 该论文的主要贡献： 1 ) 将遗传算法与模拟退火相结合的混合遗传算法应用于调度问题： 2 ) 将其与其它调度算法进行了纵向、横向的比较： 3 ) 将其并行化及性能分析。 关键词：多处理机调度：遗传调度算法；模拟退火；d a g 图；并行化：u n c 模 犁。 上海大学硕士学位论文 a b s t r a c t s c h e d u l i n g a p a r a l l e p r o g r a m t oam u l t i p r o c o s s o r s y s t e m i sa w e 1 一k n o w np r o b le ml np a r a l e lp r o c e s s jn g t h eo b j e c t iv eo fs c h e d u i i n g ist oo p t i m j z eap a r a l l e ip r o g r a m sp e r f o r m a n c e t h em a i no b j e c t l v e ， i nt h l st h e s i s ，lst om i n i m i z et h ep a r a l l e le x e c u t i o nt m ea n di m p r e v e t h ee f fjc i e n c yo ft h em u t i p r o c e s s o rs y s t e m t h es c h e d u l i n gp r o b l o mi s n p c o m p l e t ei n i t sg e n e r a lf o r m s i n c et h es i z eo fd a gg r a p hi st o t ) b ig g e rf o rs o m eb i gs c a l es c h e d u l j n gp r o b l e m ，t h eo r d i n a r ys c h e d u l i n g a 1g o r i t h m sa r eu n c a p a b i eo fd o i n gw e l lf o rt h el i m i t e dm e m o r y ak i n d o fa p p r o a c hi st o a p p l yd y n a m i cs c h e d u l i n ga l g e r t h m t h ed y n a m i c s c h e d u i n ga l g o t i t h mi se x e c u t e dd u r i n gt h ec o u r s eo fp r o g r a mr u n n i n g s o m ep a r a m e t e r so fp r o g r a ma r en o ta s c e r t a i n e du n t i lt h ep r o g r a mi s e x e c u t e d ，s o m er e s t r i c t i o n sw i l lb ea d d e dd u r i n gt h ed y n a m i cs c h e d u l i n g a g o r i t h mjse x e c u t e d s od e v i s i n gad y n a m i cs c h e d u l i n ga l g o t i t h mi s d i f f i c u l ta n dc o m p l e x a n o t h e rb e t t e ra p p r o a c hi st o p a r a l l e l jz e t h e a l g o r jt h m f i r s t l y ，w e i n t r o d u c e ds o m e b a c k g r o u n dk n o w l e d g e t h e n ，s o m e d i v e r s em o d e sa n da l g o r i t h m so fs c h e d u i n gp r o b l e mw e r ed e s c r jb e da n d t w ot y p i c a lm o d e l s ：b n pa n du n cw e r ed e t a l l e d a f t e r w a r d s ，w ep r e s e n t e d t h er e a s o n sw h yw ed e s i g n e das c h e d u l i n ga l g o r i t h mo nu n cm o d e b a s e d o nt h ec o m b n a t i o no fs i m u a t e da n n e a l i n ga l g o r i t h m ( s a a ) a n dg e n e t i c a 】g o rj t h i n ( g a ) ，w ei m p r o v e dt h ee x i s t i n gg e n e t i cs c h e d u l i n ga lg o r jt h i n a n d p r o p o s e dan e wg e n e t i cs c h e d u l i n ga l g o r i t h mm a i n t ajn i n g o p t i m a a d a p t i v e l yw i t hs i m u l a t e da n n e a l i n g ( s a m o a g s a ) o nu n cm o d e a tl a s t w ep a r a l l e l i z e da n di m p l e m e n t e do u ra l g o r i t h m o nc l u s t e r i r i gc o m p u t e r s ， z i q ja n g2 0 0 0 u s i n gt h eb e n c h m a r k sd a g g r a p h sw h i c _ lo f f e r e db vy i j k w o n g k h , o ko ft h e h o n gk o n gs c i e n c ea n dt e c h n o l o g yu n i v e r s i t y ，w e c o m p a ie do u ra l g o r i t h mw j t ho t h e rs c h e d u ijn ga l g e r t h i n s t h ey e s 【j l t s 一 土整盔堂堡主堂丝堡塞 s h o w e dt h a to u ra l g e r it h mo u t p e r f o r f i so t h e ra l g o r i t h m sw h ii et h es iz e oft a s kg r a p hjsm o d e r a t e ，a n dt h er e s u t s o fc o a r s eg z 、a n u l a ljt yd a g a r eb e t t e lt h a nt h o s eo ff i n eg r a n u l a r it y d a g t h em a i nc o n t r i b u t i o n so ft h ed i s s e r t a t i o na r e ： i ) a p p l y i n gh y b r i d6 a ( s a m o a g s a ) w h i c hi s c o m b i n e dg aw jt hs a at o s c h e d u l i n gp r o b l e m ； 2 ) c o m p a r i n gs a m o a g s aw i t ho t h e rs c h e d u l i n ga l g o r i t h m s ： 3 ) p a r a l l e l i z i n gs a m o a g s aa n da n a l y z i n g i t sp e r f o r m a n c e k e y w o r d s ：| u l t i p r 。c e s s o rs c h e d u l i n g ：g e n e t i cs c h e d u l i n ga l g o r i t h m s ： s i m u a t e da n n e a l ：d a g ：p a r a l l e l jz a t i o n ：u n cm o d e l v i 卜 原创性声明 本人声明：所呈交的论文是本人在导师指导f 进行的研究 工作。除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已发表或撰写过的研究成果。参与同一工作的其他同志对本研究 所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：日期 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，驯：学校有 权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论 文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：导师签名 日期 上海大学硕士学位论文 1 1 本文的研究背景 第一章绪论 当前，高性能计算技术在国内外受到高度的重视，它在科学研究、 二程技 术以及军事等方面的广泛应用，已取得了巨大的成就。自然而然，火规模并行 计算已成为计算机科学领域中的一项前沿课题。但是由于并行系统的体系结构 不同于传统的冯诺依曼结构，所以当并行处理成为解决大型科学与工程计算 及国防问题的重要途径的同时，它也提出了许多串行处理中所没有遇到过的问 题。例如：并行程序的设计，顺序程序的并行划分，计算任务的调度分配，处 理机之间的通讯同步，处理机负载平衡等问题。其中，调度问题是并行编译中 的一个十分重要的问题，调度结果的好坏将严重影响用户任务的并行运行时问 和并行系统的利用效率。目前，已出现了大量的文献专门研究和讨论了这一课 题。遗传算法的优点在于擅长全局搜索，特别适合于目标函数是多峰值和搜索 空间不规则的情况。本文的工作将围绕应用遗传算法解决调度问题而展开。 1 1 1 并行计算机模型和并行程序设计 由于存在多种处理机系统体系结构，导致处理机分配调度算法也存在着很 大差异，不同的多处理机体系结构对不同粒度的用户并行任务有不同的适用 性。根据一个并行计算机能够同时执行的指令与处理的数据的多少，可以把并 行计算机分为s i m d ( s i n g l e i n s t r u c t i o nm u l t i p l e d a t a ，单指令多数据并行 计算机) 和m i m d ( m u l t i p l e i n s t r u c t i o nm u l t i p l e d a t a ，多指令多数据并行计 算机) 两种，如图1 所示。s i m d 计算机同时用相同的指令对不同的数掘进行操 作，它开发的是空间并行性，真正的并行计算机是以m i m d 模型执行程序的计 算机。m i m d 是多指令流多数据流模型，即所有的处理机在同一个时钟周期内 对不同数据执行不同的指令。在这两种模型中，m i m d 模型最为通用 1 ，2 。 随着新的并行计算机组织方式的产生，按同时执行的程序和数据的不同， 人们又提出了s p m d ( s i n g l e p r o g r a mm u l t i p l e d a t a ，单程序多数据并行计算 ! = 塑盔堂塑主堂焦堡塞 机) 和m p m d ( m u l t i p l ep r o g i a m u l t i p l ed a t a ，多程序多数据并行计算机) 的 概念，如图l _ 1 所示。 盆 舞 _ m 略 妊s 9 登m 略 妊s 指令个数i程序个数p 图1 1 按指令c 程序) 数据的个数列并行计算机进行分类 从物理划分，共享内存和分布式内存是两种基本的并行计算机储存方式。 除此外，分布式共享内存也成为一种越来越重要的并行计算机存储方式。 ( 1 ) 刘于共享内存的并行计算机，操作系统的同一副本可以对称地在各 个处理机运行，各个处理单元通过对共事内存的访问来交换信息，协调各处理 器对并行任务的处理。进程内多线程就是以这种体系结构为背景提出来的。由 于多线程共享用户进程虚空间，特别适合中小粒度的并行程序实现。 ( 2 ) 对于分布式内存的并行计算机，其实现方式是利用高速网络将各个 独立计算机互连，每个处理机拥有一个本地存储器和操作系统副本，各个处理 单元之间通过消息发送来交换消息，如利用p v m ( p a r a l e lv i r t u a m a c h i n e ) 或m p i ( m e s s a g e p a s s i n gi n t e r f a c e ) 通讯库传递消息，以协调和控制各个处 理器的执行。这种类型的多处理机系统有i n t e lp a r a g o n ，c r a yt 3 d 等。 ( 3 ) 分布式共享内存的并行计算机结合了前两者的优点，是当今新一代 并行计算机的一科r 重要发展方向。目前越来越流行的机群计算( c l u s t e r i n g c o m p u t jr i g ) 大多采用这科r 形式的体系结构。通过提高某个局部结点内部的计 算能力，使它成为所谓的“超结点”，不仅提高了整个系统的计算能力，而且 砌以提高系统的模块性和扩展性，有利于快速构造超大型的计算机系统口 。 对应于不同的计算机体系结构模型，目前主要的并行程序设计模型可分 为：数据并行模型，共享变量模型和消息传递模型。最为重要的是第一利嚼口第 三种模型。 ( 1 ) 数据并行模型是一种单程序( 单指令) 多数据的并行计算模型，编 程级别较高，编程相对较简单，但它仅适用于数据并行问题。在这种模型中， 土生盔堂婴主望丝堡壅 并行处理的数据被划分成多个小块并分配到各个逻辑处理机j 二，每个处理机执 行相同的程序( 或指令) 。程序采用“同步前进”的方式，所有的处理机同时 对不同的数据执行相同的操作。数据并行模型所支持的是一种单线程控制多数 据( 主要是数组) ，并具有全局地址空间和松散同步机制的程序设计风格。具 有代表性的数据并行语言是l l p l j ( h i g h p e r f o r m a n c ef o r t r a n ) 4 。 ( 2 ) 共享变量模型是- 8 7 紧耦合的并行计算模型。在这种模型中，各个 进程独立运行，进程之问通过存放在共享存储器中的共享变量进行交互。所以， 保证共享变量的操作一致性和维护事件发生的次序是设计程序的关键问题。否 则，可能导致意想不到的错误结果。该模型的并行程序设计较容易，系统的可 编程性较好，但全局存储器也构成了整个系统的瓶颈。现有的这类语言多数是 采用对现有的程序设计语言进行扩充，增加并行库或两者都使用的方式实现 的，其代表性的有：p c ff o r t r a n 并行语言和曙光一号机中的并行库。 ( 3 ) 消息传递模型是一种松耦合的并行程序设计模型，它的编程级别相 对较低，设计程序时要考虑程序和数据的划分，任务调度等问题，这使得并行 程序设计困难，但它为编程者提供了更灵活的控制手段和表达并行的方法，一 些用数据并行方法很难表达的并行算法度都可以用消息传递模型来实现，因而 司以有更广泛的应用范围。这类语言的实现方式包括扩充串行语言，提供支持 并行的函数库及设计新的并行语言等多种方式，其代表性的有：o c c a m 语言， p v m 环境等。表1 1 是数据并行和消息传递两种并行编程模型的简单对比。 表1 - 1 数据并行与消息传递并行编程模型 对比内容数据并行消息传递 一 编程级别尚低 适用的并行机类型s i m d s p m d s i m d m i m d s p m d m p m d 执行效率依赖于编译器高 地址空间照一多个 存储类型共享内存分布式内存或共享内存 通信的实现编泽器负责程序员负责 问题类数据并行问题数据并行、任务并行 日前状况缺乏高效的编译器支持使用广泛 上海大学硕士学位论文 1 1 2 并行语言和并行算法 并行程序是通过并行语言来表达的并行语言的产生方式主要有三利r ：( 1 ) 设计全新的并行语言；( 2 ) 扩展原来的串行语言的语法成分，使它支持并行特 征；( 3 ) 不改变串行语言，仅为串行语言提供可调用的并行库。对于这三种并 行语言的实现方式，目前最常使用的是第二种和第三种方式，特别是第三种方 式。我在后面的算法实现中用到的m p i 编程就属于这种方式。 并行算法是给定并行模型的一种具体明确的解决方法和步骤。按照不同的 划分方法，并行算法有多种不同的分类。 对于相同的并行计算模型，可以有多种不同的并行算法来描述和刻画。由 于并行算法设计的不同，可能对程序的执行效率有很大的影响，不同的算法可 以有几倍、几十倍甚至上百倍的性能差异是完全正常的。并行算法基本上是随 着并行机的发展而发展的。从本质上说，不同的并行算法是根据问题类别的不 同和并行机体系结构的特点产生出来的。一个好的并行算法要既能很好地匹配 并行计算机硬件体系结构的特点，又能反映问题内在并行性。 对于机群计算，有一个很重要的原则就是设法加大计算时间相对于通信时 问的比重，减少通信次数甚至以计算换通信。这是因为对于机群系统，一次通 信的开销要远远大于一次计算的开销，因此要尽可能降低通信的次数，或将两 次通信合并为一次通信。基于同样的原因，机群计算的并行粒度不可能太小， 因为这样会大大增加通信的开销。如果能够实现计算和通信的重叠，那将会更 大地提高整个程序的执行效率 3 。 1 1 3 并行化编译 本文将主要考虑分布式内存的多处理机系统上的程序设计工作。从上面可 知，直接用并行程序设计语言来编写并行程序的代价太高，而计算机这门学科 发展到今天在串行( 顺序) 程序设汁方面已经积累了大量的代码和经验，所以 目前人们将工作注意力集中在对串行程序并行化的实现方法上。但是，将串行 程序转化为并行程序，使其目标代码在并行机上执行也是一件十分困难的工 作。其 f 一个关键难点就在于对串行程序中计算任务及数据的划分和他们到多 处理机的调度分配问题。分布式环境下，胡南军等人在运用基于超平面的线性 上海大学硕士学位论文 划分技术列串行程序中循环引用的数组进行无通信划分方面做了深入的研究， 给出了完整的线- 肚划分模式计算算法 6 。目前对于这个问题所采片j 的方法主 要有下列三二种： ( 1 ) 对串行程序进行自动的并行划分。这种方法的关键在于智能编译器 的设计。智能编译器的难点就在于并行编译器如何自动识别和确定串行程序的 并行性。因为对程序中的数据相关性的确切分析是刁i 能在多项式的时间内完成 的。k e n n e d y 和k r e m e r 5 表明寻找最佳的数据划分模式的问题是n p 闽题。所 以目前采用的方法大多数只是做一些近似的相关性分析 7 ，8 。p e t e r a r o n s s o n 和p e t e rf r i t z s o n 提出了一种自动化并行程序工具d y m o a ，这个 工具开始产生十分细的任务图，有的达3 0 0 0 0 个结点，所以在正式调度前有一 个任务合并阶段。目前，还没设计出很好的合并算法，故只在某些特殊的情形 下有较好的效果 1 0 。另外，d y c h e n g 和d m p a s e 在文献 9 中提出了设计 一种实用的半自动化的程序并行化工具的思想。 ( 2 ) 在输入的串行程序中加入用于确定程序划分的信息以帮助编译器产 生有效的并行代码。如文献 1 1 ，1 2 中设计了工具p l u s p y r 通过对串行程序中 加入t a s k - - e n d t a s k 语句，人为地将程序划分为各个不同的计算任务，然后再 在此基础上进行数据相关性分析和提取程序并行所需的信息，以帮助编译器产 生有效代码。但即使在数据相关性分析正确和程序并行性完全确定的情况下， 如何自动调度并行程序以使程序运行性能达到最优仍然是并行程序编译中的 一个十分重要的问题。 ( 3 ) 由程序员人工完成对串行程序并行化的工作。其实现方法是使用通 讯库函数人工地对程序和数据进行划分，并且决定它们的执行顺序。这样做的 优点是在某些情况下程序性能可以达到昂优；缺点是极大的增加了程序设计者 的负担，使程序设计变得极为繁琐并且程序的调试验证几乎成为不可能。 以上三神方法的主要区别在于对程序中的计算任务，数据的划分和整个程 序到多处理机上的调度分配是由程序员人工完成，还是由并行编译器自动或半 自动完成。目前做的比较好的自动并行编译器来完成对串行程序划分、调度， 并壤终产生可在并行机上执行的目标代码的代表性例予有d y m o l a 等；比较好 的半自动的并行编译器的代表性例子有h y p e r t o o l 1 3 ，c a s c h 1 4 1 和 上海大学硕士学位论文 p y r r o s 1 ，1 5 系统。下面以d y m 0 1 a 工具为例对具有自动调度功能的并行编译 器做一些简荦的介绍。d y m o l a 是一个自动并行化工具，它将由一个m o d e l i c a 编译器产生的串行模拟代码翻译成能够在并行计算机上执行地并行代码。它输 入的是相关的串行模拟代码，由d y m o l a 商用编译器产生最优化串行代码，解 析产生的代码建立任务图，再利用任务合并算法十分细的任务图合并成粗粒度 任务图，最后利用t d s ( t a s kd u p l i c a t i o ns c h e d u l i n g ) 算法得到静态调度 方案和可以执行的并行代码。d y m o l a 自动并行工具的总体框架如图卜2 ，内部 结构如图卜3 。与其它半自动并行编译工具相比，它考虑了d a g 图的产生，但 是随着处理机速度和通信速度之间距离的扩大，将来需要改进工具中用到的 c l u s t e r i n g 算法和任务合并算法来提高加速比。 圈i - 2 d y m o l a 自动并行工具的总体框架和环境 上海大学硕士学位论文 图1 - 3 d y m o l a 自动并行化工具内部结构 1 2 本文的研究工作 本文的研究工作主要是对并行编译中的调度算法进行分析、改进及并行 化。由于多处理机调度问题是典型的n p - - c o m p l e t e 问题 1 0 ，1 7 ，如何寻找到 最优调度方案近年来一直是计算机领域一个活跃的课题。自从提出多处理机模 型以来，目前已有上百篇文献专门讨论了有关调度问题的求解方法，提出了各 种各样的调度算法。由于各文献所基于的调度问题的背景和模型不同，提出了 许多不同的假设前提，同时有许多概念和模型被重复提出和定义，因此造成了 许多概念的模糊和混淆。文献 1 8 作了一些调度算法比较工作，同时参考近两 年来关于调度算法的学术报告和相关文献 1 0 ，1 9 ，2 0 ，对目前的调度模型进行 更完整的介绍，并在此基础上阐明本文算法所基于的模型和假设前提。在确定 调度模型后，本文做了以下工作； 1 遗传算法与模拟退火相结合的混合遗传调度算法的设计 关于调度算法问题的求解方法有很多，例如：分支定界法，表调度算法， 确定的启发式算法，遗传算法，任务合并算法，模拟退火算法，神经网络算法 等。由于在一般情况下求解最优调度方案是一个n p 难问题，所以大多数研究人 员都致力于设计一种有效的、多项式级的、确定的启发式调度算法。如文献2 】 - - 2 7 等都是致力于寻找基于不同模型上的一种高效的启发式规则，以争取存 多项式时间内找到一个满意的解。文献 1 8 ，2 8 ，2 9 对到现在为止的几十种代 表性的调度算法进行了分类和比较。总的来说，目前所采用的确定的启发式算 法求解的质量普遍令人不太满意，搜索到蠼优解的概率比较低，而且有些算法 还只能适用于些特定的模型和一些特定结构的d a g 图，因而存应用范围上有 很大的约束和局限性。 遗传算法是一种随机搜索技术，由于它具有处理问题的柔软性和并行处理 能力，尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛用 于组合优化、i i i i 学习、自适应控制、规划设计、和人工生命等领域。与其它 的优化方法相比，遗传算法的优点在于擅长全局搜索，目前已有相关文献 1 8 ， 2 1 ，2 2 ，3 0 ，3 1 利用遗传算法来解决调度问题。由于基本遗传算法存在着局部搜 索能力较差的缺陷，文献 1 8 提出的g c a 算法在编码上虽然有所改进且比以往 同类型的调度算法要好，适用范围也更广，但是由于只采用单纯的遗传算法的 缘故，因而不可避免在局部搜索方面仍然不够理想。本文针对这个缺陷，结合 模拟退火算法，设计了一种调度算法称为s a m o a g s a ( g e n e t i cs c h e d u l i m a l g o r i t h mm a i n t a i n i n go p t i m aa d a p t i v e l yw i t hs i m u l a t e da n n e a l i n g ) ， 我们在搜索效果上明显得到改进，提高了调度算法的解的质量。 2 调度算法的比较 由于目前众多的调度算法提出的模型及假设前提不同，这给调度算法的分 类和比较增加了不少困难，并且在现有的文献中许多概念和术语被重复提出和 重复定义的情况也造成了许多模型和概念上的混淆。为了防止这种情况出现， 我们根据自身环境的情况及国际上常见的模型定义，首先确定了本文要考虑的 调度问题的模型。然后根据各种d a g 图调度算法所基于的假设前提和使用方法 的不同对于现有的调度算法进行分类。在这个基础上，我们将本文提出的调度 算法从横向和纵向两个方面与其它的调度算法进行比较。横向比较是指根据千h 同的调度模型将s a m o a g s a 算法和e z 、l c 、d s c 、m d 、d c p 算法进行比较；纵向 比较是指在使用相同的求解方法的情况下( 都使用遗传算法) ，将s a m o a g s a 和 g c a 、s k i t g a 进行比较。为了保证比较的客观性和公证性，我们使用了文献 2 9 中设计的标准测试d a g 图集b e n c h m a r k s 进行比较对所比较的算法进行分 析与比较。b e n c h m a r k s 中的测试图主要包括随机d a g 图和来自些常用的科 学t 算中的任务图，其范围覆盖了各种不同拓扑结构的图和各种不同粒度的 图，比较结果将能够客观的反映各种算法的搜索性能。 上海大学硕士学位论文 3 调度算法并行化及性能分析 对于规模比较大的调度问题，由于任务图的规模太大，一般制度算法将会 由于内存的限制而不能胜任。一种途径是采用动态调度算法，但是由于动态调 度算法是在程序运行时进行的，并且程序中的一些参数可以是预先未知，直到 运行时刁确定的，故算法设计比较复杂、网难；而且动态调度一般要对并行程 序加一些前提上的约束，例如计算任务的划分不能是嵌套的，在循环体内不能 修改循环记数变量等。另一种途径是将比较好的调度算法并行化。本文主要研 究调度算法并行化方面。在这里我们也用文献 2 9 中的b e n c h a m r k 中的测试图 客观地分析并行后的算法的性能。 1 3 本文的结构 本文第二章将详细介绍目前调度问题的研究情况和各种调度模型，并且按 照求解调度方法的不同和调度模型的不伺将目前的调度算法进行分类。在此基 础上，我们将详细介绍本文选定的d a g 图和u n c 调度模型。结尾部分将谈谈目 前u n c 模型调度算法的缺陷和改进情况及我们使用遗传算法来求解的理由。 第三章将先简单介绍g c a 算法，再重点阐述本文提出的s a m o a g s a 算法。 本文首先分析现有遗传调度算法的缺陷，再谈谈g c a 算法的不足之处，设计如 结合模拟退火算法的混和遗传算法。算法实现后，用了几个常用任务图，其结 果从图上可以看出搜索性能比较好。 第四章将s a m o a g s a 算法与现有的调度算法进行纵向和横向的比较、分析。 在文献 2 9 提出的b e n c h m a r k s 的基础上，作者将s a m o a g s 算法与l c 、e z 、d s c 、 s m t g a 、m b 、d c p 和g c a 算法进行了比较，并对比较结果进行分析和小结。 但是，改进的算法对于规模比较大的任务如仍然不能胜任，故我们最合适的方 法是将该算法再并行化。 第五章s a m o a g s a 算法并行化。首先，确定并行算法的模型；其次，将一 些遗传算法参数进行调整；再次，并行算法实现和比较及性能分析。最后，简 单介绍我们的并行环境一自强2 0 0 0 高性能计算机系统。 第六章中对本文工作进行小结，并对此课题的最新研究方向作了简单介 绍。 上海大学硕士学伉论文 第二章调度问题和调度算法分类及比较 调度问题是并行处理中一个著名的问题。6 0 年代人们就开始在这方面进 行研究 2 1 。目前所提出的大量调度算法包括有：分支定界法，表调度法，确定 的启发式算法，遗传算法，模拟退火算法，任务合并算法，神经网络算法 3 2 等。 由于这些方法所基于的假设前提和模型的不同，他们实现的功能也不同，所以 很难在一个统的前提下进行讨论。因此，我们先对现有的调度问题的模型进 行分类，并在此基础上对现有的调度算法进行分类。然后我们重点介绍d a g 图 模型和u n c 模型上的d a g 图静态调度算法。 2 。1 调度问题模型 所谓多处理机调度是指如何将并行程序中的计算任务合理地分配到各 个处理机上的问题，其主要的优化目标有：缩短程序并行执行时间，提高系统 利用效率，平衡负载，减少调度开销等。在一般情况下，调度问题是n p 难问题。 目前关于任务图大家有不少相同的假设： ( 1 ) 任务图的结构是严格限制的( 如；树等) ，丽不是任意的； ( 2 ) 图中所有结点的计算量相同； ( 3 )结点之间的通信量为零。 关于机器模型也有不少相同的假设： ( 4 ) 可利用的机器数量是无限的； ( 5 ) 机器之间是完全互连的： ( 6 ) 网络资源没有冲突； ( 7 ) 处理机系统是同构的，也就是说，所有的机器处理速度相同。 即使在上面这样的假设前提下调度问题仍是十分复杂的。到目前为止只有 在三种十分特殊的情形下刊有能够找到最优解的多项式级的算法。这三种情形 分别是： 1 ：在数量无限的多处理机上调度树型结构的任务图，并且计算结点的 权值也就是结点的计算量必须是相同的。h u 在文献【3 3 j 中提出了解决这类调 上海大学硕二l 学位论文 度问题的多项式级的求解算法。 2 ：在两个处理机上调度任意结构的任务图，但计算结点的权值必须是 相同的。c o f f m a n 和g r a h a m 在文献【3 4 】中提出了二次级的求解算法。 3 ：在数量无限的处理机上调度间隔有序的d a g 图( i n t e r v a l o r d e r e d d a g ) ，其中计算结点的权值电必须是相同的。间隔有序的d a g 图指d a g 图 中任意两个顺序相关( p r e c e d e n c e - r e l a t e d ) 的结点都可以映射到时问轴的两 个不重叠的间隔中。p a p a d i m i t r i o u 和y a n n a k a k i s 在文献 3 5 中最早提出了 求解这类调度问题的多项式级算法。a 1 i 和e l - - r e w i n i 在文献 3 6 中证明了 下面的结论：对于间隔有序的任务图，如果边的权值和结点的权值相同的话， 调度算法也能在多项式级的时间内找到最优解。 但是在上面三种情形中，都将计算结点之间的通讯开销忽略不计。假如要 考虑结点之问的通讯开销的话，那么问题的复杂性又将是n p 难的。实际上， 考虑到问题的复杂性，大多数研究人员都致力于设计一种有效的、多项式级的、 确定的启发式调度算法。并且，为了简化问题和方便求解，人们在设计算法的 同时分别提出了不少假设前提和约束条件，这使得将这些算法进行有意义的性 能评价和比较变成十分复杂并且必须考虑以下一些问题：首先，大多数调度算 法基于不同的假设，这使得性能比较毫无目的；其次，各种算法采用不同的任 务图集合；最后，大多数算法使用小规模问题尺度进行算法性能估计，它们的 可扩展性未知。 为防止概念混淆，我们首先对现有的调度问题的模型进行分类介绍，分类 情况如图2 - i 所示： 因为调度模型的完全分类超出了本文的范围，故上面的分类概述还不够全 面，只是介绍涉及与本文算法相关的一些分类。关于在分布式环境下普通调度 问题模型c a s a v a n t 和k u h l 提出了更为广泛的分类法，他们着重考虑静态和动 态全局调度问题。在动态全局调度情形下可从物理上分为分布式划分和非分布 式划分；分布武划分又可分细分为协作式方法和非协作式方法：协作式方法和 静态情形又可以分为最优和近似最优等，更为详细情形可以参考文献 3 7 ：1 。 _ = 竖量2 1 1 兰堡主堂焦蝗塞 圈2 - 1 调度问题模型分类图 从上图可以看出，多处理机上的调度问题可以分为两大类；独立任务调度 问题和相关任务调度问题。 l 独立任务调度问题( j o bs c h e d u l i n g ) 对于独立任务调度问题，其着重考虑如何将一些独立的工作任务分配到一 个分布式的多处理机系统上以达到负载平衡，用时最少等目标。在考虑独立任 务分配时经常要考虑的一个重要问题是如何对一些预先不确定的工作任务在 程序运行时进行动态地调度。 2 相关任务调度问题( s c h e d u l i n ga n dm a p p i n g ) 与独立任务调度相对应的是相关任务调度问题，它主要考虑的问题是如何 将一个并行程序的多个相关计算任务合理地分配到一个多处理机系统上，以减 少调度后作业的最终完成时间。 从广义上来说，相关任务调度问题可以分为两种情况：静态调度和动态调 度。静态调度是指在程序编译时完成的调度。它必须在调度程序运行以前就知 道调度程序所需的有关信息，如：任务图的结构，各个计算任务的计算量，髯 计算任务之间的通讯量等。相对于静态调度来说，动态调度是在程序运行时讲 上海大学硕士学位论文 行的，并且程序中的一些参数可以预先不确定的，直到运行时才知道。动态调 度般要对并行程序加上一些前提e 的约束，如i t 算任务的划分不能是嵌套 的，在循环体内不能修改循环记数变量的值等。动态调度的目标除了要降低调 度后的并行程序的执行时间外，还包括减少开销等 1 8 。m c o s n a r d 在文献 1 2 中提出了- 4 十任务图的自动生成技术和- 4 十新的任务图模型一带参数的任务 图p 1 1 g ( p a r a m e t e r i z e dt a s kg r a p h ) ，p t g 可以看作是一种压缩的d a g 图模型， 在它基础上既可以加入参数信息初始化为静态d a g 图，也可以直接进行动态调 度。本文中将着重讨论静态调度模型和相关算法设计。 在静态调度中存在三种比较常见的并行程序表示模型：有向无环图 ( d i r e c t e da c y c l i cg r a p h ，简称d a g ) ，迭代任务图( i t e r a t i v et a s kg r a p h ，简 称i t g ) 和时间通讯图( t e m p o r a lc o n m l u n i c a t i o ng r a p h ，简称t c g ) 。其中有向 无环图也常称为顺序相关图，是目前最通用的并行程序表示形式。 有向无环图模型( d a g ) 如图2 2 ( a ) 所示。d a g 图的无环性质给如何模拟并 行计算强加了一个限制条件。d a g 图常用于分布式环境。在d a g 图中，结点表 示并行程序中的计算任务，每个计算任务可能是一个最小的计算单位( 由一些 不可分割的语句实例组成) 或一段子程序，其粒度大小可以由程序员指定或由 并行编译器确定。结点之间的有向边表示结点之间存在执行顺序上的先后约束 关系。结点之间的边还可以表示两个结点之间存在着通讯关系，有向边的权值 大小根据两个结点之间发送的数据量的大小和相应的通讯开销决定。因为带权 值的d a g 图模型能够很好的反映并行程序中的各个计算任务之间关系，包括任 务结点之间的执行顺序关系，任务结点之间的通讯开销等，所以大多数研究人 员都是在这个模型的基础上设计调度算法的。本文也将主要考虑基于d a g 图模 型上的静态调度算法的设计问题。 迭代任务图模型( i t g ) 如图2 2 ( b ) 所示。i t g 图属于数据流图的范围，它 在计算中模拟数据流或信号流。数据流图是有向图，但是相对与d a g 图来说， 数据流图能够包括循环并且更为紧密的表示计算模型。就一个描述有效计算的 数据流图来说，循环必须包括至少一个延时。一个延时可以用一个带权值的边 来表示。延时可以表示为多倍的时间单位( 常用d 表示) 或两个结点之间的通 讯量的迭代次数。延时打破了循环的优先权限制。由于延时的缘故，数据流图 上海大学硕士学位论文 能够模拟内部迭代( 没有延时) 和外部迭代( 有延时) 依赖。与展开的d a g 图 相比较，有效描述迭代计算的模型设计能够缩减图中所需的结点数目并且允f l ： 不确定的迭代次数。此外，还能够以更直观和结构更清晰的方式描述迭代。因 为能够详细地模拟迭代计算，因此迭代任务图的粒度常常介于细粒度和中等粒 度之间。迭代任务图也包括边权值和结点权值以反映计算和通讯代价，从而能 够挖掘映射和调度并行性。i t g 图适合于分布式或共享结构下任意代价的计算 任务和v l s i 系统环境。 时问通讯图模型( t c g ) 如图2 - 2 ( c ) 所示。时间通讯图是l a m p o r t1 9 7 8 年在基于时间空间图表的基础上提出的。t c g 图是一个有向无环、过程和阶段 导向的任务图。一个计算任务被划分为n 个连续过程p 。，p 。，p 。，任务图中 的每个结点只对应一个过程。对应某个过程p 的每个结点至少有一条边指向同 一过程的直接后继结点( 内部过程依赖) ，也可能有一条通讯边指向其它过程 的某个结点( 过程之间通讯) 。结点的权值表示计算量，联结过程内部和过程之 问的边表示通讯量。图2 2 ( c ) 用图说明了划分为三个过程的一个t c g 图。作 为一个带权值的有向无环图，它也要考虑到带权值的d a g 图关于过程内部的边 通讯代价为零的问题。在l a r c s 图形描绘语言的帮助下，t c g 图能够详细阐明 计算和通讯的各个过程。在这些阶段可能挖掘时间和空间的规律性，例如环就 是时间规律性的一个过程。将t c g 图按时间轴投影能够产生t i g ( t a s k i n t e r a c t i o ng r a p h ) 图。一方面，这种描述并行计算的过程导向透视图限制了 模型的灵活性。另一方面，它能够有效地描述迭代和有规律的计算任务。而且， 这种过程导向的观点能够以直观的方法描述许多程序中的计算任务。 除上面描述的特征以外，三种模型存在着一些上面已经部分谈到的关系。 我们可以将一种图模型描述转成另一种图模型，其目的是将算法应用于只对某 些图模型更有效的情形或者产生一个更为紧密的表示方法。图2 3 描述了上面 谈及的任务图模型之间的关系。该图中定义了任务图模型转化的三种关系：归 约、投影、展开。通过图的归约性质可以将一个复杂的图模型转化成一个简单 的图模型，其中简单图模型的性质是复杂图模型性质的子集。通过投影，一个 图模型可以