留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于PMVS算法的大规模数据细粒度并行优化方法

刘金硕 李扬眉 江庄毅 邓娟 眭海刚 PANJeff

刘金硕, 李扬眉, 江庄毅, 邓娟, 眭海刚, PANJeff. 基于PMVS算法的大规模数据细粒度并行优化方法[J]. 武汉大学学报 ● 信息科学版, 2019, 44(4): 608-616. doi: 10.13203/j.whugis20160186
引用本文: 刘金硕, 李扬眉, 江庄毅, 邓娟, 眭海刚, PANJeff. 基于PMVS算法的大规模数据细粒度并行优化方法[J]. 武汉大学学报 ● 信息科学版, 2019, 44(4): 608-616. doi: 10.13203/j.whugis20160186
LIU Jinshuo, LI Yangmei, JIANG Zhuangyi, DENG Juan, SUI Haigang, PAN Jeff. Fine-Grained Parallel Optimization of Large-Scale Data for PMVS Algorithm[J]. Geomatics and Information Science of Wuhan University, 2019, 44(4): 608-616. doi: 10.13203/j.whugis20160186
Citation: LIU Jinshuo, LI Yangmei, JIANG Zhuangyi, DENG Juan, SUI Haigang, PAN Jeff. Fine-Grained Parallel Optimization of Large-Scale Data for PMVS Algorithm[J]. Geomatics and Information Science of Wuhan University, 2019, 44(4): 608-616. doi: 10.13203/j.whugis20160186

基于PMVS算法的大规模数据细粒度并行优化方法

doi: 10.13203/j.whugis20160186
基金项目: 

国家自然科学基金 61672393

国家自然科学基金 U1536204

详细信息
    作者简介:

    刘金硕, 博士, 副教授, 主要从事高性能计算和图像分析研究。liujinshuo@whu.edu.cn

    通讯作者: 邓娟, 博士, 副教授。dengjuan@whu.edu.cn
  • 中图分类号: TP391

Fine-Grained Parallel Optimization of Large-Scale Data for PMVS Algorithm

Funds: 

The National Natural Science Foundation of China 61672393

The National Natural Science Foundation of China U1536204

