基于工作流模型驅(qū)動的并行算法設(shè)計教學(xué)方法

摘 要：《并行算法設(shè)計》屬于高等計算機(jī)程序設(shè)計的主要課程之一，其主要難點(diǎn)集中在如何將特定的并行求解模型轉(zhuǎn)化為具體的程序設(shè)計語言。傳統(tǒng)的教學(xué)方法主要通過講授并行程序設(shè)計語言來實(shí)現(xiàn)教學(xué)目標(biāo)，已有的教學(xué)實(shí)踐經(jīng)驗(yàn)顯示該方法存在的諸多不足之處。對此，本文提出了一種基于模型驅(qū)動的教學(xué)方法，其核心思想是：以并行問題求解模型為教學(xué)主線，通過分析與講授并行問題求解模型的基本特征以及不同模型之間的異同來向?qū)W生傳授并行算法的關(guān)鍵思想和技巧。該方法的主要優(yōu)點(diǎn)是：實(shí)現(xiàn)了算法設(shè)計思想與具體程序語言的獨(dú)立性，能有效地引導(dǎo)學(xué)生掌握并行問題求解的關(guān)鍵思想和技巧，激發(fā)了學(xué)生利用簡單模型來求解復(fù)雜問題的興趣。

關(guān)鍵詞：并行計算 算法設(shè)計 工作流 教學(xué)改革

中圖分類號：G4 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2013）05（a）-0167-03

高性能計算機(jī)是一個國家經(jīng)濟(jì)和科技實(shí)力的綜合體現(xiàn)，也是促進(jìn)經(jīng)濟(jì)、科技發(fā)展，社會進(jìn)步和國防安全的重要基礎(chǔ)。近年來，隨著大規(guī)模集成電路技術(shù)的不斷進(jìn)步?jīng)]，各類萬億次并行計算機(jī)被成功的研發(fā)和投入使用[1，2]。相對硬件的高速發(fā)展而言，并行程序設(shè)計和軟件開發(fā)則處于相對落后的階段。當(dāng)前，我國各類大學(xué)都針對計算機(jī)專業(yè)的高年級本科和研究生開設(shè)了《并行算法設(shè)計》這一課程，其目標(biāo)在于培養(yǎng)具有分析、解決并行程序設(shè)計問題能力的人才，從而提高我國在并行軟件系統(tǒng)設(shè)計方面的整體實(shí)力。

過去若干年的教學(xué)實(shí)踐顯示，《并行算法設(shè)計》課程在教學(xué)過程中存在以下具有挑戰(zhàn)性的難點(diǎn)[3-4]：（1）并行問題模型具有較高的抽象度，即使具有程序設(shè)計經(jīng)驗(yàn)的學(xué)生也難以準(zhǔn)確理解具體并行問題的抽象表達(dá)方式；（2）并行算法設(shè)計與實(shí)現(xiàn)難于在實(shí)際系統(tǒng)中部署和測試，學(xué)生很少能夠獲得感性的編程實(shí)踐經(jīng)驗(yàn)，從而導(dǎo)致學(xué)習(xí)的積極性下降；（3）現(xiàn)有的各種并行編程環(huán)境通常不具備兼容性，在一種編程環(huán)境中所獲得的知識通常難于有效地應(yīng)用到其它編程環(huán)境下；（4）并行執(zhí)行環(huán)境的調(diào)試難度極大，傳統(tǒng)的程序調(diào)試技巧基本不能應(yīng)用于并行執(zhí)行環(huán)境。

傳統(tǒng)的《并行算法設(shè)計》課程的主要教學(xué)方式是：通過選擇一種并行程序語言來向?qū)W生教授并行算法設(shè)計的相關(guān)知識。這種基于語言驅(qū)動的教學(xué)方法已經(jīng)沿用了若干年，其在教學(xué)效果上的不足之處也日益受到人們的關(guān)注，主要體現(xiàn)在：（1）教學(xué)內(nèi)容集中在并行程序設(shè)計語言的語法層面，容易誤導(dǎo)學(xué)生認(rèn)為并行程序設(shè)計和傳統(tǒng)的程序設(shè)計差別不大[5]；（2）授課內(nèi)容與特定的編程環(huán)境高度耦合，難以幫助學(xué)生樹立正確的“并行程序設(shè)計思想”，從而使得學(xué)生不能獲得獨(dú)立的分析問題和解決問題的能力[6]；（3）強(qiáng)調(diào)特定并行問題的求解技巧，忽略各類并行問題模型中存在共性，從而使得學(xué)生不能有效地應(yīng)對現(xiàn)實(shí)環(huán)境中碰到的各類新問題[7]；（4）只強(qiáng)調(diào)程序設(shè)計結(jié)果的編譯正確性，忽略程序在執(zhí)行和維護(hù)過程中的健壯性和魯棒性，從而使得學(xué)生所學(xué)的知識和經(jīng)驗(yàn)不能有效地應(yīng)用到日后的生產(chǎn)和科研實(shí)踐之中[7]。

