Online First Fit Algorithm for modeling the problem of configurable cache architecture

Customizing the cache configuration: number of line, line size and associativity to a particular program needs is well known to have tremendous benefits for performance and energy. In this paper, we describe a reconfigurable cache memory, which is efficiently applied to the L1 data cache of an embedded processor. In practice, dynamic systems require decisions to be made on-line [21,28], without full knowledge of their future impact on the system. A model for the processing of sequences of tasks is introduced, and a on-line decision algorithm is developed. The key contribution is the First Fit Algorithm (FFA), which obtains better optimization than previous algorithms. We show that our version of First Fit Algorithm (FFA) not only has competitive ratio at most 2 in the worse case (which is best possible in the worst case).