Quality of control is a critical concern in Cyber-Physical Systems (CPS) which are comprised of multiple intercommunicating control applications. Due to complex timing behaviour of these systems, poor quality of control can lead to catastrophe. Recent studies showed that, conflict miss increment in the processor cache memory shared by concurrently running control applications can degrade control quality in CPS significantly. Increasing cache associativity can help to reduce conflict misses. However, the existing reconfigurable cache architectures that allow runtime modification of cache associativity are not capable to guaranty a newly chosen associativity's suitability for the forthcoming control quality requirement. Moreover, they have timing and energy related overheads. In this regard, this paper presents a novel, self-reconfiguring cache memory architecture "SeReMo". When conflict misses increase significantly, SeReMo reconfigures its associativity to better suit the current as well as future control quality demand. To trigger reconfiguration, a low overhead, non-strictly inclusive cache hierarchy-specific approach is used. Configurations with different associativity are generated using modules made of 4 cache lines and 7 special bits. Special replacement policy and indexing scheme are used to suit modular reconfiguration. SPEC CPU 2006 benchmark trace-driven simulation reveals that SeReMo reduces average number of conflict misses per line to 1/12951 of the state-of-the-art reconfigurable cache architecture at maximum (to 1/830 on average). As a result, execution time and energy consumption reduce by 48 hours at maximum (by 2/3 on average) and by 2907 Joules at maximum (86% on average) respectively.

Missing the deadline of an application task can be catastrophic in real-time systems. Therefore, to ensure timely completion of tasks, offline worst-case execution time and schedulability analysis is often performed for such real-time systems. One of the important inputs to this analysis is a safe upper bound of misses in each processor cache memory used by the system. Cache miss prediction techniques have matured significantly for private caches in single-core processors; however, remained as a challenge for unified, shared caches in multicore processors. According to prior studies, a task's miss upper bound on a shared cache can be predicted using available private cache prediction techniques only if the shared cache maintains core-based independent static partitions. The problem is, such partitions require the use of infeasible “write-update consistency protocol” and wastes valuable cache space by duplicate caching. In this regard, this paper presents a novel cache replacement policy called “predictable variable isolation in shared antipodal memory (PVISAM).” Its replacement decisions generate virtual core-based partitions that support demand-based runtime size adjustment and line sharing to better utilize space. Moreover, these partitions require no consistency protocol. Tracedriven experimental results for Parsec benchmark applications reveal that performance of a unified shared cache memory improves by 101.68x on average (minimum 1.09x and maximum 1138.50x) when PVISAM is used instead of either the aforementioned write-update protocol-based predictable partitioning or the widely used write-invalidate consistency protocol-based partitioning. PVISAM can improve cache performance by 0.74x on average (minimum 0.02x and maximum 1.12x) compared to having no partitions at all. Both predictable partitioning and PVISAM improve unified, shared cache predictability by 63.44% (minimum 26.89% and maximum 99.99%) and 19.36% (minimum 1.58% and maximum 72.51%) on average compared to no partitions and write-invalidate protocol-based partitioning, respectively. Experimental results for synthetic traces show that PVISAM remarkably improves cache performance and predictability when compared to its three competitors even in scenarios that stress the cache.

In this article, we propose a technique to accelerate nonvolatile or hybrid of volatile and nonvolatile processor cache design space exploration for application specific embedded systems. Utilizing a novel cache behavior modeling equation and a new accurate cache miss prediction mechanism, our proposed technique can accelerate NVM or hybrid FIFO processor cache design space exploration for SPEC CPU 2000 applications up to 249 times compared to the conventional approach.

Hitherto discovered approaches analyze the execution time of a real-time application on all the possible cache hierarchy setups to find the application specific optimal two-level inclusive data cache hierarchy to reduce cost, space and energy consumption while satisfying the time deadline in real-time Multi-Processor Systems on Chip (MPSoC). These brute-force like approaches can take years to complete. Alternatively, application's memory access trace driven crude estimation methods can find a cache hierarchy quickly by compromising the accuracy of results. In this article, for the first time, we propose a fast and accurate application's trace driven approach to find the optimal real-time application specific two-level inclusive data cache hierarchy. Our proposed approach “TRISHUL” predicts the optimal cache hierarchy performance first and then utilizes that information to find the optimal cache hierarchy quickly. TRISHUL can suggest a cache hierarchy, which has up to 128 times smaller size, up to 7 times faster compared to the suggestion of the state-of-the-art crude trace driven two-level inclusive cache hierarchy selection approach for the application traces analyzed.

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 constraints. Single-pass simulation allows a designer to find the number of cache misses quickly and accurately on various cache memories. Such single-pass simulation systems have previously relied heavily on cache inclusion properties, which allowed rapid simulation of cache configurations for different applications. 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 circuit complexity at larger cache associativities. Embedded processors typically use a FIFO replacement policy in their caches instead, for which there are no full inclusion properties to exploit. In this paper, for the first time, we introduce a cache property called the “Intersection Property” that helps to reduce single-pass simulation time in a manner similar to inclusion property. An intersection property defines conditions that if met, prove a particular element exists in larger caches, thus avoiding further search time. We have discussed three such intersection properties for caches using the FIFO replacement policy in this paper. A rapid single-pass FIFO cache simulator “CIPARSim” has also been proposed. CIPARSim is the first single-pass simulator dependent on the FIFO cache properties to reduce simulation time significantly. CIPARSim's simulation time was up to 5 times faster (on average 3 times faster) compared to the state of the art single-pass FIFO cache simulator for the cache configurations tested. CIPARSim produces the cache hit and miss rates of an application accurately on various cache configurations. During simulation, CIPARSim's intersection properties alone predict up to 90% (on average 65%) of the total hits, reducing simulation time immensely.

