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

张鸿骏 等:一种适应 GPU 的混合访问缓存索引框架 3043

单元大小的索引结构,通过对时间戳的比较,选取最早访问的数据单元进行踢出 [47] .
2.4 CUDA编程技术
计算统一设备架构(compute unified device architecture,简称 CUDA)是显卡厂商 NVIDIA 推出的并行计算
架构,已逐步发展成为 NVIDIA GPU 的编程标准规范.
CUDA 提供了基于标准 C 语言的编程模型,支持对 GPU 操作相关的关键字与结构体.基于 CUDA 的 GPU
编程程序中包含 CPU Host 端执行代码与 GPU Device 端代码,程序中的两部分代码通过 CUDA 的编译器自动
地分为两部分进行编译与链接 [48] .
CUDA 支持程序开发人员编写称为内核(kernel)的设备方法代码.内核被 GPU 以单指令多线程(single
instruction multiple thread,简称 SIMT)形式执行.在程序执行过程中,加载一个内核方法相当于调用内核方法,同
时,程序开发人员需要指定对应的 GPU 空间网格(grid)执行.一个网格包含多个线程块(block),构成一个二维空
间,每个块中包含多个线程,构成一个三维空间.每个 GPU 中的线程都通过线程标识符(thread id)进行标识.在一
个块中的线程可以通过栅栏实现同步.
GPU 线程在内核方法执行过程中获得 GPU 内存的访问权限.每个线程对存储的操作包括读写私有寄存器
和本地内存.内核方法中的本地变量被自动地分配到寄存器或者内存中.GPU 其他内存中的变量可以通过接口
创建与管理.在 CUDA 程序中可能包含多个内核,所有的操作都可以应用于每一个内核.在下文介绍的 CCHT 设
计与实现过程中,将所有的 CHT 与替换操作全部实现于内核中,以提高程序的执行效率,同时面向单一的处理
器实现能够更方便地向其他平台进行移植.

3 基于不同索引空间占用缓存索引 CCHT 方法

在本节中,我们主要介绍了基于不同索引空间占用的缓存索引方法的设计与实现,包括索引结构设计与缓
存替换算法.其中,第 3.1 节给出了面向内存缓存的散列索引分析,第 3.2 节描述了双重 LRU 索引访问方法,第 3.3
节描述了粗粒度 LRU 索引访问方法.

3.1 面向内存缓存的散列索引分析
在内存缓存系统中,散列索引与缓存替换策略一般分别加以实现 [5,8] .散列索引用于对内存中的缓存数据进
[8]
行索引,在缓存系统处理查询请求时可快速访问目标数据.常见的散列索引,如本文提到的应用于 MemC3 中的
[5]
CHT 和 memcached 中的开散列(open hashing)方法.替换策略用于当内存缓存被所需缓存数据存储已满时,有
新的数据需要进行缓存,则在已缓存数据中通过某一策略选择待踢出数据,进行替换.常用的缓存索引方法有本
文中提到的 LRU、FIFO(先进先出算法)、LFU(最近最常使用算法)、CLOCK(时钟算法) [49] .其中,LRU 由于实
现简单,维护方便,策略符合一般工作负载需求而被广泛使用.
当通过 CHT 进行数据索引时,每个数据对应两个可选的桶,如果两个桶中已无空闲槽,则需要在两个位置
中选择随机槽内数据进行置换,之后根据置换出的键值数据进行散列值计算,可能会导致更多次的访存操作,如
第 2.1 节中所述.在内存缓存系统中,缓存数据无持久化存储需求.缓存替换策略可根据多维度指标,如命中率、
访问延迟、空间占用率、吞吐等踢出缓存数据.因此,我们设计了内置缓存策略的 CCHT,即在内存缓存系统中,
以 CHT 为基础,当索引散列表需要进行踢出置换时,调用缓存替换策略,进行踢出.我们依据索引开销与命中率
需求实现了两种方法,在后文中将分别加以描述.
3.2 双重LRU CCHT缓存索引方法
CCHT 设计的核心思路是通过添加桶内缓存队列操作移除 CHT 原有的无空闲槽时进行的置换操作,达到
减少内存访问和支持插入与查询操作并发执行的目的.
双重 LRU CCHT 缓存索引结构与典型的 LRU CHT 的结构类似.如图 3 所示,在结构中通过散列表对键值
数据进行索引.每个散列值对应一个桶,每个桶中包含有固定数量的槽.每个槽中包含有键值数据,占用标示,两
个用于桶内 LRU 的槽指针,两个用于全局 LRU 的槽指针.其中,与典型的 LRU CHT 结构不同的是增加用于桶内