Modelling and Validation of Shared Memory Coherency Protocols

We present an analytical model of a cache coherent shared-memory multiprocessor and compare the results obtained with those from an execution-driven simulation of the same system. Our objective is to evaluate the accuracy of analytical models of this type of system, and in particular to identify the principal sources of error in the modelling of the coherency protocol. The analytical model first derives equilibrium cache line state probabilities which are then used to determine the expected long term message traffic generated by each coherency operation. These traffic rates in turn form the inputs to a queueing model of the processing nodes. Performance measurements such as processor and bus utilisations, mean queue lengths and read/write latency then follow. Validation of the model using synthetic workloads that exercise the whole of a portion of distributed memory of known size shows excellent agreement with respect to simulation. We also consider a "real" benchmark, taken from the S..