一种适应GPU的混合访问缓存索引框架
作者:
作者单位:

作者简介:

张鸿骏(1989-),男,学士,主要研究领域为操作系统,大数据处理,分布式,并行计算.
武延军(1979-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为操作系统,系统安全.
张珩(1990-),男,博士,CCF学生会员,主要研究领域为分布式,并行计算,大数据处理,操作系统.
张立波(1989-),男,博士,主要研究领域为人工智能,深度学习,计算机视觉.

通讯作者:

张鸿骏,E-mail:hongjun@iscas.ac.cn

中图分类号:

基金项目:

中国科学院战略性先导科技专项预研课题(Y8XD373105);中国科学院前沿科学重点研究计划(ZDBS-LY-JSC038)


Hybrid Access Cache Indexing Framework Adapted to GPU
Author:
Affiliation:

Fund Project:

Strategic Priority Research Program of the Chinese Academy of Sciences (Y8XD373105); Key Research Program of Frontier Sciences, Chinese Academy of Sciences (ZDBS-LY-JSC038)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    散列表(hash table)作为一类根据关键码值(key value)提供高效数据访问的数据索引结构,其广泛应用于各类计算机应用中,尤其是在对性能要求极高的系统软件、数据库以及高性能计算领域.在网络、云计算和物联网服务方面,以散列表为核心结构已经成为缓存系统的重要系统组件.然而,随着大规模数据量的大幅度增加,以多核CPU为核心设计散列表结构的系统已经逐渐出现性能瓶颈,亟需进一步改进散列表的高性能和可扩展性.随着通用图形处理器(graphic processing unit,简称GPU)的日益普及以及硬件计算能力和并发性能的大幅度提升,各类以并行计算为核心的系统软件任务在GPU上进行了优化设计并得到可观的性能提升.由于存在稀疏性和随机性,采用现有散列表的并行结构直接在GPU上应用势必会带来高频次的内存访问和频繁的总线数据传输,影响了散列表在GPU上的性能发挥.重点分析了缓存系统中散列表索引的内存访问、命中率与索引开销,提出并设计了一种适应GPU的混合访问缓存索引框架CCHT(cache cuckoo hash table),提供了两种适应不同命中率和索引开销要求的缓存策略,允许写入与查询操作并发执行,最大程度地利用了GPU硬件的计算性能与并发特性,减少了内存访问与总线传输.通过在GPU硬件上的实现与实验验证,CCHT在保证缓存命中率的同时,性能优于其他用于缓存索引的散列表.

    Abstract:

    Hash tables, as a type of data indexing structure that provides efficient data access based on key values, are widely used in various computer applications, especially in system software, databases, and high performance that require high performance Computing field. In network, cloud computing and IoT services, hash tables have become the core system components of cache systems. However, with the large-scale increase in the amount of large-scale data, performance bottlenecks have gradually emerged in systems designed with a multi-core CPU as the core of the hash table structure. There is an urgent need to further improve the high performance and scalability of the hash table. With the increasing popularity of general-purpose graphics processing units (GPUs) and the substantial improvement of hardware computing capabilities and concurrency performance, various types of system software tasks with parallel computing as the core have been optimized on the GPU and have achieved considerable performance promotion. Due to the sparseness and randomness, using the existing parallel structure of the hash table directly on the GPU will inevitably bring high-frequency memory access and frequent bus data transmission, which affects the performance of the hash table on the GPU. This study focuses on the analysis of memory access, hit rate, and index overhead of hash table indexes in the cache system. A hybrid access cache index framework CCHT (cache cuckoo hash table) adapted to GPU is proposed and provided. The cache strategy required by index and index overhead allows concurrent execution of write and query operations, maximizing the use of the computing performance and concurrency characteristics of GPU hardware, reducing memory access and bus transferring overhead. Through GPU hardware implementation and experimental verification, CCHT has better performance than other cache indexing hash table while ensuring cache hit rate.

    参考文献
    相似文献
    引证文献
引用本文

张鸿骏,武延军,张珩,张立波.一种适应GPU的混合访问缓存索引框架.软件学报,2020,31(10):3038-3055

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2020-02-10
  • 最后修改日期:2020-04-04
  • 录用日期:
  • 在线发布日期: 2020-06-11
  • 出版日期: 2020-10-06
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号