More Information
    Author Bio:

    LIU Jinshuo, PhD, associate professor, specializes in high performance computing and image analysis. E-mail: liujinshuo@whu.edu.cn

    Corresponding author: DENG Juan, PhD, associate professor. E-mail:dengjuan@whu.edu.cn
  • 摘要: 三维多视角立体视觉算法(patch-based multi-view stereo,PMVS)以其良好的三维重建效果广泛应用于数字城市等领域,但用于大规模计算时算法的执行效率低下。针对此,提出了一种细粒度并行优化方法,从任务划分和负载均衡、主系统存储和GPU存储、通信开销等3方面加以优化;同时,设计了基于面片的PMVS算法特征提取的GPU和多线程并行改造方法,实现了CPUs_GPUs多粒度协同并行。实验结果表明,基于CPU多线程策略能实现4倍加速比,基于统一计算设备架构(compute unified device architecture,CUDA)并行策略能实现最高34倍加速比,而提出的策略在CUDA并行策略的基础上实现了30%的性能提升,可以用于其他领域大数据处理中快速调度计算资源。
  • 图  1  CUDA存储器模型

    Figure  1.  CUDA Memory Model

    图  2  CPUs_GPUs异构并行程序执行时间

    Figure  2.  Execution Time of CPUs_GPUs Parallel Program

    图  3  CPUs_GPUs协同并行优化策略示意图

    Figure  3.  CPUs_GPUs Collaborative Parallel Optimization Strategy

    图  4  内存池模型

    Figure  4.  Memory Pool Model

    图  5  顺序方式

    Figure  5.  Sequential Mode

    图  6  流水线方式

    Figure  6.  Pipelining Mode

    图  7  Harris特征提取CUDA加速优化流程

    Figure  7.  Harris Feature Extraction on GPU

    图  8  DOG特征提取CUDA加速优化流程

    Figure  8.  DOG Feature Extraction on GPU

    图  9  CPU多线程的特征提取时间

    Figure  9.  Feature Extraction Time on the Multi-threading CPU

    图  10  CPUs_GPUs协同计算策略下的特征提取时间

    Figure  10.  Feature Extraction Time Under the CPUs_GPUs Collaborative Computing Strategy

    图  11  不同分辨率下特征提取时间

    Figure  11.  Feature Extraction Time Under Different Resolution

    表  1  CPU和GPU上特征提取时间

    Table  1.   Feature Extraction Time on CPU and GPU

    图像分辨率/像素 CPU计算时间/s GPU计算时间/s 加速比
    320×240 3.924 0.428 9.168
    640×480 15.538 1.064 14.603
    2 040×1 491 142.845 5.086 28.086
    4 081×2 993 559.230 16.473 33.948
    8 162×5 986 2 235.313 73.149 30.558
    下载: 导出CSV
  • [1] 于明, 齐菲菲, 于洋, 等.基于立体视觉的三维重建算法[J].计算机工程与设计, 2013, 34(2):730-733 doi:  10.3969/j.issn.1000-7024.2013.02.066

    Yu Ming, Qi Feifei, Yu Yang, et al. 3D Reconstruction Algorithm Based on Multi-view Stereo[J]. Computer Engineering and Design, 2013, 34(2):730-733 doi:  10.3969/j.issn.1000-7024.2013.02.066
    [2] 刘金硕, 江庄毅, 徐亚渤, 等. PMVS算法的CPU多线程和GPU两级粒度并行策略[J].计算机科学, 2017, 44(2):296-301 http://d.old.wanfangdata.com.cn/Periodical/jsjkx201702050

    Liu Jinshuo, Jiang Zhuangyi, Xu Yabo, et al. Multithread and GPU Parallel Schema on Patch-Based Multi-view Stereo Algorithm[J]. Computer Science, 2017, 44(2):296-301 http://d.old.wanfangdata.com.cn/Periodical/jsjkx201702050
    [3] 肖汉, 周清累, 张祖勋.基于多GPU的Harris角点检测并行算法[J].武汉大学学报·信息科学版, 2012, 37(7):876-881 http://ch.whu.edu.cn/CN/abstract/abstract274.shtml

    Xiao Han, Zhou Qinglei, Zhang Zuxun. Parallel Algorithm of Harris Corner Detection Based on Multi-GPU[J]. Geomatics and Information Science of Wuhan University, 2012, 37(7):876-881 http://ch.whu.edu.cn/CN/abstract/abstract274.shtml
    [4] Zhang H, Xie Y, Heng P A. Accelerating Feature Extraction for Patch-based Multi-view Stereo Algorithm[C]. International Conference on Computer Design and Applications, Qinhuangdao, China, 2010
    [5] 肖汉.基于CPU+GPU的影像匹配高效能异构并行计算研究[D].武汉: 武汉大学, 2011 http://cdmd.cnki.com.cn/Article/CDMD-10486-1011404306.htm

    Xiao Han. Research on High Efficiency Heterogeneous Parallel Computing Based on CPU+GPU in Image Matching[D]. Wuhan: Wuhan University, 2011 http://cdmd.cnki.com.cn/Article/CDMD-10486-1011404306.htm
    [6] 刘金硕, 程力, 王丽娜, 等.利用CUDA的剪切波数据三维可视化[J].武汉大学学报·信息科学版, 2013, 38(11):1271-1275 http://ch.whu.edu.cn/CN/abstract/abstract2791.shtml

    Liu Jinshuo, Cheng Li, Wang Lina, et al. 3D Visua-lization of Shear Wave Data Based on CUDA[J]. Geomatics and Information Science of Wuhan University, 2013, 38(11):1271-1275 http://ch.whu.edu.cn/CN/abstract/abstract2791.shtml
    [7] 刘金硕, 邓娟, 周峥, 等.基于CUDA设计[M].北京:科学出版社, 2014:31-32, 92-94

    Liu Jinshuo, Deng Juan, Zhou Zheng, et al. Parallel Programming Based on CUDA[M]. Beijing:Science Press, 2014:31-32, 92-94
    [8] Romerolaorden D, Villazonterrazas J, Martinez-graullera O, et al. Analysis of Parallel Computing Strategies to Accelerate Ultrasound Imaging Processes[J]. IEEE Transactions on Parallel and Distributed Systems, 2016, 27:3429-3440 doi:  10.1109/TPDS.2016.2544312
    [9] 方旭东.面向大规模科学计算的CPU-GPU异构并行技术研究[D].长沙: 国防科学技术大学, 2009 http://cdmd.cnki.com.cn/Article/CDMD-90002-2010165682.htm

    Fang Xudong. Research on CPU-GPU Heteroge-neous Parallel Technology for Large-Scale Scientific Computing[D]. Changsha: National University of Defense Technology, 2009 http://cdmd.cnki.com.cn/Article/CDMD-90002-2010165682.htm
    [10] Ilic A, Sousa L. Collaborative Execution Environment for Heterogeneous Parallel Systems[C]. IEEE International Symposium on Parallel and Distributed Processing, Workshops and Phd Forum, Atlanta, USA, 2010
    [11] Lee J, Samadi M, Park Y, et al. Transparent CPU-GPU Collaboration for Data-Parallel Kernels on Heterogeneous Systems[C]. The 22nd International Conference on Parallel Architectures and Compilation Techniques, Edinburgh, UK, 2013
    [12] Ohshima S, Kise K, Katagiri T, et al. Parallel Processing of Matrix Multiplication in a CPU and GPU Heterogeneous Environment[C]. The 7th International Meeting on High Performance Computing for Computational Science, Rio de Janeiro, Brazil, 2006
    [13] 裴颂文, 宁静, 张俊格. CPU-GPU异构多核系统的动态任务调度算法[J].计算机应用研究, 2016, 33(11):3315-3319 doi:  10.3969/j.issn.1001-3695.2016.11.026

    Pei Songwen, Ning Jing, Zhang Junge. Dynamic Task Scheduling Algorithm Based on CPU-GPU Heterogeneous Multi-core System[J]. Application Research of Computers, 2016, 33(11):3315-3319 doi:  10.3969/j.issn.1001-3695.2016.11.026
    [14] Heldens S, Varbanescu A L, Iosup A. Dynamic Load Balancing for High-Performance Praph Processing on Hybrid CPU-GPU Platforms[C]. The 6th Workshop on Irregular Applications: Architectures and Algorithms, Salt Lake City, USA, 2016
    [15] Yaseen A, Ji H, Li Y H. A Load-Balancing Workload Distribution Scheme for Three-Body Interaction Computation on Graphics Processing Units(GPU)[J]. Journal of Parallel and Distributed Computing, 2016, 87:91-101 doi:  10.1016/j.jpdc.2015.10.003
    [16] Wan L J, Li K L, Liu J, et al. Efficient CPU-GPU Cooperative Computing for Solving the Subset-Sum Problem[J]. Concurrency and Computation Practice and Experience, 2016, 28(2):492-516 doi:  10.1002/cpe.v28.2
    [17] Yu C D, Wang W. Performance Models and Workload Distribution Algorithms for Optimizing a Hybrid CPU-GPU Multifrontal Solver[J]. Compututers and Mathematics with Applicatons, 2014, 67(7):1421-1437 doi:  10.1016/j.camwa.2014.01.013
    [18] Shehab E, Algergawy A, Sarhan A. Accelerating Relational Database Operations Using Both CPU and GPU Co-processor[J]. Computers and Electrical Engineering, 2017, 57:69-80 doi:  10.1016/j.compeleceng.2016.12.014
    [19] Chan L M, Srinivasan R. A Hybrid CPU-Graphics Processing Unit(GPU) Approach for Computationally Efficient Simulation-Optimization[J]. Computers and Chemical Engineering, 2016, 87:49-62 doi:  10.1016/j.compchemeng.2016.01.001
    [20] Chavez D. Parallelizing Map Projection of Raster Data on Multi-core CPU and GPU Parallel Programming Frameworks[D]. Stockholm: KTH Royal Institute of Technology, 2016
    [21] Gremse F, Hofter A, Razik L, et al. GPU-Acce-lerated Adjoint Algorithmic Differentiation[J]. Computer Physics Communications, 2016, 200:300-311 doi:  10.1016/j.cpc.2015.10.027
    [22] 刘金硕, 曾秋梅, 邹斌, 等.快速鲁棒特征算法的CUDA加速优化[J].计算机科学, 2014, 41(4):24-27 doi:  10.3969/j.issn.1002-137X.2014.04.005

    Liu Jinshuo, Zeng Qiumei, Zou Bin, et al. Speed-up Robust Feature Image Registration Algorithm Based on CUDA[J]. Computer Science, 2014, 41(4):24-27 doi:  10.3969/j.issn.1002-137X.2014.04.005
  • [1] 潘少明, 赖新果, 种衍文, 李红.  用户访问驱动的空间数据存储组织策略 . 武汉大学学报 ● 信息科学版, 2019, 44(2): 296-301, 309. doi: 10.13203/j.whugis20170019
    [2] 唐丽玉, 杨怡斐, 侯璨, 陈崇成.  利用三维体素遍历和GPU进行辐射度加速计算——以虚拟植物冠层辐射模拟为例 . 武汉大学学报 ● 信息科学版, 2018, 43(8): 1256-1263. doi: 10.13203/j.whugis20160319
    [3] 李鹏飞, 孙开敏, 李德仁, 王玮.  无人机影像应急并行处理负载均衡方法 . 武汉大学学报 ● 信息科学版, 2018, 43(2): 268-274. doi: 10.13203/j.whugis20130095
    [4] 李鹏飞, 孙开敏, 李德仁, 王玮.  无人机影像应急并行处理负载均衡方法 . 武汉大学学报 ● 信息科学版, 2018, 43(2): 268-274. doi: 10.13203/j.whugis20170022
    [5] 李鹤元, 安晓亚, 陈刚, 金澄.  一种地理信息服务动态负载均衡算法 . 武汉大学学报 ● 信息科学版, 2016, 41(11): 1524-1529. doi: 10.13203/j.whugis20140633
    [6] 李锐, 唐旭, 石小龙, 樊珈珮, 桂志鹏.  网络GIS中最佳负载均衡的分布式缓存副本策略 . 武汉大学学报 ● 信息科学版, 2015, 40(10): 1287-1293. doi: 10.13203/j.whugis20140357
    [7] 郭明强, 吴亮, 黄颖, 谢忠, 赵林.  WebGIS集群环境下Client主动式负载均衡策略 . 武汉大学学报 ● 信息科学版, 2015, 40(12): 1639-1645. doi: 10.13203/j.whugis20140069
    [8] 尹灵芝, 朱军, 王金宏, 李毅, 徐柱, 曹振宇.  GPU-CA模型下的溃坝洪水演进实时模拟与分析 . 武汉大学学报 ● 信息科学版, 2015, 40(8): 1123-1129. doi: 10.13203/j.whugis20140302
    [9] 李 鑫, 张沪寅, 吴 笛, 王 晶.  一种利用分布式遗传算法的P2P负载均衡方法 . 武汉大学学报 ● 信息科学版, 2013, 38(3): 315-318.
    [10] 郭明强, 谢忠, 黄颖.  集群并发环境下大规模矢量数据负载均衡算法 . 武汉大学学报 ● 信息科学版, 2013, 38(9): 1131-1134.
    [11] 刘金硕, 程力, 王丽娜, 郑勇.  利用CUDA的剪切波数据三维可视化 . 武汉大学学报 ● 信息科学版, 2013, 38(11): 1271-1275.
    [12] 朱莉, 沈未名, 李锐, 徐胜勇.  利用遗传算法的网络GIS集群服务器动态负载均衡算法 . 武汉大学学报 ● 信息科学版, 2011, 36(6): 721-725.
    [13] 娄联堂, 路玲, 高文良, 傅仲良.  利用图像薛定谔变换构造高通与低通滤波器 . 武汉大学学报 ● 信息科学版, 2010, 35(3): 339-342.
    [14] 李忠民, 喻占武, 朱莉.  基于空间数据内容的动态负载均衡方法 . 武汉大学学报 ● 信息科学版, 2009, 34(5): 622-625.
    [15] 舒万能, 郑世珏, 王雄.  一种基于线性变换遗传算法的VOD集群负载均衡方法 . 武汉大学学报 ● 信息科学版, 2006, 31(9): 839-841.
    [16] 王植, 贺赛先, 毛庆洲, 仲思东.  数字图像处理技术在钢坯在线检测系统中的应用 . 武汉大学学报 ● 信息科学版, 2005, 30(3): 269-273.
    [17] 高劲松, 关泽群.  基于遥感和GIS的选址策略研究与实现 . 武汉大学学报 ● 信息科学版, 2005, 30(9): 778-781.
    [18] 李建松.  工业物体表面三维视觉量测的关键技术研究 . 武汉大学学报 ● 信息科学版, 2001, 26(4): 337-342.
    [19] 梅安华, 王菁蕙.  应用机器视觉技术研究刀具磨损与耐用度 . 武汉大学学报 ● 信息科学版, 1993, 18(1): 86-93.
    [20] 袁宇正, 邓德祥, 陈勇.  准实时微机图像处理系统的设计与实现 . 武汉大学学报 ● 信息科学版, 1993, 18(1): 46-49.
  • 加载中
