Frequent value locality and value-centric data cache design

By studying the behavior of programs in the SPECint95 suite we observed tha t six out of eight programs exhibit a new kind of value locality, the frequ ent value locality, according to which a few values appear very frequently in memory locations and are therefore involved in a large fraction of memor y accesses. In these six programs ten distinct values occupy over 50% of al l memory locations and on an average account for nearly 50% of all memory a ccesses during program execution. This observation holds for smaller blocks of consecutive memory locations and the set of frequent values remains qui te stable over the execution of the program. In the six benchmarks with frequent value locality, on an average 50% of al l cache misses occur during the reading or writing of the ten most frequent ly accessed values. We propose a new data cache structure, the frequent val ue cache (FVC), which employs a value-centric approach to caching data loca tions for exploiting the frequent value locality phenomenon. FVC is a small direct-mapped cache which is dedicated to holding only frequently occurrin g values. The value-centric nature of FVC enables us to store data in a com pressed form where the compression is achieved by encoding the frequent val ues using a few bits. Moreover this simple compression scheme preserves the random access to data values in a cache line. Our experiments demonstrate that by augmenting a direct mapped cache (DMC) with a direct mapped FVC of size no more than 3 Kbytes we can obtain reduct ions in miss rates ranging from 1% to 68%. In fact we observed that higher reductions in miss rates can be achieved by augmenting a DMC with a small F VC as opposed to doubling the size of DMC for the 124.m8 8ks im and 134.per 1 benchmarks.