并行计算

来自 搜狐网 的图片

并行计算是中国的一个科技名词。

语言一发即逝，不留痕迹。当人类意识到需要把说出的话记下来时，就发明了文字。在世界范围内，曾经独立形成的古老文字除我们的汉字外，还有埃及的圣书字、两河流域的楔形文字、古印度的印章文字以及中美洲的玛雅文。后来，这些古老文字的命运各不相同，或因某种历史原因而消亡，如玛雅文；或因文字的根本变革而遭废弃，如楔形文、圣书字，只汉字沿用至今，而且古今传承的脉络清晰可见，成了中华民族文化的良好载体。

目录

名词解释

并行计算（Parallel Computing）是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算。并行计算系统既可以是专门设计的、含有多个处理器的超级计算机，也可以是以某种方式互连的若干台的独立计算机构成的集群。通过并行计算集群完成数据的处理，再将处理的结果返回给用户。

并行计算可分为时间上的并行和空间上的并行。

时间上的并行：是指流水线技术，比如说工厂生产食品的时候步骤分为：

1． 清洗：将食品冲洗干净。

2． 消毒：将食品进行消毒处理。

3． 切割：将食品切成小块。

4． 包装：将食品装入包装袋。

如果不采用流水线，一个食品完成上述四个步骤后，下一个食品才进行处理，耗时且影响效率。但是采用流水线技术，就可以同时处理四个食品。这就是并行算法中的时间并行，在同一时间启动两个或两个以上的操作，大大提高计算性能。

空间上的并行：是指多个处理机并发的执行计算，即通过网络将两个以上的处理机连接起来，达到同时计算同一个任务的不同部分，或者单个处理机无法解决的大型问题。

比如小李准备在植树节种三棵树，如果小李1个人需要6个小时才能完成任务，植树节当天他叫来了好朋友小红、小王，三个人同时开始挖坑植树，2个小时后每个人都完成了一颗植树任务，这就是并行算法中的空间并行，将一个大任务分割成多个相同的子任务，来加快问题解决速度。

特征

为利用并行计算，通常计算问题表现为以下特征：

（1）将工作分离成离散部分，有助于同时解决；

（2）随时并及时地执行多个程序指令；

（3）多计算资源下解决问题的耗时要少于单个计算资源下的耗时。

基本体系结构

并行计算科学中主要研究的是空间上的并行问题。从程序和算法设计人员的角度来看，并行计算又可分为数据并行和任务并行。一般来说，因为数据并行主要是将一个大任务化解成相同的各个子任务，比任务并行要容易处理。

空间上的并行导致了两类并行机的产生，按照Flynn的说法分为：单指令流多数据流（SIMD）和多指令流多数据流（MIMD）。我们常用的串行机也叫做单指令流单数据流（SISD）。MIMD类的机器又可分为以下常见的五类：并行向量处理机（PVP）、对称多处理机（SMP）、大规模并行处理机（MPP）、工作站机群（COW）、分布式共享存储处理机（DSM）。

访存模型

并行计算机有以下五种访存模型：

均匀访存模型（UMA）

非均匀访存模型（NUMA）

全高速缓存访存模型（COMA）

一致性高速缓存非均匀存储访问模型（CC-NUMA）

非远程存储访问模型（NORMA）。

计算模型

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

网络设置

并行计算机是靠网络将各个处理机或处理器连接起来的，一般来说有以下几种方式：处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等。静态连接

动态连接

用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。

基本术语

节点度:射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。

网络直径:网络中任何两个节点之间的最长距离，即最大路径数。

对剖宽度:对分网络各半所必须移去的最少边数。

对剖带宽:每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节)。