內容簡介
內容提要
本書是教育部“高等教育面向21世紀教學內容和課程體系改革計畫”的研究成果，是面向21世紀課程教材和教育部理科計算機套用“九五”規劃教材。 本書以並行計算為主題，主要討論並行計算的硬體基礎——當代並行計算機系統及其結構模型，並行計算的核心內容——並行算法設計與並行數值算法以及並行計算的軟體支持——並行程式的設計原理與方法。本書強調融並行機結構、並行算法和並行編程為一體，著重討論並行算法的設計方法和並行數值計算算法，力圖反映本學科的最新成就和發展趨勢。? 全書共十五章，分為四篇：第一篇包括並行計算機的系統結構模型，當代對稱多處理機、大規模並行處理機、機群系統和並行計算的性能評測；第二篇包括並行算法的一般設計策略、基本設計技術和一般設計過程；第三篇包括矩陣運算、稠密與稀疏線性方程組的求解和快速傅立葉變換；第四篇包括並行程式設計基礎、共享存儲與分布存儲系統 並行編程以及並行程式設計環境與工具。
從並行計算的角度，本書體系完整，內容豐富，取材新穎，可作為高等學校計算機及相關專 業的本科高年級學生和研究生的教學用書，也可供計算科學與工程Computational Science and Engineering)學科的研究生和科技人員閱讀參考。
目錄
第一篇 並行計算硬體基礎?
第一章 並行計算機系統及其結構模型 3 ?
1.1 並行計算 4 ?
1.1.1 並行計算與計算科學 4 ?
1.1.2 當代科學與工程問題的計算需求 4 ? 1.2 並行計算機系統互連 8 ?
1.2.1 系統互連 8 ?
1.2.2 靜態互連網路 9 ?
1.2.3 動態互連網路 13 ?
1.2.4 標準互連網路 17 ?
1.3 並行計算機系統結構 22 ?
1.3.1 並行計算機結構模型 22 ?
1.3.2 並行計算機訪存模型 26 ?
*1.3.3 並行計算機存儲組織 30 ?
1.4 小結和導讀 34 ?
習題 35 ??
第二章 當代並行計算機系統介紹 39 ?
2.1 共享存儲多處理機系統 40 ?
2.1.1 對稱多處理機smp結構特性 40 ?
*2.1.2 cc-numa origin 2000超級伺服器 41?
. 2.2 分布存儲多計算機系統 48 ?
2.2.1 大規模並行處理機mpp結構特性 49 ? *2.2.2 asci option red mpp系統 53 ?
2.3 機群系統 57 ?
2.3.1 大規模並行處理系統mpp機群sp2 58 ? 2.3.2 工作站機群cow 64 ?
*2.3.3 berkeley的now計畫 68 ?
2.4 小結和導讀 73 ?
習題 75 ??
第三章 並行計算性能評測 77 ?
3.1 並行計算機的一些基本性能指標 78 ?
3.1.1 cpu和存儲器的某些基本性能指標 78 3.1.2 通信開銷 80 ?
3.1.3 機器的成本、價格與性能/價格比 81 ?3.2 加速比性能定律 83 ?
3.2.1 amdahl定律 83 ?
3.2.2 gustafson定律 84 ?
3.2.3 sun和ni定律 86 ?
3.2.4 有關加速的討論 87 ?
3.3 可擴放性評測標準 88 ?
3.3.1 並行計算的可擴放性 88 ?
3.3.2 等效率度量標準 89 ?
3.3.3 等速度度量標準 90 ?
3.3.4 平均延遲度量標準 92 ?
3.3.5 有關可擴放性標準的討論 94 ?
*3.4 基準測試程式 95 ?
3.4.1 基本的測試程式 95 ?
3.4.2 數學庫測試程式 96 ?
3.4.3 並行測試程式 97 ?
3.5 小結和導讀 98 ?
習題 99 ?
第二篇 並行算法的設計
第四章 並行算法的設計基礎 103 ?
*4.1 並行算法的基礎知識 104 ?
4.1.1 並行算法的定義和分類 104 ?
4.1.2 並行算法的表達 105 ?
4.1.3 並行算法的複雜性度量 105 ?
4.1.4 並行算法中的同步與通信 107 ?
4.2 並行計算模型 108 ?
4.2.1 pram模型 109 ?
4.2.2 異步pram模型 110 ?
4.2.3 bsp模型 111 ?
4.2.4 logp模型 113 ?
4.2.5 對bsp和logp的評註 115 ?
4.3 小結和導讀 117 ?
習題 118 ??
第五章 並行算法的一般設計策略 123
5.1 串列算法的直接並行化 124 ?
5.1.1 設計策略描述 124 ?
5.1.2 快排序算法的並行化 124 ?
5.2 從問題描述開始設計並行算法 127 ?
5.2.1 串匹配算法 127 ?
*5.2.2 kmp串列串匹配算法 128 ?
5.2.3 並行串匹配算法的設計思路 130 ?
5.3 借用已有算法求解新問題 131 ?
5.3.1 設計策略描述 131 ?
5.3.2 利用矩陣乘法求所有點對間最短路徑 132 5.4 小結和導讀 135 ?
習題 136 ??
第六章 並行算法的基本設計技術 139 ?
6.1 劃分設計技術 140 ?
6.1.1 均勻劃分技術 140 ?
6.1.2 方根劃分技術 141 ?
6.1.3 對數劃分技術 142 ?
6.1.4 功能劃分技術 143 ?
6.2 分治設計技術 144 ?
6.2.1 雙調歸併網路 145 ?
6.2.2 凸殼問題 146 ?
6.3 平衡樹設計技術 149 ?
6.3.1 求取最大值 149 ?
6.3.2 計算前綴和 149 ?
6.4 倍增設計技術 151 ?
6.4.1 表序問題的計算 151 ?
6.4.2 求森林的根 152 ?
6.5 流水線設計技術 153 ?
6.5.1 一維心動陣列上的dft計算 154 ?
6.5.2 一維心動陣列上的卷積計算 155 ?
6.6 小結和導讀 156 ?
習題 158 ??
第七章 並行算法的一般設計過程 160 ?
7.1 pcam設計方法學 161 ?
7.2 劃分 162 ?
7.2.1 域分解 162 ?
7.2.2 功能分解 163 ?
7.2.3 劃分判據 163 ?
7.3 通信 164 ?
7.3.1 局部通信 164 ?
7.3.2 全局通信 166 ?
7.3.3 非結構化、動態和異步通信 167 ?
7.3.4 通信判據 167 ?
7.4 組合 167 ?
7.4.1 增加粒度 168 ?
7.4.2 保持靈活性和減少軟體工程成本 170 ? 7.4.3 組合判據 171 ?
7.5 映射 171 ?
7.5.1 負載平衡算法 172 ?
7.5.2 任務調度算法 173 ?
7.5.3 映射判據 174 ?
7.6 小結和導讀 174 ?
習題 175
第三篇 並行數值算法
第八章 基本通信操作 183 ?
8.1 選路方法與開關技術 184 ?
8.1.1 選路方法 184 ?
8.1.2 開關技術 186 ?
8.2 單一信包一到一傳輸 188 ?
8.3 一到多播送 188 ?
8.3.1 使用sf進行一到多播送 188 ?
8.3.2 使用ct進行一到多播送 190 ?
8.4 多到多播送 191 ?
8.4.1 使用sf進行多到多播送 192 ?
8.4.2 使用ct進行多到多播送 193 ?
8.5 小結和導讀 195 ?
習題 197 ??
第九章 稠密矩陣運算 201 ?
9.1 矩陣的劃分 202 ?
9.1.1 帶狀劃分 202 ?
9.1.2 棋盤劃分 202 ?
9.2 矩陣轉置 204 ?
9.2.1 棋盤劃分的矩陣轉置 204 ?
9.2.2 帶狀劃分的矩陣轉置 207 ?
9.3 矩陣-向量乘法 208 ?
9.3.1 帶狀劃分的矩陣-向量乘法 208 ?
9.3.2 棋盤劃分的矩陣-向量?乘法 210 ?
9.4 矩陣乘法 212 ?
9.4.1 簡單並行分塊乘法 212 ?
9.4.2 cannon乘法 214 ?
9.4.3 fox乘法 217 ?
9.4.4 dns乘法 217 ?
9.5 小結和導讀 222 ?
習題 223 ??
第十章 線性方程組的求解 226 ?
10.1 三角形方程組的求解 227 ?
10.1.1 基本術語 227 ?
10.1.2 上三角方程組的求解 228 ?
10.2 三對角方程組的求解 230 ?
10.2.1 三對角方程組直接?求解法 230 ?
10.2.2 三對角方程組奇偶歸約?求解法 231 10.3 稠密線性方程組的求解 233 ?
10.3.1 有回代的高斯消去法 233 ?
10.3.2 無回代的高斯-約旦法 237 ?
10.3.3 疊代求解的高斯-賽德爾法 239 ?
10.4 稀疏線性方程組的求解 241 ?
10.4.1 稀疏矩陣的存儲方式 241 ?
10.4.2 雅可比疊代法 243 ?
10.4.3 高斯-賽德爾疊代法 247 ?
10.4.4 超鬆弛疊代法 249 ?
10.4.5 多重格線法 249 ?
10.4.6 共軛梯度法 251 ?
10.5 小結和導讀 256 ?
習題 257 ??
第十一章 快速傅立葉變換 260 ?
11.1 離散傅氏變換 261 ?
*11.1.1 預備知識 261 ?
11.1.2 離散傅立葉變換 262 ?
11.1.3 離散傅立葉逆變換 263 ?
11.1.4 離散傅氏變換的蝶式計算 264 ?
*11.2 快速傅氏變換串列算法 266 ?
11.2.1 串列fft疊代算法 266 ?
11.2.2 串列fft遞歸算法 267 ?
11.3 並行fft算法 270 ?
11.3.1 simd-mc2上fft算法 270 ?
11.3.2 simd-bf上fft算法 272 ?
11.3.3 simd-cc上fft算法 274 ?
11.3.4 mimd-dm上fft算法 275 ?
11.4 小結和導讀 279 ?
習題 280 ?
第四篇 並行程式設計
第十二章 並行程式設計基礎 285 ?
12.1 並行程式設計概述 286 ?
12.1.1 串列程式設計與並行程式設計 286 ? 12.1.2 並行程式設計環境與工具 287 ?
12.1.3 並行程式設計方法 288 ?
12.1.4 並行編程風範 290 ?
*12.2 進程 291 ?
12.2.1 進程的基本概念 291 ?
12.2.2 進程的並行執行 294 ?
12.2.3 進程的相互作用 295 ?
12.3 執行緒 297 ?
12.3.1 執行緒的基本概念 297 ?
12.3.2 執行緒的管理 298 ?
12.3.3 執行緒的同步 299 ?
*12.4 同步 299 ?
12.4.1 原子與互斥 300 ?
12.4.2 高級同步結構 300 ?
12.4.3 低級同步原語 302 ?
12.5 通信 303 ?
12.5.1 影響通信系統性能的因素 304 ?
12.5.2 低級通信支持 305 ?
12.5.3 tcp/ip通信協定組簡介 307 ?
12.6 並行程式設計模型 310 ?
12.6.1 計算π樣本程式 310 ?
12.6.2 隱式並行模型 311 ?
12.6.3 數據並行模型 313 ?
12.6.4 訊息傳遞模型 314 ?
12.6.5 共享變數模型 315 ?
12.6.6 並行程式設計模型比較 317 ?
12.7 小結和導讀 318 ?
習題 319 ??
第十三章 共享存儲系統並行編程 322 ?
13.1 基於共享變數的共享存儲?並行編程 323 ?13.1.1 共享存儲並行編程的?基本問題 323 ?13.1.2 共享存儲編程環境 324 ?
13.2 早期共享存儲並行編?程模型 324 ?
13.2.1 ansi x3h5共享存儲模型 324 ?
13.2.2 posix執行緒模型 327 ?
13.3 openmp編程簡介 328 ?
13.3.1 openmp概述 329 ?
13.3.2 openmp編程風格 329 ?
13.3.3 openmp編程要素 330 ?
13.3.4 openmp計算實例 339 ?
13.3.5 運行庫例程與環境變數 341 ?
13.4 小結和導讀 341 ?
習題 342 ?
附錄 openmp運行庫例程 345 ??
第十四章 分布存儲系統並行編程 348
14.1 基於訊息傳遞的並行編程 349 ?
14.1.1 spmd並行程式 349 ?
14.1.2 mpmd並行程式 350 ?
14.2 mpi並行編程 351 ?
14.2.1 最基本的mpi 352 ?
14.2.2 群體通信 355 ?
14.2.3 通信體 357 ?
14.2.4 導出數據類型 358 ?
14.2.5 點到點通信 359 ?
*14.3 pvm並行編程 364 ?
14.3.1 pvm概貌 365 ?
14.3.2 pvm訊息傳遞庫 365 ?
14.4 基於數據並行的並行編程 368 ?
14.4.1 數據並行模型的特點 368 ?
14.4.2 數據並行編程的基本問題 369 ?
14.5 hpf並行編程 370 ?
14.5.1 hpf的語言特點 370 ?
14.5.2 hpf的數據並行機制 371 ?
14.5.3 hpf使用中的若干問題 375 ?
14.6 小結和導讀 378 ?
習題 379
附錄一 mpi的函式的c語言說明 384
附錄二 mpi的函式的fortran語言說明 386
第十五章 並行程式設計環境與工具 389
*15.1 軟體工具與環境 390
15.1.1 編碼工具 390
15.1.2 軟體工程工具 391
15.1.3 集成工具 391
15.1.4 將來的工具與環境 392
15.2 並行編譯器 393
15.2.1 編譯及其並行化 394
15.2.2 相關分析 396
15.2.3 代碼最佳化 398
15.2.4 代碼生成 403
15.3 並行程式調試 403
15.3.1 並行程式調試的方法與?步驟 404
15.3.2 並行程式的調試技術 406
15.3.3 並行程式的性能調試 407
15.4 並行程式性能分析 408
15.4.1 並行程式的性能預測 408
15.4.2 並行程式的性能監控 410
15.4.3 並行程式的性能可視化 411
15.5 圖形化並行程式集成開發環境 413
15.5.1 並行程式的可視化設計環境與工具 413
15.5.2 圖形套用開發環境grade的組成 414
15.5.3 grade中開發並行程式過程 414
15.6 小結和導讀 416
習題 417
算法索引 420
表格索引 422
示範程式索引 423
參考文獻 424
並行與分布計算web網址 434
專業術語中英對照及索引 440
