From: mash@mash.engr.sgi.com (John R. Mashey)
Newsgroups: comp.arch
Subject: Re: Direct Mapped vs. Set Assoc.
Date: 3 Jun 1997 20:10:01 GMT

Note that MIPS has built several chips that used set-associative,
external SRAM-based caches.
The R8000 used an external control to get a 4-set-associative cache.
The R10K supports a pseudo 2-set-associative design, i.e., with
hint bits to guess the way to fetch first.

Q: Why do this?
Everybody knows that while the hit rate improves with set-associativity,
it doesn't improve as much as the caches get bigger.

A: for certain kinds of code, such as vector or matrix technical
code, if you graph achieved performance (% of peak) versus the array sizes on
a direct-mapped L2 cache, the usual effect is:
	(a) Performance 1: fits in L1.
	(b) Smooth drop to performance 2, where fits in L2, but not L1.
	(c) Smooth drop to  DRAM speed, where nothing fits
[Yes, this is a serious oversimplification, and we know that code that can be
cache-blocked can be made to perform well even as the array sizes go up, etc],
but there is also:
	(d) Smooth curve is marred by occasional drastic drops where
	vectors line up to make cache lines clash, over large amounts
	of data.

In this case (and I've had customers draw this kind of curve for me
several times, or else they were about to draw it, and I drew it first...),
the *average* performance of a set-associative L2 cache, measured across
a wide range of sizes, is only slight better than that of the direct-mapped
L2 cache ... but the predictability and "comfort factor" is much higher,
i.e., the set-associativity (especially 4-way, but even 2-way) smooths
the curves back out again.

Customers sometimes go absolutely nuts over the spikey behavior,
especially if they want to run a job overnight, and it suddenly takes
2X longer, as happens...

This is the memory-space+throughput analog of a typical real-time
problem: average performance is important, but the non-existence of
outliers is more important than you'd expect.

--
-john mashey    DISCLAIMER: <generic disclaimer: I speak for me only...>
EMAIL:  mash@sgi.com  DDD:    415-933-3090	FAX: 415-967-8496
USPS:   Silicon Graphics/Cray Research 6L-005,
2011 N. Shoreline Blvd, Mountain View, CA 94043-1389