并行计算系统

并行计算系统（精选八篇）

并行计算系统 篇1

随着并行计算技术和框架的日益成熟,搭建并行计算环境并非难事。对于博弈并行计算来说,如何设计更好的并行算法模型,以尽量减少三种额外开销称为了关键问题。在大多数系统实践中,由于无法很好的避免额外开销,在多核计算中系统的加速比较低,甚至在计算核数达到一定数量后,加速比会出现负增长,这使得博弈计算的进一步提速遇到了瓶颈。

2 单核搜索算法简介

早期的博弈程序大多会展开一棵完整的博弈树。尽管Alpha-Beta等思想利用启发式信息对博弈树的实际展开进行了剪枝,但逻辑上仍然是展开了一棵完全树。随着计算机博弈研究的进展,学者认为原有的搜索方法不能体现人类智能在下棋中的思维习惯。上世纪80年代出现了选择性搜索的思想,这一思想更有助于提高搜索效率,因此逐渐成为主流方法。本章主要介绍计算机博弈单核条件下选择性搜索的基本思想,以及选择性搜索算法的代表——1997年著名弈棋机“深蓝”使用的“DC延展搜索”。在此基础上,针对“DC延展搜索”的缺陷提出改进方案,并给出了这一改进的实验结果。

3 博弈并行搜索模型研究

博弈中的并行计算是为了加强计算机的运算能力,从而获得更强的智能表现。在以搜 索为主结 构的博弈 系统中,并行计算 模型主要 是指对AlphaBeta搜索进行 分解,也即并行AlphaBeta搜索。目前主要的做法有顶层分支模型、PVS(Principle Variation Splitting)、YBWC(Young Brother Wait Concept) 等。这些算法本身并不涉及实现方式,但为讨论方便,下文在提及这些算法及其改进的时候,都是以多线程实现为例。

3.1 顶层分支并行模型

3.1.1顶层分支模型简介

顶层分支模型,即将博弈树根结点的所有子结点交付不同线程进行计算。这种做法其实几乎完全放弃了通信,因此通信开销几乎是零。然而相对应的,造成了大量的搜索开销,每个并行分支的平均剪枝效率远小于串行搜索。由于分解粒度较粗,各分支内部的搜索速度也可能很不均衡,会造成一些线程早早结束工作,而另一些线程则慢很多的现象,这样造成的同步开销也比较大。

3.1.2顶层分支模型的缺陷

顶层分支模型存在三个主要缺陷。

1. 负载不均衡

2. 搜索开销较高

在串行Alpha-Beta搜索中,窗口的搜索小是造成剪枝的原因,从而减少搜索结点数。在基础顶层分支并行模型下,由于各子树分别维护一个搜索窗口而无法共享,因此各子树剪枝率均小于等于串行搜索下的剪枝率。

3. 并行能力受到分支因子限制

对于一个给定的游戏,其每个局面下的着法是有一定范围的,如中国象棋一般不超过60个着法。如果此时的可用核数超过60,则有一部分核无法得到利用。

3.1Principle Variation Splitting(PVsplitting)

对于顶层分支模型的最早的改进是PV分解(Principle Variation Splitting)。PV分解模型将搜索树中的每个结点按Knuthand Moore[6] 提出的分类方法进行分类 :

PV结点——根结点以及每个PV结点的第一个子结点

CUT结点——PV结点除第一个孩子外的所有结点,以及所有ALL结点的所有孩子

ALL结点——CUT结点的第一个孩子

其他结点——所有不符合上述定义的结点

3.2 改进的顶层分支模型

在目前主流的计算机博弈系统中,很少有采用PVS与YBWC模型的,大多数还是采用顶层分支模型。原因是PVS与YBWC虽然在理论上是成功的,但在实际操作中会造成更多的控制与分配开销,且带来的改进效果受不同棋种、不同系统自身特点影响,在很多系统中实际效果与基础顶层分支模型相差不大。而顶层分支模型简单、易于根据不同系统的特点进行改进,为大多数系统所采用。

3.3 动态延展

顶层分支模型只在顶层对所有子结点进行搜索。这里对这一做法加以扩展,得到动态延展的方法。

对于给定的空闲核数n,游戏的分支因子为b,则从根节点展开k层,使得bk≥n,然后再将所有的以叶子结点为根节点的子树按上述动态分配方法,分配给空闲核进行计算。可以看出,原有的顶层分支模型是这里的一个特例,即n较小,使得k为1时即满足条件并展开。

动态延展不仅是用以应对大规模并行的需求。这种方法的实质是减小了工作的粒度,配合后面将要提出的“动态分配着法”以及“共享高层窗口”的改进,可以有效的减少同步开销,并在通信开销和搜索开销之间取得较好的平衡。

4 结论

博弈并行计算目前的研究主要是对于博弈树进行并行分解,这一做法确实有较大的瓶颈,每一点改进都较艰难,且效果并不显著。然而,如果将博弈并行的重心放在对博弈中复杂运算函数的并行,将能取得很明显的效果。本文工作结束后,作者开始尝试使用多显卡技术和多CPU技术融合,实现双并行的结构,将博弈树分解交给CPU处理,而运算函数的并行则在GPU中。

摘要：计算机博弈的核心技术是搜索。本文针对单核条件下的搜索算法、并行条件下的搜索算法两个方面进行了研究。单核搜索算法方面,简单地介绍了博弈单核条件下的选择性搜索思想,本文研究了几种已有的多核条件下博弈并行搜索方法,分析了其优劣,并针对性地提出了改进方案,给出了系统实践的结果,比较了改进方法与原有方法的效果差异。最后,本文探讨了Alpha-Beta并行搜索系统实现中一些特殊的程序设计技巧。

可扩展的冲击-接触并行计算研究 篇2

可扩展的冲击-接触并行计算研究

