基于工作流模型驱动的并行算法设计教学方法

摘 要：《并行算法设计》属于高等计算机程序设计的主要课程之一，其主要难点集中在如何将特定的并行求解模型转化为具体的程序设计语言。传统的教学方法主要通过讲授并行程序设计语言来实现教学目标，已有的教学实践经验显示该方法存在的诸多不足之处。对此，本文提出了一种基于模型驱动的教学方法，其核心思想是：以并行问题求解模型为教学主线，通过分析与讲授并行问题求解模型的基本特征以及不同模型之间的异同来向学生传授并行算法的关键思想和技巧。该方法的主要优点是：实现了算法设计思想与具体程序语言的独立性，能有效地引导学生掌握并行问题求解的关键思想和技巧，激发了学生利用简单模型来求解复杂问题的兴趣。

关键词：并行计算 算法设计 工作流 教学改革

中图分类号：G4 文献标识码：A 文章编号：1672-3791（2013）05（a）-0167-03

高性能计算机是一个国家经济和科技实力的综合体现，也是促进经济、科技发展，社会进步和国防安全的重要基础。近年来，随着大规模集成电路技术的不断进步没，各类万亿次并行计算机被成功的研发和投入使用[1，2]。相对硬件的高速发展而言，并行程序设计和软件开发则处于相对落后的阶段。当前，我国各类大学都针对计算机专业的高年级本科和研究生开设了《并行算法设计》这一课程，其目标在于培养具有分析、解决并行程序设计问题能力的人才，从而提高我国在并行软件系统设计方面的整体实力。

过去若干年的教学实践显示，《并行算法设计》课程在教学过程中存在以下具有挑战性的难点[3-4]：（1）并行问题模型具有较高的抽象度，即使具有程序设计经验的学生也难以准确理解具体并行问题的抽象表达方式；（2）并行算法设计与实现难于在实际系统中部署和测试，学生很少能够获得感性的编程实践经验，从而导致学习的积极性下降；（3）现有的各种并行编程环境通常不具备兼容性，在一种编程环境中所获得的知识通常难于有效地应用到其它编程环境下；（4）并行执行环境的调试难度极大，传统的程序调试技巧基本不能应用于并行执行环境。

传统的《并行算法设计》课程的主要教学方式是：通过选择一种并行程序语言来向学生教授并行算法设计的相关知识。这种基于语言驱动的教学方法已经沿用了若干年，其在教学效果上的不足之处也日益受到人们的关注，主要体现在：（1）教学内容集中在并行程序设计语言的语法层面，容易误导学生认为并行程序设计和传统的程序设计差别不大[5]；（2）授课内容与特定的编程环境高度耦合，难以帮助学生树立正确的“并行程序设计思想”，从而使得学生不能获得独立的分析问题和解决问题的能力[6]；（3）强调特定并行问题的求解技巧，忽略各类并行问题模型中存在共性，从而使得学生不能有效地应对现实环境中碰到的各类新问题[7]；（4）只强调程序设计结果的编译正确性，忽略程序在执行和维护过程中的健壮性和鲁棒性，从而使得学生所学的知识和经验不能有效地应用到日后的生产和科研实践之中[7]。

针对以上关于《并行算法设计》教学的难点和传统教学方式的不足之处，本文提出了一种基于工作流模型驱动的教学方法，其核心思想可以归纳为：以并行问题求解模型为教学主线，通过分析与讲授并行问题求解模型的基本特征以及不同模型之间的异同来向学生传授并行算法的关键思想和技巧，同时弱化具体程序设计语言的特点，强调并行算法设计过程中通用性思维和普适性技巧。该方法的主要优点是：实现了算法设计思想与具体程序语言的独立性，能有效地引导学生掌握并行问题求解的关键思想和技巧，激发了学生利用简单模型来求解复杂问题的兴趣。

1 并行算法设计的工作流模型

在生产和实践过程中存在大量的可并行化处理的问题。由于问题类型各异，其各自的求解算法差别很大。为了避免学生过度关注特点问题的求解技巧，我们首先通过一个通用的工作流模型来描述各类并行问题的基本求解思路，其目的是让学生从整体、宏观的层面掌握并行问题求解和算法设计的基本流程。该工作流模型的基本结构如图1所示。

图1所示的工作流模型包含7个主要步骤，其中虚线框所包括的4个步骤为并行算法设计特有的步骤，而其余3个步骤则与传统算法设计过程相同。以下是关于工作流模型中7个步骤的详细教学内容和目标。

（1）并行问题描述与分析：该阶段主要讲授并行问题描述的基本方法和基本分析思路。其中，对问题描述方法的讲授过程着重强调“形式化描述方法”的重要性和优点，目标是让学生理解“形式化描述方法”的无歧义性和普遍适用性；关于并行问题的基本分析思路则着重强调“分而治之”的关键思想。通过该部分的教学，学生将能理解并行问题求解与传统程序设计问题的差别所在，从而激发他们进一步学习的积极性。

