并行计算机体系结构：硬件/软件结合的设计与分析

第1章 引论

1. 1 为什么要用并行体系结构

1. 1. 1 计算机应用发展的趋势

1. 1. 2 微电子技术趋势

1. 1. 3 体系结构趋势

1. 1. 4 超级计算机

1. 1. 5 小结

1. 2 并行体系结构的融合

1. 2. 1 通信体系结构

1. 2. 2 共享地址空间

1. 2. 3 消息传递

1. 2. 4 融合

1. 2. 5 数据并行体系结构

1. 2. 6 其他并行体系结构

1. 2. 7 一个通用并行体系结构

1. 3 基本的设计问题

1. 3. 1 通信抽象

1. 3. 2 编程模型的要求

1. 3. 3 通信和复制

1. 3. 4 性能

1. 3. 5 小结

1. 4 结论

1. 5 历史资料

习题

第2章 并行程序

2. 1 并行应用的案例分析

2. 1. 1 洋流的模拟

2. 1. 2星系演化的模拟

2. 1. 3 用光线跟踪法来实现复杂场景的可视化

2. 1. 4 针对关联性的数据挖掘

1. 2 并行化过程

2. 2. 1 程序并行化过程中的几个步骤

2. 2. 2 计算并行和数据并行

2. 2. 3 并行化过程的目标

2. 3 一个例子程序的并行化

2. 3. 1 方程求解器的内核

2. 3. 2 分解

2. 3. 3 分配

2. 3. 4 在数据并行模型下的协调

2. 3. 5 在共享地址空间模型下的协调

2. 3. 6 在消息传递模型下的协调

2. 4 结论

习题

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

3. 1 划分阶段的性能问题

3. 1. 1 负载平衡和同步等待时间

3. 1. 2 减少固有的通信

3. 1. 3 减少额外的工作

3. 1. 4 小结

3. 2 在多存储器系统中的数据访问和通信

3. 2. 1 看作扩展的存储层次结构的多处理器系统

3. 2. 2 在扩展的存储层次结构中的附加通信

3. 2. 3 用工作集的观点看附加的通信和数据的复制

3. 3 性能的协调

3. 3. 1 减少附加通信

3. 3. 2 将通信结构化以降低代价

3. 4 从处理器角度看到的性能因素

3. 5 并行应用程序案例的深入分析

3. 5. 1　Ocean

3. 5. 2 Bames-Hut

3. 5. 3 光线跟踪

3. 5. 4 数据挖掘

3. 6 编程模型涉及的问题

3. 6. 1 命名

3. 6. 2 复制

3. 6. 3 通信的开销和粒度

3. 6. 4 块数据传送

3. 6. 5 同步

3. 6. 6 硬件代价和设计复杂性

3. 6. 7 性能模型

3. 6. 6 小结

3. 7 结论

习题

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

4. 1 改变工作负载和机器的规模

4. 1. 1 多处理器性能的基本测量

4. 1. 2 为什么要考虑扩放性

4. 1. 3 扩放的关键问题

4. 1. 4 扩放模型和加速比的测量

4. 1. 5 扩放模型对方程求解器内核的影响

4. 1. 6　扩放工作负载参数

4. 2　评价一台实际的机器

4. 2. 1 使用微基准测试程序分离性能

4. 2. 2　选择工作负载

4. 2. 3 评价一台固定规模的机器

4. 2. 4　改变机器的规模

4. 2. 5　选择性能指标

4. 3　对一个体系结构概念或设计权衡的评估

4. 3. 1 多处理器的模拟

4. 3. 2　缩小模拟的问题和机器参女的规模

4. 3. 3 处理参数空间：评价举例

4. 3. 4 小结

4. 4　说明工作负载的特征

4. 4. 1 工作负载案例分析

4. 4. 2　工作负载的特征化

4. 5 结论

习题

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

5. 1 高速缓存的一致性

5. 1. 1 高速缓存一致性问题

5. 1. 2　通过总线侦听的高速缓存一致性

5. 2　存储同一性

5. 2. 1 顺序同一性

5. 2. 2　保证顺序同一性的充分条件

5. 3 总线侦听协议的设计空间

5. 3. 1 一种三态 MSI 回写作废式协议

5. 3. 2 一种四态 MESI 回写作废式协议

5. 3. 3 一种四态 Dragon 回写更新式协议

5. 4 关于协议设计中若干折中的评估

5. 4. 1 方法论

5. 4. 2 在MESI协议下的带宽需求

5. 4. 3 协议优化的影响

5. 4. 4 高速缓存中存储块大小的权衡

5. 4. 5 基于更新和基于作废协议的对比

5. 5 同步

5. 5. 1 同步事件的组成部分

5. 5. 2 用户和系统的角色

5. 5. 3 互斥

5. 5. 4 点对点事件同步

5. 5. 5 全局 栅障 事件的同步

