@TECHREPORT{atr9,
  author =   {Jan Reineke and Daniel Grund and Christoph Berg and Reinhard Wilhelm},
  title =    {Predictability of Cache Replacement Policies},
  institution = {SFB/TR 14 AVACS},
  year =     {2006},
  type =     {Reports of SFB/TR 14 AVACS},
  number =   {9},
  month =    {September},
  note =     {ISSN: 1860-9821},
  abstract = {Hard real-time systems must obey strict timing constraints. 
              Therefore, one needs to derive guarantees on the worst-case 
	      execution times of the systems' tasks. In this context, 
	      predictable behavior of system components is crucial for the 
	      derivation of tight and thus useful bounds.  This paper 
	      presents results about the predictability of common cache 
	      replacement policies. To this end, we introduce two metrics 
	      that capture aspects of cache-state predictability. A thorough 
	      analysis of the LRU, FIFO, MRU, and PLRU policies yields the 
	      respective values under these metrics. To the best of our 
	      knowledge, this work presents the first quantitative, 
	      analytical results for the predictability of replacement 
	      policies. They support empirical evidence in static cache 
	      analysis.},
  bibtex =   {2006/avacs_technical_report_009.bib},
  pdf =      {2006/avacs_technical_report_009.pdf},
  editor =   {Bernd Becker and Werner Damm and Martin Fr{\"a}nzle and Ernst-R{\"u}diger Olderog and Andreas Podelski and Reinhard Wilhelm},
  series =    {ATR},
  subproject = {R2},
}