基于H.264实时编码的多核并行算法

针对H.264多核实时编码架构,根据编码模块的数据依赖关系,提出基于相邻宏块的并行算法,融合Slice级、宏块行级和相邻宏块级并行算法,实现多粒度并行编码算法,加大了数据并行深度。实验结果表明,该并行编码算法在图像质量几乎不变的情况下能有效提高并行加速比。     

Research on Parallel Algorithm of Fdge Extraction Based on Multi-processor

随着处理器由高主频的单核处理器逐步转向片上多核处理器(CMP),计算机并行处理能力不断提升.通过分析GIS串行算法面临的性能瓶颈,利用CMP的优势,采用线程级并行处理栅格数据.针对边缘提取算法,深入分析和比较了MPI、OpenMP等当前主流的并行编程模式,提出了并行性能估计模型.基于OpenMP编程模型分析线程数、调度方式和分块大小对算法并行性能的影响,实现边缘提取最优并行.实验证明,性能评估模型能够准确预测CMP环境下的并行性能,基于OpenMP实现的边缘提取并行算法能够提高图像边缘提取效率.     

基于同构多核处理器的H.264多粒度并行编码器

H.264码率低和视频质量高的优越性能以增加编码计算的复杂度为代价,如何开发适用于多核处理器平台的并行编码算法是提高其编码速度的重要研究内容,对于满足高清视频实时传输和大规模共享具有十分重要的意义.利用H.264开源编码器项目X264,在片级和数据级并行编码算法的基础上,通过分析图像帧之间的参考关系,提出并实现了B帧个数可变的帧级并行算法;根据宏块之间的参考关系,设计了一种类似流水线的宏块级并行方法;基于Intel同构多核平台,提出融合帧级、片级、宏块级和数据级4种不同粒度的并行编码方案,开发了H.264多粒度并行编码器.实验结果表明,在码率增加不大的情况下,H.264多粒度并行编码器可以很好地提升编码加速比,视频编码质量符合高质量的要求.     

H.264并行编码中负载平衡方法

针对在多核处理器上Slice并行编码H.264高清视频中的负载不平衡问题,首先利用已编码帧的编码统计信息,根据帧间时间相关性预测下一帧各宏块的编码负载,然后据此预测的编码负载划分Slice,使各个处理器核上编码的Slice具有相接近的计算负载,从而达到动态负载平衡目的。在Tile64多核平台上的实际测试结果表明,与传统的基于宏块区域的动态数据分配算法相比,该方法可以将编码并行加速比和并行效率提高5%左右。     

面向DSWP并行的OpenMP任务调度机制的扩展与实现

多核处理器能够提升多线程程序的性能,但早已存在的诸多单线程程序无法从中获益,程序员也习惯于编写单线程程序.自动并行化技术是将单线程程序移植到多核上的重要手段,但是当循环中存在无法确定的数据依赖或复杂的控制流时,传统的自动并行化技术无法取得良好效果.Ottoni等人针对传统自动并行失败的循环提出了Decoupled Software Pipelining(DSWP)算法用以实现指令级的细粒度并行,但其需要对处理器体系结构的深入了解以及对核间通信队列和专用指令的硬件支持,并行性能和应用广泛性受到限制.基于OpenMP应用编程接口实现的DSWP并行不依赖于硬件上对核间通信队列和专用指令的支持,且不受平台的限制,但现有的OpenMP任务调度机制无法满足DSWP并行中对任务调度的需求.对现有的OpenMP任务调度机制进行扩展,增加了任务与线程绑定的属性,保证了基于OpenMP的DSWP并行程序的正确执行.在GCC的OpenMP运行库libgomp中扩展了任务绑定属性子句的功能,扩展后的GCC作为OpenMP DSWP程序的基础编译器,为自动并行提供支持.通过对基准测试集NPB3.3.1的测试表明,传统自动并行失败的循环,经OpenMP DSWP自动并行后在双核处理器上平均加速比达到1.23以上;使用添加了OpenMP DSWP算法的Open64编译器生成的并行程序,与仅使用传统自动并行方法的Intel 编译器和Open64编译器所得程序相比,平均加速比分别高出22％和26％.     

多核计算环境下快速排序并行算法的实现

