Adapting probPromote

Each cache maintains and adapts a separate $probPromote$ value. The reader will appreciate that the lower the $probPromote$ value at a cache, the lesser is the rate at which new pages will enter the caches above it. Thus, by changing the value of $probPromote$, a lower cache can influence the influx rate of new pages at the higher caches. The fundamental idea in the PROMOTE technique is to use this leverage to create a situation where the ``usefulness" of pages evicted from the various caches are roughly the same (if possible). This is different from DEMOTE, where pages evicted from the higher cache are more useful (and hence need to be demoted) than the pages evicted from the lower cache.

To facilitate the adaptation, PROMOTE requires a very simple interface to periodically receive adaptation information like the cache life (the timestamp difference between the MRU and LRU pages in the cache) of the next higher cache(s). At regular intervals, each cache, other than the lowest, sends the hint to the next lower cache (Lines 1-3), using which, the $adaptRatio$ is computed (Lines 23, 41-43). The goal is to adapt $probPromote$ in such a way that the $adaptRatio$ approaches $0.5$ (a value that implies that the usefulness of pages evicted from the higher cache is the same as of those from the lower cache). If the higher cache has a larger life ( $adaptRatio > 0.5$), $probPromote$ is increased, else it is decreased. Since there is a lag between the adaptation in $probPromote$ and its impact on the $adaptRatio$, the recomputation of $probPromote$ (Lines 4-17) is done only on alternate times the hint is received (Line 3). Further, if the previous adaptation of $probPromote$ is found to have reduced the separation of $adaptRatio$ and $0.5$ by a reasonable fraction (Lines 7-10), then no further adaptation is done. To avoid any runaway adaptation, $probPromote$ needs to be carefully adapted so that the adaptation is proportional to the difference between $adaptRatio$ and $0.5$ and also is slower when close to extreme values of 0 and $1$ (Lines 11-12). To start off in a fair fashion, $probPromote$ is initialized according to the sizes of the caches. Since the higher caches usually demonstrate higher hit rates than the lower caches, we forbid $probPromote$ to go beyond the ratio thus determined (Lines 13-14).

Figure 6: Communication protocols for the PROMOTE technique (left panel) and the DEMOTE technique (right panel). Although shown in the same diagram, either LRU or ARC data-structures are used consistently across all levels.

Let us examine some examples of PROMOTE in existing cache management policies: