并行化程序设计-盘古文库

并行化程序设计

资料大全

来源：盘古文库

作者：火烈鸟

2025-09-15

并行化程序设计（精选7篇）

并行化程序设计第1篇

关键词：全局比对,局部比对,渐近式算法,共享内存多处理机

0 引言

多序列比对是分子生物学中重要的分析工具。它可用于探测新序列与已知序列家族的同源性,预测新序列的二级和三级结构,蛋白质家族中结构或功能的相似片断。随着测序的自动化使得新序列以指数级别增长,人们对快速高效的多序列比对算法的需求越来越迫切。目前已产生了几种多序列比对软件,如MSA,PRALINE,MAFFT,ClustalW[1],T-Coffee[2]等,这些算法的时间复杂度都非常高。其中,T-Coffee是新产生的一种方法,与前几种方法相比,它综合了全局和局部比对及位置信息,提高了准确率和敏感性,但同时也增加了它的时间复杂度。

缓存和并行化的策略通常可以降低这些算法的时间复杂度,提高计算吞吐量。ClustalW目前已产生了多种并行化版本,如SGI的ClustalW商业版本,基于PC集群的pClustalW[3],基于消息通信的ClustalW-MPI[8],这些算法都在不同环境下、不同程度上提高了ClustalW的效率,而T-Coffee目前还未实现并行化。

本文提出了基于SMP的T-Coffee并行化算法,它将T-Coffee按功能分成四个阶段,分别实施并行化策略,这样大大降低了T-Coffee的时间复杂度。它可以用于服务器上执行,以提供高效快速的多序列比对服务。

1 T-Coffee串行算法

T-Coffee是一种新的准确率高的多序列比对算法,由Jaap Heringa等四人于2000年提出。传统的多序列比对通常由序列两两比对产生距离矩阵、生成系统发育树、渐近算法的全局比对三部分组成。而T-Coffee综合了全局和局部比对信息,并增加了序列的位置信息,提高了多序列比对的敏感性和准确率。其流程如图1所示。

生成基本比对信息库分别对输入序列进行两两全局和局部比对,从而形成全局比对信息库和局部比对信息库,然后对这两个库进行组合,产生一个基本比对信息库,作为下一步的输入。这一步复杂度为O(N2L2),N是输入序列条数,L是序列的平均长度。

扩展信息库增加基本库中每两两比对信息的价值,也就是获得比对在全局中的“地位”,“位置信息”。采用启发式算法通过每个两两比对与其他所有序列的信息比较得到,其结果可直接用于多序列比对,其复杂度为O(N3L)。

生成指导树根据第二步形成的扩展信息库,使用近邻归并法生成指导树,来表示序列之间的距离,位于相同分支上的序列距离更近,复杂度为O(N3)。

渐近式多比对根据上步生成的指导树,进行多序列比对,复杂度为O(NL2)。

由此可得T-Coffee总的复杂度是:O(N2L2)+ O(N3L)+ O(N3)+O(NL2)。与ClustalW相比,T-Coffee不仅要进行全局两两比对,而且要进行两两局部比对,然后加权综合这两部分的信息,这一步的复杂度比ClustalW要高出一倍多。在第二步要加入序列的位置信息,即扩展库,而ClustalW没有这一步。第三步和第四步与ClustalW相同。

由此也可以看出,对T-Coffee并行化提高其效率的必要性。

2 T-Coffee的并行化设计

对T-Coffee算法进一步分析知,各个步骤产生的数据不相关,也就是说各个阶段可以独立执行,因此可以按功能分成四个部分,分别为:通过两两比对生成基本信息库,扩展基本信息库,根据扩展库生成指导树,渐近式全序列比对,为了引用方便分别命名为GeneratePrimaryLib(),ExtendedLib(),GenerateGuideTree(),ProgressiveAlign()。流程图如图2所示。

在GeneratePrimaryLib()阶段(见图2右),将有N(N-1)/2次两两的全局和局部序列比对,这一步的时间复杂度为O(N4)。由于每个两两比对与其他的数据不相关,所以很容易实现并行化操作,其伪代码如下:

GeneratePrimaryLib()

{

for (i=Istart;i<Iend;i++)

{

for(j=i+1;j<Jend;j++)

Result1=ClutalWAlign (i ,j);

Result2=LocalAlign(i ,j);

Result=Combine(Result1 ,Result2);

}

Return Result;

}

由于j-loop循环大小可变,我们采用OpenMP[6]的“dynamic”机制避免数据在各个处理器上的分配不平衡问题[7],理论上,“static”机制此处可用,但是各个比对所用的处理时间不同,所以此处采用“dynamic”机制。尽管作了这样的优化,它最终还受限于处理器的数目。为了达到更快的速度,必须在指导树生成和渐近式比对采取并行优化来处理。

在ExtendedLib()阶段与GeneratePrimaryLib()阶段的问题是相似的,此处要计算的不是两两比对,而是两两比对与其他任一序列形成的三元组比较,所以我们采用了相同的并行化的策略实现。

在ProgressiveAlign()阶段,串行算法在一个循环内直接调用Score(i,j),虽然循环本身不能被并行化,但是我们可以采用并行策略预先计算出Score(i,j)的数值。因此需要动态分配一新矩阵score_matrix[i,j],它会在一个并行体中计算,如下所示:

ProgressiveAlign(){

score_matrix=(int**) ckalloc((Iend-Istart)*sizeof (int*));

for(i=Istart;i<Iend;i++)

score_matrix[i]=(int*) ckalloc ((Jend-Jstart)*sizeof (int*));

{

for (i=Istart; i<Iend; i++)

for (j=Jstart; j<Jend; j++)

score_matrix[i,j]=score(i,j);

}

for(i=Istart;i<Iend;i++) {

for(j=Jstart;j<Jend;j++) {

hh=s + score_matrix[i,j];

}}}

可以看出,这是一个递归调用的循环体,和前面的循环不同,并行将多次进入该循环体。所以这个循环更适合采用OpenMP的“static”模式实现并行,以降低OpenMP的负载。

以上分别介绍了各个阶段的实现细节,主程序的执行过程如下:

当程序第一次运行时,主结点调用GeneratePrimaryLib()为从结点分配任务,在不同的处理机上执行序列的全局和局部比对。当GeneratePrimaryLib()执行完成以后,主结点调用ExtendedLib()执行,依次执行到ProgressiveAlign()产生最终的结果。

3 实验结果

我们用C语言和OpenMP[6]模型实现了T-Coffee的并行化,使其能够在共享内存(SMP)的多处理机上执行,然后在银河III上进行了测试。

实验进行了以下两项测试:(1)并行墙钟时间(parallel wall clock time[8]),即在并行机上执行时,第一个节点开始,到最后一个结点产生结果这段时间,其中包括读取数据和写结果。(2)相对加速比(relative speedup),即串行时间与并行执行时间的比值。

实验所用的序列从NCBI下载。在第一次测试中,分别使用了20,50,80条平均长度为200的核苷酸序列,结果如表1所示。当在4个处理器中执行时,其加速比依次为3.55,3.07,2.54;当处理器增至16个时,加速比为9.73,8.00,4.11。可见,加速比与处理器的数目成比例关系,处理器增加,加速比也会变大。随着序列条数增加,序列比对部分在总时间中占的比例越来越大,使得加速比有所下降。

注:序列的平均长度为200,P表示处理器数目,Time为执行时间,Speed-up为加速比。

第二次对算法的吞吐量进行了测试。分别使用了100条和600条平均长度同样为200的两种测试集,结果如下图3所示,在处理器数目为2,4个时,它们之间的加速比相差不大,但是随着处理器结点的增多,600条的序列比100条的序列加速比明显变大,这就表明了我们修改后的算法更适合处理大数据,具有高吞吐量的性质,这也正是并行化要达到的效果。

4 结论

本文提出并实现了基于共享内存多处理机系统(SMP)的T-Coffee并行算法,与串行算法相比,它明显改善了性能。在我们的算法中,将T-Coffee的四个阶段:生成基本库,扩展库,产生指导树和渐近比充分并行化,使其都能够在并行机上执行。实验结果表明,该算法明显减少了执行的墙钟时间,得到较高的相对加速比。

参考文献

[1]Clustal w.improving the sensitivity of progressive multiple sequence a-lignment through sequence weighting,positions-specific gap penalties and weight matrix choice,Nucleic Acids Research,1994,22(22):4673-4680.

[2]TCoffee.Anovel method for fast and accurate multiple sequence align-ment.IDEAL J Mol Biol,2000,302:205-217.

[3]Parallel clustal w for pc clusters.Proceedings of International Confer-ence on Computational Science and Its Applications(ICCSA),2003,2668:300-309.

[4]Dialign p.Fast pair-wise and multiple sequence alignment using paral-lel processors.BMC Bioinformatics2004,2004,5(128).

[5] Improving performance of multiple sequence alignment analysis in multi-client environments.Proceedings of the First IEEE Int.Workshop on High Performance Computational Biology (HiCOMB 2002,IPDPS 2002),2002.

[6] http://www.openmp.org.

[7]Performance optimization of clustal w:Parallel clustal w,ht clustal,multiclustal.http://www.sgi.com/industries/sciences/chembio/re-sources/papers/Clustal DevNews/Clustal DevNews.html.

并行化程序设计第2篇

随机数产生器是用来产生随机数的装置[1],一般分为真随机数产生器和伪随机数产生器。真随机数通过物理实验或自然噪音等方式产生,成本高; 伪随机数通过若干种子利用数学算法递推产生周期性的随机数序列,不需要外部物理硬件的支持,并且具有类似于真随机数的统计特征; 因此,在科学研究和工程模拟领域主要应用伪随机数产生器。相对于现在普遍应用的伪随机数产生器LCG ( Linear Congruential Generator )[2],MRG32k3a[3,4,5]具有长周期、随机数序列质量优异的特点,但较慢地产生速率制约了它的应用。