針對以上關(guān)于《并行算法設(shè)計》教學(xué)的難點(diǎn)和傳統(tǒng)教學(xué)方式的不足之處，本文提出了一種基于工作流模型驅(qū)動的教學(xué)方法，其核心思想可以歸納為：以并行問題求解模型為教學(xué)主線，通過分析與講授并行問題求解模型的基本特征以及不同模型之間的異同來向?qū)W生傳授并行算法的關(guān)鍵思想和技巧，同時弱化具體程序設(shè)計語言的特點(diǎn)，強(qiáng)調(diào)并行算法設(shè)計過程中通用性思維和普適性技巧。該方法的主要優(yōu)點(diǎn)是：實(shí)現(xiàn)了算法設(shè)計思想與具體程序語言的獨(dú)立性，能有效地引導(dǎo)學(xué)生掌握并行問題求解的關(guān)鍵思想和技巧，激發(fā)了學(xué)生利用簡單模型來求解復(fù)雜問題的興趣。

1 并行算法設(shè)計的工作流模型

在生產(chǎn)和實(shí)踐過程中存在大量的可并行化處理的問題。由于問題類型各異，其各自的求解算法差別很大。為了避免學(xué)生過度關(guān)注特點(diǎn)問題的求解技巧，我們首先通過一個通用的工作流模型來描述各類并行問題的基本求解思路，其目的是讓學(xué)生從整體、宏觀的層面掌握并行問題求解和算法設(shè)計的基本流程。該工作流模型的基本結(jié)構(gòu)如圖1所示。

圖1所示的工作流模型包含7個主要步驟，其中虛線框所包括的4個步驟為并行算法設(shè)計特有的步驟，而其余3個步驟則與傳統(tǒng)算法設(shè)計過程相同。以下是關(guān)于工作流模型中7個步驟的詳細(xì)教學(xué)內(nèi)容和目標(biāo)。

（1）并行問題描述與分析：該階段主要講授并行問題描述的基本方法和基本分析思路。其中，對問題描述方法的講授過程著重強(qiáng)調(diào)“形式化描述方法”的重要性和優(yōu)點(diǎn)，目標(biāo)是讓學(xué)生理解“形式化描述方法”的無歧義性和普遍適用性；關(guān)于并行問題的基本分析思路則著重強(qiáng)調(diào)“分而治之”的關(guān)鍵思想。通過該部分的教學(xué)，學(xué)生將能理解并行問題求解與傳統(tǒng)程序設(shè)計問題的差別所在，從而激發(fā)他們進(jìn)一步學(xué)習(xí)的積極性。

（2）外部操作過程：該階段主要講授并行問題在求解過程中需要考慮的各類外部執(zhí)行過程，例如分布式文件系統(tǒng)的操作、傳感器信號收集、網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)然静僮鬟^程。教學(xué)重點(diǎn)在于向?qū)W生強(qiáng)調(diào)“并行算法設(shè)計是一個動態(tài)的信息搜集/處理過程，而非簡單的單輸入單輸出模型”。由于“外部操作過程”在絕大多數(shù)實(shí)際并行/分布式系統(tǒng)中決定了系統(tǒng)的最終執(zhí)行效率，因此該部分的教學(xué)內(nèi)容可以通過若干實(shí)例向?qū)W生講授這些“非關(guān)鍵”操作過程是如何影響系統(tǒng)的最終執(zhí)行效率。通過該部分的教學(xué)，學(xué)生將能理解到并行算法設(shè)計和系統(tǒng)實(shí)現(xiàn)是一個“多系統(tǒng)協(xié)同工作”的復(fù)雜過程，其中任何一個系統(tǒng)的瓶頸將導(dǎo)致系統(tǒng)整體效率出現(xiàn)顯著下降。

