UNC模型上模拟退火遗传调度算法研究及并行化

摘要

多处理机调度问题是并行处理中的一个著名问题.调度的主要目的是优化并行程序在系统中运行的一些指标,本文中调度的主要目标是缩短调度后并行程序的执行时间和提高多处理机系统的利用效率.在一般情况下调度问题的复杂性是NP-complete的.对于规模比较大的调度问题,由于任务图的规模太大,一般调度算法将会由于内存的限制而不能胜任.一种途径是采用动态调度算法,但是由于动态调度算法是在程序运行时进行的,并且程序中的一些参数可以是预先未知,直到运行时才确定的,而且动态调度一般要对并行程序加一些前提上的约束,故算法设计比较复杂、困难;另一种途径是将比较好的调度算法并行化.本文首先介绍了一些背景知识,然后介绍了目前常用的各种调度模型和一些代表性的调度算法.再详细介绍两种典型调度模型BNP和UNC,阐明了设计UNC模型上的调度算法的理由.在结合已有的模拟退火算法和遗传算法的基础上,我们改进了现有的遗传调度算法,自适应地保存最优个体,并对其进行模拟退火,提出了在UNC模型上的自适应最优保存的模拟退火遗传调度算法SAMOAGSA.最后将该算法并行化,并在自强2000上高性能计算机上实现.本文采用香港科技大学Yu-Kwong Kwok提供的Benchmarks图集对本文算法和其它算法进行了比较分析.算法的比较结果显示算法对规模适中的任务图有较好的搜索效果,并且对于不同粒度的任务图而言,粗粒度的任务图的调度效果优于细粒度的任务图.该论文的主要贡献:1)将遗传算法与模拟退火相结合的混合遗传算法应用于调度问题;2)将其与其它调度算法进行了纵向、横向的比较;3)将其并行化及性能分析.

目录

文摘

英文文摘

原创性声明及本论文使用授权说明

第一章绪论

1.1本文的研究背景

1.1.1并行计算机模型和并行程序设计

1.1.2并行语言和并行算法

1.1.3并行化编译

1.2本文的研究工作

1.3本文的结构

第二章调度问题和调度算法分类及比较

2.1调度问题模型

2.2 DAG图调度问题

2.2.1 DAG图模型

2.2.2 DAG图的构造与产生

2.2.3 DAG图调度

2.3基于DAG图的静态调度算法的分类简介

2.4确定的启发式调度算法的缺陷

第三章模拟退火遗传调度算法的设计

3.1遗传算法

3.2模拟退火算法

3.3现有的遗传调度算法

3.4 SAMOAGSA算法设计

3.4.1染色体编码的选择

3.4.2初始种群的生成和遗传代数的确定

3.4.3适应度函数

3.4.4选择操作

3.4.5模拟退火操作

3.4.6交叉操作

3.4.7变异操作

3.4.8算法的特点

3.5算法实现和实验结果

第四章调度算法的比较与分析

4.1评价算法的标准

4.2参加比较的算法的介绍

4.3标准测试DAG图集合

4.4算法比较及结果分析

4.4.1 PSGs的比较结果及分析

4.4.2 RGB0S的比较结果及分析

4.4.3 RGPOS的比较结果及分析

4.4.4比较结果小结

第五章SAMOAGSA算法并行化

5.1并行化模型

5.2 SAMOAGSA并行化算法设计

5.2.1 SAMOAGSA算法框架

5.2.2控制参数设置

5.2.3迁移频率

5.3算法性能分析

5.4自强2000简介

5.4.1硬件系统配置

5.4.2软件配置

第六章总结与展望

论文著作

致谢

参考文献

论文说明