并行算法课程的教学与探讨

1、 “并行算法”课程的教学与探讨徐 云 孙广中 郑启龙 吴俊敏 陈国良（中国科学技术大学计算机科学技术系，安徽 合肥 230027） 摘 要：现在许多高校在算法课程中加入了并行算法的内容，随着高性能计算技术的发展和普及，会有越来越多的学校单设并行算法课程。本文结合作者多年讲授并行算法课程的教学体会，就如何教好与学好这门课程进行了讨论并给出了一些建议和意见。 关键词：并行算法；教学探讨；课程建设 中图分类号： TP30 文献标识码： ATeaching a Course in Parallel AlgorithmsXU Yun, SUN Guang-zhong, ZHENG Qi-long,WU

2、Jun-min, CHEN Guo-liang(University of Science and Technology of China, Hefei, Anhui 230026) Abstract: With the development and popularization of high-performance computing technology, more and more universities will offer parallel algorithm courses. Based on years of teaching experience, suggestions

3、 and advice are offered as to how to effectively teach a course in parallel algorithms. Key words: parallel algorithm; discussion of teaching; course building一、课程的背景和定位中国科学技术大学计算机系在上世纪80年代初便开展了并行算法的研究，1984年由陈国良教授率先搬上大学讲台。二十几年来，随着并行处理技术的发展，我们围绕着并行算法的课程教学，相继开设了并行计算机体系结构、并行程序设计、并行计算等并行算法类课程，逐步形成了一套较为完整

4、的并行算法类课程教学体系。课程受益面从计算机专业的研究生扩大到本科生，从计算机专业拓宽到面向计算的非计算机专业。2001年以来先后在贵州、成都、太原、大连、深圳等地举行课程讲习班，使得并行算法类课程逐步推广和辐射到全国各主要地区。2003年，“并行计算”获国家级精品课程，其教学团队带头人陈国良教授荣获教育部首届高等学校教学名师奖。“并行算法”课程是并行算法类课程体系中的核心课程，主要面向计算机专业的研究生，是体系结构专业的必修课。本课程是属于算法研究的三个层次（并行算法理论、并行算法的设计和分析、并行算法的实现）的中间层次，它不去重点研究算法理论中的某些基本问题，而是着重研究可有效并行求解问题

5、类（即用多项式数目的处理器可在对数多项式时间内求解的NC类问题）的算法设计和分析方法，而且也略去了并行算法的具体实现环节（如并行语言、编译、执行环境与工具等）。本课程也是遵循计算机学科中有关算法研究的经典内容进行组织的，它严格区别于并行数值计算类课程（这些课程主要是研究数学计算原理、方法、精度与稳定性等问题）。二、教材的建设和发展 本课程的教材建设自上世纪80年代初开始，至今已有20余年。前10年，主要围绕着“并行排序和选择”“VLSI并行算法”“并行图论算法”等课程开展非数值并行算法方面的教学研究工作，先后出版了并行算法排序和选择（1990）1，VLSI计算理论与并行算法（1991）2和并行

6、图论算法（1991）3。在此基础上，于1994年出版了并行算法的设计与分析（初版）4，并将该教材运用于计算机专业的研究生课程教学中。后10年，为了适应国外和我国高性能并行机的迅速发展以及满足国家培养高性能并行计算高级人才的需要，同时配合国家教育部高等学校计算机科学技术教学指导委员会将“并行计算”列为国家“九五”课程建设规划，我们对教材进行了部分充实和补充，于2002年出版了并行算法的设计与分析（修订版）5。目前，随着高性能计算的不断深入和个人电脑多核化的普及， 我们对教材进行了重新审定和规划，准备出版该教材的第3版。三、课程内容的讲授 本课程以并行计算模型为主线，讨论各种并行计算模型上计算机学

7、科中常用的各种基本、典型的并行算法的设计和分析方法。主要包括：并行机结构模型，并行计算模型和并行算法基本知识；各种模型上的非数值并行算法（排序，选择，组合搜索，串匹配，图论算法等）；数值并行算法（矩阵运算，线性方程组求解，FFT算法等）；并行计算理论（计算模型的等价性及其能力，下界，NC类计算问题等）。讲授这些内容时应强调并行计算模型和并行算法的设计融为一体，注重讨论并行算法的基本设计技术，展现各种常用计算问题的求解过程和方法，并力图反映本学科的最新成就与学科发展前沿。 1. 建议的讲授内容和学时分配由于并行算法的内容十分广泛，因受课时的限制，所以并非书中的全部内容都须一一讲到。根据作者多年讲

8、授并行算法课程的体会，按本课程教材并行算法的设计与分析（修订版）5，具体讲授章节和学时分配如表1所示。表1 建议的讲授章节和学时安排建议的讲授章节供参考的学时分配第一章：1.1，1.2，1.44第二章：2.12.5，2.74第三章：3.1，3.22第四章：4.1，4.2，4.5，4.74第五章：5.1，5.32第六章：6.2，6.5，6.62第八章：8.2，8.3，8.44第九章：9.19.34第十二章：12.1，12.2，12.44第十三章：13.1，13.3，13.44第十四章：14.1，14.33第十五章：15.115.44第十六章：16.1，16.4，16.63第十七章：17.117.

