研究生課程“并行算法”教學(xué)內(nèi)容優(yōu)化設(shè)計(jì)研究

吳建平，銀?？?，楊錦輝，彭 軍，汪 祥

（國(guó)防科技大學(xué) 氣象海洋學(xué)院，湖南 長(zhǎng)沙 410073）

引言

傳統(tǒng)科學(xué)研究主要采用理論研究或?qū)嶒?yàn)研究?jī)煞N手段。理論研究或難以針對(duì)實(shí)際模型進(jìn)行展開(kāi)，或只能以某種近似方式進(jìn)行，與真實(shí)模型存在差距；而實(shí)驗(yàn)研究則很難避免出現(xiàn)主觀性誤差，且因?qū)嶒?yàn)器材與安全性等問(wèn)題又使得成本較高。自20世紀(jì)起，隨著計(jì)算機(jī)的出現(xiàn)與發(fā)展，人們逐漸發(fā)現(xiàn)計(jì)算機(jī)數(shù)值模擬可以作為另一種科學(xué)研究手段。此后，計(jì)算機(jī)數(shù)值模擬得以迅速發(fā)展，并在氣象海洋環(huán)境預(yù)報(bào)、核物理、飛行器設(shè)計(jì)、拱壩建設(shè)、油氣藏勘探、地震預(yù)測(cè)、圖像處理、分子生物學(xué)、天體物理學(xué)、材料科學(xué)等許多領(lǐng)域得到了越來(lái)越廣泛的應(yīng)用。

在實(shí)際應(yīng)用中，對(duì)模擬精度要求越來(lái)越高，所要求解的問(wèn)題規(guī)模越來(lái)越大，但無(wú)論處理器的工藝水平如何高，單處理器的存儲(chǔ)與計(jì)算能力都一直滿(mǎn)足不了許多實(shí)際應(yīng)用問(wèn)題對(duì)實(shí)時(shí)性、計(jì)算能力與存儲(chǔ)需求的要求，這使得人們?cè)絹?lái)越尋求通過(guò)采用高性能并行計(jì)算機(jī)進(jìn)行大規(guī)模數(shù)值模擬。但要實(shí)現(xiàn)高性能并行計(jì)算，既需要從計(jì)算方法的層面進(jìn)行并行算法設(shè)計(jì)，又需要面向高性能并行計(jì)算機(jī)進(jìn)行具體實(shí)現(xiàn)，其中涉及方方面面的理論與技術(shù)問(wèn)題。正是在這種時(shí)代背景下，中國(guó)科技大學(xué)、清華大學(xué)、加州大學(xué)伯克利分校、哈佛大學(xué)、普渡大學(xué)、斯坦福大學(xué)、北卡羅來(lái)納大學(xué)等國(guó)內(nèi)外眾多高校陸續(xù)開(kāi)設(shè)并行計(jì)算相關(guān)課程，國(guó)內(nèi)外不僅形成許多經(jīng)典教材①《并行計(jì)算：結(jié)構(gòu)·算法·編程》、《可擴(kuò)展并行算法的設(shè)計(jì)與分析》、《并行計(jì)算導(dǎo)論》、《數(shù)值并行算法與軟件》、Introduction to Parallel Computing(Second Edition)。，在教學(xué)方面也進(jìn)行了一些研究②《精品課程“并行計(jì)算”的建設(shè)》《并行計(jì)算實(shí)驗(yàn)課程建設(shè)的實(shí)踐與探討》等。。作為國(guó)內(nèi)最早進(jìn)行高性能并行計(jì)算機(jī)研制與應(yīng)用的單位之一，國(guó)防科技大學(xué)早在20世紀(jì)80年代即由李曉梅教授開(kāi)始開(kāi)設(shè)“并行算法”研究生課程。

一、“并行算法”課程概況

