1(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001); 2(佐治亚州立大学计算机科学与技术学院 佐治亚州亚特兰大 30303) (chenyubiao@hit.edu.cn)
出版日期:
2018-09-01基金资助:
国家重点研发计划项目(2016YFB1000703) This work was supported by the National Key Research and Development Program of China (2016YFB1000703).R-Tree Optimization Method Using Internal Parallelism of Flash Memory-Based Solid-State Drives
Chen Yubiao1, Li Jianzhong1, Li Yingshu1,2, Li Faming1, Gao Hong11(College of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001); 2(College of Computer Science and Technology,Georgia State University, Atlanta, Georgia 30303)
Online:
2018-09-01摘要/Abstract
摘要: 近年来,闪存固态硬盘内部结构有了很大的改进,使得它已拥有丰富的内部并行性.R-树是一种被广泛应用于空间数据管理的索引结构.但是,基于传统机械硬盘和闪存固有特点优化的R-树索引,并没有利用固态硬盘内部并行性来提高查询和更新效率.针对R-树索引,提出一种利用固态硬盘内部并行机制加速查询和更新的方法.首先,实现一种适合于固态硬盘内部并行性的异步I/O提交技术.在此基础上,针对R-树的查询和更新操作,通过聚集读写请求批量提交,以达到利用固态硬盘内部并行性加速的目的.此外,通过理论分析证明该优化方法,即使在并行通道只有4或者8时,依然可以提供1.86和2.93的期望加速比.通过真实数据在3款固态硬盘上的实验测试结果表明,利用优化策略的查询算法可实现高达3倍的稳定加速比,优化后的更新算法可达到2倍以上的加速比.无论是查询密集型或是更新密集型应用场景均有介于两者之间的加速比.
参考文献
相关文章 14
[1] | 安仲奇, 张云尧, 邢晶, 霍志刚. 基于用户级融合I/O的Key-Value存储系统优化技术研究[J]. 计算机研究与发展, 2020, 57(3): 649-659. |
[2] | 陈玉标, 李建中, 李英姝. SBS: 基于固态盘内部并行性的R-树高效查询算法[J]. 计算机研究与发展, 2020, 57(11): 2404-2418. |
[3] | 樊凌雁,周盟,骆建军,刘海銮. 多引擎并行CBC模式的SM4算法的芯片级实现[J]. 计算机研究与发展, 2018, 55(6): 1247-1253. |
[4] | 安仲奇,杜昊,李强,霍志刚,马捷. 基于高性能I/O技术的Memcached优化研究[J]. 计算机研究与发展, 2018, 55(4): 864-874. |
[5] | 陆克中,朱金彬,李正民,隋秀峰. 面向固态硬盘的Spark数据持久化方法设计[J]. 计算机研究与发展, 2017, 54(6): 1381-1390. |
[6] | 姚英彪,杜晨杰,王发宽. 一种基于分类策略的聚簇页级闪存转换层算法[J]. 计算机研究与发展, 2017, 54(1): 142-153. |
[7] | 姚英彪,沈佐兵. 基于连续缓存和二级缓存的DFTL改进算法[J]. 计算机研究与发展, 2014, 51(9): 2012-2021. |
[8] | 方 维 孙广中 吴 超 陈国良. 一种三维快速傅里叶变换并行算法[J]. , 2011, 48(3): 440-446. |
[9] | 白 梅, 信俊昌, 东 韩, 王国仁,. 不确定数据流上的概率反轮廓查询处理[J]. , 2011, 48(10): 1842-1849. |
[10] | 綦晓颖, 汤 显, 梁智超, 孟小峰,. OAFTL:一种面向企业级应用的高效闪存转换层处理策略[J]. , 2011, 48(10): 1918-1926. |
[11] | 黄 为 魏迎梅 宋汉辰 吴玲达. 基于并行小波算法的DEM数据多分辨率模型构建[J]. , 2010, 47(6): 1026-1031. |
[12] | 包尔固德, 李伟生, 范东睿, 杨扬, 马啸宇,. Godson-T众核体系结构上的Broadcast性能优化[J]. , 2010, 47(3): 524-531. |
[13] | 蒋夏军 吴慧中 李蔚清. 数据分发管理匹配算法的R-树实现[J]. , 2006, 43(2): 362-367. |
[14] | 迟利华 刘杰 胡庆丰. 数值并行计算可扩展性评价与测试[J]. , 2005, 42(6): 1073-1078. |
PDF全文下载地址:
https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=3778