Page 177 -

4.7 / KEY TERMS, REVIEW QUESTIONS, AND PROBLEMS 147

4.4 List the following values:
a. For the direct cache example of Figure 4.10: address length, number of address-
able units, block size, number of blocks in main memory, number of lines in cache,
size of tag
b. For the associative cache example of Figure 4.12: address length, number of ad-
dressable units, block size, number of blocks in main memory, number of lines in
cache, size of tag
c. For the two-way set-associative cache example of Figure 4.15: address
length, number of addressable units, block size, number of blocks in main
memory, number of lines in set, number of sets, number of lines in cache, size
of tag
4.5 Consider a 32-bit microprocessor that has an on-chip 16-KByte four-way set-associa-
tive cache.Assume that the cache has a line size of four 32-bit words. Draw a block di-
agram of this cache showing its organization and how the different address fields are
used to determine a cache hit/miss. Where in the cache is the word from memory lo-
cation ABCDE8F8 mapped?
4.6 Given the following specifications for an external cache memory: four-way set asso-
ciative; line size of two 16-bit words; able to accommodate a total of 4K 32-bit words
from main memory; used with a 16-bit processor that issues 24-bit addresses. Design
the cache structure with all pertinent information and show how it interprets the
processor’s addresses.
4.7 The Intel 80486 has an on-chip, unified cache. It contains 8 KBytes and has a four-way
set-associative organization and a block length of four 32-bit words. The cache is or-
ganized into 128 sets. There is a single “line valid bit” and three bits, B0, B1, and B2
(the “LRU” bits), per line. On a cache miss, the 80486 reads a 16-byte line from main
memory in a bus memory read burst. Draw a simplified diagram of the cache and
show how the different fields of the address are interpreted.
16
4.8 Consider a machine with a byte addressable main memory of 2 bytes and block size
of 8 bytes. Assume that a direct mapped cache consisting of 32 lines is used with this
machine.
a. How is a 16-bit memory address divided into tag, line number, and byte
number?
b. Into what line would bytes with each of the following addresses be stored?
0001 0001 0001 1011
1100 0011 0011 0100
1101 0000 0001 1101
1010 1010 1010 1010
c. Suppose the byte with address 0001 1010 0001 1010 is stored in the cache. What
are the addresses of the other bytes stored along with it?
d. How many total bytes of memory can be stored in the cache?
e. Why is the tag also stored in the cache?
4.9 For its on-chip cache, the Intel 80486 uses a replacement algorithm referred to
as pseudo least recently used. Associated with each of the 128 sets of four lines
(labeled L0, L1, L2, L3) are three bits B0, B1, and B2. The replacement algorithm
works as follows:When a line must be replaced, the cache will first determine whether
the most recent use was from L0 and L1 or L2 and L3.Then the cache will determine
which of the pair of blocks was least recently used and mark it for replacement.
Figure 4.20 illustrates the logic.
a. Specify how the bits B0, B1, and B2 are set and then describe in words how they
are used in the replacement algorithm depicted in Figure 4.20.
b. Show that the 80486 algorithm approximates a true LRU algorithm. Hint: Con-
sider the case in which the most recent order of usage is L0, L2, L3, L1.
c. Demonstrate that a true LRU algorithm would require 6 bits per set.