(东北大学计算机科学与工程学院 沈阳 110169) (xukunhao725@163.com)
出版日期: 2021-03-01基金资助:国家重点研发计划项目(2018YFB1003404);国家自然科学基金项目(U1811261, 61672142)Parallel String Similarity Join Approach Based on CPU-GPU Heterogeneous Architecture
Xu Kunhao, Nie Tiezheng, Shen Derong, Kou Yue, Yu Ge(School of Computer Science and Engineering, Northeastern University, Shenyang 110169)
Online: 2021-03-01Supported by:This work was supported by the National Key Research and Development Program of China (2018YFB1003404) and the National Natural Science Foundation of China (U1811261, 61672142).摘要/Abstract
摘要： 相似性连接技术在数据清洗、数据集成等领域中具有重要意义, 近年来引起了学术界的广泛关注.随着数据量的不断增大、数据处理实时性的要求逐渐提高以及处理器性能提升瓶颈的出现, 传统的串行相似性连接方法已经不能满足当前大数据处理的需求.近些年, GPU作为协处理器在机器学习等领域取得了良好的加速效果, 因此基于GPU的并行算法开始成为解决各类性能问题的有效解决方案.为此, 提出了基于CPU-GPU异构体系的并行相似性连接方法.首先, 方法使用GPU构建倒排索引, 索引采用SoA(struct of arrays)结构, 从而解决了传统索引结构在并行模式下读写效率低的问题.其次, 针对串行算法的性能问题, 提出基于过滤验证框架的并行双重长度过滤算法, 其中利用前缀过滤和构建好的倒排索引提升过滤效果.方法中相似度精确计算验证过程使用CPU计算执行, 从而充分利用CPU-GPU的异构计算资源.最后, 在多个数据集上进行实验验证性能.通过与串行相似性连接算法进行对比, 实验结果表明所提出方法相对于已有方法具有更好的过滤效果和更低的索引生成代价, 并在相似性连接上具有更好的性能和良好的加速比.
参考文献
相关文章 4
| [1] | 张振国,王超,温延龙,袁晓洁. 基于相似性连接的时间序列Shapelets提取[J]. 计算机研究与发展, 2019, 56(3): 594-610. |
| [2] | 惠榛,冯登国,张敏,洪澄. 一种可抵抗统计攻击的安全索引[J]. 计算机研究与发展, 2017, 54(2): 295-304. |
| [3] | 闫宏飞,旭东,单栋栋,毛先领,赵鑫. 基于指令级并行的倒排索引压缩算法[J]. 计算机研究与发展, 2015, 52(5): 995-1004. |
| [4] | 汤文,张春明,谭光明,张佩珩,孙凝晖. 基于定制协处理器的基因重测序加速技术研究[J]. 计算机研究与发展, 2014, 51(9): 1980-1992. |
PDF全文下载地址:
https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=4389
