2003年高性能計(jì)算培訓(xùn)I班材料

2003年高性能計(jì)算培訓(xùn)I班材料*

遲學(xué)斌中國(guó)科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心

張林波中國(guó)科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院

莫?jiǎng)t堯北京應(yīng)用物理與計(jì)算數(shù)學(xué)研究所

2003年8月28日

本文檔及程序示例可從九卅p:〃Zssc.cc.QC.cn/training2OO3卜載

目錄

I第一部分并行計(jì)算基礎(chǔ)I1

|第一章并行計(jì)算基礎(chǔ)知識(shí)|3

|第二章并行計(jì)算機(jī)體系結(jié)構(gòu)I23

I第三章Linux*jfWl37

§3.1引言|37

§3.2構(gòu)建Linux機(jī)群的要素］37

§3.3幾種典型的Linux機(jī)群結(jié)構(gòu)|38

§3.3.1單臺(tái)薇和38

§3.3.2由幾臺(tái)「I常使用的微機(jī)構(gòu)成的機(jī)群|38

§3.3.3專(zhuān)用并行機(jī)群|38

|§3.4在單機(jī)上安裝、配置MPI并行環(huán)境|39

§3.4.1Linux的安裝|39

§3.4.2MPICH的安裝|39

|§3.5在聯(lián)網(wǎng)的多臺(tái)機(jī)器上安裝、配置MPI并行環(huán)回40

§3.5.1設(shè)置而回41

§3.5.2設(shè)置麗42

§3.5.3設(shè)置rsh43

§3.5.4MPICH的安裝|43

§3.5.5MPICH程序的編譯、運(yùn)行|43

§3.6專(zhuān)用并行機(jī)群系統(tǒng)|44

§3.7組建大型機(jī)群系統(tǒng)需要考慮的一些問(wèn)題|45

|第四章矩陣并行計(jì)算|47

根4.1矩陣相乘的若干并行算法|47

§4.1.1行列戈U分算法］一.47

§4.1.2行行劃分算法一.48

§4.1.3列列劃分算法一.48

§4.1.4列行劃分算法一.49

§4.1.5Cannon算法49

|§4.2線(xiàn)性方程組的解法|50

一§421分布式系統(tǒng)的并行LU分解算法|一.51

§422具仃共享存儲(chǔ)系統(tǒng)的并行LU分解算法|52

§423三角方程組的并行解法|53

|§4.3對(duì)稱(chēng)正定線(xiàn)性方程組的并麗困..55

§4.3.1Cholesky分解列格式的并行計(jì)算|55

§4.3.2雙曲變換Cholesky分解|56

11目錄

|§4.3.3修正的雙曲變換Cholesky分解|58

恰4.4三對(duì)角方程組的并行解法］59

§4.4.1遞推法］59

§4.4.2分裂法］61

除4.5異步并行送褥見(jiàn)61

§4.5.1異步并行迭代法基礎(chǔ)|....62

§4.5.2線(xiàn)性迭代的?般收斂性結(jié)巢］62

第二部分MPI并行程序設(shè)計(jì)|65

|第五章消息傳遞并行程序設(shè)計(jì)平臺(tái)MPI|67

§5.1MPI并行環(huán)境管理函數(shù)|67

§5.2進(jìn)程控制確..68

§5.3MPI進(jìn)程組操作函藪168

§5.4MPI通信子操作|71

§5.5點(diǎn)到點(diǎn)通存硒］73

§5.6阻塞式通蓿函教73

§5.7非阻塞式通信函數(shù)|.78

§5.8特殊的點(diǎn)到點(diǎn)通信函數(shù)|82

§5.9MPI的通信模式|84

§5.10用戶(hù)定義的數(shù)據(jù)類(lèi)型與打包85

jj5.H用戶(hù)定義的數(shù)據(jù)類(lèi)型|85

§5.12MPI的數(shù)據(jù)打包與拆包90

§5.13聚合通宿］93

障礙同方

§5.1493

§5.15單點(diǎn)與多點(diǎn)通信函數(shù)93

§5.16多點(diǎn)與多點(diǎn)通信函數(shù)97

§5.17全局歸約操作|100

§5.18進(jìn)程拓?fù)浣Y(jié)構(gòu)106

§5.18.1迪卡爾拓?fù)浣Y(jié)構(gòu)|106

§5.18.2一般拓?fù)浣Y(jié)構(gòu)|109

§5.18.3底層支持函數(shù)110

第六章文件輸入輸出（MPI-IO）113

§6.1基本113

§6.2基本文件操作|114

§6.2.1打開(kāi)MPI文件|114

§6.2.2關(guān)閉MPI文件|115

§623刪除環(huán)1115

§6.2.4設(shè)定文件長(zhǎng)度|115

§625為文件預(yù)留空間|115

目錄m

|§6.2.6查詢(xún)文件長(zhǎng)度|116

恰6.3查詢(xún)文件參數(shù)|116

§6.3.1查詢(xún)打開(kāi)文件的進(jìn)程細(xì)116

§6.3.2查詢(xún)文件訪問(wèn)模式|116

|§6.4設(shè)定文件視窗|116

§6.4.1文件中的數(shù)據(jù)表示格式|117

§642可移植數(shù)據(jù)類(lèi)型|117

§6.4.3查詢(xún)數(shù)據(jù)類(lèi)型相應(yīng)于文件數(shù)據(jù)表示格式［網(wǎng)118

|§6.5文件讀寫(xiě)操作|118

一§6.5.1使用顯式位移的阻塞型文件讀寫(xiě)|.119

§6.5.2使用獨(dú)立文件指針的阻塞型文件讀寫(xiě)|119

§6.5.3使用共享文件指針的阻塞型文件讀寫(xiě)|120

§654非阻塞型文件讀寫(xiě)函數(shù)］120

§6.5.5分裂型文件讀寫(xiě)函數(shù)|121

|§6.6文件指針操作|121

§6.6.1獨(dú)立文件指針操作|121

§6.6.2共享文件指針操作|122

§6.6.3文件位移在文件中的絕對(duì)地址|122

|§6.7不同進(jìn)程對(duì)同一文件讀寫(xiě)操作的相容性123

§671設(shè)定文件訪問(wèn)的原子性|123

§6.7.2杏詢(xún)atomicity的當(dāng)前值|124

§673文件讀寫(xiě)叮存儲(chǔ)設(shè)備間麗羽124

|§6.8子數(shù)組數(shù)據(jù)類(lèi)型創(chuàng)建函數(shù)］124

|第七章MPI程序示例|127

|§7.1矩陣乘積|127

§7.1.1算法描畫(huà)127

§7.1.2MPI并行程序|127

§7.1.3MPI并行程序的皎詡131

|§7.2Poisson方程求解|133

一§721并行算法設(shè)計(jì)|.133

§722MPI并行程序設(shè)計(jì)］134

§723MPI并行程序的故跡］138

I參考文獻(xiàn)I143

I附錄I145

|§A.lUnpack性能測(cè)試|145

§A.L1相關(guān)鏈接］145

§A.L2HPL簡(jiǎn)介|145

§A.1.3適用于Linux的BLAS庫(kù)|145

§A.1.4HPL的編譯、運(yùn)行與性能優(yōu)化|146

第一部分

并行計(jì)算基礎(chǔ)

第一章并行計(jì)算基礎(chǔ)知識(shí)

1.并行計(jì)算機(jī)的發(fā)展

1.1計(jì)算機(jī)系統(tǒng)發(fā)展簡(jiǎn)史

計(jì)算機(jī)的起源可以追溯到歐洲文藝復(fù)興時(shí)期。16-17世紀(jì)的思想解放和社會(huì)大變革，大

大促進(jìn)了自然科學(xué)技術(shù)的發(fā)展，其中制造?臺(tái)能幫助人進(jìn)行計(jì)算的機(jī)器，就是最耀眼的思想