“并行算法”課程針對(duì)全校研究生開(kāi)設(shè)，旨在通過(guò)學(xué)習(xí)基本知識(shí)、理解基本原理、運(yùn)用基本技術(shù)、實(shí)踐基本算法與閱讀課外資料，培養(yǎng)學(xué)員的并行計(jì)算思維、算法抽象思維、邏輯推理能力與自主學(xué)習(xí)能力，使學(xué)生具備進(jìn)行并行算法設(shè)計(jì)、實(shí)現(xiàn)到評(píng)估的初步能力，為氣象海洋等大規(guī)?？茖W(xué)與工程計(jì)算領(lǐng)域研究生打下并行計(jì)算方面的研究與應(yīng)用基礎(chǔ)。

“并行算法”課程共36學(xué)時(shí)，其中課堂實(shí)踐3學(xué)時(shí)。自20世紀(jì)90年代開(kāi)設(shè)以來(lái)，經(jīng)過(guò)多年發(fā)展和幾代教師的經(jīng)驗(yàn)積累，教學(xué)內(nèi)容進(jìn)行了多次迭代優(yōu)化，現(xiàn)已形成包括并行計(jì)算基本概念、并行算法設(shè)計(jì)基本技術(shù)、典型并行算法與并行算法編程實(shí)踐在內(nèi)的內(nèi)容體系，知識(shí)層次相對(duì)較高，不僅理論性較強(qiáng)，實(shí)踐要求也較高。本文基于“并行算法”課程教學(xué)經(jīng)驗(yàn)和實(shí)踐，主要介紹教學(xué)過(guò)程中對(duì)并行計(jì)算思維訓(xùn)練的探索，以及基于該思維與模塊化組織方式對(duì)教學(xué)內(nèi)容優(yōu)化設(shè)計(jì)方面的研究成果。

二、“并行算法”課程教學(xué)內(nèi)容優(yōu)化設(shè)計(jì)

并行計(jì)算從思維方式上可以看成計(jì)算與并行處理這兩種思維的復(fù)合。計(jì)算思維強(qiáng)調(diào)像計(jì)算機(jī)科學(xué)家那樣思考問(wèn)題與求解問(wèn)題，是理解問(wèn)題與對(duì)求解過(guò)程進(jìn)行形式化時(shí)的底層思考，計(jì)算思維要求以算法的方式求解復(fù)雜問(wèn)題，強(qiáng)調(diào)對(duì)問(wèn)題求解的可達(dá)性，且追求對(duì)計(jì)算資源的節(jié)約與求解效率的改進(jìn)。并行處理思維強(qiáng)調(diào)任務(wù)處理時(shí)對(duì)任務(wù)的分解與同時(shí)處理，在具體高性能計(jì)算硬件基礎(chǔ)的情況下，著重任務(wù)的可分離性和任務(wù)調(diào)度的合理性。并行計(jì)算的思維本質(zhì)即如何實(shí)現(xiàn)對(duì)整個(gè)任務(wù)計(jì)算過(guò)程的合理規(guī)劃，以實(shí)現(xiàn)在目標(biāo)高性能并行計(jì)算機(jī)上的高效執(zhí)行。同時(shí)，由于強(qiáng)調(diào)在高性能計(jì)算機(jī)上的可達(dá)性，并行計(jì)算非常強(qiáng)調(diào)設(shè)計(jì)求解過(guò)程在高性能并行計(jì)算機(jī)上的具體實(shí)現(xiàn)及其實(shí)際效果。