冲击-接触计算模型在汽车碰撞、金属成型等的模拟计算中有着广泛的`应用,鉴于冲击-接触计算过程复杂和计算量大,本文在分布式可扩展的并行计算平台上,设计并实现了冲击-接触的并行计算.算例证明,计算平台稳定可靠,算法简单实用,且具有较好的并行效率和可扩展性.

作 者：寇哲君 程建钢 姚振汉 作者单位：清华大学,工程力学系,北京,100084刊 名：计算力学学报 ISTIC EI PKU英文刊名：CHINESE JOURNAL OF COMPUTATIONAL MECHANICS CHINESE JOURNAL OF COMPUTATIONAL MECHANICS年，卷(期)：20(3)分类号：O34关键词：冲击-接触 并行 可扩展

并行计算系统 篇3

整个泵站装置系统进行模拟时所需要计算的网格数量十分巨大,采用CFD并行计算来进行模拟。并行计算分为本地并行计算及分布式并行计算。本地并行计算操作简单,易于实现,但受计算机本身硬件条件限制较大,对网格规模上千万的流场计算,将耗费较多时间。分布式并行能够调用的CPU数量以及内存都可增加,不受单一工作站硬件条件限制,可以使计算能力大大提高,减小计算时间。分布式并行计算需要涉及的如RSH、SSH等协议较多,不同工作站之间的数据交换依赖网卡绑定技术,并依赖于交换机类型,所需要解决的外在计算机问题较多。在此背景基础上,本文建立了实际尺寸三维流道模型,通过ICEM CFD对全流道进行网格计算划分,利用AN-SYS CFX实现了泵站装置系统全流道的并行计算,并分析了计算结果。

1 CFD计算模型简介

本文以某大型泵站为研究对象,计算模型为整个泵站装置系统,其中包括前池、进水池、进水管路、水泵、阀门、出水压力管、出水池等。进水池设计水位19.50 m,出水池设计水位69.70m,设计静扬程50.2m,设计流量30m3/s。安装水泵机组5台(设计4工1备),主水泵为单级双吸离心泵,进口直径1000mm,出口直径900mm,单泵设计流量3.75 m3/s,设计扬程53.2m,转速594r/min。

1.1 三维模型建立

利用NX UG对泵站系统建立三维物理建模。泵站装置系统包括前池进水池、泵进水管、水泵吸水室、水泵叶轮、水泵压水室、泵出水管、压力水箱、爬山管、出水池。

1.2 网格划分

利用ANSYS ICEM CFD对泵站全流场进行网格划分,对泵站装置系统采用四面体非结构网格划分。网格划分结果如表1所示。

个

1.3 数值计算基本设置

利用ANSYS CFX进行泵站系统全流道CFD计算,流场为泵站装置系统全流道,流场进口给定进口流量,流场出口给定出口静压0,水泵叶轮流域与水泵吸水室压水室相接部分定义为固定-旋转交界面。进水池与出水池池顶定义为对称边界,其余为无滑移壁面。以4台泵并联运行为例,进口流量7 500kg/s,旋转域转速594r/min。选用k-ε湍流模型进行模拟。

本文使用戴尔PRECISION T5610工作站进行计算,CPU为英特尔至强系列E5-2630v2,采用本地并行计算。

2 模拟计算结果及分析

2.1 并行计算效率比较

并行加速比S与并行效率E为并行计算效率的评价标准。

若串行处理(单CPU)时计算所用时间为t0,并行处理时计算所用时间为tn,并行采用的CPU数量为N。

则并行加速比S=t0/tn,在理想状态下S=N,并行效率E=t0/(N tn)=S/N。

以4台泵并联运行为运行工况,以12核CPU、10核CPU、8核CPU、6核CPU、4核CPU分别计算,进行2 000步计算,以10核为例,计算时CPU占用率及所用时间如表2所示。

以4核CPU计算所用时间为计算基准得表3所示并行加速比与并行效率。

由表3可知,在8核CPU参与计算时,得到最高并行效率,此时计算机综合性能发挥最佳。

2.2 水泵外特性分析

对4台泵并联运行至1台泵单独运行的情况分别进行相关数据的计算采集,以4台泵并联运行为例(见表4、图1),单泵模拟计算结果:扬程56.915 m,流量3 750 kg/s,效率90.5%。

对同一组运行时多台并联运行的水泵进行横向比较,以4台与3台泵并联为例,见图1。

根据上述水泵扬程、流量的横向对比关系图,得到:(1)泵站装置系统模拟运行情况下所得水泵扬程,均大于单泵模拟情况下水泵扬程,最大差值为0.415,且相对差值<1%;(2)由4台泵并联运行流量扬程关系图以及3台泵并联运行流量扬程关系图可知,流量关于进水池中轴线3号泵对称分布,相应水泵扬程也对称分布。

2.3 水泵内特性分析

水泵流线图、速度、压力分布如图2所示。图2展示了水泵工作时内部流动中的流线及速度和压力分布。从图2(a)观察可得,水泵在设计工况下流线均匀,无明显漩涡。从图2(b)及图2(c)观察可得,水泵叶片周围速度及压力分布均匀,但隔舌部分有明显的高压区。水泵整体运行情况良好。

2.4 进水池流态分析

进水池高度为8 100mm,以进水池池顶为基面,作水平截面。在吸入口面所在位置及其上下作参考截面,取距池顶深度4 000、6 000、7 050、7 550mm作水平截面。以池顶为基面,所做截面的流态流线图如图3所示。

图3展示了进水池由高到低5个水平截面中,水流的流动方向与流动状态。由从图3(a)到图3(d)的顺序观察可得,与进水管水流流动方向相同的区域越来越大,回流区越来越小。深度4 000mm,位于进水管中轴线上,沿进水流动方向区域变大,在入口来流的两侧,水流受到回流区水流影响,偏离来流方向;深度6 000mm,在进水管以下,沿进水管进水流动方向流动区域明显增大,且与回流区域的交界面产生了明显的横向流动,可看见明显的分界面;深度7 050mm,与水泵进水管进水面在一个平面中,沿进水管来流方向区域变的更大,且流动状态较为均匀;深度7 550mm,靠近池底,深度深于水泵进水管入水面,除了在没有进水管进水流动位置处产生碰壁回流外,所有流动方向都与进水管来流方向一致。

由于进水池出口面面积与其他固壁边界面积相比很小,所以大部分在水泵进水管入口面以上的水流由于碰到进水池墙壁而反弹回流,与向邻近的水流相互影响,在回流区域进水管进水区相遇,有明显的流向偏转,在回流区域与进水池靠近底部流入水泵进水管入口的水流相遇,产生明显漩涡。

对4台泵并联运行至1台泵单独运行情况下,同一高度截面处的进水池流态进行横向对比。选取参考截面距池顶深度为7 050mm,与水泵进水管入口的深度相同。

由图4可知:在1台泵单独运行的情况下,除了水泵进水管入口处附近流动方向朝向水泵外,其余区域全为回流区,在进水池相邻的隔墩附近,产生明显反弹与回流;从2台泵并联运行到4台泵并联运行,随着运行泵数量的增多主流区面积越来越大,水泵进水管附近流态逐渐变好,漩涡与回流减少。

综上所述,根据水泵开机数量等具体工况的不同,进水池内部流态发生有规律、渐变性的改变。参与运行的泵数量越多,回流面积越小,主流区面积越大,进水池内漩涡绕流越少,流动状态越均匀。

3 结语

泵站装置系统模拟与各装置单独模拟结果存在差异,泵站装置系统模拟更接近实际流动。在泵站装置系统模拟中,水泵与进水池相对位置不同时,流量、扬程与效率不同,相对差值在1%以内。由流动分析可知,进水池存在大面积回流区域,开机水泵数量越多,进水流量越大,回流区面积越小;水深越深,越接近水泵进水管进水面,回流区面积越小。进水池的流动不良状态会导致水泵进水管进口速度分布不均。

摘要：关于泵站的研究,一般是把进出水建筑物从泵站其他装置中分离出来作为单独的研究对象。为了研究泵站全流道CFD计算与泵站各过流装置单独计算的异同,对泵站装置系统进行全流道CFD数值计算。以某泵站二期工程为研究样本,进行1:1建模,网格划分。采用湍流模型进行并行计算,设置多组对照试验模拟计算。通过对比各组模拟结果中水泵流量、扬程、效率,对部分流道流动状态进行分析。

关键词：泵站,CFD计算,并行计算,流态分析

参考文献

[1]陈坚.对新时期我国泵站工程某些问题的再认识[J].中国农村水利水电,2004,(4):71-72.

[2]王福军.水泵与水泵站[M].北京中国农业出版社,2005.

[3]Deeny D F.An experimental study of air-entraining vortices at pump sumps[C]∥Proceedings of the Institution of Mechanical Engingeers.London,England:1956,170(2):106-116.

[4]YR Reddy,J A Pickford.Vortices at intakes in conventional sumps[J].Water Power,1972:108-109.

[5]Tagomuri M,Goloh M.Flow parterns and vortices in pump sumps[M].Prco.Int.Symp.on Large Hydro Machinery,1989:13-22.

[6]朱红耕,袁寿其.大型泵站肘形进水流道三维紊流仿真计算[J],中国农村水利水电,2005,(4):42-43.

[7]陆林广,曹志高,周济人.开敞式进水池优化水力设计[J].排灌机械学报,1997,(4):15-19.

并行计算系统 篇4

关键词：频繁模式,FP-Growth,并行计算,计算机集群

频繁模式挖掘是关联规则[1]、相关分析[2]、序列模式[3]等数据挖掘工作的重要基础。根据在挖掘过程中是否产生候选集, 频繁模式挖掘算法分成两大类, 前者以Apriori算法[1]为代表, 需要多次扫描数据库并产生大量候选集, 效率低下;后者以FP-Growth算法[4]为代表, 只需两次扫描数据库, 能够在不产生候选集的情况下产生所有的频繁项集, 效率比Apriori算法相比有巨大提高[4]。然而在挖掘频繁模式时, FP-Growth算法需要递归生成大量条件FP-tree, 存储并挖掘这些条件FP-tree, 对计算系统的时间和空间都有较高的要求, 不仅速度慢而且内存容易溢出。所以在实际应用中, 当面临海量数据库时, FP-Growth算法的串行算法已经难以满足计算需求, 面向计算机集群系统的并行计算是解决计算速度及存储压力的有效途径。

计算机集群是使用特定的连接方式, 将多台普通的计算机设备结合起来, 提供与超级计算机性能相当的并行处理系统。相对于共享内存的并行计算系统来说, 其对并行算法的要求更高, 尤其面对FP-tree这样复杂的数据结构时, 各计算节点之间很难协调统一地执行计算任务。文献[5]采用基于数据划分的形式, 分割数据库并将其分配到集群中的各个计算节点分别执行FP-Growth算法, 最后汇总各计算节点的结果, 开创了面向计算机集群FP-Growth并行计算的先河。但这种方法存在一个难以克服的缺点:数据库内的数据必然存在千丝万缕的联系, 强行划分数据库可能会牺牲结果的准确性。

本文提出了一种基于任务划分的, 面向计算机集群的新的频繁模式挖掘算法——Gridify FP-Growth, 将建立FP-tree后彼此独立的频繁模式挖掘任务划分到集群中所有的计算节点上共同执行, 不但能够提高计算效率, 而且当数据库规模不断增加时该算法具有良好的延展性。

1 相关概念介绍

1.1 频繁模式挖掘

设I = {i1, i2, …, in}是n个不同项目的集合。设D为事务集, 其中的每个事务为T⊆I的项集, 每个事务有唯一标识, 称作TID。对于项目集X⊆I, 若X⊆T, 则认为事务T 支持X。 X在D中的支持数是指D中支持X的事务数。X在D中的支持度是指D中包含X的事务的百分比。如果X的支持度不小于用户给定最小支持度阈值Min_Support, 则称X为D中的频繁项集, 项集中项目的个数称为频繁项集的维数或长度。仅含有一项的频繁集称作频繁一项集。频繁模式挖掘的任务就是找出给定数据集D中支持度超过给定最小支持度阈值的所有频繁项集。

1.2 FP-Growth算法

FP-Growth算法属于深度优先搜索, 将挖掘长频繁模式的问题转换成递归地发现一些短模式, 然后连接后缀形成。仅需要两次扫描数据库, 第一次扫描产生频繁一项集;第二次扫描建立全局FP-tree。从挖掘步骤来看, 可以分成两步:

第一步, 建立FP-tree:把数据库中的频繁集压缩进一棵频繁模式树 (FP-tree) , 同时保留其中的关联信息。

第二步, 对FP-tree进行频繁模式挖掘:由于FP-tree蕴含了所有频繁项集, 所以频繁模式挖掘的工作仅在FP-tree上进行。根据频繁一项集将FP-tree分化成一些条件模式库, 针对这些条件模式库分别建立条件FP-tree, 递归地进行挖掘。

建立FP-tree 及对FP-tree 进行挖掘的具体实现过程在文献[4]中有详细介绍, 在此不赘述。值得注意的是, 在第二步中, 根据每个条件FP-tree递归地挖掘的过程, 是彼此独立的[5]。根据这一特点, 可以将这些独立的挖掘过程分配到计算机集群中不同的计算节点分布执行。这是本文中将提到的并行算法的理论基础。

2 计算机集群系统

计算机集群 (PC Cluster) 是指一组相互独立的计算机, 利用高速通信网络组成的计算机系统, 每个节点 (即集群中的每台计算机) 都是运行其自己进程的一个独立服务器, 这些进程可以彼此通信, 同时集群中的各个节点是平等的。从某种意义上说, 计算机集群形成了一个单一系统, 可被看作是一台计算机, 协同起来向用户提供应用程序、系统资源和数据, 并以单一系统的模式加以管理。

计算机集群不仅能够提供强大处理能力, 且性价比远远优于超级计算机, 最重要的是其具有很强的可伸缩性:在系统的处理能力需要增加的时候, 可通过简单地增加集群中的节点数, 即通过向集群添加新的计算机节点, 完成系统计算能力的扩容, 这在对大规模数据库进行频繁模式挖掘时, 具有重要的应用价值。

3 面向计算机集群的FP-Growth算法的并行计算

本文以FP-Growth算法为基础, 提出了适用于计算机集群系统的并行算法, 由于计算机集群系统中的各节点形象地构成了一个计算网格, 本文把算法命名为Gridify FP-Growth, 简称GFP-Gowth算法。

3.1 GFP-Growth算法主要思想

GFP-Growth算法继承了FP-Growth算法的第一步, 即生成全局FP-tree的过程;并行计算集中在频繁模式挖掘这一阶段。

为了保证第一次建立的全局FP-tree的完整性与准确性, 建立全局FP-tree的过程在单机上执行, 另外实验证明, 当数据库规模在10k以上时, 建立全局FP-tree消耗的时间与后续频繁模式挖掘时间相比, 一般相差3个数量级以上, 对整个计算时间的影响很小, 所以建立全局FP-tree的过程不采用并行计算。

在频繁模式挖掘阶段, 当数据库规模较大的时候, FP-Growth算法会递归生成海量条件模式库, 并需要根据这些条件模式库生成一一对应的条件FP-tree。然而, 正如我们在介绍FP-Growth算法的时候提到的, 根据每个条件模式库生成条件FP-tree, 进行频繁模式挖掘的过程, 彼此间是完全独立的。这一互相独立的特点, 能够将串行算法的劣势转换为并行算法的优势:将根据每一个条件模式库挖掘频繁模式的过程分配到集群中的计算节点上分别执行, 不仅会提高计算效率, 而且不会牺牲算法的精度, 这是GFP-Growth算法的主要思想。

3.2 GFP-Growth算法主要步骤

计算机集群中的各节点之间是平等的, 可以随机指定一台计算机为中央节点。首先在中央节点上, 根据数据库生成全局FP-tree, 这一单机实现的过程与FP-Growth算法相同;生成FP-tree之后, 中央节点根据频繁一项集将全局FP-tree分化成一些条件模式库, 并行计算开始, 主要步骤如下:

第一步, 对任务进行划分。中央节点根据众多条件模式库将统一计算任务Task划分为多个子任务Jobs, 每一个条件模式库对应一个子任务, 即根据每一个条件模式库进行频繁模式挖掘的工作就是一个Job。

第二步, 对任务进行分配。由中央节点将Jobs分配到集群中的各个计算节点 (包括它自身在内) , 每个节点需要负责一至几个Jobs;在计算过程中根据各节点的计算能力进行负载动态调整。

第三步, 分别执行任务, 集群中的每个计算节点分别执行分配给自己的子任务Jobs。对Jobs对应的各条件模式库建立相应的条件FP-tree, 递归地对每个条件FP-tree进行频繁模式挖掘。

第四步, 对结果进行汇总。计算节点完成Jobs之后, 需将计算结果传递给中央节点。

这里采用异构的通讯方式, 即各个节点不是同时开始通讯的, 而是每当有节点完成计算任务, 立刻会向中央节点提交运算结果。由中央节点将全部的计算结果汇总, 并输出统一计算结果。

4 算法实现与比较

为了验证集群计算的灵活性与便利性, 实验所用设备为3台普通PC机, 且配置不同, CPU和内存分别为1.73 GHz (双核) , 2.87 GB ;1.60 GHz (双核) , 1.87 GB;2.39 GHz (双核) , 2.99 GB。采用一般的无线网络来连接计算节点, 带宽54 Mbps;编程工具和运行环境为JDK 1.6。选择配置中等的计算机1.73 GHz (双核) , 2.87 GB为中央节点。两台计算机的实验, 所采用的计算机为1.73 GHz (双核) , 2.87 GB ;1.60 GHz (双核) , 1.87 GB。

4.1 算法有效性实验

数据集采用http://archive.ics.uci.edu/ml/datasets.html上提供的Mushroom相对密集型的蘑菇数据库来进行实验。该数据库有8 124条记录, 记录了蘑菇的23种属性, 虽然是一个很小的数据库, 却非常稠密, 项集之间的相关性很强, 即使在最小支持度阈值较大时, 也存在大量频繁模式, 并且随着支持度的减小存在严重的组合爆炸问题[6] 。

实验设定频繁项集长度为15, 从图2看出随着最小支持度的增大, GFP-Growth算法的速度较FP-Growth算法有显著提高, 在支持度小于2%的情况下, 在3台计算机上实现的GFP-Growth算法执行时间少于FP-Growth算法的1/3。

4.2 算法伸缩性实验

分别采用1 000条、2 000条、3 000、4 000、5 000、10 000条事务数据集来实验, 项目数为200, 平均事务长度为50, 最小支持度为4%, 频繁项集长度为4。实验结果如图3所示, 在数据量相等的情况下, GFP-Growth算法无论在2台或3台计算机上的执行时间始终少于FP-Growth算法, 且在3台计算机上实现的GFP-Growth算法执行时间少于2台计算机上实现的GFP-Growth算法, 差距随数据量增大而增大, 说明集群系统具有良好的伸缩性。

5 结 论

本文提出了一种基于FP-Growth的频繁模式挖掘并行算法——GFP-Growth, 能够在计算机集群系统中实现并行计算。从算法的角度来看, GFP-Growth算法能够有效地提高计算速度并具有良好的伸缩性。从计算环境来看, 计算机集群系统价格低廉, 却具有大型服务器的计算功能, 并具有很强的延展性。实验证明, 数据库规模越大, 利用计算机集群进行并行计算的优势越明显。

参考文献

[1] R Agrawal and R Srikant. Fast Algorithms for Mining Association Rules[C]//In Proceedings of the 20th International Conference on VLDB, 1994: 487-499.

[2]S Brin, R Motwani, C Silverstein.Beyond Market Basket:Gener-alizing Association Rules to Correlations[C]//Proc of1997ACM-SIGMOD Int l Conf on Management of Data, Tucson, AZ:ACM Press, 1997:265-276.

[3]R Agrawal, R Srikant.Mining sequential patterns[C]//ICDE95, Taipei, Taiwan:IEEE Computer Society Press, 1995:3-14.

[4] J Han, Pei , Y Yin.Mining Frequent Patterns Without Candidate Generation[C]//Proc ACM-SIGMOD, Dallas, TX, 2000.

[5]Iko Pramudiono and Masaru Kitsuregawa.Parallel FP-Growth on PC Cluster[C]//Proc of the International Conference on Internet Com-puting, 2003.

并行计算系统 篇5

随着计算机技术的飞速发展和普及, 数据采集系统在各个领域有着广泛的应用。数据采集是工、农业控制系统中至关重要的一环, 在机械、医药、化工、食品等领域的生产过程中, 往往需要随时对各生产环节的位移、温度、湿度、流量及压力等参数进行多路检测, 以实现实时检测与控制, 保证产品质量。传统的方法是在各检测点设置传感器, 通过多路模拟开关和模数转换器件对各个模拟量进行模数转换, 取得相应的数据以供主机处理。这种方法存在如下缺陷:

(1) 模拟电压在通过电缆传到主机的过程中容易受到干扰;

(2) 主机要通过模拟开关选择传感器, 这使测头的路数受到限制, 主机的接口电路比较复杂;

(3) 主机无法向各检测点传送控制指令;

(4) 如果在检测点增加一个传感器, 就必须增加一根电缆连至主机, 因而增加了布线的复杂程度。

针对上述问题, 设计了基于计算机并行口和MC145027的多路数据采集系统, 使主机和各个测头之间只通过三根线即可实现双向的数据传输。由于MC145027特殊的译码方式能够消除瞬间的强电磁干扰, 因而保证了数据在传输过程中具有很高的可靠性。

2多路数据采集系统的组成框图

多路数据采集系统原理框图如图1所示。该检测系统的硬件电路由测头电路和主机接口电路两部分组成。主机和测头之间传输的格式遵循MC145027的编码格式。

3系统硬件电路设计

3.1测头电路设计

测头电路的原理图如图2所示。主机发送至探头的编码信号线经过信号传至各个测头, 经放大整形电路处理后送到MC145027进行解码, 当地址判断一致后, VT由低变高向单片机申请中断, 由单片机读取解码后的数据, MC145027能够解出4位数据码, 4位二进制的数据码可以表示种命令, 单片机根据命令的要求将采集到的数据 (温度、压力、湿度等) 按照MC145026的编码格式由P1.7输出, 再经过驱动电路回送至主机。

3.2主机接口电路设计

以PC机作为主机, 通过并行打印口与测头交换数据。主机接口电路如图3所示。MC145027的A1～A5引脚的状态决定主机的地址码 (00000) , D6～D9分别和主机打印口的引脚13、12、10、11相连, 上述4个引脚为打印机的状态输入口, 分别对应于主机数据总线的D4～D7。主机通过打印口的14脚 (对应于数据位D1) 向各个探头发送命令, 探头接到命令后向主机回传所要求的数据, 并通过MC145027解码后由主机读取。MC145027的VT引脚接至打印口的1脚 (对应于数据位D0) , 主机通过定时检测VT脚的状态来判断是否有应答数据到来。

4 MC145027的解码方式

MC145027通常用作解码器, 与之搭配使用的编码器为MC145026。为了说明MC145027的解码方式, 这里首先介绍一下MC145026的编码方式。

4.1 MC145026的编码方式

MC145026是数字编码器, 对外引脚中有A1～A9共9个地址或数据输入端, 当作地址使用时可有三个状态 (高电平、开路、低电平) , 当作数据使用时有两种状态 (高电平、低电平) ;这样可产生39=19683种不同的编码。数据由DO串行输出, 编码信号如图4所示。每位数据用两个数字脉冲表示:两个连续的宽脉冲表示“1”, 两个连续的窄脉冲表示“0”, 一宽一窄两个脉冲表示“开路”。引脚TE是内部时钟振荡器的工作控制端, 当TE为低电平时, 振荡器工作, 发送数据, 1个发送周期将9位数据A1～A9重复发送2次。

4.2 MC145027的解码方式

MC145027是与MC145026配套使用的解码器, 具有4位数据输出和5位地址编码, 地址可二态或三态编码, 根据其地址的不同组合最多可以产生35=243种不同的地址编码。当外部数据从DI输入时, 先接收5位地址码, 如果与本地址码的设定一致 (即A1～A5编码) , VT电平由低电平变为高电平, 表示译码成功, 开始接收编码器送来的4位数据, 由D6～D9输出, 以控制相应装置。MC145027的引脚功能和内部功能框图如图5所示。

MC145027的译码通过RC积分电路来完成宽窄脉冲的识别, 图5中, 定时元件R1、C1决定对宽窄脉冲的识别, R2、C2是整个发送周期的辨别定时元件, 用以确定各个有效单字。当外部数据从数据输入端DI输入时, 6脚将出现与9脚相同的信号, 该信号经R1、C1积分电路积分后由7脚送至数据提取电路, 数据提取电路在输入信号的每一个上升沿, 通过检测7脚的状态来判断输入的是宽脉冲还是窄脉冲。图6给出了6脚和7脚信号的波形, 假定数据输入端输入的是“开路”编码 (即一个宽脉冲和一个窄脉冲) , 宽脉冲开始于t0时刻, 结束于t1时刻, 窄脉冲开始于t2时刻, 结束于t3时刻, 整个编码于t4时刻结束。那么, 在t1时刻, 7脚的电压为0.856Vcc;在t2时刻, 7脚的电压为0.65Vcc。在此时刻, 数据提取电路检测到的7脚电平为高电平, 说明上一个脉冲为宽脉冲;此后窄脉冲通过R1给C1充电, 在窄脉冲结束时的t3时刻, 7脚的电压为0.74Vcc, 在此后的一段时间里C1通过R1放电, 在编码结束的t4时刻, 7脚的电压为0.1Vcc。此时数据提取电路检测到7脚的电平为低电平, 说明上一个脉冲为窄脉冲。

由此可见MC145027并不是对接收到的脉冲信号直接进行解码, 而是将输入信号积分后进行解码, 由于积分电路能滤除瞬间的尖脉冲干扰, 因此MC145027接收的编码信号即使受到某种程序的干扰, MC145027依然能够进行正确的解码, 这一点对于环境复杂的工业现场特别重要。

5系统软件的设计

5.1数据格式的定义

根据MC145026的编码格式, 在一个发送周期里可以发送9位数据信息, 我们定义A1～A5为测头和主机的地址信息, 由于总共可表示243个地址码, 而主机的地址码定义为00000, 因而其余242个地址码可供探头使用;在主机发至探头的编码里, 除了A1～A5表示测头的地址之外, 尚有A6～A9共4位可以表示控制命令, 设计时可以根据系统的要求将这16个命令码一一定义, 以供系统使用。在探头发往主机的编码里, 前五位A1～A5是固定格式00000, 表示主机的地址号, 后四位A6～A9表示发往主机的数据, 一个字节分两次发送, 先发高半字节 (高四位) , 再发低半字节 (低四位) 。

5.2探头地址码的设置

MC145027的地址输入脚 (A1～A5) 有三个状态 (高电平、平路、低电平) 也就是说地址线是三进制数据, 而单片机的I/O口是二进制状态 (二进制数据格式) , 在探头电路中, 为了使单片机发送的地址码与MC145027的地址码相对应, 单片机必须能自动检测自身的地址。在图7所示的电路中, P1.0～P1.6作为地址设定脚, 它们所表示的地址信息应与MC145027的地址 (A1～A5) 相同, 这涉及到二进制到三进制转换的问题。由于表示243个地址需要8位二进制数据, 而单片机只有7位地址设定脚, 另外的一位 (最高位) 只能由程序设定。这样探头的地址就可以比较灵活地设置, 因而具有一定的通用性。

5.3单片机的软件设计

探头电路中的单片机主要用来完成以下几个功能:①完成探头电路的自检;②接收并执行主机发来的控制命令;③根据主机的命令完成相应的动作;④按照MC145026的编码格式向主机发送数据。

5.4主机软件的设计

主机软件是整个控制系统的核心, 在这里只讨论和探头通信有关的内容。在主控软件中设置一个定时中断程序, 以定时检测MC145027的VT脚的状态, 当VT脚由低电平变为高电平时, 通过读取状态口的内容来接收探头发来的数据。当主机向各探头发送命令时, 就可通过并行打印口的14脚发送控制命令编码。主机命令码的发送格式也应遵循MC145026的编码格式。

6结束语

利用计算机并行口与测头进行数据交换, 可提高数据的传输效率;利用MC145027独特的解码方式能有效地克服工业现场的强电磁干扰, 保证数据的可靠传输;利用单片机及PC机模仿MC145026发送编码数据可有效地利用系统资源, 节约成本, 提高了整个系统的可靠性。

创新点:将解码器MC145027与计算机有机结合, 实现了多达242路的数据采集并行传输系统, 且电路简单、传输可靠。

参考文献

[1]丁宋威等.微机并行口通讯控制与打印机协同工作的实现.微处理机, 2001, (2) :62～64

[2]宋晖.基于并行打印口的多机通讯.兵工自动化, 2004, (6) :42～43

[3]李朝青.PC机及单片机数据通信技术.北京:北京航空航天大学出版社, 2001.

[4]鲍苏苏, 杨璐.并行口三单片机通讯接口的实现.广东自动化与信息工程, 2003, 24 (3) :17～18

[5]段军等.单片机与PC机之间并行通讯的一种实现方法.j计算机自动测量与控制, 2000, 8 (2) :32～34

[6]周丽芹等.一种基于PC机打印口的上下位机并行通讯方法.微计算机信息, 2004, (5) :110～111

并行计算技术综述 篇6

近年来多核处理器的快速发展,使得当前软件技术面临着极大挑战。无论CPU在主频率上还是处理器核数上都在飞速发展。硬件技术在不断发展的同时,要求软件技术也须同时进步。常用的并行计算技术有调用系统函数启动多线程以及利用多种并行编程语言开发并行程序,常用的并行编程模型有MPI、PVM、Open MP、TBB、Cilk++等。利用这些并行技术可以充分利用多核资源,适应目前快速发展的社会需求。并行技术不仅要提高并行效率,也要在一定程度上减轻软件开发人员负担,如近年来的TBB、Cilk++并行模型就在一定程度上减少了开发难度,提高了开发效率,使得并行软件开发人员把更多精力专注于如何提高算法本身效率,而非把时间和精力放在如何去并行一个算法。

1 并行架构[1,2]

常用的并行架构分为SMP(对称多处理器结构)、NUMA(非统一内存存取)、MPP(巨型并行处理)、CLUSTERS(集群)。

SMP系统中每个计算机中有多个对称CPU处理核,无主次或从属关系,它们共享内存空间和I/O设备,每个CPU访问内存中的任何地址所需时间是相同的,因此SMP也被称为一致存储器访问结构(UMA:Uniform Memory Access)。由操作系统调度算法将任务进行分解并分配在不同的CPU处理核上运行。SMP服务器的主要特征是共享,系统中所有资源都是共享的。

NUMA即非一致访问分布共享存储技术,它是由若干通过高速专用网络连接起来的独立节点构成的系统,各个节点可以是单个的CPU或是SMP系统。在NUMA中,Cache的一致性有多种解决方案,需要操作系统和特殊软件的支持。

MPP提供了另外一种进行系统扩展的方式,它由多个SMP服务器通过一定的节点互联网络进行连接,协同工作,完成相同的任务。其基本特征是由多个SMP服务器节点通过互联网络连接而成,每个节点只访问自己的本地资源(内存、存储等),是一种完全无共享(Share Nothing)结构,因而扩展能力最好,理论上其扩展无限制。在MPP系统中,每个SMP节点也可以运行自己的操作系统、数据库等。但和NUMA不同的是,它不存在异地内存访问的问题。

集群系统由独立的计算机组成,由控制管理工具统一管理,搭建集群的目的是共享和高效地利用资源,提供海量数据运算功能,提供负载均衡功能及出现故障时具有保障数据容错功能。

2 并行编程模型

并行编程可以调用系统函数启动多线程,也可以利用并行编程模型,如常用的并行模型有MPI、PVM、Open MP、TBB及Cilk++等。

2.1 MPI简介[3,4]

MPI(Message Passing Interface)是基于消息传递的并行编程模型。消息传递指的是并行执行的各个进程具有自己独立的堆栈和代码段,作为互不相关的多个程序独立执行,进程之间的通信通过显式地调用通信函数来完成。

(1)MPI程序基本函数

(1)MPI_Init用来初始化MPI执行环境,建立多个MPI进程之间的联系,为后续通信做准备。而MPI_Finalize则是结束MPI执行环境。这两个函数之间定义MPI程序的并行区域。

(2)MPI_Comm_rank来标识各个MPI进程。

(3)MPI_Comm_size用来标识进程组中有多少个进程,返回整形的错误值,同时有两个函数参数,MPI_Comm类型的通信域,标识参与计算的MPI进程组,如MPI_COMM_WORLD;整数指标,返回相应进程组中的进程数。

(2)MPI性能分析与优化举例

MPI消息传递开销由两部分组成:一部分是通信固有的延迟;另一部分是消息传递开销,与消息的数据量和网络带宽有关。时间消耗可以用下面的式子表示:

其中,TTotal、Tcomm、Tserial分别表示程序总用时、通信用时和串行部分用时。而通信用时一般可作如下分解:

其中,n为点对点通信次数,m为群集通信次数,ts为通信固定延迟,Bi为第i次通信的容量,ω为网络带宽,Ti为负载不平衡造成的时间消耗,TCi为群集通信耗时。

(3)解决负载均衡问题

在并行计算中,若各个处理器上的执行时间不同,因同步会使先完成的处理器等待未完成的处理器,此时应该考虑负载均衡问题,使得资源得到合理利用。负载均衡分为:静态负载均衡及动态负载均衡。静态负载均衡适用于计算前可以准确估算总的负载,且这些负载容易平均划分给各个进程的情况。对于事先不知道负载总数,或者总负载不易平均划分的情况,需要动态负载均衡策略来解决。

2.2 PVM简介[5]

PVM是一个在网络上的虚拟并行机系统的软件包,它允许将网络上基于UNIX操作系统的并行机和单处理机的集合当成一台单一的并行虚拟机来使用。PVM支持用户采用消息传递方式编写并行程序。PVM支持用户采用消息传递方式编写并行程序,计算以任务为单位,一个任务就是一个UNIX进程,每个任务都有一个taskid来标识(不同于进程号)。

PVM支持在虚拟机中自动加载任务运行,任务间可以相互通讯以及同步,在PVM系统中,一个任务被加载到哪个结点上去运行,PVM就允许用户指定任务被加载的结点,这样就方便了用户编写并行程序。

2.3 Open MP简介[3,6]

Open MP是一种面向共享内存及分布式共享内存的多处理器多线程并行编程语言,它也是一种能够用于显示指导多线程、共享内存并行的应用程序编程接口。Open MP的编程模型以线程为基础,通过编译指导语句来显示地指导并行化,为编程人员提供了并行化的完整控制。Open MP的执行模型采用Fork-Join形式,Fork-Join执行模式在开始执行的时候,只有一个主线程存在。主线程在运行过程,当遇到需要进行并行计算的时候,派生出子线程来执行并行任务。在并行执行的时候,主线程和派生线程共同工作。在并行代码结束执行后,派生线程退出或者挂起,不再工作,控制流程回到单独的主线程中。

图1是共享内存多线程应用程序的Fork-Join模型。主线程在运行时遇到并行编译指导语句,根据环境变量派生出4个子线程,4个子线程与主线程同时运行。在运行的过程中,某一个派生线程遇到了另外一个编译指导语句时,也派生出另外一组子线程。新的线程组共同完成一项任务,但对于原有的线程来说,新线程组的工作类似于一块串行程序,对原来的线程不会产生影响。新线程组在通过一个隐含的同步屏障后,汇合成原有的线程。最后,原有的线程组汇合成主线程,执行完最后的程序代码并退出。

(1)编译指导语句

编译指导语句的含义是在编译器编译程序的时候,会识别特定的注释,而这些特定的注释就包含着Open MP程序的一些语义。如在C/C++程序中,用#pragma omp parallel来标识一段并行程序块。在一个无法识别Open MP语义的普通编译器中,会将这些特定的注释当作是普通的注释而被忽略。因此,如果仅仅使用编译指导语句中,编写完成的Open MP程序就能够同时被普通编译器与支持Open MP的编译器处理。这样就可以用一份代码来编写串行或者并行程序,或者在把串行程序改编成并行程序的时候保持串行源代码部分不变,极大方便了编写人员。常用的编译指导语句以#pragma omp开始,具有如下形式:

#pragma omp[clause[[,]clause]…]

其中,directive部分就包含了具体的编译指导语句,包括parallel,for,parallel for,section,single,critical,flush,ordered和atomic,这些编译指导语句用来分配任务或者用来同步。

(2)运行时库函数

Open MP运行时函数库用以设置和获取执行环境相关的信息,它们也包含一系列用以同步的API,如omp_get_thread_num()就是一个运行时函数库中的函数,用来返回当前线程的标识号。Open MP程序同时结合了两种并行编程方式。通过编译指导语句,可以将串行的程序逐步改造成一个并行程序,同时也可以将串行程序和并行程序保持在一个源代码档中,减少了维护的负担。Open MP也提供了运行时库函数来支持运行时对并行环境的改变和优化,给编程人员足够的灵活性来控制运行时的程序运行状况。

2.4 Intel TBB(Threading Building Block)简介[7,8]

Intel TBB是一个用来支撑可扩展编程的库,TBB的工作层次要高于裸线程,它为C++程序提供了丰富而完备的方法来表达并行语义。TBB指定的是任务而不是线程,一般线程软件包都要求创建、汇合及管理线程。TBB运用自己的调度算法把任务分配到各个线程,高效合理地利用处理器资源。TBB的目标是通过线程来提升性能,将密集的计算任务并行化,提供更高层次和更简单的解决方案,TBB依赖泛型编程。TBB中还支持算法模板,如基于递归区间的面向循环算法,根据需求来递归地划分问题,从而获得并行任务的正确层次。相比静态划分问题,递归划分问题的方式更占优势。线程构建模块的函数都定义在空间tbb中,TBB提供parallel_for与parallel_reduce泛型并行算法,可以负载均衡地对固定数目的独立循环迭代体进行并行执行。

参考以下示例:

将这个循环并行化的第一步就是将循环体转换为小空间上进行操作的形式。这种形式是标准模板库(STL)风格的函数对象,称为体对象(body object),每个operator将处理一个小空间。

其中,方法operator()的迭代空间参数。blocked_range是一个在库中定义的模板类,它表示类型T上的一维迭代空间。Parallel_scan是一个以并行的方式前缀计算y[i]=y[i-1]的模板函数。在一组元素上执行像sum、max、min或者逻辑AND等的操作叫归约运行算法。由于取整的因素,并行的归约运算可以产生与串行的归约运算不同的结果。

2.5 Cilk++简介[9]

Cilk++语言扩展了C++语言来编写并行应用程序,有效地利用多处理器。Cilk++语言特别适合但不限于分而治之算法,把任务分解成子问题(任务),可以独立地加以解决。递归函数通常用于分而治之算法。这些任务会在不同循环迭代。Cilk++关键字识别函数调用和循环,可以并行运行。Cilk++语言比较适合“二分法”算法,将问题分解成若干独立子问题,再将这些执行结果合并起来。任务既可以在不同的函数里实现,也可以在一个迭代的循环中完成。Cilk++的关键词能有效地标识可并行执行的函数调用和循环,Cilk++的运行环境能有效地将这些任务调度到空闲的处理器上运行。

(1)使用Cilk++并行化程序的步骤

定位出程序中可并行部分;使用Cilk++关键词;编译程序;执行程序;通过使用reducer、锁及重写代码解决由于竞争条件而产生的冲突问题。

(2)Cilk++三个关键词:cilk_spawn、cilk_sync和cilk_for

(1)cilk_spawn关键词修改函数调用语句,可使该函数与调用函数并行执行。Func函数是能与当前strand并行执行的函数,一个strand是一串行指令序列。包含cilk_spawn的程序段可以和之后的func部分并行执行。Var是一个类型为func返回类型的变量,它接收函数调用的返回值,被称为接收者。对于返回值为空的函数,则必须省略接收者。args是被衍生的函数的参数。

(2)cilk_sync语句表示当前函数不能继续和派生的子任务并行运行,在所有子任务运行完之后,当前函数才能继续执行,cilk_sync只同步由该函数衍生的子任务,其它函数的子任务不受影响。

(3)cilk_for循环用于取代for循环,它允许循环迭代并行执行。cilk_for的语法规则基本如下:

Cilk++运行环境将一个cilk_for循环转换成基于循环迭代的递归往复,使用了有效的二分法策略,cilk_for的串行化就是将cilk_for换成for,但cilk_for循环有比C/C++的for循环更多的限制。因为循环体要并行执行,循环控制标量和非本地变量均不能被修改,否则将导致数据竞争,Reducer可以用来防止竞争。

3 云计算、分布式计算及网格计算

3.1 云计算与并行计算[10]

云计算是分布式处理、并行处理和网格计算的进一步发展,是一种新兴的共享基础架构的技术,它可以将巨大的系统池连接在一起以提供各种IT服务。连接设备、实时数据流、SOA的采用以及搜索、开放协作、社会网络和移动商务等都是推动云计算技术发展的推动因素。

云计算与并行计算相比,在应用广泛性方面,并行计算是为满足某科学领域的专业需求,要求开发者具备较强的技术水平,不具备较强的广泛性,但云计算可以运用在较多领域,而且具有好的效果。在性能方面,并行计算主要追求较高的加速比,而云计算则单机的计算能力要求较低,此系统通过将分散的结点统一,根据相应调度算法合理调度,从而获得巨大的计算能力,而且还能根据客户的需求变化进行调整。

3.2 分布式计算[11]

分布式计算是一种把需要进行大量计算的工程数据分割成小块,由多台计算机分别计算,在上传运算结果后,将结果统一合并得出数据结论的计算方法。目前常见的分布式计算形式通常使用世界各地上千万计算机的闲置计算能力,通过互联网进行数据传输,进行数据交互。

3.3 网格计算[11]

网格计算是分布式计算中一种类型,是针对复杂科学计算产生的一种新型计算模式,此系统将具有很强的数据处理能力,它是随着互联网而迅速发展起来的。这种计算模式是利用互联网把分散在不同地理位置的计算机组织成一个虚拟的超级计算机,其中每一台参与计算的计算机就是一个节点,而整个计算是由成千上万个节点组成的网格,所以这种计算方式叫网格计算。网格计算背后的思想是解决平衡和重新分配现有IT资源所需要的压力。

网格计算具有两个优势:一个是数据处理能力超强;另一个是能充分利用网上的闲置处理能力。

4 结束语

介绍了常见并行架构,分为SMP(多处理系统)、NUMA(非统一内存存取)、MPP(巨型并行处理)、CLUSTERS(集群),介绍了常用并行编程模型,有MPI、PVM、Open MP、TBB及Cilk++等,对以上各个模型进行了分析比较。

最后,介绍了云计算、分布式计算、网格计算与并行计算之间的联系及以后的发展方向。

参考文献

[1]庞征斌.基于SMP的CC-NUMA类大规模系统中Cache一致性协议研究与实现[D].国防科学技术大学,2007.

[2]王睿伯.面向NUMA结构的软件事务内存关键技术研究[D].国防科学技术大学,2007.

[3]李晓明.多核程序设计[M].清华大学出版社,2007.

[4]张武生,薛巍,李建江,等.MPI并行程序设计实例教程[M].清华大学出版社.

[5]纪珊珊.基于PVM的并行计算在PC机群上的实现[D].大连理工大学,2000.

[6]Shameem Akhter,Jason Roberts.多核程序设计技术——通过软件多线程提升性能[M].电子工业出版社,2007.

[7]James Reinders.Intel Threading Building Blocks[M].北京:机械工业出版社,2009.

[8]王磊,曹菡.基于TBB和Cilk++的并行蚁群算法在路径寻优中的应用[J].计算机应用,30(10):2781-2784.

[9]Intelcilk++sdk programmer’s guide[EB/OL].http://www.owlnet.rice.edu/～comp422/resources/Intel_Cilk++_Program-mers_Guide.pdf.

[10]刘鹏.云计算[M].北京:电子工业出版社,2010.

浅谈CUDA并行计算体系 篇7

CUDA (Compute Unified Device Architecture) 模型是由英伟达 (NVIDIA) 公司推出的一种基于GPU通用计算的编程模型和计算体系。该架构不需要借助图像学API, 直接使用类C语言即可完成并行计算, 使得使用GPU处理图像中的复杂计算成为可能。

1 CUDA编程模型

CUDA将CPU串行处理和GPU并行处理完美的结合起来。一个完整的CUDA程序是由主机 (CPU) 程序和设备 (GPU) 程序共同组成, 主机程序主要是为设备程序的运行做前期准备工作, 主要包括数据初始化、数据拷贝、内核函数间数据交换等。而设备程序主要就是完成并行计算的任务。CUDA编程模型分为两个主要部分:CUDA软件架构和CUDA硬件架构。其中CUDA软件架构又包括了软件栈、通用编程模型和存储模型三个方面。下面将从上述内容对CUDA的编程模型进行介绍。

1.1 软件模型

根据NVIDIA的官方文档, CUDA的软件体系共分3个方面:CUDA设备驱动程序、CUDA运行时库和编程接口、CUDA官方函数库。其中, 设备驱动器是直接作用于GPU上的, 开发者可以通过CUDA运行时库和CUDA函数库中的函数调用来使用设备。CUDA编程模型可以根据不同的需求提供不同的API, 开发者可根据对GPU的控制程度来使用。并且为了很好的利用CUDA架构, CUDA还提供了一系列的辅助开发、调试的工具。

1.2 硬件模型

软件程序的运行是建立在硬件的基础上的, 而GPU之所以能够比CPU处理数据更加有效, 在于GPU中有更多的晶体结构可用于计算。而在CUDA的硬件架构中, 流处理器阵列是由多个线程处理器簇组成, 而每个TPC又是由多个流处理器组成的。每个流处理器拥有一套完整的逻辑处理单元, 就有一系列的功能, 如取值、编码、译码等。每个流处理器是由8个流处理单元和2组超级函数单元构成。

2 线程模型

在CUDA编程模型中是通过大量的并行线程来实现计算的, 因此CUDA架构下最小的执行单元线程 (thread) 。每个线程块中是由多个可以通信的线程组成, 每个线程和线程块都有唯一的标示ID, 则可以通过索引确切定位到每个线程。线程的索引和线程的ID是与线程块的维度所确定的, 一维线程索引和ID是相同的, 二维维度为 (m, n) 的线程块, 线程索引 (x, y) 所对应的线程ID为x+y*m;三维维度为 (m, n, k) 的线程块, 线程索引 (x, y, z) 所对应的线程ID为x+y*m+z*m*n。CUDA线程的开辟是根据所需解决问题的数据大小来确定的, 而每个线程块内的线程数由于其共享一个核心处理器的存储器资源, 则块内线程数量是有限制的, 这个可以通过NVIDIA给出的资料查询。一般为了使每个线程块的调度达到最优值, 每个块内的线程数一般设为16的倍数, 但不能超过限定值。

3 存储器模型

CUDA内部存储器的结构是由寄存器、全局存储器、共享内存、本地寄存器、常量内存和纹理内存组成。下面是对这6个存储器的介绍:

寄存器位于GPU晶体片中, 在各种CUDA存储结构中, 它的访问速度快, 因为它是线程所私有的, 不允许其他线程访问和使用。但由于GPU硬件的限制, 寄存器不是无限的, 每个线程块中的寄存器是事先分配好的。但如果内核函数中分配的寄存器数量超过了寄存器的总数, 编译器会默认的将数据转入设备端的本地内存中, 这样就会大大降低程序数据访问的效率。

全局寄存器也称之为线性寄存器, 占设备内存的DRAM的大部分空间, 在内核函数运行时, 所有的线程都可以读写其中的数据。正因如此, 它的访问速度较慢, 耗时较多, 线程访问全局寄存器一般都要花费几百个时间周期。全局寄存器一般在CPU中完成数据空间的开辟、数据的拷贝和传输、数据的释放等操作。

常量存储器位于显存中, 空间大小一般为64K, 是一段只读的地址空间, 由于其具有缓存并且无访问冲突的优势, 常常用于常数的访问。

本地存储器是位于编译器分配的全局存储中, 是归每个线程所私有的数据空间, 与全局存储器相同, 其在程序运行过程中不会缓存, 所以其访问速度也较慢。本地存储器一般用来存放内核函数所声明的变量。

共享存储器是可以被同一块中的所有线程访问的可读写存储器, 它的生存期就是块的生命期。在没有冲突的情况下, 访问共享存储器几乎与访问寄存器一样快, 是实现线程间通信的最好方法。在同一个块内, 所有的线程都能够读共享存储器中的数据, 相比于AMD的显卡来说, 共享存储器是NVIDIA显卡的一项特色。其和寄存器一样位于GPU的晶体芯片中, 所以其访问速度较之全局内存和本地内存来说, 其效率较高, 并且可以减少线程块中的线程通信的时间, 一般只有2个时间周期。但由于其空间较小, 一般每个SM有一个16K大小的共享寄存器, 并且其数据只能在一个线程块中共享。这就容易导致各线程块中的数据不同步, 容易引起数据混乱, 为保证数据在程序执行中的同步性, CUDA中使用_syncthreads () 函数来实现线程块的同步。

纹理存储器是GPU中专门用来渲染纹理的图像处理单元, 它是一块只读空间。在内核函数运行的过程中, 使用纹理寄存器首先需将数据与纹理绑定。纹理存储器与常数存储器一样具有缓存机制。纹理存储器相较于其它存储器有两大优势:一是纹理存储器中的数据可以反复使用, 避免了数据的重复读取, 提高了效率;二是可以拾取坐标对应位置附近领域内的像元数据, 该优势在对图像进行处理中, 可以提高局部性数据读取效率。

4 结语

21世纪人类面临的众多重要科技课题, 这些课题没有万亿次以上的计算能力是无法解决的。GPU与生俱来就有强大的计算能力, NVIDIA公司推出了CUDA架构使开发的难度大大降低, 程序员可以很容易地利用GPU这个计算工具进行并行程序的开发。现在GPU在非图形领域得到了广泛的应用, 基于GPU的通用计算研究也逐渐深入。

摘要：近年来, 图形处理器 (Graphic Process Unit, GPU) 的快速发展使得其逐步用于通用计算。在性能各异的并行计算平台中, 英伟达 (NVIDIA) 公司推出的计算统一设备架构 (Compute Unified Device Architecture, CUDA) 因为充分利用GPU (Graphic Processing Unit) 强大的计算能力实现了通用并行计算而受到研究者们的青睐。

关键词：图形处理器,CUDA,并行处理

参考文献

[1]胡杰.CPU-GPU异构平台计算模型的研究与应用[D].大连:大连理工大学, 2011.

[2]邹治海.CPU架构分析与功耗模型研究[D].上海:上海交通大学, 2011.

并行计算如何用于科学问题研究 篇8

进行并行计算, 目的是为了节约计算时间, 快速地解决运算规模比较宏大的问题。从算法设计的角度, 并行计算可分为数据并行和任务并行, 数据并行是将大任务划分成相同的各个子任务, 任务并行是将大任务划分成相互独立的任务模块。

并行计算科学中主要研究的是空间上的并行问题。空间上的并行导致了两类并行机的产生, 按照Flynn可分为:单指令流多数据流 (S I M D) 和多指令流多数据流 (MIMD) 。

目前的研究文献主要集中在算法本身的优劣, 以及如何在特定领域提高算法的精度等, 对科研过程中如何运用并行算法论述较少。这对于初学者是不利的。本文通过对文献调研, 补充和完善这个方面的知识。

2 适合并行计算的任务的特征

通过并行计算的特点可以看出, 研究问题应用并行算法需要考虑到其本身的特性, 不同的问题应用并行算法的效果不一样, 具体情况如下。

2.1 数据或者计算量大的任务

并行计算和串行计算的差别在于同时进行, 这样可以减少计算时间, 但是会增加通信时间。并行计算适用于解决数据粒度大的问题, 能够极大地提高效率。数据粒度小的问题, 适合用串行计算解决问题。

2.2 数据重复性高的任务

数据量较大、数据处理方法相类似的研究问题适合用并行计算解决。通常来说, 遥感观测、理化实验、经济统计等领域, 数据观测周期相对较长, 获取周期可能是年或月, 数据量大, 但是这些海量数据可能在不同时间的格式相同, 处理流程也是相同的, 可以运用并行计算中的数据并行模式。

2.3 操作间通信少的任务

对于特定的任务, 往往不是一步就能够完成的, 需要进行多步操作。如果一个操作的输入参数来源于前一个操作的输出, 就需要对数据进行同步;如果一个操作的完成需要别的操作提供参数, 那么就需要进行数据传输。

由于网络的问题, 通信成为制约并行计算的瓶颈。能够划分成多个松散耦合模块的问题, 非常适合并行计算。一般来说, 适合面向对象编程技术解决的问题, 比较适合并行计算。例如决策系统 (如交通指挥系统、灾害指挥系统) 的底层信息处理, 需要对很多不同的参数进行处理, 每一类数据就如同一个对象一样, 处理方法是不同的, 往往不需要进行通信, 选择并行计算, 可以节约很多时间。

3 并行计算解决问题的基本思路

利用并行计算解决实际问题, 需要从事数据划分、任务分解、算法设计、问题解决几个步骤。前期的数据划分、任务分解、算法设计, 会影响到并行计算效用的发挥。每个操作步骤需要考虑的因素不同, 下面进行简单论述。

3.1 数据划分

数据划分的效果和质量, 会影响到并行计算的效率。进行数据划分, 要考虑到任务的特点, 对原始数据依赖越强的应用, 划分越简单;对抽象数据 (所谓抽象数据, 是指需要对原始数据进行处理, 得出一些含有知识的数据, 例如通过对图像进行处理, 得出道路的信息, 道路是原始数据中不具备的数据, 因此成为抽象数据) 依赖很强的数据, 划分需要考虑应用的特点。整个过程需要遵循是MIMD的思路。

划分分为两步, 首先将数据的功能进行分类, 得到单独的数据模块, 保证数据模块间的耦合性最低。然后对每个数据模块的数据, 划分成很多等份的数据, 使每个处理器处理的数据量较小。因此, 同一个问题, 可以先按照功能进行数据分来, 再按照数据量大小分成小分数据。

3.2 任务分解

对于每一份数据, 都有特定的处理方法, 因此会产生很多任务, 将这些任务进行分解, 可以很好地用于问题解决和并行算法设计。对于特定数据, 处理过程一般有流水线和并发访问两种模式, 整个过程需要遵循是MISD的思路。

将数据处理, 按照一定的逻辑关系进行划分成很多步骤, 尽量做到每一个操作, 仅仅与另一个操作存在着输入输出的关系, 操作执行过程和别的操作同步和通信的需求最小。操作的抽象程度越高, 与前面操作的同步要求越高, 因此设计也越困难。

3.3 算法设计

将数据和任务划分清楚以后, 就需要设计并行算法实现高效的并行计算了。并行算法编写, 有以下问题需要注意。

3.3.1 选择编程模式

一般并行算法有主从模式 (Masters l a v e) 、对称模式 (S P M D) 、多程序模式 (MPMD) 。这要根据问题的复杂程度、数据的特点和任务的分解结果进行处理。如果任务需要划分很多次, 并且需要随时调整, 那么最好选择主从模式;如果数据比较简单, 任务分好一次之后, 就可以出结果了, 可以选择对称模式;如果数据比较复杂, 能够划分出不同模块, 那么可以选择多程序模式。当然, 也可以根据实际问题, 进行混合选择。

3.3.2 实现并行算法

实现并行算法, 需要考虑很多因素。下面以比较流行的SPMD模式, 论述需要考虑的因素。

进程控制:在SPMD并行程序的编写过程中, 因为只有一份程序, 每个处理机上执行的是相同的程序。因此, 对于每个进程来说, 需要知道自己是属于哪个进程, 从而来确定该进程需要完成的任务。进程控制是并行程序的重要组成部分, 所有的数据处理和交换过程都离不开进程标识, 是在实现过程中必须时刻要牢记的。

数据交换:在SPMD模式中, 数据交换是其主要特征。进程之间的协同工作, 信息沟通等都离不开数据交换。如何合理地实现数据交换, 是提高并行计算程序性能的关键之一。对于一个给定的并行计算方法, 为了高效率的实现, 需要仔细分析数据依赖关系, 尽可能减少不必要的数据交换, 同时也要尽最大努力使数据交换在最少的次数内完成。

面向对象化:建立自己的通讯库, 使程序具有更加直观的可读性。比如说, 在处理机中要进行矩阵传输, 那就需要定制一个子程序来完成这项任务。

3.3.3 算法评估

算法设计完成后, 只是能够完成了任务, 还需要进行算法评估和优化。评估需要考虑算法如下特征:是否与体系结构结合、是否具有可扩展性、是否是粗粒度的;优化从如下方面进行:减少通信、优化性能。当然, 并行计算需要考虑的因素还很多, 但以上五个方面考虑之后, 就可以得到一个很好的并行计算算法。

4 结语

综上所述, 并行算法适合用于数据粒度大、数据重复性高、操作间通信少的问题。并行计算思路解决实际问题要按照数据划分、任务分解、算法设计的思路完成。通过并行算法的实现和完善, 可以达到提高解决问题效率的结果。

参考文献

[1]迟学斌.高性能并行计算[M].中科院计算机信息网络中心, 2005, 4.

[2]卢丽君, 廖明生, 张路.分布式并行计算技术在遥感数据处理中的应用[J].测绘信息与工程, 2005, 6:1～3.