火花之一。

1614年，蘇格蘭人JohnNapier發(fā)表了關(guān)于可以計(jì)算四則運(yùn)算和方根運(yùn)算的精巧裝置的

論文。1642年，法國(guó)數(shù)學(xué)家Pascal發(fā)明能進(jìn)行八位計(jì)算的計(jì)算尺。1848年，英國(guó)數(shù)學(xué)家

GeorgeBoole創(chuàng)立二進(jìn)制代數(shù)學(xué)。1880年美國(guó)普查人工用了7年的時(shí)間進(jìn)行統(tǒng)計(jì)，而1890

年，HermanHollerith用穿孔卡片存儲(chǔ)數(shù)據(jù)，并設(shè)計(jì)了機(jī)器，僅僅用了6個(gè)周就得出了準(zhǔn)確

的數(shù)據(jù)(62622250人)。1896年，HermanHollerith創(chuàng)辦了IBM公司的前身。

這些“計(jì)算機(jī)”，都是基于機(jī)械運(yùn)行方式，還沒(méi)有計(jì)算機(jī)的靈魂：邏輯運(yùn)算。而在這之

后，隨著電子技術(shù)的飛速發(fā)展，計(jì)算機(jī)開(kāi)始了質(zhì)的轉(zhuǎn)變。

1943年到1959年時(shí)期的計(jì)算機(jī)通常被稱(chēng)作第一代計(jì)算機(jī)。使用真空電子管，所有的程

序都是用機(jī)器碼編寫(xiě)，使用穿孔卡片。1946年，JohnW.Mauchly和J.PresperEckert負(fù)責(zé)研

制的ENIAC(ElectronicNumericalIntegratorandComputer)是第一臺(tái)真正意義上的數(shù)字電子

計(jì)算機(jī)。重30噸，18000個(gè)電子管，功率25千瓦。主要用于彈道計(jì)算和氫彈研制。

1949年，科學(xué)雜志大膽預(yù)測(cè)“未來(lái)的計(jì)算機(jī)不會(huì)超過(guò)1.5噸。”

真空管時(shí)代的計(jì)算機(jī)盡管已經(jīng)步入了現(xiàn)代計(jì)算機(jī)的范疇，但其體積之大、能耗之高、故

障之多、價(jià)格之貴大大制約了它的普及應(yīng)用。直到1947年,Bell實(shí)驗(yàn)室的WilliamB.Shockley.

JohnBardeen和WalterH.Brattain.發(fā)明了晶體管，電子計(jì)算機(jī)才找到了騰匕的起點(diǎn)，開(kāi)辟了

電子時(shí)代新紀(jì)元。

1959年到1964年間設(shè)計(jì)的計(jì)算機(jī)一般被稱(chēng)為第二代計(jì)算機(jī)。大量采用了晶體管和印刷

電路。計(jì)算機(jī)體積不斷縮小，功能不斷增強(qiáng)，可以運(yùn)行FORTRAN和COBOL,接收英文

字符命令。出現(xiàn)大量應(yīng)用軟件。

盡管晶體管的采用大大縮小了計(jì)算機(jī)的體積、降低了其價(jià)格，減少了故障。但離人們的

要求仍差很遠(yuǎn)，而且各行業(yè)對(duì)計(jì)算機(jī)也產(chǎn)生了較大的需求，生產(chǎn)更強(qiáng)、更輕便、更便宜的機(jī)

3

器成了當(dāng)務(wù)之急，而集成電路的發(fā)明，不僅僅使體積得以減小，更使速度加快，故障減少。

1958年，在RobertNoyce（INTEL公司的創(chuàng)始人）的領(lǐng)導(dǎo)下，繼發(fā)明了集成電路后，

又推出了微處理器。

1964年到1972年的計(jì)算機(jī)一般被稱(chēng)為第三代計(jì)算機(jī)。大量使用集成電路，典型的機(jī)型

是IBM360系列。1972年以后的計(jì)算機(jī)習(xí)慣上被稱(chēng)為第四代計(jì)算機(jī)?；诖笠?guī)模集成電路,

及后來(lái)的超大規(guī)模集成電路。計(jì)算機(jī)功能更強(qiáng)，體積更小。

在這之前，計(jì)算機(jī)技術(shù)主要集中在大型機(jī)和小型機(jī)領(lǐng)域發(fā)展，但隨著超大規(guī)模集成電路

和微處理器技術(shù)的進(jìn)步，計(jì)算機(jī)進(jìn)入尋常百姓家的技術(shù)障礙已突破。特別是從INTEL發(fā)布

其面向個(gè)人機(jī)的微處理器8080的同時(shí):互聯(lián)網(wǎng)技術(shù)、多媒體技術(shù)也得到了空前的發(fā)展，計(jì)

算機(jī)真正開(kāi)始改變?nèi)藗兊纳睢?/p>

1976年，Cray-1,第一臺(tái)商用超級(jí)計(jì)算機(jī)。集成了20萬(wàn)個(gè)晶體管，每秒進(jìn)行1.5億次

浮點(diǎn)運(yùn)算。今天，INTEL已經(jīng)推出主頻達(dá)到3.06Ghz的處理器，并已經(jīng)推出了4.7G主頻的

Pentium4樣品。

與整個(gè)人類(lèi)的發(fā)展歷程相比、與傳統(tǒng)科學(xué)技術(shù)相比，計(jì)算機(jī)的歷史才剛剛開(kāi)始書(shū)寫(xiě)，我

們正置身其中，感受其日新月異的變化，被計(jì)算機(jī)大潮裹挾著絲毫不得停歇。

1.2并行計(jì)算機(jī)發(fā)展簡(jiǎn)述

40年代開(kāi)始的現(xiàn)代計(jì)算機(jī)發(fā)展歷程可以分為兩個(gè)明顯的發(fā)展時(shí)代：串行計(jì)算時(shí)代、并

行計(jì)算時(shí)代。每一個(gè)計(jì)算時(shí)代都從體系結(jié)構(gòu)發(fā)展開(kāi)始，接著是系統(tǒng)軟件（特別是編譯器可操

作系統(tǒng)）、應(yīng)用軟件，最后隨著問(wèn)題求解環(huán)境的發(fā)展而達(dá)到頂峰。創(chuàng)建和使用并行計(jì)算機(jī)的

主要原因是因?yàn)椴⑿杏?jì)算機(jī)是解決單處理器速度瓶頸的最好方法之一。

并行計(jì)算機(jī)是由一組處理單元組成的，這組處理單元通過(guò)相互之間的通信與協(xié)作，以更

快的速度共同完成一項(xiàng)大規(guī)模的計(jì)算任務(wù)。因此，并行計(jì)算機(jī)的兩個(gè)最主要的組成部分是計(jì)

算節(jié)點(diǎn)和節(jié)點(diǎn)間的通信與協(xié)作機(jī)制。并行計(jì)算機(jī)體系結(jié)構(gòu)的發(fā)展也主要體現(xiàn)在計(jì)算節(jié)點(diǎn)性能

的提高以及節(jié)點(diǎn)間通信技術(shù)的改進(jìn)兩方面。

60年代初期，由于晶體管以及磁芯存儲(chǔ)器的出現(xiàn)，處理單元變得越來(lái)越小，存儲(chǔ)器也

更加小巧和廉價(jià)。這些技術(shù)發(fā)展的結(jié)果導(dǎo)致了并行計(jì)算機(jī)的出現(xiàn)，這一時(shí)期的并行計(jì)算機(jī)多

是規(guī)模不大的共享存儲(chǔ)多處理器系統(tǒng)，即所謂大型主機(jī)（Mainframe）。IBM360是這一時(shí)期

的典型代表。

到了60年代末期，同一個(gè)處理器開(kāi)始設(shè)置多個(gè)功能相同的功能單元，流水線(xiàn)技術(shù)也出

4