随着计算机系统结构和计算机网络技术的快速发展,科学研究和工程模拟对随机数产生器的性能及速率要求也日益增长,研究随机数产生器并行化是迫切的、必然的。并行计算技术迅速发展[6],将其应用于随机数产生器,成为提高随机数产生器产生效率的方法之一。目前国内外已经做了一些随机数产生器的并行技术的研究,并行方法总体分为两种,第一种是每个线程独自应用不同类别的随机数产生器,第二种是将一个随机数产生器并行化到每一个线程中。第一种方法易于并行化,2000年Michael Mascagni等研发出了基于第一种方法的并行化随机数产生器库SPRNG( Scalable Parallel Random Number Generators Library) ,每个线程所使用的产生器都不相同[7]; 后来Shuang Gao等在此基础上研发出基于统一计算设备架构CUDA( Compute Unified Device Architecture) 平台的并行化随机数产生器库GASPRNG( GPU accelerated scalable parallel random number generator library)[8]; Kinga Marton等于2011 年提出的一种并行化随机数产生器,各线程混合使用了不同类型的随机数产生器[9]。第二种并行化方法则较难实现,优点是能保持随机数产生器的原始序列。2011 年,Thomas Bradley等将第二种并行化方法总结为Simple skip ahead、Strided skip ahead和Hybrid三类,并且描述了基于GPU的MRG32k3a、Sobol和MT19937 三种随机数产生器的并行化算法及性能分析[10]。L’Ecuyer等人2001 年也早以概述了MRG类随机数产生器的并行化的理论过程,但没有验证并行化后的结果正确性和运行效果[11]。

目前随机数产生器的并行化研究工作主要集中于多核中央处理器CPU平台,缺少基于Intel最新产品MIC平台[12]并行化的相关理论依据和性能分析。另外,以上文献均没有详细阐述MRG32k3a并行化的具体使用方法、并行化实施方案及并行化结果分析。本文利用“分而治之”思想实现MRG32k3a并行化,设计了一种简单的并行化规则,并确定了相应的参数,实现了按周期“分而治之”并行产生随机数的算法,更主要的工作是基于MIC进行了MRG32k3a并行化后的性能测试分析,检验其可行性和优越性。文献[10]中Thomas Bradley总结的Simple skip ahead方法实质上就是 “分而治之”思想在随机数产生器应用上的体现,在一个周期内划分线程和分配任务,每个线程独立产生一段周期内的连续的随机数子序列。

本文主要研究工作分为以下三个阶段: 1) 理论研究MRG32k3a的串行与并行算法,确定最有效的并行化方案,进行理论加速比和可扩展性分析; 2) 在Intel Xeon E5-2680 上进行了MRG32k3a串行和并行的大量开发与测试,其中选用最为完备的均匀随机数产生器测试库Test U01 进行随机数序列性能测试[13,14],借助Test U01 检测保证了并行化过程的正确性,最终MRG32k3a串行及并行算法均能完全通过Test U01 测试,同时完成相应时间测试和加速比分析; 3) 移植到MIC平台,通过测试挑选出最优的Intel编译选项,然后完成时间测试和性能分析。实验数据显示MRG32k3a并行化后的加速比和并行效率理想,MIC相对CPU单线程的最佳加速比为17. 73。

1 MRG32k3a串行算法及并行化方法

1. 1 MRG32k3a串行算法

组合多重递归随机数产生器[3,4]CMRG( Combined Multiple Recursive Generator) 递推公式为:

为兼顾速度和长周期性,j = 2、k = 3 时比较理想[5]。MRG32k3a属于此种类型的CMRG,递推公式为:

其中n ≥ 3,a1,2= 1 403 580,a1,3= - 810 728,a2,1= 527 612,a2,3=-1 370 589,m1=232-209,m2=232-22 853。

产生[0,1) 之间的均匀随机数un。

周期p = ( m13- 1) ( m23- 1) /2 ≈ 2191

1. 2 MRG32k3a并行化算法设计

MRG32k3a产生的随机数序列之间存在相互依赖关系,最大维度只有45[11],采用分治法可以避免维度约束。每个线程跳到随机数序列特定位置后连续产生随机数,意思是说把原始随机数序列分割为V段,每个子序列都是原始序列的连续子序列,这些特定位置是每个线程初始值。本文将阐述MRG32k3a利用分治法并行化的具体实现过程。

设随机数序列每个状态为向量对形式:

MRG32k3a递推公式则转化为:

状态向量组Xi,n + w可以直接由Xi,n计算:

令p是MRG32k3a的周期,T为转换函数,则T( Xn) =Xn +1,T( Xp) = X。整个周期的随机数序列划分成V = 2v个长度为W = 2w的随机数子序列,其中v + w = 191。X0是随机数序列的初始状态,每个随机数子序列的初始状态定义为:

本文选取w = 127,v = 64,即最多运行V = 264个线程,各线程最多产生W = 2127个随机数序列,图1 为相应的并行化原理图。

如图1 所示,MRG32k3a并行化的关键点是计算每个线程的初始状态Cg。其中,三个参量乘积的模运算[1]定义为:

利用分治算法计算Aiw,时间复杂度降为O( logw)[10],具体过程如下:

本文实现过程中提前编写程序计算出了A1(2127)、A2(2127),并行化时直接调用获得相应线程的初始状态,减少了一定量的矩阵乘运算,节省运行时间。

MRG32k3a并行化的具体算法描述如算法1:

算法1 MRG32k3a并行化算法

输入:种子seed[6],线程数thread_num,任务量random_num

输出:random_num个随机数u

MRG32k3a串行算法产生n个随机数序列,所需时间与n大小成正比,因此时间复杂度为O( n) 或线性时间,它的并行算法在g个线程情况下时间复杂度为O( n/g) ,所以其绝对加速比为O( g) ,有效利用了线程数量,加速比随着线程数增加而线性增长。MRG32k3a串行算法的任务量与产生的随机数总量random_num成正比,同时MRG32k3a的并行算法是将总任务量平均分配给g个线程,理想情况下,并行算法的加速比接近于线程数。而当任务量较少时,一定的通信开销会额外消耗时间,比如分配线程、访问共享变量、内存间转换等操作,相应的加速比会下降,而任务量逐渐增加后,通信开销所占比例越来越小,逐渐呈现出线性加速。

可扩展性是指在确定的应用背景下,计算机系统( 或算法)性能随线程数增加而按比例提高的能力。但目前仍无一个公认的、标准的和被普遍接受的严格定义标准,本文采用等加速标准进行MRG32k3a并行算法的可扩展性分析。假定g个线程产生任务量为W的随机数所需时间为t,并行算法的平均速度为,则:。按照等加速定义,对于某个并行算法,若增大一定任务量能维持整个并行过程的平均速度不变,则称该计算是可扩展的。其中平均速度为常数,意指速度与线程数呈线性比例增长,意即加速比为线性或近似线性[6]。MRG32k3a产生随机数的任务量较大时,理论加速比接近线性加速。当W、为常数,产生随机数的时间t与线程数g成反比; 当g、为常数,产生随机数的时间t与任务量W成正比。因此产生随机数任务量较大时,接近线性加速,MRG32k3a的并行算法具有一定可扩展性。

1. 3 基于MIC并行算法实现

Intel推出的基于集成众核MIC架构的至强融核系列产品是为了解决高度并行计算问题。它基于x86 架构,支持Open MP、p Thread等并行编程模型。英特尔MIC架构具有更小的内核和更多的硬件线程,以及更宽的矢量单元,是提高整体性能、满足高度并行化应用需求的理想之选[12]。

并行程序执行时,多线程之间相互通信会使程序运行变得复杂,选择合适的并行粒度才能最大限度地提高并行的效率。MRG32k3a并行化属于细粒度并行,每线程单独产生一段连续随机数子序列,并发度高、占用资源较少、代码较短、各线程间数据交换少,适合移植到MIC上运行。

本文基于MIC的MRG3ak3a并行化实现分为三个步骤: 首先,将串行程序使用Open MP并行化,通过Test U01 测试其随机数序列的准确性; 再次,测试CPU上并行版本的性能,如果加速比不能随着核数增加而线性增长,则需要对程序进行优化,使之发挥出多核的威力; 最后,移植到MIC上进行编译选项筛选,Intel的各种优化编译选项在不同程度上会提升运行效率,为最大发挥MIC性能,要选择出最适合MRG32k3a并行程序运行的编译选项,接着完成MIC上的性能测试。

2 实验数据及性能分析

2. 1 Test U01 测试分析

为保证并行化结果的正确性,本文选用均匀随机数统计检测库Test U01 进行随机数性能测试。Test U01 相比Diehard,NIST等统计检测库,其检测最为严格,涉及216 种、455 个统计检测。综合Small Crush、Crush、Big Crush的三大类测试结果,说明了MRG32k3a串行与并行程序能够全部通过Test U01 测试。串行版本与4 线程并行版本的Test U01 测试的P-value统计分布情况,如图2 所示。图2 中串行版本P-value落在区间( 0. 08,0. 92) 之间比例为88. 56% ,4 线程并行版本P-value落在该区间的比例为87. 24% ,通过的检测比例基本相同。对串行和并行程序的测试数据进行了双样本柯尔莫诺夫-斯米尔诺夫KS( Kolmogorov-Smirnov) 统计测试,P-value为0. 6517,进一步说明它们测试数据近似服从相同分布。

2. 2 基于CPU的并行化性能测试

