214 Computer Architecture and Organization
7.4.12 Fully Associative Cache
Set associative caches are generally two-way or four-way and induce some amount of restriction against
the same lines from too many pages. A fully associative cache is free from this restriction and is con-
trolled in a different method. In a fully associative cache, any line from main memory may be placed
anywhere in the cache. The complete address is preserved as the tag address within the cache controller.
Therefore, all preserved addressed are searched and compared at the time of responding to the proces-
sor’s request for any memory content, To make the response faster, the search within controller is per-
formed through hardware mechanism.
7.4.13 Replacement Algorithms
Any type of cache memory would remain empty when the computer is initially switched on and
gets lled slowly by instructions and data as the work progresses. Therefore, at some stage of
its operation, the cache becomes full, and to write a new line in cache, some old line must be
destroyed. In direct mapped cache, there is no other alternative but to use the dedicated line number
and its speci c location in cache. However, the set-associative and fully associative cache mecha-
nism offers some exibility in this respect. Several algorithms are available to solve this problem.
Some of them are:
R Least recently used or LRU
R Least frequently used or LFU
R First in rst out or FIFO.
To implement least recently used algorithm, a LRU bit is provided within the cache controller for
set associative cache. This LRU bit is set when any line of cache is referred and other LRU bit(s) of the
same line is (are) cleared. At the time of rewriting, the portion with its LRU bit is 0 is selected. A counter
is necessary for keeping the record of the frequency of usage in case of LFU algorithm’s implementa-
tion. For FIFO algorithm, a circular buffer is necessary.
Figure 7.8 Example of two-way set associative cache
M07_GHOS1557_01_SE_C07.indd 214M07_GHOS1557_01_SE_C07.indd 214 4/29/11 5:12 PM4/29/11 5:12 PM
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.