UNC模型上模拟退火遗传调度算法分析与并行化

《UNC模型上模拟退火遗传调度算法分析与并行化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一土整盔堂堡主堂丝堡塞——～showedthatouralgerithmoutperfor[fisotheralgorithmswhiIethesizeoftaskgraphjSmoderate，andtheresu]tSofCOarsegz、anulaljtyDAGarebettelthanthoseoffinegranularityDAG．Themaincontributionsofthedissertationare：i)applyinghybrid6A(SAMOAGSA)whichiscombinedGAwjthSAAtoSchedulingProblem；2)co

2、mparingSAMOAGSAwithotherschedulingalgorithms：3)parallelizingSAMOAGSAandanalyzingitsperformance．Keywords：

3、Ⅵultipr。cessorScheduling：GeneticSchedulingAlgorithms：Simu]atedAnneal：DAG：Paralleljzation：UNCModelVI卜原创性声明本人声明：所呈交的论文是本人在导师指导F进行的研究工作。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果。参与同一工作的其他同志对

4、本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。签名：——日期本论文使用授权说明本人完全了解上海大学有关保留、使用学位论文的规定，驯：学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容。(保密的论文在解密后应遵守此规定)签名：——导师签名日期上海大学硕士学位论文1．1本文的研究背景第一章绪论当前，高性能计算技术在国内外受到高度的重视，它在科学研究、]二程技术以及军事等方面的广泛应用，已取得了巨大的成就。自然而然，火规模并行计算已成为计算机科学领域中的一项前沿课题。但是由于并行系统的体系结构不同于传统的冯·诺依曼结构，所以当并

5、行处理成为解决大型科学与工程计算及国防问题的重要途径的同时，它也提出了许多串行处理中所没有遇到过的问题。例如：并行程序的设计，顺序程序的并行划分，计算任务的调度分配，处理机之间的通讯同步，处理机负载平衡等问题。其中，调度问题是并行编译中的一个十分重要的问题，调度结果的好坏将严重影响用户任务的并行运行时问和并行系统的利用效率。目前，已出现了大量的文献专门研究和讨论了这一课题。遗传算法的优点在于擅长全局搜索，特别适合于目标函数是多峰值和搜索空间不规则的情况。本文的工作将围绕应用遗传算法解决调度问题而展开。1．1．1并行计算机模型和并行程序设计由于存在多种处理机系统体系结构，导致

6、处理机分配调度算法也存在着很大差异，不同的多处理机体系结构对不同粒度的用户并行任务有不同的适用性。根据一个并行计算机能够同时执行的指令与处理的数据的多少，可以把并行计算机分为SIMD(single—instructionmultiple—data，单指令多数据并行计算机)和MIMD(multiple—instructionmultiple—data，多指令多数据并行计算机)两种，如图1所示。sIMD计算机同时用相同的指令对不同的数掘进行操作，它开发的是空间并行性，真正的并行计算机是以MIMD模型执行程序的计算机。MIMD是多指令流多数据流模型，即所有的处理机在同一个时钟周期

7、内对不同数据执行不同的指令。在这两种模型中，MIMD模型最为通用[1，2]。随着新的并行计算机组织方式的产生，按同时执行的程序和数据的不同，人们又提出了SPMD(single—programmultiple～data，单程序多数据并行计算————!=塑盔堂塑主堂焦堡塞——机)和MPMD(multipleprogIaⅢmultipledata，多程序多数据并行计算机)的概念，如图l_1所示。盆舞／_M略妊s9登M略妊s指令个数I程序个数P图1．1按指令C程序)数据的个数列并行计算机进行分类从物理划分，共享内存和分布式内存是两种基本的并行计算机储存方式。除此外，分布式共享内存也

8、成为一种越来越重要的并行计算机存储方式。(1)刘于共享内存的并行计算机，操作系统的同一副本可以对称地在各个处理机运行，各个处理单元通过对共事内存的访问来交换信息，协调各处理器对并行任务的处理。进程内多线程就是以这种体系结构为背景提出来的。由于多线程共享用户进程虚空间，特别适合中小粒度的并行程序实现。(2)对于分布式内存的并行计算机，其实现方式是利用高速网络将各个独立计算机互连，每个处理机拥有一个本地存储器和操作系统副本，各个处理单元之间通过消息发送来交换消息，如利用PVM(para]lelvirtua]machin