并行计算导论PDF|Epub|txt|kindle电子书版本网盘下载

并行计算导论PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

1.1推动并行化1

1.1.1计算能力因素——从晶体管到浮点运算速度1

第1章 并行计算介绍1

1.1.2内存及磁盘速度的因素2

1.1.3数据通信因素2

1.2并行计算适用范围3

1.2.1在工程及设计中的应用3

1.2.2科学计算中的应用3

1.2.3商业应用4

1.2.4计算机系统中的应用4

1.3本书的组织及内容4

1.4书目评注6

习题6

2.1隐式并行：微处理器体系结构的发展趋势9

2.1.1流水线与超标量执行9

第2章 并行编程平台9

2.1.2超长指令字处理器12

2.2内存系统性能的局限12

2.2.1使用高速缓存改善有效内存延迟13

2.2.2内存带宽的影响14

2.2.3躲避内存延迟的其他方法16

2.2.4多线程与预取间的权衡17

2.3.1并行平台的控制结构18

2.3并行计算平台剖析18

2.3.2并行平台的通信模型20

2.4并行平台的物理组织22

2.4.1理想并行计算机的体系结构22

2.4.2并行计算机互连网络23

2.4.3网络拓扑结构24

2.4.4静态互连网络评价31

2.4.5动态互连网络评价33

2.4.6多处理器系统中的高速缓存一致性34

2.5.1并行计算机的消息传递成本39

2.5并行计算机的通信成本39

2.5.2共享地址空间计算机的通信成本44

2.6互连网络的路由选择机制46

2.7进程-处理器映射的影响和映射技术47

2.7.1图的映射技术48

2.7.2成本-性能平衡53

2.8书目评注54

习题55

第3章 并行算法设计原则63

3.1预备知识63

3.1.1分解、任务与依赖图63

3.1.2粒度、并发性与任务交互65

3.1.3进程和映射69

3.1.4进程与处理器69

3.2分解技术70

3.2.1递归分解70

3.2.2数据分解72

3.2.3探测性分解77

3.2.4推测性分解79

3.2.5混合分解80

3.3任务和交互的特点81

3.3.1任务特性81

3.3.2任务间交互的特征82

3.4负载平衡的映射技术84

3.4.1静态映射方案85

3.4.2动态映射方案95

3.5包含交互开销的方法96

3.5.1最大化数据本地性97

3.5.2最小化争用与热点98

3.5.3使计算与交互重叠98

3.5.4复制数据或计算99

3.5.5使用最优聚合交互操作100

3.5.6一些交互与另一些交互的重叠100

3.6.2任务图模型101

3.6并行算法模型101

3.6.1数据并行模型101

3.6.3工作池模型102

3.6.4主-从模型102

3.6.5流水线模型或生产者-消费者模型103

3.6.6混合模型103

3.7书目评注103

习题103

第4章 基本通信操作107

4.1一对多广播以及多对一归约108

4.1.1环或线性阵列108

4.1.2格网110

4.1.3超立方体111

4.1.4平衡二叉树111

4.1.5算法细节112

4.2多对多广播和归约114

4.1.6成本分析114

4.2.1线性阵列和环115

4.2.2格网117

4.2.3超立方体117

4.2.4成本分析120

4.3全归约与前缀和操作121

4.4散发和收集123

4.5多对多私自通信125

4.5.1环126

4.5.2格网128

4.5.3超立方体128

4.6循环移位131

4.6.1格网131

4.6.2超立方体133

4.7提高某些通信操作的速度135

4.7.1消息分裂和路由选择135

4.7.2全端口通信136

4.8小结137

4.9书目评注138

习题139

第5章 并行程序的解析建模143

5.1并行程序中的开销来源143

5.2并行系统的性能度量144

5.2.1执行时间144

5.2.2总并行开销144

5.2.3加速比144

5.2.4效率147

5.2.5成本149

5.3粒度对性能的影响149

5.4并行系统的可扩展性152

5.4.1并行程序的扩展特性153

5.4.2可扩展性的等效率度量155

5.4.3成本最优性和等效率函数158

5.5最小执行时间和最小成本最优执行时间159

5.4.5并发度和等效率函数159

5.4.4等效率函数的下界159

5.6并行程序渐近分析162

5.7其他可扩展性的度量162

5.8书目评注165

习题166

第6章 使用消息传递模式编程171

6.1消息传递编程的原理171

6.2操作构件：发送和接收操作172

6.2.1阻塞式消息传递操作172

6.2.2无阻塞式消息传递操作175

6.3MPI：消息传递接口176

6.3.1启动和终止MPI库177

6.3.2通信器177

6.3.3获取信息178

