4-way Set Associative Cache Project Documentation

Author

Mark L. Short

Date

Sept 25, 2014

CITE:

• Modern Processor Design, John Paul Shen, Mikko H. Lipasti, 2005
• Cache, Thomas Finley, May 2000, http://www.cs.cornell.edu/~tomf/notes/cps104/cache.html

ASSIGNMENT:

CMPS 5133 Advanced Computer Architecture Assignment #2 - Memory

Given the following benchmark code running in a four-way associative data cache with 16 blocks of 32 bytes and knowing that an integer variable occupies 4 bytes, and operations follow the usual priority, assume that at each operation the leftmost operand is fetched first and the address of A[0] is zero. Compute the number of cache misses, considering the loop index variable residing in a process register (and involved in the count of the misses) and that arrays A, B, and C reside consecutively in memory.

int A[512], B[512], C[512]
for (i = 0; i < 511, i++)
{
   A[i] = A[i] + B[i] + B[i+1] * C[i]
}

OUTCOME:

The executable compiled from the attached C++ achieves the stated purpose and outputs the results to the console window, with the following caveats:

1. No assumptions were made regarding the address of A[0] being zero.
   As a result, a more involved and accurate four-way associative data cache implementation was required.
2. The attached source code has been run on a x64 bit system, but compiled as a 32bit application. It is has been modified to support x32 / x64.
3. "Handling Updates to a Block" was not considered at this time and would require further implementation.
4. Efforts were made to meaningfully test and debug the algorithms involved in this implementation. Code was added to test the validity of the data returned from cache. Due to the added coding precautions taken, an error was uncovered that would result in the following:

   Misses: 195 (est)
   Hits:  1850 (est)
   Errors:  12
   

5. The error was properly identified and diagnosed to be due to failure to make adjustments to the range of addresses loaded into cache to insure that they all mapped to the same corresponding "tag" + "index" address fields. This was corrected with no errors currently detected.
6. CACHE DESIGN
   • Block size = 32 bytes
   • Block number = 16
   • Number of sets = 4
   • Block organization = (4 way) Set-associative
   • Block replacement policy = FIFO
   • Write policy = not implemented
7. Given the assignment formula of 'A[i] = A[i] + B[i] + B[i+1] * C[i]', the operands were accessed in the following order:
   • B[i+1]
   • C[i]
   • A[i]
   • B[i]
8. The current implementation results in the following final computation output:

   Misses: 192
   Hits:  1852
   Errors:   0