并行計算與程序設計

普通高等院?！笆濉币?guī)劃教材

并行計算與程序設計

劉其成胡佳男孫雪姣畢遠偉童向榮編著

梁小芝

內容簡介

本書對并行計算的理論知識和并行程序設計方法進行了系統(tǒng)的介紹，包括并行計算基本概念、并行

計算機基礎、并行計算模型、并行計算性能評測、并行算法設計基礎、OpenMP多線程并行程序設計、

MPI消息傳遞并行程序設計、Windows線程庫并行程序設計、Java多線程并行程序設計等內容。

本書集作者多年的教學經(jīng)驗編寫而成，語言通俗易懂，內容安排合理，講解深入淺出。本書在介紹

并行計算理論知識的基礎上，特別注重并行程序設計的實踐方法及實用性。書中含有大量精心設計并調

試通過的程序實例，方便讀者參考。

本書適合作為普通高等院校計算機科學與技術專業(yè)、軟件工程專業(yè)以及信息類相關專業(yè)本科生和研

究生的教材，也可作為社會培訓教材或軟件開發(fā)人員的參考用書。

圖書在版編目（CIP）數(shù)據(jù)

并行計算與程序設計/劉其成等編著.—北京:

中國鐵道出版社,2014.6

普通高等院?！笆濉币?guī)劃教材

ISBN978-7-113-18390-5

Ⅰ.①并…Ⅱ.①劉…Ⅲ.①并行算法－高等學校－

教材②并行程序－程序設計－高等學校－教材Ⅳ.

①TP301.6②TP311.11

中國版本圖書館CIP數(shù)據(jù)核字(2014)第107439號

書名：并行計算與程序設計

作者：劉其成胡佳男孫雪姣畢遠偉童向榮編著

策劃：劉麗麗讀者熱線：400-668-0820

責任編輯：周欣彭立輝

封面設計：劉穎

責任校對：湯淑梅

責任印制：李佳

出版發(fā)行：中國鐵道出版社（100054，北京市西城區(qū)右安門西街8號）

網(wǎng)址：http://

印刷：北京昌平百善印刷廠

版次：2014年6月第1版2014年6月第1次印刷

開本：787mm×1092mm1/16印張：13.5字數(shù)：337千

印數(shù)：1～2000冊

書號：ISBN978-7-113-18390-5

定價：29.00元

版權所有侵權必究

凡購買鐵道版圖書，如有印制質量問題，請與本社教材圖書營銷部聯(lián)系調換。電話：（010）63550836

打擊盜版舉報電話：（010）51873659

FOREWORD前言

本書緊密結合相關專業(yè)規(guī)范，面向高等院校的學生和從事軟件開發(fā)以及相關領域的工程技術

人員，在充分考慮普通高等院校學生實際情況的基礎上，覆蓋并行計算課程要求的知識單元和知

識點。

教學內容、教學方法、教學手段的改革是每個教育工作者的重要任務。編者根據(jù)多年的教學和

軟件開發(fā)經(jīng)驗，以使用多年的講義為基礎，對本書的內容取舍、組織編排和實例進行了精心設計。

本書在難易程度上遵循由淺入深、循序漸進的原則，特別考慮到普通高等學校本科學生的實際理解

和接受能力。與以往許多相關教材主要以理論為主不同，本書突出實用性，將復雜的理論融于具體

的實例和程序中。書中的實例經(jīng)過精心設計挑選，程序代碼已認真調試，可以直接運行，為讀者理

解和使用提供了方便。同時，本書注重培養(yǎng)學生的自學能力和獲取知識的能力。在編寫過程中，力

圖在內容編排、敘述方法上為教師留有發(fā)揮空間的同時，也為學生留下自學空間。

全書共分9章：第1章通過一系列實例，介紹了并行計算和并行程序設計的基礎知識，以及

一些相關概念；第2章介紹了并行計算機的體系結構、并行計算機的分類，以及多核技術和GPU

技術；第3章介紹了并行計算模型的概念，以及PRAM模型、LogP模型和BSP模型，并且對幾

種常見模型進行了比較；第4章介紹了并行計算性能評測的基本概念、并行系統(tǒng)的性能分析方法、

并行系統(tǒng)可擴展性度量指標；第5章介紹了并行算法的設計方法、并行算法的設計過程、并行算

法設計技術；第6章介紹了OpenMP主要編譯指導語句、OpenMP主要運行時庫函數(shù)、OpenMP主

要環(huán)境變量、OpenMP多線程程序性能分析；第7章介紹了MPI消息傳遞接口及MPICH實現(xiàn)、

MPI編程基礎、MPI點對點通信和MPI群集通信方法；第8章介紹了Windows線程庫基本知識、

Win32API線程函數(shù)、MFC和.NETFramework線程處理相關類庫；第9章介紹了Java線程的相關

知識、JavaRunnable接口與Thread類實現(xiàn)多線程的方法，以及Java解決線程同步與死鎖的方法。

