Memory System Design I - Fundamentals of Computer Organization and Architecture - page 112

total of n times access to that element. Based on these assumptions, the average
access time, t av , is given by

þ

mt c þ t m
m

t m
m

þ (n 1)t c t c þ (n 1)t c

t m
nm þ t c

t av ¼ ¼ ¼

n n

A further simplifying assumption to the above expression is to assume that t m ¼ mt c .
In this case the above expression will simplify to

mt c
nm þ t c ¼ t c þ

t c
n ¼

n þ 1

t av ¼ t c

n

The above expression reveals that as the number of repeated accesses n increases, the
average access time will approach t c . This is a significant performance improvement.
It should be clear from the above discussion that as more requests for items that
do not exist in the cache (cache miss) occur, more blocks would have to be brought
to the cache. This should raise two basic questions: Where to place an incoming
main memory block in the cache? And in the case where the cache is totally
filled, which cache block should the incoming main memory block replace? Place-
ment of incoming blocks and replacement of existing blocks are performed accord-
ing to specific protocols (algorithms). These protocols are strongly related to the
internal organization of the cache. Cache internal organization is discussed in the
following subsections. However, before discussing cache organization, we first
introduce the cache-mapping function.

6.2.4. Cache-Mapping Function

Without loss of generality, we present cache-mapping function taking into consider-
ation the interface between two successive levels in the memory hierarchy: primary
level and secondary level. If the focus is on the interface between the cache and main
memory, then the cache represents the primary level, while the main memory rep-
resents the secondary level. The same principles apply to the interface between any
two memory levels in the hierarchy. In the following discussion, we focus our atten-
tion to the interface between the cache and the main memory.
It should be noted that a request for accessing a memory element is made by the
processor through issuing the address of the requested element. The address issued
by the processor may correspond to that of an element that exists currently in the
cache (cache hit); otherwise, it may correspond to an element that is currently resid-
ing in the main memory. Therefore, address translation has to be made in order to
determine the whereabouts of the requested element. This is one of the functions
performed by the memory management unit (MMU). A schematic of the address
mapping function is shown in Figure 6.3.
In this figure, the system address represents the address issued by the processor
for the requested element. This address is used by an address translation function
inside the MMU. If address translation reveals that the issued address corresponds
to an element currently residing in the cache, then the element will be made