現(xiàn)了。與單純提高時(shí)鐘頻率相比，這些并行特性在處理器內(nèi)部的應(yīng)用大大提高了并行計(jì)算機(jī)

系統(tǒng)的性能。伊利諾依大學(xué)和Burroughs公司此時(shí)開(kāi)始實(shí)施HliacIV計(jì)劃，研制一臺(tái)64個(gè)

CPU的SIMD主機(jī)系統(tǒng)，它涉及到硬件技術(shù)、體系結(jié)構(gòu)、I/O設(shè)備、操作系統(tǒng)、程序設(shè)計(jì)語(yǔ)

言直至應(yīng)用程序在內(nèi)的眾多研究課題。不過(guò)，當(dāng)一臺(tái)規(guī)模大大縮小了的16CPU系統(tǒng)終于在

1975年面世時(shí)，整個(gè)計(jì)算機(jī)界已經(jīng)發(fā)生了巨大變化。

首先是存儲(chǔ)系統(tǒng)概念的革新，提出虛擬存儲(chǔ)和緩存的思想。IBM360/85系統(tǒng)與360/91

是屬于同一系列的兩個(gè)機(jī)型，360/91的主頻高于360/85,所選用的內(nèi)存速度也較快，并且

采用了動(dòng)態(tài)調(diào)度的指令流水線(xiàn)；但是，360/85的整體性能卻高于360/91,唯一的原因就是

前者采用了緩存技術(shù)，而后者則沒(méi)有。

其次是半導(dǎo)體存儲(chǔ)器開(kāi)始代替磁芯存儲(chǔ)器。最初，半導(dǎo)體存儲(chǔ)器只是在某些機(jī)器被用作

緩存，而CDC7600則率先全面采用這種體積更小、速度更快、可以直接尋址的半導(dǎo)體存儲(chǔ)

器，磁芯存儲(chǔ)器從此退出了歷史舞臺(tái)。與此同時(shí)，集成電路也出現(xiàn)了，并迅速應(yīng)用到了計(jì)算

機(jī)中。元器件技術(shù)的這兩大革命性突破，使得HliacIV的設(shè)計(jì)者們?cè)诘讓佑布约安⑿畜w系

結(jié)構(gòu)方面提出的種種改進(jìn)都大為遜色。

1976年CRAY-1問(wèn)世以后，向量計(jì)算機(jī)從此牢牢地控制著整個(gè)高性能計(jì)算機(jī)市場(chǎng)15年。

CRAY-1對(duì)所使用的邏輯電路進(jìn)行了精心的設(shè)計(jì)，采用了我們?nèi)缃穹Q(chēng)為RISC的精簡(jiǎn)指令集,

還引入了向量寄存器，以完成向量運(yùn)算。這?系列全新技術(shù)手段的使用，使CRAY-1的主頻

達(dá)到了80MHzo

微處理器隨著機(jī)器的字長(zhǎng)從4位、8位、16位一直增加到32位，其性能也隨之顯著提

高。正是因?yàn)榭吹搅宋⑻幚砥鞯倪@種潛力，卡內(nèi)基-梅隆大學(xué)開(kāi)始在當(dāng)時(shí)流行的DECPDP11

小型計(jì)算機(jī)的基礎(chǔ)上研制成功一臺(tái)由16個(gè)PDP11/40處理機(jī)通過(guò)交叉開(kāi)關(guān)與16個(gè)共享存儲(chǔ)

器模塊相連接而成的共享存儲(chǔ)多處理器系統(tǒng)C.mmp。

從80年代開(kāi)始，微處理器技術(shù)一直在高速前進(jìn)。稍后又出現(xiàn)了非常適合于SMP方式

的總線(xiàn)協(xié)議，而伯克利加州大學(xué)則對(duì)總線(xiàn)協(xié)議進(jìn)行了擴(kuò)展，提出了Cache一致性問(wèn)題的處理

方案。從此，C.mmp開(kāi)創(chuàng)出的共享存儲(chǔ)多處理器之路越走越寬；現(xiàn)在，這種體系結(jié)構(gòu)已經(jīng)

基本上統(tǒng)治了服務(wù)器和桌面工作站市場(chǎng)。

同一時(shí)期，基于消息傳遞機(jī)制的并行計(jì)算機(jī)也開(kāi)始不斷涌現(xiàn)。80年代中期，加州理工

成功地將64個(gè)i8086/i8087處理器通過(guò)超立方體互連結(jié)構(gòu)連結(jié)起來(lái)。此后，便先后出現(xiàn)了Intel

iPSC系列、INMOSTransputer系列，IntelParagon以及IBMSP的前身Vulcan等基于消息

傳遞機(jī)制的并行計(jì)算機(jī)。

80年代末到90年代初，共享存儲(chǔ)器方式的大規(guī)模并行計(jì)算機(jī)又獲得了新的發(fā)展。IBM

5

將大量早期RISC微處理器通過(guò)蝶形互連網(wǎng)絡(luò)連結(jié)起來(lái)。人們開(kāi)始考慮如何才能在實(shí)現(xiàn)共享

存儲(chǔ)器緩存一致的同時(shí)，使系統(tǒng)具有一定的可擴(kuò)展性（Scalability90年代初期，斯坦福大

學(xué)提出了DASH計(jì)劃，它通過(guò)維護(hù)一個(gè)保存有每一緩存塊位置信息的目錄結(jié)構(gòu)來(lái)實(shí)現(xiàn)分布

式共享存儲(chǔ)器的緩存一致性。后來(lái)，IEEE在此基礎(chǔ)上提出了緩存一致性協(xié)議的標(biāo)準(zhǔn)。

90年代以來(lái)，主要的幾種體系結(jié)構(gòu)開(kāi)始走向融合。屬于數(shù)據(jù)并行類(lèi)型的CM-5除大量

采用商品化的微處理器以外，也允許用戶(hù)層的程序傳遞一些簡(jiǎn)單的消息；CRAYT3D是一臺(tái)

NUMA結(jié)構(gòu)的共享存儲(chǔ)型并行計(jì)算機(jī)，但是它也提供了全局同步機(jī)制、消息隊(duì)列機(jī)制，并

采取了一些減少消息傳遞延遲的技術(shù)。

隨著商品化微處理器、網(wǎng)絡(luò)設(shè)備的發(fā)展，以及MPI/PVM等并行編程標(biāo)準(zhǔn)的發(fā)布，機(jī)群

架構(gòu)的并行計(jì)算機(jī)出現(xiàn)。IBMSP2系列機(jī)群系統(tǒng)就是其中的典型代表。在這些系統(tǒng)中，各個(gè)

節(jié)點(diǎn)采用的都是標(biāo)準(zhǔn)的商品化計(jì)算機(jī)，它們之間通過(guò)高速網(wǎng)絡(luò)連接起來(lái)。

今天，越來(lái)越多的并行計(jì)算機(jī)系統(tǒng)采用商品化的微處理器加上商品化的互連網(wǎng)絡(luò)構(gòu)造，

這種分布存儲(chǔ)的并行計(jì)算機(jī)系統(tǒng)稱(chēng)為機(jī)群。國(guó)內(nèi)幾乎所有的高性能計(jì)算機(jī)廠商都生產(chǎn)這種具

有極高性能價(jià)格比的高性能計(jì)算機(jī)，并行計(jì)算機(jī)就進(jìn)入了一個(gè)新的時(shí)代，并行計(jì)算的應(yīng)用達(dá)

到了前所未有的廣度和深度。

1.3可擴(kuò)展的并行計(jì)算機(jī)體系結(jié)構(gòu)

根據(jù)指令流和數(shù)據(jù)流的不同，通常把計(jì)算機(jī)系統(tǒng)分為：?jiǎn)沃噶盍鲉螖?shù)據(jù)流（SISD）、單

