并行计算技术（共7篇）
并行计算技术 篇1
计算机集群技术使用特定的连接方式, 将相对于超级计算机便宜许多的计算机设备结合起来, 提供与超级计算机性能相当的并行处理技术。早在七十年代就有人提出可以使用这种集群技术完成并行处理, 但是由于受到当时网络交换技术的限制, 在性能上集群系统与其他并行处理系统相比相距甚远。直到ATM技术、千兆位以太网技术逐渐成熟的今天, 集群系统才具备了与超级计算机相匹敌的能力。目前对集群技术需求最迫切、发展最快的领域主要有:www应用、数据库应用等商业计算领域。
一﹑计算机集群的概念
集群 (Cluster) 技术是指一组相互独立的计算机, 利用高速通信网络组成一个计算机系统, 每个群集节点 (即集群中的每台计算机) 都是运行其自己进程的一个独立服务器。这些进程可以彼此通信, 对网络客户机来说就像是形成了一个单一系统, 协同起来向用户提供应用程序、系统资源和数据, 并以单一系统的模式加以管理。一个客户端 (Client) 与集群相互作用时, 集群像是一个独立的服务器。而集群其中的每一台提供服务的计算机, 我们称之为节点。当一个节点不可用或者不能处理客户的请求时, 该请求将会转到另外的可用节点来处理, 而对于客户端来说, 它根本不必关心这些要使用的资源的具体位置, 集群系统会自动完成。
集群中节点以何种方式来运行, 这要看节点是如何设置的。在一个理想的两个节点的集群中, 两个服务器都同时处于活动状态, 也就是在两个节点上同时运行应用程序。当一个节点出现故障时, 运行在出故障的节点上的应用程序就会转移到另外的没有出现故障的服务器上。这样一来, 由于两个节点的工作现在由一个服务器来承担, 自然会影响服务器的性能。
二﹑计算机集群的特点
1.提供强大处理能力的高性能计算机系统:计算机集群可以通过负载均衡、并行处理、时间片处理等多种形式, 将多台计算机形成高性能计算机集群。对用户端 (Client) 而言, 计算机集群则是一个单一的系统, 可以为用户提供高性能的计算机系统, 而用户不用关心有多少计算机承担了系统实现的任务, 而只需要关注系统的整体处理能力。因此, 计算机集群可以用多台普通性能的计算机组成具有高性能的计算机系统, 承担只有超级计算机才能胜任的工作。
2.提供高可用性的计算机系统:通过计算机集群技术组成的系统, 可以确保数据和应用程序对最终用户的高可用性, 而不管故障属于什么类型。即当计算机集群中的节点计算机出现软硬件故障的时候, 高可用性集群提供了对软件和硬件失败后的接替。它将服务器镜像到备用系统或节点中, 当主节点上的系统崩溃时, 冗余节点就从替补角色转换到正式角色, 并自动投入应用, 从而保证了系统运行的不间断。
3.系统具有很强的可伸缩性:在系统的处理能力需要增加的时候, 除了通过增加集群中每个计算机节点的单机处理能力 (如通过增加CPU数量、增加内存大小等手段) 外, 还可以通过增加集群节点数, 即通过向集群添加新的计算机节点, 使服务随着处理器的添加而伸缩, 从而增大应用程序吞吐量, 以达到增加系统的整体处理能力的目的, 完成系统的扩容。
三﹑并行算法的基本概念
算法就是求解问题的方法和步骤。并行算法, 就是在并行机上用很多个处理器联合求解问题的方法和步骤。实际上, 在自然界中并行是客观存在的普遍现象, 关键问题在于能不能很好地利用。由于人们的思维能力以及思考问题的方法对并行不太习惯, 且并行算法理论不成熟, 所以总是出现了需求再来研究算法, 不具有导向性, 同时实现并行算法的并行程序性能较差, 往往满足不了人们的需求。
四﹑并行算法的研究内容
并行计算模型的第一代是共享存储模型, 如SIMD-SM和MIMD-SM的一些计算模型, 模型参数主要是CPU的单位计算时间, 这样科学家可以忽略一些细节, 集中精力设计算法。第二代是分布存储模型。在这个阶段, 人们逐渐意识到对并行计算机性能带来影响的不仅仅是CPU, 还有通信。因此如何把不同的通信性能抽象成模型参数, 是这个阶段的研究重点。第三代是分布共享存储模型, 也是我们目前研究所处的阶段。随着网络技术的发展, 通信延迟固然还有影响, 但对并行带来的影响不再像当年那样重要, 注重计算系统的多层次存储特性的影响。
设计技术并行算法研究的第二部分是并行算法的设计技术。虽然并行算法研究还不是太成熟, 但并行算法的设计依然是有章可循的, 例如划分法、分治法、平衡树法、倍增法/指针跳跃法、流水线法等都是常用的设计并行算法的方法。另外人们还可以根据问题的特性来选择适合的设计方法。
五﹑小结
本章重点介绍了计算机集群和并行算法的概念、发展背景及意义。《海量数据并行传输任务分配与调度技术研究》采用了计算机集群及并行算法技术, 服务器节点呈层叠结构排列, 分为调度节点与子结点。在某个单位中, 调度结点只有一个, 调度服务器可能在下层搜寻负载最轻的子节点来进行并行操作。子结点有多个, 结点数可扩展, 增加层内节点数目即可提升系统处理大批量请求的能力。利用并行计算机技术提高数据处理的能力, 研究并行传输的处理模型和并行算法, 实现任务的优化拆分与动态分配;研究并行处理机负载与状态监控技术, 动态调整系统负载, 实现系统负载平衡, 为用户提供功能更为强大的算法。
并行计算技术 篇2
关键词：智能化分配算法,计算机负荷,并行处理技术,高效稳定
一、智能化分配算法的概述
网络技术和计算机技术的发展是近几年才在我国流行起来, 而随着发展的不断深入, 计算机负荷并行处理技术已经成为了重中之重。智能化分配算法是指利用总负荷的分配来达成提升计算机系统的效率、均衡计算机系统的负载、减少计算机系统的通信费用、缩短计算机系统的等待时间, 让整个系统能达到最佳的性能。目前我国的负荷并行处理技术主要应用于并行数据库技术、对称多处理技术、工作站群机技术、大规模并行处理技术以及并行程序开发环境技术。并行数据库技术主要针对的是计算机查询方面和计算机数据管理方面, 还包括数据库的并行查询方面和分区管理方面, 目前我国并行数据库技术中最为重要的是虚拟服务器技术以及多线程技术;对称多处理技术主要针对的是操作系统代码共享方面和主存共享方面, 这是因为对称多处理系统是由多个处理机用总线连接而成, 使得软件和硬件呈现对称现象, 而在软件上表现为操作系统代码的共享, 在硬件上表现为所有CPU能力的相等和主存的共享;工作站群机技术主要针对的是计算机并行处理系统, 这是因为工作站群机技术自身就是通过互联网把一组MPP系统、工作站、巨型机、小型机以及服务器连接起来的一种并行处理系统;大规模并行处理技术也称之为MPP, 它主要针对的是并行程序开发方面、高速互联网方面以及节点结构方面, 这是因为大规模并行处理技术中的MIMD型松耦合分布式存储的MPP系统是目前应用率较高的;并行程序开发环境技术主要针对的是软件的可移植性方面和编程方面。
二、基于智能化分配算法的计算机负荷并行处理技术
1. 单级树形网络的描述
假设一个单级树形网络是由链路以及处理器组成, 而基于智能化分配算法的计算机负荷并行处理技术的计算原理是当负荷到达时, 处理器中的根处理器会依照分配原则把总负荷平均分成几等份, 分配时要设定自身部分的负荷为一个定值, 然后把分好的负荷分配给各个子处理器, 当处理器得到所分配的负荷时, 其相对应的处理器就可以开始计算, 一直到所有的分配负荷全部完成后才能结束。设S为该服务器系统, n为系统中的可用节点, 从而得出系统S有Sn个负荷节点, 且每个节点之间为联合;设p为该系统所分配的数据分片, 系统S有Dp个数据分片, 且每个分片之间为联合;设m为该系统的任务数量, 系统S有Tm个任务, 且每个任务之间为联合;设W为该系统的等待任务队列, Q为该系统的队列长度, Wi为该系统中第i个节点已经接到的任务, 但是却没有来得及处理任务所组成的列队, Qi为该系统的列队长度, 且每个任务之间为联合;设L为该系统中每个节点的负载, 且每个负载之间为联合。
2. 基于智能化负荷分配算法
当某一时刻中的节点负载在CPU队列长度与所有节点负载在CPU队列长度成正比, 也就是说某一时刻的节点负载在CPU队列长度等于某一时刻的CPU队列长度除以某一时刻的所有节点负载。设T为处理器系统中节点的类型向量, n为节点负载中用于可以记录的取值节点类型向量的大小, 根据处理器系统的资源配置以及处理能力等条件, 所有节点的阀值设置成 (-1, 0, 1) , -1表示为当某一时刻的节点负载是欠载, 则节点是接受节点, 0表示为当某一时刻的节点负载是平衡, 则节点的负载大小适中, 1表示为当某一时刻的节点负载是超载, 则节点是发送节点。设Dm为整个系统中数据分片的分布矩阵中的取值, 也就是说是一种数据分布矩阵情况的表明, 其大小设置成 (1, 0) , 1表示为当某一时刻的节点负载有数据分片, 则节点是副本分布, 0表示为当某一时刻的节点负载没有数据分片, 则节点是副本分布。设R为处理系统中冗余分布的等级向量, D为数据分片中的某一个记录, 则一维向量的大小等于等级向量用于记录的冗余分布等级, 也就是说一维向量的大小是数据分片中某一个记录的副本数。
设Am为整个系统中的任务执行开销矩阵, 也就是说开销矩阵是某一任务进行分配在某一节点时, 所产生的执行开销;设Xm为整个系统中的任务分配矩阵, 也就是说矩阵是某一任务进行分配在某一节点时, 所产生的矩阵, 其大小设置成 (1, 0) , 1表示为当某一时刻的任务数量已经成功分配给当某一时刻的处理器, 0表示为当某一时刻的任务数量没有成功分配给当某一时刻的处理器;设Aa为整个系统中节点机进行任务执行的开销数组计算, 也就是说一维数组是用于进行每一节点记录所有任务的执行开销之和;设Tm为整个系统中任务与任务之间的通信开销矩阵, 也就是说通信开销矩阵是不同节点机用于分配所执行的任务与任务之间所产生的信息交换;设Ca为整个系统中用于任务通信节点机的开销组数, 也就是说一维组数是用于记录的通信开销组数与所有节点、所有任务的通信开销之和;设Fa为整个系统中节点机进行任务的总开销组数, 也就是说一维组数是用于记录任务总开销组数与通信开销、所有节点开销之和。
三、结束语
智能化分配算法是指利用总负荷的分配来达成提升计算机系统的效率、均衡计算机系统的负载、减少计算机系统的通信费用、缩短计算机系统的等待时间, 让整个系统能达到最佳的性能。本文通过假设一个单级树形网络来进行基于智能化分配算法的计算机负荷并行处理技术, 先后分析了智能化分配算法的优点和缺点, 此外智能化分配算法可以通过智能任务化和总体负荷化进行启动策略的选择、执行任务的计算、执行过程的考虑、节点进程的选择、通信开销的节约以及系统稳定的提升。
参考文献
[1]崔梦天, 赵海军, 李明东, 钟勇.基于智能化分配算法的计算机负荷并行处理技术[J].系统工程与电子技术.200 (826) :270—273
[2]高山.计算机负荷对电能计量的影响[J].供电用.200 (97) :51—52
[3]吴峻峰.多核计算机集群上的有限体积元自适应并行计算[J].电子技术.201 (214) :136—137
并行计算技术 篇3
渲染一个复杂的三维场景, 需要在一秒内处理几千万个三角形顶点和光栅化几十亿的像素。早期的3D游戏, 显卡只是为屏幕上显示像素提供一个缓存, 所有的图形处理都是由CPU单独完成。图形渲染适合并行处理, 擅长于执行串行工作的CPU实际上难以胜任这项任务。所以, 那时在PC上实时生成的三维图像都很粗糙。GPU卸载了CPU的图形处理功能, 使画面清晰流畅。
1 超长流水线技术
GPU的功能更新很迅速, 平均每一年多便有新一代的GPU诞生, 运算速度也越来越快。2004年推出的GPU Nvidia Ge Force 6800 Ultra可达到峰值40 Gigaflops (1 Giga FLOPS=1秒钟进行10亿次的浮点运算) , 2005年发布的Nvidia Ge Force7800 GTX更是将峰值提高至令人惊讶的169 Gigaflops。而Intel3GHz Pentium 4采用SSE指令集也只能达到6 Gigaflops (见图1) 。GPU的运算速度如此之快, 主要得益于GPU是对图形实时渲染量身定制的, 具有两点主要特征:超长流水线与并行计算。
1.1 流水线的工作原理
流水线技术与工厂里的装配线原理类似。如果装配一台汽车需10个时间单元, 将它分成10个流水线阶段, 每个阶段分配一个时间单元, 那么一条装配线每一个时间单元就可以生产一辆汽车。显然流水线模式的生产在理想状况下要比串行方式快了10倍。也就是说为了提高流水线的速度, 可以将任务划分成更小的单元, 这样流水线的级数就增加了。CPU的设计中就使用了流水线原理, 奔腾IV就有20级的流水线。但是流水线级数越多, 一条指令从开始进入流水线到最后被执行完毕这之间的延迟间隔会相当大。换句话说, 当流水线级数过多时, 控制台发出一条指令, 会经过很长时间才会真正生效, 这不适用于快速反应要求很高的场合。打个比方, 当用消防水龙头救火时, 正常情况下打开阀门开关几秒后水便喷射出来, 立刻可用来扑灭火灾。但是如果延迟了十几分钟, 才有水流出, 即使这时水流速度 (吞吐量) 还是很快, 不过这时火灾就会造成更大的损失了。CPU的设计目标是不仅要有很高的吞吐量, 还要求很小的延迟, 这是CPU并不采用过多流水线级数的原因之一。另外, 流水线只有在满载时, 才能发挥出最佳效率来。由于CPU执行的代码中有很多分支语句, 因此长流水线需要用有效的技术来预测分支, 尽量保持流水线在满负荷状态。但是, 一旦预测分支失败, 就会清除流水线中滞留的大量无用指令, 同时将新指令流重新注入流水线。如果流水线阶段过多的话, 充满整个流水线就需要很长的时间, 这样使流水线保持满载的机会不多, 速度反而下降了。所以权衡利弊, CPU不会选择深度流水线。
1.2 流水线技术在GPU中的实现
GPU采用了几百级的流水线, 比如Ge Force 3的流水线有800个阶段。GPU的应用为何可以忍受这么大的延迟呢?假设以每秒50帧的速率显示画面, 那么只要求每帧在20ms以内生成就行。而Ge Force 3的时钟频率是200MHz (每个时钟周期是5ns) , 5ns*800=4μs<20ms。所以, 对GPU来说这一些延迟根本不成问题, 而且GPU中执行的Shader程序中, 分支语句用的很少 (在早期的GPU中, 甚至不提供动态的分支语句) 。因此, GPU的流水线深度变大后, 利大于弊, 大大提升了整体性能。
GPU的执行速度很快, 但是当运行从内存中获取纹理数据这样的指令时 (由于内存访问是瓶颈, 此操作比较缓慢) , 整个流水线便出现长时间停顿。在CPU内部, 使用多级Cache来提高访问内存的速度。GPU中也使用Cache, 不过Cache命中率不高, 只用Cache解决不了这个问题。所以, 为了令流水线保持忙碌, GPU的设计者使用了多线程机制 (multi-threading) , 见图2。当像素着色器针对某个像素的线程A遇到存取纹理的指令时, GPU会马上切换到另外一个线程B, 对另一个像素进行处理。等到纹理从内存中取回时, 可再切换到线程A。但是使用这种方法有一个前提, 线程A与线程B没有数据依赖性, 也就是说两线程之间无需通讯。如果线程B需要线程A提供某些数据, 那么即使切换到线程B, 线程B仍是无法运行, 流水线还是处于空闲状态。不过幸运的是, 图形渲染本质上是一个并行任务。
2 并行计算
无论是CPU送给GPU的顶点数据, 还是GPU光栅生成器产生的像素数据都是互不相关的, 可以并行地独立处理。而且顶点数据 (xyzw) , 像素数据 (RGBA) 一般都用四元数表示, 适合于并行计算。在GPU中专门设置了SIMD指令来处理向量, 一次可同时处理四路数据。SIMD指令使用起来非常简捷, 可以看一个顶点矩阵变换的例子 (见下代码) 。此外, 纹理片要么只能读取, 要么只能写入, 不允许可读可写, 从而解决了存贮器访问的读写冲突。GPU这种对内存使用的约束也进一步保证了并行处理的顺利完成。
为了进一步提高并行度, 可以增加流水线的条数。在Ge Force 6800 Ultra中, 有多达16组像素着色器流水线, 6组顶点着色器流水线。多条流水线可以在单一控制部件的集中控制下运行, 也可以独立运行。在单指令多数据流 (SIMD) 的结构中, 单一控制部件向每条流水线分派指令, 同样的指令被所有处理部件同时执行。另外一种控制结构是多指令多数据流 (MIMD) , 每条流水线都能够独立于其他流水线执行不同的程序。Ge Force 6800 Ultra的顶点着色器流水线使用MIMD方式控制, 像素着色器流水线使用SIMD结构。MIMD能比较有效率地执行分支程序, 而SIMD体系结构运行条件语句时会造成很低的资源利用率。不过SIMD需要硬件少, 这是一个优势。
CPU中大部分晶体管主要用于构建控制电路 (例如分支预测等) 和Cache, 只有少部分的晶体管来完成实际的运算工作。而GPU的控制相对简单, 且对Cache的需求小, 所以大部分晶体管可以组成各类专用电路、多条流水线, 使得GPU的计算速度有了突破性的飞跃, 拥有了惊人的处理浮点运算的能力。现在CPU的技术进步正在慢于摩尔定律, 而GPU (视频卡上的图形处理器) 的运行速度已超过摩尔定律。
3 结束语
虽然GPU最初是专门为图形渲染设计的, 但是GPU还可以有效地执行多种通用计算, 从线性代数和信号处理到数值仿真等等, 有的专家甚至认为GPU将进入计算的主流。
参考文献
[1][美]费尔南多 (Randima Fernando) .GPU精粹:实时图形编程的技术、技巧和技艺[M].姚勇, 王小琴, 译.北京:人民邮电出版社, 2006.
[2][美]法尔 (Matt Pharr) .GPU精粹2:高性能图形芯片和通用计算编程技巧[M].龚敏敏, 译.北京:清华大学出版社, 2007.
[3]The Cg Tutorial:The Definitive Guide to Programmable Real-Time Graphics.
并行计算技术 篇4
1 虚拟化技术的优势
虚拟化技术是在计算机硬件和软件体系的基础上, 在计算机系统构件出全新的软件层, 以便形成虚拟机监控器体系。依照类别来分, 可以将其分为:平台虚拟化, 它是针对计算机和操作系统的虚拟化, 又分成服务器虚拟化和桌面虚拟化;资源虚拟化, 针对特定的计算资源进行的虚拟化;应用程序虚拟化, 它包括仿真、模拟、解释技术;表示层虚拟化。在应用上与应用程序虚拟化类似, 所不同的是表示层虚拟化中的应用程序运行在服务器上, 客户机只显示应用程序的UI界面和用户操作。相对于传统的技术模式, 虚拟化的优势主要集中以下几个方面:其一, 物理资源抽象化能力, 可以在物理资源差异性, 分布式屏蔽的方面发挥作用, 由此使得物理资源可以在软件层面上获取视图以及访问接口;其二, 有利于实现底层物理资源的统一管理以及灵活配置;其三, 可以对于系统指令运行实现全面监控, 从而达到敏感指令的获取。下图为虚拟化技术的运行流程。
2 虚拟化技术在并行计算机中的应用问题
所谓并行计算机, 是指可以进行并行计算的计算机。相对于传统单独计算机来讲, 其无论是计算机信息处理能力, 还是计算机信息存储能力, 都是比较优越的。至于虚拟化技术与并行计算机的关系, 我们可以从以下的角度来进行理解:并行计算机体系结构是发挥其效能的关键, 两种体系结构:SMP与COW, 也存在各自的缺陷, 更好的将两者融合到一起, 趋利避害, 是现阶段研究人员不断研究的问题。而虚拟化技术的应用, 也将成为并行计算机系统中的关键性问题。简单来讲, 保证其能够发挥最大优势之一的关键技术就在于其中的虚拟化技术, 但是其在应用的过程中遇到了很多问题和缺陷。其主要表现为以下几个方面的内容。
2.1 集群方案结点地位不对称带来的困扰
众所周知, 虚拟化技术要想能够在综合贡献, 分布存储等方面发挥作用, 是以其两种并行结构优势为基础的。而其实现途径之一就是集群方式, 这种方式却在结点地位不对称的方面带来了负面影响。实际上, 以机群机构为结构形式, 可以形成多处理器工作站, 多虚拟机服务器, 以保证操作系统和应用软件的运行, 其的确可以在共享存储和分布存储方面发挥着积极作用, 但是由于其平台有着不同的结点地位, 需要设立管理结点, 在任务分配和资源信息不全的基础上, 使得其结点担负任务量过大, 会影响其运行质量。
2.2 虚拟化技术应用弱化了计算机资源利用率
将虚拟化技术运用到并行计算机体系中去, 集群方式的确可以获得比较好的效果, 但是其问题在于:编程工作任务量大, 难以针对于用户需求进行单一的系统映像, 在实现任务分割和分配的过程中也面临着同样的问题, 由此使得计算机资源利用效率处于较低状态。如果这个问题难以解决, 及时集群可以达到良好的效果, 但是其在运行过程中计算机资源利用率处于较低状态, 也难以发挥其最大效能。因此, 在今后的研究工作中, 应该积极以此为突破口去进行尝试和探索。
3 虚拟化技术在并行计算机中的应用策略
虚拟化是并行计算机系统中的关键性技术, 如何保证将其最大效能发挥出来, 就需要我们针对于上述存在的缺陷和不足, 积极采取有效措施进行改善, 以保证其能够更好的发挥其效能。具体来讲, 我们需要从以下角度入手。
3.1 DVMM新型机群体系结构的采用
为了能够应对上述提到的集群方案存在的不足之处, 可以将DVMM新型机群体系机构运用进去, 简单来讲, 是在集群方案结点硬件的基础上, 构建不同结点完全对等的结构和功能体系, 使得控制器可以更好的感知资源, 整合资源和呈现资源, 使得系统运行朝着透明化, 单一化, 共享化和分布存储化的方向发展和进步。这种模式不仅仅可以尽量的消除劣势, 使得成本处于可控状态, 还具备良好的扩展性, 有利于编程工作的开展, 使得整体性能不断增强, 由此被认为是目前比较有前景的新型机群体系结构。
3.2 实现虚拟化技术计算机资源利用率的提高
针对于虚拟化技术在计算机资源利用率方面的问题, 我们应该积极开展措施, 正确将物理服务器资源整合成为一个具备单一系统映像的虚拟资源集合体。详细来讲:其一, 迎合实际情况, 构建服务器整合方案, 在单台物理器的基础上构建多台虚拟服务器, 以保证对于物理设备资源的充分使用。这样一来不仅仅可以使得硬件资源虚拟化管理和分配变得简单, 还可以构建支持操作系统和应用软件的系统环境, 并且两者互不干涉。在这样的模式下, 使得单台物理服务器在不同虚拟机中处于运行状态, 节省了有效的物理资源, 还使得单台物理服务器得到了最大化的应用。当然, 也存在特殊的情况:用户资源需求量高于单台物理服务器资源量, 可以选择以VM集群方案来进行操作, 以保证计算机资源利用效率处于理想状态。
4 结论
综上所述, 虚拟化技术运用到并行计算机中, 不仅仅是并行计算机系统不断完善的需求, 也是信息技术不断发展的要求。处于这样的背景下, 应该积极探析目前存在的缺陷和不足, 并且以此为出发点, 积极采取有针对性的措施进行改善和调整, 以保证虚拟化技术能够在并行计算机中充分的展现其效能。
参考文献
[1]马一楠.虚拟化技术在并行计算机中的应用探讨[J].价值工程, 2010 (24) .
[2]彭近兵, 龙翔, 肖利民.实现SMP机群虚拟化的方法[J].北京航空航天大学学报, 2009 (3) .
[3]应必善, 康继昌, 顾伟康, 姚庆栋.虚拟共享存储体系结构并行计算机的原理和实现技术[J].浙江大学学报 (自然科学版) , 1996 (6) .
[4]师红玉, 林国华.虚拟化技术在并行计算机中的有效应用探讨[J].内江科技, 2011 (11) .
并行计算技术 篇5
1.1 项目背景
高分遥感在电子政务地理空间基础信息库建设与服务中的应用示范项目, 是高分重要的应用示范项目, 依托“国家自然资源和地理空间基础信息库”一期工作, 重点解决高分辨率遥感卫星数据与国家自然资源和地理空间基础信息库的融合, 推进高分数据在电子政务地理空间基础信息库的综合应用示范, 形成高分数据及其电子政务应用产品通过共享平台进行分发和共享的机制和格局, 为国家宏观综合决策服务, 包括资源环境综合监测评价、灾后重建规划实施效果监测、区域发展战略研究和区域规划、资源环境领域规划和重大基本建设项目跟踪及效益监测以及海洋资源开发和经济发展的监测工作等, 以及为政府综合部门、业务服务和电子政务业务部门及社会公众服务。
1.2 要求
为满足海量遥感数据的需要, 建设了高分遥感数据集群式生产系统, 该系统具有高效、自动、智能的技术特性, 遥感影像处理的基础支撑平台, 提供统一的数据模型、业务模型接口, 能够支撑起大规模遥感影像的集群式并行自动化处理。
2 遥感影像处理结构层次
遥感影像操作可以划分为三个不同的层次或者类别, 下面就对其进行一一分析。首先为像素级操作, 这是通过一副像素影像产生另外的像素影像, 包括邻域、括点、几何操作等, 很多数据都是有规则、几何、局部。而这种几何操作在进行遥感影像处理时表现为几何校正, 因为装载在飞机、卫星的成像传感器受到飞机姿态、卫星、时间、运动、气候等不同因素的影响, 其摄取的图像可能出现几何畸变的现象, 因此, 要能够完成旋转、重新定位、任意弯曲等操作;其次, 其具有特征性操作的特征, 这也是相关影像产生的特征, 包括区域和线, 常规性的特征包括纹理、形状、三维特征、梯度特征, 一般选择一致的测度, 包括方差、均值来进行处理和描述, 其显示特征区域进行的可行性, 而且, 还具有非局部、象征意义的特性, 在局部区域并行的同时, 还要能够对整体加以处理;再者具有目标级操作的特征, 这是由一系列特征诱发的目标, 并且其信息具有复杂性、象征意义, 一般都是通过相关知识来处理, 从而对影像进行理解、描述、解释。
3 通信和同步
在并行计算期间, 因为不同进程之间需要传输以及调度数据, 因此, 其具有相应的通信开销, 并且这种开销表现为以下不同的方面, 首先为传输等进程之间的数据, 主进程从进程调度、数据传输、任务分配入手。在处理遥感影像时, 需要能够划分影像, 并且将其映射给进程加以处理和计算, 其主要依据就是被划分部门的数据通信量, 三种图像数据划分方式, 如图所示, 其中图1表示水平条带、图2为竖直条带、图3为矩形块, 不同划分的条带边界表现为所要进行的通信数据。在处理不同影像时, 要能够选择不同的划分方式, 像素级的处理并行化分支较小, 进行数据划分时较为简单, 可以结合实际状况来选任何划分方法, 特征处理如线条所示, 按照竖直条带和水平条带来划分, 在目标级、特征级处理期间, 需要结合相应的问题、并行计算支撑环境来选择具体的划分方式。从一定角度来分析, 要想能够达到并行化的要求, 从而让被划分的数据通信量达到最小的要求。
在并行系统执行给定算法期间, 可能会出现个别进程计算需要在其他进程完成之后才能开展, 这时候同步是需要的, 所谓的同步就是在这种状况下顺利使用通信协调技术不受到影响。同步也存在以下两种不同的开销, 包括同步需要所有处理机能够进行相应的检验, 但是, 需要花费相应的时间;其次个别处理器可能为闲置, 等待准许继续续需要计算相应消息。
4 结语
高分遥感在电子政务地理空间基础信息库建设与服务中的应用示范项目, 是高分重要的应用示范项目, 依托“国家自然资源和地理空间基础信息库”一期工作, 重点解决高分辨率遥感卫星数据与国家自然资源和地理空间基础信息库的融合。通过实验不难发现, PC机群上所具有的分布式并行算法优势较为明显, 但是, 其通信开销依然是算法中需要解决的主要问题, 在集群逐渐扩展的影响下, 通信开销开始增长, 这就让并行化程度遭到制约, 选择直接少通信量、通信次的方法则能够降低实际的通信开销, 从而为实现遥感卫星数据和国家自然资源信息库融合奠定坚实的基础。
参考文献
[1]杨海平, 沈占锋, 骆剑承, 吴炜.海量遥感数据的高性能地学计算应用与发展分析[J].地球信息科学学报, 2013 (01) :128-136.
[2]王竹晓, 胡宏, 陈立民, 史忠植.动态描述逻辑推理的并行计算技术[J].计算机研究与发展, 2011 (12) :2317-2325.
[3]马伟锋, 李伟.遥感影像数据并行计算中数据分配策略研究[J].浙江工业大学学报, 2016 (03) :270-274.
并行计算技术 篇6
微粒群算法 (PSO) 是由Kennedy和Eberhart等[1]于1995年开发的一种演化计算技术, 来源于对一个简化社会模型的研究[2]。微粒群算法是一种基于群体智能的随机优化算法, 通过微粒追随自己找到的最好解和群体找到的最好解来完成。自微粒群算法提出以来, 由于它的计算快速性和算法本身的易实现性, 引起了国际上相关领域众多学者的关注和研究[3]。
在微粒群算法中, 应用问题的规模直接决定了PSO的执行效率。然而并行计算是实现高性能、高可用计算机的主要途径。因此, 并行PSO的研究对于大规模或超大规模的多变量求解具有很重要的意义。近年来, 已有学者对并行微粒群算法从不同角度进行研究。文献[4]提出的并行仿真, 使每个粒子的行为成为一个独立的线程, 进化中的粒子个体充分表现出独立性、种群表现出异步性。文献[5]主要研究的是并行PSO算法中三种不同的通信策略。依据算法中各个参数之间的关联程度不同, 提出了三种不同的通信策略。文献[6]提出基于岛屿群体模型的并行PSO算法不仅提高了求解效率, 而且改善了早收敛现象。文献[7]将设计的并行PSO算法应用于生物力学的一个实例中, 文献[8]研究一种细粒度的并行微粒群算法, 将它应用于系统辨识, 结果表明:并行PSO算法具有很好的效果。
本文首先介绍BSP并行计算模型, 接着提出了基于BSP并行计算模型的并行PSO算法。该算法改变了标准PSO算法的结构, 提高了算法的求解效率。
1 并行BSP计算模型
并行计算模型是并行计算机基本特征的抽象, 是并行算法设计和分析的基础。并行算法的设计不能局限于某种具体的并行计算机, 而必须借助抽象的计算模型。并行计算模型与并行算法设计、并行机之间有密切联系。
一个BSP计算机由n个处理机/存储器组成, 通过通信网络进行互联。在BSP模型中, 计算系由一系列用全局同步分开的周期为L的超级步 (superstep) 所组成。在各超级步中, 每个处理器均执行局部计算, 并通过选路器接收和发送消息;然后作一全局检查, 以确定该超级步是否已由所有的处理器完成;若是, 则前进到下一超级步, 否则下一个L周期被分配给未曾完成的超级步。
一个BSP程序有n个进程, 每个驻留在一个节点上, 程序按严格的超步顺序执行, 超步间采用路障同步, 如图1所示。每个超步分成如下有序的三个部分:
(1) 计算
一个或多个处理器执行若干局部计算操作。操作的所有数据只能是局部存储器中的数据, 这些数据是在程序启动时或由以前超步中的通信操作存放在局部存储器中的。结合BSPPSO算法, 多个子群体被分配在不同的处理器上独立地进化计算, 利用子群体内各个粒子的历史最好位置和群体最好位置, 搜寻子群体内部的最好解。
(2) 通信
处理器之间相互交换数据, 通信总是以点对点的方式进行。在BSPPSO算法中各个子群体相互交换信息, 不断更新全局最好位置。
(3) 同步
确保通信过程中交换的数据被传送到目的处理器上, 并使一个超步中的计算和通信必须全部完成之后, 才能开始下一个超步中的任何动作。在BSPPSO算法中, 等到所有子种群体局部进化结束, 相互比较最好信息, 得出当前的全局最好位置, 再开始继续循环整个进化过程。
BSP的一个特点是, 它将计算任务和通信任务分开。它简化了算法的设计和分析, 当然就牺牲了运行时间, 因为所谓的整体大同步意味着所有的进程均必须等待最慢者。考虑异步方式的耦合性更高, 更容易产生通信瓶颈。本文采用的是同步方式。
2 并行BSPPSO算法
算法流程描述如下:
Step1:初始化整个种群。对每个粒子的随机位置和速度进行初始设定。每个粒子由计算得到初始的适应值和初始的个体最好位置Pi及初始的群体最好位置Pg。
Step2:将整个种群分为几个子种群。各个子种群独立进化。
2.1:
在每个子种群中, 根据粒子自身的最好位置Pi和全局最好位置Pg按照进化方程进化, 然后计算粒子的适应值。
2.2:
在各个子种群独立的进化中, 若某个子种群中粒子的适应值比全局最好位置Pg的适应值好, 则它作为当前的全局最好位置Pg。其它子种群依据该Pg值继续进化, 直到进化最慢的子种群更新完全局最好位置Pg。
Step3:若未达到结束条件 (足够好的适应值) , 则返回步骤2.1, 各子种群继续循环迭代, 直到满足条件。
分析BSPPSO算法:各个子种群内部独立的利用各个粒子的历史最好位置和群体的全局最好位置按照进化方程独立进化。由于各个子种群进化快慢不同, 当进化较快的一些子群体经过比较, 得出当前的最好位置Pg, 则该Pg会影响到正在进化中的其它子种群, 能引导它们的粒子更快地朝最好位置飞去。加快了算法的收敛。这样, 各个子种群既能充分利用自身的值进行搜索, 不会迷失自己的方向, 又能及时得到全局最好位置Pg的引导, 达到最好值。
3 仿真实验
本文采用两个无约束优化基准测试函数, 分别用经典PSO和BSPPSO进行仿真实验, 并对实验结果进行比较, 以验证BSPPSO的寻优性能。测试函数是:
F1:Sphere函数
F2:Rosenbrock函数
为了提高可比性, 本文在两种算法中取同样的调整参数。惯性权重W的取值在整个搜索过程中从1.0减至0.4。粒子总个数为60。在BSPPSO中将整个群体划分为三个子群体, 每个子群体为20个粒子。各个子种群用不同的线程独立进化。实验在Windows环境下用多线程技术对BSPPSO进行模拟, 开发环境为VC++6.0。实验结果如表1所示。
在实验中分别对两种算法重复运行50次取平均。由于文章篇幅所限, 只列出其中性能改善较明显的两个函数。从结果中看, 对标准PSO很难收敛的Rosenbrock函数, BSPPSO算法极大地提高了它的收敛率和收敛速度。对于100维的Sphere函数, 在平均收敛代数近似相同的情况下, 收敛率比标准PSO要提高很多。从图2～图3中, 我们可以看到在两种算法下, 随着迭代次数的增加, 适应值的变化情况不同。总之, BSPPSO与PSO相比, 收敛性得到了加强, 适应值更好。
4 结 论
本文将BSP并行计算模型引入标准PSO, 从结构上改变了标准PSO算法的模式。基于BSP模型设计了一种全新的并行粒子群优化算法, 并将它进行并行实现。该并行算法提高了搜索效率, 同时使算法性能得到了很大改善。
摘要：在对标准微粒群算法分析的基础上, 将它与BSP并行计算模型相结合, 设计并实现了一种基于BSP并行计算模型的并行微粒群算法。这种基于BSP并行计算模型的并行微粒群算法改变了标准微粒群算法的结构, 提高了算法求解效率。实验结果表明, 该并行算法的性能比标准微粒群算法有了很大的提高。
关键词：演化计算,BSP并行计算模型,微粒群算法
参考文献
[1]Kennedy J, Eberhart R.Particle swarm optimization[A].proc IEEE Int Conf on Neural Networks, perth, 1995:19421948.
[2]谢晓峰, 张文俊, 杨之廉.微粒群算法综述.控制与决策, 2003, 18 (2) :129134.
[3]曾建潮, 介静, 崔志华.微粒群算法.北京:科学出版社, 2004.
[4]罗建宏, 张忠能.并行仿真的粒子群优化算法异步模式研究.计算机仿真, 2005, 22 (6) :6870.
[5]Chang Juifang, Chu Shuchuan, John f Roddick Pan Jengshyang.A Par-allel Particle Swarm Optimization Algorithm with communication strate-gies.Journal of information science and engineering, 2005, 21:809818.
[6]黄芳, 樊晓平.基于岛屿群体模型的并行粒子群优化算法.控制与决策, 2006, 21 (2) :175179.
[7]Schutte J F, Reinbol J A, Fregly B J, et al.Parallel Global Optimization With the Particle Swarm Algorithm.Int.J.Numer.Meth.Engng, 2003.
并行计算的内存访问方法 篇7
本发明主要涉及到计算机技术层面的内容, 尤其针对多线程的PDF格式文件操作中的内存访问控制, 同时由此引申到多线程并行计算时的内存访问有效策略及如何更好提高运行效率的方式, 下面就该发明的技术背景及发明内容做详细的介绍。
当前图书、图片、文件等实体资源的数字化, 通常是采用扫描——识别——提取的方式。先将文档扫描为PDF格式, 再进行文档模块和文字的识别, 之后提取识别后的信息, 供编档和供给搜索引擎以供建立索引。由于现有技术的限制, 在对大量文档处理过程中存在占据大量系统资源的问题, 导致处理速度减慢, 当前的多核处理器技术逐步成熟, 首选方式是在多个CPU上同时实现多线程的运行。但现实操作中仍存在提速有限且CPU未能完全利用的问题, 为此发明人结合业内多年工作经验及实验操作分析和研究该问题的成因, 发现要归因在内存操作中其分配和释放需要县城保护, 并且全部线程共享同个内存池, 这类因素导致访问需要等待, CPU效用率低, PDF的频繁操作会使得大量出现线程等待。
为了改善内存访问, 本领域技术人员提出了多种方法。例如, 专利授权公告号:CN100487660C, 名为“一种多线程处理器动态内存管理系统及方法”的中国发明专利公开了一种多线程处理器动态内存管理方法, 该方法在一定程度上解决了内核线程的内存释放问题, 能够避免某一时刻某一空闲的内核线程占用过多的空闲内存。由主控内核线程取代硬件仲裁器, 利用消息机制, 提高了内存在各个内核线程间的分配使用效率。但是该方法却无法解决共享一个内存池的多个线程均请求较大内存空间而必须排队等候的问题。并且应用此方法, 要改变内存管理代码, 并不适合代码的直接移植。
2 本发明具体内容阐述
(1) 本发明目的在于针对多个线程调用同一个执行模块时, 由于必须共享同一内存池, 且该内存池无法提供足够资源而导致内存访问等待时间过长的问题, 提供一种新的内存访问策略, 以缩短甚或消除并行计算时的内存访问等待时间, 使单个线程能够拥有独立的内存池。能在不改变或很少改变模块代码特别是完全不改变内存管理的情况下, 将单线程代码, 简单移植到多线程环境中。并让多核多线程的优势得到充分发挥。
(2) 本发明的并行计算的内存访问方法, 用于存在调用同一原始执行模块的n≥2个并行线程的情况, 其特征在于, 包括以下步骤:
S1) 根据线程数n确定需创建的映像执行模块的个数k, n-1≥k≥1;
S2) 确定该n个线程与原始执行模块及k个映像执行模块之间的映射策略F;
S3) 创建k个映像执行模块, 并为其分配各自私有的内存池;
S4) 执行所述并行的n个线程, 令各个线程按照所述映射策略F调用执行模块, 每个执行模块访问且仅访问其私有的内存池;
S5) 线程运行完成后删除创建的映像执行模块, 释放资源。
其中, 所述映像执行模块的个数为k可以是随时间变化的。或者, 所述映像执行模块的个数k在线程执行期间也可是固定不变的。较佳地, 可根据同一时间调用同一执行模块的线程个数的统计值来确定映像执行模块的数量。
根据本发明的一实施例, 所述映像执行模块的个数k为1个。根据本发明的另一实施例, 所述映像执行模块的个数k为n-1个。其中, 当所述映像执行模块的个数k为n-1个时, 所述映射策略F可为:每个线程分别调用一个不同的执行模块, 线程与执行模块是一一对应的。根据本发明的再一实施例, 所述映射策略F可为静态策略, 一个线程仅指向一个被它调用的执行模块, 而一个执行模块被一个或一个以上的线程调用。较佳地, 所述映射策略F为将调用执行模块频繁的线程, 配置为独享一个执行模块, 将相对调用执行模块频率较低的线程, 配置为共享执行模块。根据本发明的又一实施例, 所述映射策略F为动态策略的“多窗口排队”机制, 该策略F中, 为每个执行模块定义“空闲”、“繁忙”两个状态, 将所有的空闲执行模块排队需要调用执行模块的线程从空闲执行模块队列中择一调用, 若没有空闲的则等待;在线程对执行模块的调用进行中将该执行模块标记为繁忙, 执行完毕后, 线程释放该执行模块, 将其标记为空闲。
应用本发明的方法可令并行计算的效率随核心数增加而呈线性增长, 而不受内存访问瓶颈的限制。对各种操作系统均可适用。并且使用静态方式时, 甚至无需增加代码, 即可将单线程的程序直接移植到多线程环境。而灵活的动态方式和动态映射策略, 则可使本发明在占用不是那么多的系统资源的情况下显著提高效率, 事半功倍。
(3) 本发明目的在于, 在不改变操作系统的内存管理的前提下, 改变内存访问方式。为对便于对本发明进行更好的理解, 首先对一般的内存管理方式进行说明。内存管理的特点之一是执行模块是隔离的, 每一个执行模块被分配独立的内存池空间。其中, 执行模块可视为是系统在内存中建立的一个个数据结构, 用于管理运行时加载到内存中的程序代码, 数据以及资源。每个执行模块作为一个系统资源的分配单位, 享有其独自的内存池, 执行模块中的多个函数将共享该执行模块的内存池。所述执行模块可以是运行后被加载到进程中的一个windows下的.exe程序或一个动态链接库 (dll) 等。同一个执行模块, 不论多少个线程在调用, 只会被加载一次, 由同一个进程开启的所有线程, 对于同一执行模块, 它的内存池是共享的。依照操作系统类型的不同, 执行模块还可有其它形式。按照本领域技术人员的公知, 不同的操作系统的内存管理模式会有区别, 但是均会存在这样一种特定的单元, 其由一些数据和代码的集合构成, 表现为程序、函数等形式, 并且对该种代码组合操作系统会分配私有的 (private) 内存空间 (包括逻辑的或物理的) 以供其访问。因此, 在本发明中, 执行模块也可理解为在给定操作系统下, 依据该操作系统的默认内存管理方式而为其分配单独的内存池的一组代码和数据的集合。
专利名称:并行计算的内存访问方法
专利号:ZL 2010 1 0140502.6
申请日:2010.04.07公开日:2013.04.17
申请人:福州福昕软件开发有限公司林芝
摘要：本发明是一种有关计算机并行计算的内存访问的方法, 用于存在调用同一原始执行模块的n≥2个并行线程的情况, 包括以下步骤:S1) 根据线程数n确定需创建的映像执行模块的个数k, n-1≥k≥1;S2) 确定该n个线程与原始执行模块及k个映像执行模块之间的映射策略F;S3) 创建k个映像执行模块, 并为其分配各自私有的内存池;S4) 执行所述并行的n个线程, 令各个线程按照所述映射策略F调用执行模块, 每个执行模块访问且仅访问其私有的内存池;S5) 线程运行完成后删除创建的映像执行模块, 释放资源。本发明可令并行计算的效率随核心数增加而呈线性增长, 而不受内存访问瓶颈的限制。各种操作系统通用, 且便于将单线程的程序直接移植到多线程环境。