并行计算

来自计算思维百科
跳转至: 导航搜索
并行计算.jpg

并行计算或称平行计算是相对于串行计算来说的。它是一种一次可执行多个指令的算法,目的是提高计算速度,及通过扩大问题求解规模,解决大型而复杂的计算问题。所谓并行计算可分为时间上的并行和空间上的并行。 时间上的并行就是指流水线技术,而空间上的并行则是指用多个处理器并发的执行计算。

定义

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

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

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

  1. 清洗:将食品冲洗干净。
  2. 消毒:将食品进行消毒处理。
  3. 切割:将食品切成小块。
  4. 包装:将食品装入包装袋。

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

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

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

特征

为利用并行计算,通常计算问题表现为以下特征:
(1)将工作分离成离散部分,有助于同时解决;
(2)随时并及时地执行多个程序指令;
(3)多计算资源下解决问题的耗时要少于单个计算资源下的耗时。

使用方法及步骤

能够利用并行计算解决的问题,通常有以下3个特征:

(1)问题可分离;

(2)问题的分解可同时执行;

(3)并行执行效率高于顺序执行。

基本体系结构

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

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

访存模型

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

均匀访存模型(UMA)
非均匀访存模型(NUMA)
全高速缓存访存模型(COMA)
一致性高速缓存非均匀存储访问模型(CC-NUMA)
非远程存储访问模型(NORMA)。

并行计算模型

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

并行计算机网络

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

  1. 静态连接:处理单元间有着固定连接的一类网络,在程序执行期间,这种点到点的链接保持不变;典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等。
  2. 动态连接:用交换开关构成的,可按应用程序的要求动态地改变连接组态;典型的动态网络包括总线、交叉开关和多级互连网络等。

网络的基本术语

节点度:射入或射出一个节点的边数。在单向网络中,入射和出射边之和称为节点度。 网络直径:网络中任何两个节点之间的最长距离,即最大路径数。 对剖宽度:对分网络各半所必须移去的最少边数。 对剖带宽:每秒钟内,在最小的对剖平面上通过所有连线的最大信息位(或字节)。

并行计算机性能度量

基本指标

加速比评测

可扩放性标准

应用案例

应用1-食堂窗口选餐过程的并行

案例:食堂有“菜窗口”,也有“粥窗口”,两个窗口服务同时进行,在菜窗口打完菜的同学到“粥窗口”排队打粥。如果打菜和打粥都在一个窗口,那么一次只能服务一个同学,而分两个窗口,相同的时间内可以同时服务两个同学。

应用2-准备晚餐过程中的并行

案例: 通常准备晚餐的过程是先用电饭煲煲饭,煲饭的同时可以洗菜和炒菜,等菜炒好了,饭也熟了。

应用3-求和

案例:怎样计算1+2+3+4+5+6+7+8+9+10+11+12更快?

解决方案:把 1+2+3+4+5+6+7+8+9+10+11+12分成1+2+3+4,5+6+7+8,9+10+11+12三部分,让3个同学计算其中一部分,然后再把三个同学的计算结果相加得到最后答案。

应用4-汽车批量生产

案例:

生产一辆汽车一般需要四个步骤:

1. 冲压:制作车身外壳和底盘等部件;

2. 焊接:将冲压成形后的各部件焊接成车身;

3. 涂装:将车身等主要部件清洗、化学处理、打磨、喷漆和烘干;

4. 总装:将各部件(包括发动机和向外采购的零部件)组装成车。

因此,对应地需要冲压、焊接、涂装和总装四个工人。原始的方式是第一辆汽车经过上面四个步骤制作完成后,下一辆汽车才开始生产,也就是说同一时刻只在制作一辆汽车,效率极低,那么我们如何通过时间并行的方法进行汽车批量生产呢?

解决步骤:

我们发现,某个时段中一辆汽车在进行装配时,其它三个工人处于闲置状态,显然这是对资源的极大浪费!于是开始思考能有效利用资源的方法:在第一辆汽车经过冲压进入焊接工序的时候,立刻开始进行第二辆汽车的冲压,而不是等到第一辆汽车经过全部四个工序后才开始。之后的每一辆汽车都是在前一辆冲压完毕后立刻进入冲压工序,这样在后续生产中就能够保证四个工人一直处于运行状态,不会造成人员的闲置。这样就大大提高了生产效率了。

可以体现的计算思维

并行计算通过对问题的分解,同时执行多个计算,达到大大提高效率的结果,体现了计算思维并行的思想,目前一些并行计算机还是比较昂贵,但随着技术的发展,并行计算机应该会变得廉价易得,普通人都可以用,到那时,计算机处理数据的速度就更加快了。