换一个角度思考-并行计算

1、换一个角度思考：并行计算一、前言工作中，我们总是希望我们自己工作得更有效率，用更少的吋间解决更多的问题。在计算机里，这 就是并行计算的基木初衷。全世界第一台计算机eniac中就己经出现了并行计算的概念。它有20个累 加器，可以并发执行多个加减运算，可谓开并行计算的先河。在随后的上世纪五六丁年代，由于晶体管 和集成电器的发明，出现了了更多更快的计算机。ibm是这一时期的主角，同期计算机编程语言的出现, 由软件完成处理并行计算的思想进一步深化。但这一时期的计算还是大型机时代，没有儿个平民能用得 起这些昂贵的大家伙。计算机和软件技术述锁在研究院和大学校园里。七i年代，随着微电子技术的发展，出现了微型

2、处理器（cpu）。接着，1974年，全世界第一台个 人电脑：牛郎星顺利出炉。紧随其后，看到市场前景的苹果和ibm推波助澜，计算机开始进入个人时代。 个人计算机同时乂催生了软件业的窩速发展，软件乂带动cpu不断升级换代。这为并行计算摆脱高端路 线，进入平民化时代打下了基础。庞大的eniac,运算速度只相当于现在的一只计算器。全世界第一台个人计算机(pc)： 丫郎星。使川intel8080处理器，配4k内存。为什么需要并行讨ci在个人计算机诞生后的儿十年甲，程序员们编写了大量的应川软件，这些软件决大部分了采用串行 计算方法。所谓串行，是指软件在pc±执行，在进入cpu前被分解为一个个指令

3、，指令在cpu中一 条条顺序执行。任一时间内，cpu只能够运行一条指令。这种方式很符合我们对现实此界的思考习惯。 至于软件的运行速度，则依赖硬件的处理能力，尤其cpu的处理速度。这种思维方式到了 2005年遇到 了挑战。在那一年，受限于制造cpu的半导体材料限制，左右cpu发展的摩尔定律开始失效了。但芯 片业很快找到了一个变通的办法：在一块芯片中植入多个处理核心，通过多核的共同运算，捉高运行速 度。不幸的是，采用串行方法编写的软件血临着一个尷尬的局面：如果仍采用串行编程方式，运行速度 将停滞不前。这样，原來需要cpu完成的提速工作，被迫需要软件口已來完成。在另一个领域：互联 网，由于网络数据极

4、速膨胀，数据量已经远远超过一台或者儿台人型计算机的处理能力，需要更大数量 的计算机协同完成。而对这些问题，主要的解决方案就是：并行计算。probleminstructionsiiiuuni 111tnt3t2串行计算示例全球第一款双核处理器：ibm power4 （64位，2001年诞生），主要川于ibm服务器和苹果的macintosh 上。当年的mac机it于运算速度太快了，被禁止销往中国、朝鲜等“敌对国家”。amd第一款双核处理器：opteron （皓龙）。用于服务器领域，64位，2005年4月22日发布。amd第一款针对桌而的双核处理器：athlon （速龙）。同样是64位，只比服务器版

5、木晩1个月面市。intel是顶极芯片制造商中最晚推出的双核处理器:intel pentiunid, 2005年5月26日发布。三、并行计算介绍核心提示：程序二数据+算法，并行计算程序二线程+分片+算法。3.1概述并行计算目前还是一门发展中的学科。并行计算是相对串行计算而言的，并行计算可以分为吋间上 的并行计算和空间上的并行计算。吋间上的并行计算就是流水线技术，即釆用指令预取技术，将每个指令分成多步，各步间叠加操作, 当前指令完成前，后一指令准备就绪，缩小指令执行的时钟周期。典型的以时间换空间。流水线技术rh 处理器(cpu)提供，不属于我们讨论的范畴。空间上的并行计算是指rh多个处理单元(不仅

6、是cpu)执行的计算，是以空间换时间。空间上的并 行计算分为两类：单指令多数据流(simd)和多指令多数据流(mimd)osimd是流水技术的扩展，可以在一个时钟周期处理多个指令，我们目前使川的pc大多属于此列, 例如amd3dnow和intel mmxo因为是硬件提供的技术，也不属于我们讨论的内容。mimd大致又分为五类：工作站集群(cow)、对称多处理机(smp)、大规模并行处理机(mpp)、 分布共享存储处理机(dsm)、并行向量机(pvp)o是我们讨论的重点。在这一章节，我们将从程序员和算法的角度，着重讨论空间上的并行计算。空间并行计算技术包括 数据并行计算利任务并行计算。数据并行计算

