算法與並行計算

《算法與並行計算》是清華大學出版社於2012年出版的書籍，作者是Fayez Gebali，譯者是都志輝。 本書正好可以滿足這樣一種需求，它提供了關於並行計算與並行算法設計的基本知識與具體的實現案例，可以指導我們設計高效的並行算法。

基本介紹

• 書名：算法與並行計算 
• 作者：Fayez Gebali 
• 譯者：都志輝 
• ISBN：9787302290094 
• 定價：39
• 出版社：清華大學出版社 
• 出版時間：2012-11-01
• 裝幀：平裝 
• 印刷時間：2012-10-30
• 印次：1-1

圖書簡介

受到能耗的限制，僅靠CPU提升工作頻率便可直接提升處理性能的方式已經不再適用。因此設計更多但是頻率更低的處理核心便成為處理器發展的方向。多核處理器成為趨勢，為了充分利用這些處理核心，必須採用並行方式才可以發掘它們的計算能力。因此並行處理就成了未來提高處理器性能的一種必需的手段。

圖書目錄

第1章 引言1

1.1 概述1

1.2 自動並行編程1

1.3 算法3

1.3.1 算法的有向圖3

1.3.2 算法的鄰接矩陣A4

1.3.3 基於子任務的依賴關係對算法進行分類5

1.3.4 串列算法6

1.3.5 並行算法6

1.3.6 SPA6

1.3.7 NSPA7

1.3.8 RIA8

1.3.9 並行算法實現8

1.4 設計並行計算系統9

1.5 並行算法和並行體系結構10

1.6 並行算法與並行體系結構相關10

1.7 算法的實現： 兩個方面的問題11

1.8 衡量並行計算的優勢11

1.8.1 加速比11

1.8.2 通信開銷12

1.8.3 計算加速比和通信開銷12

1.9 針對多處理器系統的Amdahl法則14

1.10 Gustafson-Barsis法則15

1.11 並行計算的套用16

1.11.1 氣象建模16

1.11.2 CT17

1.11.3 計算機流體力學（CFD) 18

1.12 習題18

第2章 增強單處理器的性能21

2.1 概述21

2.2 提高處理器的時鐘頻率21

2.3 ALU的並行化22

2.4 使用分級存儲器體系24

2.4.1 記憶體-高速快取之間的操作252.4.2 高速快取的設計26

2.4.3 分層高速快取26

2.4.4 將記憶體塊映射到高速快取行 26

2.4.5 關聯映射27

2.4.6 組相關映射28

2.4.7 快取容量對快取命中率的影響28

2.5 流水線作業28

估算流水線作業的速度29

2.6 超長指令字（VLIW）處理器32

2.7 指令級並行（ILP）和超標量處理器33

2.7.1 真實數據依賴： 寫後讀（RAW) 34

2.7.2 程式的依賴關係35

2.7.3 資源衝突35

2.7.4 輸出依賴性： 寫後寫（WAW) 35

2.7.5 反依賴： 讀後寫（WAR) 36

2.8 多執行緒處理器36

2.9 習題37

第3章 並行計算機39

3.1 概述39

3.2 並行計算39

3.3 共享記憶體的多處理器（統一記憶體訪問UMA) 40

3.4 分散式記憶體多處理器（非統一記憶體訪問NUMA) 41

3.5 SIMD處理器41

3.6 脈動式處理器42

3.7 集群計算44

3.8 格線計算（雲計算）44

3.9 多核系統44

3.10 流多處理器46

3.11 並行處理器之間的通信48

3.11.1 通信類型48

3.11.2 訊息傳遞（MP）通信機制49

3.12 並行體系結構總結50

3.13 習題50

第4章 共享記憶體多處理器52

4.1 概述52

4.2 高速快取一致性和記憶體一致性53

4.2.1 目錄協定56

4.2.2 Snoopy協定57

4.3 同步和互斥57

4.3.1 同步： 鎖機制58

4.3.2 同步： 互斥量59

4.3.3 同步： 柵欄60

4.3.4 同步原語的對比61

4.4 習題62

第5章 互連網路63

5.1 概述63

5.2 邏輯拓撲結構中互連網路的分類63

5.2.1 匯流排型63

5.2.2 星型64

5.2.3 環型64

5.2.4 網型64

5.2.5 交叉開關網路65

5.2.6 交叉開關網路的連線及仲裁66

