Search

A stack distance of a reference is the depth from which the reference must be extracted from a stack. It has been widely applied to a variety of applications utilizing temporal locality information. However, calculating an exact stack distance requires significant computational complexity that is impractical for online production systems. This paper proposes an efficient algorithm that approximates a stack distance based on workload characteristics. The proposed algorithm utilizes two simple reference metrics: inter-reference distance and a quasi-unique reference count. More importantly, its approximation algorithm requires surprisingly simple calculation. Consequently, it significantly reduces computational overhead while exhibiting exceptional accuracy and runs extremely fast. Moreover, it allows configurable parameters for performance optimization by making optimal use of workload characteristics. Our extensive experiments with diverse realistic workloads demonstrate our stack distance approximation algorithm outperforms the current state-of-the-art algorithm with higher accuracy ( $3.7\times $ ), lower memory footprint ( $3.05\times $ ) and fast execution (less than 0.05 seconds) on average. In addition, with configuration parameters, our refined algorithm can achieve a 28% average additional accuracy improvement.

Though various applications such as flash memory, cache, storage systems, and even indexing for enterprise big data search, adopt hot data identification schemes, relatively little research has been expended into holistically examining alternative strategies. Rather, researchers tend to classify hot data simplistically by considering one or more frequency metrics, thereby disregarding recency, which is also an important consideration. In practice, different workloads mandate different treatment to achieve effective hot data decisions. This paper proposes a dynamic hot data identification scheme that adopts a workload stack distance approximation. Stack distance is a good recency measure, but it traditionally requires high computational complexity as well as additional space. Since stack distance calculation efficiency is a core component for our dynamic feature design, this paper additionally proposes a stack distance approximation algorithm that significantly reduces both computation and space requirements. To our knowledge, the proposed scheme is the first dynamic hot data identification scheme which judiciously assigns more weight to either recency or frequency based on workload characteristics. Our experiments with diverse realistic workloads demonstrate that our stack distance approximation achieves excellent accuracy (up to a 0.1% error rate) and our dynamic scheme improves performance by as much as 49.8%.

The Linear-Scan algorithm (1970), applicable to priority replacement policies, computes stack distances and the number of misses incurred on a given address trace, for all cache sizes, in time O( V) per access. Here, V is the number of distinct (virtual) items referenced within the trace. While the time bound was subsequently lowered to O(log V) for the Least Recently Used policy, no improvements have been reported for general priority policies. This work introduces the class of policies with nearly static priorities (NSP), which encompasses several known policies. The Min-Tree algorithm is proposed for NSP policies, whose performance is quite sensitive to the policy as well as to the address trace. Under suitable probabilistic assumptions, the expected time per access is O(log V). Experimental evidence collected on a mix of 30 benchmarks shows that the Min-Tree algorithm can be significantly faster than Linear-Scan, for interesting policies such as OPT (or Belady), Least Frequently Used (LFU), and Most Recently Used (MRU). Min-Tree can be parallelized to run in time O(log V) using O( V/log V) processors, in the worst case. A more sophisticated Lazy Min-Tree algorithm is also developed with $${O(\sqrt{V}\log V)}$$ worst-case time per access. This bound applies, in particular, to the policies OPT, LFU, and Least Recently/Frequently Used (LRFU), for which the best previously known bound was O( V). Although random replacement is not an NSP policy, the framework developed in this work leads to a stack-distance algorithm with O(log V) expected time per access. [ABSTRACT FROM AUTHOR]