并行计算

[编辑] 基本体系结构

平行计算或稱平行計算是相对于串行计算来说的，所谓并行计算分为时间上的并行和空间上的并行。 时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。并行计算科学中主要研究的是空间上的并行问题。 空间上的并行导致了两类并行机的产生，按照Flynn的说法分为：单指令流多数据流（SIMD）和多指令流多数据流（MIMD）。我们常用的串行机也叫做单指令流单数据流（SISD）。MIMD类的机器又可分为以下常见的五类：并行向量处理机(PVP)，对称多处理机(SMP)，大规模并行处理机(MPP), 工作站机群(COW)，分布式共享存储处理机(DSM)。

访存模型 并行计算机有以下四种访存模型：均匀访存模型（UMA），非均匀访存模型（NUMA），全高速缓存访存模型（COMA），一致性高速缓存非均匀存储访问模型（CC-NUMA）和非远程存储访问模型（NORMA）。

[编辑] 平行計算模型

不像串行计算机那样，全世界基本上都在使用天才计算机科学家冯·诺依曼的计算模型；并行计算机没有一个统一的计算模型。不过，人们已经提出了几种有价值的参考模型：PRAM模型，BSP模型，LogP模型，C^3模型等。

[编辑] 并行计算机网络

并行计算机是靠网络将各个处理机或处理器连接起来的，一般来说有以下几种方式

1. 静态连接：一维线性连接，网孔连接，超立方体连接，树连接，立方环连接，洗牌交换连接，蝶形连接，金字塔连接等。
2. 动态连接： 总线连接(Bus)，交叉开关(CS)，多级互联网络(MIN)。

网络的基本术语：

1. 节点度
2. 网络直径
3. 对剖宽度
4. 嵌入

[编辑] 并行计算机性能度量

1. 基本指标
   1. 执行时间
   2. 工作负载
   3. 存取性能
2. 加速比评测
   1. Amdahl定理
   2. Gustafson定理
   3. Sun-Ni定理
3. 可扩放性标准
   1. 等效率标准
   2. 等速度标准
   3. 平均延迟标准

[编辑] 并行算法

并行算法是一门还没有发展成熟的学科，虽然人们已经总结出了相当多的经验，但是远远不及串行算法那样丰富。并行算法设计中最常用的的方法是PCAM方法，即划分，通信，组合，映射。首先划分，就是将一个问题平均划分成若干份，并让各个处理器去同时执行；通信阶段，就是要分析执行过程中所要交换的数据和任务的协调情况，而组合则是要求将较小的问题组合到一起以提高性能和减少任务开销，映射则是要将任务分配到每一个处理器上。总之，并行算法还需要相当多完善的地方。 并行算法与串行算法最大的不同之处在于，并行算法不仅要考虑问题本身，而且还要考虑所使用的并行模型，网络连接等等。

• 常见的非数值算法设计方法举例
  • 并行播送与并行求和
  • 并行排序算法；
  • 并行选择算法：所谓选择问题就是在一给定的序列中选择出某组（个）满足给定条件的元素。
  • 关于图论中的一些并行算法：
    • 图论作为一门到近代才发展起来的科学。在图论中有很多关于如何设计算法的问题，比如求最小生成树，单源最短路径等等。事实上，这些算法中有很多是可以并行化的，而且并行化时运用的思想具有很大的启发性，下面是几个常见的并行图论算法。
  • 关于串处理的并行算法：
    • KMP算法的并行化。
• 常见的数值算法设计方法举例
  • 并行快速傅里叶变换。

[编辑] 参阅

• 计算机科学
• 计算机科学课程列表
• en:Message_Passing_Interface