网络并行计算

网络并行计算（精选九篇）

网络并行计算 篇1

关键词：并行计算,网络安全,密码算法,ELGamal公钥密码

传统的网络安全主要是针对网络中数据的保密性, 但现在安全的概念已经不仅仅局限于此, 它包括可用性、完整性、可控性和不可否认性, 以及攻击、防范、控制等多个方面。网络安全是一个综合, 交叉的学科领域, 它要综合利用数学、通信和计算机诸多学科的长期知识积累和最新发展成果。如何利用密码学破解信息安全问题, 最近几年备受关注。

1 什么是密码算法

密码算法是用来加密和解密的数学函数, 它是密码协议的基础。主要包括分组密码、序列密码、散列函数等, 公钥密码。在计算机系统中, 数据是用二进制来表示的, 当然发送的信息P则一定是二进制。可被传送或存储的是明文, 待加密的消息用M表示。C表示密文也是二进制数据, 一般而言它大于等于待加密的消息M。E表示加密函数, M、C之间的关系可表示为:

D是解密函数作用于C产生M, 是解密的逆过程

要恢复原始的明文消息, 需要先加密后再解密消息, 下面的等式必须成立:

2 ELGamal公钥密码体制

ELGamal公钥密码是目前网络上进行保密通信和数字签名有效的算法, 是目前比较好的密码体制。该算法既可数据加密也可数字签名。ELGamal公钥密码体制的加解密描述如下:

密钥对的产生。首先选一个素数p, 两个随机数, g和x, (g<p, x<p) , 计算y=gx (mod p) 。则

公钥:y, g和p

私钥:x, g和p

El Gamal用于数字签名。被签信息为M, 首先选择一个随机数k, k与p-1互质, 计算

再用扩展Euclidean算法对下面方程求解b:

签名就是 (a, b) 。随机数k须丢弃。

验证时要验证下式:

必须满足1<=a<p.否则签名容易伪造。

El Gamal用于加密。M为被加密信息, 首先随机选择一个数k, k与p-1互质, 计算

(C1, C2) 为密文, 是明文的两倍长。解密时计算

3 并行计算

并行计算是相对于串行计算来说的, 并行计算分为空间和时间上的并行。空间上的并行是指用多个处理器同时执行计算, 时间上的并行则是指流水线作业技术, 并行计算虽分成空间和时间上的并行, 但主要研究的是空间上的并行, 而且产生了两类并行机。按照Flynn的说法分为:单指令多数据流 (SIMD) ;多指令多数据流 (MIMD) 。并行计算能够在同一时间内处理多指令、多任务或多数据项。

如何在短时间内完成这些计算, 并行计算机及并行计算技术因此而受到人们的青睐。它具有以下几个方面的优点:

能够节省时间和成本:要使同一任务能提前完成需要调用更多的资源, 从而节约了成本。更重要的时在构建并行族群时可使用便宜的或者是即将淘汰的CPU。

能够解决大规模的问题:用单个计算机来解决许多庞大而复杂的问题是不切实际或不可能的, 尤其是计算机的内存受到限制的时候。

能够支持并行:多个计算资源能够同时做多件事情而单一计算机资源同一时刻只能做一件事情。

4 并行计算技术在加解密过程中应用

在网络安全中, 密码处于基础地位, 都希望能在密码的计算过程中加快速度, 缩短时间。但目前所用的密码算法加解密的速度都不够快, 远远不能满足许多领域的要求, 即使是DES, 当今最快的分组密码, 其加解密的速度也一样不够快。使用并行计算进行加解密可以在密码学中成倍的提高速度, 针对El Gamal公钥密码体制在其加密时需要计算的密文对是并行的, 相互独立的, 所以能用并行技术计算加密时的密文对。

以El Gamal公钥密码体制为例, 采用MPI编程, MPI是一个消息传递接口的标准, 用于开发基于消息传递的并行程序, 目的是为用户提供一个实际可用的、可移植的、高效的、灵活的消息传递接口。

在用并行技术进行加解密时应先搭建Miracl (Multiprecision Interger and Rational Arithmetic C/C++Library) 实验平台, 它是由Shamus Software Ltd所开发的用于设计与大数相关的密码学加密体制的大数运算函数库。它运算速度快, 提供源码, 是当前使用较为广泛的基于公钥密码体制保护失效的大数库之一。

通过观察ELGamal公钥体制自身特性可以发现, ELGamal公钥密码体制在加密时需要计算一个密文对。即需计算C1, C2。他们之间是相互独立的块, 所以能并行执行。并行算法具体设计如下:

(1) 生成随机数g, x;

(2) 在GF (p) 上计算密钥;

(3) 选一个随机数k, 满足k与p–1互质;

(4) 根据公钥y和随机数k并行计算密文对C1, C2即进程1计算密文C1, 进程2计算密文C2;

(5) 根据私钥x和密文对C1, C2计算机明文消息。

使用MPI并行程序来实现并行算法, ELGamal公钥密码体制并行部分的核心代码如下:

5 结论

在密码的加解密过程中, 使用并行计算可以大大提高速度, 比用串行计算能够缩短已被的时间。并行计算和密码学的结合为推进了网络安全的发展。

参考文献

[1]赵晓光.并行计算在网络安全中的应用[J].网络安全技术与应用, 2004 (9) .

[2]周伟明.多核计算与程序设计[M].武汉:华中科技大学出版社, 2008.

三维低速NS方程的并行计算 篇2

三维低速NS方程的并行计算

