Modeling finite cache effects in write-invalidate snooping protocols

Most performance studies of cache-based multiprocessors are limited to infi nite caches, mostly because of their simplicity. Since, in practice, no cac he is infinite, it is important to understand how the conclusion of such st udies and existing models are affected when caches have finite sizes. In th is paper, we extend the access burst program model, previously derived in t he context of infinite caches, to cover the case of finite cache systems. I n this new model, replacements are assumed to be uniformly distributed thro ughout the whole program execution. We apply the model to a simple cache co herence protocol and the finite cache effects are modeled by a discrete Mar kov chain. An approximate solution is found for each component of the coher ence overhead. It is shown that the expressions for all components satisfy intuitive properties. The model predictions are also compared with executio n-driven simulations of seven parallel algorithms. Overall, the model is si mple and can be used in exploratory designs of systems for which no traces are available.