Browse Theses

Many cache coherence protocols have been proposed to solve the cache coherence problem in shared memory multiprocessor systems. A number of trace-driven simulation studies have been undertaken to understand the performance trade-offs of these cache coherence protocols. A few analytical studies have also been attempted; however none of these studies explicitly model the interaction between the cache coherence protocols and the replacement policies.

This dissertation performs a comprehensive and detailed analysis of five popular cache coherence protocols in combination with several replacement policies. The methods developed in this dissertation can be extended to analyze cache coherence protocols not considered in this dissertation.

Past analytical studies of cache coherence protocols assumed values for the rates with which a cache controller issues requests on the interconnection network as the replacement policies were not modeled explicitly. We develop a model of the cache that includes details of both the cache coherence protocols and the replacement policies and derive expressions for the rates with which a cache controller issues different types of requests on the interconnection network for a block. When the sequence of memory references generated by different processors are independent but not statistically identical, an iterative procedure is employed to determine the utilization of the interconnection network and the utilization of the individual processors. This procedure is considerably simplified if the sequence of memory references generated by different processors are statistically identical.

We also conduct an analysis of infinite caches that provides a simpler method to compare different cache coherence protocols and their applicability to large-scale shared-memory multiprocessor systems. We conclude from this analysis that the infinite cache assumption simplifies the complexity of the analytical procedure while providing insight into the relative performance of different cache coherence protocols. Closed-form expressions are derived for the rates at which various types of requests are issued by the cache controller at each processor.

We develop a discrete-event simulation model to validate the analytic results. In most of the cases studied, excellent agreement (less than 5% difference) is found between the simulation and the analytical results.