基于TBB和Cilk++的并行蚁群算法在路径寻优中的应用

针对实际道路路网的一类路径寻优问题,提出了带回退机制的蚁群搜索算法,求解在实际道路路网中完成遍历所有规定节点的一条较优路径。为解决大规模实际道路路网数据量大、蚁群算法收敛速度慢的问题,分别采用Intel Threading Building Blocks(TBB)和Cilk++并行编程模型实现了并行蚁群搜索。与基于WinAPI函数的多线程蚁群算法相比,这两种模型均避免了手动启动线程及识别临界区资源等复杂操作,开发难度降低;在运行效率方面,基于TBB的并行蚁群算法和基于WinAPI的并行蚁群算法效率接近,而基于Cilk++的并行蚁群算法在双核环境下,运行效率和加速比都超过了基于WinAPI的并行蚁群算法。

MPI+TBB混合并行编程模型在分子动力学中的应用

为了提高分子动力学模拟在对称多处理(SMP)集群上的计算速度,在分子动力学并行方法中引入MPI+TBB的混合并行编程模型。基于该模型,在分子动力学软件LAMMPS中设计并实现混合并行算法,在节点间采用MPI及空间分解技术实施进程级并行,节点内采用TBB及临界区技术实施线程级并行。在SMP集群中的测试表明,该方法在体系较大以及节点数较多时可以明显减少通信时间,使加速比在纯MPI模型上提高45%。结果表明,MPI+TBB混合并行编程模型可促进分子动力学并行模拟且效率明显提升。

分形计算的并行设计及TBB实现

线程构建模块(TBB)基于模板的特点简化了并行化设计,适合高效地实现多核并行设计。针对分形计算具有计算密集和高耗时的特点,结合TBB并行化设计,以充分利用多核计算资源。对影响并行性能的计算负载不平衡问题,提出了基于采样估算的平衡优化方法,通过采样执行时间来估算工作负载,据此进行均衡的任务划分,利用TBB任务调度实现并行处理。实验结果表明,采样估算精度高,耗时比率低,能有效实现负载均衡;基于TBB的实现可获得较好加速比。

基于TBB的傅里叶变换多核并行化实现

通过对传统傅里叶变换的分析,发现其运行的瓶颈主要是循环体的运算效率低下,并且程序执行时只会被分配到一个硬件核上,并没有充分利用多核。针对上述问题,通过对英特尔线程构建模块(TBB)的研究与应用,使得循环体内的运算被划分为各个相互独立的空间,并把这些空间的运算尽可能分配到多核上,实现了对传统傅里叶变换的并行化改造,并取得较好的效果。

TBB多核编程及其混合编程模型的研究

多核处理器越来越普及,如何通过软件技术最大提升CPU每个核心的使用率,成为热点问题。引入多核并行编程模型Threading Building Blocks,并与raw threads、Open MP进行各方面详细比较,分析了其优劣。并研究了TBB结合MPI在SMP集群系统上实现高效的混合并行计算应用的方法。最终发现TBB在多核编程方面有显著的优势。TTB和MPI的结合,又为多核处理器结点集群提供了并行层次化结构,大大优化集群的性能。

基于TBB的并行Canny算法

在诸多图像边缘检测的算法中,Canny算法具有边缘检测性能良好、不易受噪声的影响、可以在噪声和边缘检测间获得很好的平衡等优点,不足之处是计算量大、实时性差。针对Canny算法存在的计算量大和实时性差等问题,提出了一种并行实现策略,即基于Threading Building Block(TBB)工具和C++语言的并行Canny算法,可以有效的缓解上述问题。通过串、并行算法执行时间的比较,证明了并行算法的优越性。

基于TBB的二维DCT并行化设计

线程构造块(TBB)能简化并行化设计,支持高效地实现多核并行功能。给出面向多核计算的二维DCT的并行化方法,并利用TBB平台实现;针对高耗时的余弦计算,利用查表和分块计算措施进行优化,并探讨粒度设置方法。在多核环境中的实验结果表明,优化后的并行化方法能有效改善执行性能,获得较好的加速比,且具备可扩展性。

三层并行遗传算法及装箱问题中的应用

提出了一个新的基于线程构建模块(TBB)的三层并行遗传算法(TPGA)。与传统遗传算法相比,在保证了算法正确性的前提下提高了运行效率,并将遗传算法的数据编码、任务处理和数据解码分别进行并行化,提高了收敛速度。TBB是Intel提供的能够完整表现并行性的代码库。采用C++语言实现了基于TBB的TPGA和串行遗传算法(SGA),通过大量实验证明,TPGA同SGA相比,不但提高了收敛速度,而且能够取得一致的最优解。

基于Parallel studio的视频编解码并行化优化

随着计算机技术的不断发展,人们对多媒体技术的实时性有了更高的要求,特别是视频编解码的时间效率。另外,随着多核CPU及相关技术的不断普及,使得原有非并行化程序的性能的不足显现了出来,因此对传统程序的并行化迫在眉睫。本文以目前较流行的视频编解码算法h.263为例,通过一个具体的视频会议系统,分析传统串行编解码算法的性能,通过英特尔Parallel studio并行化分析工具,找到算法的运行瓶颈,然后用英特尔线程构建模块对编解码算法进行并行化优化,取得了良好的效果。

Mean Shift图像分割算法的并行化

图像分割作为高性能并行计算的一个主要应用领域,其算法本身的时间复杂度和实时性需求要求不断改进计算机硬件技术和并行处理的算法。Mean Shift算法是图像分割领域一个比较经典的算法,在图像分割过程中,不需要任何先验知识,是一种无监督的分割过程,在图像分割的具体实现中应用广泛。利用TBB(threading building block)工具和CUDA(compute unified device architecture)对Mean Shift算法进行多核和GPU(graphic processing unit)并行化改造。首先分析Mean Shift分割过程中最耗时的部分Mean Shift聚类,然后利用TBB和CUDA对Mean Shift聚类进行了并行化改造,并对两种并行方法进行了对比分析。实验结果表明,两种并行方法都取得了较好的加速效果,加速比都随着图像增大和带宽参数的增加而增大,基于TBB的加速比稳定趋于核数。