A probabilistically analysable cache implementation on FPGA

Predicting the timing behaviour of modern computer architectures can be extremely difficult. Probabilistic Timing Analysis (PTA) is a recent technique to compute the execution time of a program within a given confidence interval, but requires specially designed hardware with certain properties. This work addresses the implementation of a probabilistically analyzable L1 instruction and data cache for the Ion MIPS32 processor on FPGA. We developed a random placement and replacement policy that fulfills all the requirements for PTA. Our experiments show that the cache fulfills all the requirements for PTA, and program timing can be determined with arbitrary accuracy. In addition, random placement and replacement improve the observed worst case execution time (WCET) from 6% to 19% w.r.t. a Least Recently Used policy.