基于工作流模型驅動的并行算法設計教學方法

摘 要：《并行算法設計》屬于高等計算機程序設計的主要課程之一，其主要難點集中在如何將特定的并行求解模型轉化為具體的程序設計語言。傳統的教學方法主要通過講授并行程序設計語言來實現教學目標，已有的教學實踐經驗顯示該方法存在的諸多不足之處。對此，本文提出了一種基于模型驅動的教學方法，其核心思想是：以并行問題求解模型為教學主線，通過分析與講授并行問題求解模型的基本特征以及不同模型之間的異同來向學生傳授并行算法的關鍵思想和技巧。該方法的主要優點是：實現了算法設計思想與具體程序語言的獨立性，能有效地引導學生掌握并行問題求解的關鍵思想和技巧，激發了學生利用簡單模型來求解復雜問題的興趣。

關鍵詞：并行計算 算法設計 工作流 教學改革

中圖分類號：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.