27-06-2012, 11:45 AM
CACHE MODIFICATION
[attachment=25696]
ABSTRACT
Memory hierarchy in a computer system is very much required in order to have better throughput or efficiency. A perfect storage technology would satisfy the following idealisms: Infinite capacity, infinite bandwidth, zero latency, non-volatility and very low implementation cost. Caches play a crucial role in the implementation of memory hierarchy and if a cache is well designed it can satisfy the above idealisms in a close to perfect manner.
A cache is small memory element on the processor chip to hold data so that future requests for the data are served faster. As a cache is on the chip, the latency to look up for data and fetch it is far lesser than looking up in the main memory. The different kinds of caches, Direct Mapped, Fully Associated and N-way set associated caches, provide us varying capacity and bandwidth and can be used efficiently as per the needs of the applications.
Our project is to implement the Two-Way Set Associative Cache on the PLP, replacing the existing Direct Mapped Cache and to check the performance of the new cache. Performance is to check how much percent will be the hit rate of Two-Way Set Associative Cache for the designed parameters.
THE IDEA OF A CACHE
The references to a memory at any given time intervals tend to be confined within a few localized areas in memory. This phenomenon referred to as the locality of reference is observed in a large number of typical programs. With a typical computer program flow in a straight line, loops and subroutine calls are encountered more or less very frequently. Once a program loop is executed, the CPU repeatedly refers to the instructions in the memory that constitute this loop. Every time a subroutine is called, the memory is accessed to fetch the set of instructions corresponding to the subroutine. Thus there is localization of reference in the memory to fetch instructions. There is also a tendency of degree of localization when references to data are done. There are table-lookup procedures that repeatedly refer to the memory portion where the table is stored. The procedures which are iterative refer to a common memory location and number arrays, all confined to local portion of the memory. All these observations show that over a short interval of time, the addresses generated through a typical program refer to a few localized areas of memory repeatedly, while the remainder of the memory access is relatively infrequent.
Thus the average memory access time can be reduced if the active portions of the data and program are placed in a small yet fast memory. This small fast memory is called the cache memory which reduces the total execution time of the program. It resides between the CPU and the main memory. Cache form the fastest component in the memory hierarchy.
By keeping the most frequently accessed instructions in the fast cache memory, the average memory access time will approach the access time of the cache. This forms the basic fundamental idea and the purpose. A large proportion of the memory requests will be found in the fast cache memory because of the principle of locality of reference.
What basically happens in a cache can be explained as follows: The cache is examined every single time the CPU needs to access memory. If the desired word is found in the cache, there is a cache hit and the word is read out of the cache. If the desired word addressed by the CPU is not found in the cache, there is a cache miss and the word has to be read out of the main memory into the cache and then from the cache to the CPU. A block of words now accessed now
from the main memory are brought onto the cache. This is done so that the future references find the data in the fast cache memory.
Basically the hit ratio is the ratio of number of hits divided by the total number of CPU references to the memory (both hits and misses).
Thus if the hit ratio is high enough and the CPU accesses the fast cache memory instead of the main memory, the average access time is almost equal to access time of the fast cache.
The transformation and mapping of data from the main memory onto the cache are done through practical procedures considering the organization of the cache memory.
DIRECT MAPPED CACHE
In this type of cache, the n bit memory address is divided into k bit index field and (n-k) bit tag field. The main memory contains 2^n words and the cache contains 2^k words. The direct mapped cache uses n bit address to access the main memory and k bit address to access the cache.
Each data word in the cache holds data and the tag associated with it. Whenever new data comes into the cache, the tag bits are stored along with the data brought in. When the processor makes a memory request, the index field is used to access the cache. The tag field of the processor generated address is compared with the tag bits stored alongside the data. If both the tag bits match, it is a ‘cache hit’ and the required data is present in the cache. If the tag bits do not match, it is a ‘cache miss’ and the required data, is not present in the cache and the data should be brought in from the main memory. The disadvantage of this type of cache is that, the hit ratio drops when two or more words having the same index but different tags are accessed repeatedly.
The cache memory that is presently in the PLP system is a direct mapped cache and it is shown in Fig.1. It is an 8KB unified, write allocate, write through and single level cache. Since it is unified, both the data and the instructions are stored in the same cache. There is only one level of cache. In a write through cache, each write into the cache is simply propagated to the higher level. This is a simple approach because correctness of the data is always maintained and there is no ambiguity about which copy of data is the correct one.
When there is write miss, write allocate policy is used which simply implies fetching such a block and installing it into the cache.
TWO-WAY SET ASSOCIATIVE CACHE
Our project tries to replace the existing Direct Mapped Cache into a Two-Way Set Associative Cache. Fig. 2 gives a brief description of how a Two-Way Set Associative Cache works.
Set Associative Cache is a compromise between direct cache and fully associative cache which uses both indexing and associative search as shown in the Fig. 2. The address is divided into tag, index and block offset bits. The index part of the address is used to index into any one of the two-set blocks, while the entries within the set is searched with the tag part of the address.
When compared to a direct mapped cache, the advantage of set associative cache is that it allows us to store two data at the same index thus increasing the capacity for the given N-bit address. The advantage of this over fully associative cache is that it provides some flexibility in placing the data without incurring the complexity of fully associated cache (has to search all of the entries in order to get the desired data).
[attachment=25696]
ABSTRACT
Memory hierarchy in a computer system is very much required in order to have better throughput or efficiency. A perfect storage technology would satisfy the following idealisms: Infinite capacity, infinite bandwidth, zero latency, non-volatility and very low implementation cost. Caches play a crucial role in the implementation of memory hierarchy and if a cache is well designed it can satisfy the above idealisms in a close to perfect manner.
A cache is small memory element on the processor chip to hold data so that future requests for the data are served faster. As a cache is on the chip, the latency to look up for data and fetch it is far lesser than looking up in the main memory. The different kinds of caches, Direct Mapped, Fully Associated and N-way set associated caches, provide us varying capacity and bandwidth and can be used efficiently as per the needs of the applications.
Our project is to implement the Two-Way Set Associative Cache on the PLP, replacing the existing Direct Mapped Cache and to check the performance of the new cache. Performance is to check how much percent will be the hit rate of Two-Way Set Associative Cache for the designed parameters.
THE IDEA OF A CACHE
The references to a memory at any given time intervals tend to be confined within a few localized areas in memory. This phenomenon referred to as the locality of reference is observed in a large number of typical programs. With a typical computer program flow in a straight line, loops and subroutine calls are encountered more or less very frequently. Once a program loop is executed, the CPU repeatedly refers to the instructions in the memory that constitute this loop. Every time a subroutine is called, the memory is accessed to fetch the set of instructions corresponding to the subroutine. Thus there is localization of reference in the memory to fetch instructions. There is also a tendency of degree of localization when references to data are done. There are table-lookup procedures that repeatedly refer to the memory portion where the table is stored. The procedures which are iterative refer to a common memory location and number arrays, all confined to local portion of the memory. All these observations show that over a short interval of time, the addresses generated through a typical program refer to a few localized areas of memory repeatedly, while the remainder of the memory access is relatively infrequent.
Thus the average memory access time can be reduced if the active portions of the data and program are placed in a small yet fast memory. This small fast memory is called the cache memory which reduces the total execution time of the program. It resides between the CPU and the main memory. Cache form the fastest component in the memory hierarchy.
By keeping the most frequently accessed instructions in the fast cache memory, the average memory access time will approach the access time of the cache. This forms the basic fundamental idea and the purpose. A large proportion of the memory requests will be found in the fast cache memory because of the principle of locality of reference.
What basically happens in a cache can be explained as follows: The cache is examined every single time the CPU needs to access memory. If the desired word is found in the cache, there is a cache hit and the word is read out of the cache. If the desired word addressed by the CPU is not found in the cache, there is a cache miss and the word has to be read out of the main memory into the cache and then from the cache to the CPU. A block of words now accessed now
from the main memory are brought onto the cache. This is done so that the future references find the data in the fast cache memory.
Basically the hit ratio is the ratio of number of hits divided by the total number of CPU references to the memory (both hits and misses).
Thus if the hit ratio is high enough and the CPU accesses the fast cache memory instead of the main memory, the average access time is almost equal to access time of the fast cache.
The transformation and mapping of data from the main memory onto the cache are done through practical procedures considering the organization of the cache memory.
DIRECT MAPPED CACHE
In this type of cache, the n bit memory address is divided into k bit index field and (n-k) bit tag field. The main memory contains 2^n words and the cache contains 2^k words. The direct mapped cache uses n bit address to access the main memory and k bit address to access the cache.
Each data word in the cache holds data and the tag associated with it. Whenever new data comes into the cache, the tag bits are stored along with the data brought in. When the processor makes a memory request, the index field is used to access the cache. The tag field of the processor generated address is compared with the tag bits stored alongside the data. If both the tag bits match, it is a ‘cache hit’ and the required data is present in the cache. If the tag bits do not match, it is a ‘cache miss’ and the required data, is not present in the cache and the data should be brought in from the main memory. The disadvantage of this type of cache is that, the hit ratio drops when two or more words having the same index but different tags are accessed repeatedly.
The cache memory that is presently in the PLP system is a direct mapped cache and it is shown in Fig.1. It is an 8KB unified, write allocate, write through and single level cache. Since it is unified, both the data and the instructions are stored in the same cache. There is only one level of cache. In a write through cache, each write into the cache is simply propagated to the higher level. This is a simple approach because correctness of the data is always maintained and there is no ambiguity about which copy of data is the correct one.
When there is write miss, write allocate policy is used which simply implies fetching such a block and installing it into the cache.
TWO-WAY SET ASSOCIATIVE CACHE
Our project tries to replace the existing Direct Mapped Cache into a Two-Way Set Associative Cache. Fig. 2 gives a brief description of how a Two-Way Set Associative Cache works.
Set Associative Cache is a compromise between direct cache and fully associative cache which uses both indexing and associative search as shown in the Fig. 2. The address is divided into tag, index and block offset bits. The index part of the address is used to index into any one of the two-set blocks, while the entries within the set is searched with the tag part of the address.
When compared to a direct mapped cache, the advantage of set associative cache is that it allows us to store two data at the same index thus increasing the capacity for the given N-bit address. The advantage of this over fully associative cache is that it provides some flexibility in placing the data without incurring the complexity of fully associated cache (has to search all of the entries in order to get the desired data).