并行计算机体系结构 硬件/软件结合的设计与分析 原书第2版PDF电子书下载

第1章 引论 1

1.1 为什么要用并行体系结构 3

1.1.1 计算机应用发展的趋势 4

1.1.2 微电子技术趋势 9

1.1.3 体系结构趋势 10

1.1.4 超级计算机 15

1.1.5 小结 17

1.2 并行体系结构的融合 18

1.2.1 通信体系结构 18

1.2.2 共享地址空间 20

1.2.3 消息传递 27

1.2.4 融合 29

1.2.5 数据并行处理 32

1.2.6 其他并行体系结构 34

1.2.7 一个通用并行体系结构 36

1.3 基本的设计问题 37

1.3.1 通信抽象 38

1.3.2 编程模型的要求 38

1.3.3 通信和复制 41

1.3.4 性能 42

1.4 结论 45

1.3.5 小结 45

1.5 历史资料 47

习题 50

第2章 并行程序 54

2.1 并行应用的案例分析 55

2.1.1 洋流的模拟 55

2.1.2 星系演化的模拟 56

2.1.3 用光线跟踪法来实现复杂场景的可视化 57

2.1.4 针对关联性的数据挖掘 58

2.2 并行化过程 58

2.2.1 程序并行化过程中的几个步骤 59

2.2.3 并行化过程的目标 65

2.2.2 计算并行和数据并行 65

2.3 一个例子程序的并行化 66

2.3.1 方程求解器的内核 66

2.3.2 分解 68

2.3.3 分配 71

2.3.4 在数据并行模型下的协调 72

2.3.5 在共享地址空间模型下的协调 73

2.3.6 在消息传递模型下的协调 78

2.4 结论 84

习题 84

第3章 面向性能的程序设计 88

3.1划分阶段的性能问题 89

3.1.1 负载平衡和同步等待时间 90

3.1.2 减少固有的通信 95

3.1.3 减少额外的工作 98

3.1.4 小结 99

3.2 在多存储器系统中的数据访问和通信 100

3.2.1 看作扩展的存储层次结构的多处理器系统 100

3.2.2 在扩展的存储层次结构中的附加通信 101

3.2.3 用工作集的观点看附加的通信和数据的复制 102

3.3 性能的协调 103

3.3.1 减少附加通信 103

3.3.2 将通信结构化以降低代价 108

3.4 从处理器角度看到的性能因素 113

3.5 并行应用程序案例的深入分析 115

3.5.1 Ocean 116

3.5.2 Barnes-Hut 120

3.5.3 光线跟踪 125

3.5.4 数据挖掘 128

3.6 编程模型涉及的问题 131

3.6.1 命名 132

3.6.2 复制 132

3.6.3 通信的开销和粒度 133

3.6.5 同步 134

3.6.4 块数据传送 134

3.6.6 硬件代价和设计复杂性 135

3.6.7 性能模型 135

3.6.8 小结 136

3.7 结论 136

习题 137

第4章 工作负载驱动的性能评价 142

4.1 改变工作负载和机器的规模 144

4.1.1 多处理器性能的基本测量 144

4.1.2 为什么要考虑扩放性 145

4.1.4 扩放模型和加速比的测量 148

4.1.3 扩放的关键问题 148

4.1.5 扩放模型对方程求解器内核的影响 151

4.1.6 扩放工作负载参数 153

4.2 评价一台实际的机器 154

4.2.1 使用微基准测试程序分离性能 154

4.2.2 选择工作负载 156

4.2.3 评价一台固定规模的机器 158

4.2.4 改变机器的规模 163

4.2.5 选择性能指标 164

4.3 对一个体系结构概念或设计权衡的评估 166

4.3.1 多处理器的模拟 167

4.3.2 缩小模拟的问题和机器参数的规模 168

4.3.3 处理参数空间：评价举例 171

4.3.4 小结 174

4.4 说明工作负载的特征 175

4.4.1 工作负载案例分析 175

4.4.2 工作负载的特征化 182

4.5 结论 188

习题 189

第5章 共享存储的多处理器 193

5.1 高速缓存的一致性 196

5.1.1 高速缓存一致性问题 196

5.1.2 通过总线侦听的高速缓存一致性 199

5.2 存储同一性 204

5.2.1 顺序同一性 206

5.2.2 保证顺序同一性的充分条件 208

5.3 总线侦听协议的设计空间 210

5.3.1 一种三态（MSI）回写作废式协议 211

5.3.2 一种四态（MESI）回写作废式协议 215

5.3.3 一种四态（Dragon）回写更新式协议 217

5.4 关于协议设计中若干折中的评估 220

5.4.1 方法论 221

5.4.2 在MESI协议下的带宽需求 223

5.4.3 协议优化的影响 224

5.4.4 高速缓存中存储块大小的权衡 227

5.4.5 基于更新和基于作废协议的对比 238

5.5 同步 241

5.5.1 同步事件的组成部分 242

5.5.2 用户和系统的角色 243

5.5.3 互斥 244

5.5.4 点对点事件同步 254

