第1章 引言 1
1.1 概述 1
1.2 自動並行編程 1
1.3 算法 3
1.3.1 算法的有嚮圖 3
1.3.2 算法的鄰接矩陣A 4
1.3.3 基於子任務的依賴關係對算法進行分類 5
1.3.4 串行算法 6
1.3.5 並行算法 6
1.3.6 SPA 6
1.3.7 NSPA 7
1.3.8 RIA 8
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 CT 17
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_for 79
6.3.2 數據競爭和程序不確定性 80
6.3.3 將串行代碼並行化的Cilk++組件 82
6.3.4 使用Cilk++實現矩陣乘法 82
6.4 OpenMP 84
6.4.1 OpenMP編譯指導語句 85
6.4.2 編譯指導語句子句 86
6.4.3 OpenMP負載分配 87
6.4.4 循環指導語句： for 87
6.4.5 循環指導語句： sections 89
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: 投影方嚮d1= 133
10.8.2 設計方案2: 投影方嚮d2= 134
10.9 習題 135
第11章 計算幾何分析 136
11.1 概述 136
11.2 矩陣乘算法 136
11.3 3D依賴圖和計算域D 136
3D域邊界 137
11.4 D的麵和頂點 138
11.5 算法變量的依賴矩陣 138
11.6 依賴矩陣的零空間: 廣播子域B 139
A的零空間 139
11.7 設計空間的探索: 選擇廣播變量還是流水綫變量 141
11.7.1 饋送/提取廣播變量的點 141
11.7.2 變量流水綫 143
11.8 數據調度 143
調度函數對數據時序的影響 146
11.9 使用綫性投影算子進行投影操作 147
11.9.1 投影矩陣P 147
11.9.2 投影方嚮 148
11.9.3 投影方嚮d的選擇 148
11.9.4 當投影方法d給定時，找齣矩陣P 149
11.10 投影操作對數據的影響 150
11.10.1 輸齣數據 150
11.10.2 輸入數據M2 151
11.10.3 輸入數據M3 151
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 在s1= 的情況下，采樣器的有嚮無環圖 171
14.6 在s2=的情況下，插值器的有嚮無環圖 172
14.7 在s3=的情況下，插值器的有嚮無環圖 174
14.8 多相采樣器的實現 174
14.9 插值器的架構 175
14.10 插值器的依賴關係圖 176
14.11 插值器的調度 177
14.12 在s1=的情況下，插值器的有嚮無環圖 178
14.13 在s2= 的情況下，插值器的有嚮無環圖 179
14.14 在s3= 的情況下，插值器的有嚮無環圖 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= 時的設計空間 184
15.6.1 設計方案1.a: 設s= , da= 185
15.6.2 設計方案1.b: 設s= , db= 186
15.6.3 設計方案1.c: 設s= , dc= 186
15.7 設計方案2: 當s= 時的設計空間搜索 187
15.7.1 設計方案2.a: 設s= , da= 187
15.7.2 設計方案2.b: 設s= , db= 187
15.7.3 設計方案2.c: 設s= , dc= 188
15.8 設計方案3: 當s= 時的設計空間搜索 188
設計方案3.a: 設s= , da= 188
第16章 案例學習: 用於視頻壓縮的運動估計 189
16.1 概述 189
16.2 FBMA 189
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章 範例分析: 2m階伽羅瓦域乘法 198
17.1 概述 198
17.2 2m階伽羅瓦域乘法算法 198
17.3 將域乘法錶示為RIA 200
17.4 域乘法的依賴圖 200
17.5 數據調度 201
17.6 DAG結點投影 203
17.7 設計1: 使用d1= 204
17.8 設計2: 使用d2= 204
17.9 設計3: 使用d3= 205
17.10 有限域乘法器的應用 206
第18章 範例分析: 2m階伽羅瓦域的多項式除法 207
18.1 概述 207
18.2 多項式除法算法 207
18.3 LFSR依賴圖 208
18.4 數據調度 209
18.5 DAG結點投影 210
18.6 設計1: s1=時的設計空間 211
18.7 設計2: s2=時的設計空間 212
18.8 設計3: s3=時的設計空間 214
18.9 3種設計方案的比較 215
第19章 快速傅裏葉變換 217
19.1 概述 217
19.2 時分FFT 218
19.3 流水綫基2時分FFT處理器 221
19.4 頻分FFT 221
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係統的FDM 239
21.2.1 1-D FDM的調度函數 240
21.2.2 投影方嚮 242
參考文獻 243
· · · · · · (收起)