实验环境: 搭建的CPU平台为两个8 核处理器Intel Xeon E5-2680 @ 2. 7 GHz。

实验数据及分析: 为更好地评估MRG32k3a程序的并行化成果,首先基于CPU进行了基准测试,在1、2、4、8、16 线程情况下产生不同数量随机数的时间测试结果如表1 所示。其中产生同等数量随机数的条件下,若线程数成倍增加,测试时间则成倍缩短; 同等线程数条件下,若产生随机数的数量成倍增加,测试时间也成倍增长; 而且一定情况下,产生随机数量越多其可扩展性越好。图3 表示相应线程下的加速比,横轴为线程数,纵轴为加速比,基于CPU的MRG32k3a并行化加速比与线程数呈线性增长,此时具有一定扩展性,16 线程时达到12. 1609倍的加速比,而且在2、4、8 线程时并行化效率接近100% ,因此MRG32k3a并行程序可以移植到MIC。

2. 3 基于MIC的并行化性能测试

实验环境: 本文MIC平台使用的是单个MIC卡Intel Xeon Phi 3110P 57cores @ 1. 10 GHz,它含有57 个x86 架构指令集的核心,每个物理核心带有4 线程。

筛选优化选项: 首先在224 线程产生1010个随机数情况下,依次添加不同编译选项进行时间测试,测试结果如表2 所示,图4 为相应的加速比。

如图4 所示,基于MIC并行化添加编译选项- O3、- noprec-div 、- fimf-domain-exclusion时加速比有所上升,优化效果比较明显。其中- O3 表明选用最高的优化级别“3”,- no-precdiv指使用乘倒数替代除法来简化运算,- fimf-domain-exclusion指排除与算法无关的浮点运算,减少非正常浮点操作对性能的影响。

实验数据及分析: 筛选出合适的编译选项后,基于MIC平台实现1、2、4、8、16、32、56、112、168、224 线程产生不同数量随机数序列的时间测试,测试结果如表3 所示,图5 为相应线程下的加速比。

如图5 所示,基于MIC的MRG32k3a并行化加速比效果也非常明显,最大达到216. 2105,部分线程的并行效率超过了100% 。当产生随机数越多时,提升效率越明显。另外,在MIC卡上设置的线程数并不是越多越好,线程数太多,开销会比较大。因此要设置合适的线程数以确保MIC核的高利用率,比如图5 中基于MIC产生107个随机数时在56 线程左右的效率最好,多于56 线程时加速比出现下滑趋势。当产生随机数数量不断增加,如产生1010数量的随机数,加速比逐渐呈线性状态,此时基于MIC也具有一定可扩展性。

由于C ++ 语言标准库Boost、随机数产生器库SPRNG中没有随机数产生器MRG32k3a,本文选取了英特尔数学核心函数库Intel MKL( Intel Math Kernel Library) 中MRG32k3a的并行化结果进行性能对比。如表4 所示,测试数据来自文献[10],平台为Intel Xeon E5410,pts/s指每秒可产生的随机数的数量,本文中基于MIC实现MRG32k3a并行化的最优情况下每秒大约产生8. 25E + 08 个随机数,而Intel MKL基于Intel Xeon E5410平台4 线程情况下每秒大约也只能产生1. 04E + 08 个随机数。另外,对比表1 中基于两个8 核CPU产生随机数的时间,单个MIC卡相对CPU单线程的最佳加速比为17. 73,说明基于MIC实现MRG32k3a并行化具有一定优越性,虽然MIC单核的计算能力弱于同期的CPU,但利用众核并行的优势,加速比依然理想。

3 结语

线性整数规划分支定界法并行化研究第3篇

在线性规划问题中,有些最优解可能是分数或小数,但对于某些具体问题,常常会遇到一些变量的解必须是整数。例如,变化量表示的是机器的台数,工作的人数或装货的车数等。为了满足整数解的需求,一般来说只要化整已经得到了的非整数解。但是事实上化整也不一定能得到可行解和最优解,因此需要有特定的方法来求解整数规划[1]。

上个世纪60年代Land Doig和Dakin等人提出了可以求解整数或者是混合整数线性规划问题的分支定界算法。

该算法的思想是把有约束条件的最优化问题所拥有的所有可行的解空间进行搜索。具体执行算法时,会不断地分割所有可行的解空间成为越来越小的子集,然后将每个分割出的子集里面的目标函数值计算一个下界或上界。在每次分支之后,对所有界限超过了已知的可行解的值的那些子集不再分支。这样就可以去掉许多的子集,因此缩小了搜索的范围。重复这一过程一直到找出可行解的值不大于任何子集界限的可行解的位置。所以这个算法一般可以求得最优解[1]。

要将分支定界算法由串行计算转换为并行计算,难点在于要解决对二叉树的每个左右分支都实施并行计算所面临的计算数据组织、通信处理问题[2]。

接下来以下例来阐述分支定界法解线性整数规划的步骤。

具体解题步骤如图1:

由此可知,分支定界就是根据现有解不断将问题化为子问题,并更新上下界,直到求得我们需要的答案的过程。

2 在matlab中并行化的实现

2.1 Matlab并行计算的基本概念

Matlab依赖以下两个工具来实现并行计算架构:Matlab并行计算工具箱和分布式程序。用户使用Matlab提供的并行计算工具可以更加专注于并行计算算法的设计,很大程度上减少了用户用于解决网络通信等问题上投入的工作和精力[3]。

Matlab并行计算可以分为两类问题:第一类是distributed任务,各个作业之间完全独立,不需要进行数据通信,各个作业可以异步执行;第二类是parallel任务,任务的各个作业之间需要进行数据通信,必须同步执行[4]。

进行并行计算时,工作单元有job、task、client、worker。其中client相当于计算机的界面,负责完成几乎所有的用户交互操作;job负责管理worker和分配task,每一个job包含多个task,每个task都要通过job分配给worker执行,并将执行结果返回[5]。client、job、worker运行在同一台或者是多台网络上的计算机上。

程序执行时,task是Matlab处理待完成的并行计算的基本单元,每个任务都是由一个或者是多个task组成的。由用户编写并行程序来创建和划分job和task来完成待解决的并行计算任务。

开发Matlab并行程序首先要采用串行方法运行程序;然后选择合适的并行方法,采用Matlab并行结构或者创建通用的并行计算程序;之后再控制数据和任务分配;然后采用pmode调试并行功能;配置local,在本地多核计算机执行并行任务[6]。

2.2 Matlab中的并行计算支持

为了支持并行计算,Matlab为开发者提供了许多的并行结构,这些结构中包括了Parfor循环结构,SPMD并行结构,分布式阵列,分布式数值处理算法和消息传递函数等。本文采用的是Parfor循环结构来实现分支定界法解线性规划问题的并行化。

由for关键字表示的循环可以通过使用parfor关键字代替进行并行。Matlab执行代码过程中,如果循环体使用的是for关键字,则采用串行方式执行;如果循环体使用的是parfor关键字,则采用并行方式执行。

在使用parfor关键字代替for关键字并行执行循环时,会将循环分为很多部分,每个部分交给不同的worker执行。因此对于执行效率来说,假设使用的worker的数量为n,循环次数为m,则m如果能被n整除的话,则将循环均匀划分;如果不能被整除的话,则将循环非均匀划分,其中某些worker会执行较多的循环次数。

默认情况matlab启动时只有一个进程,因此默认情况下执行parfor关键字标志的循环时是串行执行的。因此在执行前必须先打开Matlab并行计算池。

Matlab并行计算池管理很多个worker,每个worker都可以执行分配的并行计算任务,其对应的物理单元即处理器或处理器核。

Parfor循环将for循环分解为子循环,分解后得到的子循环由不同的处理单元处理,用此来减少整个循环执行所需要的时间,提高计算效率。而在使用Parfor循环代替for循环之前一定要先使用matlabpool命令启动所需要的处理单元,然后将循环体中的for关键字修改为parfor关键字,通过Matlab的程序解释器将此循环交由matlabpool启动的多个处理单元完成[7]。

3 用matlab实现分支定界法解线性规划并行化

解决线性规划问题时,分支定界法是一项相当重要的方法。因此,研究该算法的并行化对于提高解决线性规划问题而言是特别有意义的。

在使用分支定界法时,最重要的就是分支和剪枝。并且耗时最长循环最多的地方也是这里,因此我们选择将这一部分并行处理。

下面给出用Matlab编写的分支定界法并行化的程序ILpt.m。

我们仍然用开头所用的例子来进行测试,比较使用了并行和未并行的情况下计算出结果分别所使用的时间。

因为使用了matlab所提供的计算线性规划的函数linprog,因此我们需要将求解最大值问题转换为求解最小值问题。只需要将函数加负号就能解决,而且这并不影响我们的测试[8]。

对于开头所用的例子:

解:调用ILpt.m函数

>>[x,f]=ILp(c,a,b,[],[],[0;0],[inf;inf])

>>c=[-40,-90];a=[9,7;7,20];b=[56;70];

用matlab提供的时间函数来记录程序运行的时间,分别记录开启并行时和未开启时分别的运行速度来进行比较。

测试使用的是一台四核计算机,理论来说的话上可以将计算速度提高四倍,然而实际效果却达不到这个效果。这是由于该算法对二叉树的每个左右分支实施并行计算及并行计算数据组织、通信与处理时对算法运行效率影响较高,因此达不到理想效果。但是从测试结果来看,并行化后的程序的确大大提升了运行效率。

以上数据是将同样的算例计算一百次所求得的均值。

参考文献

[1]孙小玲,李端.整数规划新进展[J].运筹学学报,2014,18(1):40-65.

[2]Jack Dongarra.并行计算综论[M].北京:电子工业出版社,2005

