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并发读并发写
- 假设: