GPU加速的演化算法求解多目标流水车间调度问题

智能制造和环境可持续性研究中,多目标调度问题对于协调生产效率、成本管理与环境保护之间的平衡具有至关重要的意义,但现有基于CPU的调度解决方案在处理大规模生产任务时仍面临效率和时效性的限制,而GPU的并行计算能力可为优化大规模流水车间调度问题提供新的解决途径。针对多目标零等待流水车间调度问题(NWFSP),以同时最小化最大完成时间和总能耗(TEC)为优化目标,构建了混合整数线性规划模型(MILP)表征该调度问题,并提出一种基于GPU加速的张量化演化算法(Tensor-GPU-NSGA-Ⅱ)求解该问题。Tensor-GPU-NSGA-Ⅱ的主要创新在于对NWFSP关于最小化最大完成时间和TEC的计算过程的张量化处理,并提出了一种基于GPU的并行种群更新方法。实验结果表明,在500工件和20机器的问题规模下,Tensor-GPU-NSGA-Ⅱ在计算效率上相较于传统NSGA-Ⅱ算法取得了9761.75的加速比;且随着种群规模的增加,它的加速性能有显著提升。

基于GPU加速的溃坝洪水演进模拟研究

溃坝洪水演进与淹没范围快速模拟,对指导抢险救灾至关重要。为此,引入GPU加速技术,构建了一套高效高分辨率溃坝数值模型,与经典三驼峰溃坝试验对比发现,模拟结果与试验结果非常吻合,并利用该模型模拟了典型溃坝洪水演进及溃口流场、溃后水位变化情况。结果表明,模型能较好地模拟溃坝洪水演进,较好捕捉溃口发展过程及泥沙输移。t=200 s时溃决流量出现小峰值4 m3/s,t=450 s时,溃决流量出现最大峰值13.8 m3/s;随着下泄流量增大,溃口加速侵蚀和冲刷并逐渐连通,溃口由0.21 m扩大至0.40 m。GPU加速比约为CPU的10.33~13.75倍,且网格数越多,加速效果越明显。

面向嵌入式环境的暗光图像GPU加速增强算法

针对已有算法很难满足嵌入式场景下暗光图像增强的高性能和高效性处理需求,面向嵌入式国产GPU加速平台提出一种用于暗光图像增强的高阶分式模型,证明了提出的高阶分式模型在特定情况下等价于Retinex理论模型。为了减少GPU加速过程中每个线程的计算开销,提出一种基于像素抽样的快速boxfilter算法,实现GPU的进一步加速,同时为了避免传统伽马变换存在过度曝光和亮度提升不够明显的问题,提出了一种自适应伽马变换的算法。通过实验结果的分析,证明提出的算法在嵌入式计算场景下的高效性和有效性,实现了1280×720像素分辨率图像约148帧/s的处理速度。

基于GPU加速随机场的洞室变形破坏特征研究

洞室围岩参数一般具有很强的空间变异性,本文研究了岩体参数随机空间分布对围岩稳定性的影响。提出了基于协方差矩阵分解和GPU加速的空间随机场生成方法,建立将随机场与高级应变软化模型参数的映射,对比不同条件下随机场的变化以及对后续模拟开挖的影响。结果表明:指数型相关函数生成的随机场较为稳定分散,其最大位移值变化范围较小;平方指数型相关函数生成的随机场更为紧凑,最大位移值波动范围较大,偶然出现较危险的位移;对比X,Y相关长度可以发现,最大位移点的分布是相似的,开挖过程中洞室两侧中部、底部和拱顶是危险区域,损伤位置主要集中在洞室侧墙、拱顶交接处和侧墙中部。

基于GPU加速随机森林算法的大豆基因型填充研究