[3]胡良剑,孙晓君.Matlab数学实验[M].北京:高等教育出版社,2006.

[4]陈国良.并行算法实践[M].北京:高等教育出版社,2004.

[5]楼顺天.Matlab程序设计语言[M].西安:西安电子科技大学出版社,1997.

[6]陈国良.并行算法实践[M].北京:高等教育出版社,2004.

[7]刘维.实战Matlab并行程序设计[M].北京:北京航空航天大学出版社,2012.

并行化程序设计第4篇

分类问题在神经网络的研究与应用中是一个热点问题, 很多学者[1,2]将BP神经网络与Ada Boost算法相结合, 并有效地运用在不同领域, 实现对输入数据的强分类。然而, 随着计算机和信息技术的进步, 数据呈指数式飞速增长。在面对海量数据时, 时间和空间的复杂性已成为传统的BP-Ada Boost算法的瓶颈。由于传统的BP-Ada Boost算法在提升算法性能的同时也具有较高的时间复杂度, 在处理大输入数据量时, 容易出现算法执行时间过长, 计算机内存不足, 甚至程序无响应等状况, 无法有效地完成计算任务。如何实现高效的海量数据处理, 这是一个亟待解决的问题。

云计算是一种分布式、并行的系统, 由虚拟化的计算资源构成, 可以根据服务提供者和用户事先商定好的服务等级协议动态地提供服务, 是网格计算、分布式计算和并行计算的发展[3]。它把存储于各分布设备上的资源联合起来协同工作, 可实现对海量数据的高效并行处理。本文将云计算与传统的BP-AdaBoost算法相结合, 通过将BP-Ada Boost算法的MapReduce并行化, 将计算任务分配给多台计算机并行处理, 来实现分布式运算的效果, 不仅使得BP-Ada Boost算法处理庞大数据量成为可能, 而且在保证算法准确度的基础上提高了算法的运行效率。

1 相关原理

1.1 BP-Ada Boost算法

如何最优地构造和训练一个神经网络, 保证神经网络的泛化能力, 传统的方法取决于使用者的经验和不断的试凑。1990年, Hansen和Salamon[4]证明:通过训练多个神经网络并将其集输出, 会显著地提高神经网络的泛化能力。针对PAC学习理论下的弱学习算法如何提升为一个强学习算法的问题, Freund和Schapire[5]提出的Ada Boost算法, 可以显著提高学习算法的性能, 通过反复搜索特征空间, 获取各学习样本的权重分布, 提供相等的初始化分布权值, 并在训练过程中不断调整样本的权重:预测精度低的样本权重得到加强, 预测精度高的样本权重则被减弱。最后, 使用线性组合的方法将它们合并成为一个强分类器[6]。由于Ada Boost算法不要求事先知道弱学习算法预测精度的下限, 而非常适用于实际问题中[7]。BP-Ada Boost算法将BP神经网络与Ada Boost算法有效结合, 使用BP神经网络作为弱分类器, 反复训练BP神经网络预测样本输出, 通过Ada Boost算法得到多个BP神经网络弱分类器组成的强分类器。

BP-Ada Boost算法具体执行流程如下:

(1) 对于给定的m个学习样本, 初始化权值:D1 (i) =1/m;i=1, 2, …, m;

(2) DO FOR t=1, 2, …, T (T为训练的轮数, 即弱分类器的个数) :

(1) 利用样本权重Dt训练弱分类器 (在此即为BP神经网络) ;

(2) 获取弱分类器的预测函数gt:X→Y, 并计算gt的预测误差式中, gt (xi) 为预测分类结果, yi为期望分类结果;

(3) 计算预测序列权重:

(4) 权重调整:

式中, Bt是归一化因子, 目的是在权重比例不变的情况下使分布权值和为1;

(3) 输出强分类函数。循环结束后, 训练T轮得到T组若分类函数f (gt, αt) , 组合得到强分类函数H (x) 。

1.2 MapReduce编程模型

MapReduce是一个用以进行大数据量计算的编程模型, 同时也是一种高效的任务调度模型[8], 计算的两个重要阶段“Map”和“Reduce”是从函数式编程语言List里借鉴而来的[9]。其思想是将大数据集分解为若干个小数据集split, 每个split分别由集群中的空闲节点来实现调度和执行Map计算任务并产生大量的中间结果。Map阶段结束后, 大量节点会根据指令来执行Reduce阶段, 即对Map阶段产生的中间数据进行遍历、排序与适当的合并, 并产生最终的输出文件。MapReduce编程模型将计算表达为对数据键/值对集合进行串行化分布式操作, Map与Reduce分别实现了对数据集的“分割”与“合并”, 先将分割成的小数据片段分配给各台计算机处理, 再综合所有处理结果进行最终输出, 从而实现了分布式运算的效果。MapReduce的执行过程如图1所示。

2 BP-Ada Boost算法的改进与特点分析

2.1 BP-Ada Boost的MapReduce并行化

BP-Ada Boost是一种迭代算法[10], 其串行实现算法的时间复杂度较高。实现MapReduce编程模型的重点在于将学习算法进行MapReduce化, 用户编程实现Map和Reduce两个核心函数, 按一定的映射规则将输入的<key, value>对转换成另一个或一批<key, value>对输出。

BP-Ada Boost算法进行MapReduce化的基本思路是:对串行算法中每1次迭代启动对应的1次MapReduce计算过程, 在这一过程中, 将在一个BP弱分类器上进行的计算分布到多个BP弱分类器上并行计算, 并将计算所得的预测误差εt作为中间结果保存在本地磁盘中, 在一次MapReduce计算任务结束后计算所有εt的算术平均数并作为最终键值发回到命令节点, job () 函数根据该键值计算预测序列权重并进行权重调整, 下一次的MapReduce任务可以迭代调用。为了适合MapReduce计算模型处理, 须将待处理数据记录以行形式存储, 使待处理数据能按行分片, 且片间数据无相关性, 分片过程由MapReduce运行的环境完成, MapReduce库会自动根据输入文件大小将输入文件分成16MB到64MB的M份, 不需要编写代码[11]。

BP-Ada Boost的MapReduce并行化具体流程如下:

(1) 数据划分阶段:该阶段在命令节点将训练样本集文件分解为 (文件行号, 样本项的键/值对) , 并切分成一定的数据块大小分布到系统的各节点 (即各计算机) 进行MapReduce计算。

(2) Map阶段:Map函数的任务是完成每一个弱分类器预测误差εt的计算与重新标记。Map类调用Map () 函数接收数据划分阶段产生的键/值对, 进行弱分类器学习, 获取该弱分类器的预测函数gt与预测误差εt, 生成形如<弱分类器ID, εt>的<key, value>键/值对, 每一次Map任务产生的中间结果键/值对先被暂时保存在运行本地系统文件中, combine () 函数再以<弱分类器ID, εt>键/值对作为输入, 进行本地归约操作, 收集并进行Reduce计算。

(3) Reduce阶段:Reduce函数的任务是将Map阶段得到的中间结果合并、计算, 形成最终键值对。首先, Reduce类调用Reduce () 函数, 以Map阶段产生的中间结果为输入, 进行规约化计算, 过程如下:

(4) 在Reduce任务结束后, 将输出形如<弱分类器的<key, value>键/值对, 并将该结果发回到命令节点。Job () 函数的任务是计算预测序列的权重αt并进行权重调整生成调整后的新权重Dt+1 (i) , 该结果会保存在云计算平台系统的全局变量配置文件中, 以备下一次的MapReduce任务使用。

设图2所示为MapReduce的分解过程。当完成算法初始指定的T次循环迭代后, 权重已经被调整到一个很小的误差范围, 则既定的学习任务完成, 训练完毕, 此时的多个弱分类器已经组成为强分类器。

2.2 改进后的BP-Ada Boost算法的特点分析

MapReduce并行化BP-Ada Boost算法具有如下特点:

(1) 实现了海量数据分类

随着信息技术的发展, 数据量成指数级增长, 对海量数据的分析和处理已经成为一种热点和趋势。而传统的BP-Ada Boost算法因其算法复杂度等问题很难处理大规模的输入数据量, 并可能产生训练时间长、计算量大、计算机内存耗尽等状况。针对这一瓶颈, 提出BP-Ada Boost的MapReduce并行化方法, 将海量数据切分成可供运算的小块, 并将原本在一台机器上的运算, 分布到集群中的各个节点中并行处理, 实现海量数据处理。

(2) 降低算法的时间复杂度

传统的BP-Ada Boost算法可以实现良好的分类效果, 但是由于其本身的穿行与迭代特性, 使得它的时间复杂度较高, 运行需耗费大量的时间。BP-Ada Boost的MapReduce并行化方法, 以其独特的分布式计算特性, 将原先在一个弱分类器上进行的运算, 分布到集群的多个节点 (弱分类器) 上进行, 有效地降低了算法的时间复杂度, 缩减了算法的运行时间。假设传统的BP-Ada Boost算法的算法时间复杂度为O, 集群中平均每个节点完成n次Map任务, 在理想状态下 (不计集群中节点的通信开销) , 则改进后算法的算法时间复杂度为O/n。

3 实验及性能分析

3.1 实验环境

实验采用开源的Hadoop云计算平台, 系统由7台计算机组成, 包括1台Name Node命名节点机器作为Job Tracker, 6台Data Node数据节点机器作为Task Tracker, IP地址段为192.168.1.1~192.168.1.7。集群内机器硬件配置为INTEL Dual-core 2.6GHz处理器, 4GB内存, 500GB硬盘, 软件环境为Red Hat Enterprise Linux 5操作系统, JDK1.6.0_20, Hadoop0.20.0, 根据Hadoop项目官方网站介绍的方法对系统进行了配置。