图(11) / 表(1)
计量
  • 文章访问数:  1136
  • HTML全文浏览量:  142
  • PDF下载量:  199
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-04-19
  • 刊出日期:  2019-04-05

基于PMVS算法的大规模数据细粒度并行优化方法

doi: 10.13203/j.whugis20160186
    基金项目:

    国家自然科学基金 61672393

    国家自然科学基金 U1536204

    作者简介:

    刘金硕, 博士, 副教授, 主要从事高性能计算和图像分析研究。liujinshuo@whu.edu.cn

    通讯作者: 邓娟, 博士, 副教授。dengjuan@whu.edu.cn
  • 中图分类号: TP391

摘要: 三维多视角立体视觉算法(patch-based multi-view stereo,PMVS)以其良好的三维重建效果广泛应用于数字城市等领域,但用于大规模计算时算法的执行效率低下。针对此,提出了一种细粒度并行优化方法,从任务划分和负载均衡、主系统存储和GPU存储、通信开销等3方面加以优化;同时,设计了基于面片的PMVS算法特征提取的GPU和多线程并行改造方法,实现了CPUs_GPUs多粒度协同并行。实验结果表明,基于CPU多线程策略能实现4倍加速比,基于统一计算设备架构(compute unified device architecture,CUDA)并行策略能实现最高34倍加速比,而提出的策略在CUDA并行策略的基础上实现了30%的性能提升,可以用于其他领域大数据处理中快速调度计算资源。

