In a direct mapped
cache, memory addresses are directly mapped onto cache addresses. Every memory address has exactly one position, which it shares with other memory addresses (with the +(A mod n), +2(A mod n),... all in all A shares it cache position with m : n other memory addresses, when m is the number of memory locations).
This makes accessing the cache pretty easy, as if a block is cached then the
cache address C for a memory address A is C = A mod n. The
tag saves the rest of the address: For example we have
32 bit memory addresses. If we have a cache which can save 256 32
bit words, then the tag is 24 bit wide ( the lower 8 bits of the address is the index into the cache (actually only bits 2 till 8, as the lowest two bits are byte indexes)).
A cache location consists of the data, the tag and the valid bit ( in this case 32 bit for the
data + 24 bit for the tag).
Now how does such a cache look like?
We use a small cache and a small memory. The memory consists of 256 Bytes and our cache has got 8 elements. The tag has to be 8-3=5 bits wide.
Nr V Tag Data
0 1 00110 00000001
1 1 00110 00000010
2 0 00000 00000000
3 0 00000 00000000
4 1 10000 00000011
5 0 00000 00000000
6 0 00000 00000000
7 0 00000 00000000
In this cache only three elements are used. The first two elements contain bytes from the addresses 00110000 and 00110001 (recognize the
tag and the
index in this addresses).
If we want to read something from memory the cache is checked first. The lower bits are used as an index. Then we check if the cache element is valid and if the tag is correct. If this is the case, we read from cache, if not the element is read from memory and written into cache (overwriting an existing entry).
Writing is easier: if something is written, it is written into memory and cache (this is called
write-through cache).
Sources:
Computer Organization & Design: The Hardware / Software Interface, David A. Patterson and John L. Hennessy, Morgan Kaufmann Publishers, San Francisco, California
Technische Grundlagen der Informatik II: Script, Prof. Dr. Michael Gössel, University of Potsdam
Spim Tutorial: Einführung in die Assemblerprogrammierung mit MIPS, Reinhard Nitzsche, avaiable online
Grundlagen der Digitaltechnik, Prof. Dr.-Ing. Dr.-Ing h.c. Dr. h.c. Hans Martin Lipp, Oldenbourg Verlag, München and Wien
Technische Informatik I, Wolfram Schiffmann and Peter Schmitz, Springer Lehrbuch, Berlin
Spim Documentation, avaiable at http://www.cs.wisc.edu/~larus/spim.html