3.2 实验数据

实验采用的数据集来源于UCI国际机器学习数据库中关于红白两种葡萄酒分类的数据, 通过样本的12种属性来区分葡萄酒的种类, 样本的属性名称依次为″fixed acidity″;″volatile acidity″;″citric acid″;″residual sugar″;″chlorides″;″free sulfur dioxide″;″total sulfur dioxide″;″density″;″p H″;″sulphates″;″alcohol″;″quality″。该数据集的特点为:数据按行存储, 可用性和可靠性高, 行与行间数据耦合程度低, 以上特性保证了数据分割后各节点的数据分布均匀, 可用性高, 局部特性好, 符合MapReduce的数据分割要求。将该数据集分别在单机和集群上进行了实验, 并对结果进行了对比和分析。

3.3 对比实验及结果分析

实验一根据数据维数, 采用的BP神经网络结构为12-6-1, 先用单个BP神经网络 (即弱分类器) 对数据进行分类, 图3所示为弱分类器的分类误差。

然后采用同样的网络结构, 训练生成10个BP弱分类器, 并用10个弱分类器组成的强分类器对数据进行了分类。表1所示为两种分类器的分类效果和运行时间。

由表1可知, 传统的BP-Ada Boost强分类器虽然提高了分类的正确率, 却由于本身的串行特性, 时间复杂度高, 需要耗费比弱分类器多出数倍的时间来运行。

实验二逐步加大被处理数据量, 分别对传统的BP-AdaBoost算法与本文的改进算法进行了测试, 测试结果如表2所示。

随着数据量的加大, 传统的BP-Ada Boost算法运行时间过长, 甚至内存不足, 计算机无响应等情况, 说明传统的BP-AdaBoost算法在处理海量数据时存在不足, 而Hadoop集群不仅能处理庞大数据量, 而且运行时间大大缩短。

实验三通过改变集群中的机器数量, 测试集群的运行时间, 并通过和单机运行时间进行对比, 根据加速比的定义, 设加速比为Sp, 则Sp=T1/Tp (T1是单处理器下的运行时间, Tp是在有P个处理器并行系统中的运行时间) , 计算加速比。

由表3可知, 随着集群中Data Node节点数的增加, 集群的运行效率得到了一定程度的提升。但并非节点数越多, 集群的加速比越高。

在Hadoop集群这一并行系统中, 可以通过增加集群中处理器数量来提升运算的速度, 但加速比并非随着处理器数量的增加而线性增加, 这是因为集群中存在并行处理所引起的额外开销 (通信、等待、竞争、冗余操作和同步等) 这一限制因素。通常情况下, 增加处理器的数量会增加额外开销和降低处理器的利用率, 衡量一个并行系统有效利用处理器的能力, 可扩展性[12]是重要的性能指标。评判一个并行系统可扩展性好坏的标准有很多, 目前, 比较公认的三个指标是:等效率度量指标 (ISO-efficiency Metrics) 、等速度度量指标 (ISO-speed Metrics) 和平均延迟度量指标 (Average Latency Metrics) 。

其中, 等效率度量指标是由Kumar等人于1987年提出的。设Te为并行系统上所有处理器的有用计算时间, To为额外开销时间, Tp为p个处理器系统上并行算法的运行时间, 则有Te+To=p Tp。问题的规模W可定义为由最佳串行算法所完成的计算量, 也称工作负载, 即W=Te。所以并行算法的加速S和效率E[13]可分别表示如下:

结合实验三, 由并行算法的效率函数可知, 由于问题规模W保持不变, 随着处理器数量p的增加, 开销时间To也随之增大, 故而效率E会相应下降, 并行系统的扩展性随之降低。为了维持效率E保持不变, 必须保持To/Te的值不变, 即需要在增加处理器数p的同时, 增大问题规模W, 才能使并行系统具有良好的可扩展性。

4 结语

本文给出了一种对BP-Ada Boost算法的MapReduce并行化方法, 并将改进后的算法部署在Hadoop云计算平台上, 解决了传统算法存在的算法时间复杂度较高、无法处理庞大输入数据量等问题, 提高了数据处理能力和计算效率。通过将计算任务分布到集群中的多个节点并行处理, 使资源得到了充分利用。通过集群上的三个对比实验, 验证了该算法的可行性, 它不仅能处理海量数据, 而且降低了算法的时间复杂度, 具有较好的加速比和准确性。然而, 实现过程中集群节点间的额外开销是一个不可忽视的问题, 结合对并行系统扩展性的分析, 说明了只有在所处理的数据量和集群中的机器数之间寻找一个结合点, 才能实现系统的效率最大化, 令并行算法和并行系统具有良好的可扩展性。这将是需要不断研究的课题。

并行化程序设计第5篇

相位差法求解过程运算量大、耗时、而且迭代过程本身不利于并行化改造,很难实现实时处理。为此国内外学者从优化算法与硬件实现上对提高PD的实时性开展了研究。2007 年,James A. Georges III等人实现了双变形镜的闭环控制,在100 Hz波前扰动条件下,对点目标实现了0.005 波长RMS的复原精度[1]。2008 年,Warmuth等人对扩展目标进行了实验,在14.5 Hz波前扰动条件下,对128 pixels×128 pixels大小扩展目标实现了0.001 波长RMS的复原精度[2]。近几年来,国内针对PD算法的实时性也开展了研究,长春光机所的赵金宇博士提出了一种对目标函数的改造方法,使得目标函数计算时只进行多项式运算,便于在DSP和FPGA平台上实现[3]。长春光机所的张楠博士针对GPU异构计算平台对PD算法进行了初步并行化实现,其中用到了NVIDIA开发的快速傅里叶变换库CUFFT[4]。

本文对PD算法进行了并行化分析,把迭代算法放在了GPU上实现,减少了CPU与GPU之间的数据交互。CUFFT库函数虽然计算效率比较高,但是对于目标函数计算中涉及到的冗余计算不能有效剔除。因此本文设计了专用的FFT Kernel函数。最后在多GPU平台下,对最优化算法中线性寻优部分进行实现。

1 算法理论

相位差算法基本原理如图1 所示,光束经大气湍流和望远镜成像系统后,经过分光片分离出两束光,在成像系统的CCD1(焦面)和CCD2(离焦面)上同时采集一对短曝光图像,并且离焦量已知。通过极大似然估计理论构建最优化数学模型,利用焦面和离焦面图像复原出目标和波前[5]。下面分别从目标函数、最优化方法进行介绍。

1.1 目标函数

相位差算法的本质是通过焦面、离焦面和离焦量,构建一个目标函数然后对其求最小值。当观测目标位于成像系统等晕区内时,可以把大气和望远镜系统组成的图像系统看成是空间不变线性系统。当物体为非相干光源时,成像系统对强度是线性的,考虑噪声情况下的PD图像系统所采集到的图像表示为

其中:k表示不同的光学通道,通常取焦面和离焦面两个通道,o(x,y)是目标图像,∗表示卷积运算,nk(x,y)表示噪声,hk(x,y)为k通道的点扩散函数,其表示为

其中:F-1{}为傅里叶逆变换,Pk(u ,v)为k通道广义光瞳函数,表示为

其中:ϕ(u,v)为待测相差,Δϕk(u,v)为k通道上引入的已知相差。在高斯噪声模型下,相差 ϕ(u,v)以及目标o(x,y)可以通过最小化目标函数求得,E表示为

对上式进行傅里叶变换,得到频域内的表达式

其中:Ik(u ,v),O(u ,v),Hk(u ,v)分别为ik(x,y),o(x,y),hk(x,y)的傅里叶变换。通常情况下为了保证解的稳定性和光滑性还会在目标函数中引入正则项,关于带有正则项的PD算法理论参见文献[6-7]。

1.2 最优化求解

目标函数确定以后,PD算法的求解就成为一个无约束的非线性优化问题。非线性优化问题,通常采用的是迭代方法求解,本文采用收敛性和稳定性高的拟牛顿法(Broyden-Fletcher-Goldfarb-Shanno, BFGS),其核心思想为:构造一个近似Hesse矩阵Hk代替了目标函数的Hesse矩阵,每次迭代过程中对其进行修正产生新的Hesse矩阵Hk+1,其修正公式为

其中:ρk=1/ykTsk,整个BFGS算法实现步骤如下:

Step 1:给定初始点x0,初始Hesse矩阵H0,终止条件 ε ,令k=0。

Step 2:计算,若,则算法停止,为最终解;否则执行Step3。

Step 3:计算搜索方向。

Step 4:沿着方向搜索,计算步长为,使得最小,令。

Step 5:令,由式(6)计算。

Step 6:令k=k+1,返回Step 2。

其中梯度方向表示:

Re( )和Im( )分别表示求复数矩阵的实部和虚部。

2 PD算法GPU异构平台上实现方案

针对GPU异构,首先将PD算法在单GPU进行任务划分,再对GPU上的任务部分进行Kernel合并优化,最后分析如何在多GPU上进行任务划分,并以双GPU为例进行实现。

2.1 单GPU平台任务划分

PD算法的计算为一个迭代过程,为充分挖掘GPU的计算资源,减少CPU和GPU之间的数据拷贝,迭代过程的计算也由GPU完成,而迭代终止条件的判断由CPU完成,这样在每次迭代过程中,CPU和GPU之间只有一次数据传输。目标函数和梯度函数为数据密集型,计算都由GPU完成。PD算法参数的初始化、迭代条件的设定都由CPU完成。通过以上分析,PD算法在单GPU上的实现步骤如下:

1)CPU将焦面、离焦面图像和离焦量等初始化参数传递到GPU。

2)GPU计算目标函数及其梯度,结合梯度向量修正搜索方向。

