Package jline.lib.rmf

Class CacheSFIFORMF

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

Strict FIFO(m) is NOT equivalent to RANDOM(m)/FIFO(m). Gast and Van Houdt (SIGMETRICS 2015) prove pi_FIFO(m) = pi_RAND(m) exactly but show strict FIFO(m) differs and give it no mean-field model. The difference is the within-list age ordering: on a hit in list i < h the demoted tail of list i+1 is reinserted at position 1 of list i (positions 1..j-1 shift back), which the per-item per-list occupancy of RANDOM(m) cannot represent. This model tracks x[k,i,j] = P(item k in position j of list i) with deterministic (age-based) demotion/eviction and returns the plain mean-field fixed point; it reduces to RANDOM(m)/FIFO(m) when m_1 = ... = m_{h-1} = 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
    CacheSFIFORMF(double[] popularity, int[] capacities)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    double[]
    drift(double[] xin)
    Mean-field drift F(x) for strict 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)
    Compute the mean-field fixed point by integrating dx/dt = F(x) to steady state with LSODA.
    int
    getDimension()
     
    double[]
    missProb(double[] xss)
    Per-item out-of-cache (miss) probability at the fixed point.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • CacheSFIFORMF

      public CacheSFIFORMF(double[] popularity, int[] capacities)
      Parameters:
      popularity - aggregate per-item request probabilities (length n).
      capacities - list capacities m_1..m_h (length h).

  • Method Details

    • getDimension

      public int getDimension()

    • drift

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

    • fixedPoint

      public double[] fixedPoint(double tmax)
      Compute the mean-field fixed point by integrating dx/dt = F(x) to steady state with LSODA.
      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[] xss)
      Per-item out-of-cache (miss) probability at the fixed point.
      Parameters:
      xss - fixed-point state vector.
      Returns:
      pi0[k] = P(item k out of cache), length n.