（3）資源操作過程：該階段主要講授并行資源在分配、調(diào)度和回收過程中的基本方法。由于并行系統(tǒng)通常以共享形式為多個用戶提供服務(wù)，此處需要向?qū)W生強(qiáng)調(diào)并行資源使用過程的“共享性”特征，以及由這一特征所引入的其他相關(guān)問題，例如，安全性、數(shù)據(jù)一致性、時序有效性、服務(wù)質(zhì)量等。在不同并行編程環(huán)境中，并行資源的操作方式存在較大差別，因此本處應(yīng)該著重強(qiáng)調(diào)并行資源操作的基本流程，即“資源申請—服務(wù)協(xié)商—資源預(yù)留—資源分配—資源調(diào)度—資源使用—資源回收”這一基本通用的流程，弱化具體程序設(shè)計語言所使用的各類函數(shù)和系統(tǒng)調(diào)用方法。

（4）資源描述與定義：該階段主要講授并行資源所涉及到的基本屬性以及如何通過標(biāo)準(zhǔn)的方法來定義和描述各類異構(gòu)資源的屬性。該步驟可以結(jié)合XML相關(guān)知識來向?qū)W生傳遞“語言獨(dú)立性”在異構(gòu)并行資源系統(tǒng)中的重要性。同時，結(jié)合“資源操作過程”部分的內(nèi)容，向?qū)W生強(qiáng)調(diào)資源定義和描述是如何影響資源的后續(xù)造作的。通過該部分的學(xué)習(xí)，學(xué)生將能夠掌握如何通過抽象的標(biāo)記式語言來描述各類資源，從而實(shí)現(xiàn)上層算法設(shè)計與底層物理資源特性的“去耦合”。

（5）模型有效性驗(yàn)證：該階段主要講授驗(yàn)證并行算法求解模型的重要性，以及如何利用各類數(shù)學(xué)工具（包括自動機(jī)理論、離散數(shù)學(xué)、Petri Net等）來快速驗(yàn)證所設(shè)計算法的正確性和有效性。由于該部分的教學(xué)需要較強(qiáng)的前期理論知識，針對本科學(xué)生的教學(xué)可以通過“介紹性”的方式讓學(xué)生來了解現(xiàn)有的各類理論工具，而針對研究生教學(xué)則可以通過“橫向?qū)Ρ取狈绞絹韽?qiáng)調(diào)各種數(shù)學(xué)工具的優(yōu)點(diǎn)/缺陷以及其各自的適用范圍。通過該部分的學(xué)習(xí)，學(xué)生需要理解為何要對并行問題的求解模型進(jìn)行驗(yàn)證，以及如何快速地實(shí)現(xiàn)這種驗(yàn)證過程。

（6）目標(biāo)代碼生成：該階段將主要講授在具體的并行編程環(huán)境中，如何將所設(shè)計的并行算法轉(zhuǎn)化為特定的程序代碼，并通過并行編譯器生成最終的目標(biāo)代碼。在該部分的教學(xué)過程，可以選擇1～2種典型的并行程序環(huán)境（例如PVM、MPI、MapReduce等）為例，通過具體的實(shí)例來向?qū)W生講授并行程序語言的相關(guān)特點(diǎn)。由于此部分涉及具體的程序設(shè)計語言和語法，因此教學(xué)過程可以盡量多地對各種語言的相關(guān)特點(diǎn)進(jìn)行橫向比較，從而避免學(xué)生陷入“語言相關(guān)”的思維框架中。

（7）并行調(diào)試與維護(hù)：該階段主要講授在并行程序執(zhí)行環(huán)境中，如何對目標(biāo)程序的執(zhí)行過程進(jìn)行有效調(diào)試，以及如何對現(xiàn)有并行程序進(jìn)行維護(hù)和更新。由于并行程序調(diào)試的難度極大，因此在該部分教學(xué)過程中我們采用了“分組實(shí)驗(yàn)”的教學(xué)方法，即以6～8名學(xué)生為一個基本單位，共同對3～5個典型的并行程序進(jìn)行設(shè)計、實(shí)現(xiàn)和調(diào)試。在實(shí)驗(yàn)教學(xué)過程中，主要強(qiáng)調(diào)并行程序調(diào)試過程中的效率和技巧。例如，通過讓學(xué)生總結(jié)調(diào)試過程中碰到的各類難度問題，回顧性地引導(dǎo)其思考“如何在程序設(shè)計過程中就充分考慮后期調(diào)試工作可能碰到的潛在問題”。通過這一步驟地教學(xué)，學(xué)生將能夠更加深入地理解并行程序和算法設(shè)計的復(fù)雜性和挑戰(zhàn)性。

