page 1  (27 pages)
2to next section

THE DETECTION AND ELIMINATION OF USELESS

MISSES IN MULTIPROCESSORS

Michel Dubois, Jonas Skeppstedt*, Livio Ricciulli,

Krishnan Ramamurthy, and Per Stenstr?m*

USC Technical Report No. CENG 93-02

Department of Electrical Engineering-Systems
University of Southern California
Los Angeles, CA90089-2562, U.S.A.
(213)740-4475
dubois@paris.usc.edu

*Department of Computer Engineering
Lund University
P.O. Box 118, S-221 00 LUND, Sweden
46-46-107-523
per@dit.lth.se

Abstract

In this paper we introduce a classification of misses in shared-memory multiprocessors
based on inter processor communication. We identify the set of essential misses, i.e., the smallest set of misses necessary for correct execution. Essential misses include cold misses and true sharing misses. All other misses are useless misses and can be ignored without affecting program execution.

Based on the new classification we evaluate miss reduction techniques in hardware,
based on delaying and combining invalidations. We compare the effectiveness of five different protocols for combining invalidations leading to useless misses for cachebased multiprocessors and for multiprocessors with virtual shared memory. In cache based systems these techniques are very effective and lead to miss rates which are close to the minimum. In virtual shared memory systems, the techniques are also effective but leave room for additional improvements.

Keywords: Shared memory multiprocessor, distributed shared memory, cache coherence, consistency models, performance evaluation

To Appear in the 1993 Intl. Symp. on Computer Architecture