基于SIMD的并行傅里叶空间图像相似度计算

doi:10.19678/j.issn.1000-3428.0059427

计算机工程 ›› 2021, Vol. 47 ›› Issue (11): 247-253. doi: 10.19678/j.issn.1000-3428.0059427

基于SIMD的并行傅里叶空间图像相似度计算

郭渝洛, 边浩东, 董润婷, 唐嘉豪, 王晓英, 黄建强

青海大学计算机技术与应用系, 西宁 810016

收稿日期:2020-09-03 修回日期:2020-10-31 发布日期:2020-11-12
作者简介:郭渝洛(1999-),女,本科生,主研方向为高性能计算;边浩东、董润婷,硕士研究生;唐嘉豪,本科生;王晓英,教授;黄建强(通信作者),副教授。
基金资助:
国家自然科学基金“基于GPU异构体系结构的大规模图数据挖掘关键技术研究”（62062059）；国家自然科学基金“智能电网影响感知的数据中心需求响应策略与机制研究”（61767024）；青海省科技计划项目“GRAPES数值天气预报模式动力框架并行并行算法与优化技术研究”（2019-ZJ-7034）；国家重点实验室开放基金“基于三江源数据分析平台的全球数值天气预报系统的性能优化技术研究”（2020-ZZ-03）。

Parallel Fourier Space Image Similarity Calculation Based on SIMD

GUO Yuluo, BIAN Haodong, DONG Runting, TANG Jiahao, WANG Xiaoying, HUANG Jianqiang

Department of Computer Technology and Application, Qinghai University, Xining 810016, China

Received:2020-09-03 Revised:2020-10-31 Published:2020-11-12

摘要/Abstract

摘要： 在冷冻电镜三维重建计算模型中，傅里叶空间图像相似度算法被频繁调用，大量的计算开销导致模型整体运行速度变慢。针对该问题，提出一种基于SIMD的并行傅里叶空间图像相似度算法。通过手动负载均衡方式最大化CPU的线程使用率，添加AVX-512指令集增强CPU矢量寄存器的作用，同时设计高效的数据结构提升内存访问效率。在Intel Xeon Platinum 9242平台上的实验结果表明，与原始的OpenMP并行模型相比，经该算法优化后的程序可获得平均5.132倍的加速比，并且具有较强的鲁棒性。

关键词: 冷冻电镜, 负载均衡, 缓存, 单指令多数据流矢量化, 傅里叶空间, 图像相似度计算, 并行计算

Abstract: The existing models for calculation of three-dimensional cryo-Electron Microscope(cryo-EM) reconstruction frequently call the Fourier space-based image similarity algorithm,and the generated high computational overhead slows the running speed of the model.To solve this problem,a parallel image similarity algorithm using Fourier space is proposed based on Single Instruction Multiple Data(SIMD).By maximizing CPU thread utilization through manual load balancing,an AVX-512 instruction set is added to enhance the role of CPU vector register.Then an efficient data structure is designed to improve memory access efficiency.The experimental results on Intel Xeon Platinum 9242 platform show that compared with the original OpenMP parallel model,the optimized program can obtain an average speedup of 5.132 times and exhibits high robustness.

Key words: cryo-Electron Microscopy(cryo-EM), load balancing, cache, Single Instruction Multiple Data(SIMD) vectorization, Fourier space, image similarity calculation, parallel computing

中图分类号:

TP391

郭渝洛, 边浩东, 董润婷, 唐嘉豪, 王晓英, 黄建强. 基于SIMD的并行傅里叶空间图像相似度计算[J]. 计算机工程, 2021, 47(11): 247-253.

GUO Yuluo, BIAN Haodong, DONG Runting, TANG Jiahao, WANG Xiaoying, HUANG Jianqiang. Parallel Fourier Space Image Similarity Calculation Based on SIMD[J]. Computer Engineering, 2021, 47(11): 247-253.

http://www.ecice06.com/CN/Y2021/V47/I11/247

图/表 10

20211113145247

20211113145249

20211113145252

20211113145255

20211113145258

20211113145303

20211113145307

20211113145310

20211113145313

20211113145315

参考文献

