Real-Time and Embedded Systems Lab

Relacs - Automatic Relative Competitive Analysis

Relacs is a tool for automatic relative competitive, sensitivity, and relative dominance analysis.

Relacs as a Java applet

Relacs is provided as a Java applet. Unfortunately, due to security vulnerabilities in the Java Virtual Machine, Java applets are not supported anymore by modern web browsers.
In case your web browser still supports Java applets, right below you should see a button to start Relacs.

Relacs as a Stand-alone Command-line Java Application

Relacs may also be used from the command line.

To this end, download the Relacs Java Archive.

To invoke Relacs, run java -jar relacs.jar comp pol:LRU/FIFO asso:product[2,3,4,5][2,4] type:[hit,miss] time:60 on the command line in the directory containing the downloaded Java archive.

With the example parameters given above, Relacs will determine the competitiveness of LRU relative to FIFO for the product of the associativities [2,3,4,5] and [2,4] with a time out of 60 seconds.

Relative Competitiveness, Sensitivity, and Relative Dominance

Relative competitiveness is a generalization of the notion of competitiveness of Sleator and Tarjan [5]: Relative competitive ratios bound the performance of a replacement policy relative to the performance of another policy on any possible workload. For a short introduction and definition of relative competitiveness consider [1]. One of the benefits of relative competitive ratios is that they yield new static cache analyses for policies that could previously not be dealt with, like FIFO. It may also provide a better understanding of the relation between different policies.

The sensitivity of a replacement policy captures how strongly the initial state of the cache may influence the cache's performance in the long run. For details, see [3].

The notion of relative dominance [4] has been introduced by Dorrigiv, Lopez-Ortiz, and Munro. It bounds the difference in miss rates between two policies.

For fixed associativities, Relacs can automatically determine the relative competitiveness, sensitivity, and relative dominance of policies. For details on the automation see [2,3].

Supported Replacement Policies

Relacs currently supports the following replacement policies:

LRU - Least-Recently-Used. Replaces the block whose last accesses is least recent.
FIFO - First-In First-Out, also known as Round-Robin. Replaces the block which has been in the cache for the longest time.
FWF - Flush-When-Full. If the cache is full and a miss occurs, FWF flushes its entire contents.
PLRU - Pseudo-LRU, a tree-based approximation of LRU.
Transpose - Maintains an order on its contents. The least block in this order is replaced upon a miss. Upon an access, a block exchanges its place with its predecessor in the order. See [5].
MRU - Maintains a bit for each line to remember which lines have recently been used. Replaces a line that has not been recently used. Described in [6].
NonDet - Non-deterministically chooses which block to replace upon a miss. A policy is k-competitive relative to NonDet if and only if it is k-competitive relative to OPT.
OPT - Optimal replacement, also known as BEL and MIN. In contrast to the other policies, OPT is an offline policy, i.e. it bases its decisions not only on the past accesses but also on future accesses. Being optimal, OPT is 1-competitive relative to any policy.

It is quite easy to extend Relacs to support further policies. If you are interested in a particular policy not listed here, please let us know.

References

"Relative Competitiveness of Replacement Policies" (extended abstract), J. Reineke, D. Grund. In SIGMETRICS '08: Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, 2008.
"Relative Competitive Analysis of Cache Replacement Policies", J. Reineke, D. Grund. In LCTES '08: Proceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems, 2008.
"Sensitivity of Cache Replacement Policies", J. Reineke, D. Grund. Reports of SFB/TR 14 AVACS 36, March 2008.
"On the Relative Dominance of Paging Algorithms", R. Dorrigiv, A. Lopez-Ortiz, J. Ian Munro. In ISAAC '07: 18th International Symposium on Algorithms and Computation, 2007.
"Amortized efficiency of list update and paging rules", D. D. Sleator, R. E. Tarjan. Commun. ACM, 28(2), 1985.
"Performance evaluation of cache replacement policies for the SPEC CPU2000 benchmark suite", H. Al-Zoubi, A. Milenkovic, and M. Milenkovic. In ACM-SE 42: Proceedings of the 42nd annual Southeast regional conference, 2004.