Scalable cache coherent schemes for direct-connected shared memory multiprocessors

Abstract

Large scale shared memory multiprocessors favor a directory-based cache coherence scheme for its scalability. The directory space needed to record the information for sharers has a complexity of $\Theta(N^2)$ when a full-mapped vector is used for an N-node system. Though this overhead can be reduced by limiting the directory size assuming that the sharing degree is small, it will experience significant inefficiency when a data is widely shared. As a reason of the coherence overhead, we notice that most coherence actions in directory-based protocols are initiated by home nodes, and this nature consequently leads to limit the scalability. In order to lessen the burden of home nodes, we propose a new directory scheme and an efficient broadcast capability for a direct interconnection network. The broadcast capability is based on the fact that all switching technologies allow each router to watch a message passed by, and thus a message can be used to perform a broadcast mission without extra traffic, which can be utilized for the cache coherence problem. Only a slight change on a typical router is needed to implement our scheme. The Splash parallel program suite is used in the simulation study where our scheme is compared with other directory based schemes. Our scheme is proved to generate much less traffic for cache coherence while the space complexity is slightly more scalable ($\Theta(N^{3/2}\log{N})$). This scheme is also applicable to any k-ary n-cube networks including a mesh. Based on the proposed broadcast mechanism, we present two enhanced schemes which aggressively exploit the nature of wide sharing pattern in conjunction with software. One scheme is motivated by the fact that most widely shared data have relatively short write runs, and thus updates to those data are more effective while the invalidate scheme is still effective for other data. For this scheme, it is more important to accurately identify the widely shared data. Simulation results show that...