Optimizing single-pass simulation techniques for fast cache memory design space exploration in embedded processors

An application’s cache miss rate is used in timing analysis, system performance prediction and in deciding the best cache memory for an embedded system to meet tighter energy, performance and cost constraints. Single-pass simulation allows a designer to find the number of cache misses quickly and accurately on various cache memories. Suchsingle-pass simulation systems have previously relied heavily on cache inclusion properties, which allowed rapid simulation of cache configurations for different applications without using excessive computing resources. Thus far the only inclusion properties discovered were applicable to the Least Recently Used (LRU) replacement policy based caches. However, LRU based caches are rarely implemented in real life due to their circuitcomplexity at larger cache associativities. Embedded processors typically use a FIFO or Pseudo LRU (PLRU) replacement policy in their caches instead, for which there are no full inclusion properties to exploit. No other mechanism has also been discovered for these cache replacement policies to speedup the single-pass simulation. As a result, the replacement policies that do not show inclusion properties did not attract the cache simulator designers and researchers even though there was a great need to simulate these policies. This thesis describes a complete solution to accelerate the trace driven single-pass simulation of the cache replacement policies regardless of their capability to show inclusion properties. The solution aims to maintain low space consumption and minimal use of computing resources. For these purposes two potential speedup mechanisms have been analyzed: (i) Different methods of representing caches during simulation (or data structure based speedup); and, (ii) Replacement policy based speedup (such as cache inclusion properties). To make a significant acceleration during a single-pass simulation, two smart data structures, “Wave pointers” and ”Central Look-up Table”, have been presented inthis dissertation. These two cache configuration representation techniques can dramatically reduction the time to search an address content in a cache memory and to reflect the changes made after each cache access. Utilizing wave pointers and central look-up table, simulation can be performed up to 40 times and 57 times faster respectively compared to a single cache memory simulator DineroIV . To reduce space consumption to speedup thesingle-pass simulation process, a new cache property, “Intersection property”, has also been introduced. The intersection properties can help to predict the cache status during single-pass simulation, which can help to reduce enormous amount of simulation time. Using the intersection properties, up to 97% cache hits can be predicted. Using the speedup mechanisms discovered, a group of efficient and fast single-passcache simulators namely “SuSeSim”, “DEW”, “SCUD”, “CIPARSim” and “PSAICO” are presented for LRU, FIFO and PLRU caches. These simulators outperform the available conventional simulators significantly