研究生课程“并行算法”教学内容优化设计研究

吴建平，银福康，杨锦辉，彭 军，汪 祥

（国防科技大学 气象海洋学院，湖南 长沙 410073）

引言

传统科学研究主要采用理论研究或实验研究两种手段。理论研究或难以针对实际模型进行展开，或只能以某种近似方式进行，与真实模型存在差距；而实验研究则很难避免出现主观性误差，且因实验器材与安全性等问题又使得成本较高。自20世纪起，随着计算机的出现与发展，人们逐渐发现计算机数值模拟可以作为另一种科学研究手段。此后，计算机数值模拟得以迅速发展，并在气象海洋环境预报、核物理、飞行器设计、拱坝建设、油气藏勘探、地震预测、图像处理、分子生物学、天体物理学、材料科学等许多领域得到了越来越广泛的应用。

在实际应用中，对模拟精度要求越来越高，所要求解的问题规模越来越大，但无论处理器的工艺水平如何高，单处理器的存储与计算能力都一直满足不了许多实际应用问题对实时性、计算能力与存储需求的要求，这使得人们越来越寻求通过采用高性能并行计算机进行大规模数值模拟。但要实现高性能并行计算，既需要从计算方法的层面进行并行算法设计，又需要面向高性能并行计算机进行具体实现，其中涉及方方面面的理论与技术问题。正是在这种时代背景下，中国科技大学、清华大学、加州大学伯克利分校、哈佛大学、普渡大学、斯坦福大学、北卡罗来纳大学等国内外众多高校陆续开设并行计算相关课程，国内外不仅形成许多经典教材①《并行计算：结构·算法·编程》、《可扩展并行算法的设计与分析》、《并行计算导论》、《数值并行算法与软件》、Introduction to Parallel Computing(Second Edition)。，在教学方面也进行了一些研究②《精品课程“并行计算”的建设》《并行计算实验课程建设的实践与探讨》等。。作为国内最早进行高性能并行计算机研制与应用的单位之一，国防科技大学早在20世纪80年代即由李晓梅教授开始开设“并行算法”研究生课程。

一、“并行算法”课程概况

“并行算法”课程针对全校研究生开设，旨在通过学习基本知识、理解基本原理、运用基本技术、实践基本算法与阅读课外资料，培养学员的并行计算思维、算法抽象思维、逻辑推理能力与自主学习能力，使学生具备进行并行算法设计、实现到评估的初步能力，为气象海洋等大规模科学与工程计算领域研究生打下并行计算方面的研究与应用基础。

“并行算法”课程共36学时，其中课堂实践3学时。自20世纪90年代开设以来，经过多年发展和几代教师的经验积累，教学内容进行了多次迭代优化，现已形成包括并行计算基本概念、并行算法设计基本技术、典型并行算法与并行算法编程实践在内的内容体系，知识层次相对较高，不仅理论性较强，实践要求也较高。本文基于“并行算法”课程教学经验和实践，主要介绍教学过程中对并行计算思维训练的探索，以及基于该思维与模块化组织方式对教学内容优化设计方面的研究成果。

二、“并行算法”课程教学内容优化设计

并行计算从思维方式上可以看成计算与并行处理这两种思维的复合。计算思维强调像计算机科学家那样思考问题与求解问题，是理解问题与对求解过程进行形式化时的底层思考，计算思维要求以算法的方式求解复杂问题，强调对问题求解的可达性，且追求对计算资源的节约与求解效率的改进。并行处理思维强调任务处理时对任务的分解与同时处理，在具体高性能计算硬件基础的情况下，着重任务的可分离性和任务调度的合理性。并行计算的思维本质即如何实现对整个任务计算过程的合理规划，以实现在目标高性能并行计算机上的高效执行。同时，由于强调在高性能计算机上的可达性，并行计算非常强调设计求解过程在高性能并行计算机上的具体实现及其实际效果。

