并行計(jì)算導(dǎo)論（原書第2版）

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