基于對(duì)并行計(jì)算思維訓(xùn)練與理論實(shí)踐相結(jié)合的理念，考慮學(xué)生對(duì)教學(xué)內(nèi)容學(xué)習(xí)與理解的便利性，與未來(lái)對(duì)教學(xué)內(nèi)容的進(jìn)一步優(yōu)化設(shè)計(jì)，課程講授過(guò)程中將整體教學(xué)內(nèi)容從頂層分為并行計(jì)算基本概念、并行算法設(shè)計(jì)基本技術(shù)、典型并行算法與并行算法編程實(shí)踐四大模塊。其中，并行計(jì)算基本概念主要側(cè)重并行計(jì)算涉及的基本理念與概念，是實(shí)施后續(xù)教學(xué)內(nèi)容的基礎(chǔ)；并行算法設(shè)計(jì)基本技術(shù)主要側(cè)重并行算法設(shè)計(jì)的典型過(guò)程，以及在該過(guò)程中經(jīng)常采用的相關(guān)技術(shù)，是整門(mén)課程的核心所在；典型并行算法主要介紹數(shù)值計(jì)算與非數(shù)值計(jì)算中遇到的經(jīng)典且較為簡(jiǎn)單的并行算法，一方面用以加深對(duì)并行算法設(shè)計(jì)基本原理與常用方法的掌握，另一方面也便于在后續(xù)研究中涉及類(lèi)似并行算法設(shè)計(jì)時(shí)進(jìn)行參考；并行算法編程實(shí)踐側(cè)重簡(jiǎn)單的編程實(shí)現(xiàn)，以及利用所學(xué)知識(shí)進(jìn)行典型并行算法的具體實(shí)踐。之后對(duì)四大教學(xué)模塊，再次進(jìn)行模塊化組織，形成子模塊，具體如圖1所示。

圖1 “并行算法”課程模塊組成圖

（一）并行計(jì)算基本概念模塊

并行計(jì)算基本概念模塊主要包括采用并行計(jì)算的原因、并行計(jì)算的思維、并行計(jì)算常用概念、并行計(jì)算機(jī)的抽象及并行算法的性能評(píng)價(jià)等5個(gè)子模塊。

采用并行計(jì)算的原因主要以數(shù)值天氣預(yù)報(bào)與星系模擬等典型案例引入本課程，并通過(guò)對(duì)世界頂尖數(shù)值預(yù)報(bào)中心在高性能計(jì)算上的現(xiàn)狀進(jìn)行調(diào)研查閱，進(jìn)一步增強(qiáng)對(duì)為什么需要進(jìn)行并行計(jì)算的感性認(rèn)識(shí)。并行計(jì)算的思維主要闡述計(jì)算思維、并行處理思維與并行計(jì)算的思維方式，以及并行處理實(shí)現(xiàn)上的具備硬件基礎(chǔ)、任務(wù)可分離性與任務(wù)安排合理性三要素，并通過(guò)與日常生活中簡(jiǎn)單示例的對(duì)比，加強(qiáng)對(duì)并行處理思維的理解。并行計(jì)算常用概念主要采用圖文結(jié)合、逐步推進(jìn)的方式，從機(jī)器相關(guān)、問(wèn)題相關(guān)、算法相關(guān)三方面，逐一介紹并行計(jì)算中常用的機(jī)器規(guī)模、問(wèn)題規(guī)模、任務(wù)分解、并行度、分解粒度、數(shù)據(jù)相關(guān)性、任務(wù)調(diào)度、負(fù)載平衡、確定性、同步、死鎖、并行執(zhí)行時(shí)間、并行開(kāi)銷(xiāo)、加速比、并行效率、整機(jī)效率、可擴(kuò)展性等概念，使學(xué)生對(duì)并行計(jì)算相關(guān)概念形成初步且系統(tǒng)的了解。同時(shí)，通過(guò)安排學(xué)生閱讀并行計(jì)算相關(guān)文獻(xiàn)，進(jìn)一步掌握這些概念的英文表述，加強(qiáng)對(duì)并行計(jì)算思維的領(lǐng)悟。并行計(jì)算機(jī)的抽象圍繞并行算法設(shè)計(jì)與分析所需與對(duì)目標(biāo)并行計(jì)算機(jī)典型特征的抽象進(jìn)行展開(kāi)，包括并行計(jì)算機(jī)的互聯(lián)網(wǎng)絡(luò)、并行計(jì)算機(jī)的分類(lèi)與發(fā)展、并行計(jì)算模型，其中并行計(jì)算的互聯(lián)網(wǎng)絡(luò)主要介紹靜態(tài)邏輯互聯(lián)網(wǎng)絡(luò)結(jié)構(gòu)，尤其側(cè)重環(huán)、二維網(wǎng)格、三維網(wǎng)格、超立方體與星形等后續(xù)算法設(shè)計(jì)中常用的結(jié)構(gòu)；并行計(jì)算機(jī)的分類(lèi)與發(fā)展側(cè)重介紹Flynn分類(lèi)法，以及物理存儲(chǔ)結(jié)構(gòu)與邏輯存儲(chǔ)結(jié)構(gòu)上的不同；并行計(jì)算模型是對(duì)某類(lèi)目標(biāo)高性能計(jì)算機(jī)的共同抽象，主要講授最常用的LogP模型。在進(jìn)行并行計(jì)算機(jī)抽象時(shí)，著重強(qiáng)調(diào)物理層面與邏輯層面間的關(guān)系，物理層面是硬件本身實(shí)現(xiàn)層面，邏輯層面是算法設(shè)計(jì)時(shí)的虛擬層面。并行算法的性能評(píng)價(jià)主要在加速比與并行效率等基本概念的基礎(chǔ)上，面向并行算法在處理器個(gè)數(shù)增大情況下的潛在性能表現(xiàn)，著重介紹影響加速比的主要因素，Amdahl與Gustafson等經(jīng)典加速比定律，以及并行算法的可擴(kuò)展性分析與等效率分析方法。

