ESSENTIAL MISSES AND DATA TRAFFIC IN COHERENCE PROTOCOLS

In this paper, we introduce a classification of misses and of componen ts of the data traffic in shared-memory multiprocessors based on inter processor communication. We consider protacols with invalidations, upd ates, and prefetches in systems with infinite and finite caches. We id entify the set of essential misses and the essential traffic, i.e., th e smallest set of misses and the smallest amount of traffic necessary for correct execution. The rest of the misses and of the data traffic is nonessential and could be ignored without affecting the correctness of program execution. To illustrate the classification of misses and traffic, we apply it to a set of parallel scientific programs and obse rve the overhead created by different hardware mechanisms when block s izes and cache sizes are varied. (C) 1995 Academic Press, Inc.