“并行算法”课程的教学与探讨徐云孙广中郑启龙吴俊敏陈国良（中国科学技术大学计算机科学技术系，安徽合肥230027）摘要：现在许多高校在算法课程中加入了并行算法的内容，随着高性能计算技术的发展和普及，会有越来越多的学校单设并行算法课程。本文结合作者多年讲授并行算法课程的教学体会，就如何教好与学好这门课程进行了讨论并给出了一些建议和意见。关键词：并行算法；教学探讨；课程建设中图分类号：TP30文献标识码：ATeachingaCourseinParallelAlgorithmsXUYun,SUNGuang-zhong,ZHENGQi-long,WUJun-min,CHENGuo-liang(UniversityofScienceandTechnologyofChina,Hefei,Anhui230026)Abstract:Withthedevelopmentandpopularizationofhigh-performancecomputingtechnology,moreandmoreuniversitieswillofferparallelalgorithmcourses.Basedonyearsofteachingexperience,suggestionsandadviceareofferedastohowtoeffectivelyteachacourseinparallelalgorithms.Keywords:parallelalgorithm;discussionofteaching;coursebuilding一、课程的背景和定位中国科学技术大学计算机系在上世纪80年代初便开展了并行算法的研究，1984年由陈国良教授率先搬上大学讲台。二十几年来，随着并行处理技术的发展，我们围绕着并行算法的课程教学，相继开设了并行计算机体系结构、并行程序设计、并行计算等并行算法类课程，逐步形成了一套较为完整的并行算法类课程教学体系。课程受益面从计算机专业的研究生扩大到本科生，从计算机专业拓宽到面向计算的非计算机专业。2001年以来先后在贵州、成都、太原、大连、深圳等地举行课程讲习班，使得并行算法类课程逐步推广和辐射到全国各主要地区。2003年，“并行计算”获国家级精品课程，其教学团队带头人陈国良教授荣获教育部首届高等学校教学名师奖。“并行算法”课程是并行算法类课程体系中的核心课程，主要面向计算机专业的研究生，是体系结构专业的必修课。本课程是属于算法研究的三个层次（并行算法理论、并行算法的设计和分析、并行算法的实现）的中间层次，它不去重点研究算法理论中的某些基本问题，而是着重研究可有效并行求解问题类（即用多项式数目的处理器可在对数多项式时间内求解的NC类问题）的算法设计和分析方法，而且也略去了并行算法的具体实现环节（如并行语言、编译、执行环境与工具等）。本课程也是遵循计算机学科中有关算法研究的经典内容进行组织的，它严格区别于并行数值计算类课程（这些课程主要是研究数学计算原理、方法、精度与稳定性等问题）。二、教材的建设和发展本课程的教材建设自上世纪80年代初开始，至今已有20余年。前10年，主要围绕着“并行排序和选择”“VLSI并行算法”“并行图论算法”等课程开展非数值并行算法方面的教学研究工作，先后出版了《并行算法——排序和选择》（1990）［1］，《VLSI计算理论与并行算法》（1991）［2］和《并行图论算法》（1991）［3］。在此基础上，于1994年出版了《并行算法的设计与分析》（初版）［4］，并将该教材运用于计算机专业的研究生课程教学中。后10年，为了适应国外和我国高性能并行机的迅速发展以及满足国家培养高性能并行计算高级人才的需要，同时配合国家教育部高等学校计算机科学技术教学指导委员会将“并行计算”列为国家“九五”课程建设规划，我们对教材进行了部分充实和补充，于2002年出版了《并行算法的设计与分析》（修订版）［5］。目前，随着高性能计算的不断深入和个人电脑多核化的普及，我们对教材进行了重新审定和规划，准备出版该教材的第3版。三、课程内容的讲授本课程以并行计算模型为主线，讨论各种并行计算模型上计算机学科中常用的各种基本、典型的并行算法的设计和分析方法。主要包括：并行机结构模型，并行计算模型和并行算法基本知识；各种模型上的非数值并行算法（排序，选择，组合搜索，串匹配，图论算法等）；数值并行算法（矩阵运算，线性方程组求解，FFT算法等）；并行计算理论（计算模型的等价性及其能力，下界，NC类计算问题等）。讲授这些内容时应强调并行计算模型和并行算法的设计融为一体，注重讨论并行算法的基本设计技术，展现各种常用...