计算机并行计算的基本问题及现状引言工作中，我们总是希望我们自己工作得更有效率，用更少的时间解决更多的问题。

在计算机里，这就是并行计算的基本初衷。

全世界第一台计算机ENIAC中就己经出现了并行计算的概念。

它有20个累加器，可以并发执行多个加减运算，可谓开并行计算的先河。

在随后的20世纪五六十年代，由于晶体管和集成电器的发明，出现了更多更快的计算机。

IBM是这一时期的主角，同期计算机编程语言的出现，由软件完成处理并行计算的思想进一步深化。

但这一时期的计算还是大型机时代，没有几个平民能用得起这些昂贵的东西。

计算机和软件技术还锁在研究院和大学校园里。

20世纪70年代，随着微电子技术的发展，出现了微型处理器(CPU)接着,1974年，全世界第一台个人电脑牛郎星顺利出炉。

紧随其后，看到市场前景的苹果和IBM推波助澜，计算机开始进入个人时代。

个人计算机同时又催生了软件业的高速发展，软件又带动CPU不断升级换代。

这为并行计算摆脱高端路线，进入平民化时代打下了基础。

1并行计算的基本问题1.1为什么需要并行计算在个人计算机诞生后的几十年里，程序员们编写了大量的应用软件，这些软件决大部分了采用串行计算方法。

所谓串行，是指软件在PC 上执行，在进入CPU前被分解为一个个指令，指令在CPU中一条条顺序执行。

任一时间内，CPU只能够运行一条指令。

这种方式很符合我们对现实世界的思考习惯。

至于软件的运行速度，则依赖硬件的处理能力，尤其CPU的处理速度。

这种思维方式到了2005年遇到了挑战。

在那一年，受限于制造CPU的半导体材料限制，左右CPU发展的摩尔定律开始失效了。

但芯片业很快找到了一个变通的办法:在一块芯片中植入多个处理核心，通过多核的共同运算，提高运行速度。

不幸的是，采用串行方法编写的软件面临着一个尴尬的局面:如果仍采用串行编程方式，运行速度将停滞不前。

这样，原来需要CPU完成的提速工作，被迫需要软件自己来完成。

在另一个领域:互联网，由于网络数据极速膨胀，数据量己经远远超过一台或者几台大型计算机的处理能力，需要更大数量的计算机协同完成。

面对这些问题，主要的解决方案就是:并行计算。

1.2并行计算的涵义并行计算目前还是一门发展中的学科。

并行计算是相对串行计算而言的，并行计算可以分为时间上的并行计算和空间上的并行计算。

时间上的并行计算就是流水线技术，即采用指令预取技术，将每个指令分成多步，各步间叠加操作，当前指令完成前，后一指令准备就绪，缩小指令执行的时钟周期。

典型的以时间换空间。

空间上的并行计算是指由多个处理单元(不仅是CPU)执行的计算，是以空间换时间。

空间上的并行计算分为两类:单指令多数据流(SIMD)和多指令多数据流(MIMD)SIMD是流水技术的扩展，可以在一个时钟周期处理多个指令，我们目前使用的PC大多属于此列，例如AMD 3DNOW和Intel MMX。

MIMD大致又分为5类:工作站集群 (COW)。

对称多处理机(SMP)。

大规模并行处理机(MPP)。

分布共享存储处理机(DSM ) ,并行向量机(PVP)。

空间并行计算技术包括数据并行计算和任务并行计算。

数据并行计算是指将一个大的数据分解为多个小的数据，分散到多个处理单元执行。

任务并行是将大的任务分解为小的任务，分散到多个处理单元执行，任务并行同时还要避免任务重复执行，协调数据的上下文关系，避免冲突发生。

任务并行计算与实际应用需求紧密相关。

所以，任务并行计算要比数据并行计算复杂得多。

并行计算与串行计算的最大不同在于，并行计算不仅要考虑计算本身，还要考虑并行处理模型。

网络通信。

计算协作诸多问题。

1.3主要的并行计算体系类型1.3.1工作站集群(COW Cluster of Workstation)工作站集群可以理解为:PC+网络。

它可以由少数几台PC扩展到数千个节点的大规模并行系统，既可以是廉价的并行程序调试环境，也可以成为的高性能计算平台。

集群由于低成本，动态可扩充的特点，己经成为高性能计算平台的主流。

目前Google搜索和云计算业务即采用这一方式。

我国的联想深腾XXXX,曙光XXXX系列均属此类。

1.3.2多处理系统(SMP Symmetric Multi Processing)它由多个紧耦合多处理器组成，最大特点就是共享全部资源。

1.3.3大规模并行处理系统(MPP Massively Parallel Processing)由许多松祸合处理单元(不是处理器)组成的。

这种结构与SMP对立，每个单元自成体系，包括CPU。

内存。

硬盘。

操作系统，最大特点是不共享资源。

刀片服务器属于此列。

1.3.4分布式共享存储多处理(DSM)它可以视为对SMP的可扩充，将共享数据映射到不同的物理位置。

数据的同步由硬件或者软件来完成。

是目前高性能计算机的主流发展方向之一。

1.3.5并行向量机(PVP ,Parallel Vector Processor )PVP使用专用的向量处理器，提供数据共享，通过高速交叉开关实现通信。

向量运算是一种较简单的并行计算，适用面很广，机器比较容易实现，使用也方便，因此向量处理机(向量机)在20世纪70年代获得了迅速发展。

1.4并行计算的处理模式1.4.1主从模型( MS , Master-slave )即有一个主进程，其他是从进程。

主进程负责整个系统的控制(包括任务调度。

负载平衡)，从进程负责对数据的处理和计算任务。

Google 搜索业务目前就是采用的这种编程模型。