指令流多數(shù)據(jù)流（SIMD）、多指令流單數(shù)據(jù)流（MISD）、多指令流多數(shù)據(jù)流（MIMD）四類(lèi)。

并行計(jì)算機(jī)系統(tǒng)除少量專(zhuān)用的SIMD系統(tǒng)外，絕大部分為MIMD系統(tǒng)，包括并行向量機(jī)

（PVP,ParallelVectorProcessor）；對(duì)稱(chēng)多處理機(jī)（SMP,SymmetricMultiprocessor）；大規(guī)模

并行處理機(jī)（MPP,MassivelyParallelProcessor）；機(jī)群（Cluster）；分布式共享存儲(chǔ)多處理

機(jī)（DSM,DistributiedSharedMemory）o這5種并行計(jì)算機(jī)的結(jié)構(gòu)模型參見(jiàn)圖1。

6

圖1MIMD系統(tǒng)結(jié)構(gòu)示意圖

其中B：(Bridge)是存儲(chǔ)總線(xiàn)和I/O總線(xiàn)的接口;DIR：(CacheDirectory)是高速緩存目錄；

IOB：(I/OBus)是I/O總線(xiàn)；LD：(LocalDisk)是本地硬盤(pán);MB：(MemoryBus)是存儲(chǔ)

器總線(xiàn)；NIC：(NetworkInterfaceCircuitry)是網(wǎng)絡(luò)接口電路；P/C：(MicroprocessorandCache)

是微處理器和高速緩存；SM：(SharedMemory)是共享存儲(chǔ)器。

PVP典型的并行向量處理機(jī)結(jié)構(gòu)示意圖如圖1(A)。我國(guó)的銀河1號(hào)、目前全球top500

中排名第一的地球模擬器等都是PVPo專(zhuān)門(mén)設(shè)計(jì)定制的高帶寬交叉開(kāi)關(guān)網(wǎng)絡(luò)將專(zhuān)門(mén)設(shè)計(jì)定

制的向量處理器VP與共享存儲(chǔ)模塊連接起來(lái)，一般不使用高速緩存，而是使用大量的向量

寄存器和指令緩沖器。

SMP對(duì)稱(chēng)多處理機(jī)的結(jié)構(gòu)示意圖如圖1(B)。我國(guó)曙光1號(hào)，SGIPowerChallenge等

大量的服務(wù)器或工作站都是這類(lèi)機(jī)器。SMP系統(tǒng)一般使用商品化微處理器，具有片上或外

置高速緩存，經(jīng)由高速總線(xiàn)(或交叉開(kāi)關(guān))連向共享存儲(chǔ)器。每個(gè)處理器可等同地訪問(wèn)共享

存儲(chǔ)器、I/O設(shè)備和操作系統(tǒng)服務(wù)。SMP的主要特點(diǎn)是：?jiǎn)我徊僮飨到y(tǒng)映像，全系統(tǒng)只有一

7

個(gè)操作系統(tǒng)駐留在共享存儲(chǔ)器中，它根據(jù)各個(gè)處理器的負(fù)載情況，動(dòng)態(tài)地分配各個(gè)進(jìn)程到各

個(gè)處理器，并保持各個(gè)處理器間的負(fù)載平衡；低通信延遲，各個(gè)進(jìn)程通過(guò)讀/寫(xiě)操作系統(tǒng)提

供的共享數(shù)據(jù)緩存區(qū)來(lái)完成處理器間的通信，其延遲通常小于網(wǎng)絡(luò)通信延遲;共享總線(xiàn)帶寬，

所有處理器共享總線(xiàn)帶寬，完成對(duì)內(nèi)存模塊和I/O模塊的訪問(wèn)。同時(shí)，SMP也具有如下」

些問(wèn)題：欠可靠，總線(xiàn)、存儲(chǔ)器、操作系統(tǒng)失效可能導(dǎo)致系統(tǒng)崩潰；可擴(kuò)展性較差，由于所

有處理器都共享總線(xiàn)帶寬，而總線(xiàn)帶寬每3年才增加2倍，趕不上處理器速度和存儲(chǔ)容量的

增長(zhǎng)步伐，因此SMP的處理器個(gè)數(shù)一般少于64個(gè)，且只能提供每秒數(shù)百億次的浮點(diǎn)運(yùn)算。

SMP的典型代表有:SGIPOWERChallengeXL系列、DECAlphaserver84005/440、

HP9000/T600和IBMRS6000/R40?

MPP大規(guī)模并行處理機(jī)的結(jié)構(gòu)示意圖如圖（C）。我國(guó)曙光1000、IBMSP2都是這種類(lèi)

型的機(jī)器。MPP一般采用商品化微處理器和專(zhuān)門(mén)設(shè)計(jì)的互連網(wǎng)絡(luò)，系統(tǒng)可以擴(kuò)展到數(shù)千個(gè)

（甚至更多）處理器。

DSM分布式共享存儲(chǔ)多處理機(jī)的結(jié)構(gòu)示意圖如圖1（D）。高速緩存目錄DIR用以支持

分布高速緩存的一致性。處理器對(duì)物理分布的共享存儲(chǔ)器的訪問(wèn)是不對(duì)稱(chēng)的，這也是DSM

與SMP的區(qū)別所在。DSM的典型代表為SGI的0rigin2000和0rigin3000系列并行機(jī)，圖

1.2列出了SGI0rigin2000的體系結(jié)構(gòu)。相對(duì)于SMP,DSM具有如下主要特征：物理上分

布存儲(chǔ)，內(nèi)存模塊局部在各個(gè)節(jié)點(diǎn)上，并通過(guò)高速互連網(wǎng)絡(luò)互連，避免了SMP訪問(wèn)總線(xiàn)的

帶寬瓶頸，增強(qiáng)了并行機(jī)的可擴(kuò)展能力；單一內(nèi)存地址空間，盡管內(nèi)存模塊分布在各個(gè)節(jié)點(diǎn)

上，但是所有這些內(nèi)存模塊都由硬件進(jìn)行了統(tǒng)?編址，并通過(guò)互連網(wǎng)絡(luò)形成了并行機(jī)的共享

存儲(chǔ)器。各個(gè)節(jié)點(diǎn)既可以訪問(wèn)局部?jī)?nèi)存單元（本地訪問(wèn)），又可以直接訪問(wèn)其他節(jié)點(diǎn)的局部

內(nèi)存單元（遠(yuǎn)端訪問(wèn)）；非一致內(nèi)存訪問(wèn)模式（NUMA）,由于遠(yuǎn)端訪問(wèn)必須通過(guò)高性能互

連網(wǎng)絡(luò)，而本地訪問(wèn)只需要直接訪問(wèn)局部?jī)?nèi)存模塊，因此遠(yuǎn)端訪問(wèn)延遲一般是本地訪問(wèn)延遲

的3倍以上；單一的系統(tǒng)映像，類(lèi)似于SMP,在DSM中，用戶(hù)只看到一個(gè)操作系統(tǒng)，它可

以根據(jù)各節(jié)點(diǎn)的負(fù)載情況，動(dòng)態(tài)地分配進(jìn)程；基于Cache的數(shù)據(jù)一致性通常采用基于目錄

的Cache一致性協(xié)議來(lái)保證各節(jié)點(diǎn)的局部Cache數(shù)據(jù)和存儲(chǔ)器中數(shù)據(jù)的一致性。同時(shí)，這種

DSM也稱(chēng)為CC-NUMA結(jié)構(gòu)。

DSM較好地改善了SMP的可擴(kuò)展性能。一般地，DSM可以擴(kuò)展到上百個(gè)節(jié)點(diǎn)，能提

供每秒數(shù)千億次的浮點(diǎn)運(yùn)算功能。但由于受Cache一致性要求和互連網(wǎng)絡(luò)性能的限制，當(dāng)節(jié)

點(diǎn)數(shù)目進(jìn)一步增加時(shí)，DSM并行機(jī)的性能也將大幅下降。

