并行加速

2024-11-24

并行加速（共4篇）

并行加速篇1

摘要：共轭梯度法是为求解线性方程组而独立提出的一种常用的数值计算方法, 被广泛地应用于天气动力、物理海洋等数值计算中, 其复杂的矩阵计算产生巨大工作量, 成为业务化应用过程中的计算瓶颈。利用OpenMP共享并行技术, 将大量计算并行化, 实现基于OpenMP的共轭梯度法并行加速, 为共轭梯度法的广泛应用提供了新的计算解决方案。

关键词：共轭梯度法,OpenMP解决方案,并行加速

1 前言

共轭梯度法 (Conjugate Gradient) 是解决最优化问题的常见方法。其计算难易程度和实现规模介于最速下降法与牛顿法之间。共轭梯度法仅利用一阶求导, 克服了收敛慢 (比如最速下降法) 的缺点, 又避免了需要存储和计算多极值矩阵并求逆 (比如牛顿法) 的缺点, 共轭梯度法即是解决大型线性方程组最有用的方法, 也是解大型非线性最优化最有效的算法之一。在各种优化算法中, 共轭梯度法是非常重要的一种。其优点是所需存储量小, 具有步收敛性, 稳定性高, 而且不需要任何外来参数。

在天气动力、物理海洋等数值计算中方法的使用线性和非线性共轭梯度法, 解决各种问题, 比如陈红霞等[1]利用非线性共轭梯度法在东海黑潮流计算中的应用实现海洋数据的比对检验, 张少波等[2]利用预处理共轭梯度法在实现VVP三维风场反演中的应用等。在此过程中均发现随着计算规模的不断发展和历史资料的大量积累, 共轭梯度法的计算量大幅度提高, 甚至成为利用该方法实现业务化应用的瓶颈。为此, 选取常用的并行优化方法Open MP技术, 对共轭梯度法进行并行加速优化, 为共轭梯度法的广泛应用提供了新的计算解决方案。

2 问题提出

2.1 共轭梯度法

共轭梯度法于1952 年为求解线性方程组而提出的。后来, 人们把这种方法用于求解无约束最优化问题, 使之成为一种重要的最优化方法。共轭梯度法的基本思想是把共轭性与最速下降方法相结合, 利用已知点处的梯度构造一组共轭方向, 并沿这组方向进行搜素, 求出目标函数的极小点。根据共轭方向基本性质, 这种方法具有二次终止性。

2.2 算法原理

共轭梯度法算法如下:

假设选取x0作为Ax=b的解的初始猜测值, 与之对应的残差为r0=b-Ax0, 则p0=r0, 设循环变量k=0, 即开始如下循环:

如果残差已经足够小, 则推出循环, 否则继续。

3 设计与实现

3.1 Open MP简介

用于并行程序开发的编程模型主要分为两类: 消息传递模型和共享主存模型。共享主存模型使程序员可以不必进行数据划分和分布, Open MP (Open Multi Processing) API规范, 是用户对共享主存编程模型最新要求的全面反映, 可解决旧规范的种种局限性。 Open MP使用fork-join并行机制, 程序开始串行执行, 此时只有一个主线程, 然后在遇到用户定义的并行区域时创建出一组线程。在并行区域之内, 多个线程可以执行相同的代码块, 或使用工作共享结构体并行执行不同的任务[3]。

3.2 实验数据

实验数据文件input.txt中存储了矩阵A和b。其中矩阵A是一个83334 乘83334 的矩阵, 非0 元素共有6010480 个, 数据稀疏度为0.085%。数据存储为文本文件, 第一个元素是行 (列) 数N, 第二个元素是非0 元素的个数length。接下来是length个三元组数据 (行优先, 即每个数据的行号不会大于之前数据的行号) , 三元组里分别是数据A [i] [j] 的行号i、列号j、值val, 存储格式为int, int, double。再接下来是N个随机生成的double值, 分别是b的每一维。

3.3 并行实现

采用Open MP实现并行化。可并行化的地方有:

(1) 向量加法。形如xk+1=xk+∝kPk的操作由于每一维间没有影响, 因此可以并行化。如图1 所示