5. 5. 6 同步问题小结

5. 6 对软件的影响

5. 7 结论

习题

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

6. 1 正确性需求

6. 2 基础设计：采用原子总线的单级高速缓存

6. 2. 1 高速缓存控制器和标记的设计

6. 2. 2 侦听结果的报告

6. 2. 3 对回写的处理

6. 2. 4 基础系统组织

6. 2. 5 非原子性的状态转移

6. 2. 6 串行化

6. 2. 7 死锁

6. 2. 8 活锁和挨饿

6. 2. 9 原子操作的实现

6. 3 多级高速缓存层次结构

6. 3. 1 包含性的维护

6. 3. 2 在高速缓存层次结构中传播一致性的事务

6. 4 事务拆分型总线

6. 4. 1 事务拆分型总线设计的一个例子

6. 4. 2 总线设计和请求-响应的匹配

6. 4. 3 侦听结果和冲突的请求

6. 4. 4 流控制

6. 4. 5　一次缓存扑空的路线

6. 4. 6 串行化和顺序同一性

6. 4. 7　其他设计选择

6. 4. 8 带有多级高速缓存的事务拆分型总线

6. 4. 9　对一个处理器有多个待完成扑空的支持

6. 5 实例分析：SGI Challenge 和Sun Enterprise 6000

6. 5. 1 SGI Powerpath-2系统总线

6. 5. 2 SGI处理器和内存子系统

6. 5. 3 SGI I／O子系统

6. 5. 4 SGI Challenge内存系统性能

6. 5. 5 Sun Gigaplane系统总线

6. 5. 6 Sun处理器和内存系统

6. 5. 7 Sun I／O子系统

6. 5. 8 Sun Enterprise内存系统性能

6. 5. 9 应用程序性能

6. 6 高速缓存一致性的扩充

6. 6. 1 共享缓存的设计

6. 6. 2 虚拟标引缓存的一致性

6. 6. 3 转换检测缓冲器的一致性

6. 6. 4 环上基于侦听的高速缓存一致性

6. 6. 5 在基于总线的系统中的数据和侦听带宽的扩展

6. 7 结论

习题

第7章 可扩展多处理器

7. 1 可扩展性

7. 1. 1 带宽的可扩展性

7. 1. 2 时延的可扩展性

7. 1. 3 成本的可扩展性

7. 1. 4 物理可扩展性

7. 1. 5 通用并行体系结构的可扩展性

7. 2 编程模型的实现

7. 2. 1 基本的网络事务

7. 2. 2 共享地址空间

7. 2. 3 消息传递

7. 2. 4 主动消息

7. 2. 5 共同的挑战

7. 2. 6 通信体系结构设计空间

7. 3 物理DMA

7. 3. 1 节点到网络的接口

7. 3. 2 通信抽象的实现

7. 3. 3 案例分析：nCUBE／2

7. 3. 4 典型的局域网接口

7. 4 用户级访问

7. 4. 1 节点到网络的接口

7. 4. 2 案例分析：Thinking Machines CM-5

7. 4. 3 用户级的处理程序

7. 5 专用消息处理

7. 5. 1 案例分析：Intel Paragon

7. 5. 2 案例分析：Meiko CS-2

7. 6 共享的物理地址空间

7. 6. 1 案例分析：CRAY T3D

7. 6. 2 案例分析：CRAY T3E

7. 6. 3 小结

7. 7 工作站机群和工作站网络

7. 7. 1 案例分析：Myrinet SBUS Lanai

7. 7. 2 案例分析：PCI存储器通道

7. 8 并行软件涉及的问题

7. 8. 1 网络事务的性能

7. 8. 2 共享地址空间操作

7. 8. 3 消息传递操作

7. 8. 4 应用层性能

7. 9 同步

7. 9. 1 加锁算法

7. 9. 2 栅障算法

7. 10 结论

习题

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

8. 1 可扩展的高速缓存一致性

8. 2 基于目录方法概述

8. 2. 1 简单目录方案的操作

8. 2. 2 可扩展性

8. 2. 3 组织目录表的其他方法

8. 3 目录协议和折中的评价

8. 3. 1 目录方案的数据共享模式

8. 3. 2 本地和远程通信流量

8. 3. 3 高速缓存块尺寸的影响

8. 4 目录协议设计上的挑战性问题

8. 4. 1 性能

8. 4. 2 正确性

8. 5 基于存储器的目录协议：SGI的Origin系统

8. 5. 1 高速缓存一致性协议

8. 5. 2 关于正确性问题

8. 5. 3 目录结构的细节

8. 5. 4 协议扩展

8. 5. 5 Origin2000硬件概述

8. 5. 6 Hub的实现

8. 5. 7 性能特征

8. 6 基于高速缓存的目录协议：Sequent的NUMA-Q

8. 6. 1 高速缓存一致性协议

