Please enable Javascript to view the contents

并行算法总结

 ·  ☕ 1 分钟

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:互斥读互斥写

1.3. 并行算法的基础知识和性能分析

2. 设计技术

2.1. 并行算法的三种基本设计方法及其代表实例

2.2. 基本设计技术

分享

Wenbo Chen
作者
Wenbo Chen
CG Student

目录