2 教學(xué)實(shí)例與效果分析

本節(jié)將通過具體的教學(xué)實(shí)例進(jìn)一步闡述基于工作流模型的并行算法設(shè)計教學(xué)方法。我們選擇了并行排序算法設(shè)計這一種最為典型的并行求解問題作為教學(xué)案例，原因是學(xué)生在傳統(tǒng)的算法設(shè)計課程中已經(jīng)較為充分地理解了該問題。通過以上7個步驟，我們希望達(dá)到的教學(xué)目標(biāo)是：學(xué)生能夠有效掌握并行算法設(shè)計與傳統(tǒng)算法設(shè)計的差別，并以此為基礎(chǔ)來進(jìn)一步理解并行算法設(shè)計的基本思想和基本技巧，同時引導(dǎo)學(xué)生從并行系統(tǒng)的基本特性出來思考并行問題的一般性求解方法和實(shí)現(xiàn)技巧。

針對本教學(xué)實(shí)例的特點(diǎn)和學(xué)生的已有基礎(chǔ)知識，本實(shí)例相關(guān)的教學(xué)計劃和安排如表1所示。在以下教學(xué)計劃中，理論教學(xué)總課時以6～8個學(xué)時為宜，實(shí)驗(yàn)教學(xué)以4～6個學(xué)時為宜。其中，理論教學(xué)集中在前五個階段，實(shí)驗(yàn)教學(xué)則集中在“目標(biāo)代碼生成”和“并行調(diào)試與維護(hù)”兩個階段。與傳統(tǒng)的并行教學(xué)方法不同，我們將所有與具體程序設(shè)計語言和編程環(huán)境相關(guān)的內(nèi)容集中在“實(shí)驗(yàn)教學(xué)”環(huán)節(jié)，主要目標(biāo)在于引導(dǎo)學(xué)生樹立“語言無關(guān)”的并行設(shè)計思想和方法。同時，將“語言相關(guān)”的教學(xué)內(nèi)容放在實(shí)驗(yàn)教學(xué)環(huán)節(jié)還能夠幫助學(xué)生快速地掌握和理解各類并行編程語言和系統(tǒng)的使用方法，避免在課堂上空洞地談?wù)撜Z法和程序設(shè)計技巧。以上教學(xué)方法的另一個特點(diǎn)是：理論教學(xué)內(nèi)容需要結(jié)合多門專業(yè)課程的相關(guān)知識。這一特點(diǎn)主要是由《并行算法設(shè)計》課程內(nèi)容所決定，同時也要求授課老師必須具備較為全面的綜合素質(zhì)和計算機(jī)理論方面的基礎(chǔ)（如表1）。

以上教學(xué)計劃和方案在計算機(jī)科學(xué)與技術(shù)專業(yè)的大三班級中進(jìn)行試點(diǎn)。為了評估實(shí)際教學(xué)效果，我們在本課程結(jié)束后組織了一次較為大型的課程設(shè)計，并對學(xué)生在課程設(shè)計過程中所表現(xiàn)的并行程序設(shè)計能力和素質(zhì)進(jìn)行了相關(guān)的統(tǒng)計和分析。為了對比本教學(xué)方法與傳統(tǒng)的基于“語言驅(qū)動”的教學(xué)方法之間的差別，我們從“并行問題求解”“算法設(shè)計與實(shí)現(xiàn)”“程序設(shè)計與調(diào)試”三個方面對兩種教學(xué)方案進(jìn)行了比較，結(jié)果如表2～表4所示。