機(jī)群（或工作站機(jī)群，COW）的結(jié)構(gòu)示意圖如圖（E）o我國(guó)的曙光1000A,曙光2000、

曙光3000以及前不久推出的曙光4000L等都是機(jī)群架構(gòu)的并行計(jì)算機(jī)。COW的每個(gè)系統(tǒng)

都是一個(gè)完整的工作站，一個(gè)節(jié)點(diǎn)可以是一臺(tái)PC或SMP,各個(gè)節(jié)點(diǎn)一般由商品化的網(wǎng)絡(luò)互

8

連，每個(gè)節(jié)點(diǎn)一般有本地磁盤(pán)，節(jié)點(diǎn)上的網(wǎng)絡(luò)接口是松散耦合到I/O總線(xiàn)上的，一個(gè)完整的

操作系統(tǒng)駐留在每個(gè)節(jié)點(diǎn)上。

SMP、MPP、DSM和COW等并行結(jié)構(gòu)趨向融合，DSM是SMP和MPP的自然結(jié)合，

MPP和COW的界限逐漸模糊。在中國(guó)現(xiàn)在使用PVP并行向量機(jī)很少，使用最多的是SMP、

DSM、Cluster架構(gòu)的并行計(jì)算機(jī)。國(guó)內(nèi)主要的高性能計(jì)算機(jī)廠商如曙光、聯(lián)想、浪潮生產(chǎn)

的都是Cluster架構(gòu)的并行計(jì)算機(jī)。節(jié)點(diǎn)為2/4個(gè)處理器的SMP,互連網(wǎng)絡(luò)為千兆網(wǎng)、myrinet

等，節(jié)點(diǎn)操作系統(tǒng)一般為L(zhǎng)inux。

和SMP、DSM等相比，機(jī)群在較低的費(fèi)用下，具有高性能、可擴(kuò)展性、高吞吐量、易

用性等特點(diǎn)。按照應(yīng)用目的（科學(xué)計(jì)算/商業(yè)計(jì)算）分類(lèi)，機(jī)群可分為高性能機(jī)群和高可用

機(jī)群；按照節(jié)點(diǎn)硬件分類(lèi)，可以分為PC機(jī)群、工作站機(jī)群、SMP機(jī)群；按照節(jié)點(diǎn)操作系統(tǒng)

分類(lèi)，可以分為L(zhǎng)inux機(jī)群、NT機(jī)群等；按照節(jié)點(diǎn)體系結(jié)構(gòu)和操作系統(tǒng)的類(lèi)型，可分為同

構(gòu)機(jī)群、異構(gòu)機(jī)群等。

1.4機(jī)群系統(tǒng)的發(fā)展

機(jī)群系統(tǒng)由節(jié)點(diǎn)機(jī)、互連網(wǎng)絡(luò)與通信軟件、機(jī)群中間件等構(gòu)成。下面從這三方面敘述機(jī)

群系統(tǒng)的發(fā)展?fàn)顩r。

1.4.1機(jī)群節(jié)點(diǎn)的發(fā)展

機(jī)群節(jié)點(diǎn)機(jī)?般為PC、工作站、SMP,其基本組成為處理器、內(nèi)存和緩存、磁盤(pán)、系

統(tǒng)總線(xiàn)等構(gòu)成。20多年來(lái)，微處理器結(jié)構(gòu)（RISC、CISC、VLIW和向量處理器）和工藝發(fā)

展迅速，今天單片CPU比20年前的超級(jí)計(jì)算機(jī)更為強(qiáng)大。

1）CPU技術(shù)的發(fā)展

隨著CPU主頻向GHz時(shí)代的推進(jìn)，長(zhǎng)期處于實(shí)驗(yàn)室階段的銅工藝取得了突破性進(jìn)展，

有望取代鋁工藝而成為CPU制造的主流技術(shù)。銅工藝最大的好處是使CPU在高頻率下的運(yùn)

行更加穩(wěn)定。要解決微處理器提速難題，改進(jìn)制造工藝只是目前通用的一種方法，采用新型

晶體管結(jié)構(gòu)也是目前業(yè)界正在研究的重點(diǎn)課題。從2000年底開(kāi)始，Intel、AMD、IBM、貝

爾實(shí)驗(yàn)室都公布了類(lèi)似的最新科研成果。2001年底，Intel公司宣布發(fā)明了一種命名為

“TeraHertz”的晶體管結(jié)構(gòu)，晶體管的切換速度可達(dá)每秒1萬(wàn)億次，Intel將利用該晶體管

制造微處理器，預(yù)計(jì)2005年前其微處理器速度將達(dá)10GHz,2010年將達(dá)20GHz。AMD公

司2001年底也宣布已成功開(kāi)發(fā)一款迄今為止開(kāi)關(guān)速度最快的CMOS晶體管，開(kāi)關(guān)速度高達(dá)

每秒3.33萬(wàn)億（trillion）次，顯示了AMD公司有能力在十年內(nèi)將每一芯片的晶體管數(shù)目增加

9

20倍，而令微處理器的性能提升10倍。

當(dāng)前，主流微處理器仍然是Intel的IA-64、IBM的Power>Compaq的Alpha和SUN的

UtraSPARC、HP的PA-RISC系列、SGI的MIPS和AMD的Opteron處理器。

Intel推出第一代的IA-64Itanium后，已成功進(jìn)軍高端服務(wù)器市場(chǎng)。新?，代Itanium在一

枚芯片上集成一級(jí)緩存(16KB,數(shù)據(jù)傳輸帶寬為19.2GB/S),二級(jí)緩存(256KB,數(shù)據(jù)傳輸

帶寬為72GB/S),三級(jí)緩存(3MB,數(shù)據(jù)傳輸帶寬達(dá)64GB/s),工作頻率達(dá)1.2GHz以上。

Compaq在高速處理器領(lǐng)域曾處于領(lǐng)先地位。2001年6月Compaq宣布向Intel轉(zhuǎn)讓

Alpha微處理器和編譯技術(shù)、工具及資源。Compaq在EV6之后，曾計(jì)劃開(kāi)發(fā)EV7、EV8甚

至EV9,具體是2002年推出EV7(0.18pm),時(shí)鐘超過(guò)1GHz；2004年能期望獲得EV8,

時(shí)鐘超過(guò)1.5GHz。IBM公司目前的主力型號(hào)有POWER3和POWER4。POWER4時(shí)鐘頻率

超過(guò)IGHzoPOWER4之后將開(kāi)發(fā)POWER4+和POWER4++或POWER5。IBM計(jì)劃在其推

出POWER5之前，使每年的處理器時(shí)鐘數(shù)提高25%,性能增長(zhǎng)3倍。

SGI公司的MIPS系列微處理器主要用于Origin服務(wù)器。MIPS系列微處理器目前的主

力產(chǎn)品是R12000(400MHz,800MFLOPS)和R14000(500MHz,1GFLPOS)。2002年將

推出R16000(650MHz,1.2GFLPOS)。2003年推出R18000(800MHz,3.2GFLPOS)。2004

年推出R20000(超過(guò)1GHz,4GFLPOS)。

AMD公司2002年底推出的Opteron處理器是能夠兼容32位的64位處理器，對(duì)Intel

的Itanium構(gòu)成巨大沖擊，Itanium現(xiàn)在為用戶(hù)所詬病的就是對(duì)Intel以前的32位的應(yīng)用兼容

性不好。剛剛推出的Opteron246(2.0GHz,4.0GFLOPS)。

未來(lái)幾年，各廠商將在增加可以同時(shí)執(zhí)行的指令數(shù)；采用銅布線(xiàn)等新的半導(dǎo)體技術(shù)；采

用SOI等先進(jìn)的加工工藝；安裝大容量片內(nèi)高速緩存；配備高速存儲(chǔ)器輸入輸出的設(shè)備，

