Debugging innovations

We implemented a lot of strategies, and understanding their behavior was not always easy. What helped us a lot was to think about how differently a new strategy might perform from a standard strategy. The base strategies such as LRU, LFU and FIFO were useful for comparison and testing. These are probably the oldest as well as the most used portions of our code and were particularly useful for debugging newer strategies.

As an example, we describe the debugging of some strategies. We implemented some multilevel queuing strategies. These used LRU policy between queues, and LFU within a particular queue. Another policy did the reverse, maintaining LFU between queues and LRU within them. Many problems were caught by proper use of the boundary cases here. Observe that if the queue size is one, the policy becomes pure LRU in one case and pure LFU in the other. Similarly, if there is only one queue, then the policies become equivalent to pure LFU and pure LRU respectively.

We also created random access traces to test our strategies. We generated of the order of $10^4$ test cases for debugging purposes. In this regard, it was found useful to have artificial values of cache parameters (e.g. a 8 byte cache with line size 1) to help us understand what was going on. This was very useful for debugging. We used shell scripts heavily to carry out the extensive testing.