(2) 矩阵向量乘法。迭代中需要计算APk, 这里使用行划分来进行并行计算, 则每个CPU处理器只需要得到A的第行与Pk则可得到最终结果APk的第i维。又因为APk在计算中出现了两次, 因此采用一个矩阵存储下来, 节约计算时间。如图2 所示。

(3) 向量的点积。形如的向量点积运行可以利用并行来实现, 由于最终是个累加操作, 可以使用Open MP中的re duction函数实现。如图3 所示。

3.4 构建稀疏矩阵

稀疏矩阵的Open MP核心实现代码如下

3.5 结果与分析

(1) 并行程序的正确性

利用多批次小规模的数据测试后, 并行程序运结果保持二进制一致, 并行化并没有影响结果的正确。

(2) 并行程序的加速性和可扩展性

由于数据规模比较大, 迭代次数比较多, 因此对100 次迭代循环总时间进行计时, 再得到每次循环的平均运行时间。计算性能如下:

串行程序的每次循环平均运行时间为12.5 秒。并行程序在1、 2、 4、 8 个CPU核的每次循环平均运行时间如表1 所示。

4 结语

大规模计算的性能优化是天气动力、物理海洋等数值计算中的主要问题, 随着业务化需求的增大, 计算规模越来越大, 性能优化成为瓶颈问题。利用Open MP技术对共轭梯度法中最多的向量加、向量乘和向量点积进行分析, 并进行了测试实验, 达到了预期效果, 确认Open MP并行优化是共轭梯度法广泛应用的一种较好的计算解决方案。

参考文献

[1]陈红霞, 袁业立, 刘娜, 等.非线性共轭梯度法在东海黑潮流计算中的应用[J].海洋学报, 2003, 25 (6) :31-38.

[2]张少波, 胡明宝, 张鹏, 等.预处理共轭梯度法在VVP三维风场反演中的应用[J].气象学报, 2004, 24 (8) :303-308.

[3]殷顺昌.Open MP并行程序性能分析[D].国防科技大学, 2006.

并行加速篇2

1 C++AMP介绍

GPU计算由来已久, 已经成熟的接口包括NVIDIA的CUDA C和AMD的OPENCL接口, 随着微软公司Visual Studio 2012的发布, 在Build大会上微软向大家呈现了一种新的GPU并行计算模式C++AMP, 其最低运行环境是:Win7系统+Visual Studio 2012+Direct X11, 所以它比另外两种并行端口适用范围更广, 可以实现真正意义上的跨平台运行。C++AMP采用面向对象的C++语言开发, 支持CPU, GPU等跨平台编译运行, 具有逻辑结构简单、数据隐式拷贝、自动负载均衡等特点, 可以快速、稳定地实现并行计算。

一个C++AMP计算过程中最重要的包括:

(1) 数据, 其基本数据类型有array<T, N>, array_view<T, N>, index<N>, extent<N>, tiled_extent<D0, D1, D2>, title_index (D0, D1, D2>, accelerator, accelerator_view, texture<T, N>等;

(2) 迭代函数parallel_for_each函数, 是C++AMP并行计算的核心部分, 负责线程开辟、核函数计算等工作, 基本的计算过程由核函数指定, 通常核函数为Lambda表达式, 也可以是由限定符restrict (amp) 限定的GPU函数;

(3) 线程索引index类, 线程开辟大小extent类, 他们两者是一一对应的。如果extent是二维的, 则index也是二维的, 由index类对象来实现对线程的惟一标示;

(4) 数学函数, 数学函数库有双精度数学函数与快速数学函数两种, 根据需要选择。

C++AMP的执行模式是由CPU线程控制、由parallel_for_each函数作为详细设置、由核函数完成核心计算任务、数据隐式拷贝的执行模型。程序开始运行时, 只有CPU主线程活动, 当执行到并行区域时, 主线程根据parallel_for_each函数的设置, 启动GPU线程组来完成相应的计算任务, 最后拷贝数据回CPU主线程, 这时GPU线程挂起或者退出, 控制流又回到CPU主线程中。

2 蚁群算法介绍

为了更加清楚详细地描述蚁群算法, 本文借助经典的TSP问题来描述 (TSP问题:已知n个城市以及城市两两之间的距离, 求一条遍历所有城市的最短路径, 除初始城市之外每个城市访问且仅访问一次) 。

蚁群算法可以定义如下:设有n个城市, m个蚂蚁, 任意城市i与城市j之间的距离为d (i, j) , 启发函数定义为η (i, j) =1 d (i, j) , 任意城市i与城市j之间的信息素浓度为τ (i, j) , 并且初始时刻信息素浓度相同, 蚂蚁k经过城市i转到城市j的概率计算公式如下所示:

式中:J (k) 是蚂蚁k下一步允许选择的城市的集合;α, β为权重系数。当所有蚂蚁都完成一次循环后, 对信息素矩阵进行更新操作, 这样, 新时刻路径 (i, j) 上的信息素浓度采用调整式 (2) 进行调节:

式中:ρ (0<ρ<1) 表示信息素保留程度, 其值越大表示信息素挥发速率越慢;Δτk (i, j) 表示在本次循环中第k只蚂蚁在路径 (i, j) 上的信息素贡献。每只蚂蚁的信息素贡献可以用式 (3) 进行计算:

式中:Q是信息素强度, 它影响算法的收敛速度;Lk表示第k只蚂蚁在本次循环中所有的路径总和[4]。

3 并行蚁群算法

根据上述介绍, 可以看出每只蚂蚁寻找自己路径依赖于上次循环产生的信息素矩阵以及各城市之间的静态路径长度, 两两蚂蚁之间没有信息素交流, 经过分析, 这是一种符合SIMD模型的过程, 故可以将每只蚂蚁寻找最优路径的过程并行进行, 从而加速算法计算。并行蚁群算法可以用如下算法进行描述:

Step1:初始化所有参数、变量, 如权重系数α, β;蚂蚁个数m;最大迭代步数NC;信息素矩阵初始值τ (i, j) =1。

Step2:按照蚂蚁个数分配线程, 每个线程代表一只蚂蚁。每只蚂蚁独立构造一个解 (解即一条遍历所有城市的路径) , 详细描述为:蚂蚁k随机选取一个城市i作为自己的初始点, 再根据转移概率公式计算转移概率pkij;根据概率最大者选择下一个城市j, 从而蚂蚁走过路径为 (i, j) 。若当前路径长度大于上一循环求得最短路径长度, 则结束本次循环;否则继续循环, 直到蚂蚁k寻找到一个解。

Step3:规约Step2中所有蚂蚁产生的解, 求解出所有解中的最优解和最优值进行保存操作。

Step4:根据当前最优解和最优值信息, 进行信息素矩阵更新操作。

Step5:判断是否满足结束条件, 若满足, 则输出最优解和最优值;否则, 循环执行次数+1, 转Step2。结束条件为循环次数大于NC或者当前解已经稳定 (通常两步解出的最优解与最优值相同即可认为当前解已经稳定) 。

串行蚁群算法的时间复杂度为O (NC⋅m⋅n2) , 计算量主要集中在蚂蚁各自构造一个解的过程。蚁群算法在一代迭代中包括蚂蚁独立求解、相互交流得到较优解和改变信息素的过程, 且信息素的改变直接影响下一代概率计算的结果, 从而产生不同的解, 并向较优解进化。由于把算法并行化, 采用每只蚂蚁并行寻找路径的模式进行, 则并行蚁群算法的时间复杂度减小为O (NC⋅n2) , 使算法有明显的加速。

4 数值实验

4.1 实验环境

实验环境采用NVIDIA Ge Force GT 440环境, 具体参数配置如表1所示。

4.2 数值结果

数值实验采用的数据为随机生成的二维坐标, 取值范围在[0, 1 000], 分城市数目n、蚂蚁数目m、迭代次数NC等三个参数进行实验分析, 实验结果如表2所示。

由表2前三行可知, 串行时间与并行时间随着迭代次数的增加呈现线性增长趋势, 这也符合第3节的理论推导, 此时串行时间与并行时间相当, 加速比在[1-0.01, 1+0.01]范围之内, 可以认为此时没有加速效果。由此三行知道, 加速比和运行时间都与迭代次数无关。下面选取小的迭代次数来进行数值实验, 分析城市数目与蚂蚁数目对串行时间、并行时间、加速比的影响。

由表2整体可以看出, 当城市数目及蚂蚁数目较大时, 对数据普遍有加速效果。由表2第4~6行分析可知, 固定城市数目, 随着蚂蚁数目增大, 串行时间呈现线性增长, 而并行时间的增长率小于线性, 加速比越来越大。这是由于并行线程数目是以蚂蚁数目为参数的, 蚂蚁数目越大, 并行线程数目越多, 从而使得并行时间增长率比线性还小。但是此时并行时间并没有遵循第3节分析的函数O (NC∙n2) , 这是由于虽然并行线程开辟了m个, 但是最终的物理执行过程同时运行的线程个数为96个 (SP个数) , 又涉及到CPU-GPU异构通信时间, 从而使得整体并行时间没有按照理论分析的结果。并行线程数目m越大, 负载相对越均衡, 物理资源占用越充分, 从而加速效果越来越明显, 直到达到相应的物理瓶颈。这也可以由表2的7, 8行得出。

由表2中的第5, 7行和第6, 8行可以对比出, 蚂蚁数目m一定时, 城市数目n对于串行、并行算法时间的影响。对比5, 7两行可以看出, 蚂蚁数目大体一样, 城市数目改变量比较大, 其加速比相差不大;对比6, 8两行可以看出, 蚂蚁数目一样时, 城市数目的改变对于整个算法的加速比影响并不是很大。这个也可以从并行程序中串行执行部分、数据交换所用时间以及算法本身所用时间方面进行分析, 这个加速效果是合理的。

5 结论

并行加速篇3

关键词：互联网,广域网,加速系统

一、概述

网络技术发展至今, 其功德无量造福着全人类。在各种迅速发展的电子商务、网游等业务中, 提出了对处理数据速度及网络的传输速度更高的要求。在高带宽延时广域网的发展中, 传统的TCP将难以适应。在高带宽延时的网络条件下, TCP流将有抖动的发生, 在不停的抖动下让路由器中的队列长度产生未稳定性状态, 且TCP的性能方面会伴随着链路带宽或延时的增加而降低。一些学者们对TCP的拥塞控制机制加以改进, 经由加以改变TCP拥塞窗口的调整参数, 使其在互联网中发挥更好的性能, 而并行TCP主要是经由TCP流之间的相互协作及让TCP连接的数目有所增加, 从而有助于网络传输的性能方面的提高。

并行TCP加速系统的设计

二、在当前的广域网中, 主要存在着三个方面的问题, 它们分别是带宽、延迟与可靠性, 对并行TCP广域网加速系统的设计采取双网关模式, 该加速系统主要由系统配置、会话控制的接入、数据应用管理与网关间传输控制该四个模块构成。

1系统配置。该模块方便用户针对各种不同服务同其侧重的优化指标配置系统参数, 同时能达成加速效应, 例如设置并发流的数目和调度方式, 以及多种策略自身的参数等等。

2会话控制的接入。此模块可让管理会话、同步控制会话与会话数据流量的控制得以实现。按用户的需求而言, 能对局域网中的各种服务应用进行访问, 在系统中分组管理各种会话, 可按服务应用的端口同IP地址来进行。在管理会话当中经由所接入会话设置的ID码, 促使会话的迅速控制与定位得以实现。因进行设计时采取双网关加速模式, 数据传输是由网关两端会话接入同网间并行TCP隧道一同协作得以完成, 在启动系统的时候服务器端会话已成功创建, 在准许会话接入负载时, 服务器端网关会分配一个空闲会话连接于接入客户端网关新会话里, 共同与网间隧道组成数据链路1条, 以此达成用户与服务器间进行传输数据。

3数据应用管理。此模块功能是对数据进行转化转发, 当中含有分块封装的会话数据、分配转发控制及分发控制、网间数据的重组解析。

该模块经由对会话类型加以判断, 分别完成对会话数据的接入与网间隧道会话数据的操作处理。系统将按会话接入的会话号同组标识进行分块封装其数据, 分配给相对应的网间隧道会话需依据分配数据的策略, 然后对网间隧道会话数据加以解析, 然后进行获取控制信息, 把当中的有效数据分发至对应的接入会话。

4网关间的传输控制。在此模块中, 可实现隧道TCP会话的接入控制与输送隧道数据, 也就是网关间并行TCP隧道的管理, 在隧道TCP会话接入的控制过程中, 它是按配置文件的服务器端网关的IP及隧道侦听端口对隧道TCP会话分组进行有效管理, 由此产生并行TCP隧道。该系统的准确定位是经由隧道TCP会话标识同隧道标识一起加以实现, socket可以完成其隧道数据的传输。

三、广域网并行TCP加速系统的实现

据此种设计, 使系统加速的客户端网关模式与服务器端网关模式得到了实现。

1数据转化转发的控制。若要使转化转发中的网关间数据与会话数据得以实现, 数据应用管理对网关间数据传输的包封装格式有所定义;数据包的用处是对会话数据加以携带, 能对控制信息的确认包与同步包加以携带, 其在会话流量控制和会话同步控制过程中分别得到很好的应用。

在数据转发控制中, 若果实现对会话数据进行重组, 可在会话的发送缓存过程中所获得。而会话的发送缓存为BC (Block Container) 对象, BC对象是以指向数据包中有效数据的指针同数据包序列号构成映射, 对数据包加以解析完后, 能够于会话发送的缓存BC对象里增添对应表项, 这样可使大量避免数据的转储存。

在会话中发送数据的时候, 能够对缓存BC中的表项进行有效读取, 若果返回的为非空指针的话, 可在对应内存地址中进行对数据块读取, 若果为空指针的话, 数据包则有延迟现象产生, 产生阻塞的必是发送线程, 仍需等待该数据包来对此发送线程进行有效激活。

2会话管理。在加速网关系统会话类型的实现中, 分别有网间隧道中的TCP会话与系统可外接入会话。基于socket编程中建立连接的方式有侦听接收与主动请求两种, 系统对服务器端与会话的客户端分别能够实现异同的管理模式。

在服务器端管理的层次中, 它同客户端管理存在异曲同工之处, 它们的区别主要在于服务端的管理目标为TS (Tcp Server) , 是以其监听的套接字同端口号为主键创建Map对象。

3会话同步的控制。在实现系统的过程当中, 可以使着布尔型数组得到维护的是每个会话分组, 数组位序也可当作待分配的会话号资源, 在两端网关上, 其数组布尔型元素的值也有着不同寻常的意义。

在服务器端中的网关, 它所能标记的是其位序对应会话的状态为忙碌或空闲;在客户端的网关中, 它标识其位序对应会话的创建或断开。该系统功能可达成会话号充分使会话状态及会话的绑定, 由此通过对网关两端同样的会话号资源进行灵活设置, 最终达成会话的同步性。

4会话流量的控制。在TCP滑动窗口的机制里, 为实现流量的控制, 该系统中却选用相似TCP滑动窗口流量控制机制, 需经由返回信息确认进行统计数据量。

依据用户的配置来看, 该系统为每个会话分组设定一个接收窗口值RCV_W与发送窗口值SND_W, 并且要确保RCV_W不大于SND_W。而各个接入会话对两个变量进行了声明, 在整个流量控制的过程里, 完全可由两端处会话的发送线程和接收线程一起协同来完成。

结语

在当今互联网上, 广域网广泛存在着一些瓶颈, 而能解决广域网遇到的瓶颈却是并行TCP加速网关系统。该系统可实现会话接入的重定向、会话数据的截获和数据网关间的并行传输等。为了在实际网络中可得到应用, 还需进行完善网关的控制, 客户端网关同服务器端网关之间需要使状态信息的交互得以实现, 以便应付网络异常情况的产生, 从而能使系统的健壮性得到有效提高。

参考文献

并行加速篇4

关键词：KD-Tree,GPU,光线跟踪

本文提出的算法在GPU内核函数中模拟了栈的行为, 有效的对于KD-Tree进行深度遍历, 从而提升了光线遍历求交的性能。本文的并行算法相对于传统的单核处理器的串行算法加速高达50倍。

1 光线跟踪简介

光线跟踪时一种全局光照渲染技术[1], 可以生成照片级质量的图片, 可以很好的支持反射、折射和阴影等效果。

随着可编程GPU技术的发布, 更多的学者用GPU并行计算光线跟踪, 从而得到了一定程度的优化, 使得光线跟踪技术速度上升了很多。但是实时的光线跟踪渲染技术仍然是很大的挑战。

2 本文的光线跟踪算法

本文利用CUDA架构, 充分发掘GPU的硬件性能, 改进了传统光线跟踪算法的性能。

2.1 光线跟踪算法概述

首先, 算法根据光栅化的原理[2], 生成覆盖每个像素的三角形索引。然后并行生成一级光线, 一级光线可以直接与其相对应的三角形求交, 而不用进行KD-Tree的遍历。因为三角形与光线是已知相交的, 所以其求交算法可以简化为光线与平面相交, 从而进一步改进了光线跟踪算法的性能。

在一级光线求交结束后, 算法对于交点进行着色过程。本文的着色算法应用的是经典的Phong局部光照模型。与局部光照模型不同的是, 在着色过程中, 会通过一条阴影光线计算光照中的阴影, 从而实现像素级别的阴影效果。在着色过程中, 每个像素的着色是有单独的线程完成的, 因为像素着色之间是互不干扰的, 这样可以最大化的利用GPU的硬件能力优化算法中。

在像素着色过程中, 有的三角形的材质是有折射或反射属性的, 根据三角形的材质属性, 算法会生成二级光线。在二级光线生成后, 重复上述循环。不过二级光线的求交过程是需要通过遍历KD-Tree进行的。二级光线的着色结果会累加到相应的像素中, 从而实现了折射和反射的效果。

2.2 基于栈行为的KD-Tree遍历算法

本文提出的算法在GPU内核中实现了KD-Tree的深度遍历过程。必须在GPU内核函数中利用有限的硬件资源高效的实现栈的行为。

本文算法中的栈是利用32位的无符号整数位操作实现的。因为这种局部内存是存储在硬件中的寄存器中的, 访问速度相对很快, 所以非常适合进行栈的模拟。32位无符号整数的资源有限, 本文的栈是基于位操作的, 从而充分利用了硬件的资源。

其工作方式大致如下:

1) 如果光线与当前节点的某一个子节点相交, 以同样方式继续遍历这个子节点。