9、3，17.54第十八章：18.1，18.2，18.5，18.64第十九章：19.1，19.3，19.53第二十章：20.1，20.2，20.53 2. 讲授的要点和重点全书总共二十章，大体可分为三大部分：(1)并行算法基础；(2)各种常用计算问题的并行算法设计；(3)一些算法理论问题。其中第2部分所占篇幅最大。我们在多年的教学过程中归纳出以下的讲授和学习要点，仅供大家参考：第一部分：并行算法的基础知识及其基本设计技术(1)并行算法基础并行计算机体系结构（PVP: 并行向量处理机系统；SMP: 对称多处理机系统；MPP: 大规模并行处理机系统；DSM: 分布共享存储系统；COW: 工作站机群系统

10、)。并行计算机互连网络（静态互连网络: LA, RC, MC, TC, HC, CCC；动态互连网络: Buses, Crossbar, MIN）。并行计算模型（PRAM, APRAM, BSP, LogP等）。并行算法的一般概念（定义、分类、表达、度量等）。(2)并行算法的基本设计技术（划分法、分治法、平衡树法、倍增法、流水线法等）。第二部分：各种常用计算问题的并行算法设计(1)各种专用和通用计算模型上的排序和选择(比较器网络上的算法；同步算法；异步和分布式算法)。(2)数据传输与选路（选路算法的概念、分类；二维网孔上的选路算法；超立方网络上的随机选路算法；数据的分布和集中）。(3)并行串匹

11、配（SIMDSM上的非周期串和周期串的匹配算法；模式预处理）。(4)矩阵和线性方程组求解等数值计算（矩阵运算: 转置、相乘以及矩阵乘向量；线性方程组求解: 高斯消去法、GaussJordan法、GaussSeidel法，偏微分方程求解，矩阵的特征根与特征向量等）。(5)FFT和卷积与滤波（DFT直接并行算法；SIMDBF上的FFT并行算法）。(6)图论算法（图的并行搜索；传递闭包；连通分量；最短路径等）。(7)图像分析和计算几何（分量标定；包含问题；构造问题等）。(8)搜索问题（线性表上的搜索；组合搜索等）。第三部分：一些算法理论问题(1)随机算法（随机并行算法的模型和度量；随机算法的设计方法

12、；部分独立集问题的并行随机算法；多项式恒等的验证并行随机算法；并行随机快排序算法）。(2)VLSI计算理论（VLSI算法复杂度的度量标准；VLSI电路模型和计算模型；典型计算图的结构布局法；分治布局法）。(3)模型与下界（不同PRAM模型的相互模拟；PRAMCREW的下界；PRAMCRCW的下界；P完全理论: P类与NC类、P完全问题、NC类与非NC类）。四、教学形式的组织 1. 多媒体教学由于并行算法课程的内容较多，因此传统的教师在讲台上板书、学生在课堂上记笔记的教学手段，已经无法满足现在的大纲要求和进度了。所以本课程的课堂讲授和例题解答均使用了多媒体设备，同时，中国科学技术大学的网络建设也

13、为网上教学提供了方便。我们在网上设立了“并行算法类教学网站”()，并行算法课程主讲老师将课程的教学大纲、讲授与学习要点、参考书目等均放在相关的课程网页上，学生可自由访问。 2. 特邀讲座本课程的特色之一是安排了若干次校内外知名专家和学者的特邀讲座，使同学们了解本学科的最新成就与学科发展前沿。在今年上学期的课程中，我们特地邀请了在串匹配、图像处理等方面的资深专家做了相关讲座，深受同学们的欢迎和好评。 3. 作业和课程论文通过作业和课程论文的教学环节，可以将“学习和研究”紧密地结合起来。课程论文研究是从文献阅读到选择研究题目，从设计和实验到结果分析论证，从数据和资料到整理成文的全过程，学生通过这种

14、研究性学习培养了学生追踪本学科领域最新进展和提高自主学习和独立研究的能力。 4. 实验上机实践是并行算法教学中不可或缺的重要环节，应得到足够的重视。目前由于PC 机群的普及，很多单位、学校，甚至实验室都可很容易地搭建PC 机群，这为并行算法课程上机实践提供了切实可行的实验平台。鉴于当前MPI 的广泛使用，建议实验中以MPI 的使用为主，要求每个人均能独立地用MPI 编程实现某一个典型的并行数值或非数值并行算法，从而了解并行程序的基本编写、调试和运行的全过程。随着高性能计算技术的发展和普及，越来越多的高校将开设并行算法课程。因此，探索并行算法课程的教学，不断提高学生的创新思维和能力，便成为教学改革的重要研究内容。本文针对并行算法课程，结合作者多年来教学的体会，对课程的定位、教学内容的组织以及教学形式进行了一些探讨，希望对从事并行算法教学的教师和学习该课程的学生有所帮助