Direct-Mapped Cache

A form of cache in which each memory block from the main store may only ever be placed in one cache block. Each location in main store is directly mapped to a single location in the cache.

This might be done by indexing the cache with the most significant bits of the main store block's address. This means that the remaining address bits must also be stored in the cache, to indicate which of the possible main store blocks is there. These bits are known as the "Tag". Finally a bit is stored for each cached address to show if the address is valid (the "Valid" bit). This is required so that cache locations that are as-yet unused (ie, unfilled by main store locations) are never read.

    One of several different Caches available today. It works by directly mapping certain blocks of memory to one certain block of cache. For instance block 1010010 in memory will always be mapped to block 0010 in the cache, no matter what. That way if you want to look for 1010010 in cache you know exactly where it should be. If it's not there then you know you've just wasted your time and to go to memory.

    One thing to know about how direct-mapped cache is that the location a memory block is mapped to directly depends on its least signifigant bits. So any memory block with the least signifigant bits "0010" will, if its in cache, be in location "0010" in the cache. The most signifigant bits of the memory block are actually stored in the cache itself for reference.

    Of course once a momory block is loaded and it has the same cache location as an old block, the old block is erased and the new put in. You can't store two at once. Also the locations dont have to be 8 bits long, as I used above, I was just using those as an example.

    So now that you have this useless knowledge of how this cache works what do you do with it? I don't know. Go fix the ozone layer problem or something.

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