Page 64 - 《软件学报》2020年第10期

3040 Journal of Software 软件学报 Vol.31, No.10, October 2020

效使用.其次,在采用 GPU 硬件作为计算核心单元时,在 CPU 与 GPU 内存之间的频繁数据传输引入了更多的系
统中断、进程切换、驱动调用等额外开销.因此,减少散列表内存访问次数与减少数据在 GPU 访存与内存之间
的频繁移动仍是优化散列表系统性能的重要途径.
在上述背景下,本文提出了一种适应 GPU 的混合访问缓存索引框架 CCHT(cache cuckoo hash table).该索引
框架可应用于缓存替换系统进行索引管理.CCHT 通过多级缓存索引数据结构与支持并发读写的缓存插入查
询算法实现了较低的内存访问次数.多级索引数据结构在提供了索引位置信息与全部缓存踢出优先队列信息
的同时,提供了散列表桶内踢出优先队列.支持并发读写的缓存插入查询算法,给出了在内存缓存系统中插入和
查询数据时散列表的操作方法.包括:当散列表桶内索引存储空间满与全局存储空间满时的踢出算法和插入查
询时桶内踢出队列与全局踢出队列的更新算法.本文根据内存缓存系统的命中率与索引空间占用开销,分别提
出了命中率相对更高的双重 LRU CCHT 与缓存空间开销占用相对更小的粗粒度 LRU CCHT.其中,双重 LRU
CCHT 通过两个缓存踢出优先级队列,在全局踢出与桶内踢出过程中独立使用,实现了高缓存命中率.粗粒度
LRU CCHT 方法则仅通过一个缓存踢出优先级队列,在全局踢出与桶内踢出过程中共同使用,在保证了缓存命
中率的同时,进一步减少了优先级队列对索引空间的占用开销.本文将 CCHT 在 GPUCPU 异构环境下进行了实
现,并为减少内存带宽的占用与 GPU 的访问次数,提出了基于外存计算系统(out-of-core)的多级索引数据结构.
通过这种结构,实现了在 CCHT 的请求处理过程中,在 CPU 与 GPU 内存间仅传输键数据,避免了值数据占用
GPU 内存空间以及带宽资源.通过实验验证,当缓存空间大小与散列表比值为 80%时,插入与全局负载的平均访
存次数分别最高降低了 30.39%和 32.91%;当缓存空间大小与散列表比值为 90%时,分别降低了 94.63%和
97.29%.这表明,CCHT 在散列表高装载率的情况下,仍能提供较低的内存访问次数,保证了缓存替换系统的性
能.在 CPUGPU 异构环境上的实验说明,CCHT 相对其他数据索引方法,在系统吞吐性能上得到了提升,验证了采
用的多级索引数据结构与实现方法的有效性.
1 相关工作

[9]
Cuckoo 散列是一种高效空间利用率的开放寻址方法 .它对每个对象指定多个候选散列表桶位置,同时允
许将已存储的对象替换到其他候选桶位置中.SILT [13] 通过两种散列方法实现了空间的高占用率,但受到了散列
[8]
表大小的限制,不能应用于大存储空间的内存缓存中.MemC3 在保证空间高利用率的同时,通过标签与优化锁
机制,消除了对散列表尺寸大小的限制.Hopscotch hashing [14] 和 Cache-oblivious hashing [15] 通过增加索引指针空
间保证访问并发性,提高了吞吐性能.Li 等人 [31] 通过硬件事务内存(HTM)与粗粒度锁机制,实现了访问的高并
发.FlashStore [15] 通过 Cuckoo 散列将一个对象映射到 16 个桶位置上,提高了插入时对象寻找空闲槽的几率.
Kirsch 等人 [16] 采用附加隐藏空间减少了插入寻找空闲空间的开销.
在 CPUGPU 异构环境上 CHT 实现的研究过程中,Horton table [10] 采用了附加空间与附加散列映射函数的方
式,代替了原有无空闲槽时进行的替换方法.Stadium hashing [11] 采用了 CPU 和 GPU 混合使用的方式以提升性
能,即将键(key)存储在 GPU 中,值(value)存储在 CPU 内存中.它通过添加票板(ticket board)的辅助数据结构来区
分对于 CPU 和 GPU 的操作,同时允许对同一散列表的并发读写操作.Barber [12] 采用了相似的位映射结构实现了
两个压缩类散列表.Xie 等人 [29,30] 采用 GPU 上程序编译和插桩的方式静态或动态地指定临时或不常用的数据
跳过部分芯片缓存,以减少芯片缓存的频繁置换.
实际应用中,散列表被广泛用于各种类型的系统软件及数据处理程序.很多内存键值存储系统通过应用于
GPU 上的散列表来加速键数据的查找 [23,32,33] .早期实现在 GPU 上的散列表用于数据库操作、图形处理和计算
机视觉 [34−38] .在内存数据库中,有很多相关的工作在 CPU 平台 [39−42] 、GPU 平台 [43−45] 和 Xeon Phi 平台 [21,46] 上对
散列表进行优化.

2 研究背景
本节介绍了我们工作的基础.其中,第 2.1 节描述了 CHT 的基本概念,第 2.2 节给出了 CHT 的典型实现方式,