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

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

return success
end if
H 2 =Hash 2 (key)// //compute the hash value of key with hash function 2
if i=Findfree(H 2 )
Set(H 2 ,i,key,value)
UpdateLRU(H,i)
return success
end if
H=Comparetimestamp(H 1 ,H 2 )//find a hash value through comparing the timestamps of H 1 and H 2
i=EvictBucketTail(H)//evict the tail unit of bucket H LRU queue
Set(H,i,key,value)
updateLRU(H,i)
return success
Procedure UpdateLRU(H,i):
UpdateBucketLRU(H,i)//update bucket internal LRU queue
UpdateGlobalLRU(H,i)//update global LRU queue
算法 2. 双重 LRU CCHT 查询算法.
输入:键数据 key;
输出:值数据 value.
H=hash 1 (key)
for i=0;i<BucketInternalMax;i++ do
if CompareKey(Bucket[H][i]→key,key)//compare the value of key

UpdateLRU(H,i)
return Bucket[H][i]→value
end if
end for
H=Hash 2 (key)
for i=0;i<BucketInternalMax;i++ do
if CompareKey(Bucket[H][i]→key,key)
UpdateLRU(H,i)
return Bucket[H][i]→value
end if
end for
return NULL
3.3 粗粒度LRU CCHT方法
为了节省 CCHT 中指针占用的存储空间,我们提出了粗粒度 LRU CCHT 方法,如图 4 所示.相对双重 LRU
CCHT 索引结构,取消了用于全局 LRU 队列的槽指针,添加了基于桶的 LRU 队列操作.每个桶中包含有两个桶
指针,用于维护粗粒度的 LRU 队列.
当通过粗粒度 LRU CCHT 方法进行插入操作和查询成功后,将对应桶放置于桶 LRU 队首,对应的索引单元
放置于桶内 LRU 队首.当插入数据时,若内存缓存中无空闲缓存空间,则选择桶 LRU 队列中位于队尾的桶,选择
队尾桶中的桶内 LRU 队列队尾的槽进行键值数据的踢出与释放.
粗粒度 LRU CCHT 方法通过桶 LRU 算法取代了双重 LRU CCHT 方法与 LRU CHT 方法中的全局 LRU 索