面向异构架构的传递闭包并行算法

传统求图传递闭包的方法存在计算量大与计算时间长的问题。为加快处理大数据量的传递闭包算法的计算速度,结合算法密集计算和开放式计算语言（OpenCL）框架的特征,采用本地存储器优化的并行子矩阵乘和分块的矩阵乘并行计算,提出一种基于OpenCL的传递闭包并行算法。利用本地存储器优化的并行子矩阵乘算法来优化计算步骤,提高图形处理器（GPU）的存储器利用率,降低数据获取延迟。通过分块矩阵乘并行计算算法实现大数据量的矩阵乘,提高GPU计算核心的利用率。数据结果表明,与CPU串行算法、基于开放多处理的并行算法和基于统一设备计算架构的并行算法相比,传递闭包并行算法在OpenCL架构下NVIDIA GeForce GTX 1070计算平台上分别获得了593.14倍、208.62倍和1.05倍的加速比。     

图象分块平均绝对差匹配并行算法

本文针对图象匹配算法中的乘法运算与差运算的一类并行计算问题 ,设计了一种图象分块平均绝对差匹配并行算法。该算法对于 N× N的参考图像、与处理元阵列大小相同的 M× M的实时图象 (N=BK,K=M,B>1) ,可通过将参考图像分成 B× B个图像块的分块匹配来实现 ,并具有很好的并行效率     

基于分块合并直方图改进的图像检索方法

在图像分块的基础之上,利用图像块的颜色信息作为图像特征进行图像的匹配。同时,还对块的直方图进行了合并,既提高了图像匹配的精度,又降低了算法的计算时间。最后,对图像块的匹配算法进行了探索,利用贪婪算法产生优化的对应块匹配方法。试验结果表明贪婪图像匹配算法优于传统分块的图像检索算法。     

基于CUDA的图像匹配算法

为解决目前已有的图像匹配算法不适用于对实时性要求很强的应用,提出了PLS（Partial Least Squares）与余弦定理相结合的并行化图像匹配算法。该算法在CUDA架构下,对图像矩阵分块,分块后每个小块图像存入共享存储器处理并提取每个小块图像特征,通过合并后图像特征采用余弦定理计算图像的相似度,从而找出匹配图像。实验表明,CUDA架构下可以实现图像的并行匹配,与CPU上串行匹配相比,时效性提高了百倍以上。     

基于内插阵列变换的扩展传播算子实值算法

针对内插阵列变换(VIA)思想在非圆信号波达方向(DOA)估计算法中的应用问题,提出一种基于内插阵列变换的扩展传播算子实值算法——VIA-EPM实值算法。利用真实阵列流型与虚拟阵列流型之间的变换矩阵,将真实阵列输出转换为虚拟阵列输出,再根据信号源为实数的特点,分别求取虚拟阵列输出的实部和虚部,将其串联组合,扩展阵列输出的维数,通过对扩展阵列输出矩阵进行分块并得出扩展传播算子,进而得到一种传播算子(PM)类的DOA估计算法。仿真实验表明：存在阵元位置误差的情况下,VIA-EPM实值算法通过对阵元位置校准数据进行内插阵列变换,取得与阵元位置校准的扩展传播算子实值算法(EPM实值算法)相当的估计性能,保持了阵列扩展能力、高估计精度以及高分辨力;并且在二维阵元位置误差情况下,其估计性能明显优于阵元位置未校准的EPM实值算法。结合VIA-EPM实值算法的计算复杂度分析可以看出：它同时获得了内插阵列变换技术以及信号非圆特性的优势;与复运算相比,其复杂度也相对降低。     

分块矩阵的张量积及其并行计算

矩阵张量积的计算是矩阵计算中的一类重要问题,与乘法相比,张量积的计算量更为庞大.分析了分块矩阵张量积的相关数学特性,证明了在置换相抵意义下两个矩阵的张量积运算可以交换,特别刻画了这类置换矩阵,并由此证明了在置换相抵条件下分块矩阵可以分块地进行张量积运算.在此基础上,讨论了矩阵张量积的并行计算问题,提出了几种并行计算模型,进行了必要的算法分析,并通过实例阐述了这些算法的思想和过程.     

异构Beowulf系统负载均衡技术的研究与实现

负载均衡技术是并行计算系统的关键技术之一,其主要思想是将计算任务合理分配到各节点,以避免由于某个节点的计算速度慢而导致的整个系统的性能瓶颈。为了使系统达到更优的结果,提出了一种基于MPICH的负载均衡模型,构建了一个异构Beawulf并行计算系统,并且用一个适合异构环境的矩阵分块相乘算法进行了性能测试。实验结果表明,此算法比使用传统的矩阵相乘算法执行效率更高。从而证明了系统能够把计算任务高效合理地分配到各个节点。     