8. 6. 2 关于正确性问题

8. 6. 3 协议扩展

8. 6. 4 NUMA-Q硬件一览

8. 6. 5 协议和SMP节点的交互

8. 6. 6 IQ链路的实现

8. 6. 7 性能特征

8. 6. 8 对比案例分析：HAL S1多处理器

8. 7 性能参数和协议性能

8. 8 同步

8. 8. 1 几种同步算法的性能

8. 8. 2 实现原子性原语

8. 9 对并行软件的影响

8. 10 高级论题

8. 10. 1 减少目录存储的开销

8. 10. 2 层次式的一致性

8. 11 结论

习题

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

9. 1 放松的存储同一性模型

9. 1. 1 系统规范说明

9. 1. 2 程序员接口

9. 1. 3 翻译机制

9. 1. 4 真实的多处理器系统中的同一性模型

9. 2 克服容量限制

9. 2. 1 第三层高速缓存

9. 2. 2 惟有高速续存的存储器体系结构

9. 3 降低硬件成本

9. 3. 1 具有去耦辅助部件的硬件访问控制

9. 3. 2 通过代码修改实现的访问控制

9. 3. 3 基于页面的访问控制：共享虚拟存储器

9. 3. 4 语言和编译器支持的访问控制

9. 4 综合：分类和简单的COMA

9. 4. 1 综合：简单的COMA和Stache

9. 5 对并行软件的影响

9. 6 高级论题

9. 6. 1 灵活性和CC-NUMA系统中的地址约束

9. 6. 2 以软件实现放松的存储同一性

9. 7 结论

习题

第10章 互连网络设计

10. 1 基本定义

10. 2 基本的通信性能

10. 2. 1 时延

10. 2. 2 带宽

10. 3 组织结构

10. 3. 1 链路

10. 3. 2 交换机

10. 3. 3 网络接口

10. 4 互连拓扑结构

10. 4. 1 全连接网络

10. 4. 2 线性阵列和环

10. 4. 3 多维网格和多维花环

10. 4. 4 树

10. 4. 5 蝶网

10. 4. 6 超立方体

10. 5 对网络拓扑设计折中的评价

10. 5. 1 无负载时延

10. 5. 2 负载情况下的时延

10. 6 路由

10. 6. 1 路由机制

10. 6. 2 确定性路由

10. 6. 3 免死锁

10. 6. 4 虚通道

10. 6. 5 上行-下行路由

10. 6. 6 折转模型路由

10. 6. 7 自适应路由

10. 7 交换机的设计

10. 7. 1 端口

10. 7. 2 内部数据通路

10. 7. 3 通道缓冲

10. 7. 4 输出调度

10. 7. 5 堆叠式维度交换机

10. 8 流控

10. 8. 1 并行计算机网络与局域网. 广域网的对照

10. 8. 2 链路级的流控

10. 8. 3 端到端的流控

10. 9 案例分析

10. 9. 1 CRAY T3D网络

10. 9. 2 IBM SP-1. SP-2网络

10. 9. 3 可扩展一致性接口

10. 9. 4 SCI的Origin网

10. 9. 5 Myricom网络

10. 10 结论

习题

第11章 时延的包容

11. 1 时延包容技术概述

11. 1. 1 时延包容与通信流水线

11. 1. 2 采用技术

11. 1. 3 基本要求. 优点与局限性

11. 2 显式消息传递中的时延包容

11. 2. 1 通信结构

11. 2. 2 块数据传送

11. 2. 3 预通信

11. 2. 4 跨越同一线程中的通信

11. 2. 5 多线程技术

11. 3 共享地址空间中的时延包容

11. 4 共享地址空间中的数据成块传送

11. 4. 1 技术和机制

11. 4. 2 策略问题和折衷方案

11. 4. 3 性能收益

11. 5 跨越长时延事件

11. 5. 1 跨越写操作

11. 5. 2 跨越读操作

11. 5. 3 小结

11. 6 共享地址空间中的预通信

11. 6. 1 没有共享数据高速缓存的共享地址空间

11. 6. 2 缓存一致的共享地址空间

11. 6. 3 性能收益

11. 6. 4 小结

11. 7 共享地址空间中的多线程技术

11. 7. 1 技术和机制

11. 7. 2 性能收益

11. 7. 3 阻塞方式的实现问题

11. 7. 4 交替方式的实现问题

11. 7. 5 在多发布处理器中集成多线程

11. 8 免锁定的缓存设计

11. 9 结论

习题

第12章 将来的发展方向

12. 1 技术与体系结构

12. 1. 1 演变趋势

12. 1. 2 遇到的阻碍

12. 1. 3 潜在的突破

12. 2 应用程序和系统软件

12. 2. 1 演变趋势

12. 2. 2 遇到的困难

12. 2. 3 潜在的突破

附录 并行基准测试程序集

参考文献

索引