提高處理器與外部存儲(chǔ)器及其他處理器之間的數(shù)據(jù)速率；增加多媒體功能等多方面持續(xù)改

進(jìn)，這些高性能微處理器在處理性能方面都將比現(xiàn)有產(chǎn)品有大幅提高。當(dāng)前及未來(lái)的一些典

型微處理器發(fā)展歸納為下表。

表1典型微處理器發(fā)展預(yù)測(cè)

制造商2001年2002年2003年2004年

Intel公司ItaniumMckinleyMadison?

800MHzZ1.2GHz2GHz?

SGI公司RI4000RI6000RI8000R20000

500MHz+650MHz800MHz+1GHz+

CompaqEV68CEV7EV79轉(zhuǎn)向IA-64

1.25GHz1.2GHz1.6-1.7GHz

HP公司PA-8700PA-8800PA-8900轉(zhuǎn)向IA-64

720MHz900MHz1.2GHz

IBM公司POWER4POWER4+POWER4-H-?POWERS?

10

lGHz+1.25GHz?1.55GHz?2GHz?

SUN公司UltraSPARCIVUltraSPARCV99

1GHz1.5GHz

AMD公司Opteron240?250;Opteron252

1.4-2.4GHz2.6GHz

2）節(jié)點(diǎn)操作系統(tǒng)

現(xiàn)代操作系統(tǒng)位用戶(hù)提供兩個(gè)基本的功能，第一是使計(jì)算機(jī)更容易使用，用戶(hù)使用的是

操作系統(tǒng)提供的虛擬機(jī)而無(wú)須與計(jì)算機(jī)硬件直接打交道。第二是可讓用戶(hù)共享硬件資源。多

任務(wù)操作系統(tǒng)為每個(gè)進(jìn)程分配要執(zhí)行的工作，為每個(gè)進(jìn)程分配內(nèi)存和系統(tǒng)資源，在一個(gè)進(jìn)程

中，至少要分配一個(gè)執(zhí)行的線(xiàn)程或一個(gè)可執(zhí)行單元?，F(xiàn)代操作系統(tǒng)還支持在程序內(nèi)部對(duì)多線(xiàn)

程進(jìn)行控制，因此并行處理可以進(jìn)程內(nèi)多線(xiàn)程的方式進(jìn)行。

目前機(jī)群系統(tǒng)節(jié)點(diǎn)中最流行的操作系統(tǒng)恐怕是Linux了。Hnux最初是由芬蘭赫爾辛基

大學(xué)計(jì)算機(jī)系大學(xué)生LinusTorvalds在從1990年底到1991年的兒個(gè)月中陸續(xù)編寫(xiě)的，1993

年，Linus決定轉(zhuǎn)向GPL版權(quán)。一些軟件公司如RedHat、InfoMagic等適時(shí)推出以Linux為

核心的操作系統(tǒng)版本，大大地推動(dòng)了Linux的商品化。

linux的主要特點(diǎn)是，開(kāi)放性、標(biāo)準(zhǔn)化、多用戶(hù)、多任務(wù)，Linux可以連續(xù)運(yùn)行數(shù)月、數(shù)

年而無(wú)須重新啟動(dòng)，一臺(tái)Linux服務(wù)器支持100-300個(gè)用戶(hù)毫無(wú)問(wèn)題。Linux向用戶(hù)提供三

種界面：用戶(hù)命令界面、系統(tǒng)調(diào)用界面和圖形用戶(hù)界面。Linux一般由四個(gè)部分組成：內(nèi)核、

Shell、文件系統(tǒng)和實(shí)用工具。內(nèi)核是運(yùn)行程序和管理磁盤(pán)、打印機(jī)等硬件設(shè)備的核心程序。

它從用戶(hù)那里接受命令并把命令送到內(nèi)核去執(zhí)行。Shell是系統(tǒng)的用戶(hù)界面，提供了系統(tǒng)與

內(nèi)核進(jìn)行交互操作的一種接口。它接受用戶(hù)輸入的命令，并把它送到內(nèi)核去執(zhí)行。實(shí)際上

Shell是一個(gè)命令解釋器，Shell有自己的編程語(yǔ)言，它允許用戶(hù)編寫(xiě)由Shell命令組成的程

序。

每個(gè)Linux系統(tǒng)的用戶(hù)可以擁有自己的用戶(hù)界面和Shell,用以滿(mǎn)足他們自己專(zhuān)門(mén)的Shell

需要。同Linux一樣，Shell也有多種不同的版本。目前主要有下列版本的Shell：BourneShell

（貝爾實(shí)驗(yàn)室開(kāi)發(fā)）、Bash（GNU的BourneAgainShell,是GNU操作系統(tǒng)上默認(rèn)的Shell）＞

KornShell（對(duì)BourneShell的發(fā)展，大部分與BourneShell兼容）、CShell（Sun公司Shell

的BSD版本）。

Linux實(shí)用工具可以分為三類(lèi)：編輯器、過(guò)濾器、交互程序。

Linux的內(nèi)核版本是在Linus領(lǐng)導(dǎo)下的開(kāi)發(fā)小組開(kāi)發(fā)出的系統(tǒng)內(nèi)核的版本號(hào)。一般說(shuō)來(lái),

以序號(hào)的第二位為偶數(shù)的版本表明這是一個(gè)可以使用的穩(wěn)定的版本。?些組織和廠商將

Linux的系統(tǒng)內(nèi)核與應(yīng)用程序和文檔包裝起來(lái),并提供一些安裝界面和系統(tǒng)設(shè)定的管理工具，

11

這樣就構(gòu)成了一個(gè)發(fā)行套件。

1.4.2機(jī)群互連網(wǎng)絡(luò)

機(jī)群節(jié)點(diǎn)通過(guò)使用標(biāo)準(zhǔn)網(wǎng)絡(luò)協(xié)議（如TCP/IP）或底層協(xié)議（如活動(dòng)消息）來(lái)進(jìn)行通信。

從性能（延遲和帶寬）來(lái)看，以太網(wǎng)連接并不能提供足夠的性能，它的帶寬和延遲不能和目

前節(jié)點(diǎn)的計(jì)算能力很好地匹配，而其它如SCLMyrinet等則提供比較好的性能。機(jī)群系統(tǒng)

一般會(huì)有幾套網(wǎng)絡(luò)，各有不同功能，根據(jù)其功能并考慮性能價(jià)格的平衡，選用相應(yīng)的網(wǎng)絡(luò)。

10/100/1000Mb以太網(wǎng)標(biāo)準(zhǔn)以太網(wǎng)（10Mb/S）已很少用于作為機(jī)群系統(tǒng)的互連網(wǎng)絡(luò)，

目前快速以太網(wǎng)（100Mb/S）往往用于作為機(jī)群系統(tǒng)控制網(wǎng)絡(luò)和監(jiān)控網(wǎng)絡(luò)。目前許多機(jī)群系

統(tǒng)采用千兆以太網(wǎng)（1000Mb/S）作為計(jì)算網(wǎng)絡(luò)。千兆網(wǎng)絡(luò)最大的優(yōu)點(diǎn)是，機(jī)群系統(tǒng)計(jì)算網(wǎng)

絡(luò)從快速以太網(wǎng)升級(jí)到千兆網(wǎng)，應(yīng)用可以平滑過(guò)渡。千兆網(wǎng)絡(luò)可以采用銅線(xiàn)或光纜進(jìn)行連接。

MyrinetMyrinet是Myricom提供的全雙工互連網(wǎng)絡(luò)，使用低延遲的開(kāi)通式路由開(kāi)關(guān)，

通過(guò)自動(dòng)映射網(wǎng)絡(luò)配置來(lái)提供容錯(cuò)。Myrinet提供低延遲（5微秒，單向點(diǎn)對(duì)點(diǎn)）、高吞吐率

和可編程板上處理器，其主要缺點(diǎn)是價(jià)格比較昂貴。