（二）并行算法設(shè)計(jì)基本技術(shù)模塊

并行算法設(shè)計(jì)基本技術(shù)模塊包括基本通信操作、常用任務(wù)分解、常用任務(wù)調(diào)度、常用設(shè)計(jì)模式、減小交互開(kāi)銷(xiāo)影響的常用方法等5個(gè)子模塊。

基本通信操作主要針對(duì)常用拓?fù)浣Y(jié)構(gòu)，如線性陣列、網(wǎng)格與超立方體等，介紹常用的廣播、規(guī)約、分散、收集、多對(duì)多私有通信等涉及多個(gè)處理器的通信操作，既作為引子也是最簡(jiǎn)單的并行算法，提高并行計(jì)算的思維能力，又強(qiáng)化對(duì)并行計(jì)算模型用途的認(rèn)識(shí)與便于在需要時(shí)熟練應(yīng)用。常用任務(wù)分解主要介紹嵌套分解與數(shù)據(jù)劃分等常用的任務(wù)分解技術(shù)，其中嵌套分解強(qiáng)調(diào)對(duì)基于分治策略相關(guān)算法設(shè)計(jì)的適用性以及具體的使用方式；數(shù)據(jù)劃分強(qiáng)調(diào)對(duì)以數(shù)據(jù)為中心的并行算法設(shè)計(jì)的適用性，主要側(cè)重于輸出劃分、輸入劃分、中間結(jié)果劃分與圖劃分等最常用的技術(shù)，結(jié)合實(shí)例進(jìn)行介紹，并重點(diǎn)注重區(qū)分各自適用范圍與各自受到的約束，真正提高學(xué)生對(duì)各種方法的掌握與實(shí)際應(yīng)用水平。常用任務(wù)調(diào)度主要介紹數(shù)組分布與圖劃分等常用靜態(tài)調(diào)度技術(shù)，以及集中式動(dòng)態(tài)調(diào)度技術(shù)，其中數(shù)組分布主要通過(guò)數(shù)值天氣預(yù)報(bào)等問(wèn)題中常用的Stencil計(jì)算重點(diǎn)介紹塊分布及其優(yōu)缺點(diǎn)；通過(guò)數(shù)值天氣預(yù)報(bào)譜模式中譜空間負(fù)載平衡算法等重點(diǎn)介紹循環(huán)塊分布及其優(yōu)缺點(diǎn)；通過(guò)污染物擴(kuò)散、稀疏矩陣稠密向量乘等問(wèn)題，介紹圖劃分算法及其優(yōu)缺點(diǎn)。常用設(shè)計(jì)模式主要介紹數(shù)據(jù)并行計(jì)算、流水線、工作池、任務(wù)圖與主從等常用設(shè)計(jì)模式，側(cè)重前兩種針對(duì)靜態(tài)調(diào)度和第三種對(duì)動(dòng)態(tài)調(diào)度等最常用的技術(shù)，并結(jié)合并行計(jì)算的思維進(jìn)行介紹。減小交互開(kāi)銷(xiāo)影響的方法主要包括最大化數(shù)據(jù)局部性、最小化競(jìng)爭(zhēng)與熱點(diǎn)、計(jì)算與交互重疊、數(shù)據(jù)復(fù)制或重復(fù)計(jì)算、利用優(yōu)化過(guò)的聚合交互操作、將交互開(kāi)銷(xiāo)相互重疊等編程實(shí)現(xiàn)時(shí)的常用技術(shù)，主要結(jié)合具體實(shí)例進(jìn)行介紹。