[1] CHENG Y,GRIGORIEFF N,PENCZEK P,et al.A primer to single-particle cryo-electron microscopy[J].Cell,2015,161(3):438-449.
[2] KUHLBRANDT W.The resolution revolution[J].Science,2014,343(6178):1443-1444.
[3] NOGALES E.The development of cryo-EM into a mainstream structural biology technique[J].Nature Methods,2016,13(1):24-27.
[4] TAN G,GUO Z,CHEN M,et al.Single-particle 3d reconstruction from cryo-electron microscopy images on GPU[C]//Proceedings of the 23rd International Conference.New York,USA:ACM Press,2009:380-389.
[5] WANG K P,XU S Z,FU H H,et al.Parallelizing cryo-EM 3D reconstruction on GPU cluster with a partitioned and streamed model[C]//Proceedings of 2019 ACM International Conference on Supercomputing.New York,USA:ACM Press,2019:13-23.
[6] LI L,LI X,TAN G,et al.Experience of parallelizing cryo-EM 3D reconstruction on a CPU-GPU heterogeneous system[C]//Proceedings of the 20th International Symposium on High Performance Distributed Computing.New York,USA:ACM Press,2011:195-204.
[7] EL-MAHDY A,EL-SHISHINY H.An efficient load-balancing algorithm for image processing applications on multicore processors[C]//Proceedings of the 1st International Forum on Next-generation Multicore/Manycore Technologies.New York,USA:ACM Press,2008:1-5.
[8] BARKER K J,CHRISOCHOIDES N P.An evaluation of a framework for the dynamic load balancing of highly adaptive and irregular parallel applications[C]//Proceedings of 2003 ACM/IEEE Conference on Supercomputing.Washington D.C.,USA:IEEE Press,2003:45.
[9] FALCO I,LASKOWSKI E,OLEJNIK R,et al.Multi-objective parallel extremal optimization in processor load balancing for distributed programs[C]//Proceedings of Genetic and Evolutionary Computation Conference Companion.New York,USA:ACM Press,2017:1796-1803.
[10] BOETTCHER M,AL-HASHIMI B M,EYOLE M,et al.Advanced SIMD:extending the reach of contemporary SIMD architectures[C]//Proceedings of 2014 Design,Automation and Test in Europe Conference and Exhibition.Leuven,Belgium:European Design and Automation Association,2014:1-4.
[11] 王晶,张云泉,梁军.基于ARM V8平台的向量算法库实现与优化[J].计算机工程,2019,45(6):82-88. WANG J,ZHANG Y Q,LIANG J.Vector algorithm library implementation and optimization based on ARM V8 platform[J].Computer Engineering,2019,45(6):82-88.(in Chinese)
[12] XIE B W,ZHAN J F,LIU X,et al.CVR:efficient vectorization of SpMV on X86 processors[C]//Proceedings of 2018 International Symposium on Code Generation and Optimization.New York,USA:ACM Press,2018:149-162.
[13] 郭晨,郑烇,丁尧,等.基于动态流行度与请求代价的命名数据网络缓存策略[J].计算机工程,2018,44(2):46-50. GUO C,ZHENG Q,DING Y,et al.Cache strategy based on dynamic popularity and request cost in named data networking[J].Computer Engineering,2018,44(2):46-50.(in Chinese)
[14] BRODAL G S,FAGERBERG R,JACOB R.Cache oblivious search trees via binary trees of small height[C]//Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms.New York,USA:ACM Press,2005:39-48.
[15] YOON S E,LINDSTROM P,PASCUCCI V,et al.Cache-oblivious mesh layouts[C]//Proceedings of SIGGRAPH'05.New York,USA:ACM Press,2005:886-893.
[16] ZHAO R,LIU G,SRINATH S,et al.Improving high-level synthesis with decoupled data structure optimization[C]//Proceedings of the 53th ACM/EDAC/IEEE Design Automation Conference.Washington D.C.,USA:IEEE Press,2016:1-6.
[17] ROSIER D J,KLUG A.Reconstruction of three dimensional structures from electron micrographs[J].Nature,1968,217(5124):130-134.
[18] MILNE J L S,BORGNIA M J,BARTESAGHI A,et al.Cryo-electron microscopy-a primer for the non-microscopist[J].The FEBS Journal,2013,280(1):28-45.
[19] 王宏伟.冷冻电子显微学在结构生物学研究中的现状与展望[J].中国科学,2014,44(10):1020-1028. WANG H W.Current status and prospect of cryoelectron microscopy in structural biology[J].Science China,2014,44(10):1020-1028.(in Chinese)
[20] 黄岚青,刘海广.冷冻电镜单颗粒技术的发展、现状与未来[J].物理,2017,46(2):91-99. HUANG L Q,LIU H G.Application of cryo-electron microscopy in structure biology:current status and future perspectives[J].Physics,2017,46(2):91-99.(in Chinese)
[21] FRANK J.Single-particle imaging of macromolecules by cryo-electron microscopy[J].Annual Review of Biophysics and Biomolecular Structure,2002,31(1):303-319.

