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

　　当今并行计算机体系结构最令人振奋的发展是对传统的相互各异的并行实现方式的完美综合。本书正是以此技术为背景，通过大量的实例，精确的数据和作者对并行结构深邃的理解向人们提示了蕴藏于并行体系结构中的强大力量，并同时首次对设计的平衡性能做了充分的定量评估。本书用硬件、软件方面的最新技术对并行结构设计中的若干重大问题做了全面、深刻的追踪探讨。本书是诸多专家智慧的结晶、经验的融合，是广大学生、科研人员、工程人员的权威教材，也是奉献于并行结构科学的经典之作。DavidE.Culler&JaswinderPalSinghwithAnoopGupta：ParallelComputerArchitecture，A

　　DavidE.Culler，加洲大学伯克利分校计算机科学系教授。Culler博士的研究领域包括计算机体系结构、通信、编程语言、操作系统和性能分析。他曾是伯克利工作站网络（NOW）项目的领导者。该项目点燃了当前在全球范围发展的高性能机群系统商业化的革命之火。Culler博士因他在快速通信的主动消息、LogP并行性能模型、Split-C并行语言、TAM线程抽象机和数据流体系结构方面的研究而闻名于世。他曾被国家科学基金会授予过总统学术研究基金奖和总统青年研究人员奖。他于1989年获得麻省理工学院博士学位。目前任加洲大学伯克利分校电气工程与计算机科学系的副主任，是千年（Millennium）项目的负责人，从事校园网范围的机群系统的研究。等等

第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 潜在的突破
附录 并行基准测试程序集
参考文献
索引