摘要:散列表（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.



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/6069