Lab 3 -- The Memory Unit

Related Reading

3.1 The Main Memory

The memory unit can be specified at various levels of abstraction. A hardware engineer might describe the implementation using decoders and registers. In our abstract view, we encapsulate the memory in a Java class. The following six files implement an abstraction of the memory unit of a typical hardware machine:

  1. Word: a class that defines machine words.
  2. Data: a class that defines the machine words that can be used as data.
  3. MachineE: a class for all exceptions raised by the machine.
  4. MemoryE: a class for exceptions raised by the memory unit of the machine.
  5. MemoryI: the interface of the memory unit.
  6. Memory: an implementation of the memory unit.

3.2 Caches

Almost every hardware machine includes a cache. We will build a CachedMemory which is an object that behaves like a regular Memory but is optimized to use to a small local cache whenever possible. The idea is that when a fetch operation is requested from the CachedMemory, the operation will first attempt to use the cache; if the cache entry is not valid or missing, the operation will use the main memory as usual.

Here is an example of how a CachedMemory operates. Consider a Memory of size 70 and a cache of size 10. The cache will be represented using three arrays of size 10:

  1. an array Word[] cacheCells,
  2. an array boolean[] valid, and
  3. an array int[] tag.
If we try to fetch the contents of location 32, the following sequence of events take place:
  1. We compute 32 / 10 and 32 % 10 which gives us the tag 3 and the index 2.
  2. We check whether valid[2] is true.
  3. We check whether tag[2] is equal to 3.
  4. If both checks succeed, the cache entry is valid, and there is no need to go to the main memory. We can immediately return cacheCells[2].
  5. If one of the checks fails, then we fetch a Word from location 32 in the main memory (call this Word X), then:
    1. set valid[2] = true,
    2. set tag[2] = 3,
    3. set cacheCells[2] = X, and
    4. return X.
In the case of a store operation, we will always write to both the memory and the cache without performing any checks. Writing to the cache involves the same sequence of calculations to update the arrays valid, tag, and cacheCells.

3.3 To do

Implement a class CachedMemory that extends the class Memory. The constructor for the class CachedMemory should create a Memory and then three local arrays cacheCells, valid, and tag to represent the cache. Initially, every entry in the array valid contains false. The other two arrays may contain arbitrary values.

Visited times since March 23, 1999 (or the last crash).