基因型填充(Genotype Imputation, GI)是一种利用现有的基因型信息来推断未测定或不完整基因型的技术。为了探索在大豆基因组测序中处理不完整数据的高效填充方法,以提高数据处理速度和效率,本研究采用真实的大豆参考面板基因型数据,通过对数据进行2%、5%、10%和25%的完全随机缺失处理,利用GPU加速的随机森林机器学习算法构建填充模型,并对不同缺失比例的数据进行填充。同时,对比分析了不同处理器的准确性和性能。结果显示:基于GPU加速的随机森林算法在大豆基因组中实现了优秀的填充精度。与主流基因填充软件相比,该方法至少提供了4倍以上的运算时间优势。因此,GPU加速的基因型填充策略可应用于大规模基因型数据处理中,提高大豆基因型数据处理的速度和效率,同时减少计算时间和资源消耗。

基于GPU加速的三阶有限体积格式管道瞬变流求解模型

为高效和高精度求解长距离输水系统瞬变流变化过程,应用三阶ENO有限体积格式求解一维管道非恒定流方程组,基于Lax-Friedrichs通量裂分法重构界面通量,上下游界面采用虚拟网格技术并结合交叉管网边界条件建立了一套高效和高精度求解管道瞬变流水锤波的数值模型。引入GPU加速技术,实现对大型输水系统的高效计算。通过特征线法、一阶及二阶Godunov有限体积格式对模型进行验证,结果表明,三阶ENO格式在极低的Courant数时也能保持较好的间断捕捉性能且无非物理振荡。同时,对Courant数的高度不敏感性,使得模型划分网格时具有高度的灵活性并能显著提高计算速度。应用GPU加速技术,发现模型在较多网格数时有明显的加速效果,且加速效果随网格数增多而显著。本文模型可为长距离输水系统非恒定瞬变过程的高效精准快速模拟预测提供理论支撑。

基于GPU加速的合成孔径雷达后向投影成像方法研究

SAR成像需使用算法对原始回波数据进行相干聚焦处理,得到目标区域的二维雷达图像。后向投影算法采用时域逐点相干聚焦,算法实现简单且适用于任意成像轨迹,因而得到广泛应用,但是该算法极为耗时,仅适用于数据量不大或实时性要求不高的情况。论文提出了一种基于GPU加速的合成孔径雷达后向投影成像方法,解决了传统后向投影算法处理效率低、难以实时成像的难题。

基于GPU加速的多源点云融合算法研究

点云融合是一种将多个来源的点云数据配准和融合为一个更完整和准确的三维模型的重要算法。目前,已经出现了许多种点云融合算法,如串行编程方式(ICP)、非刚性配准等,这些算法通常需要大量的计算资源。文章基于图形处理单元(GPU)并行计算技术,提出了一种高效的多源点云融合算法,主要包括基于GPU的点云配准算法和点云融合算法。通过对点云数据在GPU中的存储和传输进行优化,以及设计高效的GPU并行算法,可以大幅度提高点云融合的计算速度和效率,为实际应用提供有力支持。

起伏地表叠前逆时偏移理论及GPU加速技术

从起伏地表直接进行叠前逆时偏移是解决地表起伏大并且地下构造复杂这种双复杂结构地区成像问题的有力工具.本文给出了起伏地表直接进行叠前逆时偏移的实现过程,针对有限差分方法处理起伏地表自由边界条件的复杂性,采用了一种简化的自由边界条件,避免了大量的逻辑判断,在此基础上,采用图形处理器(GraphicProcessing Unit,简称GPU)将算法加速,比传统的CPU计算速度提高了一个数量级.文中对理论模型进行了计算,并与起伏地表直接进行单程波叠前偏移方法做比较,结果表明:起伏地表叠前逆时偏移有效突破了成像倾角限制,对起伏地表浅层构造以及地下高陡构造成像效果显著提高.关于逆时偏移成像噪音去除以及存储量等问题,笔者已有文章介绍,本文将不再涉及.

GPU加速的二值图连通域标记并行算法

