随着高性能计算机的飞速发展和数值计算方法的日趋成熟,并行计算已成为求解大规模科学与工程问题的基本支撑技术。大规模并行计算的首要任务就是合理地分配计算资源,一方面希望平衡各处理器的计算负载,缩短处理器的空闲等待时间;另一方面希望减少处理器之间的通信开销,缩短通信时间,提高并行性能。超图剖分策略以顶点表示计算负载,以超边表示数据依赖关系,通过最小化处理器间的公共超边来求解上述负载平衡问题,是一个极其有效的方法。其度量模型更加准确,剖分质量更加优秀,成为近年来备受研究者关注的热点问题。然而,面对日益复杂的应用问题,许多现有的超图剖分算法已无法适应日益变化的应用需求。本文的研究工作围绕面向非结构网格CFD计算的多层超图剖分算法展开。针对多层算法的粗化、初始剖分、精化阶段展开深入研究,提出了一系列满足CFD计算实际需要的启发式算法,并将设计的多层算法应用于大规模CFD计算问题中,具有重要的理论研究意义和实际应用价值。本文的主要研究成果如下:(1)提出了基于顶点等级制度的加权内积匹配粗化算法。讨论了现有粗化算法存在的问题,分析了粗化阶段的重要性及对剖分性能的影响。提出以公共超边为度量基础的加权内积匹配制度,来隐藏更多边权;通过顶点权重确定访问次序,通过顶点的邻接度影响匹配优先级,来产生更高的粗化率。基于上述思想,提出基于顶点等级制度的加权内积匹配(HWIPM)粗化算法。数值实验表明,该算法在粗化率、边权隐藏、运行时间各方面均表现出较大的优势,并对最终的剖分性能产生了积极影响。(2)提出了基于锁定收益的直接K路剖分遗传精化算法。分析了直接K路剖分较递归二路剖分的优势,并针对存在的问题,提出两种优化策略:一是提出基于二叉堆的顶点收益优先级维护策略,将其应用于K路边界精化中,大大降低了算法的复杂性;二是提出锁定收益的计算方法,将其应用于顶点的移动过程中,较大地减少了剖分截权。综合上述策略,提出基于锁定收益的K路(LKFM)精化算法,并结合遗传算法的全局寻优能力,形成邻域搜索采用LKFM算法,全局优化采用遗传算法的直接K路(MHGA)精化算法。数值实验表明,该算法在剖分截权、运行时间各方面均表现出明显的优势。(3)提出了基于截权和最大子区外接度最小化的多目标粒子群精化算法。研究了最小化截权和最大子区外接度的重要性及两者之间的对立统一关系,提出建立多目标模型对该问题进行优化。针对这一问题,在最小化截权的基础上,基于分层排序和线性加权相结合的方法,提出分阶段多目标MKFM精化算法,并将其与粒子群算法结合,形成MHPSO精化算法。数值实验表明,该算法在保证剖分截权较优、且不明显增大运行时间的前提下,在最小化最大子区外接度方面表现出明显优势,该优势在CFD计算领域尤为突出。(4)实现了多层超图剖分研究成果在非结构网格CFD并行计算中的应用。将所研究的多层超图剖分算法应用于非结构网格CFD计算,形成以超图剖分为分解策略,以MPI消息传递为通信手段的并行数值模拟。针对三个典型算例,在天河一号超级计算机上进行了剖分性能与正确性分析,并比较了不同的剖分方法对并行性能的影响。实验结果表明,本文提出的剖分方法应用于非结构网格CFD计算时,能保证计算结果的正确性,提供较高的并行效率,具有良好的可扩展性。