English Abstract

刘金硕, 李扬眉, 江庄毅, 邓娟, 眭海刚, PANJeff. 基于PMVS算法的大规模数据细粒度并行优化方法[J]. 武汉大学学报 ● 信息科学版, 2019, 44(4): 608-616. doi: 10.13203/j.whugis20160186
引用本文: 刘金硕, 李扬眉, 江庄毅, 邓娟, 眭海刚, PANJeff. 基于PMVS算法的大规模数据细粒度并行优化方法[J]. 武汉大学学报 ● 信息科学版, 2019, 44(4): 608-616. doi: 10.13203/j.whugis20160186
LIU Jinshuo, LI Yangmei, JIANG Zhuangyi, DENG Juan, SUI Haigang, PAN Jeff. Fine-Grained Parallel Optimization of Large-Scale Data for PMVS Algorithm[J]. Geomatics and Information Science of Wuhan University, 2019, 44(4): 608-616. doi: 10.13203/j.whugis20160186
Citation: LIU Jinshuo, LI Yangmei, JIANG Zhuangyi, DENG Juan, SUI Haigang, PAN Jeff. Fine-Grained Parallel Optimization of Large-Scale Data for PMVS Algorithm[J]. Geomatics and Information Science of Wuhan University, 2019, 44(4): 608-616. doi: 10.13203/j.whugis20160186
  • 基于匹配点的三维重建算法[1-2]根据二维场景图像序列中提取的特征点来恢复场景的立体信息, 而Harris-DOG(Harris-difference of Guassian)特征是一种广泛使用的图像特征。三维多视角立体视觉算法(patch-based multi-view ste- reo, PMVS)是重建效果比较好的一种基于匹配点的三维重建算法。但对于PMVS算法中的序列影像特征提取而言,需要处理的影像数量较为庞大。

    目前,基于CPU多线程和多GPU异构架构[3-4]已经成为单机并行加速的主要方案。CPU_GPU异构平台主要采用主-从方式[5]运行,即CPU作为主机端,负责执行复杂逻辑运算并完成程序控制,而GPU作为协处理器,负责执行并行计算任务[6]。CPU与GPU之间通过外设部件互联标准总线连接,GPU仍然作为计算节点的外部设备,CPU和GPU之间的数据传输必须在CPU控制下显式地进行[7]。但是,GPU加速后的执行时间仍然较长,造成CPU的长时间空闲等待,浪费了多核CPU的计算能力。因此,当GPU执行计算任务时,CPU也同时执行部分任务,可以提高设备的利用率;同时采用多核多线程方式运行CPU,能够最大限度地缩短任务的执行时间[8]

    方旭东[9]提出了一种基于profiling的CPU_GPU任务划分策略, 采用曲线拟合法求取最佳任务划分。Ilic等[10]提出一种基于CPUs_GPUs异构系统的协同计算方案。Lee等[11]提出了一种透明的CPUs_GPUs协同计算架构。Ohshima等[12]提出了一种基于CPUs_GPUs异构系统的执行时间分析方法和负载均衡策略,使得任务执行时间最短。裴颂文等[13]提出了一种CPUs-GPUs异构多核系统的动态任务调度算法,动态调整分配到CPU和GPU上的数据块大小,减小负载的总执行时间, 提高了系统加速比。

    在以上研究的基础上,本文提出了一种细粒度并行优化方法,从任务划分和负载均衡、主存储和GPU存储访问、通信开销3个方面加以优化;同时针对序列影像的快速特征提取问题, 实现了Harris-DOG特征提取算法的CPUs_GPUs多粒度协同并行,来验证该方法的有效性。其中CPU采用pthreads函数库实现多线程并行, 充分发挥了多核CPU的计算能力;GPU采用统一计算设备架构(compute unified device architecture, CUDA)实现并行, 优化线程组织、存储器访问;同时多核CPU和GPU之间通过负载均衡和通信开销优化[14-17],实现CPU和GPU的协同并行。

    • CUDA是由NVIDIA公司推出的基于GPU的通用并行计算架构,采用CPU+GPU异构模式,由CPU负责执行复杂逻辑处理和事务处理,由GPU负责计算密集型的大规模数据并行计算[18]。CUDA架构提供了6种设备端存储器和两种主机端存储器,如图 1所示。共享存储器是GPU片内的可读写高速存储器,它可以被同一线程块(Block)中的所有线程(Thread)访问。全局存储器位于板载显存中,CPU、GPU都能对其进行读写访问, 它的存储容量最大,用于存储所有的计算数据。纹理存储器是只读的存储器,适合实现大数据量的非对齐访问或随机访问, 能实现比全局存储器更快的访问速度[7]

      图  1  CUDA存储器模型

      Figure 1.  CUDA Memory Model

    • 串行程序并行化主要包括CPU多核并行和GPU异构并行两种方式。通常未并行化的程序执行时间如图 2(a)所示(仅CPU处理),程序指令顺序执行,程序数据均在内存中分配和处理;而CPUs_GPUs多粒度并行的程序执行时间如图 2(b)所示(GPU和CPU共同处理),包括串行部分执行时间、数据在外存到内存之间的通信时间以及并行部分执行时间。串行部分执行时间不变,而并行部分则在GPU设备端和CPU多核心上同时执行。如图 2所示,并行部分运行时间又包含了主机端向设备端传输数据时间(H2D)以及CPUs_GPUs协同并行执行时间和设备端向主机端传输数据时间(D2H)。因此,可以采用CPUs_GPUs协同并行优化策略,其层次结构如图 3所示。

      图  2  CPUs_GPUs异构并行程序执行时间

      Figure 2.  Execution Time of CPUs_GPUs Parallel Program

      图  3  CPUs_GPUs协同并行优化策略示意图

      Figure 3.  CPUs_GPUs Collaborative Parallel Optimization Strategy

      1) 任务划分及负载均衡。根据获取的任务和CPU、GPU的单位任务计算时间,同时考虑CPU多线程开销,计算CPU和GPU间的最优任务划分并实现负载均衡。

      2) 通信开销优化。采用内存池技术减少数据从磁盘读入内存的通信时间,采用流水线技术隐藏CPU从内存读入数据的时间,以实现通信开销的优化。

      3) GPU访存优化。合理的全局存储器的合并访问策略以及合理的共享存储器、常量存储器、纹理存储器使用策略可以有效提高GPU的访存效率[19]

      4) 主存储优化。利用哈希表来标识每个数据块在内存中的位置以降低查找数据块的时间复杂度,利用更新数据块信息摘要的方式以避免多线程同时访问同一数据块造成资源冲突。

    • 根据CPU和GPU的单位任务计算时间,同时考虑多线程、存储和通信开销,得出CPU和GPU间的最优任务划分,使得任务的总计算时间最短。

      首先,设CPU、GPU单线程的单位任务计算时间分别为tCPUtGPU,CPU多线程情况下用于计算的CPU线程数为k。可以得到CPU多线程的单位任务计算时间tmt为:

      $$ {t_{{\rm{mt}}}} = \alpha \frac{{{t_{{\rm{CPU}}}}}}{k} $$ (1)

      式中,α为引入的多线程参数。实际情况中,CPU多线程存在线程开销和存储通信的限制,如果简单地把单位任务从单线程执行转换为多线程执行进行时间上的平分,会存在一定的误差,所以引入修正参数α,且规定α>1,在实际计算时, 根据经验取α=1.5。

      然后,设任务总量为s,分配给CPU多线程执行的任务量为sCPU,分配给GPU并行执行的任务量为sCPU,且s=sCPU+sCPU。则CPU多线程的任务执行总时间为αtCPUsCPU/k,GPU的任务执行总时间为sGPUtGPU,CPUs_GPUs多粒度并行优化策略的总时间由这两部分组成。当CPU多线程的任务和GPU的任务同时完成时,可以使总时间最短,由αtCPUsCPU/k = sGPUtGPUssCPUsGPU均为自然数,可得:

      $$ {s_{{\rm{CPU}}}} = \left\lfloor {\frac{{ks}}{{k + \alpha r}} + 0.5{\rm{ }}} \right\rfloor $$ (2)
      $$ {s_{{\rm{CPU}}}} = \left\lfloor {\frac{{\alpha sr}}{{k + \alpha r}} + 0.5{\rm{ }}} \right\rfloor $$ (3)

      式中,r = tCPU/tCPU;“ $ \left\lfloor {~~} \right\rfloor $ ”表示取整操作。

      最后,需要确定在CPU多核环境中开辟的线程数k。因为操作系统会将不同线程分派到不同CPU计算核心上,若线程数超过CPU核数,则造成CPU核心上下文切换的额外开销[20];同时GPU计算任务需要CPU线程负责调度,每一个GPU都需要占用一个线程。因此,设CPU核数为p,GPU核数为q,则用于计算的CPU线程数k需要满足:

      $$ 0 \le k \le {\rm{min}}\{ {s_{{\rm{CPU}}}}, p - q\} $$ (4)

      由于CPU任务数sCPUk相关,则由kmk为自然数可得:

      $$ k = {\rm{max}}\{ {\rm{min}}\left\{ {\left\lfloor {s - \alpha r} \right\rfloor , p - q} \right\}, 0\} $$ (5)

      综上所述,CPU和GPU间的最优任务划分{CPU任务数,GPU任务数,CPU线程数}为{sCPU, sCPU, k}。

    • 在CPU和GPU协同并行工作中,CPU和GPU之间的数据传输以及计算模块与存储模块的通信开销是制约性能的瓶颈[21]。程序实际的带宽越接近设备提供的理论带宽,表示带宽利用率越高,程序的性能越好。通过对通信开销进行优化,提高带宽利用率,可以提高CPU多线程和GPU协同工作的效率。

      数据从磁盘读入内存的通信时间是不可消除的,但可以通过两方面来减少通信开销方面的影响。一方面是提高硬盘的读写速度,通过硬件的提升来减少读写时间,可行的办法是采用更快速度的读写硬盘。另一方面是采用内存池技术,通过在内存中划分特定的分区,采用一定的调度策略将文件分块存入内存池当中,CPU定期从内存中的文件存放区中获取数据,从而减少数据资源在总线上传输时对CPU多线程和GPU协同工作等待资源造成的影响,达到通信开销优化的目的。本文主要讨论第二种通信开销的优化方案。内存池模型如图 4所示。

      图  4  内存池模型

      Figure 4.  Memory Pool Model

      内存池数据预取的步骤如下。

      1) 每个影像称为一个文件块,在内存池中划分出n个内存区域。文件块的总数超过n,开始阶段,每个文件块被分为若干个大小固定的子文件块。

      2) 硬盘与内存池之间初始化n个通道,文件访问程序从硬盘中预读入部分文件块加入内存池,文件小块在内存池中进行缓存。

      3) 在内存池中,每个通道接口设置一个标记为Pi,每个文件块设置一个计数器。当文件小块加入内存池时,计数器数目会加1,计数器计数达到文件块大小的时候,文件块会被转入数据存放区,等待处理程序获取。

      4) Pi标记为可覆盖,计数器被置0,内存池中的通道接口接收新的数据块的存放。

      此外,CPU从内存读入影像执行的通信时间可以通过流水线技术加以隐藏。CPU读入影像通过总线访问内存,而CPU对影像进行预处理和特征提取时,总线空闲,把这一部分时间也用来访存读入影像,使读入影像、预处理、特征提取在时间上重叠起来,当处理的序列影像数量庞大时,将大幅度减少总的处理时间。图 5为顺序方式执行的示意图,图 6为流水线方式执行的示意图。

      图  5  顺序方式

      Figure 5.  Sequential Mode

      图  6  流水线方式

      Figure 6.  Pipelining Mode

      设读入影像、预处理、特征提取3个阶段的处理时间分别为t1t2t3,处理n幅影像的顺序执行方式总的执行时间为T1,采用流水线技术重叠各个阶段总的执行时间为T2,则有:

      $$ {T_1} = n\left( {{t_1} + {t_2} + {t_3}} \right) $$ (6)
      $$ \begin{array}{l} {T_2} = {t_1} + {t_2} + \left( {n - 2} \right){\rm{max}}\left\{ {{t_1}, {t_2}, {t_3}} \right\} + \\ {\rm{max}}\{ {t_1}, {t_2}\} + {\rm{max}}\{ {t_2}, {t_3}\} \end{array} $$ (7)

      当图像足够多,即n足够大时,

      $$ {T_2} \approx \left( {n - 2} \right){\rm{max}}\left\{ {{t_1}, {t_2}, {t_3}} \right\} \le {T_1} $$ (8)
    • 设备端存储器的带宽利用率是CUDA程序的性能瓶颈之一,也是制约程序性能提升的最大因素。设备端存储器访问优化的方法如下:全局存储器的合并访问优化;共享存储器的充分使用和存储器冲突优化;使用常量存储器和纹理存储器加速。合理的全局存储器的合并访问策略可以提高GPU的访存效率。首先,每个线程块的每次内存访问都保证块内线程按线程号tid顺序访问连续的内存单元;其次,为避免多个线程块之间出现的访存冲突,根据线程块号bid进行访问。假设数据总量为M,线程块数为N,线程块号为bid,则该线程块访存的起始偏移量为(M/N) bid。程序的函数局部变量应尽可能放入共享存储器中,充分利用共享存储器的访问速度快的特点。而常量存储器和纹理存储器则应对经常使用的只读数据进行存储。

    • CPU对内存中大块影像数据的访问会消耗执行的时间,需要采取相应的策略来优化CPU的存储访问。大块影像数据分割后通过信息摘要来标识每一个小块数据对象,通过哈希表来标识每个数据块在内存中的位置。大块影像数据信息摘要内容包括名称、类型、大小、信息摘要算法5(message digest algorithm 5,MD5)校验码。分割数据块完成之后,生成每个小块数据的分块信息,并将小块数据的其他信息一同写到信息摘要当中。小块数据对象的信息包含对象大小、哈希表中的键以及下一个分块主键。

      哈希表中保存了分块数据的主键,值为数据在内存中的地址信息。当数据块传输到内存池中时,更新哈希表的信息,数据块之间通过设置的SegMentObjectNext操作建立关联,形成数据块的逻辑组织形式,类似于单向链表结构。根据信息摘要,查找数据块的主键,然后保存数据块地址信息。当查看信息摘要中下一数据块的主键为null时,说明大块数据图像文件已经全部加载到内存中。在数据块加载到内存的过程中,影像数据处理程序从内存中读取文件块进行处理。读取步骤如下。

      1) 根据影像名称,访问数据块信息摘要。

      2) 根据数据块信息摘要,获得数据块主键。

      3) 根据主键获得数据块地址,然后定位到数据块。

      设在内存池中存放m幅影像,每幅影像包含n个影像块,那么查找影像块的最坏时间复杂度为O(mn);采用了数据块信息摘要以后,查找影像块最坏时间复杂度为O(m+n),大大降低了哈希表的查找时间开销。

      多线程对内存中的数据进行访问时需要考虑资源竞争的问题,本文采取更新信息摘要的方式来解决。对图像数据块的操作主要涉及读操作,很少涉及写操作。在读取时对数据块加读锁,当线程读取了大图像中的小数据之后,需要更新小块数据中的摘要信息,标记是否已读取标记为1(已读)。当其他线程访问这个小块数据时,如果查阅到标记为1,则访问下一块数据,从而避免多个线程对同一块数据的操作。

    • 针对序列影像Harris-DOG特征提取问题,采用两级并行优化策略,利用GPU并行进行第一级加速,再利用CPUs_GPUs协同并行策略均衡CPU和GPU负载进行第二级优化,对存储访问以及通信进行第三级优化。首先按照任务划分策略,将任务按影像为单位进行划分,并相应地调度到CPU和GPU上,CPU任务采用多核多线程方式处理,GPU任务采用CUDA并行方式处理。

      CUDA并行程序分为主机端代码和设备端代码, 主机端负责逻辑运算和GPU设备管理, 设备端则负责并行计算。Harris-DOG算子特征提取算法针对同样的原始图像输入,分别运用Harris算子和DOG算子进行特征点提取,然后合并两种特征点集合,以获得理想的特征点集。因此特征点提取过程中只需要一次图像读入显存操作,而特征点集合构建和合并则由CPU计算。

    • 在GPU上实现Harris特征点提取时,将原始图像从主机端上传至GPU显存中,GPU线程采用条带状划分,即所有的线程以一维方式组织,不同线程对应图像同一像素行的不同像素列, 每个Block设置256个线程。计算过程中,按像素行进行计算,由于Block的设置, 图像又以256个像素列分为多个部分, 每个部分之间有若干像素列相互重叠,以保证最终结果的正确性。基于GPU加速的Harris特征点提取流程如图 7所示。首先读入原始图像I存放于内存中,并初始化邻域窗口大小等参数,一并上传到GPU端[22],然后在GPU端分别计算图像在水平方向和竖直方向上的一阶导数以及自相关矩阵M;接着计算每个像素点的Harris响应值H,并且将计算结果回传到CPU端; 最后为了保证特征点的均匀覆盖,用32×32像素的网格将图像进行分割,在每个网格中提取出响应值H最大的4个像素点作为特征点。

      图  7  Harris特征提取CUDA加速优化流程

      Figure 7.  Harris Feature Extraction on GPU

    • 在GPU上实现DOG特征点提取时,线程按照一维条带方式划分,每个Block处理256个像素列,每个Block之间有部分列相互重叠。基于GPU加速的DOG特征点提取流程如图 8所示。首先读取GPU显存中图像数据;然后由CPU端一次性生成所有n个不同尺度下的高斯滤波模板,由于计算时需要反复使用到滤波模板,因此将其绑定到GPU端常量存储器中,以提高访存速度;接着在GPU端对所有尺度图像进行高斯滤波,并将生成的图像金字塔存储在全局存储器中,避免CPU和GPU间反复交换数据,以减少I/O等待时间,并计算相邻尺度的高斯差分D;下一步采用非极大值抑制(non-maximum suppression, NMS)法求取局部极值点,每个GPU线程处理一个像素点,先将该像素点与同一尺度下的8个邻近像素比较差分值D,若是极大(小)值,则再将该像素点与相邻尺度的各9个像素点进行比较,得到3个尺度下的局部极值点,作为候选特征点;最后在CPU端计算每个32×32像素网格中差分值D最大的4个点作为特征点。

      图  8  DOG特征提取CUDA加速优化流程

      Figure 8.  DOG Feature Extraction on GPU

    • 使用多核CPU上的多线程技术能够实现CPU多核心的并行计算,通过操作系统提供的支持来调度CPU的多个核心。默认情况下,不同线程会被调度到不同核心上执行,并满足负载均衡要求。常用的CPU多线程方式有系统多线程应用程序编程接口(application programming interface, API)、跨平台线程库、开源并行编程(open multi-processing, openMP)等,本文采用pthreads跨平台线程库来实现算法的多线程并行。

      CPUs_GPUs协同执行流程为:首先程序创建主线程,根据已有参数计算CPUs_GPUs任务划分。假定CPU拥有n个核心,则启动n个线程,其中一个线程负责调度GPU, 其余n-1个线程负责CPU的计算任务,每个线程一次处理一幅影像,直至完成相应数量的任务。所有计算任务完成之后,主线程收回控制权直至退出。CPUs_GPUs计算任务划分步骤根据CPU核心数量设置相应的线程数。在CPUs_GPUs协同优化过程中,还需要考虑其他因素对时间的影响进行综合优化,主要包括存储的访问优化、通信开销的优化以及负载均衡的优化。

    • 为了找到最高效的序列影像特征提取方案,并且验证CPUs_GPUs策略的有效性,在CPU为Intel Core i5-3470@3.2 GHz,内存为4 GB,显卡为NVIDIA TESLA C2075,显存6 GB的环境下进行了实验。为了减少误差和偶然因素对实验的影响,重复10次测试了36幅序列影像在不同分辨率下的特征提取时间,图 9表 1中的数据为10次实验的平均值。在测试平台上对仅采用CPU多线程、仅采用CUDA并行优化和采用CPUs_GPUs协同优化的3种不同策略进行了比较。

      图  9  CPU多线程的特征提取时间

      Figure 9.  Feature Extraction Time on the Multi-threading CPU

      表 1  CPU和GPU上特征提取时间

      Table 1.  Feature Extraction Time on CPU and GPU

      图像分辨率/像素 CPU计算时间/s GPU计算时间/s 加速比
      320×240 3.924 0.428 9.168
      640×480 15.538 1.064 14.603
      2 040×1 491 142.845 5.086 28.086
      4 081×2 993 559.230 16.473 33.948
      8 162×5 986 2 235.313 73.149 30.558

      采用CPU多线程策略时,对给定的36幅分辨率为320×240的同一场景图像进行Harris-DOG特征提取。如图 9所示,单线程特征提取时间为139.448 s,多线程最短时间为34.507 s,加速比达到4.04倍。当线程数为1~4时,每个线程分别进行36、18、12、9幅影像的计算,由操作系统将线程调度到对应数目的CPU核心上执行。随着线程数的增加,计算时间迅速减少,并与线程数成反比,加速比即为线程数;当线程数大于4时,由于CPU核心数的限制,无论创建多少个线程,每个CPU核心均完成9幅影像的计算,CPU处于满载状态,不再有进一步的性能提升,同时还会带来线程创建和调度的额外开销。基于CPU多线程的策略在线程数小于或等于CPU核心数时,有明显的加速效果,当线程数大于CPU核心数时,则无法进一步加速, 最大加速比为CPU核心数。

      采用CUDA并行加速策略时,分别对5组不同分辨率下的单幅影像进行特征提取, 并比较串行和并行程序的计算时间,如表 1所示。从表 1可知,经过CUDA优化的特征提取时间有了明显缩短, 加速比达到9~34倍,并且加速比随着图像分辨率的增大而增大。而当图像分辨率达到4 000×3 000左右时,如果再增大图像分辨率,加速比也不会继续增加,而是在30倍左右波动。

      采用CPUs_GPUs协同调度策略时,针对36幅同一场景图像, 测量了分辨率为320×240像素和640×480像素的特征提取时间,并对理论计算的最佳任务分配进行实证。当图像分辨率为320×240像素时,在CPU任务数为0~18情况下的CPU单线程和三线程特征提取时间曲线如图 10所示。当负责计算CPU任务的线程数为3时,在CPU任务数为0~18情况下,图像分辨率为320×240像素和640×480像素的特征提取时间曲线如图 11所示。

      图  10  CPUs_GPUs协同计算策略下的特征提取时间

      Figure 10.  Feature Extraction Time Under the CPUs_GPUs Collaborative Computing Strategy

      图  11  不同分辨率下特征提取时间

      Figure 11.  Feature Extraction Time Under Different Resolution

      图 10中的曲线表明,当CPU任务数为0时,所有任务交由GPU处理,即§3.1和§3.2所讨论的CUDA并行优化策略,特征提取时间为15.022 s。随着CPU任务数的增加,计算总时间先小幅下降,然后快速上升,即在GPU基础上加入CPU进行协同计算能够带来一定程度的性能提升,随后由于GPU任务数的减少,GPU并行加速效果逐渐减弱,此时计算时间主要由CPU性能决定。CPU单线程协同计算在CPU任务数为3时计算时间最短,最短时间为12.777 s,而CPU三线程协同计算则在CPU任务数为6时计算时间最短, 最短时间为11.435 s,可以看出基于CPU多线程和GPU的协同计算能更充分使用处理器资源,达到更好的加速效果。

      表 1可知,分辨率为320×240像素的图像序列的加速比为9.168,单线程情况下根据§3.1可知,CPUs_GPUs任务划分应为{3, 33, 1},计算时间为12.777 s,与单线程曲线吻合。而三线程情况下根据式(2)计算,CPU核数c=4时,CPUs_GPUs任务划分应为{6, 30, 3},计算时间为11.435 s,与三线程曲线吻合。相较于CUDA异构并行策略9.168倍的加速比,基于CPUs_GPUs协同计算的优化策略达到了12.195倍的加速比, 性能提升33%。而图 11中的曲线表明,根据§2.1以及表 1中的数据可知,图像分辨率为640×480像素时,CPUs_GPUs任务划分应为{4, 32, 3},计算时间为29.765 s,与图 11中曲线相吻合, 加速比达到18.623倍, 性能提升27%。

      因此,序列影像Harris-DOG特征提取两级并行优化算法能在GPU加速的基础上实现30%左右的性能提升,取得明显的加速效果,并且证明了本文提出的CPUs_GPUs协同调度策略的有效性。

    • 本文提出了CPUs _GPUs多粒度并行策略,并进行数学描述和推导,同时针对序列影像Harris-DOG特征快速提取问题进行实验验证。通过与CPU多线程策略和CUDA并行优化策略的比较,分析各自的性能提升效果,实验证实CPUs_GPUs协同计算策略的加速效果优于其他两种策略,取得明显的加速效果。但目前该策略仍存在不足,CPUs_GPUs协同计算策略的效果由CUDA并行加速比决定,同时多线程修正参数α依据经验来确定,制约了该协同计算策略的使用。因此,下一步工作将研究CPUs_GPUs协同计算策略中多线程修正参数α与线程开销和存储器特性的关系,提高该协同优化策略的精确性和通用性。

参考文献 (22)

目录

    /

    返回文章
    返回