飞行器设计中分布与并行任务生成和调度算法研究.pdf

南京航空航天大学
硕士学位论文
飞行器设计中分布与并行任务生成和调度算法研究
姓名:赵路
申请学位级别:硕士
专业:计算机应用技术
指导教师:庄毅
2011-01
南京航空航天大学硕士学位论文

摘要
在计算物理、石油勘探、生物科学、桥梁设计、飞行器设计和航天器设计等领域中,大型
矩阵计算是一个关键的技术难题。主要难点是问题求解时随着矩阵阶数的增加,运算和存储规
模都将大幅度上升。而且当所求问题的规模很大时,所需的运算能力和存储空间有可能会超出
单台高性能计算机的承受能力范围。因此,在上述领域中,如何高效的存储和计算大型矩阵的
是一个研究热点。
论文工作主要针对大型矩阵的特征值问题,在研究了常用的分布与并行程序设计模型和算
法的基础上,深入研究了直接变换法,以及直接变换算法的分布与并行化处理方法,从理论上
分析了直接变换法和 DPC-DTM(Distributed puting Based on Direct Transformation
Method for Mode Synthesis)加速比不高的瓶颈问题, 并用实验验证了该瓶颈的存在;针对
DPC-DTM 瓶颈,采用并行子空间迭代方法,考虑将该算法结合直接变换法,提出了 RDPC-DTM
(Refined Distributed puting Based on Direct Transformation Method for Mode
Synthesis)算法,可解决 DPC-DTM 的瓶颈问题;进一步,针对 RDPC-DTM 算法在应用于大型
矩阵计算时存在的分布并行任务的调度问题,本文在研究了 Min-min、Min-max、遗传算法、粒
子群算法和蚁群算法后,选用解结果相对较好的遗传算法进行改进,根据大型矩阵计算的特点
和 RDPC-DTM 具有的可分布性等特点,设计了染色体的编码、适应度计算函数、选择算子、
交叉算子和终止条件,提出了基于遗传算法的并行任务的调度算法(Parallel Task Scheduling
Algorithm Based on ic Algorithm, PTSAGA),并通过对比实验验证了算法的有效性。
实验结果表明,本文提出的 RDPC-DTM 算法可以解决超大型矩阵的存储问题,提高了计
算速度和资源利用率, RDPC-DTM 算法与 DPC-DTM 算法相比,速度和加速比有较大的提高;
本文提出的基于遗传算法的并行任务调度算法 PTSAGA 可以运用到机群环境中,实验结果表
明, PTSAGA 提高了机群的负载平衡和资源利用率。

关键词:分布与并行计算,遗传算法,负载平衡,子结构,模态综合法,矩阵存储,任务调度
I
飞行器设计中分布与并行任务生成和调度算法研究

Abstract
In the area involving huge amount putation, such putational physics, petroleum
exploration, bridge design, biological science, aircraft design and spac ecraft design, the large-scale
matrix calculation is the key crux. The scale puation and storage will dramatically increase
along with the growing of matrix dimension, which will ultimately exceed the capability of single
computer. Thus, the problem of how to efficiently calculate and store large-scale matrix needs is
challenging and significant, expecially in the area processing huge amount of data.
In view of the eigenvalue problem of large-scale matrix, this thesis focues on the Direct
Transformation Method for Mode Synthesis as well as its concrete designing named Distributed and