并行計算導論（原書第2版）

 第1章  并行計算介紹
 1. 1  推動并行化
 1. 1. 1  計算能力因素--從晶體管到
 浮點運算速度
 1. 1. 2  內(nèi)存及磁盤速度的因素
 1. 1. 3  數(shù)據(jù)通信因素
 1. 2  并行計算適用范圍
 1. 2. 1  在工程及設(shè)計中的應用
 1. 2. 2  科學計算中的應用
 1. 2. 3  商業(yè)應用
 1. 2. 4  計算機系統(tǒng)中的應用
 1. 3  本書的組織及內(nèi)容
 1. 4  書目評注
 習題
 第2章  并行編程平臺
 2. 1  隱式并行：微處理器體系結(jié)構(gòu)的
 發(fā)展趨勢*
 2. 1. 1  流水線與超標量執(zhí)行
 2. 1. 2  超長指令字處理器
 2. 2  內(nèi)存系統(tǒng)性能的局限*
 2. 2. 1  使用高速緩存改善有效內(nèi)存延遲
 2. 2. 2  內(nèi)存帶寬的影響
 2. 2. 3  躲避內(nèi)存延遲的其他方法
 2. 2. 4  多線程與預取間的權(quán)衡
 2. 3  并行計算平臺剖析
 2. 3. 1  并行平臺的控制結(jié)構(gòu)
 2. 3. 2  并行平臺的通信模型
 2. 4  并行平臺的物理組織
 2. 4. 1  理想并行計算機的體系結(jié)構(gòu)
 2. 4. 2  并行計算機互連網(wǎng)絡(luò)
 2. 4. 3  網(wǎng)絡(luò)拓撲結(jié)構(gòu)
 2. 4. 4  靜態(tài)互連網(wǎng)絡(luò)評價
 2. 4. 5  動態(tài)互連網(wǎng)絡(luò)評價
 2, 4. 6  多處理器系統(tǒng)中的高速
 緩存一致性
 2. 5  并行計算機的通信成本
 2. 5. 1  并行計算機的消息傳遞成本
 2. 5. 2  共享地址空間計算機的通信成本
 2. 6  互連網(wǎng)絡(luò)的路由選擇機制
 2. 7  進程-處理器映射的影響和映射技術(shù)
 2. 7. 1  圖的映射技術(shù)
 2. 7. 2  成本-性能平衡
 2. 8  書目評注
 習題
 第3章  并行算法設(shè)計原則
 3. 1  預備知識
 3. 1. 1  分解. 任務與依賴圖
 3. 1. 2  粒度. 并發(fā)性與任務交互
 3. 1. 3  進程和映射
 3. 1, 4  進程與處理器
 3. 2  分解技術(shù)
 3. 2. 1  遞歸分解
 3. 2. 2  數(shù)據(jù)分解
 3. 2. 3  探測性分解
 3. 2. 4  推測性分解
 3. 2. 5  混合分解
 3. 3  任務和交互的特點
 3. 3. 1  任務特性
 3. 3. 2  任務間交互的特征
 3. 4  負載平衡的映射技術(shù)
 3. 4. 1  靜態(tài)映射方案
 3. 4. 2  動態(tài)映射方案
 3. 5  包含交互開銷的方法
 3. 5. 1  最大化數(shù)據(jù)本地性
 3. 5. 2 最小化爭用與熱點
 3. 5. 3  使計算與交互重疊
 3. 5. 4  復制數(shù)據(jù)或計算
 3. 5. 5  使用最優(yōu)聚合交互操作
 3. 5. 6  一些交互與另一些交互的重疊
 3. 6  并行算法模型
 3. 6. 1  數(shù)據(jù)并行模型
 3. 6. 2  任務圖模型
 3. 6. 3  工作池模型
 3. 6. 4  主-從模型
 3. 6. 5  流水線模型或生產(chǎn)者-消費者
 模型
 3. 6. 6  混合模型
 3. 7  書目評注
 習題
 第4章  基本通信操作
 4. 1  一對多廣播以及多對一歸約
 4. 1. 1  環(huán)或線性陣列
 4. 1. 2  格網(wǎng)
 4. 1. 3  超立方體
 4. 1. 4  平衡二叉樹
 4. 1. 5  算法細節(jié)
 4. 1. 6  成本分析
 4. 2  多對多廣播和歸約
 4. 2. 1  線性陣列和環(huán)
 4. 2. 2  格網(wǎng)
 4. 2. 3  超立方體
 4. 2. 4  成本分析
 4. 3  全歸約與前綴和操作
 4. 4  散發(fā)和收集
 4. 5  多對多私自通信
 4. 5. 1  環(huán)
 4. 5. 2  格網(wǎng)
 4. 5. 3  超立方體
 4. 6  循環(huán)移位
 4. 6. 1  格網(wǎng)
 4. 6. 2  超立方體
 4. 7  提高某些通信操作的速度
 4. 7. 1  消息分裂和路由選擇
 4. 7. 2  全端口通信
 4. 8  小結(jié)
 4. 9  書目評注
 習題
 第5章  并行程序的解析建模
 5. 1  并行程序中的開銷來源
 5. 2  并行系統(tǒng)的性能度量
 5. 2. 1  執(zhí)行時間
 5. 2. 2  總并行開銷
 5. 2. 3  加速比
 5. 2. 4  效率
 5. 2. 5  成本
 5. 3  粒度對性能的影響
 5. 4  并行系統(tǒng)的可擴展性
 5. 4. 1  并行程序的擴展特性
 5. 4. 2  可擴展性的等效率度量
 5. 4. 3  成本最優(yōu)性和等效率函數(shù)
 5. 4. 4  等效率函數(shù)的下界
 5. 4. 5  并發(fā)度和等效率函數(shù)
 5. 5  最小執(zhí)行時間和最小成本
 最優(yōu)執(zhí)行時間
 5. 6  并行程序漸近分析
 5. 7  其他可擴展性的度量
 5. 8  書目評注
 習題
 第6章  使用消息傳遞模式編程
 6. 1  消息傳遞編程的原理
 6. 2  操作構(gòu)件：發(fā)送和接收操作
 6. 2. 1  阻塞式消息傳遞操作
 6. 2. 2  無阻塞式消息傳遞操作
 6. 3  MPI：消息傳遞接口
 6. 3. 1  啟動和終止MPI庫
 6. 3. 2  通信器
 6. 3. 3  獲取信息
 6. 3. 4  發(fā)送和接收消息
 6. 3. 5  實例：奇偶排序
 6. 4  拓撲結(jié)構(gòu)與嵌入
 6. 4. 1  創(chuàng)建和使用笛卡兒拓撲結(jié)構(gòu)
 6. 4. 2  實例：Cannon的矩陣與矩陣相乘
 6. 5  計算與通信重疊
 6. 6  聚合的通信和計算操作
 6. 6. 1  障礙
 6. 6. 2  廣播
 6. 6. 3  歸約
 6. 6. 4  前綴
 6. 6. 5  收集
 6. 6. 6  散發(fā)
 6. 6. 7  多對多
 6. 6. 8  實例：一維矩陣與向量相乘
 6. 6. 9  實例：單源最短路徑
 6. 6. 10  實例：樣本排序
 6. 7  進程組和通信器
 6. 8  書目評注
 習題
 第7章  共享地址空間平臺的編程
 7. 1  線程基礎(chǔ)
 7. 2  為什么要用線程
 7. 3  POSIX線程API
 7. 4  線程基礎(chǔ)：創(chuàng)建和終止
 7. 5  Pthreads中的同步原語
 7. 5. 1  共享變量的互斥
 7. 5. 2  用于同步的條件變量
 7. 6  控制線程及同步的屬性
 7. 6. 1  線程的屬性對象
 7. 6. 2  互斥鎖的屬性對象
 7. 7  線程注銷
 7. 8  復合同步結(jié)構(gòu)
 7. 8. 1  讀-寫鎖
 7. 8. 2  障礙
 7. 9  設(shè)計異步程序的技巧
 7. 10  OpenMP：基于命令的并行
 編程標準
 7. 10. 1  OpenMP編程模型
 7. 10. 2  在OpenMP中指定并發(fā)任務
 7. 10. 3  OpenMP中的同步結(jié)構(gòu)
 7. 10. 4  OpenMP中的數(shù)據(jù)處理
 7. 10. 5  OpenMP庫函數(shù)
 7. 10. 6  OpenMP中的環(huán)境變量
 7. 10. 7  顯式線程與基于OpenMP編程
 的比較
 7. 11  書目評注
 習題
 第8章  稠密矩陣算法
 8. 1  矩陣向量乘法
 8. 1. 1  一維行劃分
 8. 1. 2  二維劃分
 8. 2  矩陣與矩陣的乘法
 8. 2. 1  簡單的并行算法
 8. 2. 2  Cannon算法
 8. 2. 3  DNS算法
 8. 3  線性方程組求解
 8. 3. 1  簡單高斯消元算法
 8. 3. 2  帶部分主元選擇的高斯消元算法
 8. 3. 3  求解三角系統(tǒng)：回代法
 8. 3. 4  求解線性方程組時的數(shù)值因素
 8. 4  書目評注
 習題
 第9章  排序
 9. 1  并行計算機中的排序問題
 9. 1. 1  輸入輸出序列的存放位置
 9. 1. 2  如何進行比較
 9. 2  排序網(wǎng)絡(luò)
 9. 2. 1  雙調(diào)排序
 9. 2. 2  將雙調(diào)排序映射到超立方體
 和格網(wǎng)
 9. 3  冒泡排序及其變體
 9. 3. 1  奇偶轉(zhuǎn)換
 9. 3. 2  希爾排序
 9. 4  快速排序
 9. 4. 1  并行快速排序
 9. 4. 2  用于CRCWPRAM的并行形式
 9. 4. 3  用于實際體系結(jié)構(gòu)的并行形式
 9. 4. 4  主元選擇
 9. 5  桶和樣本排序
 9. 6  其他排序算法
 9. 6. 1  枚舉排序
 9. 6. 2  基數(shù)排序
 9. 7  書目評注
 習題
 第10章  圖算法
 10. 1  定義和表示
 10. 2  最小生成樹：Prim算法
 10. 3  單源最短路徑：Dijkstra算法
 10. 4  全部頂點對間的最短路徑
 10. 4. 1  Dijkstra算法
 10. 4. 2  Floyd算法
 10. 4. 3  性能比較
 10. 5  傳遞閉包
 10. 6  連通分量
 10. 7  稀疏圖算法
 10. 7. 1  查找最大獨立集
 10. 7. 2  單源最短路徑
 10. 8  書目評注
 習題
 第11章  離散優(yōu)化問題的搜索算法
 11. 1  定義與實例
 11. 2  順序搜索算法
 11. 2. 1  深度優(yōu)先搜索算法
 11. 2. 2  最佳優(yōu)先搜索算法
 11. 3  搜索開銷因子
 11. 4  并行深度優(yōu)先搜索
 11. 4. 1  并行DFS的重要參數(shù)
 11. 4. 2  并行DFS分析的一般框架
 11. 4. 3  負載平衡方案分析
 11. 4. 4  終止檢測
 11. 4. 5  試驗結(jié)果
 11. 4. 6  深度優(yōu)先分支定界搜索的
 并行形式
 11. 4. 7  IDA*的并行形式
 11. 5  并行最佳優(yōu)先搜索
 11. 6  并行搜索算法的加速比異常
 11. 7  書目評注
 習題
 第12章  動態(tài)規(guī)劃
 12. 1  動態(tài)規(guī)劃概述
 12. 2  串行一元DP形式
 12. 2. 1  最短路徑問題
 12. 2. 2  0／1背包問題
 12. 3  非串行一元DP形式
 12. 4  串行多元DP形式
 12. 5  非串行多元DP形式
 12. 6  綜述與討論
 12. 7  書目評注
 習題
 第13章  快速傅里葉變換
 13. 1  串行算法
 13. 2  二進制交換算法
 13. 2. 1  全帶寬網(wǎng)絡(luò)
 13. 2. 2  有限帶寬網(wǎng)絡(luò)
 13. 2. 3  并行快速傅里葉變換中的
 額外計算
 13. 3  轉(zhuǎn)置算法
 13. 3. 1  二維轉(zhuǎn)置算法
 13. 3. 2  轉(zhuǎn)置算法的推廣
 13. 4  書目評注
 習題
 附錄A  函數(shù)的復雜度與階次分析
 索引