基于对并行计算思维训练与理论实践相结合的理念，考虑学生对教学内容学习与理解的便利性，与未来对教学内容的进一步优化设计，课程讲授过程中将整体教学内容从顶层分为并行计算基本概念、并行算法设计基本技术、典型并行算法与并行算法编程实践四大模块。其中，并行计算基本概念主要侧重并行计算涉及的基本理念与概念，是实施后续教学内容的基础；并行算法设计基本技术主要侧重并行算法设计的典型过程，以及在该过程中经常采用的相关技术，是整门课程的核心所在；典型并行算法主要介绍数值计算与非数值计算中遇到的经典且较为简单的并行算法，一方面用以加深对并行算法设计基本原理与常用方法的掌握，另一方面也便于在后续研究中涉及类似并行算法设计时进行参考；并行算法编程实践侧重简单的编程实现，以及利用所学知识进行典型并行算法的具体实践。之后对四大教学模块，再次进行模块化组织，形成子模块，具体如图1所示。

图1 “并行算法”课程模块组成图

（一）并行计算基本概念模块

并行计算基本概念模块主要包括采用并行计算的原因、并行计算的思维、并行计算常用概念、并行计算机的抽象及并行算法的性能评价等5个子模块。

采用并行计算的原因主要以数值天气预报与星系模拟等典型案例引入本课程，并通过对世界顶尖数值预报中心在高性能计算上的现状进行调研查阅，进一步增强对为什么需要进行并行计算的感性认识。并行计算的思维主要阐述计算思维、并行处理思维与并行计算的思维方式，以及并行处理实现上的具备硬件基础、任务可分离性与任务安排合理性三要素，并通过与日常生活中简单示例的对比，加强对并行处理思维的理解。并行计算常用概念主要采用图文结合、逐步推进的方式，从机器相关、问题相关、算法相关三方面，逐一介绍并行计算中常用的机器规模、问题规模、任务分解、并行度、分解粒度、数据相关性、任务调度、负载平衡、确定性、同步、死锁、并行执行时间、并行开销、加速比、并行效率、整机效率、可扩展性等概念，使学生对并行计算相关概念形成初步且系统的了解。同时，通过安排学生阅读并行计算相关文献，进一步掌握这些概念的英文表述，加强对并行计算思维的领悟。并行计算机的抽象围绕并行算法设计与分析所需与对目标并行计算机典型特征的抽象进行展开，包括并行计算机的互联网络、并行计算机的分类与发展、并行计算模型，其中并行计算的互联网络主要介绍静态逻辑互联网络结构，尤其侧重环、二维网格、三维网格、超立方体与星形等后续算法设计中常用的结构；并行计算机的分类与发展侧重介绍Flynn分类法，以及物理存储结构与逻辑存储结构上的不同；并行计算模型是对某类目标高性能计算机的共同抽象，主要讲授最常用的LogP模型。在进行并行计算机抽象时，着重强调物理层面与逻辑层面间的关系，物理层面是硬件本身实现层面，逻辑层面是算法设计时的虚拟层面。并行算法的性能评价主要在加速比与并行效率等基本概念的基础上，面向并行算法在处理器个数增大情况下的潜在性能表现，着重介绍影响加速比的主要因素，Amdahl与Gustafson等经典加速比定律，以及并行算法的可扩展性分析与等效率分析方法。

（二）并行算法设计基本技术模块

并行算法设计基本技术模块包括基本通信操作、常用任务分解、常用任务调度、常用设计模式、减小交互开销影响的常用方法等5个子模块。

基本通信操作主要针对常用拓扑结构，如线性阵列、网格与超立方体等，介绍常用的广播、规约、分散、收集、多对多私有通信等涉及多个处理器的通信操作，既作为引子也是最简单的并行算法，提高并行计算的思维能力，又强化对并行计算模型用途的认识与便于在需要时熟练应用。常用任务分解主要介绍嵌套分解与数据划分等常用的任务分解技术，其中嵌套分解强调对基于分治策略相关算法设计的适用性以及具体的使用方式；数据划分强调对以数据为中心的并行算法设计的适用性，主要侧重于输出划分、输入划分、中间结果划分与图划分等最常用的技术，结合实例进行介绍，并重点注重区分各自适用范围与各自受到的约束，真正提高学生对各种方法的掌握与实际应用水平。常用任务调度主要介绍数组分布与图划分等常用静态调度技术，以及集中式动态调度技术，其中数组分布主要通过数值天气预报等问题中常用的Stencil计算重点介绍块分布及其优缺点；通过数值天气预报谱模式中谱空间负载平衡算法等重点介绍循环块分布及其优缺点；通过污染物扩散、稀疏矩阵稠密向量乘等问题，介绍图划分算法及其优缺点。常用设计模式主要介绍数据并行计算、流水线、工作池、任务图与主从等常用设计模式，侧重前两种针对静态调度和第三种对动态调度等最常用的技术，并结合并行计算的思维进行介绍。减小交互开销影响的方法主要包括最大化数据局部性、最小化竞争与热点、计算与交互重叠、数据复制或重复计算、利用优化过的聚合交互操作、将交互开销相互重叠等编程实现时的常用技术，主要结合具体实例进行介绍。

