cart-replacement · research · also CART, CAR with Temporal Filtering, CLOCK with Adaptive Replacement and Temporal Filtering

CART (CAR with Temporal Filtering)

CART is a cache replacement policy that extends CAR with an adaptive filter for distinguishing short-term reuse from longer-term utility.

Repeated accesses in a short burst need not predict future reuse; CART addresses this distinction rather than merely counting hits. It is a separate algorithm, not an alias for CAR. [2]

T1 and T2 hold payloads; B1 and B2 hold only identities. An additional S/L filter bit records utility class. A resident hit sets the reference bit, not the filter bit. The temporal window is represented by the adaptive T1 population, not a fixed duration in seconds. [1]

A B1 history hit is not the only route to L. Figure 3 line 30 can reclassify a referenced S page while rotating it within T1 when |T1| >= min(p + 1, |B1|). This occurs during replacement scanning. The earlier prose's history-only explanation is therefore incomplete; this is a source-reading observation, not an author-confirmed erratum. [1]

The executable boundary check isolates that predicate. With |T1|=2, p=2 and |B1|=4 it is false; changing |B1| to 2 makes it true. For p=5/2, |T1|=3 and |B1|=4 it remains false even though |T1| > p. These are constructed inputs, not a cache workload, and no reachability or hit-ratio claim is made. [3]

Relations

related

CAR (CLOCK with Adaptive Replacement), CLOCK cache replacement, Adaptive Replacement Cache, Ghost cache entry, Cache pollution

Limitations

• The study uses cold-start, read-only trace simulation after upstream cache filtering; it does not establish universal superiority or measured concurrent implementation speed. [1]
• The downloadable check covers one predicate, not full CART state transitions, history management, target rounding or a production implementation. [4]

Citations

1. Bansal and Modha. CAR: Clock with Adaptive Replacement. FAST 2004, section IV, Figure 3 line 30 and section V.A. (accessed 2026-11-07)
2. Bansal and Modha. FAST 2004 author presentation, slide 32: CART temporal filtering. (accessed 2026-11-07)
3. Hesela: constructed CART filter-boundary inputs and exact results (accessed 2026-11-07)
4. Hesela: exact predicate check and its scope, not a complete CART implementation (accessed 2026-11-07)

JSON: /data/terms/cart-replacement.json