本書由劉其成、胡佳男、孫雪姣、畢遠偉、童向榮編著，其中第1章由畢遠偉編寫，第2章

由童向榮編寫，第3~4章、6~8章由劉其成編寫，第5章由孫雪姣編寫，第9章由胡佳男編寫。

另外，張瑩瑩、邵珠方參與了部分內容的編寫，鄭文靜繪制了部分圖形。劉其成設計了全書的結

構，并對全書進行了統(tǒng)稿。

在本書的編寫過程中，參閱了大量書籍和其他相關資料，得到了張偉教授及中國鐵道出版社

的支持和幫助，在此表示衷心感謝。

盡管書稿幾經(jīng)修改，但由于作者學識有限，書中難免有疏漏與不當之處，懇請各位同仁、讀

者不吝賜教。

編者

2014年4月

CONTENTS目錄

第1章概述..................................................................................................................1

1.1實例.....................................................................................................................................................1

1.1.1求和.........................................................................................................................................1

1.1.2泡茶問題..................................................................................................................................2

1.1.3圖書館新書上架......................................................................................................................2

1.1.4天氣預報..................................................................................................................................3

1.1.5美國HPCC計劃......................................................................................................................3

1.1.6教務管理系統(tǒng)..........................................................................................................................3

1.1.7地球物理石油勘探數(shù)據(jù)處理系統(tǒng)...........................................................................................4

1.2并行計算基礎知識..............................................................................................................................5

1.2.1并行計算的重要性..................................................................................................................5

1.2.2并行計算的定義、并行計算機系統(tǒng)及軟件............................................................................6

1.2.3并行計算的應用分類..............................................................................................................6

1.2.4并行設計的方法......................................................................................................................7

1.2.5應用系統(tǒng)的并行性..................................................................................................................8

1.2.6并行計算的研究內容..............................................................................................................8

1.3并行程序設計策略和模型...................................................................................................................9

1.3.1并行程序設計策略..................................................................................................................9

1.3.2并行程序設計模型..................................................................................................................9

1.4相關概念............................................................................................................................................10

1.4.1順序、并發(fā)與并行................................................................................................................10

1.4.2進程和線程............................................................................................................................11

1.4.3一些基本概念........................................................................................................................12

第2章并行計算機基礎...............................................................................................14

2.1并行計算機體系結構........................................................................................................................14

2.1.1結點.......................................................................................................................................15

2.1.2互聯(lián)網(wǎng)絡................................................................................................................................15

2.1.3并行計算機訪存模型............................................................................................................19

2.2并行計算機的分類............................................................................................................................20

2.2.1并行計算機的控制結構.........................................................................................................20

2.2.2地址空間................................................................................................................................21

2.2.3并行計算機系統(tǒng)結構模型.....................................................................................................21

2.3多核技術............................................................................................................................................27

2.3.1多核芯片................................................................................................................................27

2.3.2片上多核處理器體系結構.....................................................................................................28

2.3.3超線程技術............................................................................................................................29

2.3.4基于多核的軟件開發(fā)............................................................................................................30

2.3.5虛擬化技術............................................................................................................................30

2.4GPU技術...........................................................................................................................................30

2.4.1簡介.......................................................................................................................................30

2.4.2GPU與并行計算....................................................................................................................31

·1·

并行計算與程序設計

第3章并行計算模型..................................................................................................32

3.1并行計算模型概述............................................................................................................................32

3.1.1串行計算模型與并行計算模型.............................................................................................32

3.1.2并行計算模型與并行算法.....................................................................................................32

3.1.3并行計算模型與并行系統(tǒng)中其他模型的關系......................................................................33

3.2PRAM模型........................................................................................................................................33

3.2.1基本PRAM模型....................................................................................................................33

3.2.2實例.......................................................................................................................................34

3.3BSP模型............................................................................................................................................35

3.3.1BSP模型原理........................................................................................................................35

3.3.2實例.......................................................................................................................................36

3.4LogP模型...........................................................................................................................................37

3.4.1LogP模型原理.......................................................................................................................37

3.4.2實例.......................................................................................................................................37

3.5并行計算模型比較............................................................................................................................38

3.5.1PRAM模型和LogP模型的比較............................................................................................38

3.5.2BSP模型和LogP模型的比較...............................................................................................38

第4章并行計算性能評測............................................................................................39

4.1基本概念............................................................................................................................................39

4.1.1運行時間................................................................................................................................39

4.1.2問題規(guī)模................................................................................................................................40

4.1.3額外開銷函數(shù)........................................................................................................................40

4.2并行系統(tǒng)的性能分析........................................................................................................................42

4.2.1加速比...................................................................................................................................42

4.2.2效率.......................................................................................................................................46

4.2.3開銷.......................................................................................................................................47

4.2.4粒度和數(shù)據(jù)映射對性能的影響.............................................................................................47

4.2.5實例.......................................................................................................................................48

4.3并行系統(tǒng)的可擴展性度量.................................................................................................................48

4.3.1可擴展性................................................................................................................................48