研究了快速排序算法,并在其基础上提出了基于多核技术的OpenMP并行编程模型的快速排序算法.实验结果表明,该并行算法具有较高的并行加速比和并行效率.     

多核环境下边缘提取并行算法研究

随着处理器由高主频的单核处理器逐步转向片上多核处理器(CMP),计算机并行处理能力不断提升。通过分析GIS串行算法面临的性能瓶颈,利用CMP的优势,采用线程级并行处理栅格数据。针对边缘提取算法,深入分析和比较了MPI、OpenMP等当前主流的并行编程模式,提出了并行性能估计模型。基于OpenMP编程模型分析线程数、调度方式和分块大小对算法并行性能的影响,实现边缘提取最优并行。实验证明,性能评估模型能够准确预测CMP环境下的并行性能,基于OpenMP实现的边缘提取并行算法能够提高图像边缘提取效率。     

基于GPU的多层次并行QR分解算法研究

QR分解作为一个基本计算模块,广泛应用在图像处理、信号处理、通信工程等众多领域.传统的并行QR分解算法只能挖掘计算过程中的数据级并行.在分析快速Givens Rotation分解特征的基础上,提出了一种多层次并行算法,能够同时挖掘计算过程中的任务级并行和数据级并行,非常适合于以图形处理器(GPU)为代表的大规模并行处理器.同时,采用GPU的并行QR分解算法可以作为基本运算模块被GPU平台上的众多应用程序直接调用.实验结果显示,与CPU平台上使用OpenMP实现的算法相比,基于GPU的多层次并行算法能够获得5倍以上的性能提升,而调用QR分解模块的奇异值分解(SVD)应用可以获得3倍以上的性能提升.     

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

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

面向层次化NoC的混合并行编程模型

为更好发挥多核处理器的硬件性能,针对层次化的片上网络架构,提出MPI/OpenMP混合并行编程模型。运用基于MPI的任务级并行模型实现片内簇间的高效通信,采用OpenMP模型实现簇内四核的通信、同步和数据交换。实验结果表明,与单一并行编程模型相比,混合并行编程模型加速比提高了20%~50%。     

简单要素模型多边形拓扑检查并行算法

将并行计算应用到大数据量简单要素模型多边形拓扑检查中,设计实现了简单要素模型多边形拓扑检查并行算法。算法针对拓扑检查的计算特点,改进了主从式并行策略,在主进程中进一步划分线程以实现任务并行,从而隐藏拓扑错误提取和结果写入时间。采用MPI和PThread实现进程与线程的结合。利用苏南五市土地现状调查地类图斑数据对算法进行测试。经测试,该算法能够对大数据量简单要素模型多边形进行准确、快速的拓扑检查。算法提出的进程与线程结合的任务并行策略相对于传统主从式策略加速比提高约20%。     

基于高清编码的自适应Slice划分算法

对于多核高清视频实时编码系统,提出一种自适应Slice划分算法。该算法基于码率控制和熵编码复杂度模型,通过Intra预测得到当前编码图像的纹理复杂度分布,预测编码图像的计算复杂度分布,通过自适应Slice划分实现多核间计算复杂度均匀分配,从而提高多核并行编码效率。实验结果表明,与固定宏块数的Slice划分算法相比,该算法能更有效地提高并行加速比。     

基于时域依赖的编码树单元级零延时码率控制算法

基于高效视频编码标准的x265编码器根据图像复杂度来分配比特,复杂图像往往包含运动变化较大的高频信息,其时域相关性较弱且消耗较多比特,导致分配给运动变化平缓图像的比特减少,进而影响编码质量且码率波动较大。同时,x265编码器采用独立率失真优化技术编码,忽略了编码单元间在时域上的相关性,进而损失编码性能。针对上述问题,提出一种基于时域依赖的编码树单元级码率控制算法。首先,根据迭代策略寻找最合适的量化参数进行帧级比特分配;其次,建立零延时的失真时域反向传播模型并计算失真影响因子;最后,将失真影响因子用于调整编码单元的拉格朗日乘子及量化参数。实验结果显示,相较于x265-3.6的码率控制算法,平均BD-rate码率节省达到5.6%。     

基于H.264/AVC的自适应帧级位分配优化算法*