5.5.5 全局（栅障）事件的同步 255

5.5.6 同步问题小结 259

5.6 对软件的影响 259

5.7 结论 264

习题 265

6.1 正确性需求 273

第6章 基于侦听的多处理器的设计 273

6.2 基础设计：采用原子总线的单级高速缓存 275

6.2.1 高速缓存控制器和标记的设计 276

6.2.2 侦听结果的报告 277

6.2.3 对回写的处理 278

6.2.4 基础系统组织 279

6.2.5 非原子性的状态转移 279

6.2.6 串行化 281

6.2.7 死锁 282

6.2.8 活锁和挨饿 283

6.2.9 原子操作的实现 283

6.3 多级高速缓存层次结构 284

6.3.1 包含性的维护 285

6.3.2 在高速缓存层次结构中传播一致性的事务 287

6.4 事务拆分型总线 289

6.4.1 事务拆分型总线设计的一个例子 290

6.4.2 总线设计和请求－响应的匹配 290

6.4.3 侦听结果和冲突的请求 292

6.4.4 流控制 293

6.4.5 一次缓存扑空的路线 293

6.4.6 串行化和顺序同一性 294

6.4.7 其他设计选择 296

6.4.8 带有多级高速缓存的事务拆分型总线 297

6.4.9 对一个处理器有多个待完成扑空的支持 299

6.5 实例分析：SGI Challenge和Sun Enterprise 6000 301

6.5.1 SGI Powerpath-2系统总线 302

6.5.2 SGI处理器和内存子系统 304

6.5.3 SGI I/O子系统 306

6.5.4 SGI Challenge内存系统性能 307

6.5.5 Sun Gigaplane系统总线 308

6.5.6 Sun处理器和内存系统 309

6.5.7 Sun I/O子系统 311

6.5.8 Sun Enterprise内存系统性能 311

6.5.9 应用程序性能 312

6.6.1 共享缓存的设计 314

6.6 高速缓存一致性的扩充 314

6.6.2 虚拟标引缓存的一致性 317

6.6.3 转换检测缓冲器的一致性 318

6.6.4 环上基于侦听的高速缓存一致性 320

6.6.5 在基于总线的系统中的数据和侦听带宽的扩展 322

6.7 结论 323

习题 324

第7章 可扩展多处理器 329

7.1 可扩展性 331

7.1.1 带宽的可扩展性 331

7.1.2 时延的可扩展性 333

7.1.3 成本的可扩展性 334

7.1.4 物理可扩展性 336

7.1.5 通用并行体系结构的可扩展性 339

7.2 编程模型的实现 340

7.2.1 基本的网络事务 341

7.2.2 共享地址空间 343

7.2.3 消息传递 346

7.2.4 主动消息 349

7.2.5 共同的挑战 350

7.2.6 通信体系结构设计空间 351

7.3.1 节点到网络的接口 352

7.3 物理DMA 352

7.3.2 通信抽象的实现 354

7.3.3 案例分析：nCUBE/2 354

7.3.4 典型的局域网接口 355

7.4 用户级访问 356

7.4.1 节点到网络的接口 356

7.4.2 案例分析：Thinking Machines CM-5 357

7.4.3 用户级的处理程序 358

7.5 专用消息处理 360

7.5.1 案例分析：Intel Paragon 362

7.5.2 案例分析：Meiko CS-2 365

7.6 共享的物理地址空间 367

7.6.1 案例分析：CRAY T3D 369

7.6.2 案例分析：CRAY T3E 371

7.6.3 小结 372

7.7 工作站机群和工作站网络 372

7.7.1 案例分析：Myrinet SBUS Lanai 374

7.7.2 案例分析：PCI存储器通道 376

7.8 并行软件涉及的问题 378

7.8.1 网络事务的性能 378

7.8.2 共享地址空间操作 382

7.8.3 消息传递操作 383

7.8.4 应用层性能 384

7.9 同步 390

7.9.1 加锁算法 390

7.9.2 栅障算法 393

7.10 结论 397

习题 398

第8章 基于目录的高速缓存一致性 400

8.1 可扩展的高速缓存一致性 403

8.2 基于目录方法概述 404

8.2.1 简单目录方案的操作 404

8.2.2 可扩展性 407

8.2.3 组织目录表的其他方法 408

8.3 目录协议和折中的评价 412

8.3.1 目录方案的数据共享模式 413

8.3.2 本地和远程通信流量 418

8.3.3 高速缓存块尺寸的影响 423

8.4 目录协议设计上的挑战性问题 423

8.4.1 性能 423

8.4.2 正确性 427

8.5 基于存储器的目录协议：SGI的Origin系统 432

8.5.1 高速缓存一致性协议 432

8.5.2 关于正确性问题 438

8.5.3 目录结构的细节 441

8.5.4 协议扩展 442

8.5.5 Origin2000硬件概述 443

8.5.6 Hub的实现 445

8.5.7 性能特征 447

8.6 基于高速缓存的目录协议：Sequent的NUMA-Q 451

8.6.1 高速缓存一致性协议 452