（三）典型并行算法模塊

典型并行算法模塊包括并行排序算法、稠密矩陣并行算法、稀疏線性方程組并行求解、FFT并行算法等4個(gè)子模塊。

并行排序算法是典型的非數(shù)值并行算法，主要涉及算法確定性高且計(jì)算復(fù)雜度相對(duì)較低的雙調(diào)排序及其并行算法，以及計(jì)算復(fù)雜度量階最小的快速排序及其并行算法，著重關(guān)注雙調(diào)排序算法與網(wǎng)絡(luò)間對(duì)應(yīng)關(guān)系和快速排序算法中數(shù)據(jù)劃分與嵌套分解相結(jié)合的分解技術(shù)。稠密矩陣并行算法主要從稠密矩陣向量并行乘、稠密矩陣并行乘與基于LU分解的稠密線性方程組并行求解等知識(shí)點(diǎn)進(jìn)行教學(xué)，著重關(guān)注較為簡(jiǎn)單且與基本理論結(jié)合度非常緊密的前兩類(lèi)算法。稀疏線性方程組并行求解主要講授最典型的三對(duì)角線性方程組并行分裂法、Jacobi迭代并行算法、SOR型迭代并行算法、一般迭代法的并行算法等，著重關(guān)注簡(jiǎn)單但富有獨(dú)特性的并行分裂法、Jacobi型迭代法，以及SOR迭代的紅黑排序算法。FFT并行算法是與二進(jìn)制、超立方體邏輯拓?fù)浣Y(jié)構(gòu)密切相關(guān)的典型快速算法，其并行算法教學(xué)主要講授基于按位交換與基于數(shù)組重分布兩類(lèi)并行算法，并著重強(qiáng)調(diào)其對(duì)其他快速算法并行算法設(shè)計(jì)的參考意義。

（四）并行算法編程實(shí)踐模塊

并行算法編程實(shí)踐模塊包括分布存儲(chǔ)并行算法MPI實(shí)現(xiàn)、共享存儲(chǔ)并行算法OpenMP實(shí)現(xiàn)、并行程序的課堂實(shí)踐共3個(gè)子模塊。