运用矩阵结构的可并行地形层次细节算法

针对ROAM算法因分块间的耦合关系不适合大规模地形渲染,以及算法递归实现导致绘制效率低下的问题,结合嵌套网格算法压缩比高的优点,提出一种运用矩阵结构的可并行计算的地形层次细节算法.采用矩阵结构消除地形分块间的耦合关系,以解决大规模地形的分块渲染问题;用对矩阵的遍历代替递归操作来提高算法的执行速度;最后将计算并行化处理,...     

异构并行平台的Caffe推理速度提升方法

随着计算机硬件性能的提高,目前在个人终端上也开始出现使用预训练机器学习模型进行推理的运用.Caffe是一款流行的深度学习框架,擅长图像分类等任务,但是在默认状态下只能单核运行,无法充分发挥异构并行计算设备的计算能力.深度学习对于计算性能的要求较高,如果能并行化以充分使用所有计算设备,就能提升计算速度和使用体验.由于CPU和GPU的计算性能之比在不同模型下存在差异,因此不能简单将任务均分到多个计算设备.而任务拆分过多或者需要等待多设备完成任务后同步的调度算法会引入更多开销.因此,还需要设计合适的调度算法减少设备空闲时间,才能获得更好的性能.已有一些提高Caffe并行表现的方法,但是对于具体平台有限制且使用难度较高,无法简单充分利用异构并行计算设备的计算能力.本文将Caffe接口扩展,使得自定义程序可以调用异构并行平台的多核或多计算设备使用Caffe进行深度学习推理.接着将目前已有的多种调度算法运用到此类任务上并考察了运行效果.为了减少已有调度算法的同步开销,本文提出了先进先出调度和快速分块调度两种新的算法.测试表明,使用快速分块调度算法结合异构并行计算设备,Caffe的推理速度相比只使用单个CPU核心或者单个GPU都大幅提升.而且,相比已有调度算法中表现最好的HAT算法,本文提出的快速分块调度算法在MNIST和Cifar-10两个数据集上分别减少了7.4%和21.0%的计算性能浪费.     

异构Beowulf系统负载均衡技术的研究与实现

负载均衡技术是并行计算系统的关键技术之一,其主要思想是将计算任务合理分配到各节点,以避免由于某个节点的计算速度慢而导致的整个系统的性能瓶颈.为了使系统达到更优的结果,提出了一种基于MPICH的负载均衡模型.构建了一个异构Beowulf并行计算系统,并且用-个适合异构环境的矩阵分块相乘算法进行了性能测试.实验结果表明,此算法比使用传统的矩阵相乘算法执行效率更高.从而证明了系统能够把计算任务高效合理地分配到各个节点.     

基于Cortex嵌入式多处理器系统的图像中值滤波算法并行化的研究

嵌入式系统在图像处理、空间计算等领域越来越广泛,如何在功耗、成本和计算能力三个主要方面取得平衡,利用多核和多处理器系统以并行计算方式提高嵌入式系统计算能力是一种有效的解决方案.讨论了基于Cortex嵌入式多处理器系统的基本结构,并在该系统上进行图像中值滤波算法的并行化研究.实验结果分析表明,在该嵌入式多处理器平台上配合并行算法能够成倍提高图像中值滤波的运行性能.     

多核环境下的图像分割并行算法研究

对多核环境下的图像分割并行算法进行研究,在基于正交小波分解的多分辨率图像锥中引入模糊C-均值(FCM)算法,采用OpenMP语言设计P-FCM多核并行模型,并给出该模型的算法实现步骤。在对初始图像数据预处理时,采用矩形块数据分割法进行图像分块,将分块后的子图像数据作为并行运算时的输入数据由主线程分给不同的处理器。实验结果表明,在处理较大图像时,该算法效率较高。     

Euclidean distance transform for binary images on reconfigurable mesh-connected computers.

The distance calculation in an image is a basic operation in computer vision, pattern recognition, and robotics. Several parallel algorithms have been proposed for calculating the Euclidean distance transform (EDT). Recently, Chen and Chuang proposed a parallel algorithm for computing the EDT on mesh-connected SIMD computers (1995). For an nxn image, their algorithm runs in O(n) time on a two-dimensional (2-D) nxn mesh-connected processor array. In this paper, we propose a more efficient parallel algorithm for computing the EDT on a reconfigurable mesh model. For the same problem, our algorithm runs in O(log(2)n) time on a 2-D nxn reconfigurable mesh. Since a reconfigurable mesh uses the same amount of VLSI area as a plain mesh of the same size does when implemented in VLSI, our algorithm improves the result in [3] significantly.     

