Lecture_17_Cache Memory Organization

8 Cache Memory Organization
There are three main different organization techniques used for cache memory. The
three techniques are discussed below. These techniques differ in two main aspects:
1. The criterion used to place, in the cache, an incoming block from the main memory.
2. The criterion used to replace a cache block by an incoming block.
8.1 Direct Mapping
This is the simplest among the three techniques. Its simplicity stems from the fact that it places an incoming main memory block into a specific fixed cache block location. The placement is done based on a fixed relation between the incoming block number, i, the cache block number, j, and the number of cache blocks, N:

j = i mod N

Example 1: Consider, for example, the case of a main memory consisting of 4K blocks, a cache memory consisting of 128 blocks, and a block size of 16 words. Figure 35 shows the division of the main memory and the cache according to the direct-mapped cache technique. As the figure shows, there are a total of 32 main memory blocks that map to a given cache block. For example, main memory blocks 0, 128, 256, 384, . . . , 3968 map to cache block 0. We therefore call the direct-mapping technique a many-to-one mapping technique.






























The main advantage of the direct-mapping technique is its simplicity in determining where to place an incoming main memory block in the cache. Its main disadvantage is the inefficient use of the cache. This is because according to this technique, a number of main memory blocks may compete for a given cache block even if there exist other empty cache blocks. This disadvantage should lead to achieving a low cache hit ratio.
According to the direct-mapping technique, the address issued by the processor interprets by dividing the address into three fields as shown in Figure 36. The lengths, in bits, of each of the fields in Figure 36 are:
1. Word field = log2 B, where B is the size of the block in words.
2. Block field = log2 N, where N is the size of the cache in blocks.
3. Tag field = log2 (M/N), where M is the size of the main memory in blocks.
4. The number of bits in the main memory address = log2 (B × M)

It should be noted that the total number of bits as computed by the first three equations should add up to the length of the main memory address. This can be used as a check for the correctness of your computation.









Example 2: Compute the above four parameters for Example 1.
Word field = log2 B = log2 16 = log2 24 = 4 bits
Block field = log2 N = log2 128 = log2 27 = 7 bits
Tag field = log2(M/N) = log2(22 × 210/27) = 5 bits
The number of bits in the main memory address = log2 (B × M) = log2 (24 × 212) = 16 bits.


8.2 Fully Associative Mapping
According to this technique, an incoming main memory block can be placed in any available cache block. Therefore, the address issued by the processor need only have two fields. These are the Tag and Word fields. The first uniquely identifies the block while residing in the cache. The second field identifies the element within the block that is requested by the processor. the address issued by the processor is interpreted by dividing it into two fields as shown in Figure 37. The length, in bits, of each of the fields in Figure 37 are given by:
1. Word field = log2 B, where B is the size of the block in words
2. Tag field = log2 M, where M is the size of the main memory in blocks
3. The number of bits in the main memory address = log2 (B × M)







Example 3: Compute the above three parameters for a memory system having the
following specification: size of the main memory is 4K blocks, size of the cache is
128 blocks, and the block size is 16 words. Assume that the system uses associative
mapping.
Word field = log2 B = log2 16 = log2 24 = 4 bits
Tag field = log2 M = log2 22 × 210 = 12 bits
The number of bits in the main memory address = log2 (B × M) = log2(24 × 212) = 16 bits.

8.3 Set-Associative Mapping
In the set-associative mapping technique, the cache is divided into a number of sets. Each set consists of a number of blocks. A given main memory block maps to a specific cache set based on the equation s = i mod S, where S is the number of sets in the cache, i is the main memory block number, and s is the specific cache set to which block i maps. However, an incoming block maps to any block in the assigned cache set. Therefore, the address issued by the processor is divided into three distinct fields. These are the Tag, Set,
and Word fields. The Set field is used to uniquely identify the specific cache set that ideally should hold the targeted block. The Tag field uniquely identifies the targeted block within the determined set. The Word field identifies the element (word) within the block that is requested by the processor. According to the set-associative mapping technique, the address issued by the processor is interprets by dividing it into three fields as shown in Figure 38. The length, in bits, of each of the fields of Figure 38 is given by

1. Word field = log2 B, where B is the size of the block in words
2. Set field = log2 S, where S is the number of sets in the cache
3. Tag field = log2 (M/S), where M is the size of the main memory in blocks. S = N/Bs, where N is the number of cache blocks and Bs is the number of blocks per set
4. The number of bits in the main memory address = log2 (B × M)