6.3.4发送和接收消息178

6.3.5实例：奇偶排序182

6.4.1创建和使用笛卡儿拓扑结构184

6.4拓扑结构与嵌入184

6.4.2实例：Cannon的矩阵与矩阵相乘185

6.5计算与通信重叠187

6.6聚合的通信和计算操作191

6.6.1障碍191

6.6.2广播191

6.6.3归约191

6.6.4前缀193

6.6.5收集193

6.6.6散发194

6.6.7多对多195

6.6.8实例：一维矩阵与向量相乘195

6.6.9实例：单源最短路径197

6.6.10实例：样本排序199

6.7进程组和通信器200

6.8书目评注203

习题204

7.1线程基础205

第7章 共享地址空间平台的编程205

7.2为什么要用线程206

7.3POSIX线程API207

7.4线程基础：创建和终止207

7.5Pthreads中的同步原语210

7.5.1共享变量的互斥210

7.5.2用于同步的条件变量216

7.6.1线程的属性对象219

7.6控制线程及同步的属性219

7.6.2互斥锁的属性对象220

7.7线程注销221

7.8复合同步结构221

7.8.1读-写锁222

7.8.2障碍225

7.9设计异步程序的技巧228

7.10.1OpenMP编程模型229

7.10OpenMP：基于命令的并行编程标准229

7.10.2在OpenMP中指定并发任务232

7.10.3OpenMP中的同步结构237

7.10.4OpenMP中的数据处理240

7.10.5OpenMP库函数241

7.10.6OpenMP中的环境变量242

7.10.7显式线程与基于OpenMP编程的比较243

7.11书目评注243

习题244

第8章 稠密矩阵算法247

8.1矩阵向量乘法247

8.1.1一维行划分247

8.1.2二维划分250

8.2矩阵与矩阵的乘法253

8.2.1简单的并行算法254

8.2.2Cannon算法254

8.2.3DNS算法256

8.3线性方程组求解258

8.3.1简单高斯消元算法259

8.3.2带部分主元选择的高斯消元算法269

8.3.3求解三角系统：回代法271

8.3.4求解线性方程组时的数值因素272

8.4书目评注272

习题273

第9章 排序279

9.1并行计算机中的排序问题279

9.1.1输入输出序列的存放位置279

9.1.2如何进行比较280

9.2排序网络281

9.2.1双调排序282

9.2.2将双调排序映射到超立方体和格网285

9.3冒泡排序及其变体290

9.3.1奇偶转换290

9.3.2希尔排序293

9.4快速排序294

9.4.1并行快速排序295

9.4.2用于CRCWPRAM的并行形式296

9.4.3用于实际体系结构的并行形式298

9.4.4主元选择302

9.5桶和样本排序303

9.6其他排序算法305

9.6.1枚举排序305

9.6.2基数排序306

9.7书目评注307

习题308

第10章 图算法315

10.1定义和表示315

10.2最小生成树：Prim算法317

10.3单源最短路径：Dijkstra算法321

10.4全部顶点对间的最短路径321

10.4.1Dijkstra算法322

10.4.2Floyd算法323

10.4.3性能比较327

10.5传递闭包327

10.6连通分量328

10.7稀疏图算法331

10.7.1查找最大独立集332

10.7.2单源最短路径334

10.8书目评注340

习题341

第11章 离散优化问题的搜索算法345

11.1定义与实例345

11.2顺序搜索算法349

11.2.1深度优先搜索算法349

11.2.2最佳优先搜索算法351

11.3搜索开销因子353

11.4并行深度优先搜索353

11.4.1并行DFS的重要参数355

11.4.2并行DFS分析的一般框架357

11.4.3负载平衡方案分析359

11.4.4终止检测360

11.4.5试验结果362

11.4.6深度优先分支定界搜索的并行形式364

11.4.7IDA＊的并行形式365

11.5并行最佳优先搜索365

11.6并行搜索算法的加速比异常368

11.7书目评注371

习题374

第12章 动态规划379

12.1动态规划概述379

12.2串行一元DP形式381

12.2.1最短路径问题381

12.2.20/1背包问题382

12.3非串行一元DP形式384

12.5非串行多元DP形式387

12.4串行多元DP形式387

12.6综述与讨论390

12.7书目评注391

习题391

第13章 快速傅里叶变换395

13.1串行算法395

13.2二进制交换算法398

13.2.1全带宽网络399

13.2.2有限带宽网络404

13.2.3并行快速傅里叶变换中的额外计算405

13.3转置算法407

13.3.1二维转置算法407

13.3.2转置算法的推广410

13.4书目评注413

习题414

附录A 函数的复杂度与阶次分析417

索引419