5.1 Cache Analysis



next up previous
Next: 5.2 Analysis of Results Up: 5 Technical Results and Previous: 5 Technical Results and

5.1 Cache Analysis

   To evaluate various cache parameters of all the machines in our experiments we used the program given in problem#5.2 in [18]. The program has been included in the appendix A. This program contains procedures to get an accurate measurements of the user CPU time, a nested loop to read and write memory at different strides and array sizes and another identical loop to subtract the overhead incurred. The average read and write time per access for different array and stride sizes have been plotted on a - graph (Figures 1, 2, 3, 4, 5, 6).
Number of Levels of Cache
From these graphs we can deduce the number of levels of cache for the given system. For instance, if we observe two distinct values where the access time is almost the same for several array sizes and most of the stride sizes, the system has only level one cache. Three such distinct values denote both level one and level two cache.
Cache Size
To find the size of the various caches, we observe that when the array size is increased, the access time stays almost constant with increasing stride size. However at a certain array size, the access increases to a new value and then stays constant with increasing array size. Therefore at this array size, the data does not fit in the current level of memory hierarchy and is now being accessed from the next lower level of the memory hierarchy. Hence this value of array size indicates the size of the current level of memory hierarchy, i.e., first level cache, second level cache or main memory.
Block Size
To find the block size in a first or second level cache, we observe the access time plot for an array size which does not fit in this level of memory hierarchy. We find that the access time increases with the size of stride and then flattens out after a certain stride size. This happens because for every block of data brought in from the next level of memory hierarchy, the number of data accessed decreases as the stride size increases, till we access only one data point per block which is brought in. Increasing the stride size further does not affect the access time because now only those blocks are brought in which have the data to be accessed. Clearly the stride size at which we observe this knee is the block size for that cache. We assume that the block size for the second level cache is always greater than or equal to the block size of the first level cache.
Associativity
If the cache is n way set associative, then the access time for array size greater than the cache size and stride size of or more, the access time will be the same as when the data hits in this cache. For instance, for 21064 ALPHA processors (fig 5, 4), the second level cache is two way associative. Hence for array sizes of more than the size of the second level cache, and a stride size of , both the elements of the array accessed are mapped to the same location in the second level cache and hence the access time is the same as that of a second level cache hit.
TLB and Page Size
We observe that typically, the second level cache access time shows a peak with the increasing stride size for some array sizes which fit in the second level cache. This is due to misses in the TLB. The access time is maximum for a stride size equal to the page size. For smaller stride sizes, more than one data points are accessed per page hence the overhead of a TLB miss is amortized to some extent. For a stride size larger than the page size, the number of misses is smaller because the TLB is fully associative. For an array of size smaller than , there will be no TLB misses and hence the access time curve will be flat with increasing stride size. For strides of size greater than or equal to , there will be no TLB misses and hence the access time will be the same as the second level cache hit time.

 

 


: Cache Analysis Results



next up previous
Next: 5.2 Analysis of Results Up: 5 Technical Results and Previous: 5 Technical Results and



rajeev@eecs.berkeley.edu