本文在求解低速NS方程的串行程序基础上,针对分布式存贮网络异构的`并行编程环境建立了隐式并行计算软件,并行计算的方法采用区域分解法.并行软件对高速列车进行了气动特性计算,并对并行效率和并行可靠性进行了研究,结果表明:并行计算结果与串行计算吻合良好,并行改造后的软件可以应用于工程实际问题.

作 者：王开春 李树民 朱国林 作者单位：中国空气动力研究与发展中心,四川,绵阳,621000刊 名：空气动力学学报 ISTIC EI PKU英文刊名：ACTA AERODYNAMICA SINICA年，卷(期)：20(z1)分类号：V211.3关键词：低速NS方程 并行计算

网络并行计算 篇3

1 网络数据传输中问题描述

1.1 假设问题

假若计算机网络只有一条通道对节点上的多数信息进行传输, 这时可利用G= (N, L) 这一数学模型来描述被传输的信息;该通道的通信传输有较强的稳定性, 可对各节点间的数据进行有效传输;传输通道的网络可靠性和介质长度之间无需对数据进行直接交换。

1.2 问题模型

研究表明, 计算机网络节点间连线载体的成本数学模型公式如下:

其中, C为载体总有成本, N为总有交叉点数, Diaij是从i和j两个交叉点间逻辑连线最的载体数量, α和β为网络交叉点常数。gij=1, 说明i与j两个节点间存在直接的通讯连线;如gij=0, 说明i与j两个节点间没有直接的通讯连线。

在R最大化, 且C≤C0时, 计算机网络的整体可靠度模型如下所示:

其中, P (li) 表示第i条节点线路载体的可靠程度, Ω是网络中正常状态的总合, li表示第i条节点线路的载体。

2 并行遗传算法优化计算机网络可靠性过程

并行遗传算法可分为粗粒度、细粒度和主从式度三类模型。粗粒度模型十七中为有效的一种, 其有较强的适应能力, 被广泛应用于并行遗传算法模型中。其主要是将随机形成的初始群体利用处理器将其分割成为无数个子群体, 子群体在各个处理器上互相独立的进行并行操作, 只有经过指定的进化代, 子群体将会对无数个个体进行交换, 引进新型的优异基因, 是子群体更加多样化, 可有效避免基因在还未到达成熟期时开始收敛。该算法模型由于通信成本较小, 因此, 较适于实施在集群系统没有较高的通信网络时。

经研究表明, 以pop=m*pops群体规模保持不变为基础, 对子群体的数量进行适当增加, 可有效提升网络优化质量。利用同方这一探索技术, 其计算机网络有108个集群, 处理器为16个, 因此, 将m设置为16, 而pops设置为10.8。

2.1 初始化子群体

将所有独立的节点随机组合成为新的初始群体, 因其算法为并行法, 因此, 其比原有的算法要简单很多, 原来是将一个网络核心节点上构建形成一个较大的群体后, 将其随机分布于各个节点上。

2.2 连接拓扑

网络连接拓扑 (如图1所示) 包含各个子群体的单、双向环、无迁移状态的完全隔离以及网格等。据研究证明, 单相环连接拓扑可有效保障基因在优异状态下在群体范围内进行扩散, 同时, 又能够将群体进行隔离, 使群体多样性得到保障, 虽说其收敛速度过于缓慢, 但其解的质量非常高。

2.3 迁移计划

可利用粗粒度模型对子群体内的优异基因进行对外分离, 所选基因是随机产生的, 部分算法是利用迁入者对群体里差异较大个体进行替换;最为常用的是将优异个体进行迁移或进行取代。本文可是利用此法, 因此, nnew迁移的数量设为1。

根据研究可知, 如epoch迁移的间隔归于小, 将会使群体间的多样形态遭到破损, 影响解的质量, 针对这一问题, 本文利用仿真实验, 在保证其可靠性有效前提下, 使收敛速度到达最快。

3 仿真实验

为了检测网络拓扑并行遗传算法的性能, 节点以及载体皆选用3种, 数学模板为G= (N, L) , 其中N为60, L为61, 解群体空间区域为3121=5.39*1057, 其中, di为61条弧长。

成本公式如下所示:

第一类在并行情况下可靠性为0.84、预算成本为21.3、接质量值为37426.2;串行情况下可靠性为0.83、预算成本为124、接质量值为48642.7;

第二类在并行情况下可靠性为0.823、预算成本为31.9、接质量值为28268.7;串行情况下可靠性为0.826、预算成本为59.4、接质量值为35963.3;

第三类在并行情况下可靠性为0.836、预算成本为54.8、接质量值为21231.5;串行情况下可靠性为0.816、预算成本为65、接质量值为29971.4;

以上案例说明, 这三个方案, 不管是并行好事串行, 皆有较高的适应度, 虽三个方案所用成本不一, 并行的可靠性以及收敛度等皆优于串联算法, 因此, 并行遗传算法能优化计算机网络可靠性。

4 结束语

综上所述, 普通串联遗传的算法, 只是将计算机网络的节点存储以及通信等存在的问题进行简化, 使运行效率得到提高, 并不能达到最高效率, 但是并行遗传法不仅有效提高了计算机网络的速度与质量, 耗能保障可靠性较高。

摘要：本文分析了计算机网络运行中存在的问题, 阐述了当前形势下, 优化其可靠性的重要程度, 针对现今网络运行存在的问题进行分析研究。笔者通过研究, 结合总结和归纳自身多年工作经验, 提出利用粗粒度并行遗传算法对其可靠性进行优化。希望通过本文的分析研究, 希望能够在计算机网络在预算成本允许的情况下, 实现可靠性的优化工作, 使其运行质量与水平得到保障。

关键词：计算机网络,可靠性,优化,并行,遗传算法,应用

参考文献

[1]周环.计算机网络可靠度优化计算中遗传算法的应用分析[J].中国电子商务, 2013 (05) .

[2]周政.并行遗传算法在软件可靠性优化中的应用[J].华章, 2013 (19) .

网络并行计算 篇4

2011年11月18日，计算机科学与工程学院举办了陈国良院士报告会— 并行计算的研究方法。主要针对陈国良院士关于并行计算的研究方法。

并行计算（Parallel Computing）是指同时使用多种计算资源解决计算问题的过程。为执行并行计算，计算资源应包括一台配有多处理机（并行处理）的计算机、一个与网络相连的计算机专有编号，或者两者结合使用。并行计算的主要目的是快速解决大型且复杂的计算问题。此外还包括：利用非本地资源，节约成本 ― 使用多个“廉价”计算资源取代大型计算机，同时克服单个计算机上存在的存储器限制。

陈国良院士是现任中国科学技术大学软件学院院长，国家高性能计算中心（合肥）主任，深圳大学计算机与软件学院院长，智能感知与图像理解教育部重点实验室（西安电子科技大学）学术委员会主任。中国计算机学会高性能计算专业委员会主任，享受国家政府特殊津贴。

陈国良院士是我国非数值并行算法研究的学科带头人，这次讲座他介绍了并行算法的教学与研究： “算法理论－算法设计－算法实现－算法应用”一套完整的并行算法学科体系，提出了“结构－算法－编程”一体化的并行计算研究方法。

80年代初在国内最早开展了非数值并行算法的研究。在该方面取得了许多国际同期最好的成果，包括分组选择网络、Benes网络选路算法、VLSI平面嵌入算法和网络最大流算法等；改进了某些图灵奖获主的研究工作，包括改进Yao的选择网络时间界、并行化Knuth的顺序串匹配算法和修正Karp的随机串匹配为确定串匹配算法；在国际上首次分析了(0,d]均匀分布调和装箱算法和二维条形装箱NFDH算法的平均性能。受到国内外同行的高度评价。90年代初在国内早期开展了神经网络组合优化和遗传算法的研究，促进了交叉学科的研究与发展；与国际同期研制出具有世界先进水平的并行神经信息处理系统，为我国神经网络的教学、研究与应用提供了良好的工具与环境。90年代中期开展了高性能计算及其应用的研究，率先成立了我国第一个国家高性能计算中心，推进了我国该领域的发展；开发了自主版权的国产曙光并行机“用户开发环境”商用软件，为推广国产并行机应用做出了重要贡献；研制了基于曙光1000的安徽省防灾减灾决策支持系统，在安徽省灾害性天气预报和汛期淮河流域群库优化调度中起了重要作用，产生了显著的社会和经济效益。

在具体实例中，陈国良院士介绍了基于曙光1000 的中尺度数值气象预报系统及其在江淮流域的适用性研究。他在基于曙光1000 建立起来的中尺度数值气象预报系统及其在江淮流域的适用性研究, 包括MM 4 数值预报模式的分析及其并行化方法, 系统组成及基于该系统的预报过程。通过对1998 年、1999 年发生在江淮流域的多次各类暴雨天气过程, 利用曙光1000 上并行化中尺度模式MM 4 进行的数值预报结果与实况进行的对比分析研究, 结果表明: 曙光1000 上并行化的中尺度数值模式MM 4 对发生在江淮流域的江淮气旋、梅雨锋暴雨等中尺度天气系统具有较好的预报能力, 尤其在6 至24 小时的预报时效内对发生在系统内的中尺度降水系统(中尺度雨带)具有很好的预报能力, 反映出该系统具有良好的区域适用性。实例研究也表明, 该中尺度数值模式仍然有许多问题要解决, 文中指出了今后将继续研究和改进的方向。

浅谈CUDA并行计算体系 篇5

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.

Android平台并行计算研究 篇6

关键词：Android,信息,科技

0引言

由于科技的高速发展,人类的信息化程度越来越高,人们对大规模计算的需求也越来越高。但对于中小企业或个人来说,有大型计算需求的情况下,却没有经济能力支撑起巨大的硬件设备。但是个人设备的大规模普及,使得我们有机会利用周围设备的闲置计算资源,实现大规模计算。近年来由于Android平台的占有率不断扩大,及其开放性,使得其在并行计算平台的构成上有巨大的优势。所以本文将通过设计一套基于Android的并行计算框架,期望利用在网络环境下的Android设备的闲置计算资源,完成高性能计算。

1 Android平台并行计算的设计与实现

Android平台的并行计算采用服务端/ 客户端模式实现。服务端与客户端分别以独立应用存在。通信使用了Socket,由于Socket是在双方建立起连接后就可以直接进行数据的传输,在连接时可实现信息的主动推送,而不需要每次由客户端想服务器发送请求。同时Socket具有数据丢失率低,使用简单且易于移植的特点。应用程序继承于android.app.Service,运行于后台。

1.1服务端设计与实现

服务端实例继承android.app.Service, 使之运行于终端后台,不影响其他应用。 主要代码结构如下:

(1) 资源配置管理

服务端实现了用于通信Socket的启动,监听和关闭。管理客户端的连接。

on Start Command() 方法覆盖了父类方法,当应用启动时,系统会自动调用此方法。on Start Command() 方法中调用服务开始。

on Destroy() 方法覆盖了父类方法,当应用退出时自动调用,用于端口释放及资源释放。

(2) 任务分配和管理

start Server() 方法为服务开始,方法中在指定端口初始化了服务端Socket监听。 同时启动监视线程,并且等待客户端的连接。收到连接后,启动单独线程处理连接要求。

server Execute() 方法处理与客户端的连接,方法中启动单独线程处理。并使用参数中的Socket解析通信信号,进行事件处理。方法中不关闭Socket,保证应用运行中,通讯始终保持连续,以便于处理交互信号。server Execute() 被调用时,也用于客户端的注册,分配id。

monitor Thread() 在服务启动时加载, 运行于单独线程,每间隔1秒,检查一次当前连接客户端的状态。客户端状态保存于内部类Client Status,其主要属性有id及状态(等待,执行中)。所有客户端状态保持在一个列表中(client List)。该方法通过不断遍历改列表,进行客户端的管理。如客户端连接异常,则关闭与客户端的连接,释放资源。

(3) 通信

send() 方法用于通信的发送,其方法内部是取到Socket的输出流,并将通信内容写入流。

recv() 方法用于通信的接收,其方法内部是取到Socket的输入流,并读取内容。

通信指令及内容使用二进制编码。

(4) 结果的规约

reduce() 方法处理结果的规约。该方法在监视线程被反复调用,处理客户端返回值并进行规约处理。所有客户端处理完成后即得出全局规约结果。

1.2客户端设计与实现

客户端处理相对于服务端简单,主要代码结构如下:

(1) 资源配置管理

客户端实现了用于通信Socket的启动和关闭。管理与服务端的连接。

on Start Command() 方法覆盖了父类方法,当应用启动时,系统会自动调用此方法。on Start Command() 方法中调用连接服务。

on Destroy() 方法覆盖了父类方法,当应用退出时自动调用,用于端口释放及资源释放。

connect Server() 方法实现了,根据指定服务地址及端口进行连接的过程。

(2) 通信

send() 方法用于通信的发送,其方法内部是取到Socket的输出流,并将通信内容写入流。

recv() 方法用于通信的接收,其方法内部是取到Socket的输入流,并读取内容。 接收指令后调用execute() 方法,处理指令。

通信指令及内容使用二进制编码。

(3) 计算

execute() 方法处理指令,其中主要指令操作有注册register(),及计算calculate()。

register() 方法用于取得本机唯一识别并向服务端注册。

calculate() 方法用于执行的计算操作, 并将结果返回于服务端。

2结论

本文通过设计Android平台的并行计算应用,编码及测试,说明了Android平台的并行计算的可能性。虽然Android设备的硬件性能并不如传统计算机硬件的优异,但设备的使用成本低,闲置计算资源多,足可以满足一些中小企业或个人的大规模运算的需要。

参考文献

[1]郭本俊,王鹏,陈高云,等.基于MPI的云计算模型[J].计算机工程,2009,35(24)

[2]张必银,张天序,吕捷.基于Java"转接器"的并行计算系统[J].计算机应用,2004,24(6)

[3]张晓军,杨灿群,黄春.Java MPI的实现[J]微型机与应用,2000,19(3)

[4]曾剑宇,李炳法.MPI及其Java实现[J].信息技术,2002,12

[5]王如亲,常传文,林明.并行算术编码在Android上的实现[J].计算机与数字工程,2013,9

[6]刘俊莉,王楚斌,林晓锐,等.并行计算实验平台的研究与实现[J].科技信息,2009,(22)

GPU并行计算技术分析与应用 篇7

目前,单核CPU的发展已经遇到了瓶颈,而传统CPU架构也不利于多核心效率的提高。美国Sandia国家实验室的一项模拟测试显示,在传统架构下,由于存储机制和内存带宽的限制,16核以上处理器不仅不能为超级计算机带来性能提升,甚至可能导致效率大幅度下降。而图形处理器(GPU)因为用途不同,其架构从一开始就是专为大量并行运算核心优化设计的,所以同时期GPU效能与核心数量保持了成正比的增长势头。NVIDIA公司最新的GPU GT200,单芯片的浮点运算性能已超过1TFlops,达到每秒万亿次运算级别。而Intel公司最高端的四核心处理器浮点运算性能仅有70GFlops左右。前者的价格却只有后者的一半。因此,利用GPU的大规模并行计算能力加速通用计算成为新热点。

1 GPU加速通用计算技术应用可行性分析

上世纪90年代有人提出了GPGPU概念,即用于通用目的的图形处理器[1]。但是在过去,想要让GPU进行非图形的通用计算,必须通过OpenGL或DirectX之类的图形API与GPU沟通,以映射到着色器的方式编程,这种开发方式太复杂,因此GPU通用计算一直难以实用化。直到NVIDIA的G80 GPU采用统一渲染架构,用流处理器取代传统的着色器,情况才有改观。2006年11月,NVIDIA公司发布了基于G80的并行编程模型和C语言开发环境CUDA(Compute Unified Device Architecture,计算统一设备架构)[2]。因为有了扩展语法的C语言和接口函数库支持,程序员不必过于深入了解GPU的内部细节,就可以快速编写出适用于GPU的通用计算程序。在2008年,NVIDIA凭借CUDA大力推广基于GPU的Tesla系列通用运算产品获得成功。目前,全球前100强超级计算机中就有采用GPU为运算核心,我国也有了以GPU为运算核心的计算集群。

当前,主要的GPGPU技术除前面提到的CUDA,还有AMD的Stream Computing(流计算,以下简称Stream)技术[3],和Apple公司倡导的OpenCL(开放计算语言)[4]。另外,处于开发阶段的还有:Intel的Larrabee架构和微软的DirectX 11 Computer Shader等。

Stream比CUDA还早推出,但推广力度不够,发展相对缓慢,易用性也不是很好,而且一直都局限在专业领域,直到2008年12月才开始支持在消费级图形卡上的应用。Khronos组织于2008年12月8日推出OpenCL1.0版,它是针对异构系统进行并行编程的全新开放式统一标准,未来CUDA和Stream都将支持以OpenCL为接口的开发。

总的来说,虽然CUDA只能支持NVIDIA的GPU,但它是目前最成熟,实用化程度最高的GPGPU架构,而且,它的编程模型也最适合公开GPU的并行计算功能。NVIDIA的官方网站上也免费提供CUDA的编译器、工具包、开发包和大量学习资料的下载[5]。目前,CUDA已发布了2.1正式版本,并已有商业化的产品广泛应用于视频编解码、金融、地质、医学成像、物理仿真等科学计算领域。国内有研究者使用内置16个流处理器的入门级图形卡,与双核2.6GHz奔腾4进行2维FFT运算对比,结果显示,基于CUDA的CUFFT子程序比针对多核心CPU优化过的专业FFTW程序包运算速度至少快1倍以上[6]。如果使用具有240个流处理器、工作频率更高的GTX280图形卡,某些特定的应用性能将会提高2个数量级[2]。以下以CUDA编程为例探讨大规模并行计算的应用。

2 CUDA编程[7]

2.1 CUDA编程模型

NVIDIA将使用GPU通用计算的模型进行了抽象,将图形硬件中运算单元组织层次结构抽象为线程组层次结构,图1中显示了这种抽象的大致对应关系。

GPU中运算单元的组织层次为:

TPC(纹理单元)→SM(流多处理器)→SP(流处理器)

相应地,CUDA中线程组层次为:

Grid(网格)→Block(线程块)→Thread(线程)

CUDA将在GPU设备上执行的C语言函数称为内核(Kernel),一个内核在一个可能由多个大小相同、组织为一维或二维的线程块网格中执行,线程总数等于每个块中的线程数乘以块的数量。每个执行内核代码的线程都会被分配一个线程ID,可通过内部变量blockIdx,blockDim,threadIdx等在内核中定位该线程。

同一线程块内的线程可通过高带宽的共享存储器(Shared Memory)进行协作,但不同块内的线程不能访问同一个区域的共享存储器。

逻辑上,一个线程块中最多可以有512个线程并发执行,但硬件实际执行时,是以32个线程组成一个warp,属同一warp的线程在同一个物理多处理器上执行同一条指令,这称为SIMT(单指令多线程),一个线程块中的所有线程根据执行的指令分属不同的warp,它们的执行是异步并发的,而不是并行的,如图2所示。存储器操作和数学运算可以异步执行,所有线程中的运算在GPU中统一调度,以远多于实际流处理器数量的线程隐藏读取存储器的延迟而并发执行。

2.2 CUDA基本编程方法

CUDA新定义了一组关键字并使用一种全新的<<<…>>>语法扩展了C语言,它说明了内核中线程块的组织,指定了每个线程块的结构和线程数。用global声明的函数中的代码每个线程都可能执行,所以可以无需循环语句,就达到线程并发执行的效果。详细的编程方法,可参见文献[7]。

下面的代码示例将大小为N×N的矩阵A和矩阵B相加,并将结果存储在矩阵C中:

globalvoid matrixAdd(float A[N][N],float B[N][N],float C[N][N])

{ //关键字global声明该内核是由CPU调用,在GPU上执行

int i=blockIdx.x * blockDim.x+threadIdx.x;

int j=blockIdx.y * blockDim.y+threadIdx.y;

if (i < N && j < N)

C[i][j]=A[i][j]+B[i][j];

}

int main()

{

//定义线程块大小:16×16线程

dim3 dimBlock(16,16);

//定义线程块网格的大小

dim3 dimGrid((N+dimBlock.x-1)/dimBlock.x,(N+dimBlock.y-1)/dimBlock.y);

//调用内核,其中网格和线程块的维度由<<<…>>>语法的第一个和第二个参数指定

matrixAdd<<>>(A, B, C);

}

2.3 CUDA编程代码优化策略

为充分发挥GPU的性能,用CUDA编程时应注意:对于可并行操作的算法,应尽可能将运算映射到图形硬件上执行;图形硬件上执行的运算操作应有足够的数学计算强度,即保持大的运算吞吐量;使用尽可能多的线程进行运算,最大化的并发执行;尽可能减少低带宽的存储器操作;根据最优的存储器访问模式,尽可能以最优方式组织存储器访问;计算过程中尽量使数据在多处理器的共享存储器内进行交换;应最小化大开销数学指令的使用;尽可能少用分支跳转指令,无法避免时要特别注意防止warp块内的分支。

除此之外,CUDA在异步存储器操作、流管理等层面上可以进一步加强程序执行的并发性,还可利用纹理过滤快速转换数据类型以提高效能。

3 应用实例

信号处理中,可对采样信号进行瞬时自相关算法计算平均频率。在信噪比较高,采样点数较多的情况下,该算法对单一频率信号可以得到较高的测频精度。但如果信号的采样频率很高,则计算量很大,如果需要实时计算,用软件难以实现,一般都采用硬件实现。

算法的步骤是:

①对N点实信号序列x(n)做DFT得到X(k)。

②将X(k)做变换得

undefined

③对X′(k)做IDFT,得到x(n)的解析信号s(n)。

④求s(n)的瞬时自相关序列r(n,τ)=s(n)s*(n-τ),τ为采样间隔。

⑤将r(n,τ)实部与模的比值求反余弦可得到瞬时频率f(n)。

⑥将序列f(n)加权平均即得到信号的平均频率f。

用CUDA内核对长度为M×N的序列进行自相关运算时,将整个序列分成M组,每个线程块执行单路N点的自相关运算,由M个线程块并发执行。编程应遵循的主要步骤如下(这也是所有CUDA程序必须遵循的主要步骤):

①将M×N点序列的数据一次从主机内存拷贝到图形卡内存。

②按上面所列的6个步骤在内核中计算每N点的平均频率。

③一次将M个平均频率的计算结果从图形卡内存拷贝到主机内存。

按以上流程编写的CUDA自相关算法计算信号平均频率的GPU程序,执行结果与CPU上代码执行的结果相同,性能有50倍的提升。硬件平台:GPU采用Nvidia的Geforce GTX285图形卡,流处理器频率1500MHz;CPU采用AMD的4核心羿龙II 3.0GHz处理器。GPU和CPU编程的开发环境均采用Visual Studio 2005。GPU内核中的FFT采用基2算法;CPU代码中FFT采用Intel MKL的FFT子程序,并使用Intel编译器进行最高性能优化(包括SSE3指令集加速)。各运算5次,取平均值。对比平台和测试数据如表1所示:

从表1中数据可见,如采样频率潍1GHz,则10000个128点信号持续时间为1.28毫秒,用CPU计算延时很大,不能满足实时处理需要,而GPU的计算延时仅为信号持续时间的1倍多,运算性能与FPGA硬件实现性能相当,基本可以满足实时计算的要求,而且还有性能提升的潜力(如改用更高效的混合基FFT算法)。考虑到软件实现的灵活性和硬件的易扩展性,GPU在信号处理领域的应用前景是可观的。

4 结束语

GPU的结构决定了它的数学运算能力巨大,但分支控制性能低下。它要求在每个计算单元中执行完全相同的操作,因此,只适合执行可以大量并行化的运算。另外,目前GPU硬件是专为单精度浮点运算设计的,执行双精度运算性能会降低一个数量级,对运算精度要求高的场合暂时还不宜使用GPU。所以,GPU目前还不能取代CPU。

因此,GPU大规模并行通用计算的理想运用模式是:用CPU控制主要的流程,将问题分解,把需要大量并行处理的计算密集型任务放到GPU上处理。另外,研究传统问题的新算法,使之适于并行计算也是一大发展方向。

参考文献

[1]John D Owens,David Luebke,Naga Govindaraju,et al.A Survey ofGeneral-Purpose Computation on Graphics Hardware[Z].ComputerGraphics Forum,2007,26:80-113.

[2][EB/OL].http://cuda.csdn.net/.

[3]AMD White Paper:AMD Stream Computing:Software Stack[M].Advanced Micro Devices,Inc.2007/12.

[4]The OpenCL Specification[Z].Khronos OpenCL Working Group,2008.

[5][EB/OL].http://www.nvidia.cn/object/cuda-learn-cn.html.

[6]徐山.一种基于图形处理器运用FFT算法生成海洋表面的方法[D].北京大学,2007年硕士论文.

并行计算实验教学环境建设 篇8

关键词：局域网,Matlab,并行计算,实验教学

在日常生活中遇到许多问题在求解的过程中都需要很大的计算量，如背包问题，邮递员问题等一系列NP问题。因此我们可以采用并行计算的方法来解决此类问题，并行计算教学已成为许多本科学校数学专业必修课程，为使并行计算的本科教学能够顺利实施，必须要有相应的实验教学环境[1]。

PC机群[2]是最容易实现的并行计算环境，Matlab是高校数学系学生常用的软件，大多高校数学系的学生都掌握Matlab的基本使用，因此本文考虑用Matlab搭建并行计算实验教学环境，其目的是服务于高校数学系并行计算教学和学习。本文通过实践给出并行计算实验教学环境的搭建过程，先搭建局域网，然后通过局域网搭建多台PC机并行计算环境，此方案适合并行计算实验教学和集中上机实习。

1 基于多台PC机实验室并行环境搭建

1.1 基本配置及原理介绍

在本文搭建的并行环境中，涉及的硬件有四台PC机、路由器、双绞线。操作系统为Windows XP。一台PC机为主机，其余三台客服机。

在Matlab并行机群中，每台参与计算的计算机中都需要启动一个叫Matlab Distributed Computing Engine(MDCE)的服务[3]通过Matlab R2009b构建的PC机群并行环境如图1。

1.2 实验室中Matlab并行计算机环境配置

先通过路由器将四台PC机连成局域网，然后通过Matlab在局域网搭建PC机群并行系统。在Matalb 2009b测试局域网及相关服务的连通性及配置PC机群。最后配置并行环境，Matalb的Parall菜单中Manager Configuration新建Job Manager配置，在Scheduler输入Job Manager名和所从属主机名，所选Job Manager必须是Admin center中已创建的，在jobs菜单下，输入job计划使用Worker的最大最小数目，设置完成之后，全部测试通过如图2，在窗口下放所有项显示为“passed”。

2 并行计算实例

首先通过J o b M a n a g e r传输代码：s e t(j o b,'FileDependencies',{'fun1.m','fun2.m','main.m'})其次设置文件关联，让Worker node访问网络文件和本地文件set(job,'PathDependencies',{'ipsharedir','/mnt/'})接着使用Configurations Manager设置.在matlab的菜单栏上选择Parallel->Manage Configurations...,启动Configurations Manager，设置jobmanager的属性(Properties...)

以简单实例测试PC机群并行计算环境的可行性，例求2+4,5+8和1+7的和，在PC机群并行计算环境2+4,5+8和1+7可分别由三台电脑独立完成，再由服务器将各电脑求得的值汇总后再计算如图3。具体操作如下：

⑴资源查找,创建对象:jm=findResource('scheduler','t ype','jobmanager','name','myjobmanager',…‘LookupURL’,‘node5’);需要修改的是有下划线参数,第一个即前面jobmanager的名字,第二个即本地主机的名字;

⑵创建工作,并将该工作所需的数据、程序发到各个worker处.job1=create Job(jm);%工作名为job1.

set(job1,‘FileDependencies’{‘bb1.m’,‘bb2.m’,‘bb3.m’,…'W_FDJ1.mat','W_FDJ2.mat','W_FDJ3.mat'})注:set()函数就是将该工作所需的数据、程序发到各个worker处,本程序不需要用到;

⑶创建任务c r e at eTa s k(j o b1,@s u m,1,{2,4});createTask(job1,@sum,1,{5,8});createTask(job1,@sum,1,{1,7}).为job1创建了3个任务,@sum代表函数头,1代表返回参数个数,此处为1个,{2,4}代表函数sum的输入参数。

3 结束语

本文针对以Matlab软件为基础的并行环境的构建.给出了构建并行环境的搭建过程，并进行了优劣对比。对于本科院校开设《并行算法设计》课程教学有所帮助，在计算机实验室内搭建并行系统，有利于对并行算法的验证以及对并行算法进行研究。

参考文献

[1]百度百科.并行计算简介[DB/OL].http://baike.baidu.com/view/1666.htm,2012-3.

[2]百度百科.Windows环境下的Matlab并行机群计算配置及应用[DB/OL].http://wenku.baidu.com/view/f042ee4ecf84b9d528ea7a5a.html.

基于GPU并行计算的OMP算法 篇9

关键词：压缩感知,正交匹配追踪算法,图形处理单元,并行计算,加速比

随着信息技术、计算机技术及多媒体技术的快速发展,需要处理的数据量越来越大,而传统的Nyquist采样定理要求对信号的采样率不得低于信号带宽的2倍,这就需要有效的方法来提高对信号的处理能力。压缩感知( Compressed Sensing, CS) 理论是Donobo与Candes等人在2006年提出的一种新的信号处理理论框架[1]。该理论表明,利用较少的信号值就可实现稀疏的或可压缩信号的精确重建,这使得其在信号处理领域中有着非常广阔的应用前景[2]。重建算法是CS理论的核心。在匹配追踪( Matching Pursuit,MP) 算法的基础上提出来的正交匹配追踪( Orthogonal Matching Pursuit,OMP) 算法是经典的重建算法[3],其沿用了MP算法选择原子的准则,不同的是OMP算法通过递归地对已选择的所有原子进行正交化处理,以保证每次迭代的最优性,从而减少了迭代次数[4]。

OMP算法提高了算法的性能,但在分解的每一步都对所选原子做正交化处理,增加了算法的计算复杂度[5]。针对这一问题,本文采用并行计算在图形处理单元( Graphics Processing Unit,GPU) 上加速该算法,首先分析OMP算法的复杂度,找出影响其复杂度较高的部分,在GPU平台上设计其并行方案对算法进行优化,以提高OMP算法的运行速度。

1OMP算法分析

令传感矩阵 Α = ( α1,…,αn) ,其中 αi∈Rm( R表示实数集) 是矩阵 Α 的第i列,称矩阵 Α 和向量 αi分别为字典和原子。令y = Az,其中z在 Ψ 域( 可逆变换矩阵) 中k阶稀疏[6]。 当迭代次数t≤k时,OMP算法计算步骤如下:

第一步,输入传感矩阵A∈Rm × n,测量值y∈Rm,稀疏度为k; 令残差r = y,被选中原子的索引集i = Φ;

第二步,计算得到残差r在传感矩阵的列 αi'上投影最大值的索引;

第三步,由更新索引集;

第四步,由最小二乘法得到

第五步,更新残差

按照上述几步,对OMP算法的复杂度作如下分析:

1) 投影: 投影部分的实质是矩阵向量的乘法运算。残差r在原子 αi'上的投影可以表述为表示两个向量的内积表示向量的l2模。为简化计算,令,则投影部分可以转化为其中. /表示点除。由于矩阵 Α 的大小为m × n而残差r是大小为m的列向量,因此,投影部分的复杂度为 Ο( m × n) 。

2) 选择最匹配的原子: 从未选中的原子中选取与残差r投影绝对值最大原子的索引。字典 Α 每一行有n个原子,且kn,故本部分的复杂度为 Ο( n) 。

3) 更新权值: 令其中u = ( u1,…,ut)T为各原子的权值。由最小二乘法原理可以将更新权值的过程简化为式( 1) 所示。

式中: Q = AtTAt是一个大小为t × t的矩阵; g = AtTy是大小为t的列向量。分析可知Q的复杂度为 Ο( t2m2) 而g的复杂度为 Ο( tm2) 。因此计算Q的逆矩阵的复杂度为 Ο( t3) ,即该部分的复杂度。

4) 更新残差: 由于t≤k≪n2,因此相比于投影部分的复杂度,这一步的复杂度非常小甚至可以忽略。

基于上述分析可知,当k值比较小的时候,OMP算法的计算复杂度主要取决于投影部分,且其复杂度为 Ο( m × n) ; 而当k取值较大的时候,OMP算法的计算复杂度主要取决于矩阵求逆部分,其复杂度为 Ο( k3) 。因此,影响OMP算法计算效率的关键步骤为投影部分矩阵向量相乘和更新权值部分矩阵求逆。

2GPU简述

GPU是由流多处理器 ( Streaming Multiprocessor,SM) 构成的,而流多处理器是由流处理器( Streaming Processor,SP) 构成的。运行在GPU上的程序称为核函数。图1所示为GPU编程模型,GPU线程被组织成Thread-Block-Grid三层结构,每个Grid包含若干Block,每个Block又包含若 干个Thread。GPU运行时采用单指令多线程 ( Single Instruction, Multiple Thread,SIMT) 执行模式,这意味着同一个SM中的SP执行的指令完全相同。GPU的存储器是由1个全局存储器和4个不同类型的片上存储器构成,分别为常量存储器、纹理存储器、共享存储器和寄存器[7]。寄存器是线程特定的,即每个线程只能访问自己的寄存器,而共享存储器是SM特定的, 每个SM的所有线程都能访问这个SM的共享存储器。全局存储器、常量存储器和纹理存储器都可以被所有GPU的线程访问。常量存储器和纹理存储器都是只读的,使用它们可以减少所需要的内存带宽。全局存储器、常量存储器和纹理存储器的使用可以实现不同的优化,例如纹理存储器可以为特定的数据格式提供不同的寻址方式[7,8,9,10]。

本实验是在NVIDIA GTX480显卡上完成的,它由15个有效的SM构成,每个SM由32个SP构成。因此,该显卡总共含有480个处理器内核( Processor Core) 。NVIDIA GTX480的每个SM包含64 kbyte的寄存器和48 kbyte的共享存储器, 在运行时SM将寄存器平均分配给所有线程。此外,每个NVIDIA GTX480还包含1. 5 Gbyte的全局存储器和64 kbyte的纹理存储器。

3OMP算法在GPU上的并行实现

通过分析可知,影响OMP算法复杂度的关键步骤是矩阵求逆和矩阵向量相乘两部分。下面分别介绍基于GPU的矩阵求逆和矩阵向量相乘的并行计算,并给出OMP算法在GPU上并行实现的方案。

3.1矩阵逆更新

由式( 1) 可知求解t × t大小矩阵逆的复杂度为 Ο( t3) 。 然而在OMP算法的每次迭代中,At是在At - 1上添加一列构成的,这表明可以使用矩阵逆更新算法[11]来求解矩阵的逆从而降低其计算复杂度。

在第t - 1次迭代时,At - 1是大小为m × ( t - 1) 的矩阵。 据矩阵逆 更新算法 的思想,作如下定 义: Ht - 1= (AtT- 1At- 1)- 1。在第t次迭代中,OMP算法将列向量ait添加到At - 1使得At= ( At - 1ait) 。由Ht - 1= ( AtT- 1At - 1)- 1可以得到

式中: d和P的表述如式( 3) 和式( 4) 所示

为了进一步简化计算,作如下定义

将d和P简化为式( 7) 和式( 8)

由此,Ht的表达式可以简化为式( 9)

对简化后Ht的复杂度作如下分析: u1是一个矩阵向量相乘的过程,计算u1的复杂度为 Ο( m( t - 1) ) ; u2也是一个矩阵向量相乘的过程,其复杂度为 Ο( ( t - 1)2) 。计算d的复杂度为 Ο( t) 。u2u2T的复杂度为 Ο( ( t - 1)2) ,u1Tu2的复杂度为的复杂度为 Ο( m) 。由此可知,在采用矩阵逆更新算法后,矩阵求逆部分的复杂度得到了大幅度地降低。

在GPU上计算Ht时,根据式( 6) 、( 8) 和( 9) 可知只需定义4个核函数: 第一个核函数用于计算u1; 第二个核函数计算u2; 第三个核函数计算u2u2T并得到d; 最后一个核函数计算u1Tu2并最终得到Ht。GPU线程通过对这4个核函数的调度,实现矩阵求逆在GPU上的并行运算。

3.2矩阵向量相乘块算法

在计算r在AT中原子上的投影时,AT中的每个原子仅使用一次,而AT中的每行都会与r相乘,可知r会被多次读取,即在矩阵向量相乘中,r是重复使用的数据。因此,应将r加载到GPU共享存储器中。然而,NVIDIA GTX480中只有12 kbyte共享存储器可以加载,无法存放较大的向量。因此, 在矩阵向量相乘的过程中采用分块算法[12,13]来实现。根据文献[12]可知,该算法有以下优点: 1) 块计算所需要的数据量很小,可以加载到共享存储器中; 2) 若干个块可以由多处理器并行计算; 3) 块内数据的计算,可以有效地在一个多处理器内并行执行。块算法不但解决了NVIDIA GTX480共享存储器不足的问题,还可以有效地提高矩阵向量相乘的速度。

在GPU中,矩阵向量相乘块算法实现如下: 令 δ = ATr,每个块完成 δ 中16 × 16个原子的计算,每个SM包含16 × 16个线程。因此在块算法中将矩阵AT划分成大小为16 × 256的块,而将向量r划分成长度为256的段。在共享存储器中定义两个大小为256的变量用于存放r和临时计算结果。迭代开始时,每个线程从r中加载一个原子,再从AT中加载16个原子到寄存器中进行计算。每个线程进行m/256次迭代。 每次迭代中,每个线程对r中的小数据段和AT中的小数据块进行乘积运算并对结果进行累积。迭代结束后,将累积的结果保存到共享存储器中。r中一个小数据段计算完成后,将下一个小数据段加载到共享存储器中,为与AT中下一个小数据块的计算做准备。

3.3OMP算法的并行实现

要在GPU上并行实现OMP算法,需要在GPU上为输入变量分配内存。输入变量为AT和y,输出变量为z。由前面的分析可知,OMP算法中会用到原子的l2- 范数,因此定义 ρ ( 长度为n的向量) 用于存放算法中经常使用原子的l2- 范数,定义向量i用于存储已选定原子的索引。如图2所示为OMP算法在GPU上并行实现的流程图。

在OMP算法运行前,首先把矩阵AT和向量y中的数据从CPU内存传输至GPU的全局存储器; OMP算法执行结束后,将输出的z从GPU全局存储器中拷贝到CPU内存中。 OMP算法的每一次迭代中都会用到 ρ,为了避免频繁的重新计算,提前计算得到 ρ 并把它保存到GPU的全局存储器中。

OMP并行过程包含k次循环,每次循环求得一个原子的索引。在GPU上并行实现OMP算法方案如下: 首先定义一个核函数|ATr| ·* ( z = 0) · / ρ,其中“·* ”表示两个向量的点乘。在这个核函数中,z用来区分原子是否已经被选中: 如果z中相应原子不为零,则表示该原子已被选中,将在这个原子上的投影值设置为零,以避免该原子再次被选中。这种方法的优点是不需要额外的内存来区分原子是否被选中。其次,通过计算最大投影值来寻找最匹配原子的过程,使用CUBLAS库函数来实现。第三,采用矩阵逆更新算法和矩阵向量相乘块算法来实现矩阵求逆和矩阵向量相乘在GPU上的并行计算。第四,定义两个核函数,一个用于计算( AtTAt)- 1和AtTy的积,另一个用于更新残差r。

4实验结果及分析

本实验是在Intel( R) core( TM) i7处理器12 Gbyte内存, NVIDIA GTX480显卡上完成的。实验的基本设置如下: 传感矩阵 Φ 服从标准高斯分布; 变换矩阵 Ψ 不影响算法的运行速度,因此令A = Φ。实验测试中,每组参数设置下的测量值都能够正确地恢复,选取以下6组实验数据进行比较分析,其中n和m分别表示传感矩阵 Α 的行和列,而k表示矩阵 Α 的稀疏度。

4. 1矩阵向量相乘

从表1的实验结果可以看出: 基于GPU的并行矩阵向量相乘块算法相比其在CPU的串行算法运算速度提高了50多倍; 且随着数据量的增加,加速效果更好,因而较好地解决了矩阵向量相乘计算耗时长的难题。

4. 2矩阵求逆

从表2的实验结果可看出: 基于GPU并行矩阵求逆算法相比其在CPU上的串行算法运行速度提高了近2倍; 其加速比只与稀疏度k相关,而不依赖于n和m的大小。即k相同时,并行求逆算法相比其串行算法加速比相同。

4. 3仿真结果

从表3的实验结果可以看出: 基于GPU的并行OMP算法相比其CPU上的串行算法运行速度提高了30 ~ 44倍: 当n = 16 384时,加速比可以达到44倍; n = 8 192时,加速比也可达到30多倍。实验结果充分地证明了基于GPU并行计算OMP算法的有效性和方案的可行性。图3是对表3中6组不同参数设置下并行OMP算法的加速效果图。

5小结