3) GPU在搜索方向进行线性寻优,将当前方向最小代价函数值传递到CPU。

4) CPU收到代价函数值后,完成了一轮的迭代,并判断是否满足迭代收敛条件,如果满足,GPU输出当前的复原目标和波前;否则跳转到2)继续迭代。

2.2 单GPU端任务优化

由PD算法的执行流程可知,对整个算法的优化问题可以缩小为对单次迭代的优化问题。单次迭代的计算主要包括评价函数和梯度函数的计算。这两部分的计算过程中涉及到许多冗余计算,这部分冗余计算与光瞳的数值化采样和光学传递函数(OTF)截止频率有关。光瞳函数和光学传递函数都有一个有效数据区域,在有效区域内数据为非0,在区域外数据为0。如图2 所示,其中N为图像在水平和垂直方向的像素,α为采样率,圆形光瞳的有效区域为半径为N/α的圆域,而OTF的有效区域为半径为2N/α的圆域[9]。

代价函数计算需要6 步完成,每一步计算数学表达式为

梯度函数计算需要6步完成,每一步的计算数学表达式为

上面计算过程中,Tik是临时函数,FOTF光学传递函数,Frow{}和Fcol{}表示批量行和列一维FFT,F-1row{}和F-1col{}表示批量行和列一维IFFT。

在对光瞳函数所有行做批量一维FFT计算时,零向量经过FFT之后结果还是零向量。光瞳函数非零的行向量,其首位部分也为零,对其做一维FFT时,与这些零元相关的数据读取和计算是冗余的。而CUFFT提供的一维FFT和二维FFT都不能有效去除以上冗余的计算。所以,本文定制了适合PD算法的FFT,其实现过程源于Volkov等人[10]。

本文对代价函数和梯度函数的计算分别采用两个方法实现,其计算过程如表1、表2 所示。方法1:采用CUFFT库函数计算FFT,对代价函数和梯度函数计算没有Kernel合并;方法2:采用剔除冗余计算的FFT,并且对代价函数和梯度函数计算进行了Kernel合并。为了尽可能多Kernel合并,我们调整了目标函数和梯度函数计算过程中二维FFT中Kernel的计算次序。以表1 中目标函数计算为例交换了Step5, Step6计算次序,从而使Step3~Step5 可以合并为一个Kernel。

目标函数计算中,Step1 和Step2 由M2_cost_K1 计算,Step3~Step5 由M2_cost_K2 计算,Step6 由M2_cost_K3 计算;方法1 和方法2 的Step7 都由M1_M2_cost_K1 完成。两种方法的Step8 都由M1_M2_cost_F1 完成。目标函数值作为迭代终止条件最后要传给CPU,而GPU进行规约求和时,活动线程数越来越少,所以我们采用三步实现规约求和运行。第一步由GPU完成部分规约,然后把结果传给CPU,再由CPU完成最后的规约。

梯度函数计算中,Step1 和Step2 由M2_grad_K1 计算,Step3~Step5 由M2_grad_K2 计算,Step6 和Step7由M2_grad_K3 计算。两种方法的Step8 都由M1_M2_grad_K1 完成。值得注意的是,与代价函数不同的是梯度函数的计算结果不需要传给CPU,所以梯度函数的规约全部由GPU完成。代价函数规约求和为一个标量,而梯度函数为一个向量,所以为了提高计算并行度,每个Kernel函数完成多个元素的规约,同时采用GPU的多个Stream进行处理。

2.3 多GPU平台任务划分

在多GPU平台上,为了尽量减少计算过程中的数据交互,宏观上GPU0作为主,其除了负责最优化过程中Hesse矩阵的相关计算,还参与代价函数和梯度函数的计算,其他GPU为从设备,进行代价函数和梯度函数的计算。线性寻优过程中每个GPU分别负责一个步长的计算,然后将代价函数值传给CPU判断是否为最优步长,如果当前多个GPU中找到最优步长,则终止线性寻优过程,让最优步长的GPU进行梯度函数计算,否则继续寻找最优步长。

对于数据交互问题主要涉及到两个方面:CPU与GPU之间数据交互,GPU与GPU之间数据交互,以双GPU平台为例,其数据传输如图3 所示,CPU与GPU之间只存在单向代价函数值的传输,而对于GPU之间主要有三个数据进行交互:当前最优解、当前梯度向量和当前搜索方向。无论最优解在GPU0还是在GPU1,都需要共享最优解作为下一次迭代的起点,所以最优解的传输是双向的;因为最优化算法BFGS的计算由GPU0完成,最优解确定之后,由最优解所在GPU继续进行梯度计算,再将梯度向量传给GPU0确定搜索方向(如果最优步长在GPU0则无需梯度向量传输),最后GPU0将修正后的搜索方向与GPU1共享。

3 实验结果分析

3.1 实验配置

本文实验所采用的硬件配置:Intel(R) core(TM) i7-3930k主频3.2 GHz CPU,内存8 G,NVIDIA Telsa K20c GPU。软件配置:Windows 7 64-bit操作系统,VS2010+CUDA6.5 编程环境。实验数据:静态的65项泽尼克多项式模拟相差PV=2λ 的大气湍流,128 pixels×128 pixels、256 pixels×256 pixels和512 pixels×512pixels大小的静态图像。

3.2 实验结果

图4(a)为复原的波面,图4(b)为复原之后的残余误差,复原前波前RMS=0.243 3 波长,复原后波前残差RMS=0.004 波长。

为提高计算性能,本文把焦面图像和离焦面图像的计算进行合并进行批量处理。CUFFT库函数提供了批量FFT的函数,例如对于双精度的复数到复数的FFT计算只需要传递函数句柄plan Many_Z2Z给cufft Exec Z2Z函数。本文对两方法中涉及到的Kernel函数进行测试,选择了最优的线程配置,如表3,表4 所示。其中M1_M2_cost_F1 为规约求和的计算,该函数中只列出了在GPU上Kernel的配置。M1_M2_grad_F1 函数完成梯度计算中的规约求和,其与Cost function规约求和有两点不同,其一是这里65 项规约求和,每8 项为一个Kernel,最后1 项为一个Kernel,总共9 个Kernel调用完成,采用了4 级流水线实现了计算和访存的并行,其二是最终的计算结果无需传给CPU,整个规约过程都由GPU独立完成。需要说明的是,表4 中M1_M2_grad_F1 线程配置为前八个Kernel的配置,最后一个Kernel的配置与M1_M2_cost_F1 中规约求和相同。

针对上述线程配置,Cost function和Gradient function各个Kernel的执行时间如表5,表6 所示。需要说明的是,M1_M2_cost_F1 中符号“/”前为Kernel执行时间,符号后为GPU向CPU数据传输时间。M1_M2_grad_F1 的执行时间为4 级流水线上9 个Kernel执行的总时间。方法2 FFT计算过程中,128 点,256 点,512 点FFT的计算分别采用16×8 分解基,16×16 分解基,8×8×8 分解基。另外,利用实数FFT计算结果的共轭对称性,CUFFT在计算实数的FFT时,也是只保存了一半的信息。

μs

然后在单GPU和双GPU上,方法1 和方法2 针对128 pixels×128 pixels、256 pixels×256 pixels大小图像,都经过50 次迭代进行测试,结果及加速比如表7 所示。方法1 不能剔除与光瞳函数和OTF截止频率有效区域以外的冗余计算,并且不能利用Kernel合并减少对Global Memory的访问开销,从而效率不如方法2。对于256 pixels×256 pixels大小的图像,在单GPU方法2 比方法1 效率提高了1.57 倍,在双GPU上方法2 比方法1 提高1.6 倍。当图像尺寸较小时, GPU之间数据传输和同步开销占总开销的比例较大,而且数据量小时,GPU的计算资源没有得到充分利用,所以对于128 pixels×128 pixels大小的图像,两种方法在双GPU和单GPU分别加速只有1 ms和5 ms。

4 结论及展望

本文对相位差算法进行并行分析,在GPU平台上采用了两种方法实现,方法1 采用库函数CUFFT,方法2 采用定制的FFT。方法2 的FFT不仅实现了冗余数据的剔除还实现了Kernel的合并,从而大大提高了性能。由于本文开发的FFT只是针对二的幂次大小图像,方法2 对于非二的幂次图像的处理是下一步研究的重点。

参考文献

[1]Georges J AⅢ,Dorrance P,Gleichman K,et al.High-speed closed-loop dual deformable-mirror phase-diversity testbed[C]//Advanced Wavefront Control:Methods,Devices,and Applications V,San Diego,California,USA,August 26,2007:671105.

[2]Warmuth M W,Parker S W,Wilson A J,et al.Operation of phase-diverse adaptive-optics with extended scenes[C]//Optical Engineering Applications.International Society for Optics and Photonics,San Diego,California,USA,August 10,2008:709307.

[3]赵金宇,陈占芳,王斌,等.相位差异法目标函数的并行化改造[J].光学精密工程,2012,20(2):431-438.ZHAO Jinyu,CHEN Zhanfang,WANG Bin,et al.Parallelity improvement of object function for phase diversity[J].Optics and Precision Engineering,2012,20(2):431-438.

[4]张楠.基于相位差异的地基望远镜图像恢复算法与GPU高速实现[D].长春:中国科学院长春光学精密机械与物理研究所,2012:59-77.ZHANG Nan.Image restoration algorithm based on phase diversity for ground-based telescope and high speed implementation on GPU[D].Changchun:Changchun Institute of Optics,Fine Mechanics and Physics,Chinese Academy of Science,2012:59-77.

