Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!leah!bingvaxu!sunybcs!rutgers!att!mtuxo!mtgzz!drutx!druhi!terrell
From: terrell@druhi.ATT.COM (TerrellE)
Newsgroups: comp.sys.ibm.pc
Subject: Re: Cache types and uses ?
Summary: Cache Organization
Message-ID: <4127@druhi.ATT.COM>
Date: 7 Apr 89 15:27:50 GMT
References: <22673@agate.BERKELEY.EDU>
Organization: AT&T, Denver, CO
Lines: 44


Cache memories exploit the fact that most programs exhibit locality
of memory references.  Locality of memory reference means that if a given
memory location is accessed, it is likely to be accessed again soon.  The
memory location could be a program variable or an instruction in the program's
executable code.

Consider a program that repeatedly executes a tight loop.  Inside of this
loop, a small set of variables are referenced.  This program will tend to
speed up significantly if a cache is in use, since there is great locality
of reference in the program code (the same instructions are referenced again
and again) as well as the program's variables (the same variables are 
repeatedly referenced).

A program that will experience much less speedup is one that is very
branchy, and has very scattered variable references.

Cache performance depends primarily on locality of memory references, 
and (except in pathelogical cases) is not greatly affected by where the 
program instructions and variables are placed in memory.  However, one 
could decimate cache performance by placing program instructions and 
program variables in memory in a way that the two to use the same 
cache locations at the same time (i.e. thrash), but this typically 
doesn't happen in ordinary programs.

If you want to find out about different cache organizations (direct-mapped,
set associative, etc), see:

A. J. Smith, "Cache Memories", Computing Surveys, Vol 14, No. 3, 
Sept. 1982, pp. 473-530.


Smith also wrote a similar (but more up-to-date) article in (if memory serves)
IEEE Computer within the last year.


In summary, ordinary programs tend to exhibit reasonable locality in memory
references for program variables and instructions, and consequently will
tend to experience a significant speedup.  The locality of memory references
is more important to cache performance than where the program instructions 
and variables are placed in memory, except in pathelogical cases. 


Eric Terrell (att!druhi!terrell)