1.4.3機(jī)群中間件和單一系統(tǒng)映像（SSI）

如果一群互連的計(jì)算機(jī)被設(shè)計(jì)成看起來(lái)如同統(tǒng)一的資源，我們就說(shuō)該系統(tǒng)實(shí)現(xiàn)了單一系

統(tǒng)映像（SSI,SingleSystemImage）?SSI是用中間件層實(shí)現(xiàn)的，處于操作系統(tǒng)和用戶(hù)層環(huán)境

中間。SSI支持的服務(wù)包括：?jiǎn)我蝗肟邳c(diǎn)，?個(gè)用戶(hù)可以像連接到單系統(tǒng)一樣連接至機(jī)群,

而不是像分布式系統(tǒng)一樣連接到單個(gè)節(jié)點(diǎn)；單一文件層次，用戶(hù)看到的文件系統(tǒng)是文件的單

一層次，目錄是在同一根目錄下的；單點(diǎn)管理和控制，整個(gè)機(jī)群可以從用單一GUI工具創(chuàng)

建的單一窗口進(jìn)行管理和控制；單一虛擬網(wǎng)絡(luò)，任何節(jié)點(diǎn)可以通過(guò)機(jī)群域訪問(wèn)網(wǎng)絡(luò)連接；單

一內(nèi)存空間，將屬于機(jī)群的各節(jié)點(diǎn)的內(nèi)存作為共享內(nèi)存；單一作業(yè)管理系統(tǒng)，用戶(hù)可以用透

明的作業(yè)提交機(jī)制在任一節(jié)點(diǎn)提交作業(yè)等等。

SSI的優(yōu)點(diǎn)包括：為整個(gè)系統(tǒng)資源和運(yùn)行情況在任一節(jié)點(diǎn)提供一個(gè)簡(jiǎn)單、直觀的視圖；

使最終用戶(hù)無(wú)須了解應(yīng)用在什么地方運(yùn)行；使操作者無(wú)須了解資源的物理位置；使管理者在

一點(diǎn)上管理整個(gè)機(jī)群；使得一個(gè)擁有多個(gè)進(jìn)程的并行應(yīng)用看起來(lái)就像一個(gè)串行應(yīng)用等等。目

前比較成熟的提供機(jī)群系統(tǒng)SSI的中間件/軟件/工具有：NFS（網(wǎng)絡(luò)文件系統(tǒng)）、LSF（作業(yè)

管理系統(tǒng)）等。

曙光系列機(jī)群提供了一套包括機(jī)群管理系統(tǒng)、機(jī)群作業(yè)管理系統(tǒng)、機(jī)群并行文件系統(tǒng)等

在內(nèi)的機(jī)群系統(tǒng)軟件，?定程度上實(shí)現(xiàn)了機(jī)群的SSI。

12

2.并行計(jì)算基本概念

2.1并行算法基礎(chǔ)知識(shí)

2.1.1并行算法定義與分類(lèi)

算法是解題的精確描述，是一組有窮的規(guī)則，它規(guī)定了解決某一特定類(lèi)型問(wèn)題的一系列

運(yùn)算。并行計(jì)算是可同時(shí)求解的諸進(jìn)程的集合，這些進(jìn)程相互作用和協(xié)調(diào)動(dòng)作，并最終獲得

問(wèn)題的求解。并行算法就是對(duì)并行計(jì)算過(guò)程的精確描述。

并行算法可以從不同的角度分類(lèi)為數(shù)值計(jì)算并行算法和非數(shù)值計(jì)算并行算法；同步并行

算法和異步并行算法；共享存儲(chǔ)并行算法和分布存儲(chǔ)并行算法。

數(shù)值計(jì)算是指基于代數(shù)關(guān)系運(yùn)算的計(jì)算問(wèn)題，如矩陣運(yùn)算、多項(xiàng)式求值、線(xiàn)性代數(shù)方程

組求解等。求解數(shù)值計(jì)算問(wèn)題的算法稱(chēng)為數(shù)值算法(NumericalAlgorithm科學(xué)與工程中

的計(jì)算問(wèn)題如計(jì)算力學(xué)、計(jì)算物理、計(jì)算化學(xué)等一般是數(shù)值計(jì)算問(wèn)題。非數(shù)值計(jì)算是指基于

比較關(guān)系運(yùn)算的一類(lèi)諸如排序、選擇、搜索、匹配等符號(hào)處理，相應(yīng)的算法也稱(chēng)為非數(shù)值算

法(Non-numericalAlgorithm)。非數(shù)值計(jì)算在符號(hào)類(lèi)信息處理中獲得廣泛應(yīng)用，如數(shù)據(jù)庫(kù)領(lǐng)

域的計(jì)算問(wèn)題、海量數(shù)據(jù)挖掘等，近年來(lái)廣泛關(guān)注的生物信息學(xué)主要也是非數(shù)值計(jì)算。

2.1.2并行算法復(fù)雜性

對(duì)算法進(jìn)行分析時(shí)，常要使用上界(UpperBound)、下界(LowerBound)和緊致界(Tightly

Bound)等概念。分別定義如下：

上界令〃制和g仇)是定義在自然數(shù)集合N上的兩個(gè)函數(shù)，如果存在正常數(shù)c和〃。，使得對(duì)

于所有均有*〃)<=cg伍),則稱(chēng)gW是/〃”的?個(gè)上界，記做/何=0例叨。

下界令和g勿是定義在自然數(shù)集合N上的兩個(gè)函數(shù)，如果存在正常數(shù)c和“0,使得對(duì)

于所有均有f(n)>=cg(n),則稱(chēng)名㈤是於)的一個(gè)下界，記做"值仞八

緊致界令〃力和g何是定義在自然數(shù)集合N上的兩個(gè)函數(shù)，如果存在正常數(shù)。八C2和〃。，

使得對(duì)于所有n>=n(),均有cig(n)<=f(n)<=c2g(n),則稱(chēng)卻〃)是力力)的一，個(gè)緊致界，記做

f(n)=&(g(n)).

在分析算法時(shí)，如果對(duì)算法的所有輸入分析其平均性態(tài)時(shí)的復(fù)雜度，則稱(chēng)之為期望復(fù)雜

度(ExpectedComplexity),在某些輸入時(shí)，可以使得算法的時(shí)間、空間復(fù)雜度最壞，此時(shí)

13

的復(fù)雜度稱(chēng)為最壞情況下的復(fù)雜度(Worst-CaseComplexity)o

2.1.3并行算法運(yùn)行時(shí)間

進(jìn)行并行計(jì)算的兩個(gè)基本目的是：在問(wèn)題規(guī)模一定的情況下，縮短求解時(shí)間；在給定時(shí)

間范圍內(nèi)，擴(kuò)大問(wèn)題求解規(guī)模。并行算法運(yùn)行時(shí)間表示算法開(kāi)始直到算法執(zhí)行完畢的時(shí)間，

主要包括輸入輸出(I/O)時(shí)間、計(jì)算CPU時(shí)間和并行開(kāi)銷(xiāo)(包括通信、同步等時(shí)間)。并

行開(kāi)銷(xiāo)是進(jìn)行并行計(jì)算而引入的開(kāi)銷(xiāo)。

對(duì)于一個(gè)具體的并行算法，對(duì)其計(jì)算時(shí)間的估計(jì)通常由上述三部分時(shí)間的界的估計(jì)所組

成。如果要求輸入輸出N個(gè)數(shù)據(jù)，則認(rèn)為該算法的I/O時(shí)間界為0(N)：如果問(wèn)題規(guī)模為n,

涉及的計(jì)算量一般為t(n),則該算法的計(jì)算CPU時(shí)間界為O(t(n))；對(duì)要求通信和同步的次

數(shù)為L(zhǎng)、通信量為M個(gè)數(shù)據(jù)，則該算法的并行開(kāi)銷(xiāo)為O(L+M)。