选择文件类型/文献管理软件名称

选择包含的内容

基于SIMD的并行傅里叶空间图像相似度计算

Parallel Fourier Space Image Similarity Calculation Based on SIMD

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	刘向举, 赵犇, 方贤进, 徐杨洋. SDN中基于过程优化的动态负载均衡策略[J]. 计算机工程, 2023, 49(8): 137-145.
[2]	王其涵, 庞建民, 岳峰, 祝迪, 沈莉, 肖谦. 面向申威架构的KNN并行算法实现与优化[J]. 计算机工程, 2023, 49(5): 286-294.
[3]	石小容, 李爱萍, 牛保宁, 段利国, 赵菊敏. 兼顾个性化需求的云边协作两级内容缓存研究[J]. 计算机工程, 2023, 49(5): 223-230.
[4]	夏立斌, 刘晓宇, 姜晓巍, 孙功星. 基于分布式数据集的并行计算框架内存优化方法[J]. 计算机工程, 2023, 49(4): 43-51.
[5]	桑永宣, 魏江坡, 王博, 宋莹. 具有边缘缓存机制的混合启发式任务卸载算法[J]. 计算机工程, 2023, 49(4): 149-158.
[6]	杨周凡, 韩林, 李冰洋, 谢景明, 韩璞, 刘勇杰. 基于“嵩山”超级计算机系统的大规模管网仿真[J]. 计算机工程, 2022, 48(9): 155-161.
[7]	王奎宇, 宋晓勤, 缪娟娟, 张昕婷, 雷磊. 基于SDN的高性能QoS保障低轨道卫星星间路由算法[J]. 计算机工程, 2022, 48(5): 185-190,199.
[8]	杨涛, 郑烇, 徐正欢, 施钱宝, 彭思伟. 通用缓存替换策略下的缓存强一致性研究[J]. 计算机工程, 2022, 48(12): 180-188,195.
[9]	何晓斌, 高洁, 肖伟, 陈起, 刘鑫, 陈左宁. 应用透明的超算多层存储加速技术研究[J]. 计算机工程, 2022, 48(12): 1-8.
[10]	贺鹏飞, 范鹏飞, 尹千慧, 王中训, 张桐敬, 梁大伟. 基于负载均衡算法的Hyperledger Fabric共识机制研究[J]. 计算机工程, 2022, 48(11): 170-176.
[11]	李亚朋, 庞建民, 徐金龙, 聂凯. 一种针对线性循环结构的非线性静态调度策略[J]. 计算机工程, 2022, 48(1): 155-162.
[12]	施凌鹏, 朱征, 周俊松, 李鑫, 李静. 面向微服务架构的云系统负载均衡机制[J]. 计算机工程, 2021, 47(9): 44-50,58.
[13]	左攀, 束永安. DCN中基于前馈神经网络的动态多路径负载均衡方法[J]. 计算机工程, 2021, 47(9): 113-119.
[14]	黄瑞, 金光浩, 李磊, 姜文超, 宋庆增. 轻量化神经网络加速器的设计与实现[J]. 计算机工程, 2021, 47(9): 185-190,196.
[15]	易培淮, 李卫东, 林韬, 邹佳恒, 邓子艳, 刘言. GPU在缪子快速模拟中的应用[J]. 计算机工程, 2021, 47(8): 100-108.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于SIMD的并行傅里叶空间图像相似度计算

Parallel Fourier Space Image Similarity Calculation Based on SIMD

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献

相关文章 15

编辑推荐

Metrics

本文评价