第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