The CACHESKEW simulator

Authors: André Seznec, Jérome Hédouin

Contact: André Seznec

Last Modification: Sept. 97

A brief introduction to skewed-associativity
General organization of the simulator
How to test new replacement policies
How to test new mapping functions
The simulator package (as a tar file)
Back to processor architecture research in CAPS team



The CACHESKEW simulator is provided as is in order to serve as a basis to develop cache simulators for testing ideas related to skewed-associative caches. This package has been built in order to be easily modified for being able to test new indexing functions or new replacement policies.


A brief introduction to skewed-associativity

The skewed associative cache is a new organization for multi-bank caches. Skewed-associative caches have been shown to have two major advantages over conventional set-associative caches.
First, at equal associativity degrees, a skewed-associative cache typically exhibits the same hardware complexity as a set-associative cache, but exhibits lower miss ratio. This is particularly significant for BTBs and L2 caches for which a significant ratio of conflict misses occurs even on 2-way set-associative caches.
Second, the behavior of skewed-associative caches is quite insensitive to the precise data placement in memory. Recently, we have shown that the skewed associative structure offers a unique opportunity to build TLBs supporting multiple page sizes.

Related publications:

[1] A. Seznec, ``A case for two-way skewed-associative cache'', Proceedings of the 20th International Symposium on Computer Architecture(IEEE-ACM), San Diego, may 1993

[2] A. Seznec, F. Bodin, ``Skewed-associative caches'' , Proceedings of PARLE' 93, Munich, June 1993

[3] A. Seznec, " About set and skewed associativity on second level caches'', Proceedings of the International Conference on Computer Design, Boston, October 1993

[4] F. Bodin, A. Seznec, "Skewed-associativity improves performance and enhances predictability", IEEE Transactions on Computers, May 1997 (A short version appears in Proceedings of the 22th International Symposium on Computer Architecture (IEEE-ACM), Santa-Margharita, June 1995)

[5] N. Drach, A. Gefflaut, P. Joubert, A. Seznec, ``About cache associativity in low-cost shared memory multi-microprocessors'', Parallel Processing Letters, Sept. 1995 (also IRISA Report No 760)

[6] A. Seznec `` A New Case for Skewed-Associativity``, 22 pages, IRISA Report No 1114, July 1997

[7] P. Michaud, ``A Statistical Model of Skewed Associativity'', International Symposium on Performance Analysis of Systems and Software, Austin, March 6-8, 2003. slides

[8] A. Seznec, ``Concurrent Support of Multiple Page Sizes on a Skewed Associative TLB'', to appear in IEEE Transactions on Computers, 2003


General organization of the simulator

oThe simulator is made to compare different replacement policies for a cache of a given size. This size is given as a parameter. The replacement policies are defined in the simulator and each of them is applied to a cache of equal size. Three differents sets of skewing functions are defined in the simulator and one of the parameters is used to decide which functions will be used during the simulation.

Two simulators CACHESKEW and CACHESKEWL2 are provided. CACHESKEW (rep. CACHESKEWL2) targets L1 (resp L2) caches. In the current version of CACHESKEWL2, a direct-mapped split L1 cache is simulated. Inclusion property is enforced. The L1 cache is 8Kbyte and has 16bytes cache line.

oUsage: NAME NbMapfct CacheSize LogLine ResFile < SimFile

oThe different files constituing the CACHESKEW simulator are:

Replacement policies

The replacement policies provided here are described in ``A New Case for Skewed-Associativity``. Corresponding files:

  • Single-bit replacement policy --> SkewPseudoLRU.c

  • Usefulness policy --> SkewUseful.c

  • Not Recently Used --> SkewNRU.c

  • Not Recently Used + Useful --> SkewUNRU.c

  • Enhanced Not Recently Used --> SkewENRU.c


    How to test a new replacement policy

    Feel free to test new replacement policies. Proceed as follows:

    ocreate a new file containing the replacement policy. ie the functions of allocation and of test of presence in the cache.

    odo not forget to add the name of your file in the makefile.

    ocreate a new array of caches in the file cacheLibrary.h .

    oadd the initialisation of this array in the file initcache.c .

    oadd the simulation of the caches in the file SimL1.c .

    oadd the display of the result for this array of caches in the file display.c .


    How to test new skewing functions

    Feel free to test new skewing functions. Proceed as follows:
    ocreate a new file containing the mapping function that you wish to test.

    oadd the name of this file in the makefile

    ocreate a new case in the file initcache.c