4.3.2度量指標................................................................................................................................50

4.3.3實例.......................................................................................................................................52

第5章并行算法設計基礎............................................................................................53

5.1并行算法設計方法............................................................................................................................53

5.1.1基本方法................................................................................................................................53

5.1.2實例.......................................................................................................................................54

5.2并行算法設計過程............................................................................................................................56

5.2.1PCAM設計方法學.................................................................................................................57

5.2.2劃分.......................................................................................................................................57

5.2.3通信.......................................................................................................................................59

5.2.4組合.......................................................................................................................................61

5.2.5映射.......................................................................................................................................63

5.3并行算法設計技術............................................................................................................................64

·2·

目錄

第6章OpenMP多線程并行程序設計..........................................................................66

6.1OpenMP編程基礎..............................................................................................................................66

6.1.1OpenMP多線程編程模型......................................................................................................66

6.1.2OpenMP程序結構..................................................................................................................67

6.1.3使用MicrosoftVisualStudio.NET編寫OpenMP程序............................................................68

6.2編譯指導語句....................................................................................................................................70

6.2.1并行域結構——parallel指令...............................................................................................71

6.2.2共享任務結構........................................................................................................................71

6.2.3同步結構................................................................................................................................78

6.2.4數(shù)據(jù)處理子句........................................................................................................................83

6.3運行時庫函數(shù)....................................................................................................................................92

6.3.1基本函數(shù)................................................................................................................................93

6.3.2運行時庫函數(shù)的互斥鎖支持.................................................................................................94

6.4環(huán)境變量............................................................................................................................................95

6.5實例...................................................................................................................................................96

6.5.1求和.......................................................................................................................................96

6.5.2數(shù)值積分..............................................................................................................................101

6.6OpenMP多線程程序性能分析........................................................................................................106

6.6.1并行額外開銷......................................................................................................................106

6.6.2線程同步帶來的開銷..........................................................................................................108

6.6.3負載均衡..............................................................................................................................109

6.6.4OpenMP中的任務調度........................................................................................................111

第7章MPI消息傳遞并行程序設計.............................................................................119

7.1MPI消息傳遞接口...........................................................................................................................119

7.1.1簡介.....................................................................................................................................119

7.1.2MPI程序特點......................................................................................................................119

7.2典型MPI實現(xiàn)——MPICH...............................................................................................................121

7.2.1簡介.....................................................................................................................................121

7.2.2MPICH的安裝和配置..........................................................................................................121

7.3MPI編程基礎..................................................................................................................................126

7.3.1簡單的MPI程序示例..........................................................................................................126

7.3.2MPI程序的四個基本函數(shù)...................................................................................................127

7.3.3統(tǒng)計時間..............................................................................................................................127

7.3.4錯誤管理..............................................................................................................................128

7.4MPI的點對點通信...........................................................................................................................128

7.4.1點對點通信的例子..............................................................................................................128

7.4.2MPI_SEND()函數(shù)..................................................................................................................129

7.4.3MPI_RECV()函數(shù).................................................................................................................129

7.4.4消息管理七要素..................................................................................................................130

7.4.5非阻塞通信..........................................................................................................................132

7.5MPI群集通信..................................................................................................................................132

7.5.1一對多群集通信函數(shù)..........................................................................................................133

7.5.2多對一群集通信函數(shù)..........................................................................................................133

7.5.3多對多群集通信函數(shù)..........................................................................................................135

·3·

并行計算與程序設計

7.5.4同步函數(shù)..............................................................................................................................136

7.6實例.................................................................................................................................................136

7.6.1求和.....................................................................................................................................136

7.6.2數(shù)值積分..............................................................................................................................137

第8章Windows線程庫并行程序設計.......................................................................140

8.1Windows線程庫...............................................................................................................................140

8.2Win32API多線程程序設計............................................................................................................140

8.2.1Win32API線程操作基本函數(shù)............................................................................................140

8.2.2Win32API線程間通信函數(shù)................................................................................................145

8.3MFC線程庫.....................................................................................................................................156

8.3.1MFC線程操作基本函數(shù)......................................................................................................156

8.3.2MFC同步類.........................................................................................................................157

8.4.NETFramework線程庫...................................................................................................................162

8.4.1.NET線程基本操作.............................................................................................................162

8.4.2.NET線程同步.....................................................................................................................163

8.5實例.................................................................................................................................................175

8.5.1求和.....................................................................................................................................175

8.5.2數(shù)值積分..............................................................................................................................179

第9章Java多線程并行程序設計..............................................................................185

9.1線程.................................................................................................................................................185

9.1.1基本概念..............................................................................................................................185

9.1.2線程的狀態(tài)與生命周期.......................................................................................................186

9.1.3線程調度與優(yōu)先級..............................................................................................................186

9.2Runnable接口與Thread類.............................................................................................................187

9.2.1Runnable接口......................................................................................................................187

9.2.2Thread類..............................................................................................................................187

9.3多線程的實現(xiàn).................................................................................................................................