结合NVIDIA公司统一计算设备架构(CUDA)下的图形处理器(GPU)并行结构和硬件特点,提出了一种新的二值图像连通域标记并行算法,高速有效地标识出了二值图的连通域位置及大小,大幅缩减了标记时间耗费。该算法通过搜索邻域内最小标号值的像素点对连通域进行标记,各像素点处理顺序不分先后并且不相互依赖,因此可以并行执行。算法效率不受连通域形状及数量的影响,具有很好的鲁棒性。实验结果表明,该并行算法充分发挥了GPU并行处理能力,在处理高分辨率与多连通域图像时效率为一般CPU标记算法的300倍,比OpenCV的优化函数(CPU)效率高近17倍。

GPU加速的航迹关联改进蚁群求解算法

分布式信息融合系统中,航迹关联问题可转化为多维分配进行求解,现有的求解方法存在着收敛速度慢、求解代数多的缺点,难以满足实时性要求。鉴于此,提出了一种GPU加速的改进蚁群求解算法。首先,运用灰色理论建立航迹关联多维分配问题模型;其次,蚁群算法求解过程中,通过选择最大灰关联系数邻域内的状态估计对搜索列表进行更新,缩小蚂蚁的搜索区域,并采用狼群分配原则更新信息素,避免了搜索陷入局部最优;最后,采用GPU加速的并行策略进行求解。仿真结果表明,一个关联周期内,10步迭代之内该算法的关联正确率可达90%以上;GPU加速的并行求解策略能够提高求解效率,且随着问题规模的增大,加速效果越明显。

基于GPU加速的几何纹理合成方法

提出了一种基于GPU加速的几何纹理合成方法,以解决几何纹理合成过程中高计算量、高存储占用和高耗时等问题.首先,对样本几何纹理数据进行子块划分,并根据子块在样本中的位置关系设计可重用样本顶点数据的数据结构,优化存储以降低内存的占用率;然后,采用GPU多线程并发技术设计并行加速算法,将串行的几何纹理合成过程并行化,从而实现快速生成任意尺寸的新的几何纹理.实验结果表明,该算法不仅占用存储较少,而且在保证合成质量的同时极大地降低了几何纹理的合成耗时.

基于GPU加速及改进谱FDTD方法的周期性结构分析

为解决作为分析周期性结构的时域数值算法本身在计算单角度入射时依然存在效率偏低的这一问题,提出了一种改进的谱FDTD方法,并运用图形处理器(GPU)对算法进行硬件加速.改进的算法在保证单频点运算结果精确的前提下,通过降低单次运算对运算结果频谱分辨率的要求以降低总体的运算时间.算例验证表明,在保证同等精度的前提下,改进后的算法将单角度斜入射问题的计算效率提高了1倍以上,并在此基础上通过GPU硬件加速成功实现了20倍以上的加速比,这证明了GPU加速的改进谱FDTD法的可行性与高效性.

无网格Galerkin法GPU加速并行计算及其应用

针对无网格Galerkin法计算耗时的问题,采用逐节点对法来组装刚度矩阵、共轭梯度法求解基于CSR格式存储的稀疏线性方程组,提出了一种利用罚函数法施加本质边界条件的EFG法GPU加速并行算法,给出了刚度矩阵和惩罚刚度矩阵的统一格式,以及GPU加速并行算法的流程图。编写了基于CUDA构架平台的GPU程序,且在NVIDIA GeForce GTX 660显卡上通过数值算例对所提算法进行了性能测试与分析比较,探讨了影响加速比的因素。算例结果验证了所提算法的可行性,并在满足计算精度的前提下,其加速比最大可达17倍;同时线性方程组的求解对加速比起决定性影响。

八叉树编码与GPU加速结合的光线投射法

为了同时保证绘制速度和图像质量,提出了一种基于GPU加速的光线投射算法.该算法利用图形硬件自带的三线性插值功能来完成光线投射算法中耗时的采样、插值过程,在采样过程中进行空间跳跃,以实现绘制加速.实验结果表明:该算法保证了高质量的图像绘制效果,在增加存储容量较小的同时将绘制速度提高了95倍,实现了海量体数据基于GPU的实时绘制.

