Improving the Performance of Sparse Directories

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.