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

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

4.4 优化细节
CCHT 采用任务批处理提交方式.在其他程序调用接入库函数时,将传入的键值数据及对应的操作复制到
键值数据与操作的缓冲区,当达到批处理提交的任务数阈值时,将键值数据及操作提交至 GPU 核函数,由 GPU
线程根据线程 id 并发对相应操作的键值数据进行处理.通过任务批处理提交的方式,减少了 CPU 与 GPU 间内
存的访问与传输频次,减少了 PCI-E 总线的访问,同时能够充分利用 GPU 多线程的并发性,提升散列表任务的
处理性能.
通过 GPU 执行维度参数配置实现单一 warp 中执行一种指令.在 CCHT 中,指令分支出现于各线程运行
global 函数 CCHT_process 后,需要根据散列表操作类型,调用不同的 device 函数.如果采用同一 warp 中混合多
种操作,将导致由 warp divergence 引发的同一 warp 中的不同散列表操作类型将顺序执行.我们通过限定同一
warp 执行单一线程实现避免指令分支造成的同步等待.虽然同一 warp 中仅执行单一线程影响了 GPU 的并发性
能,但基于 warp 粒度的并发仍能达到很好的吞吐效果,这一点,在后文的第 5.5 节中得到了验证.
在键值数据与任务缓存区的实现上,采用了混合与复用的方式.所有操作的键值数据与任务共享一个连续
的缓冲区.在返回结果时,将数据返回至提交任务的数据缓冲区中.这种混合与复用的实现方式减少了 CPU 与
GPU 内存的空间开销,释放了更多内存空间用于键值数据的存储.同时,相对多段缓存区的设计,连续的内存访
问操作比例增大,减少了因为数据存储在多段缓存区域造成的内存访问.
基于 CUDA 原生的原子操作锁机制.在 CCHT 中,包含并发写入、读取槽数据与变更 LRU 队列的操作,
需要对每个槽和 LRU 队列进行读写锁设计.即需要支持多个线程同时操作数据可以获得更好的并发性能,防
止因锁等待导致单个线程任务延迟过长.我们在 GPU 内存中设置了锁标识数据,默认值为 0.对于写操作,采用
了原子 atomicMax()方法实现,返回现有标识数据,并将标识数据更新为现有标识数据与置入数据的最大值.
在置入数据值为 1 的情况下:当返回值为 0 时,表明锁空闲,完成后通过 atomicExch()置 0 解锁;当返回值不为
0 时,表明有其他读或写线程正在访问数据.对于读操作,基于 atomicAdd()的方法进行实现,返回现有标识数
据,并将标识数据更新为现有标识数据与置入数据之和.当返回值模 2 值不为 0 时,表明有写线程正在访问数
据;当返回值模 2 结果为 0 时,表明无其他写线程访问数据.成功占用锁并完成操作后,通过 atomicSub()方法释
放当前读线程对锁占用.通过上述方法实现了允许同一时间单一写操作或多个读操作同时进行.基于 CUDA
原生的原子操作锁机制代替了 CUDA 传统原子数据操作赋值方法,打破了对依赖 CUDA 库函数的原子操作
数据大小的上限限制.在 CCHT 的 GPU 端处理任务请求过程中,线程同一时刻仅可能获取单个槽的锁,不会因
为多个锁资源同时抢占而造成死锁.
5 实验结果与分析

实验在 CPU+GPU 异构服务器上进行,其中,CPU 为 Intel(R) Core(TM) i7-6700K,四核 4.00Ghz 主频,内存
DDR4 32GB,GPU 为 NVIDIA GeForce GTX 1080Ti,显存 11GB.
实验中采用 YCSB [50] 生成的数据集进行测试,数据键值的长度为 24B,值类型为 100B,插入数据集的规模为
6
3×10 个元素.数据操作请求包括 3 种典型的工作负载,Zipf、latest、uniform.其中,Zipf 工作负载分布偏度为
0.99,latest 工作负载为最近使用的数据请求,uniform 工作负载查询的数据概率相同.每个工作负载请求中包含
两类插入与查询操作比值,分别为全部是查询操作以及查询操作占比 50%.根据内存缓存典型运行环境特征 [12] ,
在查询返回丢失后,进行插入操作.在实验过程中,首先进行数据集加载与缓存预热操作,然后再进行工作负载
请求操作.
为了对 CCHT 应用性能进行验证,我们实现了以 CCHT 为核心的缓存替换系统原型.为了对比,还实现了另
外 3 种缓存索引算法:LRU CHT、LRU 开散列表(LRU open hash)、随机 CHT(random CHT),其中,LRU CHT 与
随机 CHT 在 CPUGPU 异构平台下进行对比验证.LRU 开散列表由于动态分配数据空间的特性不适用于
CPUGPU 异构平台的初始化固定存储空间,我们在 CPU 平台进行了实现与对比验证.设置 CCHT 与 CHT 的散
4
列值长度为 2 ,每个散列值对应的桶包含 4 个索引存储单元.CHT 的踢出替换操作上限为 5 000 次.CCHT 批处