分布存儲(chǔ)并行算法MPI實(shí)現(xiàn)主要介紹實(shí)現(xiàn)最簡(jiǎn)單MPI編程的6個(gè)基本函數(shù)，以及結(jié)合減少交互開(kāi)銷(xiāo)影響方法的理論知識(shí)，介紹在MPI中的相關(guān)實(shí)現(xiàn)措施。實(shí)現(xiàn)簡(jiǎn)單MPI并行程序的6個(gè)基本函數(shù)是該子模塊的核心和最重要內(nèi)容，旨在讓學(xué)生能直接動(dòng)手實(shí)踐，并增強(qiáng)對(duì)并行計(jì)算的感性認(rèn)識(shí)。共享存儲(chǔ)并行算法OpenMP實(shí)現(xiàn)主要介紹基本指導(dǎo)語(yǔ)句、基本庫(kù)函數(shù)與環(huán)境變量，旨在培養(yǎng)學(xué)生采用OpenMP進(jìn)行并行計(jì)算的基本能力，側(cè)重Parallel與循環(huán)指導(dǎo)語(yǔ)句，以及數(shù)據(jù)屬性子句與環(huán)境變量等內(nèi)容。同時(shí)，與MPI編程實(shí)現(xiàn)進(jìn)行對(duì)照，理解二者各自?xún)?yōu)缺點(diǎn)及各自適用性。并行程序的課堂實(shí)踐主要從矩陣乘并行算法與Jacobi迭代并行算法中挑選其一，進(jìn)行MPI編程實(shí)現(xiàn)，并進(jìn)行并行算法與所編并行程序的性能評(píng)估，以培養(yǎng)與檢驗(yàn)學(xué)生對(duì)已經(jīng)設(shè)計(jì)好的并行算法，直接進(jìn)行簡(jiǎn)單編程實(shí)踐，并對(duì)所編寫(xiě)并行程序進(jìn)行正確性驗(yàn)證，與對(duì)并行程序進(jìn)行性能分析評(píng)估，以及基于此的可能優(yōu)化改進(jìn)途徑分析等方面的能力。

本課程中的編程實(shí)踐側(cè)重于最基本的編程實(shí)現(xiàn)，主要用于增強(qiáng)學(xué)生的學(xué)習(xí)興趣，提高學(xué)生動(dòng)手能力，進(jìn)而進(jìn)一步加深學(xué)生對(duì)所學(xué)基本概念與基本理論知識(shí)的理解與掌握，同時(shí)強(qiáng)化對(duì)并行算法設(shè)計(jì)、實(shí)現(xiàn)到評(píng)價(jià)全過(guò)程的了解。同時(shí)，對(duì)并行程序進(jìn)行課堂實(shí)踐，課堂上未完成者允許其課后自行完成，但強(qiáng)調(diào)完成時(shí)的自主性，通過(guò)同時(shí)提交并行程序代碼與實(shí)踐報(bào)告進(jìn)行考核。

結(jié)語(yǔ)

本文對(duì)國(guó)防科技大學(xué)“并行算法”課程教學(xué)團(tuán)隊(duì)近年來(lái)在課程內(nèi)容改革方面的探索進(jìn)行了介紹，并著重闡述了在整個(gè)教學(xué)過(guò)程設(shè)計(jì)從任務(wù)分解、任務(wù)調(diào)度，到算法設(shè)計(jì)全過(guò)程中，對(duì)并行計(jì)算思維訓(xùn)練的考慮，以及結(jié)合并行計(jì)算思維訓(xùn)練與理論實(shí)際結(jié)合理念下的教學(xué)內(nèi)容模塊化組織改革探索，在將整個(gè)教學(xué)內(nèi)容組織成并行計(jì)算基本概念、并行算法設(shè)計(jì)基本技術(shù)、典型并行算法與并行算法編程實(shí)踐四大模塊的基礎(chǔ)上，再對(duì)每個(gè)模塊再按子模塊的方式進(jìn)行組織。組織過(guò)程中，著重強(qiáng)調(diào)典型并行算法與并行算法編程實(shí)踐兩模塊主要側(cè)重于加深對(duì)基本理論知識(shí)的理解，強(qiáng)化并行計(jì)算思維的訓(xùn)練。教學(xué)內(nèi)容的優(yōu)化設(shè)計(jì)，改進(jìn)了課程內(nèi)容的組織方式與教學(xué)實(shí)施的便利性，也更有利于促進(jìn)學(xué)生綜合素質(zhì)的提高。