并行處理基本原理

第1章 并行機和并行計算
1.1 并行體系結(jié)構(gòu)的發(fā)展歷程
1.1.1 串行計算機中的并行性
1.1.2 向量或SIMD計算機
1.1.3 多處理機或MIMD計算機
1.2 互連網(wǎng)絡
1.3 體系結(jié)構(gòu)并行性的應用
1.4 SIMD和MIMD程序設計
1.5 算法并行性
1.6 小結(jié)
1.7 參考文獻注解
1.8 練習題
第2章 并行計算基礎
2.1 描述算法并行性的參數(shù)
2.2 前綴問題
2.3 并行前綴算法
2.3.1 高/低并行前綴算法
2.3.2 奇/偶并行前綴算法
2.3.3 Ladner和Fischer并行前綴算法
2.4 大規(guī)模問題求解算法的特性
2.5 編程實現(xiàn)并行前綴算法
2.6 并行算法的加速比和效率
2.7 性能分析
2.7.1 影響性能的因素
2.7.2 一個簡單的性能模型--Amdahl定律
2.7.3 平均執(zhí)行速度
2.8 小結(jié)
2.9 參考文獻注解
2.10 練習題
第3章 向量算法與體系結(jié)構(gòu)
3.1 向量和矩陣算法
3.2 向量體系結(jié)構(gòu)--單指令多數(shù)據(jù)流體系結(jié)構(gòu)
3.3 SIMD指令集
3.3.1 SIMD計算機的寄存器和存儲器
3.3.2 向量、控制器與協(xié)同指令
3.3.3 數(shù)據(jù)相關(guān)條件操作
3.3.4 向量長度和分段處理
3.3.5 在PE之間路由數(shù)據(jù)
3.4 互素存儲器系統(tǒng)
3.5 用PE索引來解決存儲布局問題
3.6 SIMD語言結(jié)構(gòu)--Fortran 90
3.6.1 數(shù)組和數(shù)組分片
3.6.2 數(shù)組賦值和數(shù)組表達式
3.6.3 Fortran 90數(shù)組內(nèi)置函數(shù)
3.6.4 Fortran 90中SIMD操作舉例
3.7 流水SIMD向量計算機
3.7.1 流水SIMD處理機的結(jié)構(gòu)
3.7.2 流水SIMD計算機的存儲器接口
3.7.3 流水SIMD計算機的性能
3.8 向量體系結(jié)構(gòu)小結(jié)
3.9 參考文獻注解
3.10 練習題
第4章 MIMD計算機或多處理機
4.1 共享存儲器和消息傳遞體系結(jié)構(gòu)
4.1.1 混合類型多處理機體系結(jié)構(gòu)
4.1.2 共享存儲器和消息傳遞的特點
4.1.3 消息傳遞體系結(jié)構(gòu)中的網(wǎng)絡拓撲結(jié)構(gòu)
4.1.4 直接和間接網(wǎng)絡
4.1.5 實際系統(tǒng)的分類
4.2 共享存儲器多處理機程序設計總覽
4.2.1 數(shù)據(jù)共享和進程管理
4.2.2 同步
4.2.3 原子性與同步
4.2.4 作業(yè)分配
4.2.5 多個進程執(zhí)行一個程序
4.3 共享存儲器程序設計的選擇與領域
4.3.1 進程管理--啟動、停止和層次
4.3.2 并行進程對數(shù)據(jù)的訪問
4.3.3 作業(yè)分配
4.3.4 多處理機的同步
4.4 共享存儲器多處理機程序設計語言
4.4.1 OpenMP語言擴展
4.4.2 OpenMP Fortran語言的應用程序接口(API)
4.4.3 OpenMP Fortran實例與討論
4.5 流水MIMD--多線程
4.6 小結(jié)
4.7 參考文獻注解
4.8 練習題
第5章 分布式存儲器多處理機
5.1 處理機/存儲器對中的分布式數(shù)據(jù)和操作
5.2 使用消息傳遞機制編程
5.2.1 通信串行進程語言
5.2.2 分布式存儲器編程實例：矩陣乘法
5.3 通信的特征
5.3.1 點對點通信
5.3.2 在分布式存儲器程序中的變量分類
5.3.3 高級通信操作
5.3.4 使用高級通信進行分布高斯消元法
5.3.5 進程拓撲與處理機拓撲
5.4 消息傳遞接口(MPI)
5.4.1 MPI中的基本概念
5.4.2 MPI程序?qū)嵗?-矩陣乘法
5.5 管理通信的硬件--分布式高速緩存
5.5.1 高速緩存一致性
5.5.2 共享存儲器的一致性
5.6 小結(jié)--共享存儲器多處理機與分布式存儲器多處理機
5.7 參考文獻注解
5.8 練習題
第6章 互連網(wǎng)絡
6.1 網(wǎng)絡特性
6.2 置換
6.3 靜態(tài)網(wǎng)絡
6.3.1 網(wǎng)格
6.3.2 環(huán)
6.3.3 樹
6.3.4 立方體網(wǎng)絡
6.3.5 性能
6.4 動態(tài)網(wǎng)絡
6.4.1 總線(bus)
6.4.2 交叉開關(guān)
6.4.3 多級互連網(wǎng)絡
6.4.4 組合網(wǎng)絡--互斥自由同步
6.4.5 性能
6.5 小結(jié)
6.6 參考文獻注解
6.7 練習題
第7章 數(shù)據(jù)相關(guān)性與并行性
7.1 發(fā)現(xiàn)(串行)代碼中的并行操作
7.2 具有復雜名稱的變量
7.2.1 嵌套循環(huán)
7.2.2 關(guān)于數(shù)組訪問不確定性問題的變化
7.3 樣本編譯技術(shù)
7.3.1 循環(huán)變換
7.3.2 循環(huán)重構(gòu)
7.3.3 循環(huán)替換變換
7.3.4 消除反相關(guān)和輸出相關(guān)的變換
7.4 數(shù)據(jù)流原理
7.4.1 數(shù)據(jù)流基本概念
7.4.2 數(shù)據(jù)流計算的圖形化表示
7.4.3 數(shù)據(jù)流的條件
7.4.4 數(shù)據(jù)流迭代
7.4.5 數(shù)據(jù)流函數(shù)的應用與遞歸
7.4.6 數(shù)據(jù)流中的結(jié)構(gòu)值--數(shù)組
7.5 數(shù)據(jù)流體系結(jié)構(gòu)
7.5.1 MIT靜態(tài)數(shù)據(jù)流體系結(jié)構(gòu)
7.5.2 動態(tài)數(shù)據(jù)流計算機
7.5.3 數(shù)據(jù)流機器的一些問題
7.6 脈動陣列
7.7 小結(jié)
7.8 參考文獻注解
7.9 練習題
第8章 同步實現(xiàn)與數(shù)據(jù)共享
8.1 同步傳輸信息的特點
8.2 不同類別的協(xié)同計算同步
8.2.1 一個生產(chǎn)者和一個或多個消費者
8.2.2 全局歸約
8.2.3 全局前綴
8.2.4 劃分結(jié)構(gòu)的協(xié)同更新
8.2.5 管理共享作業(yè)集
8.2.6 協(xié)同的列表操作
8.2.7 使用Fetch&Add并行訪問隊列
8.2.8 直方圖--細粒度數(shù)據(jù)相關(guān)同步
8.3 等待機制
8.3.1 硬件等待
8.3.2 軟件等待
8.3.3 多級等待
8.4 用原子讀寫操作實現(xiàn)互斥
8.5 證明同步實現(xiàn)的正確性
8.5.1 使用鎖實現(xiàn)Produce/Consume
8.5.2 時間邏輯
8.5.3 正確性證明
8.6 另一種同步實現(xiàn)--障礙.
8.6.1 障礙同步的特點.
8.6.2 障礙實現(xiàn)的特點
8.7 小結(jié)
8.8 參考文獻注解
8.9 練習題
第9章 并行處理機性能
9.1 Amdahl定律回顧
9.1.1 工作粒度對Amdahl定律的影響
9.1.2 Amdahl定律參數(shù)的最小方差估計
9.2 參數(shù)化的執(zhí)行時間
9.2.1 流水線向量機的性能
9.2.2 流水線多處理機的性能
9.2.3 多流水線多處理機系統(tǒng)
9.3 障礙同步的性能
9.3.1 障礙性能的說明
9.3.2 障礙性能測量的手段
9.3.3 障礙同步性能測量舉例
9.4 并行循環(huán)靜態(tài)調(diào)度和動態(tài)調(diào)度的統(tǒng)計模型
9.4.1 動態(tài)調(diào)度模型
9.4.2 靜態(tài)調(diào)度模型
9.4.3 實驗結(jié)果的比較
9.5 小結(jié)
9.6 參考文獻注解
9.7 練習題
第10章 并行程序的時間特性
10.1 高速緩存行為的時間特性
10.1.1 高速緩存特性的時間局部性度量標準
10.1.2 冒泡排序程序局部性度量標準的應用舉例
10.2 分布式高速緩存多處理機中的讀共享
10.2.1 共享數(shù)據(jù)讀取的一個簡單例子
10.2.2 KSR-1體系結(jié)構(gòu)
10.2.3 讀多重性度量標準
10.2.4 實驗
10.2.5 編程控制的郵寄存儲和預取
1O.3 消息傳遞多處理機系統(tǒng)中的消息等待
10.4 小結(jié)
10.5 參考文獻注解
10.6 練習題
第11章 并行輸入輸出
11.1 并行I/O問題
11.1.1 數(shù)據(jù)相關(guān)性和輸入輸出
11.1.2 輸入輸出格式轉(zhuǎn)換
11.1.3 輸入輸出延遲和帶寬需求的數(shù)值例子
11.2 并行輸入輸出的硬件
11.2.1 主存方面的傳輸控制
11.2.2 輸入輸出通道的并發(fā)
11.2.3 并行外圍設備
11.3 并行訪問磁盤陣列--RAID
11.4 共享存儲器多處理機中的并行格式化I/O
11.4.1 使用c中的I/O例程fread()和sscan()實現(xiàn)并行輸入
11.4.2 使用C中的I/O例程sprintf()和fwrite()實現(xiàn)并行輸出
11.5 多處理機中的聚合I/O--MPI-IO
11.5.1 MPI-2中的I/O概念
11.5.2 MPI-IO示例
11.6 小結(jié)
11.7 參考文獻注解
11.8 練習題
附錄A MPI消息傳遞庫程序
A.1 點對點通信程序
A.2 聚合通信程序
A.3 MPI數(shù)據(jù)類型和構(gòu)造器
A.4 通信器、進程組和拓撲
A.5 MPI環(huán)境和錯誤處理
A.6 小結(jié)與MPI-2擴展
附錄B 同步機制
B.1 硬件級同步
B.2 語言級同步
B.3 等待機制
參考文獻