[5]杨磊.Phase diversity波前重构的研究及在高分辨图像复原中的应用[D].昆明:中国科学院云南天文台,2007:1-10.YAN Lei.Researches of the phase diversity wave-front reconstruction techniques and its application in the high resolution image restoration[D].Kunming:Yunnan Observatory of Chinese Academy of Sciences,2007:1-10.

[6]李斐.相位差法波前探测技术及其在图像恢复中的应用研究[D].长沙:国防科学技术大学,2011:30-43.LI Fei.Phase diversity wavefront sensing and its application in image restoration[D].Changsha:National University of Defense Technology,2011:30-43.

[7]汪宗洋,王建立,王斌,等.基于相位差异的图像复原方法[J].光电工程,2010,37(12):25-29.WANG Zongyang,WANG Jianli,WANG Bin,et al.Image restoration based on phase diversity[J].Opto-Electronic Engineering,2010,37(12):25-29.

[8]陈宝林.最优化理论与方法[M].北京:清华大学出版社,2005:281-315,394-412.CHEN Baolin.Theory and Methods of Optimization[M].Beijing:Tsinghua University Press,2005:281-315,394-412.

[9]Zielinski T P.Robust Image-based Wavefront Sensing[M].University of Rochester,2011:14-16.

并行化程序设计第6篇

层叠样式表CSS是由W3C定义和维护的标准,一种用来为结构化文档如HTML文档或XML应用添加样式( 字体、间距和颜色等) 的计算机语言[1]。

相对于传统HTML的表现而言,CSS能够对网页中对象的位置排版进行像素级的精确控制[2]。CSS规范的广泛使用和嵌入式浏览器的广泛使用,使CSS引擎成为嵌入式浏览器中必不可少的部分。CSS引擎完成的功能是将网页中的CSS样式描述准确无误地解析出来,并对每个DOM节点( 文档对象模型,DOM树是由结构文档生成的树结构,DOM节点是DOM树中的节点) 进行样式匹配、样式运用,最终使样式效果得以实现[3]。

随着互联网的发展,嵌入式浏览器的响应速度成为影响用户体验的一个重要因素。越来越多的厂商开始利用多核处理器,然而,当前的嵌入式浏览器并没有充分利用硬件并行化的优势,因此导致计算资源闲置问题。

为了利用多核优势,一些桌面浏览器如Chrome开始采用多进程的方式,一个标签页一个进程,在标签页很多的情况下加快了网页的处理速度。然而在嵌入式设备上,更多的用户需求体现在一个标签页的情况下网页加载速度问题,这就要求提高浏览器的处理速度。据统计CSS引擎的处理时间占浏览器总处理时间的近40%[4],所以对CSS引擎的处理采用并行化,可以大大加快网页的加载速度,同时可以充分利用硬件资源。本文针对目前嵌入式系统处理速度有限、内存受限以及多核处理器广泛发展的特点,提出了一种CSS引擎并行处理的方法。

1 CSS引擎结构

从整体上看,CSS引擎的输入是文档对象模型( DOM树) 和一个CSS样式集,经过CSS引擎的处理,输出标注了CSS样式的一棵渲染树[5]如图1( a) 所示。本文将CSS引擎分为CSS样式解析器、内部样式结构、样式分类和样式匹配4 个模块,内部结构如图1( b) 所示。

在页面解析过程中,HTML解析器遇到CSS样式描述,会调用CSS样式解析器对CSS样式描述进行解析,具体为经过词法分析、语法分析和语义处理得到内部样式结构,供程序内部使用。内部样式结构依据CSS规范而设计,具有严格的层次关系,从最高层到最底层有样式表( CSSStyle Sheet) 、样式规则( CSSStyleRule) 、样式选择符( CSSSelector) 、样式声明( CSSMutal Style Declaration) 、样式属性( CSSProperty ) 和样式属性值( CSSValue) 等,如图2 所示,表示了将一个CSS描述进行词法解析的过程。其中,样式规则由样式选择符和样式声明成对组成。

样式分类部分是对已解析得到的内部样式规则按照样式选择符类型进行分类,对于待匹配的节点,适用的样式选择符单元类型集是全部样式选择符单元类型的一个子集,在每次样式匹配前确定最小适用样式规则分类集,可以减少一些不相关样式规则的匹配。

样式匹配是将每个样式规则映射到DOM树上各个节点的过程。样式匹配在网页解析过程中调用次数非常多,匹配过程也较为复杂,需要消耗大量的时间,是CSS引擎的性能瓶颈。采用合适的样式匹配算法可以大大减少匹配的时间,优化网页的加载。

2 并行化CSS引擎处理方法

CSS引擎所做的主要工作包括CSS资源预取、CSS解析、CSS选择器匹配[6]。通过CSS引擎处理后,各个样式才能映射到DOM节点,确定每个节点的位置颜色大小等信息。下面通过CSS引擎的工作分别描述并行化算法具体的实施方式。

2. 1 CSS资源预取

如果在一个CSS样式表中引用了过多的外部CSS资源( 如图片或CSS样式表) ,用户在请求资源下载时需要经历长时间的网络延时,为了减少下载资源所花费的时间,尽可能地从网络中预取所依赖的资源是非常必要的。

本文的方法是在HTML文档解析开始先进行文档的预扫描,如果发现有外部资源,就利用并行算法将其预取下来,即资源预取和页面解析是并行执行的,此时并不影响页面解析。如图3 是未采用并行算法时页面解析过程中发现DOM节点中用到外部资源,页面解析阻塞,开始加载资源; 图4 是采用并行算法后,页面解析不受影响。

下载足够的外部资源是非常重要的。如果加载资源过多会减慢页面加载的速度,增大网络的负担; 如果加载资源不足,在CSS样式解析中需要重新加载外部资源,增大了网页解析的延迟。本文通过HTML预扫描器确定外部资源中选择符的ID或类属性是否都被预扫描器发现了,如果外部资源CSS选择符中所有的属性值都被HTML预扫描部分发现了,就开始加载此资源。这样经过判定后加载的资源在页面解析过程中会被使用,增大了加载资源的可用性。

2. 2 CSS解析

在本文的并行方法中,如果HTML解析过程中遇到样式描述符就将其分发给CSS解析器,每个样式解析分属不同的线程,这就意味着一旦有新的CSS样式,CSS解析会立即执行。然而为保证所有CSS样式规则的顺序与串行CSS引擎产生的规则顺序一致,本文中的方法是为每个解析任务分配一个独一无二的串行ID号,用来重排最初文档中的CSS样式表。图5 所示是串行CSS资源解析的流程,遇新的CSS样式时页面解析会被中断,图6 中所示当采用并行算法后,HTML页面解析不受影响。

CSS样式解析主要是将输入的CSS代码经过词法分析、语法解析生成计算机可以识别的语言。词法分析器,有时也被称作tokenizer,主要是将从样式表中输入的字符序列转换为单词序列,并对单词序列分类。词法分析器一般以函数的形式存在,供语法解析器调用。词法分析器通常不会关心每个单词之间的关系。例如有一个规则集div{ color: red} ,当进行完词法分析后,一共得到6 个有效的token: “div”,“{ ”,“color”,“: ”,“red”,“} ”。可见词法分析不依赖外部单词的信息,只依靠词法,比较简单。

语法解析器主要进行语法检查、并构建由词法分析器所返回的单词组成的数据结构,一般是语法解析树、抽象语法树等层次化的数据结构。例如上例中,如果网页书写人员将“red”写成了“rd”,语法解析器会报语法错误,此条规则会失效。

经过词法分析、语法解析后,CSS解析器输出一些CSS选择符和样式声明,为选择器匹配奠定基础。

2. 3 CSS选择器匹配

CSS匹配算法的功能就是将各个样式映射到DOM节点上。对于每个节点,CSS引擎必须找到所有匹配此节点的选择器或者规则。一个具体的CSS选择器匹配的例子如图5 所示: ul em{ color: blue} ,如图7 所示是将em节点的颜色设置为蓝色,为了找到em的先辈节点,必须从底向上遍历DOM树,直到找到ul节点,此次匹配完成。

2. 3. 1 根据CSS选择符的类型并行化处理

