Memory System Design II - Fundamentals of Computer Organization and Architecture - page 145

Figure 7.10 Associative mapping address translation
page number field and all virtual page numbers stored in the page table. Although
such a search is done associatively, it requires the use of an added hardware
overhead.
A possible compromise between the complexity of the associative mapping and
the simplicity of the direct mapping is the set-associative mapping technique. This
hybrid technique is explained below.
7.2.3. Set-Associative Mapping
Figure 7.11 illustrates the address translation according to the set-associative map-
ping. In this case, the virtual address issued by the processor is divided into three
fields: the tag, the index, and the offset. The page table used in set-associative map-
ping is divided into sets, each consisting of a number of entries. Each entry in the
page table consists of a tag and the corresponding physical page address. Similar
to direct mapping, the index field is used to directly determine the set in which a
search should be conducted. If the number of bits in the index field is S, then the
number of sets in the page table should be 2 S . Once the set is determined, then a
search (similar to associative mapping) is conducted to match the tag field with
all entries in that specific set. If a match is found, then the corresponding physical
page address is extracted and concatenated with the offset field in order to generate
the physical address of the word requested by the processor. If, on the other hand, a
match could not be found, then this represents a page fault. In this case, the MMU
will have to bring the corresponding page from the hard disk, load it into the main
memory, update the corresponding set and indicate the validity of the page. The
translation process is then carried out as explained before.