1. 并行算法绪论
1.1. 并行计算机体系结构
并行计算机的分类
- SISD：单指令流单数据流机，传统的单处理机
- SIMD：单指令流多数据流机
- MISD：多指令流单数据流机，实际中不存在的机器
- MIMD：多指令流多数据流机
- PVP：并行向量机
- SMP：对称多处理机
- MPP：大规模并行处理机
- COW：工作站机群
- DSM：分布共享存储多处理机
并行计算机的互连方式
- 静态：
- LA：一维线性连接
- MC：网孔连接
- TC：树形连接
- MT：树网连接
- HC：超立方连接
- BC：蝶形连接
- SE：洗牌交换连接
1.2. 并行计算模型
- PRAM模型：又称SIMD-SM模型
- 假设：
- SM容量无限
- 有限/无限个功能相同的处理器
- 本地指令和SM的R/W操作都取单位时间
- 分类：
- PRAM-CRCW并发读并发写
- CPRAM-CRCW：仅允许写入相同的数据
- PPRAM-CRCW：仅允许优先级最高的处理器写入
- APRAM-CRCW：允许任意处理器自由写入
- PRAM-CRRW：并发读互斥写
- PRAM-EREW：互斥读互斥写
- PRAM-CRCW并发读并发写
- 假设：
