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

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

引.相对于双重 LRU CCHT,减少了 2×m×(s−1)个槽指针占用,其中,m 为 CCHT 内桶的个数,s 为单个桶中槽的个
数,为 CCHT 节省了索引存储开销.

Fig.4 Coarse LRU CCHT structure
图 4 粗粒度 LRU CCHT 缓存索引结构

4 CCHT 在面向 CPUGPU 异构环境上的实现
根据第 3 节中 CCHT 的方法描述,本节主要介绍了 CCHT 在 CPUGPU 异构环境上进行的实现.其中,第 4.1
节描述了面向 CPUGPU 异构存储下的多级数据索引结构,第 4.2 节给出了异构环境下 CCHT 的应用接口函数,
第 4.3 节描述了 CCHT 的实现细节,第 4.4 节给出了 CCHT 在实现过程中的优化.
4.1 异构存储下的多级索引数据结构
在现实应用中,如图数据、日志数据及视频数据为值数据的散列表值数据存储空间开销大.以 GPU 内存为
散列表的处理设计与性能受到了系统 PCI 总线带宽和 GPU 内存大小的限制.因此,我们采用了基于外存计算系
统的方式设计了多级索引数据结构.在存储空间初始化时,在 CPU 内存中分配连续的存储空间.在对 GPU 上散
列表进行操作时,用 CPU 上原始值数据对应的索引序列值进行表示,减少了 GPU 内存空间的占用及 PCI-E 带宽
传输开销.
键值数据在 CPU 和 GPU 的分布如图 5 所示.
如插入键值数据对 KV 1 ,值数据 V 1 存储在 CPU 内存
的连续值存储区,位置标识 ID 为 0;键数据 K 1 与索引
位置 ID 值 0,通过系统总线传输至 GPU 内存中,并存
储在对应散列值桶中的空闲槽内.当查询 KV 3 时,将
K 3 通过系统总线传输至 GPU 内存中,待查询完成后,
通过总线返回对应位置标识 ID 值 2.通过多级
CPUGPU 异构值索引结构,有效地减少了 GPU 中内
存的占用和总线带宽占用.在 GPU 内存中,除查询必
须的键数据,仅包含值数据的位置标识外,相对于原

Fig.5 The CCHT data structure under CPUGPU 始值数据,减少了有限 GPU 空间内存的占用.在请求
图 5 CPUGPU 下的 CCHT 数据结构 处理时,插入与查询的值数据均不通过总线传输至
GPU 内存,有效地避免了因值数据过大造成的总线
带宽占用以及性能损耗.
4.2 异构环境下CCHT的应用接口函数
CCHT 实现的方法主要包含接入库函数,数据存储区域初始化函数及操作散列表的 GPU kernel(核)函数.我