基于OpenCL的JPEG压缩算法并行化设计与实现

随着图像数据的大量增加,传统单处理器或多处理器结构的计算设备已无法满足实时性数据处理要求。异构并行计算技术因其高效的计算效率和并行的实时性数据处理能力,正得到广泛关注和应用。利用GPU在图形图像处理方面并行性的优势,提出了基于OpenCL的JPEG压缩算法并行化设计方法。将JPEG算法功能分解为多个内核程序,内核之间通过事件信息传递进行顺序控制,并在GPU+CPU的异构平台上完成了并行算法的仿真验证。实验结果表明,与CPU串行处理方式相比,本文提出的并行化算法在保持相同图像质量情况下有效提高了算法的执行效率,大幅降低了算法的执行时间,并且随着图形尺寸的增加,算法效率获得明显的提升。     

自适应SSDA图像匹配并行算法设计与实现

为了充分利用多核处理器的硬件资源和计算能力来提高图像匹配应用的实时性,通过对自适应阈值SSDA图像匹配算法原理的分析,基于任务分解的多核并行编程模式思想,设计了一种自适应阈值SSDA图像匹配并行算法,并在多核计算机上采用OpenMP模型编程实现该并行算法,同时还进行了相关的代码优化。实验结果表明,优化后的并行算法在保持匹配算法精度的同时大大提高了匹配速度和多核利用率,取得了良好的效果。     

卫星遥感图像并行几何校正算法研究

几何校正是遥感图像处理过程中的重要环节，具有计算量大、耗时长的特点，导致遥感图像处理的效率低下．该文提出一种分布存储环境下的并行几何校正算法，每个处理器通过计算本地输入子图像在目标图像中的范围，确定其需要进行重采样计算的区域，使计算过程中所需的数据均为本地数据，很好地解决了数据局部性问题．文章利用首尾相连的闭线段近似表示理想的输出图像块边界这一思想，详细讨论了局部输出区域的计算方法，并采用一种新的存储结构用于保存校正后的输出图像块信息．在机群系统上对算法进行实现，结果表明该算法具有良好的并行性能．     

基于CUDA技术的卷积神经网络识别算法

针对具有高浮点运算能力的流处理器设备GPU对神经网络的适用性问题,提出卷积神经网络的并行化识别算法,采用计算统一设备架构(CUDA)技术,并定义其上的并行化数据结构,描述计算任务到CUDA的映射机制。实验结果证明,在GTX200硬件架构的GPU上实现的并行识别算法的平均浮点运算能力峰值较CPU上串行算法提高了近60倍,更适用于神经网络的相关应用。     

负载平衡无关的并行程序最适处理器网格选择

用户在编写并行程序时,通常是把物理处理器看成逻辑的处理器(进程)网格,以便于算法的实现.随着用户可用处理器的不断增多,可选择的网格形状也随之增加,如何为基于消息传递的并行程序选择合适的、能发挥出并行机潜在性能的处理器网格形状,是一个迫切需要解决的问题.在提出基于通信点概念的最小度数通信点集合法之后,通过对并行程序通信模式的分析,试图解决与负载平衡无关的并行程序的最适处理器网格选择问题.通过对ScaLAPACK软件包中的一个并行测试程序——并行Cholesky(对称正定矩阵分解)通信点集合度的分析,此方法成功地选择了最适处理器网格形状,并与实验结果相一致.     

遥感卫星图像几何粗校正的数据并行方法研究

主要研究星上遥感图像的实时几何粗校正问题．卫星遥感图像现在一般都大到上万个像素行和列，采用传统的单个处理器的串行方式在星上进行实时处理是难以满足应用要求的．提出了一种在一维PE阵列的SIMD计算机上采用基于处理元阵列平移的数据并行校正方法，并根据NASA的LANDSAT-1卫星的有关的参数，对该方法进行了详细讨论，给出了具体的实现方法．通过对复杂性和加速比的讨论，表明该方法在性能上比采用单个处理器的串行方法提高了N倍．     

一个改进的并行关联规则算法研究

在研究关联规则挖掘算法的基础上,对并行关联规则算法进行了比较全面的分析,并给出了并行数据挖掘的计算框架。提出了一个以计算服务器为中心节点的并行挖掘算法,可以发挥各局部节点的优势,无需各局部节点进行通信,减少了各局部节点的通信负荷。通过理论分析和实验数据验证,该算法具有较好的可扩展性和海量处理能力,特别是在节点数目较多的情况下更显示出优势。