基于OpenMP矩阵相乘并行算法的设计

目的设计并实现一种基于数据划分的矩阵乘法的并行算法,将划分的数据交给多个线程同时执行,充分挖掘计算机的性能。方法根据OpenMP并行编程的基本风格,并在Visual Studio2005上搭建能够实现并行编程的环境平台。结果并行算法所花费的时间较非并行算法短。结论通过与非并行矩阵乘法性能进行比较,验证该算法可以有效地利用多核处理器的优势。     

多核处理器中基于MapReduce的哈希划分优化

针对传统的并行哈希划分算法不能高效地利用多核处理器的并行资源,且不能较好处理有倾斜的输入数据的问题,提出了一种在多核处理器中基于MapReduce的哈希划分算法,并且提出了存储结构优化、多步划分优化、数据倾斜优化3种优化策略。该算法将输入数据分成若干块后提交给各个线程并行处理,并选择合适的策略避免写冲突,使其能够高效地利用多核处理器的并行资源。文中提出的哈希表能够提高cache效率,从而提升算法的整体性能。引入MapReduce模型可使多步哈希划分在Map过程和Reduce过程中分别进行;数据倾斜优化策略能使算法适应有倾斜的输入数据,且具有较好的效果。实验结果表明:在多核处理器中,文中提出的算法能够适应各种分布的输入数据,并且使哈希划分的整体性能得到提升。     

基于异构平台的图像中值滤波的OpenCL加速算法

图像噪声降低了图像信噪比和质量,去噪是图像处理工作的重要环节之一.本文提出了一种基于开放式计算语言(OpenCL)架构的图像中值滤波快速降噪并行算法.介绍了OpenCL体系结构特点和中值滤波处理流程.根据图形处理器(GPU)的并发结构特点,对图像中值滤波功能模块进行了并行优化,降低了算法复杂度.通过充分激活NDRange索引空间中的工作组和工作项来提高数据访问效率,优化内核工作组配置参数,实现了中值滤波器的并行处理.实验结果表明,在图像质量保持不变的情况下,与基于CPU的串行算法、基于开放多处理(OpenMP)并行算法和基于统一计算设备架构(CUDA)并行算法性能相比,图像中值滤波并行算法在OpenCL架构下NVIDIA GPU计算平台上分别获得了29.74、17.29、1.15倍的加速比.验证了算法的有效性和平台的可移植性,基本满足应用的实时性处理要求.     

基于多核并行计算技术的混合交通微观仿真

为提高混合交通微观仿真的运行速度,将多核并行计算技术应用于混合交通微观仿真中.提出混合交通微观仿真的并行化方法,包括基于对串行混合交通微观仿真中各个模块CPU运算时间的百分比分析,确定基于数据并行的任务分解方法,及结合多内核CPU架构特点确定Fork/Join的并行模式.提出基于多核技术的混合交通微观仿真的关键并行算法,包括初始路网分割算法、车辆穿越边界算法及动态负载平衡算法.通过仿真实验验证多核并行计算技术能够提高混合交通微观仿真的运行效率.     

基于OpenCL的图像灰度化并行算法研究

随着图像数据量的增加,传统单核处理器或多处理器结构的计算方式已无法满足图像灰度化实时处理需求.该文利用图像处理器(GPU)在异构并行计算的优势,提出了基于开放式计算语言(OpenCL)的图像灰度化并行算法.通过分析加权平均图像灰度化数据处理的并行性,对任务进行了层次化分解,设计了2级并行的并行算法并映射到“CPU+GPU”异构计算平台上.实验结果显示:图像灰度化并行算法在OpenCL架构下NVIDIA GPU计算平台上相比串行算法、多核CPU并行算法和CUDA并行算法的性能分别获得了27.04倍、4.96倍和1.21倍的加速比.该文提出的并行优化方法的有效性和性能可移植性得到了验证.     

一种采用预排序策略的多核并行skyline算法

为提升大规模多维数据集的skyline计算效率,提出了一种多核并行算法MPSCS(multi-core parallelskyline computation based on sorting).首先按照任意一维对数据集进行预排序,然后划分为多个子集,使用skeleton并行程序设计模型进行并行化处理.与未采用预排序策略的多核并行算法相比,MPSCS算法处理过程简单,具有较好的渐进性、用户友好性和效率.实验结果表明,对规模较大、维数较高的数据集,效率可提高30%～40%,相对加速比可达线性.     

基于多核的并行混合交通微观仿真系统