为了获得精确的帧级目标位分配和提高编码质量,在JVT-G012码率控制算法的基础上,提出一种自适应的帧级位分配优化算法。该算法充分考虑帧之间纹理复杂度,弥补了JVT-G012算法中对帧目标位平均分配算法的不足。大量实验结果表明,改进后的算法在高运动或场景切换情况下,能明显提高视频编码质量,实现目标位的优化分配和输出码率的精确控制。     

闭排队网络基于并行仿真的灵敏度估计和优化算法

基于Markov性能势理论，对一类闭排队网络的灵敏度估计和优化，建立了一种行之有效的并行仿真算法。采用公共随机数，使所有的处理器使用相同的样本轨道，以减少各个处理器之间的通讯时间。在一台SPMD并行计算机上的仿真实例表明，该并行仿真算法对于闭排队网络的优化能显著地提高运算速度。     

基于排队网络的多优先级MapReduce作业调度算法

MapReduce是一个能够对大规模数据进行分布式处理的框架,目前被各个领域广泛应用。在提供MapReduce服务的集群中,如何保证不同优先级用户的截止时间限定是MapReduce作业调度问题的一个挑战。针对这一问题,提出了一个基于排队网络的多优先级作业调度算法（MPSA）。首先分析和归纳了基于MapReduce模型的算法,提出了三种常见模式,采用Jackson排队网络对基于MapReduce模型的算法建立了数学模型,应用该网络模型可以求出不同优先级队列对资源的需求;随后使用AR(1)模型进行预测,使算法可以动态地适应不同的用户访问量;利用二分查找算法,分步计算出不同优先级在map阶段和reduce阶段分配的槽位数;最后实现了在MapReduce模型中应用的实时调度算法。实验结果表明,与传统的FIFO和公平调度算法相比,本文提出的算法在用户到达率和任务规模变化的情况下,可以更加有效地满足不同优先级用户的截止时间限定。     

云计算环境下对资源聚类的工作流任务调度算法

针对云计算环境中资源具有规模庞大、异构性、多样性等特点,提出了一种对资源进行模糊聚类的工作流任务调度算法。经过对网络资源属性进行量化、规范化,以预先构建的任务模型和资源模型为基础,结合模糊数学理论划分资源,使得在任务调度时能够较准确地优先选择综合性能较好的资源类簇,缩短了任务资源相匹配的时间,提高了调度性能。通过仿真实验将此算法与HEFT、DLS进行比较,实验结果表明,当任务在[0,100]范围增加时,该算法平均SLR比HEFT小34%,比DLS小99%,其平均Speedup比HEFT大59%,比DLS大102%;当资源在[0,100]范围增加时,该算法平均SLR比HEFT小36%,比DLS小97%,其平均Speedup比HEFT大45%,比DLS大108%。所提算法实现了对资源的合理划分,且在执行跨度方面具有优越性。     

基于多核处理器的K线程低能耗的任务调度优化算法

针对具有独立DVFS的多核处理器系统,提出了一种K线程低能耗模型的并行任务调度优化算法(Tasks Optimization based on Energy-Effectiveness Model,TO-EEM)。与传统的并行任务节能调度相比,该算法的主要目标是不仅通过降低处理器频率来减少处理器瞬时功耗,而且结合并行任务间的同步互斥所造成的线程阻塞情况,合理分配线程资源来减少线程同步时间,优化并行性能;保证任务在一定的并行加速比性能前提下,提高资源利用率,减少能耗,达到程序能耗和性能之间的折衷。文中进行了大量模拟实验,结果证明提出的任务优化模型算法节能效果明显,能有效降低处理器的功耗,并始终保持线性加速比。     

A study of achievable speedup in distributed simulation via NULLmessages

The results of an experimental study on distributed simulation of three open queuing networks are reported. The distributed simulation scheme considered is a simple variation of the scheme given by K.M. Chandy and J. Misra (1979) using NULL messages. A new approach is used to study the relationship between the overhead and performance of a distributed simulator, and the approach is illustrated by studying these three example networks. Two measures of ideal speedup of distributed simulation over sequential simulation are defined and measured. These values of ideal speedup are much less than simply the number of processors, and hence provide a more realistic value for the ideal speedup