7、是指将一个大的数据分解为多个小的数据，分散到多个处 理单元执行。任务并行是将大的任务分解为小的任务，分散到多个处理单元执行，任务并行同时还要避 免任务車复执行，协调数据的上下文关系，避免冲突发牛。任务并行计算与实际应用需求紧密相关。所 以，任务并行计算要比数据并行计算复杂得多。并行计算与串行计算的最大不同在于，并行计算不仅要 考虑计算本身，还要考虑并行处理模型、网络通信、计算协作诸多问题。3.2主要的并行计算体系类型3.2.1工作站集群(cow cluster of workstation)o工作站集群可以理解为：pc+网络。它可以市少数几台 pc扩展到数t个节点的大规模并行系统，既可以是廉价

8、的并行程序调试环境，也可以成为的高性能计算 平台。集群山于低成本，动态可扩充的特点，已经成为高性能计算平台的主流。目前google搜索和云计 算业务即采用这一方式。我国的联想深腾xxxx、曙光xxxx系列均属此类322称多处理系统(smp symmetric multi processing),它由多个紧耦合多处理器组成，最人特点就是共 享全部资源。3.2.3人规模并行处理系统(mpp massively parallel processing)山许多松耦合处理单元(不是处理器)组 成的。这种结构与smp对立，每个单-元自成体系，包括cpu、内存、硬盘、操作系统，最大特点是不 共享资源。刀片服

9、务器属于此列。3.2.4分布式共享存储多处理(dsm)o它可以视为对smp的可扩充，将共享数据映射到不同的物理位置。 数据的同步由硬件或者软件來完成。是ei渝高性能计算机的主流发展方向之一。3.2.5并行向量机(pvp, parallel vector processor)o pvp使用专用的向量处理器，提供数据共亨，通过高 速交叉开关实现通信。向量运算是一种较简单的并行计算，适用血很广，机器比较容易实现，使用也方 便，因此向量处理机(向量机)在七十年代获得了迅速发展。3.3并行计算的处理模式3.3.1主从模型(ms, master-slave),即有一个主进程，其它是从进程。主进程负责整个系

10、统的控制(包 括任务调度、负载平衡)，从进程负责对数据的处理和计算任务。google搜索业务目前就是采用的这种 编程模型。3.3.2对称处理模型(spm)o这种架构没有主从概念之分，所仃进程的地位都是平等的。在并行执行过程中，我们可以任意选择其中一个进程执行输入输出操作，其它进程扮演同样的角色。3.3.3多程序处理模型（mppm）：在计算机集群中，每台计算机节点执行不同的程序和相同的程序。3.4并行计算设计原则3.4.1适应性。并行算法是并行计算的基础，是为解决实际问题而出现，必须与实际应用相结合。3.4.2可扩展。并行算法是否能够随计算节点增加或减少而同步的线性变化，是评价一个并行算法是否

11、有效的重要标志z。3.4.3粗粒度通常情况下，粒度越人越好。这是因为在每个处理机中有很多需要计算的工作任务，如此 可以充分发挥多处理机的作用。并行加速比对细粒度问题一般情况下是不会很高的，这也是为什么并行 计算需耍求解大规模问题的原因所在。3.4.5减少通信一个高效的并行算法，通信是至关。提高性能的一个关键是减少数据通信量和通信次数。 3.4.6优化性能。评价性能的优缺，主要是看单节点计算的处理能力，和并行执行效率。这与实际采川 的技术息息相关。3.5并行计算设计方法3.5.1分片3.5.1.1数据分片数据分片包括两类：数值分片和哈希分片。数值分片适用丁已知数据范围的分解，如果int、long

12、 类型处理。哈希分片适用于未知数据范围的数据分解，包括字符串，字节数组类型。数据分片是把相同的操作作用于不同的数据，达到提到快速求解的h的。数据分片模型是一种较高 层次的并行计算模型，编程却相对简单。数据分片的并行计算最早应用于并行向量计算机（pvp）。经过 长期实践表明，该技术可以高效地求解大部分的科学和工程计算问题。数据并行处理对象是数值，对应 非数值类问题，则需要其它并行计算模型来解决。google的搜索业务是釆用数据分片的并行计算模式。 3.5.1.2任务分片任务分片的并行计算主要针对非数值类的并行处理。它通常消息传递机制（目前主流是pmi）,各并 行计算执行单元z间通过传递消息来交换