为了提高混合交通微观仿真的运行速度,基于多核并行计算技术构建了一个混合交通微观仿真平台.文中首先从平台功能结构、并行混合交通微观仿真流程设计与实现两个方面对平台进行介绍;其次,设计并实现了该仿真平台的关键并行算法,包括初始路网分割算法、车辆穿越边界算法及动态负载平衡算法;最后,通过仿真实验验证了多核并行计算技术能够大大提高混合交通微观仿真的运行效率.     

CPU+GPU异构并行的矩阵转置算法研究

针对当前算法优化研究一般局限于单一硬件平台、很难实现在不同平台上高效运行的问题,利用图形处理器(GPU)提出了基于开放式计算语言(OpenCL)的矩阵转置并行算法.通过矩阵子块粗粒度并行、矩阵元素细粒度并行、工作项与数据的空间映射和本地存储器优化方法的应用,使矩阵转置算法在GPU计算平台上的性能提高了12倍.实验结果表明,与基于CPU的串行算法、基于开放多处理(OpenMP)并行算法和基于统一计算设备架构(CUDA)并行算法性能相比,矩阵转置并行算法在OpenCL架构下NVIDIA GPU计算平台上分别获得了12.26,2.23和1.50的加速比.该算法不仅性能高,而且实现了在不同计算平台间的性能移植.     

多细胞基因表达式编程函数优化的并行算法研究

并行算法是当前研究解决算法效率问题的成熟技术之一。为提高GEP算法解决复杂函数优化问题的效率,将并行算法引入多细胞基因表达式编程函数优化问题,解决传统计算形式不能充分发挥多核处理器性能的问题。通过分析多细胞基因表达式编程并行算法的机理和MPI和Open MP混合并行模型,设计与实现多细胞基因表达式编程函数优化的并行算法(Parallel Multicellular Gene Expression Programming algorithm for Function Optimization)PGMFO。实验结果表明针对复杂的函数优化问题,在不影响精度和收敛性的情况下,PGMFO算法比原有的算法效率高出10%~20%。     

多核构架下基于OpenMP 的Huffman压缩算法并行设计

本文是对多核程序设计的一种探索,在OpenMP模型下以赫夫曼算法为基础设计并行压缩程序.首先对传统的串行程序进行分析,使应用程序开发人员了解程序行为、发现性能瓶颈、明确优化方向.再用OpenMP的基本结构进行并行程序的设计之后,借助开发工具对并行程序进行优化和调试,得到改进方案.然后在双核处理器上分别运行并行程序与串行程序,将两者进行性能上的比较,实验结果证明性能得到很大程度地提高。     

基于GPU加速的全源对最短路径并行算法

针对最短路径算法处理大规模数据集低效的问题，提出了基于图形处理器（Graphics Processing Unit,GPU）加速的全源对最短路径并行算法.首先通过优化矩阵乘法算法实现了在工作组内和组间进行并行运算数据，然后减少了非规则行造成的工作项分支，最后降低了工作项对邻接矩阵计算条带存储资源的访问延时.实验结果表明，与基于AMD Ryzen5 1600X CPU的串行算法、基于开放多处理（Open Multi-Processing, OpenMP）并行算法和基于统一计算设备架构（Compute Unified Device Architecture, CUDA）并行算法相比，最短路径并行算法在开放式计算语言（Open Computing Language, OpenCL）架构下NVIDIA GeForce GTX 1 070计算平台上分别获得了196.35、36.76和2.25倍的加速比，验证了提出的并行优化方法的有效性和性能可移植性.     

大场景点云文件多核并行批量压缩方法研究

为了减少大场景点云文件无损压缩时间,避免数据处理过程中人工操作造成的时间浪费和输入失误,本文引入LASzip点云无损压缩算法和OpenMP并行编程技术,提出了在单机多核CPU系统环境下基于LASzip的大场景点云文件多核并行批量压缩算法。实验结果显示,与串行算法相比,并行算法在压缩比不变的情况下压缩时间明显下降,取得了很好的加速比。当线程数为8时,压缩和解压缩加速比分别达到4.27和3.99,优化效果显著。     

基于Amdahl定律的分组密码并行处理模型研究

为进行分组密码并行处理的理论研究和定量分析,构建了基于Amdahl定律的分组密码并行处理模型.通过引入分组内数据级并行性、分组内指令级并行性、分组间数据级并行性和分组间指令级并行性等并行性,建立了分组密码的多维度并行处理模型,研究了算法参数和并行参数对分组密码处理性能的影响.结果表明,并行比例大的算法其性能提升空间较大,且开发任一并行性都能够提升密码运算性能;但对于具体的应用场景,需要根据算法结构、工作模式等来进行合理的资源配置和并行性开发;该模型能够为分组密码算法的并行处理架构设计、资源配置和并行性开发等提供理论依据和指导原则.      

