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

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

时,数据在 CPU 和 GPU 内存间传输的延迟时间.在 CCHT 中具体是指调用 GPU 处理散列表请求时,请求数据与
操作命令缓冲区由 CPU 内存拷贝到 GPU 内存和请求结果由 GPU 内存拷贝到 CPU 内存的时间总和.数据传输
延迟时间见表 4,4 种散列表在各工作负载中单次调用 GPU 数据传输的规模相同,我们采用以 80%缓存空间占
比的 latest、query 100%工作负载为代表进行实验验证.其中,双重 LRU CCHT 和粗粒度 LRU CCHT 的数据传
输延迟均高于 LRU CHT 和随机 CHT,原因是 CCHT 采用了批处理操作,允许散列表在 GPU 上大规模并发处理
请求.以实验设置的批处理阈值 2 000 为例,CCHT 在调用 GPU 时,单次的传输数据包括 2 000 个操作数据和操
作请求类型,平均单个操作数据和操作请求类型的传输延迟远低于 LRU CHT 和随机 CHT.
Table 4 CPUGPU data transfer delay
表 4 CPUGPU 数据传输延时
Hash table type Delay (μs)
Double LRU CCHT 40
Coarse LRU CCHT 40
LRU CHT 13
Random CHT 12

进一步地,我们对单次操作的平均延迟进行了对比评估,即散列表处理单次请求在 CPU 或 GPU 环境上的平
均延迟时间.其中,LRU 开散列表为单次请求处理在 CPU 环境上的平均延迟时间,其余散列表为单次请求处理
在 GPU 环境上的平均延迟时间.单次操作的平均延迟如图 10 所示.双重 LRU CCHT 和粗粒度 LRU CCHT 的延
迟时间高于其他散列表,原因是 CCHT 实现了 GPU 上大规模的并发操作,虽然通过 warp 分配避免了分支等待
的延迟开销,但各线程间仍存在着对于槽和 LRU 队列锁的竞争操作,以及在同一次批处理中的同步开销,即执
行完操作的线程需等待未执行完操作的线程完成后一同返回.这类操作均带来了额外的开销,导致了延迟的增
加.同时,从实验结果可以看出,粗粒度 LRU CCHT 的延迟同样高于双重 LRU CCHT.这是因为粗粒度 LRU
CCHT 在全局和桶内共用的同一 LRU 队列均在 GPU 环境上进行操作,相对双重 LRU CCHT 仅桶内锁在 GPU
环境上进行操作,粗粒度 LRU CCHT 存在更多的锁竞争.LRU CHT 和随机 CHT 虽然低于前两者,但由于受高负
载下可能发生插入操作出现频繁槽数据置换的影响,单次延迟最高达到了 143μs,远高于平均延迟时间.LRU 开
散列表由于没有锁竞争以及运行在 CPU 环境上,延迟时间在 0.36μs~0.49μs.

Fig.10 Latency on workloads with 80% cache space size/hash table size
图 10 在 80%缓存空间工作负载中的延迟表现