推荐星级：
- 1
- 2
- 3
- 4
- 5
基于向量引用Platform-Oblivious内存连接优化技术
资料介绍
以MapD为代表的图分析数据库系统通过GPU、Phi等新型众核处理器来支持高性能分析处理,在面向复杂数据模式时,连接操作仍然是重要的性能瓶颈.近年来,异构处理器逐渐成为高性能计算的主流平台,内存连接性能的研究从多核CPU平台扩展到新兴的众核处理器,但众多的研究成果并未系统地揭示连接算法性能、连接数据集大小、硬件架构之间的内在联系,难以为未来异构处理器平台的数据库提供连接平台优化选择策略.以面向多核CPU、Xeon Phi、GPU处理器平台的内存连接优化技术为目标,通过优化内存哈希表设计,实现以向量映射替代哈希映射操作,消除哈希代价对内存连接算法的影响,从而更加准确地测量内存连接算法在多核CPU的cache大小、Xeon Phi的cache大小、Xeon Phi的并发多线程、GPU的SIMT(单指令多线程)机制等硬件相关因素影响下的性能特征.实验结果表明,缓存与并发多线程机制是提高内存连接算法性能的重要影响因素.缓存机制对于满足cache大小的连接操作具有性能优势,而GPU的并发多线程机制则在较大表的连接操作中具有较高的性能,Xeon Phi则在满足其L2 cache大小的连接操作中具有最高性能.实验结果揭示了内存连接操作性能与异构处理器硬件特性的联系,为未来异构处理器平台内存数据库查询优化器提供了优化策略.
部分文件列表
| 文件名 | 大小 |
| 基于向量引用Platform-Oblivious内存连接优化技术.pdf | 1M |
部分页面预览
（完整内容请下载后查看）软件学报ISSN 1000-9825, CODEN RUXUEW
Journal of Software,2018,29(3):883-895 [doi: 10.13328/j.cnki.jos.005446]
©中国科学院软件研究所版权所有.
E-mail:
Tel: +86-10-62562563
基于向量引用Platform-Oblivious 内存连接优化技术∗
1,2,3
4
1,2
张延松
,
张
宇
,
王
珊
1(数据工程与知识工程教育部重点实验室(中国人民大学),北京 100872)
2(中国人民大学 信息学院,北京 100872)
3(中国人民大学 中国调查与数据中心,北京 100872)
4(国家卫星气象中心,北京 100081)
通讯作者: 张宇, E-mail:
摘 要: 以 MapD 为代表的图分析数据库系统通过 GPU、Phi 等新型众核处理器来支持高性能分析处理,在面向
复杂数据模式时,连接操作仍然是重要的性能瓶颈.近年来,异构处理器逐渐成为高性能计算的主流平台,内存连接
性能的研究从多核 CPU 平台扩展到新兴的众核处理器,但众多的研究成果并未系统地揭示连接算法性能、连接数
据集大小、硬件架构之间的内在联系,难以为未来异构处理器平台的数据库提供连接平台优化选择策略.以面向多
核 CPU、Xeon Phi、GPU 处理器平台的内存连接优化技术为目标,通过优化内存哈希表设计,实现以向量映射替代
哈希映射操作,消除哈希代价对内存连接算法的影响,从而更加准确地测量内存连接算法在多核 CPU 的 cache 大小、
Xeon Phi 的 cache 大小、Xeon Phi 的并发多线程、GPU 的 SIMT(单指令多线程)机制等硬件相关因素影响下的性
能特征.实验结果表明,缓存与并发多线程机制是提高内存连接算法性能的重要影响因素.缓存机制对于满足 cache
大小的连接操作具有性能优势,而 GPU 的并发多线程机制则在较大表的连接操作中具有较高的性能,Xeon Phi 则在
满足其 L2 cache 大小的连接操作中具有最高性能.实验结果揭示了内存连接操作性能与异构处理器硬件特性的联
系,为未来异构处理器平台内存数据库查询优化器提供了优化策略.
关键词: 内存连接操作;哈希连接;向量映射;异构处理器平台
中图法分类号: TP311
中文引用格式: 张延松,张宇,王珊.基于向量引用 Platform-Oblivious 内存连接优化技术.软件学报,2018,29(3):883-895. http://
英文引用格式: Zhang YS, Zhang Y, Wang S. Vector referencing oriented platform-oblivious in-memory join optimization
technique. Ruan Jian Xue Bao/Journal of Software, 2018,29(3):883-
htm
Vector Referencing Oriented Platform-Oblivious In-Memory Join Optimization Technique
ZHANG Yan-Song1,2,3
,
ZHANG Yu4, WANG Shan1,2
1(Key Laboratory of Data Engineering and Knowledge Engineering of Ministry of Education (Renmin University), Beijing 100872,
China)
2(School of Information, Renmin University of China, Beijing 100872, China)
∗ 基金项目: 国家自然科学基金(61732014, 61772533); 国家高技术研究发展计划(863)(2015AA015307); 中央高校基本科研业
务费专项资金(16XNLQ02)
Foundation item: National Natural Science Foundation of China (61732014, 61772533); National High Technology Research and
Development Program of China (863) (2015AA015307); the Basic Research Funds in Renmin University of China from the Central
Government (16XNLQ02)
本文由基于图结构的大数据分析与管理技术专刊特约编辑林学民教授、杜小勇教授、李翠平教授推荐.
收稿时间: 2017-07-31; 修改时间: 2017-09-05; 采用时间: 2017-11-07; jos 在线出版时间: 2017-12-05
CNKI 网络优先出版: 2017-12-06 15:23:24, http://kns.cnki.net/kcms/detail/11.2560.TP.20171206.1522.010.html
884
Journal of Software 软件学报 Vol.29, No.3, March 2018
3(National Survey Research Center at Renmin University of China, Beijing 100872, China)
4(National Satellite Meteorological Centre, Beijing 100081, China)
Abstract: Graph analysis database such as MapD employs the emerging manycore architecture GPU and Phi processors to support high
performance analytical processing, where the join operation is still the performance bottleneck when facing complex data schemas. In
recent years, as heterogeneous processors come to be main-stream high performance computing platforms, the researches of in-memory
join performance extend the focuses from multicore to the emerging manycore platforms. However those efforts have not uncover the
inner relationships among join algorithm performance, join dataset size and hardware architectures, and cannot provide sufficient join
selection strategies for databases under the future heterogeneous processor platforms. This paper targets in-memory join optimization
techniques on multicore, Xeon Phi and GPU processor platforms. By optimizing hash table design, this work uses vector mapping instead
of hash mapping to eliminate the hashing overhead effects for performance, so that the in-memory join performance characteristics
influenced can be measured by hardware factors such as multicore cache size, Xeon Phi cache size, Xeon Phi simultaneous
multi-threading mechanism, and GPU SIMT (single instruction multiple threads) mechanism. The experimental results show that caching
and simultaneous massive-threading mechanism are key factors to improve in-memory join algorithm performance. Caching mechanism
performs well for cache fit join operations, the simultaneous massive-threading mechanism of GPU does well for big table joins, and
Xeon Phi achieves the highest performance for L2 cache fit joins. The experimental results also exploit the relationship between
in-memory join performance and heterogeneous processor hardware features, and provide optimization policy for in-memory database
query optimizer on future heterogeneous processor platforms.
Key words: in-memory join operation; Hash join; vector mapping; heterogeneous processor platform
社交网络分析和大数据可视化,是图结构大数据分析的重要组成部分.MapD[1]是一种面向大规模社交网络
分析性能压力而开发的GPU 数据库系统,主要用于Twitter 社交网络数据实时分析处理,其研发的初衷是传统数
据库技术难以支持大规模图数据实时分析处理需求,其独特的 GPU 数据库查询处理引擎相对于传统基于 x86
处理器架构的数据库查询处理引擎有显著的性能优势,成为当前大数据实时分析处理领域的代表性技术.从图
数据分析处理需求来看,社交网络分析具有典型的多维分析处理特征,在数据可视化[2]中,需要以 GIS 数据、时
间数据、类别数据等信息构建多维分析处理模型,支持从不同维度、不同层次、不同视角的社交网络分析处理.
而在面对复杂模式下的分析处理时,连接是其中执行代价较高的操作,连接性能也是数据库综合性能的重要指
标之一.从 MapD 数据库技术特点来看,其发展揭示了新兴数据库技术充分利用新硬件技术发展来克服传统数
据库性能瓶颈的设计思想,为数据库查询优化技术研究提供了宝贵的参考.
从硬件技术发展趋势来看,处理器技术经历了从单核到多核再到众核架构的革新.在标志着高性能计算的
TOP 500[3]和绿色计算的GREEN500[4]榜单中,包含众核协处理器Xeon Phi 和GPU 的异构处理器平台已经成为
主流配置,在高性能计算HPC 领域得到了广泛应用,数据库也面临从x86 多核CPU 平台向支持新一代众核处理
器的异构处理器平台的技术升级.但硬件结构变化在带来新硬件性能红利的同时,也增加了数据库查询优化的
技术障碍和系统结构的复杂性,数据库在异构处理器平台上的应用仍然进展缓慢.
连接是数据库执行代价最大的操作之一,连接优化技术一直是数据库性能优化研究的一个热点问题.
hardware-conscious 还是hardware-oblivious,哪种算法设计有更高的性能?研究中的hardware 泛指x86 多核处理
器,hardware-conscious 算法设计思想的目标是追求最高的性能,其指导思想是充分考虑相关硬件的特性对连接
算法进行深度优化设计与调优;而 hardware-oblivious 算法设计思想的目标是追求简单通用的实现框架和较高
的硬件自适应性能,其指导思想是利用硬件具有的共性设计连接算法,利用硬件性能的支持自动达到相对较高
的性能.内存数据库核心的连接算法广泛采用hardware-conscious 优化设计思想.传统的x86 架构处理器技术采
用以cache 为中心的设计思想,40%以上的晶体管用于制作cache 单元,处理器结构复杂,核心数量增长缓慢,价格
昂贵,系统能耗较高.其上的连接操作主要以中、低度并行算法设计和以cache 为中心的数据访问优化技术为基
础,性能受制于 x86 平台有限的 LLC(last level cache,最后一级 cache)容量和较低的核心数量.GPU 采用与 x86
处理器不同的架构,数以千计的处理核心支持更多的硬件级线程,提供强大的并行处理能力,GPU 主要通过
SIMT(single instruction multiple threads,单指令多线程)机制,以大量并发线程访问内存,并通过硬件级的线程切
全部评论(0)