13、数据，协调步伐，执行控制操作。消息传递一般是针对分布节 点内存，也口j以适用于共享内存的并行节点。消息传递模型为程序员提供了更加灵活的控制手段和表现 形式。消息传递模型很容易实现，控制变化手段灵活多样，但是需要程序员有丰富的并行编程经验。是 一种较低层次，编程相对复杂的模型，适用于业务流程的并行化处理。3.5.2通信协调计算过程中的数据共享。通信工作目询主要山tcp/ip协议完成。3.5.3组织组织各任务并发执行，提高性能。在主线程的控制下，子线程在此承拟具体的并发操作任务。3.5.4映射分配任务（分布处理、共享处理）。线程和通信共同完成。3.6并行计算评价指标3.6.1粒度。多处理机单独执行

14、任务大小的度量。3.6.2加速比。串行执行时间为t,使川n个处理机并行执行执行的时间为q,则加速比为：s=t/q （越 大越好）3.6.3效率。若n个处理器的加速比为s,则并行算法的效率是：e=s/n3.6.4性能。求解一个问题的计算量为w,执行时间为t,则性能为f=w/t （越大越好）3.7并行计算注意事项probleminstructionsiiiii 11 卜丄3.7.1任务分解：这是所有并行计算的核心问题，优秀的任务分解需要保证平均和处理负载的平衡，同 吋，随着处理器能力的动态伸缩动态调节3.7.2通信：并发处理离不开网络通信联系。相较与cpu运算，数据在网络间传递延迟是并发处理的瓶

15、颈z。光纤网络是h前最好的选择。3.7.3并行协调：是并行运算过程中控制流程。3.7.4并行冲突：并行冲突来源主要是任务分解和并行协调。3.7.5数据归并：这是数据计算完成后,必不可少的一步操作。数据归并需要注意:过滤重复数据,合 并相关性数据等。3.7.5死锁。死锁是在编程过程中，市于人为的原因造成。死锁表示为：对彖间在不放弃口己资源下互 相调用。请程序员注意。3.8哪些任务不能使川并行计算3.8.1有着严格业务处理流程的计算。如在得到前一任务结果之前，不能进行卞一步操作的处理。3.8.2 web作业，如php, jsp这类脚本编稈mu 11卜丄 iiiii 11 卜丄 iiiii 11 卜

16、丄并行计算示例ibm 360,共享存储多处理器大型主机，使用cisc处理器。上世纪六i年代的代表机型。1976年面世的并行向量机：cray-1,是首次采用risc芯片的机型。从此，向量机牢牢控制住高端计算 帀场。我国的银河系统也属于向量机范畴。google案列可以说，google是十余年來，it界最成功的计算机公司。成功不仅來口于它为大众捉供的及时准确 的免费信息，还有造就它成功的业务模式和技术。下面，我简单介绍一下它的技术实现。4.1 google技术的优秀z处google采用了 pc+linux的解决方案。google集群在存储了海量的网络数据同时，乂保证了捜索业 务的快速、稳定和负载平衡

17、。是低成本、高效能的完美组合，这也是技术业界推崇google模式的主耍原 因。目前google技术已经广泛应用到它的搜索、云计算等诸多领域，并且成为众多开源社区模仿的对彖, 如 nutch, hadoopo4.2奠定google技术成功的三人基石4.2.1 gfs （google file system）gfs是一个基t linux平台的分布式文件管理系统，是google最核心的技术。它实现了海量数据管 理，机器容错，数据容错，负载平衡等多项指标。可以不夸张地说，山于gfs的稳定，保证了 google 的成功。4.2.1 bigtablebigtable是google在2004年，为管理海量数

18、据研发的一个半结构化数据存储模型。它运行在gfs z上，主要特点有：（1）数据以“块”的形式保存在磁盘上，每个块按照用户的要求大小可调，通常是64m-块。（2）存储量极大。在gfs的管理下，可以分布到数千台服务器上。（3）搜索速度快。bigtable是专为搜索而设计的，通过了优化的搜索算法，提高搜索质量。（4）“在多不在精”，通过将大量数据均匀分布多台物理计算机节点上，实现高效的并行计算。4.2.3 mapreduce4.2.3.1 map就町以看做是把一个大块数据分解成多个小块数据的处理。是一个“分”的处理。4.2.3.2 reduce是map返回的数据后，对数据进行的筛选、过滤，合并。可以看作是一个“合”的处理。423.3 mapreduce通常在gfs的控制下，并发到数百台计算机节点上。mapreduce