Package jline.lib.rmf

Class CacheFIFORMF

java.lang.Object
jline.lib.rmf.CacheFIFORMF
public class CacheFIFORMF extends Object
Position-resolved density-dependent population process (DDPP) mean field for FIFO(m) cache replacement.

FIFO(m) and RANDOM(m) share the exact stationary distribution (Gast and Van Houdt, SIGMETRICS 2015, Thm 1: pi_FIFO(m) = pi_RAND(m)), so their steady-state hit ratios coincide. Their mean-field TRANSIENTS differ: FIFO evicts the deterministic tail (fixed residence of m insertions) whereas RANDOM evicts a uniformly random victim (geometric residence), so H(t) from a cold cache ramps differently even though H(inf) agrees. This model provides that dedicated FIFO transient.

FIFO(m) differs from strict FIFO(m) (CacheSFIFORMF) only in the reinsertion position on a hit: the demoted tail of list i+1 lands at the vacated position j of list i (in place, no within-list shift), whereas strict FIFO reinserts it at position 1.

Reference: N. Gast and B. Van Houdt, "Transient and Steady-state Regime of a Family of List-based Cache Replacement Algorithms", ACM SIGMETRICS 2015.

  • Constructor Summary

    Constructors
    Constructor
    Description
    CacheFIFORMF(double[] popularity, int[] capacities)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    double[]
    drift(double[] xin)
    Mean-field drift F(x) for FIFO(m).
    Object[]
    driftTrajectory(double time, int nPoints, double[] xinit)
    Integrate the drift over a finite window on a uniform time grid from a supplied (or default) initial occupancy.
    double[]
    fixedPoint()
     
    double[]
    fixedPoint(double tmax)
    Mean-field fixed point by integrating dx/dt = F(x) to steady state.
    int
    getDimension()
     
    double[]
    missProb(double[] x)
    Per-item out-of-cache (miss) probability of a state vector.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • CacheFIFORMF

      public CacheFIFORMF(double[] popularity, int[] capacities)

  • Method Details

    • getDimension

      public int getDimension()

    • drift

      public double[] drift(double[] xin)
      Mean-field drift F(x) for FIFO(m).
      Parameters:
      xin - state vector of dimension getDimension().
      Returns:
      dX of the same dimension.

    • fixedPoint

      public double[] fixedPoint(double tmax)
      Mean-field fixed point by integrating dx/dt = F(x) to steady state.
      Parameters:
      tmax - integration horizon.
      Returns:
      fixed-point state vector of dimension getDimension().

    • fixedPoint

      public double[] fixedPoint()

    • driftTrajectory

      public Object[] driftTrajectory(double time, int nPoints, double[] xinit)
      Integrate the drift over a finite window on a uniform time grid from a supplied (or default) initial occupancy. Transient counterpart of fixedPoint(), mirroring CacheRMF.driftTrajectory.
      Parameters:
      time - end time of the window (start is 0).
      nPoints - number of uniform grid points (>= 2).
      xinit - initial occupancy (dim,), or null for the default warm start.
      Returns:
      Object[]{ T (double[nPoints]), X (double[nPoints][dim]) }.

    • missProb

      public double[] missProb(double[] x)
      Per-item out-of-cache (miss) probability of a state vector.
      Parameters:
      x - state vector.
      Returns:
      pi0[k] = P(item k out of cache), length n.