Cache Memory : Cache Organization

Cache is usually designed to be user-transparent therefore in order to locate an item in the cache it is necessary to have some functions which maps the main memory address into cache location. In general, it is likely that most future accesses to main  memory by the processor will be to locations recently accesses. So the cache automatically retains a copy of some of the recently used words from the main memory. If the cache is designed properly, then most of the time the processor will request memory words that are already in the cache. Cache memory implementation depends on multiple aspects such as principle of locality of reference, operations of cache, design aspects and cache bandwidth.

Principle of locality of reference: 

Since code is generally executed sequentially, virtually all programs repeat sections of code and repeatedly access the same or nearby data. This characteristic is embodied in the Principle of Locality, which has been found empirically to be obeyed by most programs. It applies to both instruction references and data references, though it is more likely in instruction references. There are two aspects, firstly is temporal locality in which individual locality once referred are likely to be referenced again in near future. Secondly, spatial locality in which references including the next location is likely to be near the last reference. The Locality of reference is based on two forms, namely :

Temporal Locality : The temporal locality refers to access of that program which is accessed once, would likely to be accessed again. This allocates a reference point of the data accessed in the memory.

Spatial Locality : The spatial locality refers to any data that is in close proximity to the recently accessed data, would be referenced i.e allocation of neighbours in the memory points as there is faster access.

A set of close of addresses are put in cache block for easy access. A pre-determined allocation through locality of reference in computer helps in eradication of memory problems and thus cache memory gets well managed.

Mapping Function :

As there are less number of cache lines then main memory blocks, an algorithm is required for mapping main memory blocks into cache lines. Some way is required for finding which main memory block currently occupies a cache line. The selection of the mapping function represent how the cache is organized. Three techniques are normally used : direct, associative, and set associative.

Direct Mapping : Direct mapping technique maps every block of main memory into only one possible cache line. If a line is previously taken up by a memory block when a new block needs to be loaded, the old block is trashed. An address space is split into two parts index field and tag field. The cache is used to store the tag field whereas the rest is stored in the main memory. Direct mapping`s performance is directly proportional to the Hit ratio.The mapping is represented as follows :

        i = j modulo m

    where
        i = cache line number
        j = main memory block number
       m = number of lines in the cache



The direct mapping method is easy and inexpensive to implement. Its main disadvantage is that there exists a fixed cache location for any given block. So, if a program wants to reference
words repeatedly from two different blocks that map into same line, then the block will be repeatedly swapped in the cache. The hit ratio will also be low.

Associative Mapping : Associative mapping overcomes the disadvantage of direct mapping by permitting each main memory block to be loaded into any line of the cache. Here the cache control logic understand a memory address simply as a tag and a word field. The tag field uniquely acknowledge a block of main memory. To find out whether a block is in the cache, the cache control logic must simultaneously test every line's tag for a match.


with associative mapping, there is a flexibility with which we can select, which block to replace when a new block is read into the cache. For this, replacement algorithms are built to maximize the hit ratio. The main disadvantage of associative mapping is the complex circuitry needed to examine the tags of all cache lines in parallel.

Set-Associative Mapping : The set-associative mapping possess the strengths of both the direct and associative techniques while reducing their disadvantages. Here the cache is divided into v sets, each of which made up of k lines. It is represented by following relationship.

        m = v x k
        i = j modulo v

    where
        i = cache set number
        j = main memory block number
        m = number of lines in the cache

It is termed as k-way set associative mapping. A set-associate scheme works by dividing the cache SRAM into equal sections called cache ways. The cache page size is equal to the size of the cache way. Each cache way is treated like a small direct mapped cache.


To make the explanation clearer, let’s look at a specific example. In this scheme, two lines of memory may be stored at any time. This scheme is less complex than a Associative cache because the number of comparators is equal to the number of cache ways.






Next Topic :

No comments:

Post a Comment