5.2.7 多級互連網路66

5.2.8 榕樹（Banyan）網路66

5.2.9 樹型網路67

5.2.10 隨機拓撲網路68

5.3 網際網路交換架構68

5.3.1 輸入佇列交換器69

5.3.2 輸出佇列交換器70

5.3.3 共享緩衝區交換器71

5.3.4 多輸入佇列交換器73

5.3.5 多輸出佇列交換器73

5.3.6 多輸入輸出佇列交換器74

5.3.7 VRQ交換器75

5.4 習題76

第6章 並發平台78

6.1 概述78

6.2 並發平台78

6.3 Cilk++78

6.3.1 Cilk++並行循環： cilk_for79

6.3.2 數據競爭和程式不確定性80

6.3.3 將串列代碼並行化的Cilk++組件82

6.3.4 使用Cilk++實現矩陣乘法82

6.4 OpenMP84

6.4.1 OpenMP編譯指導語句85

6.4.2 編譯指導語句子句86

6.4.3 OpenMP負載分配87

6.4.4 循環指導語句： for87

6.4.5 循環指導語句： sections89

6.4.6 運行時庫函式90

6.4.7 環境變數90

6.4.8 OpenMP同步90

6.5 統一計算設備架構（CUDA) 91

6.5.1 定義CUDA中的執行緒、塊和格線93

6.5.2 將函式交付核心執行94

6.5.3 主機與CUDA設備間的通信95

6.5.4 CUDA執行緒的同步與通信95

6.5.5 核心和格線95

6.5.6 塊97

6.5.7 執行緒97

6.5.8 CUDA C語言擴展97

第7章 針對並行算法的特別技術98

7.1 概述98

7.2 定義算法變數99

7.3 獨立循環調度99

7.4 依賴循環100

7.5 針對簡單依賴循環的循環分發方法100

7.6 循環展開101

7.7 問題劃分101

7.8 分而治之(遞歸劃分)策略102

7.9 流水線104

7.10 習題106

第8章 非串列-並行算法107

8.1 概述107

8.2 並行化用DAG表示的NSPA算法108

8.3 分析NSPA的形式化方法109

矩陣的冪的意義: 矩陣的連通性110

8.4 辨別算法中的環112

8.5 提取串列及並行算法的性能參數113

8.6 相關定理114

8.7 串列和並行算法在並行計算機上的性能116

8.8 習題116

第9章 z-變換分析118

9.1 概述118

9.2 z-變換的定義118

9.3 一維有限脈衝回響濾波器算法119

9.4 z-變換的軟體硬體實現119

9.5 設計1: 用霍納法則實現廣播輸入管道輸出120

9.6 設計2: 管道輸入廣播輸出121

9.7 設計3: 管道輸入管道輸出122

9.8 習題123

第10章 依賴關係圖分析124

10.1 概述124

10.2 一維有限衝擊回響濾波算法124

10.3 算法的依賴關係圖124

10.4 計算算法的依賴關係圖125

定義D中的變數125

10.5 一維有限衝擊回響濾波的調度函式127

10.5.1 將依賴關係圖轉換為有向無環圖或串列-並行算法127

10.5.2 廣播變數128

10.5.3 流水變數128

10.5.4 確定調度函式129

10.5.5 線性執行緒/任務調度的限制130

10.5.6 非線性調度操作131

10.6 結點投影操作131

10.7 非線性投影操作132

使用並發平台133

10.8 有向無環圖分析的軟體和硬體實現133

10.8.1 設計方案1: 投影方向d?1=\?t133

10.8.2 設計方案2: 投影方向d?2=\?t134

10.9 習題135

第11章 計算幾何分析136

11.1 概述136

11.2 矩陣乘算法136

11.3 3D依賴圖和計算域D136

3D域邊界137

11.4 D的面和頂點138

11.5 算法變數的依賴矩陣138

11.6 依賴矩陣的零空間: 廣播子域B139

A的零空間139

11.7 設計空間的探索: 選擇廣播變數還是流水線變數141

11.7.1 饋送/提取廣播變數的點141

11.7.2 變數流水線143

11.8 數據調度143

調度函式對數據時序的影響146

11.9 使用線性投影運算元進行投影操作147

11.9.1 投影矩陣P147

11.9.2 投影方向148

11.9.3 投影方向d的選擇148