（三）典型并行算法模块

典型并行算法模块包括并行排序算法、稠密矩阵并行算法、稀疏线性方程组并行求解、FFT并行算法等4个子模块。

并行排序算法是典型的非数值并行算法，主要涉及算法确定性高且计算复杂度相对较低的双调排序及其并行算法，以及计算复杂度量阶最小的快速排序及其并行算法，着重关注双调排序算法与网络间对应关系和快速排序算法中数据划分与嵌套分解相结合的分解技术。稠密矩阵并行算法主要从稠密矩阵向量并行乘、稠密矩阵并行乘与基于LU分解的稠密线性方程组并行求解等知识点进行教学，着重关注较为简单且与基本理论结合度非常紧密的前两类算法。稀疏线性方程组并行求解主要讲授最典型的三对角线性方程组并行分裂法、Jacobi迭代并行算法、SOR型迭代并行算法、一般迭代法的并行算法等，着重关注简单但富有独特性的并行分裂法、Jacobi型迭代法，以及SOR迭代的红黑排序算法。FFT并行算法是与二进制、超立方体逻辑拓扑结构密切相关的典型快速算法，其并行算法教学主要讲授基于按位交换与基于数组重分布两类并行算法，并着重强调其对其他快速算法并行算法设计的参考意义。

（四）并行算法编程实践模块

并行算法编程实践模块包括分布存储并行算法MPI实现、共享存储并行算法OpenMP实现、并行程序的课堂实践共3个子模块。

分布存储并行算法MPI实现主要介绍实现最简单MPI编程的6个基本函数，以及结合减少交互开销影响方法的理论知识，介绍在MPI中的相关实现措施。实现简单MPI并行程序的6个基本函数是该子模块的核心和最重要内容，旨在让学生能直接动手实践，并增强对并行计算的感性认识。共享存储并行算法OpenMP实现主要介绍基本指导语句、基本库函数与环境变量，旨在培养学生采用OpenMP进行并行计算的基本能力，侧重Parallel与循环指导语句，以及数据属性子句与环境变量等内容。同时，与MPI编程实现进行对照，理解二者各自优缺点及各自适用性。并行程序的课堂实践主要从矩阵乘并行算法与Jacobi迭代并行算法中挑选其一，进行MPI编程实现，并进行并行算法与所编并行程序的性能评估，以培养与检验学生对已经设计好的并行算法，直接进行简单编程实践，并对所编写并行程序进行正确性验证，与对并行程序进行性能分析评估，以及基于此的可能优化改进途径分析等方面的能力。

本课程中的编程实践侧重于最基本的编程实现，主要用于增强学生的学习兴趣，提高学生动手能力，进而进一步加深学生对所学基本概念与基本理论知识的理解与掌握，同时强化对并行算法设计、实现到评价全过程的了解。同时，对并行程序进行课堂实践，课堂上未完成者允许其课后自行完成，但强调完成时的自主性，通过同时提交并行程序代码与实践报告进行考核。

结语

本文对国防科技大学“并行算法”课程教学团队近年来在课程内容改革方面的探索进行了介绍，并着重阐述了在整个教学过程设计从任务分解、任务调度，到算法设计全过程中，对并行计算思维训练的考虑，以及结合并行计算思维训练与理论实际结合理念下的教学内容模块化组织改革探索，在将整个教学内容组织成并行计算基本概念、并行算法设计基本技术、典型并行算法与并行算法编程实践四大模块的基础上，再对每个模块再按子模块的方式进行组织。组织过程中，着重强调典型并行算法与并行算法编程实践两模块主要侧重于加深对基本理论知识的理解，强化并行计算思维的训练。教学内容的优化设计，改进了课程内容的组织方式与教学实施的便利性，也更有利于促进学生综合素质的提高。