2) 如果光线没有和叶子节点中的三角形相交, 需要进行回朔过程。在回朔中, 首先检查当前对应的位是否为1。如果该位是1, 则代表当前节点的兄弟节点已经被访问过了, 所以直接退到其父亲节点。如果该位是0, 则检查光线是否与其兄弟节点相交, 相交的话就把相应的位更新为1。否则把相应的位更新为0, 然后退到其父亲节点。

根据上述算法, 可以利用32位的无符号整数有效的模拟二叉树遍历中的栈的行为, 从而在GPU内核函数端进行KD-Tree的深度遍历。

2.3 去除噪音的后处理过程

由于光线跟踪算法的一些局限性, 其生成的图片仍然会存在一些噪音。主要原因有以下两点:

1) 很多三角形与光线几乎平行, 所以导致出现了病态方程。由于计算机的浮点计算精度有限, 致使其求交结果很不精确。

2) 为了避免反射折射光线与当前三角形相交, 本文的算发会把生成的光线沿着光线方向移动一个位移。从而避免一些错误的阴影、折射和反射的计算。但是在一些精度很高的模型中, 这个位移会直接穿过一些原本与其相交的三角形, 所以导致求出错误结果。

上述问题是有与光线跟踪本身的特性造成的, 很难从根本上避免。可以采用多采样的方式进行弥补, 不过这回使算法的性能下降非常快。

本文采用一种后出里的简单快速的方法去除噪音。对于每个像素, 算法检查周围其与周围4个像素的差值。如果这些差值的绝对值之和大于一定阈值, 那么算法会认为当前像素是因为上述原因造成的噪音, 从而进行一定的平滑处理。

这种噪音处理方法具有一定的局限性, 可能会模糊一些物体的边缘。但是人的视觉对于噪音比边缘敏感很多, 所以大部分情况下, 其结果还是比未处理的更优。

3 本文的并行光线跟踪算法的性能

本文所进行的实验在Nvidia GTX 285的环境下进行测试, 得到的实验结果与性能如下:

上述算法的性能比较中, 图片的分辨率为1024×768。数据显示, 本文的算法相对于传统的CPU实现的光线跟踪算法有了大幅度的性能提升, 基本达到了每秒2帧左右的水平。对于非常复杂的场景, 本文的算法依然可以达到接近每秒1帧左右的性能。

4 结论