11.9.4 當投影方法d給定時，找出矩陣P149

11.10 投影操作對數據的影響150

11.10.1 輸出數據150

11.10.2 輸入數據M?2151

11.10.3 輸入數據M?3151

11.11 最終的多執行緒/多處理器體系結構151

11.12 本章總結152

11.13 習題152

第12章 實例: 一維IIR數字濾波器154

12.1 概述154

12.2 一維IIR數字濾波器算法154

12.3 IIR濾波器的依賴圖154

12.3.1 二維依賴圖154

12.3.2 一維濾波器的調度函式155

12.3.3 投影方向和投影矩陣的選擇157

12.3.4 設計1: 投影方向157

12.3.5 設計2: 投影方向157

12.4 一維IIR數字濾波器算法的z域分析159

12.4.1 設計3: 廣播輸入和流水線輸出159

12.4.2 流水線輸入和廣播輸出159

12.4.3 設計4: 流水線輸入和輸出159

12.5 習題161

第13章 案例分析: 二維與三維數字濾波器162

13.1 概述162

13.2 行和幀環繞問題162

13.3 二維遞歸濾波器163

13.3.1 二維IIR設計1: 廣播XY輸入、流水輸出163

13.3.2 二維IIR設計2: 流水XY輸入、廣播輸出164

13.4 三維數字濾波器165

13.4.1 三維IIR設計1: 廣播XY輸入、流水輸出166

13.4.2 三維IIR設計2: 流水化X和Y輸入、廣播輸出166

第14章 實例分析： 多重速率的採樣器和插值器168

14.1 概述168

14.2 採樣器的架構168

14.3 採樣器的依賴關係圖169

14.4 採樣器時序170

14.5 在s?1=\ 的情況下，採樣器的有向無環圖171

14.6 在s?2=\的情況下，插值器的有向無環圖172

14.7 在s?3=\的情況下，插值器的有向無環圖174

14.8 多相採樣器的實現174

14.9 插值器的架構175

14.10 插值器的依賴關係圖176

14.11 插值器的調度177

14.12 在s?1=\的情況下，插值器的有向無環圖178

14.13 在s?2=\ 的情況下，插值器的有向無環圖179

14.14 在s?3=\ 的情況下，插值器的有向無環圖180

14.15 多相插值器的實現181

第15章 案例學習: 模式匹配182

15.1 概述182

15.2 將算法表達為正則疊代算法(RIA)182

15.3 得到算法依賴圖183

15.4 數據調度183

15.5 DAG結點的投影184

15.6 設計方案1: 當s=\?t時的設計空間184

15.6.1 設計方案1.a: 設s=\?t, da=\?t185

15.6.2 設計方案1.b: 設s=\?t, db=\?t186

15.6.3 設計方案1.c: 設s=\?t, dc=\?t186

15.7 設計方案2: 當s=\?t時的設計空間搜尋187

15.7.1 設計方案2.a: 設s=\?t, da=\?t187

15.7.2 設計方案2.b: 設s=\?t, db=\?t187

15.7.3 設計方案2.c: 設s=\?t, dc=\?t188

15.8 設計方案3: 當s=\?t時的設計空間搜尋188

設計方案3.a: 設s=\?t , da=\?t188

第16章 案例學習: 用於視頻壓縮的運動估計189

16.1 概述189

16.2 FBMA189

16.3 數據緩衝要求190

16.4 FBMA的形式化191

16.5 運動估計的分層形式化191

16.5.1 第3層(最左層)192

16.5.2 第2層192

16.5.3 第1層192

16.5.4 第0層(最右層)192

16.6 層次化結構塊的硬體設計193

16.6.1 第3層的硬體設計193

16.6.2 第2層的硬體設計196

16.6.3 第1層的硬體設計197

16.6.4 第0層的硬體設計197

第17章 範例分析: 2?m階伽羅瓦域乘法198

17.1 概述198

17.2 2?m階伽羅瓦域乘法算法198

17.3 將域乘法表示為RIA200

17.4 域乘法的依賴圖200

17.5 數據調度201

17.6 DAG結點投影203

17.7 設計1: 使用d?1=\?t204

17.8 設計2: 使用d?2=\?t204

17.9 設計3: 使用d?3=\?t205

17.10 有限域乘法器的套用206

第18章 範例分析: 2?m階伽羅瓦域的多項式除法207

