Abstract: "This paper considers alternative directory protocols for providing cache coherence in shared-memory multiprocessors with 32 to 128 processors, where the state requirements of Dir[subscript N] may be considered too large. We consider Dir[subscript i]B, i = 1,2,4, Dir[subscript N], Tristate (also called superset), Coarse Vector, and three new protocols. The new protocols -- Gray-hardware, Gray-software, Home -- are optimizations of Tristate that use gray coding to favor near-neighbor sharing. Our results are the first to compare all these protocols with complete applications (and the first evaluation of Tristate with a non- synthetic workload). Results for three applications -- ocean (one dimensional sharing), appbt (three-dimensional sharing), and barnes (dynamic sharing) -- for 128 processors on the Wisconsin Wind Tunnel show that (a) Dir1B sends 15 to 43 times as many invalidation messages as Dir[subscript N], (b) Gray-software sends 1.0 to 4.7 times as many messages as Dir[subscript N], making it better than Tristate, Gray- Hardware, and Home, and (c) the choice between Dir[subscript i]B, Coarse Vector, and Gray-software depends on whether one wants to optimize for few sharers (Dir[subscript i]B), many sharers (Coarse Vector), or hedge one's bets between both alternatives (Gray-software)."

Some alternative directory entry formats are described, including a special entry format for implementing queueing semaphores. Evaluation of the various entry formats is done with probabilistic models of shared cache blocks and software simulation. A variable length global table organization is presented which can be used to reduce the size of the global table, regardless of the entry format. Its performance is analyzed using software simulation. A protocol which maintains a linked list of processors which have a particular block cached is presented. Several variations of this protocol induce less interconnection network traffic than traditional protocols."

New high-performance processors tend to shift from multi to many cores. More- over, shared memory has turned to dominant paradigm for mainstream multicore pro- cessors. As memory wall issue loomed over architecture design, most modern computer systems have several layers in their memory hierarchy. Among many, caches has be- come everlasting components of memory hierarchies as they signicantly reduce access time by taking the advantage of locality. ☐ Major processor vendors usually rely on cache coherence, and implement a vari- ant of MESI, e.g., MOESI for AMD, to help reduce inter-chip trac on the fast in- terconnection network. Supposedly, maintaining coherence should help with keeping parallel and concurrent programmers happy, all the while providing them with a well- known cache behavior for shared memory. This thesis challenge the assumption that Coherence is well-suited for large-scale many core processors. Seeking an alternative for coherence, LC cache protocol is extensively investigated. ☐ LC-Cache is a cache protocol weaker than Coherence, but which preserves causality. It relies on the Location Consistency (LC) model. The basic philosophy behind LC is to maintain a unique view of memory only if there is a reason to. Other ordinary memory accesses may be observed in any order by the other processors of the computer system. ☐ The motivation to stand against cache coherence, relies on underestimated lim- itations implied on system design by coherence. Observations presented in this thesis, demonstrates that coherence eliminates the possibility of having a directory based pro- tocol in practice since size of such directory grows linearly with number of cores. In addition, coherence adds implicit latency in many cases to the protocol. ☐ This thesis presents LCCSim, a simulation framework to compare cache proto- col based on location consistency against cache coherence protocols. A comparative analysis between the MESI and MOESI coherence protocols is provided, and pit them against LC-Cache. Both MESI and MOESI consistently generate more on-chip trac compared to LC cache since transitions in LC cache are done locally. However, LC cache degrades total latency of accesses as it does not take the advantage of cache to cache forwarding. Additionally, LC cache cannot be considered a true implementation based on LC since it does not behave according to the memory model. The following summarizes the contributions of this thesis: 1.Detailed specication of LC cache protocol, covering the missing aspects in the original paper. 2.A simulation framework to compare cache protocols based on LC against cache coherence protocols. 3.Extensive analysis of LC cache protocol, leading to discovery of several weak- nesses. 4.Demonstrating features for an ecient cache protocol, truly based on location consistency.

Directory-based cache consistency protocols have the potential to allow shared-memory multiprocessors to scale to a large number of processors. While many variations of these coherence schemes exist in the literature, they have typically been described at a rather high level, making adequate evaluation difficult. This paper explores the implementation issues of directory-based coherency strategies by developing a design at the level of detail needed to write a memory system functional simulator with an accurate timing model. The paper presents the design of both an invalidation coherency protocol and the associated directory/memory hardware. Support is added to prevent deadlock, handle subtle consistency situations, and implement a proper programming model of multiprocess execution. Extensions are delineated for realizing a multiple-threaded directory that can continue to process commands while waiting for a reply from a cache. The final hardware design is evaluated in the context of the number of parts required for implementation.

The book illustrates state-of-the-art software solutions for cache coherence maintenance in shared-memory multiprocessors. It begins with a brief overview of the cache coherence problem and introduces software solutions to the problem. The text defines and details static and dynamic software schemes, techniques for modeling performance evaluation mechanisms, and performance evaluation studies.