（2）外部操作过程：该阶段主要讲授并行问题在求解过程中需要考虑的各类外部执行过程，例如分布式文件系统的操作、传感器信号收集、网络数据传输等基本操作过程。教学重点在于向学生强调“并行算法设计是一个动态的信息搜集/处理过程，而非简单的单输入单输出模型”。由于“外部操作过程”在绝大多数实际并行/分布式系统中决定了系统的最终执行效率，因此该部分的教学内容可以通过若干实例向学生讲授这些“非关键”操作过程是如何影响系统的最终执行效率。通过该部分的教学，学生将能理解到并行算法设计和系统实现是一个“多系统协同工作”的复杂过程，其中任何一个系统的瓶颈将导致系统整体效率出现显著下降。

（3）资源操作过程：该阶段主要讲授并行资源在分配、调度和回收过程中的基本方法。由于并行系统通常以共享形式为多个用户提供服务，此处需要向学生强调并行资源使用过程的“共享性”特征，以及由这一特征所引入的其他相关问题，例如，安全性、数据一致性、时序有效性、服务质量等。在不同并行编程环境中，并行资源的操作方式存在较大差别，因此本处应该着重强调并行资源操作的基本流程，即“资源申请—服务协商—资源预留—资源分配—资源调度—资源使用—资源回收”这一基本通用的流程，弱化具体程序设计语言所使用的各类函数和系统调用方法。

（4）资源描述与定义：该阶段主要讲授并行资源所涉及到的基本属性以及如何通过标准的方法来定义和描述各类异构资源的属性。该步骤可以结合XML相关知识来向学生传递“语言独立性”在异构并行资源系统中的重要性。同时，结合“资源操作过程”部分的内容，向学生强调资源定义和描述是如何影响资源的后续造作的。通过该部分的学习，学生将能够掌握如何通过抽象的标记式语言来描述各类资源，从而实现上层算法设计与底层物理资源特性的“去耦合”。

（5）模型有效性验证：该阶段主要讲授验证并行算法求解模型的重要性，以及如何利用各类数学工具（包括自动机理论、离散数学、Petri Net等）来快速验证所设计算法的正确性和有效性。由于该部分的教学需要较强的前期理论知识，针对本科学生的教学可以通过“介绍性”的方式让学生来了解现有的各类理论工具，而针对研究生教学则可以通过“横向对比”方式来强调各种数学工具的优点/缺陷以及其各自的适用范围。通过该部分的学习，学生需要理解为何要对并行问题的求解模型进行验证，以及如何快速地实现这种验证过程。

（6）目标代码生成：该阶段将主要讲授在具体的并行编程环境中，如何将所设计的并行算法转化为特定的程序代码，并通过并行编译器生成最终的目标代码。在该部分的教学过程，可以选择1～2种典型的并行程序环境（例如PVM、MPI、MapReduce等）为例，通过具体的实例来向学生讲授并行程序语言的相关特点。由于此部分涉及具体的程序设计语言和语法，因此教学过程可以尽量多地对各种语言的相关特点进行横向比较，从而避免学生陷入“语言相关”的思维框架中。

（7）并行调试与维护：该阶段主要讲授在并行程序执行环境中，如何对目标程序的执行过程进行有效调试，以及如何对现有并行程序进行维护和更新。由于并行程序调试的难度极大，因此在该部分教学过程中我们采用了“分组实验”的教学方法，即以6～8名学生为一个基本单位，共同对3～5个典型的并行程序进行设计、实现和调试。在实验教学过程中，主要强调并行程序调试过程中的效率和技巧。例如，通过让学生总结调试过程中碰到的各类难度问题，回顾性地引导其思考“如何在程序设计过程中就充分考虑后期调试工作可能碰到的潜在问题”。通过这一步骤地教学，学生将能够更加深入地理解并行程序和算法设计的复杂性和挑战性。

2 教学实例与效果分析

本节将通过具体的教学实例进一步阐述基于工作流模型的并行算法设计教学方法。我们选择了并行排序算法设计这一种最为典型的并行求解问题作为教学案例，原因是学生在传统的算法设计课程中已经较为充分地理解了该问题。通过以上7个步骤，我们希望达到的教学目标是：学生能够有效掌握并行算法设计与传统算法设计的差别，并以此为基础来进一步理解并行算法设计的基本思想和基本技巧，同时引导学生从并行系统的基本特性出来思考并行问题的一般性求解方法和实现技巧。