一种多核处理器环境下的软件结构及负载均衡

通信网络技术迅速发展对产品的性能提出了更高的要求,多核处理器以其高性能的优点逐渐得到通信厂商的广泛使用.为了发挥多核处理器的潜能,在分析通信网关服务器产品特性的基础上,充分利用服务器的进程功能和特点,研究一种多核处理器环境下的软件结构,提出基于哈希算法的负载均衡,阐述基于动态哈希(hash)算法的负载均衡的设计和实现.不但提高了多核处理器处理用户请求的效率,而且具有强扩展性和高可靠性等优点.     

超立方体多计算机上数据并行算法性能研究

讨论了超立方体多计算机上的数据并行算法，着重分析通信参数对算法性能的影响。提出了一个计算模型，并以并行归并算法为例，对数据元素数目和处理机数目等设计参数进行性能评价。     

采用BWT的多核并行的子串匹配算法

针对P-BWT精确匹配算法存在只支持短串查询并且只能工作在单处理器上的问题,提出了一个多核并行的支持任意查询长度的精确查询算法.改进了P-BWT索引上的查询过程,当一个查询串跨越了多个数据分片时,首先在其匹配的最后一个分片上查询,然后依次在前面分片上进行验证.进一步提出了一个多核并行查询算法来减少搜索和验证过程的迭代次数.实验结果表明,所述算法可以高效并行地完成子串匹配任务.     

面向X86多核处理器的数据流程序任务调度与缓存优化

数据流编程作为一种编程模式被广泛地应用于多核处理器系统,其多核处理器的并行调度和对主存的访问延迟对程序的性能有很大的影响.为此,结合X86多核处理器的特点,提出一种数据流程序的任务调度与缓存优化方法.任务调度优化首先在预处理阶段提高目标程序的局部性和并行粒度;然后利用数据流程序的数据并行、任务并行和流水并行优化核间负载均衡,并构造软件流水调度.缓存优化针对目标系统的层次性缓存结构特征,通过消除缓存伪共享减少多核并行运行时相互间的干扰,根据逻辑线程间的通信分布实现逻辑线程到处理器核的映射.以COStream作为数据流编程语言,输出经过编译优化后的目标代码.实验选取数字媒体领域典型的算法进行测试,测试结果表明,编译优化后的测试程序基本达到线性加速比,验证了编译系统的有效性.     

基于并行计算的图像检索技术的研究

由于图像处理和检索过程中的数据量巨大,而且各种算法中大量卷积运算和矩阵乘法运算的存在,为图像处理过程中的并行算法设计和实现提供了可能。提高图像处理的速度是由图像数据的特点和图像处理算法的复杂性引起的。并行计算是提高处理和检索速度的有效手段之一。所以将以并行算法在图像处理和检索中的应用为研究对象,重点研究图像处理和图像检索的并行算法处理,并且证明多核环境下实现的基于内容的图像检索技术大大提高了图像的检索速率。     

基于GPU并行优化的BBPSO-PF算法

针对粒子滤波算法在重采样环节因粒子交互而不能充分并行处理的问题,提出了基于图形处理器(GPU)的并行骨干粒子群优化粒子滤波算法(BBPSO-PF).首先利用骨干粒子群算法具有易并行的特点优化粒子滤波算法重采样环节,从算法结构上提高粒子滤波算法的并行度.然后利用GPU的多线程架构并行处理每个粒子群的数据,每个线程负责一个粒子群,使粒子群之间得到并行化处理,解决粒子滤波重采样因粒子交互而不能充分并行的缺点.最后利用GPU中对齐与合并的内存访问原则,给粒子群设计高效的数据存储结构,降低内存访问事务,提高粒子群的数据存取速度,进一步提高算法实时性.该方法在保证算法精度前提下明显提高了算法的实时性.     

基于OpenMP的对称矩阵:LDLT分解并行算法实现

分析对称矩阵LDLT分解过程的并行结构,给出对称矩阵LDLT分解的并行算法,然后考虑粗粒度组合后的负载平衡,提出基于OpenMP的对称矩阵LDLT分解并行算法的实现方案,并对该方案的并行计算性能进行数值实验.实验表明,基于OpenMP的对称矩阵LDLT分解并行算法在多核处理器系统中能够显著地提高算法性能.