Embedded systems designers are free to choose the most suitable configuration of L1 cache in modern processor based SoCs. Choosing the appropriate L1 cache configuration necessitates the simulation of long memory access traces to accurately obtain hit/miss rates. The long execution time taken to simulate these traces, particularly separate simulation for each configuration is a major drawback. Researchers have proposed techniques to speed up the simulation of caches with LRU replacement policy. These techniques are of little use in the majority of embedded processors as these processors utilize Round-robin policy based caches. In this paper we propose a fast L1 cache simulation approach, called SCUD (Sorted Collection of Unique Data), for caches with the Round-robin policy. SCUD is a single-pass cache simulator that can simulate multiple L1 cache configurations (with varying set sizes and associativities) by reading the application trace once. Utilizing fast binary searches in a novel data structure, SCUD simulates an application trace significantly faster than a widely used single configuration cache simulator (Dinero IV). We show SCUD can simulate a set of cache configurations up to 57 times faster than Dinero IV. SCUD shows an average speed up of 19.34 times over Dinero IV for Mediabench applications, and an average speed up of over 10 times for SPEC CPU2000 applications.

Increasing the speed of cache simulation to obtain hit/miss rates enables performance estimation, cache exploration for embedded systems and energy estimation. Previously, such simulations, particularly exact approaches, have been exclusively for caches which utilize the least recently used (LRU) replacement policy. In this paper, we propose a new, fast and exact cache simulation method for the First In First Out(FIFO) replacement policy. This method, called DEW, is able to simulate multiple level 1 cache configurations (different set sizes, associativities, and block sizes) with FIFO replacement policy. DEW utilizes a binomial tree based representation of cache configurations and a novel searching method to speed up simulation over single cache simulators like Dinero IV. Depending on different cache block sizes and benchmark applications, DEW operates around 8 to 40 times faster than Dinero IV. Dinero IV compares 2.17 to 19.42 times more cache ways than DEW to determine accurate miss rates.

The pipelined Multiprocessor System on Chip (MPSoC) paradigm is well suited to the data flow nature of streaming applications. A pipelined MPSoC is a system where processing elements (PEs) are connected in a pipeline. Each PE is implemented using one of a number of processor configurations (configurations differ by instruction sets and cache sizes) available for that PE. The goal is to select a pipelined MPSoC with a mapping of a processor configuration to every PE. To estimate the run-time of a pipelined MPSoC, designers typically perform cycle-accurate simulation of the whole pipelined system. Since the number of possible pipelined implementations can be in the order of billions, estimation methods are necessary. In this paper, we propose two methods to estimate the runtime of a pipelined MPSoC, minimizing the use of slow cycle-accurate simulations. The first method estimates the runtime of the pipelined MPSoC, by performing cycle accurate simulations of individual processor configurations (rather than the whole pipelined system), and then utilizing an analytical model to estimate the runtime of the pipelined system. In the second method, runtimes of individual processor configurations are estimated using an analytical processor model (which uses cycle-accurate simulations of selected configurations, and an equation based on ISA and cache statistics). These estimated runtimes of individual processor configurations are then used to estimate the total runtime of the pipelined system. By evaluating our approach on three benchmarks, we show that the maximum estimation error is 5.91% and 16.45%, with an average estimation error of 2.28% and 6.30% for the first and second method respectively. The time to simulate all the possible pipelined implementations (design points) using cycle-accurate simulator is in the order of years, as design spaces with at least 1010design points are considered in this paper. However, the time to simulate all processor configurations individually (first method) takes tens of hours, while the time to simulate a subset of processor configurations and estimate their runtimes (second method) is only a few hours. Once these simulations are done, the runtime of each pipelined implementation can be estimated within milliseconds.