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