1.4.2对称处理模型(SPM)这种架构没有主从概念之分，所有进程的地位都是平等的。

在并行执行过程中，我们可以任意选择其中一个进程执行输入输出操作，其他进程扮演同样的角色。

1.4.3多程序处理模型( MPPM )在计算机集群中，每台计算机节点执行不同的程序和相同的程序。

1.5并行计算设计原则(1)适应性。

并行算法是并行计算的基础，是为解决实际问题而出现，必须与实际应用相结合。

(2)可扩展。

并行算法是否能够随计算节点增加或减少而同步的线性变化，是评价一个并行算法是否有效的重要标志之一。

(3)粗粒度。

通常情况下，粒度越大越好。

这是因为在每个处理机中有很多需要计算的工作任务，如此可以充分发挥多处理机的作用。

并行加速比对细粒度问题一般情况下是不会很高的，这也是为什么并行计算需要求解大规模问题的原因所在。

(4)减少通信。

一个高效的并行算法，通信是至关。

提高性能的一个关键是减少数据通信量和通信次数。

(5)优化性能。

评价性能的优缺，主要是看单节点计算的处理能力，和并行执行效率。

这与实际采用的技术息息相关。

1.6并行计算设计方法1.6.1分片(1)数据分片。

数据分片包括两类:数值分片和哈希分片。

数值分片适用于己知数据范围的分解，如果Int,Long类型处理。

哈希分片适用于未知数据范围的数据分解，包括字符串，字节数组类型。

数据分片是把相同的操作作用于不同的数据，达到提到快速求解的目的。

数据分片模型是一种较高层次的并行计算模型，编程却相对简单。

数据分片的并行计算最早应用于并行向量计算机(PVP))经过长期实践表明，该技术可以高效地求解大部分的科学和工程计算问题。

数据并行处理对象是数值，对应非数值类问题，则需要其他并行计算模型来解决。

Google的搜索业务是采用数据分片的并行计算模式。

(2)任务分片。

任务分片的并行计算主要针对非数值类的并行处理。

它通常的消息传递机制(目前主流是PMI是各并行计算执行单元之间通过传递消息来交换数据，协调步伐，执行控制操作。

消息传递一般是针对分布节点内存，也可以适用于共享内存的并行节点。

消息传递模型为程序员提供了更加灵活的控制手段和表现形式。

消息传递模型很容易实现，控制变化手段灵活多样，但是需要程序员有丰富的并行编程经验。

是一种较低层次，编程相对复杂的模型，适用于业务流程的并行化处理。

1.6.2通信协调计算过程中的数据共享。

通信工作目前主要由TCP/IP协议完成。

1.6.3组织组织各任务并发执行，提高性能。

在主线程的控制下，子线程在此承担具体的并发操作任务。

1.6.4映射分配任务(分布处理。

共享处理)。

线程和通信共同完成。

1.7并行计算应注意的事项(1)任务分解:这是所有并行计算的核心问题，优秀的任务分解需要保证平均和处理负载的平衡，同时，随着处理器能力的动态伸缩动态调节。

(2)通信:并发处理离不开网络通信联系。

相较与CPU运算，数据在网络间传递延迟是并发处理的瓶颈之一。

光纤网络是目前最好的选择。

(3)并行协调:是并行运算过程中控制流程。

(4)并行冲突:并行冲突来源主要是任务分解和并行协调。

(5)数据归并:这是数据计算完成后，必不可少的一步操作。

数据归并需要注意:过滤重复数据，合并相关性数据等。

(6)死锁。

死锁是在编程过程中，由于人为的原因造成。

死锁表示为:对象间在不放弃自己资源下互相调用。

请程序员注意。

2并行计算的发展现状2.1多核为主流的体系结构多核处理器代表了计算技术的一次创新。

由于数字数据和互联网的全球化，商业和消费者开始要求多核处理器带来性能改进，这个重要创新就开始了，因为多核处理器比单核处理器具有性能和效率优势，多核处理器将会成为被广泛采用的计算模型。

在驱动PC安全性和虚拟化技术的重大进程过程中，多核处理器扮演着中心作用，这些安全性和虚拟化技术的开发用于为商业计算市场提供更大的安全性。

更好的资源利用率。

创造更大价值。

普通消费者用户也期望得到前所未有的性能，这将极大地扩展其家庭PC和数字媒体计算系统的使用。

多核处理器具有不增加功耗而提高性能的好处，实现更大的性能/能耗比。

在一个处理器中放入两个或多个功能强大的计算核产生了一个重大的可能性。

由于多核处理器能提供比单核处理器更好的性能和效率，下一代的软件应用程序很有可能是基于多核处理器而开发的。

不管这些应用是帮助专业的电影公司以更少的投入和更少的时间完成更真实的电影，还是以更彻底的方法使得PC更自然和直观，多核处理器技术将永远改变计算世界。

多核处理器表达了AMD了解顾客需求并且开发最能满足客户要求产品的意愿。

微软多核计算的主管Dan Reed称，整个世界上很缺乏那些并行计算的研究人员，而一个间接的原因就是学院里对于并行计算的关注度不够，而这些学院正是下一代软件开发人员诞生的地方。

越来越高的时钟频率导致应用程序的代码运行得越来越快，而对于当前多核处理器来讲这一规则虽然成立，但却有所不同。

而这种不同可以做一个形象的比喻，那就是一部跑车和一辆学校的巴士。

当跑车能够以很快的速度飞奔时，巴士虽然比较慢，但它可以载着更多的人前行。

问题就是，简单地在计算机CPU上增加多个核并不能增加传统应用程序代码的运行速度，这一结果是根据一项来自于Forrester研究公司的报告得出的。

换句话说，复杂的工作需要拆分来填充这辆巴士上的空座位。