并行處理基本原理

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