18.1 概述207

18.2 多項式除法算法207

18.3 LFSR依賴圖208

18.4 數據調度209

18.5 DAG結點投影210

18.6 設計1: s?1=\時的設計空間211

18.7 設計2: s?2=\時的設計空間212

18.8 設計3: s?3=\時的設計空間214

18.9 3種設計方案的比較215

第19章 快速傅立葉變換217

19.1 概述217

19.2 時分FFT218

19.3 流水線基2時分FFT處理器221

19.4 頻分FFT221

19.5 流水線基2頻分FFT處理器224

第20章 求解線性方程組225

20.1 概述225

20.2 特別矩陣結構225

20.2.1 平面旋轉(吉文斯)矩陣226

20.2.2 帶狀矩陣226

20.2.3 對角矩陣227

20.2.4 上三角矩陣227

20.2.5 下三角矩陣227

20.2.6 三對角矩陣227

20.2.7 上Hessenberg矩陣227

20.2.8 下Hessenberg矩陣228

20.3 前向替代(直接技術)228

20.3.1 前向替代依賴圖228

20.3.2 前向替代規劃方程和有向無環圖(DAG)229

20.3.3 前向替代投影函式230

20.4 回代230

20.5 矩陣三角化算法230

20.5.1 Givens旋轉算法232

20.5.2 矩陣三角化調度函式233

20.5.3 矩陣三角化投影方向234

20.6 連續超額鬆弛(SOR)(疊代法)234

20.6.1 SOR算法235

20.6.2 SOR算法調度算法235

20.6.3 SOR算法的投影方向236

20.7 習題237

第21章 使用有限差分法求解偏微分方程238

21.1 概述238

21.2 1-D系統的FDM239

21.2.1 1-D FDM的調度函式240

21.2.2 投影方向242

參考文獻243

圖書前言

本書大概可以分為兩大部分，第1～11章側重於基本的並行算法與知識的介紹，第12～21章側重於如何利用前面介紹的知識來解決具體的套用問題。其中，第1章對本書中出現的幾種重要算法： 串列算法，並行算法，以及正則疊代算法等進行了介紹。第2章介紹了提升單處理器性能的手段。第3章介紹了並行計算機的主要類型，包括： 共享記憶體，分散式記憶體，單指令多數據流，脈動陣列以及多核系統。第4章介紹了共享記憶體多核系統以及緊密相關的兩個問題： 高速快取一致性和處理器同步。第5章介紹了並行處理器的集中內部網際網路： 匯流排型，星型，環型，以及網路拓撲，探討了幾種更高效的網路類型： 交換陣列，多層級網路。第6章介紹了用於開發並行套用的並發平台軟體工具，包括Cilk++、OpenMP以及統一計算設備架構（CUDA) 。第7章介紹了特定算法在並行計算機上的實現方法、算法任務級別的流水線處理等。第8章介紹了NSPA算法的處理方法，NSPA是指無法歸類於串列、並行或者是串並行的算法。第9章介紹z-變換的方法。第10章介紹構建疊代算法的依賴圖。第11章介紹基於計算幾何和線性代數概念的疊代算法分析技術。第12章探討的是不同的一維（1D）有限脈衝回響（FIR）數碼濾波器的並行處理架構。第13章探討的是不同的二維（2D）和三維（3D）無限脈衝回響（IIR）數碼濾波器的並行處理架構。第14章探討的是不同的多採樣率抽樣器和中斷器的並行處理架構。第15章探討的是模式識別算法所需的並行處理架構。第16章探討的是運用於視頻壓縮的運動估計並行處理架構。第17章探討的是不同的有限域的2?m階伽羅瓦域乘法的並行處理架構。第18章探討的是不同的有限域的2?m階伽羅瓦域除法的並行處理架構。第19章探討的是不同的快速傅立葉變換算法的並行處理架構。第20章探討了線性方程的求解系統。第21章討論了使用有限差分法（FDM）來求解偏微分方程的不同的並行處理架構。

本書不是一本特別初級的入門教材，但是有一定計算機專業基礎的讀者閱讀起來是不會有很大障礙的。另外對於需要直接了解某些具體案例的並行處理方法的讀者，也可以從本書找到答案或者啟發。推薦計算機、電子電氣工程等相關專業的高年級本科生、研究生以及從事相關研究的科研人員閱讀本書。