2.1.4問(wèn)題規(guī)模與分類(lèi)

高性能計(jì)算機(jī)產(chǎn)生和發(fā)展的就是為了滿(mǎn)足日益增長(zhǎng)的大規(guī)?？茖W(xué)與工程計(jì)算、事務(wù)處理

與商業(yè)計(jì)算的需求。問(wèn)題求解最大規(guī)模是并行計(jì)算機(jī)最重要的指標(biāo)之一，也是一個(gè)國(guó)家高新

技術(shù)發(fā)展的標(biāo)志。一般地，問(wèn)題規(guī)模分解為輸入輸出規(guī)模、計(jì)算規(guī)模、內(nèi)存需求、通信(同

步)規(guī)模，分別表示問(wèn)題求解所需要的i/o量、計(jì)算量、內(nèi)存大小和通信量(包括通信次數(shù)

與通信數(shù)據(jù)量)。

根據(jù)在求解中所消耗資源程度，問(wèn)題又相應(yīng)分為CPU密集應(yīng)用、memory密集應(yīng)用、disk

密集應(yīng)用和網(wǎng)絡(luò)密集應(yīng)用。針對(duì)不同類(lèi)型的問(wèn)題，性能瓶頸也往往不同，并行算法就是要又

針對(duì)性的消除相應(yīng)的瓶頸，從而達(dá)到縮短計(jì)算時(shí)間的目的。

2.1.5并行程序中數(shù)據(jù)相關(guān)性

機(jī)群中的并行通常表現(xiàn)在程序級(jí)或任務(wù)級(jí)。能否將順序執(zhí)行的程序轉(zhuǎn)換成語(yǔ)義等價(jià)的、

可并行執(zhí)行的程序，主要取決于程序的結(jié)構(gòu)形式，特別是其中的數(shù)據(jù)相關(guān)性。由于在機(jī)群上

并行運(yùn)行的程序段是異步的，所以在程序段之間會(huì)出現(xiàn)下面的3種數(shù)據(jù)相關(guān)。為敘述簡(jiǎn)單起

見(jiàn)，僅以賦值語(yǔ)句表示程序段P。

1)數(shù)據(jù)相關(guān)

若P1左邊變量出現(xiàn)在P2的右邊變量集內(nèi)時(shí)，則稱(chēng)P2數(shù)據(jù)相關(guān)于P1。例如：

Pl：A=B+C

14

P2：D=AxB

其中，變量A是導(dǎo)致Pl和P2發(fā)生數(shù)據(jù)相關(guān)的原因。為了保證程序執(zhí)行的語(yǔ)義正確性，變

量A必須是先在P1中寫(xiě)入后方可從P2中讀出，即必須先寫(xiě)后讀。顯然，P1和P2不能并

行執(zhí)行。

2）數(shù)據(jù)反相關(guān)

若P2的左邊變量出現(xiàn)在P1的右邊變量集內(nèi)時(shí)，則稱(chēng)P1數(shù)據(jù)反相關(guān)于P2。例如：

Pl：A=BxC

P2：C=E+D

Pl通過(guò)變量C數(shù)據(jù)相關(guān)于P2。為保證語(yǔ)義正確性，必須等P1將變量C讀出后，P2方可向

變量C進(jìn)行寫(xiě)入操作，即必須先讀后寫(xiě)。

3）數(shù)據(jù)輸出相關(guān)

若P1和P2的左邊變量相同，則稱(chēng)P2數(shù)據(jù)輸出相關(guān)于P1。例如：

Pl：A=B+C

P2：A=DxE

為保證語(yǔ)義正確性，必須保證P1先寫(xiě)入A,然后允許P2再寫(xiě)入A。

除了上述3種相關(guān)外，還存在一種特殊情況，即兩個(gè)程序段的輸入變量互為輸出變量.

此時(shí)，兩者必須并行執(zhí)行，方可保證語(yǔ)義的正確性。這就要求硬件機(jī)構(gòu)能保證兩者進(jìn)行同步

讀寫(xiě)。但若兩個(gè)處理機(jī)各帶有局部存儲(chǔ)器，則可降低同步要求。

4）數(shù)據(jù)相關(guān)判斷準(zhǔn)則

程序并行性檢測(cè)主要是判別程序中是否存在前述的各種數(shù)據(jù)相關(guān)。每個(gè)程序段在執(zhí)行過(guò)

程中通常要使用輸入和輸出這兩個(gè)分離的變量集。若用li表示Pi程序段中操作所要讀取的

存儲(chǔ)單元集，用Oi表示要寫(xiě)入的存儲(chǔ)單元集，則P1和P2兩個(gè)程序段能并行執(zhí)行的伯恩斯

坦準(zhǔn)則是：

11口02=中，即P1的輸入變量集與P2的輸出變量集不相交；

12001=0）,即P2的輸入變量集與P1的輸出變量集不相交；

01002-0）,即Pl和P2的輸出變量集不相交。

2.2并行計(jì)算模型

計(jì)算模型是對(duì)計(jì)算機(jī)的抽象。對(duì)于算法設(shè)計(jì)者而言，計(jì)算模型為設(shè)計(jì)、分析和評(píng)價(jià)算法

提供了基礎(chǔ)。馮.偌依曼機(jī)就是一個(gè)理想的串行計(jì)算模型，但現(xiàn)在還沒(méi)有一個(gè)通用的并行計(jì)

算模型。下面對(duì)PRAM模型、LogP模型進(jìn)行簡(jiǎn)單的介紹。

15

2.2.1PRAM模型

PRAM(ParallelRandomAccessMachine)模型，即并行隨機(jī)存取模型，是一種抽象的

并行計(jì)算模型。在這個(gè)模型中，假設(shè)存在著一個(gè)容量無(wú)限大的共享存儲(chǔ)器；每臺(tái)處理器有簡(jiǎn)

單的算術(shù)運(yùn)算和邏輯判斷功能；在任何時(shí)刻各處理器均可以通過(guò)共享存儲(chǔ)單元交換數(shù)據(jù)。

PRAM可分為SIMD-PRAM和MIMD-PRAMoSIMD-PRAM模型又可以細(xì)分為不允許同時(shí)

讀和同時(shí)寫(xiě)(Exclusive-ReadandExclusive-Write)的PRAM模型，簡(jiǎn)記為PRAM-EREW；

允許同時(shí)讀但不允許同時(shí)寫(xiě)(Concurrent-ReadandExclusive-Write)的PRAM-CREW模型；

允許同時(shí)讀寫(xiě)的PRAM-CRCW模型。當(dāng)然允許同時(shí)讀寫(xiě)是不現(xiàn)實(shí)的，因而又進(jìn)一步約定為

允許所有的處理器同時(shí)寫(xiě)相同的數(shù)，此時(shí)稱(chēng)為公共(Common)的PRAM-EREW模型，簡(jiǎn)

記為CPRAM-EREW模型；只允許最有優(yōu)先(Priority)的處理器先寫(xiě)，此時(shí)稱(chēng)為優(yōu)先的

PRAM-EREW,簡(jiǎn)記為PPRAM-EREW；允許任意(Arbitrary)的處理器自由寫(xiě)，此時(shí)稱(chēng)為

任意的PRAM-EREW,簡(jiǎn)記為APRAM-EREWo

SIMD-PRAM計(jì)算模型MIMD-PRAM計(jì)算模型

圖2PRAM計(jì)算模型

令TM表示某并行算法在并行計(jì)算模型M上的計(jì)算時(shí)間，則有：

TEREW>-=TCRCW

TEREW=O(TcREW*logP)=O(TcRCW*logP)

其中，p為處理器數(shù)目，上式的含義是，一個(gè)具有時(shí)間復(fù)雜度GREW和7CRC『的算法，可以

在PRAM-EREW模型上，花費(fèi)logP倍的時(shí)間模