提升稀疏目录缓存一致性系统性能的方法  

Improving the Performance of Sparse Directories

作　　者：张轮凯[1,2] 宋风龙[1] 王达[1] 范东睿[1] 孙凝晖[1] 

机构地区：[1]中国科学院计算技术研究所高性能计算机研究中心,北京100190 [2]中国科学院大学,北京100049

出　　处：《计算机研究与发展》2014年第9期1955-1970,共16页Journal of Computer Research and Development

基　　金：国家"九七三"重点基础研究发展计划基金项目(2011CB302501);国家自然科学基金项目(61173007;61100013;61100015;61202059)

摘　　要：稀疏目录技术在缓存一致性非一致存储访问(cache coherent non-uniform memory access,ccNUMA)系统中有广泛应用.但是,稀疏目录技术的一个主要缺陷在于目录项替换在目录热点存在的情况下会严重降低系统的性能.针对此问题,研究如何提升稀疏目录性能.首先,从定性和定量的角度对主流的稀疏目录替换算法进行了分析,并且发现最为原始的最久未使用(least-recent-used,LRU)算法的性能实际上要优于一些近期提出的目录替换算法,如最少共享者(least-sharer-count,LSC)算法.其次,将victim cache的思想应用到稀疏目录上,提出了victim目录(victim directory),该技术在主稀疏目录模块上加入了一个小的全相联二级目录存储.最后,提出了选择性victim目录(selective victim directory)技术,使得victim目录选择性地仅存储有用的目录项,从而进一步减少了目录替换的数量.选择性victim目录通过向所有节点的cache发出探查消息(probe messages),从而选择性地存储较为有用的目录项.实验证明,选择性victim目录取得了比简单victim目录更好的性能;而且在仅增加了1KB左右的硬件开销的代价下,选择性victim目录节省了35.7%的程序运行时间.Sparse directory technique is proved to be an effective coherence scheme in ccNUMA system.However,the downside is that sparse directories may require costly directory evictions which degenerate the overall system performance.This paper discusses and evaluates the methods to improve the effectiveness of sparse directories,including replacement policies of sparse directories and victim directories.First,we qualitatively and quantitatively compare state-of-the-art replacement policies of sparse directories,and the results show that,contrary to common beliefs,the traditional least-recent-used（LRU）considerably outperforms several recently proposed directory replacement policies（e.g.,least-sharer-count（LSC）policy）.We further propose victim directory schemes which add small fully associative directory buffers to the main sparse directory modules.Two different victim directory schemes are proposed,namely：simple victim directory and selective victim directory.Selective victim directory scheme manages to differentiate the usefulness of directory entries by sending probe messages to caches,and it only preserves the useful directory entries in the victim directory.Experiments show that,with minimal hardware requirement（in our experiment,around 1KB additional storage per ccNUMA node）,selective victim directory scheme saves on average 35.7%execution time compared with baseline sparse directory scheme,therefore it is extremely effective in improving the performance of sparse directories.

关 键 词：ccNUMA系统 稀疏目录 替换算法 victim目录 选择性victim目录 

分 类 号：TP33[自动化与计算机技术—计算机系统结构]