按照浏览器对CSS选择符书写规则带来的页面开销( 从小到大) 的顺序,CSS选择符的类型分为ID选择符( 如#top{ margin-top: 50px} ) 、类选择符( 如id. x { font-size: 12px} ) 、类型选择符( 如a{ text-decoration: none; } ) 、相邻兄弟选择符( 如h1 + h2{margin-top: 50px } ) 、子选择符( 如top > li{ margin-top: 50px } )和后代选择符( 如top a { 后代选择符,示例top a { } } ) 等[7]。本文的并行化方法是根据CSS解析后得到的CSS选择器的类型,将不同的选择器分在不同的线程中,与DOM节点进行匹配,如图8 所示。图9 为匹配算法执行的伪代码。其中id Match( DOM) ,class Match ( DOM ) ,tag Match ( DOM ) 和other Match( DOM) 分别在不同的线程中,执行遍历DOM的操作,一直遇到匹配的DOM节点为止。

该算法首先根据不同的选择符类型建立哈希表,建立哈希表的具体方式利用了webkit中的策略[8,9,10],表中存放ID、类、标签名称或其他。如当输入选择器的类型为ID时,我们用idMatch线程处理,利用从右到左的匹配方式,逐级找到DOM节点。其他类型类似。例如对于“p img”,我们首先找到“img”节点,然后遍历其DOM树,当在其祖先节点中找到“p”时才将此选择器的属性值应用到此节点,否则选择器不匹配。

2. 3. 2 并行DOM遍历

对于2. 3. 1 节,我们是根据选择器类型的不同进行了并行化处理,如果对于选择器的类型特别单一的网页,可以对DOM树结构进行并行化处理。首先将DOM树映射到一个节点数组中,本文利用work-stealing算法[11]将不同的数组块分给不同的核心处理。图10 示出了并行化的具体实施方式。

对于不同的选择器不同的DOM节点,每个选择器匹配一个节点所花费的时间是不同的。DOM树中相邻的节点可能有相似的属性,所以匹配路线和处理时间也相似。相邻节点之间的这种相似性意味着在不同的子树上可能需要不同的处理时间,这就导致了静态分配不平衡性,从而增大了动态调整时间。为解决此问题,本文通过将不同的节点随机分配到不同的数组中,在一个并行循环中执行work-stealing算法,减少窃取的次数,加快了处理速度。

3 算法分析与验证

采用以上并行化CSS引擎处理算法在多核处理器环境下,可以充分利用硬件资源,效果更优。对于引用外部样式资源比较多的情况下,可以减少网络延时带来的影响。由于利用了多线程处理,增加了线程之间的通信; 对资源的预加载以及CSS解析中增加了对空间的占用。这种牺牲空间换取时间的方式对于硬件处理来说是可行的。

考虑到不同的网页外部CSS样式表和图片的数量不同,本文基于不同的网页做了实验模型化,基于不同种类的网页进行仿真测试,测试结果如表1 所示。结果表明,采用并行化算法可以明显提高加载速度,但是增加了空间的占用。而对于百度首页这种页面内容单一的网页,提升的效果并不明显。

4 结语

本文对嵌入式浏览器CSS引擎的功能和结构进行了简要说明,主要介绍了并行化CSS选择器的三个方面: CSS资源预取、CSS解析和选择器匹配。另外选择器匹配中通过CSS选择符并行化和DOM数据结构的并行化,详细介绍了并行化的实现方式。通过采用此方法,在多核处理器上可以大大加快网页的加载速度。由于CSS引擎相对独立,这种并行方法具有较强的可移植性。本文的研究对于将来多核处理器中CSS引擎并行化处理具有较好的参考价值。

摘要：针对嵌入式浏览器CSS(Cascading Style Sheets)解析效率低下的问题,提出一种CSS引擎并行化处理方法。通过对CSS引擎资源预取、样式解析和选择器匹配功能的描述,分别介绍如何将资源预取、样式解析与网页解析并行执行,以及CSS选择器并行匹配。该并行处理方法可以克服嵌入式浏览器边解析边加载带来的网络延时以及串行处理带来的用户等待时间长的问题。通过对多种网页加载时间的仿真测试,页面的加载速度提高了很多,实验结果验证了该方法的可行性。

关键词：层叠样式表引擎,并行化,资源预取,样式解析,选择器匹配

参考文献

[1]Mozilla.CSS[EB/OL].https://developer.mozilla.org/en-US/docs/CSS,Aug,2012.

[2]罗智明.基于智能手机平台的CSS引擎优化与实现[D].电子科技大学,2012:8-14.

[3]刘剑,桑楠,郭文生.嵌入式浏览器CSS引擎的研究与改进[J].计算机工程,2011,37(9):44-46.

[4]Badea C,Haghighat M R,Nicolau A,et al.Towards parallelizing the layout engine of firefox[C]//Proceedings of the 2nd USENIX conference on Hot topics in parallelism.USENIX Association,2010:1.

[5]Meyerovich L A,Bodik R.Fast and parallel webpage layout[C]//Proceedings of the 19th international conference on World wide web.ACM,2010:711-720.

[6]Cascaval C,Fowler S,Montesinos-Ortego P,et al.Zoomm:a parallel web browser engine for multicore mobile devices[C]//Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming.ACM,2013:271-280.

[7]田岭.深入理解CSS选择符的匹配方式[J].软件导刊,2012,10(12):37-38.

[8]葛春良.嵌入式浏览器多线程机制的研究与实现[D].电子科技大学,2012:38-39.

[9]The Web Kit open source project[EB/OL].[2011-02-10].http://www.Webkit.org.

[10]赵经纬,周余,王自强,等.基于Web Kit的嵌入式浏览器的研究与实现[J].电子测量技术,2009,34(3):135-138.

并行程序设计及实现第7篇

并行计算是指将顺序执行的计算任务分成可以同时执行的子任务，并行执行这些子任务，从而完成整个计算任务。程序一般是指顺序执行的指令集合，程序一般在一个处理器上执行。

1.1 问题的引入

排序(Sorting)是将一个数据元素(或记录)的任意序列，重新排列成一个按关键字有效的序列。在这里只考虑内部排序，即等待排序记录存放在计算机的随机存储器中，排序过程中不需要访问外部存储设备。

选择排序是排序开始的时候，扫描元素个数为n整个列表，找到它的最小元素然后和第一个元素交换，将最小元素放到它在有序表中的最终位置上，其他元素依此类推。

归并排序中“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。利用归并的思想容易实现排序。

从而可以发现，在归并排序中，每一次的归并过程都是可以并行进行的。在理想的情况下，可以把n个记录平均分配到n台处理机上，那么每台处理机上就存储了一个长度为1的子序列;然后不同处理机上的子序列两两归并，得到n/2个长度为2的有序子序列，这些子序列分别保存在n/2台处理机上;再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止。

1.2 算法的实现

现在设定可以使用的处理机数目为4台，给出一个在4个处理机上运行的并行排序算法(使用的编程语言为C++)。这里可以简单的将待排序的数组a[n](假定n为4的倍数)平均分为4部分，将这4部分分别放到4台处理机上进行选择排序。将4台机器上已经排定次序的4个部分的数据，两两进行归并得到两个基本有序的序列;最后将这两个基本有序的序列进行规并，得到有序的数组b[n]。

用一个8节点的有向无环图来描述这个并行算法。如果图1中的节点表示并行程序的任务，那么就可以将图1看成是8任务并行程序描述图的直观表示。其中：(1)任务0：获得需要处理的数据，将数据分为4部分并将这些数据发送给任务1、2、3、4;(2)任务1、2、3、4：采用选择排序法对接收到的数据进行排序;(3)任务5、6：分别从任务1、2以及任务3、4接收的有序数组进行归并排序;(4)任务7：接收任务5、6所发送的数据并进行归并排序;最后输出处理后的数据。

2 并行程序的实现

2.1 基于TCP/IP协议的Windows套接字编程

网络套接字编程有两种不同类型的应用：服务器与客户。服务器与客户有不同的行为，他们的创建过程是不同的。下面给出创建基于连接的TCP/IP服务器与客户的通用模型。

服务器：(1)初始化Windows套接字环境;(2)创建套接字;(3)绑定套接字;(4)监听套接字;(5)接受连接;(6)发送或接收数据;(7)断开连接;(8)结束Windows套接字环境。

客户：(1)初始化Windows套接字环境。同服务器编程模型中第1项;(2)创建套接字。同服务器编程模型中第2项;(3)连接服务器;(4)发送或接收数据。同服务器编程模型中第6项;(5)断开连接。同服务器编程模型中第7项;(6)结束Windows套接字环境。同服务器编程模型中第8项。

2.2 利用网络套接字编程实现任务之间的通信

通过网络套接字传送的数据一般为字节流，而进行计算的数据类型却不一定以字节为单位。因此须考虑两种数据打包和解包的方法。

(1)将表示数据值得字符作为网络传输的数据。比如，要在网络上传输整型数据15，那么就可以将字符1和字符5在通过网络传输到目标机器，然后目标机器在将字符1和字符5进行解释，得到整型数据15。下面给出根据这种设计得到的打包和解包函数，以整型数据为例。

函数PacketIntArray对整型数组打包成字符串。其中，a为要打包的数组的首地址，arrlen为数组中元素的个数，buf为字符串的地址，buflen为字符串的长度。

void PacketIntArray(int*a,int arrlen,char*buf,int buflen)

函数UnpackIntArray将字符串解包为整型数组。其中，a为要解包后的数组首地址，arrlen为数组中元素的个数，buf为字符串的地址，buflen为字符串的长度。

void UnpackIntArray(int*a,int arrlen,char*buf,int buflen)

(2)将数据在内存中的表示形式作为网络上传输的数据。比如，要在网络上传输整数15，那么可以将整数15在内存中的值0x0000000F传输到目标机器，然后目标机器对0x0000000F进行解释得到数值15。由于不同的操作系统对数据在内存中的表示形式及存储顺序有不同，所以这种方式只能在相同的操作系统之间进行数据传输。下面同样给出根据这种思想设计的打包和解包函数，具体实现如下所示：

函数PacketIntArray2实现数据的打包。其中，a为要解包后的数组首地址，arrlen为数组中元素的个数，buf为字符串的地址，buflen为字符串的长度。

void PacketIntArray2(int*a,int arrlen,char*buf,int buflen)

函数PacketIntArray2实现数据的打包。其中，a为要解包后的数组首地址，arrlen为数组中元素的个数，buf为字符串的地址，buflen为字符串的长度。

void UnpackIntArray2(int*a,int arrlen,char*buf,int buflen)

将计算所需的数据转化成为字节流之后，就可以调用recv和send函数在机器之间进行数据传输。

2.3 并行程序的实例

下面提出并行算法。

(1）在并行程序描述表添加内容。

首先定义一个PPDescription类型的对象ppd，然后手动填写或从文件中读入数据填充ppd对象中的成员变量。

成员变量name中的为描述并行程序名称的字符串，将这并行程序称为EightTasksSort。

成员变量graph保存表示描述并行程序的邻接矩阵，其内容为：

第i行第j列(0<=i,j<=7)的值为-1，表示节点i没有到节点j的边，即任务i不向任务j发送数据。第i行第j列(0<=i,j<=7)的值为大于等于零的数t，表示节点i有到节点j的边，即任务i向任务j发送数据，且发送数据需要的时间为t。