针对本教学实例的特点和学生的已有基础知识，本实例相关的教学计划和安排如表1所示。在以下教学计划中，理论教学总课时以6～8个学时为宜，实验教学以4～6个学时为宜。其中，理论教学集中在前五个阶段，实验教学则集中在“目标代码生成”和“并行调试与维护”两个阶段。与传统的并行教学方法不同，我们将所有与具体程序设计语言和编程环境相关的内容集中在“实验教学”环节，主要目标在于引导学生树立“语言无关”的并行设计思想和方法。同时，将“语言相关”的教学内容放在实验教学环节还能够帮助学生快速地掌握和理解各类并行编程语言和系统的使用方法，避免在课堂上空洞地谈论语法和程序设计技巧。以上教学方法的另一个特点是：理论教学内容需要结合多门专业课程的相关知识。这一特点主要是由《并行算法设计》课程内容所决定，同时也要求授课老师必须具备较为全面的综合素质和计算机理论方面的基础（如表1）。

以上教学计划和方案在计算机科学与技术专业的大三班级中进行试点。为了评估实际教学效果，我们在本课程结束后组织了一次较为大型的课程设计，并对学生在课程设计过程中所表现的并行程序设计能力和素质进行了相关的统计和分析。为了对比本教学方法与传统的基于“语言驱动”的教学方法之间的差别，我们从“并行问题求解”“算法设计与实现”“程序设计与调试”三个方面对两种教学方案进行了比较，结果如表2～表4所示。

以上统计结果显示，采用工作流驱动的教学方法时，学生在“并行问题求解”方面的表现明显优于传统的教学方法，这说明该教学方法能够有效提高学生的分析问题和解决问题的能力，而非单纯地熟悉并行程序设计语言。在算法设计和程序设计两个方面，学生的成绩也高于传统方法约20%～30%，这一结果表明：强调程序设计语言的教学方法并不能有效提高学生并行算法设计和程序设计的能力。在课程设计过程中，我们发现那些能够快速分析出问题求解方法的学生往往在后期的算法设计和程序实现阶段表现出较高的积极性，而不能准确获得问题求解方法的学生则表现出较强烈的挫折感，从而无法有效地开展后阶段的设计任务。综合以上统计结果和分析，我们认为在《并行算法设计》课程中采用基于工作流模型驱动的教学方法能够更有效地提高学生的问题分析能力和积极性，进而激发学生通过逐步解决子问题来获得复杂并行问题的最终解决方案。

3 总结与讨论

《并行算法设计》课程是一门涉及多门专业课程的综合性课程，其难度和复杂度对老师和学生都提出了较高的要求。本文阐述了一种基于工作流模型驱动的教学方法，其核心思想是以并行问题求解模型为教学主线，通过分析与讲授并行问题求解模型的基本特征以及不同模型之间的异同来向学生传授并行算法的关键思想和技巧。该方法的主要优点是：实现了算法设计思想与具体程序语言的独立性，能有效地引导学生掌握并行问题求解的关键思想和技巧，激发了学生利用简单模型来求解复杂问题的兴趣。教学成绩的统计分析显示该方法明显优于传统的基于语言驱动的教学方法。目前，该教学方案仍有以下方面值得继续探索和改进。

（1）现实系统中的并行问题往往极为复杂，解决这些问题通常需要以团队的形式协同工作。因此，如何培养学生在并行算法设计过程中的团队协同工作能力是一个值得深入探讨和研究的问题。

（2）现实系统中的并行问题往往与特定领域（非计算机专业）相关，解决这些问题常常需要学生快速理解和掌握这些领域的若干基础知识。因此，如何培养学生快速掌握特定领域的基本概念和基础知识的能力是一个具有现实意义的课题。目前，我们已经开始尝试在教学中插入一些“文献检索”方面的基础知识，用于帮助学生掌握获取特定领域相关知识的技巧。

（3）并行算法和程序通常存在跨平台移植的问题。虽然随着编程语言和软件环境的改善，跨平台移植的难度有所降低，但在以后的较长时间内，跨平台移植的问题依然会是并行算法设计过程中的一个重要内容。因此，如何让学生在“问题分析”“模型求解”“算法设计”这些阶段尽量独立于具体程序设计语言成为一个极为重要问题。本文所提的教学方法在这方面做了若干努力，但仍然存在较大的改进空间。

参考文献

[1]郑方，郑霄，李宏亮，等.面向用户的并行计算机系统可用性建模研究[J].计算机研究与发展，2008，45（5）：886-894.

[2]陈国良，吴俊敏，章锋.并行计算机体系结构[M].高等教育出版社，2002.

[3]徐云，孙广中，郑启龙，等.“并行算法”课程的教学与探讨[J].教育与现代化，2008，8（4）.

[4]王智广，刘伟峰.“并行计算”课程算法实践教学的新工具：CUDA编程模型[J].计算机教育，2008，6（23）.

[5]陈国良，安虹，陈岐，等.并行算法实践[M].高等教育出版社，2003.

[6]Carro M，Marino J，Angel H，Moreno J.Teaching how to derive correct concurrent programs [J].In：Proceedings of the Teaching Formal Methods. Lecture Notes in Computer Science， Springer，1994，32：85-106.

[7]Carro M，Marino J，Angel H， Moreno J.A Model-Driven Approach to Teaching Concurrency[J].ACM Transactions on Computing Education，2013，13（1）：1-19.