并行程序设计模型（精选九篇）
并行程序设计模型 篇1
我国大、中型制造企业大都是集研发制造于一体的公司。面对市场的激烈竞争, 缩短产品交付周期是企业获取市场的重要法宝。产品设计周期和工艺设计周期在产品面向客户的交付周期中占有很大的比例, 对于多品种、小批量企业来说, 这个比例高达50%。着眼于提高设计—工艺并行度, 大大缩短设计工艺周期, 对企业生存与发展有着极其重要的意义。
1 传统工作模式分析
某公司获得了市场订单后, 设计部门将承担设计任务, 设计完成后 (通常以图纸归档为标记) , 提交工艺部门完成工艺设计。工艺设计包含工装设计、工艺规程 (工艺卡片设计等) 设计、工艺流程分工等, 其中工艺规程设计占工艺设计80%的工作量。设计和工艺是严格的串行方式。假定某产品设计周期5个月, 工艺周期3个月, 其设计工艺总周期则为8个月。
2 设计—工艺并行管理模型的探讨
产品设计阶段通常划分为:方案设计、技术设计、施工设计 (工作图设计) 、试验试制。方案设计、技术设计是面向设计的设计, 施工设计是面向制造 (工艺) 的设计, 在设计周期中占的时间比重最大。当产品设计进入到施工设计阶段, 涉及到产品的重大技术方案已经定型, 此时工艺人员可以高度介入, 开始工艺设计。以典型产品转向架设计为例, 假定方案设计、技术设计周期为2个月, 施工设计周期为3个月, 工艺规程设计周期为3个月, 其设计工艺周期为8个月。转向架大约由900个零部件构成, 按照设计零件的个数 (工作量) 与时间均等划分, 1个月可以完成300个零件设计, 所以工艺人员在施工设计开始后1个月就能从事工艺设计, 特别是大量的零部件的工艺卡片设计。按照这种并行模式, 可以将原设计工艺需8个月的工作周期缩短为6个月, 约25%。见图1。
实现这种管理模式, 有2个先决条件: (1) 在施工设计阶段, 设计人员和工艺人员要形成一对一的任务关系, 工艺人员完全明白自己对口的零部件工艺设计任务; (2) 有一个良好的信息平台支撑, 保证工艺人员能及时获取设计信息, 高度并行地从事工作。
3 设计—工艺并行信息化模型的探讨
信息化模型主要是将管理模型数字化 (计算机化) 。我们假定产品设计工作已完全在PDM的项目管理模块支撑下进行, 实现了设计项目的阶段划分, 任务分解, 任务指派, 整个设计工作在项目任务树的组织下有序展开。我们将设计项目任务树扩展至设计—工艺并行项目任务树, 在项目创建时确定是否是设计—工艺并行项目。如果是, 则在创建设计项目任务树的同时, PDM系统自动创建工艺项目任务树, 两个任务树保持相同结构, 特别是在施工设计阶段, 设计每指派一个任务, 必在工艺任务树中自动产生一个相应的工艺任务, 设计任务和工艺任务间建立关系, 形成1—1的明确关系, 保证工艺任务的执行者, 随时能浏览设计任务的工作情况, 从而确定是否开展对应的零部件的工艺卡片设计。每个工艺任务与设计任务一样, 必须具备“任务名称”“任务承担者”“开始时间和完成时间”三个要素。见图2。
4 结语
本文只给出了在PDM系统支撑下的设计—工艺并行的顶层结构, 仅涉及项目阶段划分和任务分解, 至于设计BOM和工艺BOM的数据结构、设计变更向工艺的传递等问题, 由于篇幅有限没有阐述。基于本文原理的设计—工艺并行的工作模式已在某大型制造企业实现。
摘要：产品设计与工艺设计高度并行工作, 能显著有效地缩短产品设计周期, 是制造业追求的目标。从现状分析、管理模型、信息化模型三个维度进行了有益探讨, 并给出了基于PDM系统的实现方法。
并行程序设计模型 篇2
关 键 词：MOS器件；模型参数；参数提取；器件模型
1 引言
器件的模型和模型参数提取是电子设计自动化（EDA）领域的关键工作[1]。采用遗传算法进行半导体器件模型参数提取是近年来兴起并被广泛使用的一种参数提取方法[2-3]。遗传算法全局搜索能力强、不需进行繁琐的求导运算，不依赖参数初始值等特点，理论上来说只要有足够的迭代次数种能找到最优解[4]。但是，由于遗传算法是一种搜索类算法,较之传统的基于梯度进行迭代计算的解析算法, 每进行一次迭代所需要的时间较长，计算量有了显著增加, 而且对许多复杂问题而言，例如采用的全局优化策略提取复杂模型的大量参数时，标准遗传算法的求解效果往往不是解决这个问题的最有效的方法，必须对算法进行修改与优化，这些因素无疑大大增加了遗传算法的计算量，为此必须考虑算法的耗时问题。本文针对遗传算法自身的耗时问题，讨论了并行遗传算法的特点，并以主从式遗传算法为例，证实了并行计算在参数提取工作中的可行性。
2 并行遗传算法
为了有效的解决遗传算法（GA）在模型参数提取过程中的耗时问题, 提高GA的运行速度，采用并行遗传算法（PGA）是提高搜索效率的方法之一。并行遗传算法[5-6]主要有主从式并行遗传算法、粗粒度并行遗传算法和细粒度并行遗传算法。
2.1 全局PGA模型－主从式模型（master-slave model）
如图1所示，主从式模型分为一个主处理器(master)和若干个从处理器(slaves)。主处理器监控整个染色体种群，并基于全局统计执行选择等全局操作；从处理器接收来自主处理器的个体进行适应度评估等局部操作，再把计算结果传给主处理器。
主从式模型的优点是简单，保留了串行GA 的搜索行为，对计算机体系结构没有严格要求，适合运行在共享存储和分布式存储的并行计算机上。如果适应度估值操作比其他遗传算子计算量大的多时，这是一种非常有效的并行化方法。
2.2 粗粒度PGA模型－分布式模型（distributed model）
该模型又称分布式、MIMD、岛屿模式遗传算法模型。在处理器个数较少的情况下，我们可以将群体分为若干个子群体，每个子群体包含一些个体，每个子群体分配一个处理器，让它们相互独立地并行执行进化。为了防止子群体早熟，每经过一定的间隔(即若干进化代)，各子群体间会交换部分个体以引入其他子群体的优秀基因，丰富各子群体的多样性。除了基本的遗传算子外，粗粒度模型引入了“迁移”算子，负责管理区域之间的个体交换。如图2所示，通常存在两种迁移实现:岛屿模型、踏脚石模型。
2.3 细粒度PGA模型－分散型 (fine-grained model)
细粒度模型又称为邻域模型(neighborhood model)或细胞模型(cellular model)模型。如果并行计算机系统的规模很大，理想情况下处理器多到可以与染色体一一对应，则我们可以将每个个体分配一个处理器，让它们相互独立地并行执行进化，这样就能获得并行遗传算法的最大可能的并发性。如图3所示，在细粒度模型中，通常处理器被连接成平面网格(grid)，每个处理器上仅分配一个个体，选择和交叉只在网格中相邻个体之间进行，所以网格上的邻域关系就限定了个体空间上的关系。由于对处理器数量的要求很高，所以细粒度模型的应用范围不广。
3 基于MPI的主从式遗传算法的的实现
3.1 总体构想
我们采用的主从式并行模型分为一个主处理器(master)和若干个从处理器(slaves)。主处理器监控整个染色体种群，并基于全局统计执行选择等全局操作；从处理器接收来自主处理器的个体进行适应度评估等局部操作，再把计算结果传给主处理器，其个体的分配过程是这样的：假设种群规模为N, 优化模型参数变量个数为M。适应度评估时，程序传给评价函数N个长度为M的向量。并行的任务是master处理器将这个N个长度为M的向量平均分配到各slaves处理器做适应度计算，计算结束后，评价函数返回N个适应度给master处理器。计算各处理器分得的染色体个数的方法是，首先计算出每个处理器至少分配到的染色体个数为AveNum=N/Size，如果处理器个数不能整除行数，这样将有部分处理器分得到（AveNum+1）个染色体，规定多余的染色体分配到编号小的处理器上。
3.2 并行中的消息传递机制
另外，需要注意的是，仅仅依靠例如C，C++，java等编程语言所编写的程序是无法实现上面叙述的染色体在各处理器之间的传递任务。因为，在并行计算环境中，每个进程均有自己独立的地址空间，一个进程不能直接访问其它进程中的数据，因而，在进行并行计算的任务之间进行的数据传输必须通过消息传递机制。消息传递机制，是指用户必须显式地通过发送和接收消息来实现处理器之间的数据交换。
本文采用的是MPI(Massage Passage Interface)消息传递接口。MPI是一个很好的数据传递软件平台，可以通过调用MPI库函数来进行进程调度以及任务间的通信。它实际上是一个消息传递函数库的标准说明，吸取了众多消息传递系统的优点，是目前国际上最流行的并行编程环境之一，其特点是通用性强(只要求网络支持TCP/IP网络协议)、系统规模小、技术比较成熟。本文通过调用MPI的库程序来达到程序员所要达到的并行目的，使异构的计算机群体作为一个紧凑、灵活、经济的计算机资源来使用的并行环境。
3.3 共享内存多处理器主从式并行环境搭建
全局并行化模型并不限定计算机体系结构，它可以在共享内存和分布式内存计算机中高效实现。现在简单介绍一下两种并行编程的方法：分布式内存方法和共享式内存方法。
对于分布式内存的并行计算机，各个处理器拥有自己独立的局部存储器，不存在公用的存储单元，显然，这种方法的问题就产生于分布式内存的组织。由于每个节点都只能访问自己的内存，如果其他节点需要访问这些内存中的数据，就必须对这些数据结构进行复制并通过网络进行传送，这会导致大量的网络负载。他的优点是拥有很好的扩展性，有利于快速构造超大型的计算系统。
在共享内存多处理器计算机中构成并行环境，在共享式内存方法中，内存对于所有的处理器来说都是通用的。这种方法并没有分布式内存方法中所提到的那些问题。而且对于这种系统进行编程要简单很多，因为所有的数据对于所有的处理器来说都是可以使用的，这与串行程序并没有太多区别。这些系统的一个大问题是扩展性差，不容易添加其他处理器。
为了在微机环境下使用MPI构成分布式内存并行环境，只要将PC机联接局域网，然后在每台PC机上安装相应操作系统，并安装MPI软件包即可。分布式内存即种群被一个处理器存储。这个主处理器负责将个体发送给其它从处理器进行评估，并收集计算结果，进行遗传操作来生成下一代。
对于本文所采用的在共享内存多处理器计算机中构成主从式并行环境就更为简单，只要在PC机上安装操作系统（本文安装linux操作系统）和MPI软件包就可以实现并行环境了。在共享内存多处理器计算机中，种群可以保存在共享内存中，每个处理器可以读取被分配到的个体信息并将适应度写回，不会有任何冲突。
4 实验结果分析
将以上方法实现的基于MPI的主从式遗传算法应用于1.2um SOI MOS器件的阈值电压模型参数提取工作中。如图4所示，实验结果表明曲线拟合的效果很好，转移特性曲线最大误差都低于5%。采用并行计算后，参数提取的速度提高了接近2.5倍。
5 结论
从实际的测试效果来看，以上方法实现的程序的简洁有效，智能化程度很高，且具有较高的精确度。因此，本文提出的基于MPI的主从式遗传算法可以解决遗传算法在器件参数提取过程中的耗时问题。该方法简单易用，适合推广使用。
参考文献
[1] J.Liou A,Analysis and Design of MOSFETS: Modeling,Simulation,and Parameter Extraction[M].KLUWER ACADEMIC PUBLISHERS,1998.
[2] Kondo M,Onodera H,Tamaru K.Model adaptable MOSFET parameter extraction method using an intermediate model[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1998,17(5):400-405.
[3] Yang P, Chatterjee P K, An optimal parameter extraction program for MOSFET models[J].IEEE Transaction on Electron Devices,1983,30(9):1214-1219.
[4] Li Yiming. An automatic parameter extraction technique for advanced CMOS device modeling using genetic algorithm.Microelectronic Engineering,2006,41(4): 1309-1321.
[5] 康立山，非数值并行算法(第一册)-并行遗传算法[M].科学出版社,2003.
并行程序设计模型 篇3
关键词：可视化,并行程序设计,软件事务性内存,扩展性
0引言
随着计算机硬件技术的发展,多核已经成为目前主流的处理器架构,由于传统的串行程序设计不能充分发挥多核处理器的优势,所以并行程序设计方法的研究成为了一个热点[1]。并行程序一直被用来处理大规模计算和复杂计算等问题,虽然多核计算机的普及给并行计算的应用奠定了良好的硬件基础,但是并行程序设计方法却没有跟上计算机硬件的发展速度,并行编程效率低成为了制约并行程序广泛应用的一个瓶颈。为了解决这个难题,国内外学者在并行程序设计模型及语言方面进行了许多的研究。共享内存和消息传递等并行程序设计方法逐渐进入人们的视野,在一定程度上简化了程序设计人员的开发过程,但是这些模型还是集中在底层功能的调用,要掌握它们还需要进行系统的学习。与此同时,国内外学者在并行程序设计方法领域也做了各个方面的探索,例如并行设计模式、并行结构骨架、算法骨架以及可视化并行程序设计的理论。这些抽象程度更高的理论对于简化并行应用程序的开发有更大的实际意义。在已有的可视化并行程序设计方法中,虽然能够按照一些指定的代码模板进行并行程序设计,但是它的可扩展性和通用性较差。如果用灵活的底层设计方式进行程序开发,开发难度又会大大增加,开发效率也自然会变低。
近年来,软件事务性内存[2]作为一种新兴的并行程序设计模型被越来越多的研究与使用,它接口简单且可扩展性非常强,如果将可视化的编程方法与STM模型相结合,设计一种满足可视化编程要求的STM模型,可以为并行程序的设计提供一种可行的方法,使得并行程序的开发效率有一定的提高。
1相关工作
可视化程序设计[7]是指将程序、数据、系统结构或者系统的动态行为用可视的表现形式来表达。良好的可视化编程模式能够简化系统设计的复杂度,提高程序开发的效率。目前,针对串行应用程序的可视化建模方法和技术已经比较成熟,但是在并行程序设计方面尚且没有统一的标准。从编程模型的角度看,现有的可视化并行程序设计方法可以分为基于模板的、基于数据流的、基于进程的三类。基于模板的可视化并行程序设计通过提供一些用于进程交互的代码模板来构建并行应用程序。并行程序中进程的交互方式和通信结构一般由预先采用的模板决定,程序设计人员只需要提供应用程序的细节处理过程,并将这些细节填充到相应的模板之中,就可以使被整合在一起的程序编程完整地并行应用程序。基于数据流的可视化并行程序设计主要使用数据流图来进行并行程序设计,基于进程的可视化并行程序设计则是让程序开发者自己定义进程结构和显示的消息传递操作。由于传统的基于模板的可视化并行程序设计中模板的单一性和不可变性[8],使得基于模板的可视化并行程序设计方式相对死板,不易变通,如HeNCE是一个利用PVM为开发网络并行程序而设计的并行编程环境,但它的子任务之间不能有数据依赖使得它可用性不强。DPnDP是采用MIMD结构的并行开发模型,但是它不提供创建新模板的工具,只有在一个指定的C++框架内才能建议模板。VPE是为IBM RS6000工作站开发的一个小型可视化并行程序开发环境,虽然功能完善,但是它针对特定的硬件平台。而软件事务性内存具有良好的可扩展性和易用性且接口简单,在STM模型上运行的并行程序进程之间的通信方式和同步策略均可以非常方便的进行扩充和修改。基于STM模型的可视化并行程序设计会使得并行程序设计流程变得简单,增加开发效率,并且由于STM的可扩展性和易用性,使得基于此模板的可视化并行程序设计方法的通用性大大增强,只需要选定不同的仲裁策略和同步方法,就可以使得STM并行程序设计模板满足大多数并行程序设计的要求。
软件事务性内存的执行过程[3]一般分为事务的初始化和启动、事务的执行、事务的提交三个阶段。事务具有ACDI特性,不同事务在执行的过程中彼此独立,在提交阶段进行确认检测防止冲突的发生而影响数据的正确性。STM模型就是通过这种机制保证并行程序的正确执行。在典型的事务性内存模型中,事务对内存对象的访问有读和写两种方式。在一个事务读取内存单元时,它可以采取两种不同的策略,分别是读透明和读可见策略。所谓读透明策略就是事务之间的读取操作彼此独立,一个事物的读取操作不影响其他事务的执行;而读可见策略指的是一个事务读取一个对象时其他事务不能同时对这个共享对象进行读取操作,事务之间的读操作是彼此可见的。与事务的读操作不同,事务的写操作一般都是可见的,不同的事务不能同时对共享对象进行写操作。在面向可视化的并行编程过程中,一方面,用户图形接口要设计的简洁灵活,以保证实际程序开发过程中的可扩展性,另一方面,模型的算法实现要设计的严谨稳定,以保证并行程序运行时的正确定和安全性。ASTM是一种面向对象的软件事务性内存,面向可视化并行程序设计的STM模型是在它的基础上增加了可视化程序设计的必要因素来设计的。
2VPP STM设计
VPP STM模型的架构如图1所示,下面介绍可视化STM模型的实现算法。
2.1事务粒度
事务粒度是事务控制并发程序访问的最小数据单元[4],粗粒度的访问方式会制约多事务的并发执行,事务会由于频繁的访问冲突而回滚或访问失败,而细粒度的访问方式会限制一个事务的执行效率,并且由于共享数据单元划分的太小会导致冲突的检测时间增长,从而影响STM模型整体的效率。在目前常见的程序设计方法中,面向对象的程序设计方法已经成为最重要的开发方式,程序中的数据访问其实是对实例对象属性的访问,这种访问粒度是以对象为单位的,为了保持访问粒度的一致性,我们的STM模型也将采用面向对象的程序设计方法,以对象作为事务粒度的单位进行模型的设计。
定义1 定义事务集合为T(T1,T2,…,Tn),模型中任何活动事务Tx∈T;共享数据对象所在集合为 O(O1,O2,…,On) ,一个事务Tx从启动到提交过程中所访问的数据对象集合为T0∈0。
2.2版本控制与冲突检测
不同的并发事务同时执行的时候,事务与事务之间的操作可能会产生冲突,为了防止事物之间的冲突影响共享数据的正确性,需要版本控制与冲突检测来进行事务之间的并发控制。事务之间的冲突可以分为读后写、写后读、写后写三种。
定义2 每一个共享对象Ox∈O都维护有自身的版本信息集合 V(V1,V2,…) ,每一个版本 Vx都有一个时间戳timestamp作为标识,一个共享对象的版本序列 (V1,V2,…)中的timestamp按版本下标序号严格递增。
定义3 当一个事务Tx对Ox进行写操作并且成功提交后O中的Ox就会被成功修改到最新版本Vnew,此时其他事务就可以看到Tx对Ox修改后的状态了。如果Tx在执行之后提交失败,那么O中的Ox还是维持Tx修改前版本Vold不变。
不同的版本控制策略对STM系统维护的版本数量要求不一样[9],一方面,可以将一个共享内存对象生命周期内被访问的版本数据都保存下来以便事务在提交失败后可以查找指定的版本进行回滚恢复操作,另一方面,也可以用一些临时的存储单元对事务操作共享数据进行一个拷贝,如果事务提交成功,则用拷贝最新的数据对象替换之前的副本,如果事务提交失败,则用临时存储单元之中的数据副本恢复共享数据单元。
为了增强可视化并行程序设计方法的可扩展性,面向可视化的STM采用基于快照[5]的临时数据存储方式,在并发事务较多的情况下避免了数据版本冗长难以维护的缺点。当并发执行的事务在提交过程中检测到了冲突,就要采取一定的策略来选择须要正确提交的事务或者应该回滚的事务[6],仲裁策略通常以时间或者优先级作为仲裁的参考要素,在面向可视化的并行编程模型中,用户通过拖拽图形接口的方式进行建模,不同的程序可能要求不同,例如实时性的控制程序需要以时间作为重要的参考条件而一些内核调度程序需要以优先级作为事务提交成败的标准。在可视化的STM模型中可以用不同的图标代表不同的仲裁策略,在用户需要的时候可以按需要进行并行程序的建模,如图2所示。把可视化程序设计的通用性和直观性与STM的灵活性与可扩展性结合起来,会对提高并发程序的开发效率有很实际的帮助。
2.3事务同步
一个事务在成功提交之后,它对共享数据作出的修改后便对全体事务可见,在它正确提交之后任何事务再对同一共享对象的读写操作都是在这个对象新版本的基础上进行的。这就要求要有一个全局的统一时钟来标识对象的新旧版本,这个时钟对STM系统的全体事务都是一致的,一个事物在访问一个对象时只需要拿这个对象当前版本的时间戳和系统的当前时间作比较就可以知道这个对象是否处在一个一致性状态。
2.4图形接口与算法实现
用户图形接口采用UML类图设计中的活动图来进行设计。活动是某件事情正在进行的状态,它在状态机中表现为有一系列动作组成的非原子的执行过程。活动图的图标包含对活动的描述,如果一个活动引发下一个活动,两个活动的图标之间用带箭头的直线连接,活动图中的一个活动代表一个事务,每一个活动都有一个开始时间,记作代表此活动事务的时间戳。UML活动图中包含的图形元素有动作状态、活动状态、动作流、分叉与汇合等。动作状态是指执行原子的、不可中断的动作,并在此动作完成后通过完成转换转向另一个状态。因为事务具有ACDI的特性,所以活动图中的动作状态对应到VPP STM系统中是指一个事务生命周期中执行的所有动作。一个活动图有很多动作或者活动状态,活动图通常开始于初始状态,这时VPP STM系统要进行初始化操作,即在视图模型搭建好之后,根据UML活动图中用户输入的数据对象初始化整个STM系统的数据集合O。这时启动VPP STM中的第一个事务Tstart:初始化事务的读写数据集合T0,记录事务开始的时间戳 timestamp。之后事务开始执行读写操作并提交,如果提交成功,那么更新T0中所有数据对象的版本信息V0。由于对象在运行时可能会存在两个或者多个并发运行的控制流,为了对并发的控制流建模,在UML中引入了分叉与汇合的概念。分叉用于将动作流分为两个或者多个并发运行的分支,而汇合则用于同步这些并发分支,以达到共同完成一项事务的目的。分叉可以用来描述并发线程,每个分叉可以有一个输入转换和两个或多个输出转换,每个转换都可以是独立的控制流。在VPP STM中,会在每一个分支结点根据结点的出度初始化所需的事务集合T(T1,T2,…),并将每个事务所需要执行的数据操作写入这个事务的读写集合,完成初始化后记录事务开始的时间戳。进入UML的分支后,每一个事务就单独执行自己的任务,在进行读写操作之前,事务首先要申请对共享对象的访问权限:在申请所有权时如果这个Ox现在被其他的Tx拥有, 则比较两个事务的timestamp,终止timestamp较大的(晚开始的)事务。否则获得这个Ox的所有权,并且在这个Ox的V(V1,V2,…) 中寻找一个时间戳小于此事务时间戳且最新的Vnew生成这个Ox的快照。申请到了访问权事务开始对共享数据对象的快照副本进行读写操作:进行读操作时,先在此事务的写集中查找,有则返回。如果没有就返回申请到的Vnew的值。进行写操作时,如果当前事务拥有这个Ox,就直接在事务的写集中进行修改。否则会先进行冲突检测,如果无冲突就申请这个Ox的所有权,若申请成功则把修改值添加到事务的写集中。在UML活动图中,汇合代表两个或多个并发控制流同步发生,当所有的控制流都打到汇合点后,控制才能继续往下进行。每个汇合可以有两个或多个输入转换和一个输出转换。相对的,在VPP STM系统中,事务读写操作完成后,如果没有冲突发生就确认提交:为相应的T0分配新版本,如果有数据更新则将 快照中的值写入新版本,记录提交的时间戳,并将新版本放入这个共享数据对象的版本信息集合中。如果遇到冲突则选用给定的仲裁策略进行事务的回滚操作,事务回滚后此事务的所有操作不对共享对象产生任何影响,在UML中,相当于重新回到分支点再进行一次事务的初始化操作。当所有的事务均提交成功后,整个UML活动图的执行任务才算完成。
3测试用例及实验结果
3.1测试用例
实验用Linklist benchmark来进行测试,在Linklist benchmark中,设定链表元素个数为2000、链表写操作占总操作数作百分比为20%。除了设定不同的账户和存取操作之外,VPP STM还可以用不同的仲裁策略进行设计。用VPP STM 对Linklist benchmark进行建模结果如图3所示。
3.2实验结果
实验环境:处理器:Inter Core 2 Duo CPU (2.66GHz) 内存:2.00GB操作系统:32位Windows 7专业版在上述硬件环境下对用VPP STM建模的Linklist benchmark进行测试,实验结果如图4所示。
用不同的冲突检测策略进行Linklist benchmark的测试结果如表1所示。
4结语
VPP STM将软件事务性内存用到可视化并行编程中,使得可视化并行编程变得相对简单并且灵活,通过对Linklist基准测试程序进行建模测试可以看出VPP STM可以解决实际的并行处理问题,对不同的用例采用不同的冲突控制策略可以更好地满足实际运用的不同要求。同时,实验结果表明,如果开启的线程过多,事务提交时发生冲突导致事务回滚的性能损耗会超过多线程并行处理所带来的性能提升,从而使得系统整体性能相对下降,如何提高事务提交的成功率也是今后研究工作中需要解决的一个问题。
参考文献
[1]Olukotun K,Hammond L.The Future of Microprocessors[J].ACM Queue,2005,3:26-29.
[2]Nir Shavit,Dan Touitou.Software transactional memory[C]//Sysmpos-ium on Principles of Distributed Computing,1997,10:99-116.
[3]Pascal Felber,Christof Fetzer,Patrick Marlier,et al.Time-Based Software Transactional Memory[J].IEEE Trans on Parallel and dis-tributed systems,2010,21:1793-1805.
[4]Maurice Herlihy,Victor Luchangco,Mark Moir,et al.Software trans-actional memory for dynamic-sized data structures[M].ACM Press,2003:92-101.
[5]Christopher Cole,Maurice Herlihy.Snapshots and Software Transac-tional Memory[J].Elsevier Science,2005.
[6]Zhang X Q,Peng L,Xie L G.Lowering Conflicts of High Contention Software Transactional Memory[C]//2008International Conference on Computer Science and Software Engineering.2008.
[7]胡长军,丁良,常晓东,等.面向并行程序设计的扩展UML建模[J].计算机工程,2007,34(1):86-93.
[8]徐祯.面向并行程序设计的可视化建模系统的研究与实现[D].天津大学,2007.
并行程序设计模型 篇4
关键词：自动测试系统；并行测试；数据共享
中图分类号：TP274文献标识码：A文章编号：1007-9599 (2011) 06-0000-01
Design of Parallel Test Software on ATS
Hong Chenghua1,Cao Juan1,Zhao Xuyang1,Mi Wenpeng2
(1.Teaching and Research Section 103,the PLA Second Artillery Academy,Qingzhou262500,China;2.Teaching and Research Section 202,the PLA Second Artillery Academy,Qingzhou262500,China)
Abstract:First studies how to meet auto test system（ATS) hardware architecture demands of parallel test by improving test instruments and hardware interface.Then,it focuses on using multi-process/multi-thread software technique to fulfill parallel test of auto test system（ATS).Several techniques are presented to resolve test instruments and data sharing between multi-processes,such as memory mapping,message posting and DLL.Several application examples are given to demonstrate these techniques.In actual applications,these techniques can be used by one or combined.
Keywords:Auto test system（ATS);Parallel test;Data sharing
自动测试系统（ATS）在相同时间内对单个被测对象（UUT）进行多路激励以及测量的测试任务称为并行测试。当单个UUT有多个I/O，且每个I/O都必须被独立测试时，并行测试可减少操作人员的数量，减少测试程序（TP）的运行时间，减少CPU和测试装置的闲置时间，但同时这样也会增加ATS的总处理能力。在进行并行测试过程中，UUT功能和参数所用的测试时间会比使用传统的串行测试方法要少很多。因此在实现并行测试在结合硬件结构设计的同时，重点在于并行ATS的软件开发。[1]
一、软件实现
在测试资源以及硬件接口模式满足要求的条件下，以串行ATS的架构为基础，软件实现的过程是通过采用多进程/多线程技术来完成ATS的并行测试。并且，DLL、消息传递和内存映射等多种技术中的不同组合方式可用于解决多进程之间的测试资源以及数据共享问题。
（一）ATS软件平台。ATS软件平台主要包括四部分：测试程序、管理程序、服务程序和驱动程序。图1展示的是ATS软件构成：
1.测试程序：多个测试子程序共同组成，一个测试子程序承担一个被测对象的测试项目选择、加／断电、测试和测试结果实时报告等功能。
2.管理程序：调用、分配测试资源，调用测试程序，修改、保存、查阅、打印与删除测试结果的文件。
3.服务程序：在软件平台中，除其它程序以外测试资源的校准程序、故障诊断程序、可互换程序以及辅助文件等。
4.驱动程序：完成测试资源激励或测量被测对象。
（二）多进程与多线程。多进程或多线程技术应用于ATS上要完成并行测试时的软件开发。在相应的进程中创建线程，线程的整个寿命周期都在进程中，这是一个动态的概念。而进程是一个静态的概念，它没有任何操作，只是线程依存的地方多任务是指同一时间可以有多个程序在内存中运行。主线程是在进程创建时自动创立的，主线程本身又可生成新的线程。[2]
二、硬件结构设计
测试硬件接口模式以及测试软件运行模式的限制导致现在广泛使用的电子装备通用ATS虽然可以测试多种UUT，但大多沿用串行测试工作方式，不能同时对单个UUT的多路I/O和多个UUT同时完成测试。因此在串行ATS升级为并行ATS的过程中，首先必须进行系统硬件结构的改进设计。
（一）测试资源的选择。个别测试资源在工作模式上只能支持串行测试，因此，并行测试系统中应采用支持多通道同时并行测试的测试资源。
（二）接口模式的改进。串行ATS与UUT之间的连接方式是由单个UUT通过适配器实现与测试系统的相连，因此，ATS在相同时间内只能对单个UUT完成测试。
并行ATS与UUT之间的连接方式可采取多个UUT同时接到ATS上，来实现并行测试。
三、测试资源和数据共享技术
由于在多线程程序中，调试程序是一个固有的难题，所以如果单个UUT的测试流程的存在形式是多线程，那么测试流程的调试就会比较困难。调试程序又是编写完测试程序后的一个必要步骤。所以，建议测试程序的存在形式采用进程。
同时如果一个测试程序采用一个进程，那么多个测试程序之间的测试资源与数据的共享就是一个难题。运用以下几种技术可以解决这一难题。
（一）DLL。驱动程序支持了测试资源的运行。在并行自动测试系统中，一个测试资源的驱动程序有可能会在多个进程中得到应用，所以它应该是安全并可以重载的。
在并行测试的测试资源的调用过程中，应该分配好管理程序中的通道，禁止在同一时间不同的测试程序调用同一个通道。
（二）内存映射文件。为了方便管理程序和不同的测试程序查看与修改，在ATS中，可以在内存映射文件中存放测试资源的使用情况。如果需要在多个进程之间形成内存的共享，可以采用如下方法：在一个进程中创建一个文件并映射之，然后另一个进程可以通过打开和映射该件，这样就可以将它作为自己进程的内存来使用。[3]
（三）消息传递。用于一个进程发送数据到其它进程。程序对整个系统和资源的管理采用如下方法：在一个测试程序启动之后，给管理程序发送一个消息，告知管理程序哪一个测试程序启动了，且占用了哪些测试资源。
四、结论
各国的军事装备部门以及相关厂商对并行测试作为新一代自动测试系统的一个发展方向给予了相对的重视，也使之成为了一个学术界研究的热点。软件开发技术以及硬件测试资源被并行测试技术的研究推动发展。
参考文献：
[1]卓家靖,孟晨,方丹.并行自动测试系统硬件结构研究仁[J].计算机测量与控制,2009,17(5):820-821
[2]飞思科技产品研发中心.Delphi下深人Windows核心编程[M].北京:电子工业出版社,2003
[3]Jeffrey Richter.Windows核心编程[M].黄陇,李虎.北京:机械工业出版社,2008
并行程序设计模型 篇5
GPU已经不再局限于3D图形处理了, 由最早以游戏为主要代表的图形应用, 到现在大规模并行超级计算机和处理大批量并行浮点运算, 尤其在动画渲染、气象研究、能源勘探、生物医疗、金融分析、地理信息系统等各个领域发挥着重要作用。“天河一号A”超级计算机是GPU应用的典型代表, 它采用了GPU和CPU混合架构, 并使用了超过14000颗CPU, 其中配备了2048颗我国自主研发的飞腾FT-1000八核心处理器, Tesla M2050 GPU7168颗, 总运算能力2.5PFLOPS, 曾在2010年11月获得全球速度最快超级计算机的头衔。它的成功已经充分证明了GPU在数据计算方面的重要性。
为了提高DCT变换的速度以及扩展更多的应用, 文中主要分析面向Open CL模型的DCT变换的并行化。通过结合Open CL语言和GPU的并行特性, 充分发掘其中可以并行计算的部分, 针对基于GPU的DCT变换的性能进行优化。
1 Open CL
随着GPU可编程性不断增强, 各种编程工具的不断推出, 例如Nvidia的CUDA、AMD的Brook+、Apple的Open CL、IBM的CBE、Intel的Larrabee, 这些工具使GPU通用计算编程的复杂性大幅度降低, 已逐步成为一种新型可编程高性能并行计算资源。对于编程人员来说他可以选择不同的语言或者API进行编程, 文中选用Open CL编程。
1.1 Open CL的组成
Open CL最早是由Apple公司提出, 在Intel、AMD、NVIDIA等巨头的参与下, 2008年12月已形成第一版标准。Open CL全称Open Computing Language[3,4], 即“开放计算语言”, 为编写跨平台的GPU计算的程序提供了方便。
Open CL的组成包含三个部分, 如下:
1) Open CL编程语言。又被称为Open CL C编程语言。它是基于ISO C99标准的一个扩展子集, 主要用来编写Kernel程序的语言, 能运行在任何类型的微处理器上。
2) Open CL平台API。它定义了协同执行的单个处理器程序找到Open CL设备所用的函数和函数的功能, 以及Open CL应用创建上下文的函数。
3) Open CL运行时API。它用于管理上下文进行命令队列的创建和运行时发生的其他操作。
图形里面也有很多API, 比如Open GL、Direct X是针对图形的, Open CL是针对并行计算的API。这些构成便于主机程序启动Kernel程序, 并为并行计算提供了一个有效的开发平台。Open CL作为业界公认的第一个异构计算开发语言标准, 正逐渐被各主要计算平台所采用。文中采用的异构处理平台为多核CPU和GPU。
1.2 Open CL平台模型
Open CL平台模型为开发人员提供了在计算设备上执行的Open CL C函数。主机 (Host) 是Open CL平台模型中的核心设备, 它能够连接一个或多个Open CL计算设备 (Compute Device) 。其中每个Open CL计算设备又由一个或多个计算单元 (Compute Unit) 组成, 每个计算单元由一个或多个处理单元 (Processing Element) 组成, 各种计算操作都是在处理单元中完成的。例如AMD Radeon HD7970包含有32组CU, 每组CU包含64个PE。Host端是Open CL程序的入口和出口, 控制着计算设备中处理单元需要进行的计算, 从而实现管理平台模型中所有计算资源。计算命令通过应用程序从Host端向各个Open CL计算设备的处理单元进行传送。GPU通过单指令多数据 (SIMD) 指令类型来支持数据并行计算。在单指令多数据流的结构中, 单一控制部件向每条流水线分派指令, 同样的指令被所有处理部件同时执行。
Open CL采用存储器类型的层次结构, 如图1所示[5], 开发人员可以利用这些存储器来编程。这些存储器类型包括:全局、常数、局部和私有存储器。全局存储器可以由主机程序动态地分配, 并支持主机和设备的读写访问操作。常数存储器支持主机的读写访问操作, 并且支持设备的只读访问操作。局部存储器可以由主机动态地分配, 也可以由设备代码静态地分配。主机不能访问Open CL中的局部存储器。私有存储器在计算单元内部, 与处理单元能交换数据。
2 DCT在GPU上的并行化实现
为了方便开发人员在GPU平台上进行编程, 提高开发效率, 目前, 各大厂商提供了很多高效、直观的开发平台, 即CAL、Brook+、CUDA、Open CL等, 这些平台有各自的特点。文中主要从Open CL角度进行分析DCT变换的并行化。
2.1 DCT变换的工作原理
1974年, Ahmed, Natarajan和Rao首先提出了DCT (Discrete Cosine Transform) 算法, DCT全称为离散余弦变换[6,7,8]。DCT变换与K-L变换的准最优正交变换非常相似, 能将图像的大部分能量集中到直流系数中, 并且其算法快速有效, 因而有利于软件和硬件实现。K-L变换 (Karhunen-Loeve Transform) , 由卡尔胡宁 (Karhumen) 与勒夫 (Loeve) 分别提出[9]。其具有将图像能量集中于某些系数中的能力, 一个能把最多的能量集中于最少的系数上的变换所产生的重建误差最小, 但是采用实际电路完成十分困难。因此, 目前在MPEG-4和JPEG2000的静态纹理编码中主要采用DWT变换实现, 而其他多数图像和视频编码中选择采用DCT变换进行实现。
针对二维图像的DCT变换, 其变换过程如下:
1) 对图像块的每行进行一维DCT变换。
2) 对经行变换的块的每列再进行一维DCT变换。
其中, 一维DCT变换采用线性变换Y=HX实现, 它将N维向量X通过变换矩阵H转换成新的N维向量Y。公式如式 (1) 所示[10]:
DCT变换的变换核H第k行第n列的元素定义如公式 (2) 所示:
其中k=0, 1, 2..., N-1, n=0, 1, 2..., N-1
从式 (2) 可以证明得到, DCT变换核Hkn是为无理数, H是正交矩阵且DCT完全可逆的, 变换对于输入的整数图像数据而言, 进行DCT变换时需要进行大量的浮点运算, 容易导致图在像轻微失真, 另外还需要进行大量的乘法和除法运算, 软件和硬件不易实时实现, 这将不利于在实时的多媒体和视频领域的广泛应用, 尤其是在医学图像、遥感成像等特定领域是不允许的。
2.2 DCT变换的并行化
DCT变换在GPU上的实现步骤, 如下:
1) 将原始数据从Host端的内存传送到Device端的显存, 将原始图像分成8×8的块, 每个线程根据对应的索引号读取显存中某个块中的一列到GPU的内存中。
2) 每个线程根据对应的索引号先对某个块中的一列做一维8点DCT快速正变换, 再对变换以后的块中的某行做一维8点DCT快速正变换, 结果为变换后的块。
3) 每个线程根据对应的索引号把某个块中的一列从GPU的内存传送到显存中。
2.3 DCT变换的并行化实现
Open CL的执行模型可以分为两部分, 如图所示。一部分是在Host上执行的主程序, 另一部分是在Open CL设备上执行的Kernel程序, Open CL通过主程序来定义上下文并管理内核程序在Open CL设备的执行。
1) 主程序
执行在Host端的主程序, 如下:
2) Kernerl程序
执行在OpenCL设备上的Kernerl程序, 如下:
3 实验结果及分析
1) 测试环境
文中采用的的硬件和操作系统等配置如下:
(1) Windows 7 X64位操作系统;
(2) Intel (R) Core (TM) i7-3770 4核;内存8GB;500G硬盘;
(3) 显卡:AMD Radeon HD 5650、AMD Radeon HD 6950和AMD Radeon HD 7970。
2) 构建环境
构建OpenCL环境的具体步骤如下:
第1步:下载。
下载最新的AMD driver, AMD APP SDK。本实验中采用:
(1) AMD SDK:AMD-APP-SDK-v2.8-Windows-64.exe
(2) AMD Driver:12-10_win7_win8_64_dd_ccc_whql.exe
第2步:安装。
依次安装AMD Driver和AMD APP SDK。AMD APP SDK目前支持的IDE有:Visual Studio。在安装过程中会自动添加一部分环境变量。
第3步:查看。
在程序→运行→cmd中键入clinfo, 查看输出信息, 如果所有计算设备都能找到, 则安装成功。
第4步:编译。
编译SDK Sample中的样例。在$ (AMDAPPSDKSAMPLESROOT) samplesopencl目录下的Open CLSamples.sln解决方案, 包含了多个Open CL工程。用户可根据需要选择相应工程, 并设置为启动项目, 然后进行build和debug。可执行文件保存在$ (AMDAPPS-DKSAMPLESROOT) samplesopenclbin相应目录下。
第5步:当开发人员创建自己的Open CL项目时, 可以通过两种方法进行编译。
(1) 在解决方案资源管理器中按照向导建立工程, 并按照步骤4进行编译和调试。
(2) 用户可以在SDK中的模板工程 (Template) 对源码进行修改并编译执行。
3) 实验结果
实验结果如表1所示, 单位:ms。
通过测试, 实验结果表明, DCT并行化变换速度比原来常用的DCT变换速度有明显提高, 并且显卡性能越好, 采用并行化后, 速度提高越多, 节省了大量的时间。
4 结论
GPU作为一种非常有潜力的计算工具, 仍在不断发展。文中通过对面向Open CL模型的DCT变换的并行化方法的分析和实现, 探讨了Open CL的关键技术, 并且提出了一种把传统串行DCT快速变换映射到GPU的并行化方法, 在实验过程中, 对比采用C语言和Open CL语言编写的DCT变换, 基于Open CL开发的应用程序可以最佳地调用异构系统中的所有计算资源, 最大化发挥计算能力, 真正体现异构计算的高效节能优势。
参考文献
[1]Youngsub Ko, Youngmin Yi, Soonhoi Ha.An efficient parallelization technique for x264 encoder on heterogeneous platforms consist ing of CPUs and GPUs.Journal of Real-Time Image Processing, 2013 (01) .
[2]Changmin Lee, Won Woo Ro, Jean-Luc Gaudiot.Boosting CUDA Applications with CPU–GPU Hybrid Computing[J].International Journal of Parallel Programming.2013 (05) .
[3]Cheong Ghil Kim, Yong Soo Choi.A high performance parallel DCT with OpenCL on heterogeneous computing environment[J].Multi media Tools and Applications.2013.05 (64) :475-489.
[4]陈钢, 吴百锋.面向OpenCL模型的GPU性能优化[J].计算机辅助设计与图形学学报, 2011 (04) :571-580.
[5]李焱, 张云泉, 王可, 等.异构平台上基于OpenCL的FFT实现与优化[J].计算机科学, 2011 (08) :284-296.
[6]阮军, 韩定定.基于CUDA的DCT快速变换实现方法[J].微电子学与计算机, 2009 (08) :201-210.
[7]Wei-Jhe Hsu, Hsueh-Ming Hang, Yi-Fu Chen.Motion Estimation and DCT Coding Combined Scheme for H.264/AVC Codec[C].In ternational Computer Symposium.2013 (21) :413-421.
[8]Dariusz Rafal Augustyn, Sebastian Zederowski.Applying CUDA Technology in DCT-Based Method of Query Selectivity Estimation[J].Advances in Intelligent Systems and Computing.2013 (185) :3-12.
温特斯模型参数并行求解方法与应用 篇6
关键词：温特斯模型,并行计算,预测,压缩空气
空压机群在压缩空气生产过程中将消耗大量的电能,通过对机群的合理调度有助于提高能源的利用率,而合理调度取决于对压缩空气量需求的合理预测。针对压缩空气生产和使用的周期性特性,本文利用霍尔特-温特斯模型对时间序列趋势变化的预测特点,在分析压缩空气产能周期性和规律变化的基础上设计了一个符合实际的压缩空气产能预测模型。
温特斯模型中的一组平滑系数一般通过经验取值,取值的不同对预测的精度影响较大。为提高预测精度,常用穷举法,遍历平滑系数所有取值[1],该方法通常需要进行100万次以上的串行循环计算,所需计算时间长,效率低,而利用并行计算方法求解最优平滑系数,可减少计算时间,提高运行效率。
1 并行计算加速比
并行计算[2,3]通常针对具体问题,利用它内在的并行性设计并行算法,将其分解为互相独立、但彼此又有一定联系的若干子问题,分别交由不同处理机,按照并行算法完成问题求解。
并行计算运行时间分析是衡量并行算法最重要的标准之一,其用并行加速比来反映并行算法计算效率的高低。根据Amdahl定律,并行算法的绝对加速比为:
式(1)中:Ts为标准串行算法的运行时间,Tp为并行算法的并行时间。
2 温特斯模型基本理论
2.1 温特斯模型原理
温特斯线性和季节性指数平滑预测模型[4]由霍尔特-温特斯提出,是一种把具有线性趋势、季节变动和规则变动的时间序列进行因素分析,并与指数平滑法结合起来的季节预测模型。该模型由三个平滑方程式组成。首先分别对长期趋势St、趋势增量bt、季节变动Ft,作指数平滑,然后由这三个平滑结果建立预测模型,外推得到所需预测值。该模型特别适用于既有线性趋势又有季节变动的时间序列短期预测。
温特斯线性和季节性指数平滑预测模型的三个平滑方程[5,6,7]为
其中:St代表稳定性;bt代表趋势性;Ft代表季节性;L为季节或周期长度,如一年的月数、季节数等;Yt为t时期的实际值;α、β、γ为平滑系数,取值在(0,1)之间。
式(2)对指数平滑平均数St进行计算。第一项中消除了Yt中Ft-L即季节变化因子的影响。当t-L时期的值大于季节平均值时,Ft-L的值大于1,经除法运算后得到的值小于Yt,即表示消去了t-L时期Ft中大于季节平均值的差额;当Ft-L的值大于1时,情况相反。第二项中t-1时期的平均数St-1加上bt-1即趋势变化平均数,提高了指数平滑结果的准确性。通过该式计算出的St,即可代入式(3)、式(4)式进行运算。
式(3)用来修匀平滑时间序列的变化趋势值。St-St-1的差值存在随机干扰,因此用平滑系数β进行加权,用1-β对bt-1进行加权。
式(4)对季节因子的指数平滑平均数Ft进行计算,为季节因子(Yt/St)和季节数据Ft-L加权运算之和。Ft是t时期的实际值Yt与时间序列指数平滑平均值St的比值,其中Yt既包括季节性也包括随机性,St不包括季节性。
根据式(2)～式(4)可以求得k个时期以后的预测值,公式如下:
k的取值一般在(1,L)之间,若取值在(1,2L)之间,则表示要预测下两个周期。
2.2 温特斯模型的求解步骤
在使用温特斯模型前,首先要判断历史数据是否存季节性波动,若不存在,则不能使用该模型。温特斯预测模型的求解步骤如下:
(1)确定季节性周期长度L;
(2)选取平滑系数α、β、γ,一般依靠经验取值,取值范围在(0,1)之间,本文运用并行计算方法求取一组最优平滑系数;
(3)确定初始值,一般初始值由以下式(6)～式(8)给出,也可由其它方法确定;
(4)利用式(2)～式(4),确定St、bt、Ft这三个值;
(5)通过式(5),获得所需预测值。
3 预测模型软件设计
3.1 模型参数的并行求解
本文选取2010年1月4日至2010年1月31日四周的历史压缩空气日产数据,并对2010年2月1日至7日这周的日产压缩空气量进行预测。通过对提取的数据分析,如图1所示,周一至周五的日产压缩空气量远远高于周六的产量,周日的产量相较于周六又有大幅回升,具有明显的周期性,适用于温特斯模型。因此本文中将季节性周期长度定为7,以一周为一个周期。
平滑系数α、β、γ的值,一般依据经验取值,或通过穷举获得。前一种方法所求得的预测结果一般不理想,而后一种方法计算量大,三个平滑系数分别从0.01取值至0.99,三重嵌套循环,需要进行100万次以上的计算,串行计算所需时间长、效率低。为减小计算时间提高计算效率,本文所设计的软件利用Parallel类及并行循环,并发枚举出α、β值,在[0.01,0.99]区间内进行任意的组合,γ的值依旧顺序遍历获取。当实际值与预测值的相对误差和最小时,即可以认为该组平滑系数为最优。通过实验得到的一组最优平滑系数为:α=0.15,β=0.14,γ=0.01。
3.2 结果分析
并行效率的高低可以利用Amdahl定律即加速比来评价。在Intel Core i7四核处理器,4G内存的同一硬件环境下运行,串行计算所用的执行时间为413秒,并行计算所用的执行时间为217秒,加速比为P=1.903。由此可见并行算法比串行算法提升了近一倍的性能,提高了运算速度。
对预测结果的精度和可靠性进行评价是预测分析的重要组成部分,常用多项误差形式来对预测结果进行评价,以此来判定各种预测方法的优点和可行性。常用的误差指标如下,其中Yt是序列在t时刻的实际值,
(1)绝对误差(Absolute Error):
(2)相对误差(Relative Error ):
(3)归一化偏差(Normalized Bias):
通过运算得到:当平滑系数取值最优时,预测值与实际值相对误差和最小。如表1所示,所得到的预测值相对误差均小于10%,最低值达到0.03%,平均相对误差为3.89%,归一化偏差为0.04。如图2所示,第五周的预测值的趋势变化与实际值的趋势变化基本一致,表明该模型预测精度较高,可适用于短期日产压缩空气量的预测。
4 结论
霍尔特-温特斯模型是一种三参数指数平滑模型,适用于线性趋势、季节变动和规律变动的时间序列问题。将并行计算引入到温特斯预测模型的最优平滑系数求解,不仅提高了计算效率,而且达到了预期的预测效果,预测得到的数据将为能源生产的任务调度、制定高效节能的生产计划提供决策支持。
参考文献
[1]赵嶷飞,王红勇,张亮.用霍尔特-温特斯模型预测航空运输总周转量.中国民航大学学报,2007;25(2):1—3,11
[2]王鹏,吕爽,聂治,等.并行计算应用及实战.北京:机械工业出版社,2008
[3] Wang Hao,Fu Xudong,Wang Guangqian.A common parallel com-puting framework for modeling hydrological process of river basins.Parallel Computing,2011;37:302—315
[4] Grubb H,Mason A.Long lead-time forecasting of UK air passengersby Holt-Winters methods with damped trend.International Journal ofForecasting,2001;17:71—82
[5]牛东晓,曹树华,卢建昌,等.电力负荷预测技术及其应用.北京:中国电力出版社,2009
[6]张晓庆.关于线性季节加法趋势预测模型的探讨.统计与决策,2005;(9):22—23
并行程序设计模型 篇7
人类在享受互联互通和信息共享带来的便捷与效益的同时，网络技术发展过程中对安全性的忽视，导致网络环境中存在各式各样的安全隐患，严重威胁着网络运营及合法用户的信息安全。因此，寻找并弥补威胁网络关键资源的脆弱性是提高网络安全性的一种有效方法。文献[1]基于逻辑推理的方法，首先将最优弥补求解问题转化为布尔表达式；然后求解该布尔表达式的析取范式，从而得到所有的弥补措施；最后通过分析比较得到最优弥补建议。该方法在最坏情况下具有不可避免的指数时间复杂度，无法应用于网络规模较大的真实目标网络系统。文献[2]提出采用归纳有序二元决策图（ROBDD）的方法求解最优弥补。该方法可以有效地获取攻击图的最优弥补，但在该方法中，未对脆弱性进行度量标准的说明，因此在实际应用上具有一定的局限性。
由于求解最优弥补问题是NP完全性问题，对于NP完全性问题，采用启发式搜索方法可以更快地获得结果。并行遗传算法[3,4,5,6]具有以下优势：覆盖面大，利于全局择优；对问题的依赖性较小，求解的鲁棒性较好；具有并行计算的特点，可以用大规模的并行计算来提高计算速度；特别适用于复杂大系统问题的优化求解，但其存在收敛速度慢、局部搜索能力差等不足之处。并行遗传算法可以克服经典遗传算法的不足，提高遗传算法求解的速度和质量。基于此，本文将攻击图与并行遗传算法相结合，提出了一种基于并行遗传算法的网络最优弥补模型（Optimal Network Hardening Model Based on Paralle Genetic Algorithm,PGA-ONHM）。
1 最优弥补问题的转化
虽然并行遗传算法可以克服经典遗传算法的不足，特别适用于复杂大系统问题的优化求解[7,8,9]，但在具体的实现过程中，其适应度函数不能有约束条件，适应度函数的值需大于0，其最终得到的最优个体适应度函数值为最大值。求解最优弥补是有约束条件的，即需要满足约束条件g(x)=0，然后在满足此条件的弥补策略中寻找最优弥补。
为了能够将攻击图与并行遗传算法相结合，从而找到适用于求解大规模复杂目标网络系统最优弥补的模型，本文首先通过建立相应的数学模型，将最优弥补问题转化成一个带有惩罚的非约束优化问题，然后利用并行遗传算法得到其最优弥补的近似解。
令c1,c2,⋯,cn为目标网络系统的初始属性点，cost(ci)(i=0,1,2,⋯,n)为弥补初始属性节点ci需付出的成本代价，通过总结分析，并进行大量的模拟实验，建立的数学模型为：
通过此数学模型，可以将带有约束条件g(x)的最优弥补问题转化成能够应用并行遗传算法的非约束优化问题。r为惩罚因子，目的是设法对违背约束条件的个体给予惩罚，即当弥补策略不能保证目标网络系统正常、安全运行时，给予该策略一定的惩罚，使该策略所消耗的成本代价适应度放大，这样更易于选择最优弥补。
2 PGA-ONHM模型的设计与实现
2.1 并行遗传算法设计
目前，并行遗传算法的模型主要有三种：主从式、粗粒度、细粒度。其中，粗粒度模型首先将初始群体按照处理器数量分割成若干个子群体；然后将子群体分配给不同的处理器相互独立地并行执行，每经过一定的进化代，各子群体间会交换若干个体以引入其他子群体的优秀基因，防止未成熟收敛的发生。由于该模型通信开销少，而且适应性强、应用广，因此本文采用并行遗传算法的粗粒度模型。
(1）初始化总群体及子群体参数
总群体大小的选取应适中，过小则不易全局最优解，反之则运算量过大，收敛速度减慢。通常取编码长度的2倍。若总群体的大小为N，依据处理器数量将总群体均匀划分为U个子群体，则各子群体的大小为M=N U,M>1。
(2）子群体间的通信方式
由于从进程都是各自独立地运行遗传算法，每个进程到达符合迁移条件所需要的时间是不同的，因此，为了消除等待同步耽搁的时间，本文采用子群体间异步通信的方式。当主进程收到从进程提交的个体后，将染色体存放在缓冲区，并将缓冲区中上次收到的染色体发送给它。这样不仅降低了迁移算子的复杂度，同时省去了等待进程同步的时间，提高了运算速度。
(3）子群体的迁移策略
迁移是并行遗传算法引入的一个新算子，它是指进化过程中子群体间交换个体的过程，迁移策略主要控制的参数如下：
(1)迁移规模：每次迁移个体的数量。
(2)迁移率：个体迁移的时间间隔，即进化几代迁移一次。
(3)迁移策略：在确定迁移规模和迁移率后，就要确定哪些个体进行迁移。对于迁移个体的选择，本文采用子群体中的最优个体向外移民的策略。
(4）终止条件
程序终止的方式有两种：一是根据目标网络系统的规模，设定最大迭代次数，当迭代次数达到最大迭代次数时，则程序结束；二是在进化若干代后，若新一代中存在某个染色体的选择概率超过80%（此概率由用户设定），或者新一代中所有的染色体都相同，则程序结束。
2.2 子群体参数设计
(1）编码
编码的基本要求是为染色体的基因型（代码串）和表现型（参数值）建立对应关系，从而决定初始化种群。根据实际的应用需求，本文采用二进制代码进行编码，则对应关系就是二进制与十进制的转换关系。
(2）适应度函数
适应度函数是经典遗传算法中进行选择、交叉和变异操作的依据，该函数的选取是一个技巧性很高，但理论上的研究又很不充分的复杂问题。通过大量的模拟实验和分析，本文采用的适应度函数ti为：
其中r采用动态惩罚函数法。该方法在遗传算法的进化初期，为了保证算法能在全局范围内进行搜索，选取较小的惩罚因子，但在遗传算法的后期，为了增强局部搜索能力，将选取较大的惩罚因子。
(3）遗传算子
选择为经典遗传算法基本的遗传算子之一，常用的选择方法有期望值法、适应度概率法以及最佳个体保存法。文献[5]对以上三种方法的遗传算法性能进行对比，实验表明，采用期望值法的经典遗传算法，其离线性能与在线性能均高于采用另外两种方法。采用适应度概率法时可能会产生随机误差，这种误差在群体数较大时更易发生。因此，本文采用期望值法，且计算选择概率的公式为Pi=ti∑ti，其中：∑ti表示适应度值的总和；ti表示种群中第i个染色体的适应度值。
交叉为经典遗传算法基本的遗传算子之一，即将两个染色体的基因进行互换产生新的后代。与选择操作相比较，该操作能使基因排序变化更加灵活，实现真正意义上的人为重组，适用于大范围操作。在具体操作中，交叉分两个步骤：第一步是选择两两匹配的对象，第二步是决定交换点及交换规则。常用的交叉方式有单点交叉、双点交叉、按序交叉和位置交叉等，根据实际应用情况，本文采用按序交叉。
变异为经典遗传算法基本的遗传算子之一。由于本文采用二进制代码进行编码，即就是将基因值取反。
2.3 PGA-ONHM模型的实现
利用PGA-ONHM模型求解目标网络系统的最优弥补时，首先由主进程设定总群体大小、初始化子群体、设定子群体的参数（交叉、选择、变异等），把生成的子群体分配给从进程；然后子群体在从进程中进行独立进化，当达到预定代数时，向主进程发出迁移申请，主进程执行迁移策略，当从进程满足终止条件时，向主进程输出最优解；最后主进程从所有从进程输出的最优解中选择一个最优解。算法主进程流程图如图1所示。
各从进程独立地运行遗传算法进行进化，首先根据子群体参数设计对个体进行染色体二进制编码，并利用式（2）和式（3）计算每个个体的适应度函数，得到每个个体的选择概率，然后对父本进行选择、交叉、变异操作，产生下一代个体。当进化的代数满足迁移率时，向主程序返回最优解。从进程算法流程如图2所示。
2.4 算法复杂度分析
设目标网络系统中初始属性节点数量为C，迭代次数上限为D。
在主进程中，首先根据初始属性节点数量，从所有弥补策略中平均选取N个个体组成总群体，然后将总群体划分为U个子群体，一般来说N=2C，所以时间复杂度为：
在从进程中，子群体的大小为M=N U，各个子群体独立运行遗传算法，其时间复杂度主要从以下几部分分析：
(1）二进制编码。对每个个体进行二进制编码，时间复杂度为O(M)。
(2）适应度函数计算。对每个个体进行适应度函数计算，因为式（2）的时间复杂度为O(C)，所以适应度函数计算的时间复杂度为O(MC)。
(3）选择。首先计算每个个体的选择概率，然后将选择概率小的个体替换为选择概率大的个体，时间复杂度为O(M)。
(4）交叉。随机选择父本中的两个个体进行交叉操作，从而产生新的个体，时间复杂度为O(M2)。
(5）变异。根据变异概率，对个体执行变异操作，时间复杂度为O(M)。
(6）迁移。根据迁移率，向主进程提交当前子种群中选择概率大的个体，时间复杂度为O(M)。
当每一代进化未满足终止条件时，算法进行迭代。因此，遗传算法的时间复杂度为O(MC)⋅O(D)=O(2DC2/U)。
3 实验结果与分析
为了验证PGA-ONHM模型的可行性、有效性和可扩展性，本文从不同分析角度做了两组实验，并对实验结果进行了分析。实验环境如下：服务器PowerEDGE R710，操作系统RetHAT V5.4，内存32 GB,CPU 2.26 GHz。
3.1 算法性能验证实验
由算法性能分析可知，该算法性能与目标网络系统中初始属性节点数量C,迭代次数D,子群体U等参数有关。为了验证不同网络环境下这些参数对算法性能的影响，在得到最优解的前提下，分别设计了如下两组实验。
第一组实验验证初始属性节点数量不同时，单次迭代的平均计算时间如图3所示。由图3可知，单次迭代的平均计算时间随着初始属性节点数量C的增加呈多项式增加趋势。
第二组实验验证子群体数量（即处理器数量）对算法性能的影响。令初始属性节点数量为500，当子群体数量不同时，单次迭代的平均时间如图4所示。由图4可知，单次迭代的平均计算时间随着U的增加呈减小趋势。
由上述两组实验结果可知，在PGA-ONHM模型中，算法CPU消耗的时间随着初始属性节点数量C的增加呈多项式增加趋势，随着子群体数量U的增加呈减小趋势，实验结果与算法性能分析结果一致。
3.2 算法对比实验
(1）经典遗传算法和并行遗传算法对比实验，实验结果如表1所示。表1列出了在初始属性节点数量不同的情况下，求解最优弥补时两种算法的平均迭代次数和单次迭代的平均计算时间。
从实验结果可以看出：一方面，针对同一目标网络环境，无论是平均迭代次数还是单次迭代的平均计算时间，并行遗传算法比经典遗传算法都要优越，其主要原因是在并行遗传算法的具体实现过程中，首先将总群体分成若干子群体，然后将子群体分配到各自的处理机上，独立地进行遗传算法的进化操作，实现了从全局角度开发群体进化的并行性，从而提高了计算效率；另一方面，并行遗传算法具有良好的可扩展性，当初始属性节点数量达到2 000时，单次迭代的平均计算时间也不过7 ms。
(2）加速比实验。目前公认的评价并行遗传算法性能的指标是加速比，即并行遗传算法与经典遗传算法完成等量工作所耗时间的比例，它标志着一个并行遗传算法的好坏。本文在相同的硬件环境下，对同一目标网络环境通过改变处理器数量，进行了加速比实验，实验结果如表2所示。加速比和处理器数量的关系如图5所示。由图5可知，加速比与处理器几乎呈线性关系，因此，本文所提并行遗传算法可以得到较好的加速比，是行之有效的并行手段。
4 结论
PGA-ONHM模型通过建立数学模型将攻击图与并行遗传算法相结合，得到最优弥补的近似解。为了验证该模型的可行性、有效性和可扩展性，本文从不同的分析角度做了两组实验，实验结果表明：CPU消耗时间随着初始属性节点数量的增加呈多项式增加，随着子群体数量的增加呈减小趋势；无论是平均迭代次数还是单次迭代的平均计算时间，并行遗传算法比经典遗传算法都要优越；加速比与处理器呈线性关系；能够克服局部最优解的问题，可以适用于大规模复杂的网络系统。
参考文献
[1]JHA S,SHEYNER O,WING J M.Two formal analyses of attack graphs[C]//Proceedings of 15th IEEE Conference on Computer Security Foundations Workshop.[S.l.]:IEEE,2002:49-63.
[2]NOEL S,JAJODIA S,O′BERRY B,et al.Efficient minimumcost network hardening via exploit dependency graphs[C]//Proceedings of 19th Annual Conference on Computer Security Applications.[S.l.]:IEEE,2003:86-95.
[3]WANG L Y,NOEL S,JAJODIA S.Minimum-cost network hardening using attack graphs[J].Computer communications,2006,29(18):3812-3824.
[4]HOMER J.From attack graphs to automated configuration management:an iterative approach[R].Kansas:Kansas State University Technical Report,2008.
[5]SI J Q,ZHANG B,MAN D P,et al.Approach to making strategies for network security enhancement based on attack graphs[J].Journal on communications,2009,30(2):123-128.
[6]CHEN F,WANG L Y,SU J S.An efficient approach to minimum-cost network hardening using attack graphs[C]//Proceedings of 2008 the 4th International Conference on Information Assurance and Security.Naples:IEEE,2008:209-212.
[7]CHEN F,ZHANG Y,SU J S,et al.Two formal analyses of attack graphs[J].Journal of software,2010,21(4):838-848.
[8]CHEN F.A hierarchical network security risk evaluation approach based on multi-goal attack graph[D].Changsha:National University of Defense Technology,2008.
并行程序设计模型 篇8
器件的模型和模型参数提取是电子设计自动化(EDA)领域的关键工作[1]。采用遗传算法进行半导体器件模型参数提取是近年来兴起并被广泛使用的一种参数提取方法[2,3]。遗传算法全局搜索能力强、不需进行繁琐的求导运算,不依赖参数初始值等特点,理论上来说只要有足够的迭代次数种能找到最优解[4]。但是,由于遗传算法是一种搜索类算法,较之传统的基于梯度进行迭代计算的解析算法,每进行一次迭代所需要的时间较长,计算量有了显著增加,而且对许多复杂问题而言,例如采用的全局优化策略提取复杂模型的大量参数时,标准遗传算法的求解效果往往不是解决这个问题的最有效的方法,必须对算法进行修改与优化,这些因素无疑大大增加了遗传算法的计算量,为此必须考虑算法的耗时问题。本文针对遗传算法自身的耗时问题,讨论了并行遗传算法的特点,并以主从式遗传算法为例,证实了并行计算在参数提取工作中的可行性。
2 并行遗传算法
为了有效的解决遗传算法(GA)在模型参数提取过程中的耗时问题,提高GA的运行速度,采用并行遗传算法(PGA)是提高搜索效率的方法之一。并行遗传算法[5,6]主要有主从式并行遗传算法、粗粒度并行遗传算法和细粒度并行遗传算法。
2.1 全局PGA模型-主从式模型(master-slave model)
如图1所示,主从式模型分为一个主处理器(master)和若干个从处理器(slaves)。主处理器监控整个染色体种群,并基于全局统计执行选择等全局操作;从处理器接收来自主处理器的个体进行适应度评估等局部操作,再把计算结果传给主处理器。
主从式模型的优点是简单,保留了串行GA的搜索行为,对计算机体系结构没有严格要求,适合运行在共享存储和分布式存储的并行计算机上。如果适应度估值操作比其他遗传算子计算量大的多时,这是一种非常有效的并行化方法。
2.2 粗粒度PGA模型-分布式模型(distributed model)
该模型又称分布式、MIMD、岛屿模式遗传算法模型。在处理器个数较少的情况下,我们可以将群体分为若干个子群体,每个子群体包含一些个体,每个子群体分配一个处理器,让它们相互独立地并行执行进化。为了防止子群体早熟,每经过一定的间隔(即若干进化代),各子群体间会交换部分个体以引入其他子群体的优秀基因,丰富各子群体的多样性。除了基本的遗传算子外,粗粒度模型引入了“迁移”算子,负责管理区域之间的个体交换。如图2所示,通常存在两种迁移实现:岛屿模型、踏脚石模型。
2.3 细粒度PGA模型-分散型(fine-grained model)
细粒度模型又称为邻域模型(neighborhood model)或细胞模型(cellular model)模型。如果并行计算机系统的规模很大,理想情况下处理器多到可以与染色体一一对应,则我们可以将每个个体分配一个处理器,让它们相互独立地并行执行进化,这样就能获得并行遗传算法的最大可能的并发性。如图3所示,在细粒度模型中,通常处理器被连接成平面网格(grid),每个处理器上仅分配一个个体,选择和交叉只在网格中相邻个体之间进行,所以网格上的邻域关系就限定了个体空间上的关系。由于对处理器数量的要求很高,所以细粒度模型的应用范围不广。
3 基于MPI的主从式遗传算法的的实现
3.1 总体构想
我们采用的主从式并行模型分为一个主处理器(master)和若干个从处理器(slaves)。主处理器监控整个染色体种群,并基于全局统计执行选择等全局操作;从处理器接收来自主处理器的个体进行适应度评估等局部操作,再把计算结果传给主处理器,其个体的分配过程是这样的:假设种群规模为N,优化模型参数变量个数为M。适应度评估时,程序传给评价函数N个长度为M的向量。并行的任务是master处理器将这个N个长度为M的向量平均分配到各slaves处理器做适应度计算,计算结束后,评价函数返回N个适应度给master处理器。计算各处理器分得的染色体个数的方法是,首先计算出每个处理器至少分配到的染色体个数为Ave Num=N/Size,如果处理器个数不能整除行数,这样将有部分处理器分得到(Ave Num+1)个染色体,规定多余的染色体分配到编号小的处理器上。
3.2 并行中的消息传递机制
另外,需要注意的是,仅仅依靠例如C,C++,java等编程语言所编写的程序是无法实现上面叙述的染色体在各处理器之间的传递任务。因为,在并行计算环境中,每个进程均有自己独立的地址空间,一个进程不能直接访问其它进程中的数据,因而,在进行并行计算的任务之间进行的数据传输必须通过消息传递机制。消息传递机制,是指用户必须显式地通过发送和接收消息来实现处理器之间的数据交换。
本文采用的是MPI(Massage Passage Interface)消息传递接口。MPI是一个很好的数据传递软件平台,可以通过调用MPI库函数来进行进程调度以及任务间的通信。它实际上是一个消息传递函数库的标准说明,吸取了众多消息传递系统的优点,是目前国际上最流行的并行编程环境之一,其特点是通用性强(只要求网络支持TCP/IP网络协议)、系统规模小、技术比较成熟。本文通过调用MP的库程序来达到程序员所要达到的并行目的,使异构的计算机群体作为一个紧凑、灵活、经济的计算机资源来使用的并行环境。
3.3 共享内存多处理器主从式并行环境搭建
全局并行化模型并不限定计算机体系结构,它可以在共享内存和分布式内存计算机中高效实现。现在简单介绍一下两种并行编程的方法:分布式内存方法和共享式内存方法。
对于分布式内存的并行计算机,各个处理器拥有自己独立的局部存储器,不存在公用的存储单元,显然,这种方法的问题就产生于分布式内存的组织。由于每个节点都只能访问自己的内存,如果其他节点需要访问这些内存中的数据,就必须对这些数据结构进行复制并通过网络进行传送,这会导致大量的网络负载。他的优点是拥有很好的扩展性,有利于快速构造超大型的计算系统。
在共享内存多处理器计算机中构成并行环境,在共享式内存方法中,内存对于所有的处理器来说都是通用的。这种方法并没有分布式内存方法中所提到的那些问题。而且对于这种系统进行编程要简单很多,因为所有的数据对于所有的处理器来说都是可以使用的,这与串行程序并没有太多区别。这些系统的一个大问题是扩展性差,不容易添加其他处理器。
为了在微机环境下使用MPI构成分布式内存并行环境,只要将PC机联接局域网,然后在每台PC机上安装相应操作系统,并安装MPI软件包即可。分布式内存即种群被一个处理器存储。这个主处理器负责将个体发送给其它从处理器进行评估,并收集计算结果,进行遗传操作来生成下一代。
对于本文所采用的在共享内存多处理器计算机中构成主从式并行环境就更为简单,只要在PC机上安装操作系统(本文安装linux操作系统)和MPI软件包就可以实现并行环境了。在共享内存多处理器计算机中,种群可以保存在共享内存中,每个处理器可以读取被分配到的个体信息并将适应度写回,不会有任何冲突。
4 实验结果分析
将以上方法实现的基于MPI的主从式遗传算法应用于1.2um SOI MOS器件的阈值电压模型参数提取工作中。如图4所示,实验结果表明曲线拟合的效果很好,转移特性曲线最大误差都低于5%。采用并行计算后,参数提取的速度提高了接近2.5倍。
5 结论
从实际的测试效果来看,以上方法实现的程序的简洁有效,智能化程度很高,且具有较高的精确度。因此,本文提出的基于MPI的主从式遗传算法可以解决遗传算法在器件参数提取过程中的耗时问题。该方法简单易用,适合推广使用。
摘要：器件的模型和模型参数提取是电子设计自动化(EDA)领域的关键工作。采用遗传算法进行器件模型参数提取工作是近年来兴起并被广泛使用的一种参数提取方法。本文讨论了并行遗传算法的特点,针对遗传算法自身的耗时问题,提出了基于MPI的主从式遗传算法,并证实了并行计算在参数提取工作中的可行性。该方法简单易用,显著提升了MOS器件模型参数提取的速度。
关键词：MOS器件,模型参数,参数提取,器件模型
参考文献
[1]J.Liou A,Analysis and Design of MOSFETS:Modeling,Simulation,and Parameter Extraction[M].KLUWER ACADEMIC PUBLISHERS,1998.
[2]Kondo M,Onodera H,Tamaru K.Model adaptable MOSFET parameter extraction method using an intermediate model[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1998,17(5):400-405.
[3]Yang P,Chatterjee P K,An optimal parameter extraction program for MOSFET models[J].IEEE Transaction on Electron Devices,1983,30(9):1214-1219.
[4]Li Yiming.An automatic parameter extraction technique for advanced CMOS device modeling using genetic algorithm.Microelectronic Engineering,2006,41(4):1309-1321.
[5]康立山,非数值并行算法(第一册)-并行遗传算法[M].科学出版社,2003.
并行程序设计模型 篇9
SMP集群是目前国内外流行的并行计算机体系结构之一,它具备节点间分布存储和节点内共享存储的两级内存层次结构,提供了节点间和节点内的两级并行。在设计并行程序时如果同时考虑两种结构的特点,充分利用结构所提供的两级并行性,采用分布内存和共享内存相结合的编程技术,可获得更好的加速比和运行效率。分布内存并行程序设计主要采用消息传递机制,编程模型有消息传递接口(MPI)和并行虚拟机(PVM)等;共享内存并行编程可采用多线程机制(如POSIX)和编译制导(如OpenMP)[1]。混合编程模型是专门针对SMP集群提出的,它将这两种并行程序设计技术结合在一起,充分利用了SMP集群的两级内存层次结构特点,节点间采用分布式存储的消息传递进行通信,节点内利用共享存储进行通信,实现消息传递和共享变量编程的混合。
近年来,三维网格模型在几何建模、计算机图形学等领域得到广泛应用,寻找任意两个顶点间最短路径问题是三维网格模型的基本计算问题。而随着三维网格模型规模的不断扩大,对最短路径问题的计算量和复杂度也急剧上升,时间开销不断增大。将最短路径问题的并行求解在SMP集群平台下实现,可以通过利用SMP集群的两级并行特性来提高并行算法的效率。因此,本文对SMP集群上的粗粒度MPI并行算法进行改进,采用了节点间粗粒度MPI并行和节点内细粒度OpenMP并行的多粒度混合编程方法求解三维网格模型上的最短路径问题。实际性能测试表明,该三维网格多粒度混合并行算法在运行时间方面明显优于原来的粗粒度MPI并行算法,具有更好的加速比和执行效率。
1 SMP集群
1.1 SMP体系结构
SMP集群体系结构如图1所示。图1中显示了具有N个节点(每个节点为2个CPU) 的SMP集群体系结构,图中P/C指的是SMP节点中的处理器(Processor,即CPU)和该处理器的局部高速缓存(Cache)。在SMP中,多个处理器通过总线或交叉开关连接起来,并通过它们访问共享的内存区域和I/O设备,因而SMP具备均匀存储访问UMA结构,并有单一物理地址空间和处理器间低通信延迟的特性。SMP集群通过通信网络(例如Myrinet、以太网或高性能开关)把多个SMP节点连接起来,并且节点间可以通过消息传递进行通信[2]。
1.2 SMP集群的特点
1) 每个节点是一个SMP ,都可以作为独立的一个计算机系统来使用;
2) 每个节点上有一份独立完整的操作系统;
3) SMP集群具有两级存储机制:节点内共享存储和节点间分布式存储;
4) 两级的存储机制决定了SMP集群有两级并行机制:节点内为单地址空间的共享变量编程模型,而节点间为分布式存储的消息传递编程模型。
2 SMP集群混合编程模型
分布式存储体系结构下的并行编程模型主要有消息传递编程模型,它的特点是多地址空间、编程困难、可移植性好,其实现标准有MPI、PVM等。共享存储体系结构下的并行编程模型主要是共享变量编程模型,它具有单地址空间、编程容易、可移植性差等特点,其实现标准有OpenMP和Pthreads等。SMP集群因为同时兼顾了计算性能和可扩展性的两方面,已经成为并行计算机体系结构的主要发展趋势。由于SMP集群同时具备共享存储体系结构和分布式存储体系结构的特点,传统的共享存储体系结构和分布式存储体系结构下的编程模型已经不再完全适用于它,需要给出一种新的编程模型来综合利用这两种模式的优点。
2.1 混合编程模型的实现机制
SMP集群混合编程模型的实现机制有很多种。SMP集群的节点间是分布存储,无疑消息传递模型MPI是分布存储编程的最佳选择。节点内的共享存储编程机制分别有Thread和OpenMP两类,Thread代表所有直接利用线程来实现节点内的并行化计算的模型,例如Linux Threads或POSIX Threads;OpenMP是基于编译制导的共享存储编程模型。因此,有两类混合编程机制:Thread(节点内)+MPI(节点间)和OpenMP(节点内)+MPI(节点间)两类。
2.2 两种混合编程模型比较
编程模型的选择主要取决于易用性与否和计算性能的好坏,从这两个角度分析OpenMP+ MPI优于Thread+MPI[2] 。主要原因是OpenMP和Thread都是由操作系统支持的线程实现,OpenMP直接提供了大量的并行操作语句,封装了线程的同步和互斥操作,而使用Thread模型时却还要考虑繁杂的线程间的同步和互斥,易用性远远不及OpenMP;另外Thread模型是一种低级的方法,它一般使用库方法,而不是编译制导法,这种方法会妨碍编译优化。综合权衡各种因素对程序性能的影响,OpenMP+MPI是更适合于SMP集群的混合编程模型。
3 MPI+OpenMP混合编程模型
MPI和OpenMP具有很大的互补性,为充分利用硬件分布/共享内存层次系统结构可以将这两种编程模型相结合,实现MPI +OpenMP混合并行程序设计。
3.1 分布式存储编程模型MPI
MPI是由学术界、政府和工业协会共同开发的消息传递编程模型的实现标准,具有可移植性好、功能强大、效率高等优点,特别适用于粗粒度的并行。MPI的优点是实现进程级并行,允许静态任务调度,提供明确的并行机制,通常可获得较高的性能;提供了多种点对点和组通信库函数,可根据实际问题的需要选择最优的通信模式。 MPI的缺点是程序设计中需要程序员完成任务和数据的划分及分布,应用的开发和调试难度较大;消息传递的开销非常大,需考虑尽量减少通信延迟;串行程序到并行程序的转化难度大,需做大量的代码修改;动态负载平衡困难等。
3.2 共享存储编程模型OpenMP
OpenMP是共享存储系统编程的工业标准,它具有简单、移植性好和可扩展等优点。OpenMP定义了一个由编译制导、运行时库函数和环境变量构成的集合,用来描述共享内存的并行机制。OpenMP的优点是实现线程级并行,线程间通信通过读/写共享变量实现,编程相对简单,充分利用了共享存储体系结构的特点,避免了消息传递的开销;将串行程序转换为并行程序时无须对代码作大的改动;更好地利用了共享内存体系结构,允许运行时调度,并提供了细粒度和粗粒度并行机制。其不足之处是只能在共享存储结构的机器上运行;数据的放置策略不当可能会引发其他问题;并行化的循环粒度过小会增加系统开销等[3]。
3.3 MPI+OpenMP混合编程模型的实现
混合编程模型通常采用层次结构,上层的MPI表示节点间的并行,下层的OpenMP表示节点内的多线程并行。这种模型的实现首先对问题进行MPI分解,将任务划分成通信不密集的几个部分,每个部分分配到一个SMP节点上,节点间通过MPI消息传递进行通信;然后在每个进程内采用OpenMP编译制导语句再次分解,并分配到SMP的不同处理器上由多个线程并行执行,节点内通过共享存储进行通信。图2描述了SMP集群上MPI+OpenMP混合编程模型的实现机制。
从图2中可知,在每个节点上只有一个MPI进程,首先对该进程初始化,然后每个节点上的MPI进程可以独立作一些局部计算,需要时也可以进行节点间的通信。MPI进程内的主要计算部分(通常是循环部分)采用OpenMP多线程并行求解;在OpenMP求解部分结束后,MPI进程也可以做局部计算、通信或同步;当全部计算工作结束后MPI进程结束。虽然程序中混合了两种模式,但调试时对MPI和OpenMP分别跟踪调试。OpenMP的线程级并行具有较小的延迟,可缓解纯MPI实现带来的网络延迟,同时混合编程还可以优化I/O等资源的使用。
4 三维网格多粒度混合并行算法
4.1 并行化粒度
MPI适合在多节点之间的粗粒度通信,本文采用SPMD的编程模式。而节点内的OpenMP多线程并行具有粗粒度并行化和细粒度并行化两种方法。粗粒度并行化是指OpenMP编译制导指令使用在程序的最外层,首先在主程序中生成多个线程,每个线程类似于SPMD编程模式中的一个进程,使用这些线程就类似于使用SPMD编程模式中的进程,它们均执行相同的代码段,操作在各自不同的数据上。细粒度并行化是指利用OpenMP只并行求解循环部分的计算,又称为循环级并行化。细粒度并行化的方法是在需要用多线程求解的原串行代码中的循环代码段外插入OpenMP的编译制导指令,例如PARALLEL DO等,对串行代码中的其它代码则不并行化。
粗粒度并行使用的编译制导指令较少,并行化通信与调度开销小。但这种方法除了省去数据分配的操作外,程序员使用多线程等同于使用MPI的多进程,编程的复杂度和难度大大增加,而且当混合模型的两级并行机制一同使用时,这种编程复杂性将更大。细粒度并行化比粗粒度并行化的工作量大大降低,只要在循环计算外使用OpenMP编译制导指令并行化即可,而且可以容易地对已有MPI程序的循环做OpenMP多线程并行化。基于这些因素,节点内OpenMP编程采用细粒度并行。因此多粒度混合是指节点间采用MPI粗粒度并行,节点内采用OpenMP细粒度并行。
4.2 三维网格多粒度混合并行算法的实现
求解最短路径问题是三维网格计算中的基本计算问题,有多种三维网格模型上的最短路径算法[4,5],而本文此处采用类矩阵相乘的数值并行算法实现[6]。该算法的实现包括如下四个基本过程:(1)读取初始数据;(2)根据一定划分原则分配数据到各处理器;(3)各处理器并行更新最短路径;(4)汇总数据。上述算法的实现过程包括节点间通信和各节点并行计算两部分,对于需要在各计算节点间传递数据的通信过程采用节点间MPI消息传递编程模型。而对于算法中占大部分计算时间的路径更新过程采用节点内OpenMP细粒度并行编程,这是因为该路径更新过程是通过循环实现的,OpenMP细粒度并行化就是针对这类计算量大的循环进行,OpenMP多线程并行执行会大大提高整个算法的运行效率。此外,算法过程中也有其他循环,但是考虑到循环并行化会带来调度的开销,对于计算量小的循环,我们放弃对它的并行化。下面给出三维网格多粒度混合并行算法的主要伪代码:
#include <mpi.h>
#include <omp.h>
……
int main (int argc, char *argv [])
{
……
MP_Init (&argc, &argv); /*MPI初始化*/
MPI_Comm_size ( MPI_COMM_WORLD,&numprocess);
MPI_Comm_rank (MPI_COMM_WORLD,&myid);
mpi_read_data(); /*读取数据过程(1),MPI消息传递*/
mpi_send_data(); /*发送数据过程(2),MPI消息传递*/
omp_set_num_threads (n); /*设置OpenMP线程数目n*/
#pragma omp parallel for private(i,j,k)
/*路径更新过程(3),OpenMP多线程并行*/
……
mpi_collect_data(); /*汇总数据过程(4),MPI消息传递*/
MPI_Finalize (); /*MPI进程结束*/
}
在上述伪代码中,OpenMP线程数目n的设置与每个节点内的处理器个数相同,我们的实验环境中每个SMP节点有两个处理器,因此OpenMP创建的线程个数为2。这样选择的原因是当节点内的线程数小于这个数值时,SMP的优越性没有发挥到最大,即加速求解的效果没有达到最大;而当线程数大于物理处理器数时,将会因为线程竞争总线带宽而导致性能下降。因此,当SMP节点内每个处理器上只启动一个线程时,效率最高[2]。
5 实验测试
这里采用的SMP集群为Dell PowerEdge 2850系统,每个节点机都有两个主频为2.8GHz的Intel Xeon CPU,内存为ECC DDR-2 SDRAM 2GB,每台节点机上均运行Linux RH9操作系统。本文在8节点SMP集群上建立了LAM-MPI+OpenMP混合并行编程环境。采用本文提出的节点间MPI粗粒度并行和节点内OpenMP细粒度并行的多粒度混合并行算法对三维网格求解最短路径问题进行实验,该程序在SMP集群环境上通过了测试。测试程序分别为粗粒度MPI程序single_mpi和MPI+OpenMP多粒度混合程序mix_mpi_omp,测试数据为891个顶点、1681个面片的蝴蝶三维网格模型,如图3所示。
表1表示粗粒度MPI程序single_mpi和MPI+OpenMP多粒度混合程序mix_mpi_omp的执行时间比较,图4给出这两种并行算法在节点个数分别为1、2、3、4、6、8时的加速比(每个节点为2个CPU)。加速比的求解使用Liu等定义[7]的适合SMP集群的加速比公式:S=Tparallel(1_node)/ Tparallel(N_node),表示一个节点并行执行时间和N个结点并行执行时间的比值。
从表1可以看出,采用MPI+OpenMP多粒度混合并行算法的执行时间要少于粗粒度MPI并行算法,一方面是因为混合编程更充分地利用了CPU的处理能力,并且有着更小的通信开销;另一方面是因为多粒度的程序设计方式提高了并行的加速比。图4表明MPI+OpenMPI多粒度混合并行算法的加速比明显好于粗粒度MPI并行算法的加速比,并且随着节点个数的增加,二者加速比的差距也加大,这表明MPI+OpenMP多粒度混合并行算法有着更好的执行效率和可扩展性。
6 结 论
目前,SMP集群的多层次并行体系结构计算机已成为主流的高性能计算平台,MPI+OpenMP这种混合编程模型相比于单纯的MPI消息传递编程模型更能充分发挥SMP集群节点的性能。本文给出的MPI+OpenMP三维网格多粒度混合并行算法就是利用了这种多层次体系结构的优点,同时解决了大规模三维网格并行计算时间开销过大的问题。实验表明,这种混合编程模式的并行程序性能要超过单一MPI编程模式的程序,并且具有良好的执行效率和可移植性。
参考文献
[1]李清宝,张平.基于分布/共享内存层次结构的并行程序设计[J].计算机应用,2004(6).
[2]陈勇,陈国良,等.SMP机群混合编程模型研究[J].小型微型计算机系统,2004(10).
[3]单莹,等.基于SMP集群的多层次并行编程模型与并行优化技术[J].计算机应用研究,2006(10).
[4]孙晓鹏,李华.基于CSR存储的三维网格最短路径算法[J].计算机工程与应用,2005(10):5-7.
[5]张丽艳,吴熹.三角网格模型上任意两点间的近似最短路径算法研究[J].计算机辅助设计与图形学学报,2003(5):592-597.
[6]武亮亮,郑晓薇.基于三维网格的最短路径并行算法研究[J].计算机工程与设计,2008(5).