论文摘要
随着高性能计算机系统的快速发展,并行计算已经成为科学和工程计算的基本支撑技术。负载平衡问题是并行计算研究的基本问题。尤其在数百个处理器以上规模的并行计算中,负载平衡问题是影响并行程序性能的关键。长期以来,负载平衡算法的研究比较广泛。但是,结合当前高性能计算机的发展和实际应用的需求,并行计算对负载平衡提出了新的要求。一方面,新的数值计算方法和高性能算法具有新的负载特征,需要构造相应的新的负载平衡算法;另一方面,许多重要的关键应用(例如:武器物理、天气预报、流体力学、惯性约束聚变等)需要在数百上千个处理器上进行并行模拟,而这种大规模应用对负载平衡研究提出了新的挑战,很多现有的负载平衡算法无法适应。因此,结合高性能计算机系统的特征和实际应用特点,设计适应数百上千个处理器的负载平衡算法是当前并行计算研究的一个重要前沿课题。负载平衡算法的研究需要结合实际应用的负载特征来进行。根据负载分布的特征,并行应用可分别用静态负载模型、动态负载模型、多约束负载模型等模型来描述,负载平衡算法可以针对不同的模型来进行。本文针对这些模型,在数百上千个处理器上,对负载平衡算法进行了系统深入的研究,取得了如下创新成果:一、针对实际应用中具有普适性的静态负载模型,本文使用图排序的思想,构造了基于最小线性排序的负载平衡算法。本文算法作为一种最小线性排序算法,与现有其他算法相比,执行速度较快,排序质量较高。在国产MPP并行机上,上千个处理器上的并行数值实验验证了算法的有效性。二、针对复杂数值模拟应用中普遍存在的动态负载不平衡问题,在现有动态负载模型的基础上,提出了图重排序模型,该模型能更好地描述负载的动态特征。在此基础上,构造了基于图重排序的负载平衡算法。新算法弥补了在处理动态负载模型时,基于最小线性排序的算法不能显式控制数据迁移开销这个缺点。数值试验说明了图重排序模型和动态负载平衡算法的有效性。三、多约束负载模型来源于多个方面,一方面现代高性能计算机的多级存储结构中速度和容量的差异要求应用程序同时平衡计算量与存储需求,另一方面多阶段模拟的多个计算过程需要同时平衡计算量。本文使用迭代法的思想,构造了一维多约束负载平衡算法。理论分析和上千个处理器上的并行数值实验验证了算法的有效性。这种算法与图排序算法结合,可以处理一般的多约束负载模型,从而推广了基于图排序的负载平衡算法的使用范围。四、自适应结构网格并行计算是科学计算中的重要方法。它的内在多尺度性造成其负载平衡问题具有巨大的难度。本文构造了一种刻画自适应结构网格并行计算负载特征的模型。针对这个模型,本文提出了一种逐层投影多约束图剖分算法。这种算法在涵盖了很多当前负载平衡算法的基础上,引进了多种新的负载平衡技术,具有较大的潜力。数值试验初步表明本文算法在减小层间通信和步间数据迁移方面有较好的效果。