8.6.2 关于正确性问题 458

8.6.3 协议扩展 459

8.6.4 NUMA-Q硬件一览 460

8.6.5 协议和SMP节点的交互 462

8.6.6 IQ链路的实现 463

8.6.7 性能特征 464

8.6.8 对比案例分析：HALS1多处理器 466

8.7 性能参数和协议性能 467

8.8 同步 469

8.8.1 几种同步算法的性能 470

8.8.2 实现原子性原语 471

8.9 对并行软件的影响 472

8.10 高级论题 474

8.10.1 减少目录存储的开销 474

8.10.2 层次式的一致性 477

8.11 结论 484

习题 485

第9章 硬件／软件功能的折中 491

9.1 放松的存储同一性模型 492

9.1.1 系统规范说明 496

9.1.2 程序员接口 501

9.1.3 翻译机制 504

9.1.4 真实的多处理器系统中的同一性模型 504

9.2 克服容量限制 505

9.2.1 第三层高速缓存 505

9.2.2 惟有高速缓存的存储器体系结构 506

9.3 降低硬件成本 509

9.3.2 通过代码修改实现的访问控制 510

9.3.1 具有去耦辅助部件的硬件访问控制 510

9.3.3 基于页面的访问控制：共享虚拟存储器 511

9.3.4 语言和编译器支持的访问控制 520

9.4 综合：分类和简单的COMA 522

9.4.1 综合：简单的COMA和Stache 523

9.5 对并行软件的影响 526

9.6 高级论题 527

9.6.1 灵活性和CC-NUMA系统中的地址约束 527

9.6.2 以软件实现放松的存储同一性 528

9.7 结论 533

习题 533

第10章 互连网络设计 539

10.1 基本定义 540

10.2 基本的通信性能 543

10.2.1 时延 543

10.2.2 带宽 547

10.3 组织结构 549

10.3.1 链路 550

10.3.2 交换机 551

10.3.3 网络接口 552

10.4.2 线性阵列和环 553

10.4.1 全连接网络 553

10.4 互连拓扑结构 553

10.4.3 多维网格和多维花环 554

10.4.4 树 555

10.4.5 蝶网 557

10.4.6 超立方体 560

10.5 对网络拓扑设计折中的评价 561

10.5.1 无负载时延 562

10.5.2 负载情况下的时延 565

10.6 路由 569

10.6.1 路由机制 569

10.6.3 免死锁 570

10.6.2 确定性路由 570

10.6.4 虚通道 573

10.6.5 上行*－下行*路由 574

10.6.6 折转模型路由 575

10.6.7 自适应路由 577

10.7 交换机的设计 578

10.7.1 端口 578

10.7.2 内部数据通路 579

10.7.3 通道缓冲 580

10.7.4 输出调度 583

10.8 流控 585

10.7.5 堆叠式维度交换机 585

10.8.1 并行计算机网络与局域网、广域网的对照 586

10.8.2 链路级的流控 587

10.8.3 端到端的流控 590

10.9 案例分析 591

10.9.1 CRAY T3D网络 591

10.9.2 IBM SP-1、SP-2网络 593

10.9.3 可扩展一致性接口 595

10.9.4 SGI的Origin网 596

10.9.5 Myricom网络 597

10.10 结论 598

习题 598

第11章 时延的包容 601

11.1.1 时延包容与通信流水线 603

11.1 时延包容技术概述 603

11.1.2 采用技术 605

11.1.3 基本要求、优点与局限性 607

11.2 显式消息传递中的时延包容 612

11.2.1 通信结构 612

11.2.2 块数据传送 612

11.2.3 预通信 613

11.2.5 多线程技术 614

11.3 共享地址空间中的时延包容 614

11.2.4 跨越同一线程中的通信 614

11.4 共享地址空间中的数据成块传送 615

11.4.1 技术和机制 616

11.4.2 策略问题和折衷方案 617

11.4.3 性能收益 618

11.5 跨越长时延事件 622

11.5.1 跨越写操作 623

11.5.2 跨越读操作 626

11.5.3 小结 632

11.6 共享地址空间中的预通信 632

11.6.1 没有共享数据高速缓存的共享地址空间 632

11.6.2 缓存一致的共享地址空间 634

11.6.3 性能收益 641

11.7 共享地址空间中的多线程技术 645

11.6.4 小结 645

11.7.1 技术和机制 646

11.7.2 性能收益 656

11.7.3 阻塞方式的实现问题 658

11.7.4 交替方式的实现问题 660

11.7.5 在多发布处理器中集成多线程 662

11.8 免锁定的缓存设计 664

11.9 结论 666

习题 667

12.1 技术与体系结构 673

第12章 将来的发展方向 673

12.1.1 演变趋势 674

12.1.2 遇到的阻碍 676

12.1.3 潜在的突破 679

12.2 应用程序和系统软件 687

12.2.1 演变趋势 687

12.2.2 遇到的困难 690

12.2.3 潜在的突破 691

附录 并行基准测试程序集 692

参考文献 696

索引 722