并行计算中的通信性能研究

并行计算通信性能研究摘要：在基于网络环境的分布式并行计算中，因为一般情况下，局域网的底层通信协议多为以太网协议，而以太网采用的是总线通信和信道竞争两种技术，因此基于网络环境的分布式并行计算中最大的问题可能就是要解决好通信开销的问题。本文研究了一种子任务计算和通信错开的解决方案，从理论上分析该方案的加速比和并行效率等。关键词：分布式并行计算；以太网；信道竞争；并行效率；加速比Abstract：Generallyspeakinginthelowerlayeroflocalnetwork，theprotocolisEthernet，andEthernetisbasedonbustopologyandChannelCompetition.Sothemostimportantproblemfordistributedparallelcomputing,maybetoolargerforcommunicationspending.Inthispaperwestudiedaschemetosolvethisproblem,andgivetheanalysisofthisparallelefficiencyandaccelerateproportion。Keywords：distributedparallelcomputing，Ethernetchannelcompetition，parallelefficiency,accelerateproportion前言并行计算是目前解决大规模计算问题的一种有效方法，利用普通局域网中的计算机可以有效实现并行计算，其最大意义在于能够充分利用网络中大量闲散的CPU，提供的计算能力远远的超过同等的串行计算机;性价比远远高于同等的小型机，而且可以很容易进行扩展。如果运用的恰当，可以获得非常好的效果。在进行并行计算时，各个节点之间的负载平衡，数据传递问题至关重要！并行计算机是由一组处理单元组成的。这组处理单元通过相互之间的通信与协作，以更快的速度共同完成一项大规模的计算任务。因此，并行计算机的两个最主要的组成部分是计算节点和节点间的通信与协作机制。并行计算机体系结构的发展也主要体现在计算节点性能的提高以及节点间通信技术的改进两方面。多处理机并行计算一般由计算和通信两部分组成。根据多处理机并行计算过程对处理机间信息交换的依赖方式的不同可分为同步并行计算和异步并行计算。同步并行计算通常是指并行计算机系统中每一处理器，无论它的计算速度与其它处理器相差多大，也不论它所处理的任务量如何与众不同，都必须等待所有的处理器都到达同一个珊后才能做进一步的工作，这个珊常被称为同步点。而异步并行计算则是指在通常用于等待同步操作的时间内并行计算机系统内每一处理器各自完成自己的有用工作。与同步计算相比，当某处理器等待其它处理器到达某一栅时，异步并行计算提供该处理器有用的计算供其执行。1并行通信机制的发展20世纪80年代中期，加州理工学院成功地将64个i8086/i8087处理器通过超立方体互连结构连结起来。此后，便先后出现了InteliPSC系列、INMOSTransputer系列，IntelParagon以及IBMSP的前身Vulcan等基于消息传递机制的并行计算机。20世纪80年代末到90年代初，共享存储器方式的大规模并行计算机又获得了新的发展。IBM将大量早期RISC微处理器通过蝶形互连网络连结起来。人们开始考虑如何才能在实现共享存储器缓存一致的同时，使系统具有一定的可扩展性。20世纪90年代初期，斯坦福大学提出了DASH计划，它通过维护一个保存有每一缓存块位置信息的目录结构来实现分布式共享存储器的缓存一致性。后来，IEEE在此基础上提出了缓存一致性协议的标准。20世纪90年代至今，主要的几种体系结构开始走向融合。属于数据并行类型的CM-5除大量采用商品化的微处理器以外，也允许用户层的程序传递一些简单的消息。CrayT3D是一台NUMA结构的共享存储型并行计算机，但是它也提供了全局同步机制、消息队列机制，并采取了一些减少消息传递延迟的技术。随着微处理器商品化、网络设备的发展以及MPI/PVM等并行编程标准的发布，集群架构的并行计算机出现开始。IBMSP2系列集群系统就是其中的典型代表。在这些系统中，各个节点采用的都是标准的商品化计算机，它们之间通过高速网络连接起来。2影响通信性能的因素2.1网络带宽低工作站机群系统使用的网络是普通的局域网,而局域网的带宽通常都比较低,如以太网的带宽只有10MB/S。局域网的带宽之所以低,原因主要是局域网是为长距离的数据通信而设计的,由于通信距离较长,限制了通信速度的提高,因为信号的频率越高,它能够传输的距离也越短。另外一个原因是出于价格上的考虑。为了降低网络系统布线所需的成本,大多数是LAN共享一根信号总线进行数据传输,因此这也在很大程度上影响了网络系统的性能,特别是在网络负载较重时,由于各结点都要抢占信号总线,很容易造成通信阻塞,使得实际通信带宽比其最大带宽要小得多。2.2传统TCP/IP协议的多层次结构带来了很大的处理开销TCP/IP协议是面向低速率、高差错和大数据包传输而设计的,它是一个多层次的软件结构,按自底向上的顺序可划分为四层:网络接口层、网间网层、传输层和应用层。由于协议层次多,在进行数据传输时,数据需要经过多次拷贝才能从应用层传递到网络接口或从网络接口传送到应用层,而多次拷贝带来了很大的网络延迟时间。另外,在多层协议的实现中,各层还重复实现了很多相同的功能,比如:·从IP层到传输层都要进行差错控制·从网络接口层到应用层都要进行协议的处理机调度·从IP层到应用层都要进行流量控制·从IP层到应用层都要进行数据包组装和定序的缓冲这些冗余的功能虽然可确保数据的无差错传送,但随着链路传输出错率降低,这种冗余处理反而限制了数据及时提交给应用程序处理。可见,多层次的协议结构是造成通信瓶颈的主要原因之一,合并某些层次,删除冗余的处理,设计一种轻型通信协议,是提高通信性能的重要方法。2.3协议复杂的缓冲管理增加了网络延迟网络协议处理包括很多功能,如流量控制、差错控制、出错重发机制、拥塞控制等,而这些功能的实现都与缓冲管理密切相关。缓冲管理的作用是完成数据的分组和组装,缓冲区可看成一种网络资源,这种资源是有限的,对它的管理很重要。不过通常的缓冲管理机制都比较复杂,例如,采用一种BerkeleyUNIX叫mbufs的结构对协议的数据包进行缓冲管理,但mbufs算法很复杂,开销很大。在DECsta5000上,对单字节消息缓冲管理,需要100微秒,而对512字节数据包需要300微秒,可见缓冲管理带来的网络延迟也很大,如何简化协议复杂的缓冲管理也是通信技术研究的主要内容。2.4操作系统额外开销不可忽视操作系统提供的系统调用和原语是网络协议实现的底层软件支持。在网络协议实现中涉及到上下文切换、调入调出页面、启动I/O设备、中断响应等操作系统处理,有时这些开销可能比协议本身的处理开销还大。比如,在360系统上对一个数据包的协议处理SunTCPIP时间为100微秒,而操作系统的额外开销却高达240微秒,这就造成了通信性能对操作系统一定程度上的依赖。因此,要提高通信系统的性能,降低网络延迟,应当尽量减少网络协议对主机操作系统的服务请求,最大限度地使通信与计算重叠[4]。3异步分布式并行算法异步并行计算相对于同步并行计算会带来一些计算过程的“混乱”，并使计算的收敛性分析复杂化。但是，在基于网络环境的分布式并行计算中，最大的问题可能就是要解决好通信开销的问题。因为所使用的局域网环境，其底层协议大多是基于以太网的，其上为协议。而以太网是一种总线型局域网，它采用的是CSMA（载波侦听多路访问冲突检测）技术。如果采用同步并行计算，强调的是负载均衡，各处理到达同一个珊后才能做进一步的工作：交换信息、评估交换后的信息、进行下一步的计算工作，这样做的一个必然结果是通信相对集中、形成一个“交通瓶颈”、造成待交换信息的堵塞。而异步并行算法，在分布式多处理机系统中，可使计算过程和通信过程重叠成为可能，从而可以运用性能优越的通信和计算错开的方式进行消息传递。因此，设计高效正确的异步并行算法一直是并行处理领域中的主要研究方向之一。异步并行计算的概念已在共享存贮多处理器系统和少量基于消息传递的MIMD系统中成功地用于大型线性方程组问题的求解。与传统的异步并行算法的策略不同的是，该基于分布式网络的算法策略，兼有负载均衡、同时又可以有效地错异步并行SRM开计算和通信的双重优点。应用异步并行算法的思想，采用通信和计算错开的策略。此处，着重对效果从理论上分析[2]。3.1异步分布式并行算法描述通常，将一个大型计算任务，划分为基于计算量近似相同的子计算任务时，通信相对集中，造成信息交换的堵塞。记一个算法的串行实现时间为Ts;同样算法的并行实现总时间为Tp；那么加速比Sp定义为：而Tp可作如下分解：其中,表示各子任务作串行计算的时间的最大值（在该方案中，因为是采用负载基本均衡的分配方法，此处各处理机的Ts基本相同，它近似为Ts/N,N为处理机数量）[3]：TPA表示由于算法并行化过程中额外增加的计算量，如一个依赖于区域边界条件的微分方程求解[7]。进行边界交换信息，修正子域边界条件，并重新计算、整合，逐步逼近精确解。迭代步数取决于区域的划分、边界条件修正的方法等。这种迭代过程便产生了由于并行化而额外增加的计算量TPA。Tpc表示交换边界信息时，产生的通信开销时间。这就是在很多情况下，处理不当就会导致并行不如并行的结果。在现有的有关基于网络的分布并行计算文章中，多数研究者的精力主要集中在“如何减少TPA”上，而忽略了Tpc的存在。在基于网络环境的分布式并行计算实验中，发现是影响并行加速比的一个很重要的因素。在充分分析了以太网协议的基本特征之后，该文提出了一种适用于基于网络环境的分布式并行计算的异步通信算法模型，并以SRM作为算例加以实现，取得了很好的效果。在算法的并行化过程中，为了提高并行计算效率，现在普遍采用的一个措施就是要求任务划分负载均衡，不致于部分理机处于闲置状态。这种思路主要是考虑到减少，如果确实做到了负载绝对均衡，至少从直观上来看，每个处理机都在满负荷工作，肯定比有部分处理机处于闲置状态工作效率高。但是人们在追求负载均衡的时候，却忽略了Tpc的负作用。当各负载均衡性能相似的处理机作分布式网络并行计算时，几乎是同时完成了各子任务的计算，等待边界信息的交换。而基于以太网的局域网是总线结构，也就是说在同一时间，只允许一个信号在信道上传输，当所有处理机同时要求交换信息时，结果是谁都不能通信，按CSMA技术原则，只有等待一个随机的时间之后再去竞争信道。这种冲突和竞争，将会使Tpc成为影响Tp的一个极重要的因素。而在通信完成之后，每台处理机执行自己的计算时间，信道处于空闲。异步分布式并行计算方法，其实质是在保证负载均衡的前提下，有效地错开通信时间。它既可以保证系统负载均衡，又可以充分利用传输信道资源，解决好信道“冲突-竞争-空闲的问题。可用如下的示意图表示两不种情况下的解决方案。在方案2中，通信和计算是异步进行的。在同一时间内，在没有局域网上其它主机参与信道竞争的情况下，只有两台主机参与通信，线路畅通、效率极高，而其它计算机可以执行独立的计算子任务。理论分析和实验均表明，以上方案将分布式并行中通信开销时间降到了最低限度[1]。3.2加速比及并行效率分析理想状态，也即无通信开销的状态，在分布式并行计算情况下实际上是不存在的。为了模拟此环境，假定算法并行化时，各处理机均利用固定的虚拟边界条件进行计算。即不进行边界交换，只做独立的并行计算。此处，给出理想状态下的理论分析。在理想状态下，SRM算法的加速比、并行效率分别为：假设求解区域划分为N*N个网格，在一台处理机作串行计算时，其计算量近似为：N*N*a，其中a为每个结点所需要的计算量。当使用P台处理机作并行计算时，如图5所示，从水平方P个子域，每个子域内包含有(N/P+1)*N个结点，从而计算量为(N/P+1)*N*a；可得理想状态下，其加速比理论值为：由上式，可得并行效率为：3.3异步分布式并行SRM算法的加速比及并行效率异步分布式并行算法考虑到了通信量，但按前面所提的思路，尽量错开通信时间，可使通信开销降到最低限度。异步分布式并行算法的加速比、并行效率分别为：假设求解区域划分为N*N个网格，在一台处理机作串行计算时，其计算量近似为：N*N*a；其中a为每个结点所需要的计算量。当使用P台处理机作并行计算时，如图5所示，从水平方向划分为P个子域，每个子域内包含有（N/P+1）*N个结点，而计算量为由于通信交换信息的过程是异步进行的，基本上消除了信中的等待和冲突。当P->∞时，异步分布式并行SRM算法的加速比、并行效率分别为：其中，表示边界上重复的计算量，一般为O（N）,Tpc为边界上交换信息的通信时间。由此不难看出，随着处理机的增加，各处理机的子计算任务迅速减少，计算时间变小，而通信相应频繁，从而又出现了处理机花大量的时间在等待通信。此处要强调的是等待通信，因为采用异步通信技术，使得没有冲突存在。但不管怎样，Tpc是变大了（用于等待）。4提高并行效率的方法