以上統(tǒng)計結(jié)果顯示，采用工作流驅(qū)動的教學(xué)方法時，學(xué)生在“并行問題求解”方面的表現(xiàn)明顯優(yōu)于傳統(tǒng)的教學(xué)方法，這說明該教學(xué)方法能夠有效提高學(xué)生的分析問題和解決問題的能力，而非單純地熟悉并行程序設(shè)計語言。在算法設(shè)計和程序設(shè)計兩個方面，學(xué)生的成績也高于傳統(tǒng)方法約20%～30%，這一結(jié)果表明：強(qiáng)調(diào)程序設(shè)計語言的教學(xué)方法并不能有效提高學(xué)生并行算法設(shè)計和程序設(shè)計的能力。在課程設(shè)計過程中，我們發(fā)現(xiàn)那些能夠快速分析出問題求解方法的學(xué)生往往在后期的算法設(shè)計和程序?qū)崿F(xiàn)階段表現(xiàn)出較高的積極性，而不能準(zhǔn)確獲得問題求解方法的學(xué)生則表現(xiàn)出較強(qiáng)烈的挫折感，從而無法有效地開展后階段的設(shè)計任務(wù)。綜合以上統(tǒng)計結(jié)果和分析，我們認(rèn)為在《并行算法設(shè)計》課程中采用基于工作流模型驅(qū)動的教學(xué)方法能夠更有效地提高學(xué)生的問題分析能力和積極性，進(jìn)而激發(fā)學(xué)生通過逐步解決子問題來獲得復(fù)雜并行問題的最終解決方案。

3 總結(jié)與討論

《并行算法設(shè)計》課程是一門涉及多門專業(yè)課程的綜合性課程，其難度和復(fù)雜度對老師和學(xué)生都提出了較高的要求。本文闡述了一種基于工作流模型驅(qū)動的教學(xué)方法，其核心思想是以并行問題求解模型為教學(xué)主線，通過分析與講授并行問題求解模型的基本特征以及不同模型之間的異同來向?qū)W生傳授并行算法的關(guān)鍵思想和技巧。該方法的主要優(yōu)點(diǎn)是：實(shí)現(xiàn)了算法設(shè)計思想與具體程序語言的獨(dú)立性，能有效地引導(dǎo)學(xué)生掌握并行問題求解的關(guān)鍵思想和技巧，激發(fā)了學(xué)生利用簡單模型來求解復(fù)雜問題的興趣。教學(xué)成績的統(tǒng)計分析顯示該方法明顯優(yōu)于傳統(tǒng)的基于語言驅(qū)動的教學(xué)方法。目前，該教學(xué)方案仍有以下方面值得繼續(xù)探索和改進(jìn)。

（1）現(xiàn)實(shí)系統(tǒng)中的并行問題往往極為復(fù)雜，解決這些問題通常需要以團(tuán)隊的形式協(xié)同工作。因此，如何培養(yǎng)學(xué)生在并行算法設(shè)計過程中的團(tuán)隊協(xié)同工作能力是一個值得深入探討和研究的問題。

（2）現(xiàn)實(shí)系統(tǒng)中的并行問題往往與特定領(lǐng)域（非計算機(jī)專業(yè)）相關(guān)，解決這些問題常常需要學(xué)生快速理解和掌握這些領(lǐng)域的若干基礎(chǔ)知識。因此，如何培養(yǎng)學(xué)生快速掌握特定領(lǐng)域的基本概念和基礎(chǔ)知識的能力是一個具有現(xiàn)實(shí)意義的課題。目前，我們已經(jīng)開始嘗試在教學(xué)中插入一些“文獻(xiàn)檢索”方面的基礎(chǔ)知識，用于幫助學(xué)生掌握獲取特定領(lǐng)域相關(guān)知識的技巧。

（3）并行算法和程序通常存在跨平臺移植的問題。雖然隨著編程語言和軟件環(huán)境的改善，跨平臺移植的難度有所降低，但在以后的較長時間內(nèi)，跨平臺移植的問題依然會是并行算法設(shè)計過程中的一個重要內(nèi)容。因此，如何讓學(xué)生在“問題分析”“模型求解”“算法設(shè)計”這些階段盡量獨(dú)立于具體程序設(shè)計語言成為一個極為重要問題。本文所提的教學(xué)方法在這方面做了若干努力，但仍然存在較大的改進(jìn)空間。

參考文獻(xiàn)

[1]鄭方，鄭霄，李宏亮，等.面向用戶的并行計算機(jī)系統(tǒng)可用性建模研究[J].計算機(jī)研究與發(fā)展，2008，45（5）：886-894.

[2]陳國良，吳俊敏，章鋒.并行計算機(jī)體系結(jié)構(gòu)[M].高等教育出版社，2002.

[3]徐云，孫廣中，鄭啟龍，等.“并行算法”課程的教學(xué)與探討[J].教育與現(xiàn)代化，2008，8（4）.

[4]王智廣，劉偉峰.“并行計算”課程算法實(shí)踐教學(xué)的新工具：CUDA編程模型[J].計算機(jī)教育，2008，6（23）.

[5]陳國良，安虹，陳岐，等.并行算法實(shí)踐[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.