稀疏线性代数方程组迭代法中的预处理技术研究.ppt

混凝土材料断裂过程模拟程混凝土材料断裂过程模拟程序中的高性能并行算法开发序中的高性能并行算法开发吴建平、王正华吴建平、王正华国防科学技术大学计算机学院国防科学技术大学计算机学院并行与分布处理国防科技重点实验室并行与分布处理国防科技重点实验室报告内容报告内容v 原串行程序的结构与特点原串行程序的结构与特点v 单机计算速度的提升方法单机计算速度的提升方法v 并行算法设计时的若干关键并行算法设计时的若干关键 问题简介问题简介v 对高性能计算的几点看法对高性能计算的几点看法原原串行程序的结构特点串行程序的结构特点原原串行程序的结构特点串行程序的结构特点(续续)问题规模：问题规模：44117个网格点个网格点 系数矩阵的总外形约系数矩阵的总外形约649M，分解需要约分解需要约3.3T个浮点操作个浮点操作 2.53GHz，1G内存：内存：CVF Debug模式，默认优化编译模式，默认优化编译 一次加载所发费的时间约一次加载所发费的时间约18.01小时；小时；Asesk子程序所发费的时间约子程序所发费的时间约17.9小时；小时；Demove总共需要约总共需要约17.78小时；小时；Foba所发费的时间共约所发费的时间共约7.3分钟；分钟；Demove占占总时间总时间98.74%，Demove+Foba的时间的时间 约占总时间的约占总时间的99.42%；原串行程序的结构特点原串行程序的结构特点(续续)CVF Release模式，最佳优化编译模式，最佳优化编译 一次加载内一次加载内Asesk子程序约需子程序约需2.92小时；小时；Demove总共约需总共约需2.87小时；小时；Foba所发费的时间约所发费的时间约7.3分钟；分钟；Asesk+Foba的时间占总时间的时间占总时间99%左右；左右；分成分成21块计算时，辅存需要块计算时，辅存需要6个多个多G。报告内容报告内容v 原串行程序的结构与特点原串行程序的结构与特点v 单机计算速度的提升方法单机计算速度的提升方法v 并行算法设计时的若干关键并行算法设计时的若干关键 问题简介问题简介v 对高性能计算的几点看法对高性能计算的几点看法单机计算速度的提升方法单机计算速度的提升方法 程序优化技术程序优化技术 循环调换循环调换 将重复计算缩减为一次将重复计算缩减为一次 浮点除法替换为浮点乘法浮点除法替换为浮点乘法 将循环内的计算尽可能外提将循环内的计算尽可能外提单机计算速度的提升方法单机计算速度的提升方法(续续)将直接法改进为预条件将直接法改进为预条件CGCG法法 迭代法内主要是矩阵乘向量，矩阵每行约迭代法内主要是矩阵乘向量，矩阵每行约81 个非零元，对个非零元，对44117个网格点的问题，一次个网格点的问题，一次 矩阵向量乘只要矩阵向量乘只要21.4M个浮点操作个浮点操作 选取选取ICT(50,10-3)预条件时，预条件构造时间预条件时，预条件构造时间 19.6秒，秒，129次预条件迭代时间共次预条件迭代时间共38.31秒，残秒，残 量量2范数与右端项范数与右端项2范数的比值达范数的比值达7.410-11。单机计算速度的提升方法单机计算速度的提升方法(续续)先进的全局刚度矩阵装配技术先进的全局刚度矩阵装配技术 逐单元装配法逐单元装配法开辟有限的存储空间，用其对每个单元的信息逐步开辟有限的存储空间，用其对每个单元的信息逐步存储，用指针指明各未知量对应的行中各元素的列存储，用指针指明各未知量对应的行中各元素的列号与值。空间不足时，对相关单元都已存储的未知号与值。空间不足时，对相关单元都已存储的未知量对应的行进行装配，并倒空。量对应的行进行装配，并倒空。直接逐行全局装配法直接逐行全局装配法直接利用指针来链接每个未知量所直接联系到的所直接利用指针来链接每个未知量所直接联系到的所有单元与在单元中的局部编号，逐未知量进行装配有单元与在单元中的局部编号，逐未知量进行装配报告内容报告内容v 原串行程序的结构与特点原串行程序的结构与特点v 单机计算速度的提升方法单机计算速度的提升方法v 并行算法设计时的若干关键并行算法设计时的若干关键 问题简介问题简介v 对高性能计算的几点看法对高性能计算的几点看法并行算法设计时的若干关键问题并行算法设计时的若干关键问题v 全局并行计算策略全局并行计算策略v 整体刚度矩阵的并行装配整体刚度矩阵的并行装配v 稀疏线性方程组的并行求解稀疏线性方程组的并行求解v 稀疏向量的全局并行相加稀疏向量的全局并行相加全局并行计算策略全局并行计算策略v 全局按单元进行任务分配全局按单元进行任务分配v 对各个小数组，从对各个小数组，从0 0号进程读入号进程读入 后，广播到其他进程后，广播到其他进程v 最后一维为未知量个数的数组最后一维为未知量个数的数组 在每个进程上都保存一份在每个进程上都保存一份v 稀疏线性方程组的并行求解按稀疏线性方程组的并行求解按 未知量个数进行任务分配未知量个数进行任务分配整体刚度矩阵的并行装配整体刚度矩阵的并行装配v 确定与每个未知量直接相关的确定与每个未知量直接相关的 局部单元个数局部单元个数v 在每个进程上进行局部装配在每个进程上进行局部装配v 对各个进程上的局部矩阵进行对各个进程上的局部矩阵进行 累加，得到整体刚度矩阵累加，得到整体刚度矩阵v 每个进程对局部每一行中的非每个进程对局部每一行中的非 零元按列号进行排序零元按列号进行排序稀疏线性方程组的并行求解稀疏线性方程组的并行求解v 稀疏矩阵与向量的并行乘法稀疏矩阵与向量的并行乘法 该操作的通信结构始终不变，事先确定通该操作的通信结构始终不变，事先确定通 信结构后，再在后续迭代中反复用其收集信结构后，再在后续迭代中反复用其收集 局部计算需要用到的其他进程上的分量局部计算需要用到的其他进程上的分量v ICTICT预条件的并行化预条件的并行化 ICCP2003ICCP2003：局部分解并行化技术局部分解并行化技术v 并行对角元归一化算法并行对角元归一化算法稀疏向量的全局并行相加稀疏向量的全局并行相加 对最后一维长为未知量个数的向量，对最后一维长为未知量个数的向量，有的是从有限元信息得到的，所以得到的有的是从有限元信息得到的，所以得到的局部向量是稀疏的，要采用稀疏向量技术局部向量是稀疏的，要采用稀疏向量技术进行存储，也要采用稀疏向量技术进行并进行存储，也要采用稀疏向量技术进行并行累加来得到全局结果向量，以减少计算行累加来得到全局结果向量，以减少计算时间。时间。计算效果v 机器：机器：Sun6800,4Sun6800,4个个CPUCPU，8G8G内存内存v 问题：问题：7101771017个网格点，个网格点，7880078800个单元个单元v 第第1 1次加载约需次加载约需6060秒秒v 第第2 2次到第次到第5858次加载每次约需次加载每次约需5050秒秒v 总共需要计算总共需要计算9494次加载，估计大约只次加载，估计大约只 要要3 3个小时左右。个小时左右。对更对更大规模机器的需求大规模机器的需求 虽在虽在4 4 CPUCPU的的Sun6800Sun6800上，求解上，求解7101771017 个网格点的问题只要个网格点的问题只要3 3个小时，但随个小时，但随 问题规模的增大，计算时间将大幅增问题规模的增大，计算时间将大幅增 加，为实时计算，必须增大机器规模加，为实时计算，必须增大机器规模 当当问题规模大幅增加时，物理内存不问题规模大幅增加时，物理内存不 足也将影响问题求解，从而也需要增足也将影响问题求解，从而也需要增 大机器规模大机器规模对对不同模型对应程序改造的代价不同模型对应程序改造的代价 对编译好的可执行程序，输入都集中对编译好的可执行程序，输入都集中 在在3 3个文件中；个文件中；开发的核心算法形成了软件包，只需开发的核心算法形成了软件包，只需 要对主体计算程序进行与本程序类似要对主体计算程序进行与本程序类似 的修改，调用该软件包中的子程序；的修改，调用该软件包中的子程序；整体刚度矩阵并行装配只需要调用整体刚度矩阵并行装配只需要调用1 1 或或5 5个子程序；个子程序；对对不同模型对应程序改造的代价不同模型对应程序改造的代价(续续)稀疏向量的并行相加只要调用稀疏向量的并行相加只要调用1 1个子个子 程序；程序；稀疏线性方程组的并行求解可以只调稀疏线性方程组的并行求解可以只调 用用5 5到到6 6个子程序来实现。个子程序来实现。结论：在核心算法以软件包形式存在结论：在核心算法以软件包形式存在 的前提下，对其它模型对应程序进行的前提下，对其它模型对应程序进行 改造的代价并不大改造的代价并不大推广应用前景推广应用前景 针对其它有限元计算问题，可以将这里针对其它有限元计算问题，可以将这里 所开发的软件直接进行移植与推广所开发的软件直接进行移植与推广 针对非有限元，但涉及到线性方程组的针对非有限元，但涉及到线性方程组的 问题，可以开发类似的并行计算方法问题，可以开发类似的并行计算方法 针对一般的计算问题，可以将并行开发针对一般的计算问题，可以将并行开发 的实践经验进行推广应用的实践经验进行推广应用报告内容报告内容v 原串行程序的结构与特点原串行程序的结构与特点v 单机计算速度的提升方法单机计算速度的提升方法v 并行算法设计时的若干关键并行算法设计时的若干关键 问题简介问题简介v 对高性能计算的几点看法对高性能计算的几点看法对高性能计算的几点看法对高性能计算的几点看法 对计算资源进行集中调度与使用对计算资源进行集中调度与使用 软件开发要跟上硬件设施的采购软件开发要跟上硬件设施的采购 并行算法是一门大学问并行算法是一门大学问 自动并行技术与解题环境也是研究趋势自动并行技术与解题环境也是研究趋势 之一之一对计算资源进行集中调度与使用对计算资源进行集中调度与使用 计算资源可能分布在各地计算资源可能分布在各地 各个单位对资源的使用存在淡季与旺季，各个单位对资源的使用存在淡季与旺季，不利于对资源的充分利用不利于对资源的充分利用 资源的集中调度与使用可以提高利用率，资源的集中调度与使用可以提高利用率，也有利于对系统的集中统一维护也有利于对系统的集中统一维护软件开发要跟上硬件设施的采购软件开发要跟上硬件设施的采购 硬件采购是用来解决实际问题的，实际问题的解决硬件采购是用来解决实际问题的，实际问题的解决 只有硬件是不够的，需要同时开发相应的软件只有硬件是不够的，需要同时开发相应的软件 软件开发时，要注意对现有硬件与软件资源的充分软件开发时，要注意对现有硬件与软件资源的充分 利用。例如，对这里的问题：利用。例如，对这里的问题：o 内存不足时可以利用辅存来减少内存不足时可以利用辅存来减少swapswap时间时间 实践证明，在实践证明，在sunsun机器上，该策略非常有效机器上，该策略非常有效o SunSun高性能库的调用高性能库的调用 SunSun高性能库是针对特定机器开发的数学函数库，高性能库是针对特定机器开发的数学函数库，调用库中函数可提高效率调用库中函数可提高效率o 利用利用S3LS3L可能将进一步提升计算速度可能将进一步提升计算速度并行算法是一门大学问并行算法是一门大学问 并行程序开发并不是自动并行编译能完全解决的并行程序开发并不是自动并行编译能完全解决的 并行算法也并不是直接调用某些并行库就行的，并并行算法也并不是直接调用某些并行库就行的，并 非所有并行算法都可以通过这种方法来实现非所有并行算法都可以通过这种方法来实现 并行算法也不是学会并行算法也不是学会MPIMPI或或OpenMPOpenMP编程就行的，算编程就行的，算 法设计的本质是思想，并行算法也不例外法设计的本质是思想，并行算法也不例外 高效并行程序的设计涉及体系结构、并行程序设高效并行程序的设计涉及体系结构、并行程序设 计、并行计算方法、性能分析与评测等许多问题计、并行计算方法、性能分析与评测等许多问题 正确高效的并行算法涉及涉及到计算机、数学、正确高效的并行算法涉及涉及到计算机、数学、物理等许多学科，稀疏线性方程组的高效并行求物理等许多学科，稀疏线性方程组的高效并行求 解也不例外解也不例外谢谢！谢谢！谢谢！谢谢！