GPU加速的物体空间线绘制算法

提出一种网格模型线绘制的GPU加速算法,其在物体空间进行计算,避免了图像空间计算的不连续性.提出了GPU加速物体空间线绘制的通用算法框架,理论上对任何特征线定义均可以按照该框架实现GPU加速的特征线绘制;基于该框架,实现了轮廓线与光极线(photic extremum lines,PEL)2种特征线的GPU加速绘制.实验结果表明,使用文中算法生成的线绘制结果与传统CPU算法结果几乎没有差别,但是绘制速度提高一个数量级以上.

GPU加速的支持交互式切割的柔性体实时变形算法

使用OpenGL和GLSL实现了GPU加速的柔性体实时变形算法。变形计算使用共旋线性有限元法,可以处理大尺度旋转情况。为了能够与交互式切割操作协同运作,GPU数据结构使用带激活标志的可变长线性数组。将切割过程中需要更新的单元分为"全肮脏"和"部分肮脏"两类,以此降低GPU数据的更新量。针对GPU不能完成发散操作的缺点,设计顶点相邻四面体信息数据结构和相应的切割更新算法,将力的发散操作变为聚合操作。使用四面体单元刚度矩阵高频模式过滤方法来提高稳定积分的时间步长,以此降低切割产生的退化单元对变形计算稳定性的负面影响。最后给出若干仿真测试的结果,对仿真效果和运行效率进行了分析。

基于GPU加速的包络波形反演

波形反演利用地震资料的相位和振幅信息对速度进行建模,是当前分辨率最高的速度估计方法。波形反演对初始速度场具有较高的要求,当初始速度场和真实的速度场相差较远时,容易产生周波跳跃问题。通常在进行速度反演时,采用多尺度方法减轻波形反演的非线性,然而当实际地震资料中缺少大偏移距和低频数据时,多尺度方法不再适用。此外,计算效率也限制了波形反演的应用。因此,这里提出基于GPU加速的包络波形反演来获取包含长波长信息的初始速度场,并提高计算效率。通过对Marmousi模型的测试,验证了方法的正确性和有效性。

三维医学图像核回归算法的GPU加速研究

核回归理论被广泛应用于医学图像处理和医学图像重建领域,并取得了十分显著的效果。它包括传统核回归方法(CKR)和控制核回归方法(SKR)。三维SKR算法比三维CKR算法具有更优的去噪效果和边缘保持效果,但三维SKR算法的计算量过于庞大且复杂,使其应用领域受到限制。目前,医学图像重建使用的是基于GPU的三维CKR算法,所以基于GPU的三维SKR算法的实现是一项有研究价值且具有挑战性的工作。本文首先优化三维SKR算法的计算过程,然后利用GPU进行CUDA编程实现三维SKR并行加速算法。实验表明,基于GPU的三维SKR算法与基于CPU单线程三维SKR算法相比能获得约244.9～246.3倍的加速比,与基于CPU多线程三维SKR算法相比能获得约123.0～137.4倍的加速比。

基于非结构网格隐式算法的GPU加速研究

针对非结构网格隐式算法在GPU上的加速效果不佳的问题,通过分析GPU的架构及并行模式,研究并实现了基于非结构网格格点格式的隐式LU-SGS算法的GPU并行加速.通过采用RCM和Metis网格重排序(重组)方法,优化非结构网格的数据局部性,改善非结构网格的隐式算法在GPU上的并行加速效果.通过三维机翼算例验证了本文实现的正确性及效率.结果表明两种网格重排序(重组)方法分别得到了63%和69%的加速效果提高.优化后的LU-SGS隐式GPU并行算法获得了相较于CPU串行算法27倍的加速比,充分说明了本文方法的高效性.