Analysis of sector caches for uni- and multiprocessor systems
Jeffrey B. Rothman, Alan Jay Smith · 1999
This dissertation examines the use of sector caches to provide a more cost-effective and efficient use of cache resources for uniprocessor and multiprocessor systems. A sector cache is a cache in which the block (sector) is divided into several subsectors (subblocks), which are not required to be simultaneously present in the cache. The first part of this dissertation presents Cerberus, an efficient system for simulating the execution of shared-memory multiprocessor programs on a uniprocessor workstation. Using EDS (execution driven simulation), it generates address traces which can be used to drive cache simulations on the fly, eliminating the large disk space requirements needed by trace files. We demonstrate that EDS uses only 5 percent of the total execution cycles when combined with a cache simulator and show that EDS is just as efficient as using trace driven simulation. The second part of this dissertation is a thorough analysis of the design and use of uniprocessor sector caches. We start by creating a workload based on a number of program traces and then we calculate miss ratios for a wide range of sector cache designs. The miss ratios are then used to estimate performance, using typical timings, for a variety of one level and two level cache designs. We find that for single level caches, sector caches are seldom advantageous. For multilevel cache designs with small amounts of storage at the first level caches sector caches can yield significant performance improvements. As a variant to the standard sector cache, we propose a new design, called the sector pool cache, in which subsectors may be shared between sectors, so that the cache data arrays are used much more efficiently. Our results show that the sector pool cache can be an attractive solution for a first level on-chip cache when used in conjunction with a regular second level off-chip sector cache. Sector caches show even better potential for multiprocessors. Sector caches allow the possibility of multiple processors writing to disjoint portions of the same block without interfering with each other, which reduces the amount of false sharing. In the third part of this dissertation, we examine characteristics of multiprocessor memory accesses and use sector caches to reduce bus traffic and execution time. We establish new methods for characterizing cache block reference patterns, and we measure how these patterns change with variation in workload and block size. In addition to our general analysis of reference patterns, we also present a detailed analysis of false sharing and dead sharing in each shared memory multiprocessor program studied. We find that for the programs studied, the worst 10 blocks from each of our traces contribute almost 50% of the false sharing misses and almost 20% of the true sharing misses (on average). To attempt to solve the false and dead sharing problems using hardware, we present a new cache protocol, Minerva, which allows the effective cache block size to vary dynamically. Minerva works using sector caches. Depending on the assumed cache sizes, block sizes, and bus timings, we find that Minerva reduces execution times by 19–40%, averaged over 12 test parallel programs. Our evaluation considers the utility of various other optimizations, compares the use of Minerva with restructuring the code, and considers the extra state bits required. (Abstract shortened by UMI.)