PERFORMANCE OF PRUNING-CACHE DIRECTORIES FOR LARGE-SCALE MULTIPROCESSORS

Shared-memory multiprocessors known as multis are implemented with sin gle buses and snooping cache protocols. While they have been quite suc cessful, multis are inherently limited to a small number of processors . As systems grow beyond a single bus, the bandwidth requirements of b roadcast operations limit scalability, and hardware support to provide cache coherence without the use of broadcast can become very expensiv e. We describe an approach for maintaining coherence using approximate information held in special-purpose caches, called pruning-caches, th at provides robust performance over a wide range of workloads. The sch eme works because the caches bold information necessary to limit broad casts to those parts of the hierarchy that need to receive it, so info rmation purged from the cache simply results in increased network traf fic, not incorrect behavior. We compare the pruning-cache approach to the more conventional inclusion cache for providing MultiLevel Inclusi on (MLI) in the cache hierarchy, and show that pruning-caches are more cost-effective, and more robust. We also show, through both analysis and simulation, that the k-ary n-cube topology provides scalable, bott leneck-free communication for uniform, point-to-point traffic. We conc lude that pruning-caches can be employed to build a scalable system fo r a broad range of workloads.