program-counter-based-classification · research · also PCC buffer classification, Program-Counter-based Classification

Program-counter-based classification (PCC)

PCC classifies buffer-cache accesses by the program contexts issuing I/O, allowing learned access patterns to guide replacement across files.

PCC's signature PC sums call-site addresses along the stack up to main(), separating callers that share an I/O wrapper. A single system-call address would merge those callers. The historical 32-bit signature is a compact context key, not a collision-free identity. [1]

The block table records the last accessing context. When a tracked block is reused, its previous context receives the reuse evidence, even if a different context issues the new access. The classifier's sequential category means distinct blocks without reuse, not necessarily adjacent disk addresses. [1]

The OSDI 2004 comparison replaced UBM's classifier while retaining its marginal-gain cache manager; the kernel implementation used Linux 2.4.20. AMP's later PCC* comparator instead used PCC detection with AMP cache management. These are different experimental comparisons. [1] [2]

For synthetic address lists, [0x1000,0x2000,0x4000] and [0x1000,0x2800,0x3800] both sum to 0x7000. This collision needs neither overflow nor identical frames. Exact-list identity separates them; a sum alone does not. The downloadable calculation is an arithmetic illustration, not a measured collision rate or cache benchmark. [3]

Relations

related
Unified Buffer Management (UBM), AMP buffer caching, Locality of reference

Limitations

  • Sampling and context history affect classification; a learned pattern is a prediction, not a guarantee of future block reuse. [1]
  • The Linux 2.4.20 prototype could not obtain signature PCs for mmap accesses and classified those references as other. [1]

Citations

  1. Gniady, Butt and Hu. Program-Counter-Based Pattern Classification in Buffer Caching. OSDI 2004, sections 4-5. (accessed 2026-11-21)
  2. Zhou, von Behren and Brewer. AMP: Program Context Specific Buffer Caching. USENIX ATC 2005, sections 1-3. (accessed 2026-11-21)
  3. Hesela. Exact additive-signature examples: common wrappers, distinct sums and equal-sum collisions. (accessed 2026-11-21)

Further reading

  1. Hesela. Bounded exact-sum illustration; no stack unwinding, cache simulation or hash-probability model. (accessed 2026-11-21)
  2. Hesela. Signature arithmetic tests and an independent bit-column addition oracle. (accessed 2026-11-21)
  3. Hesela. Interpretation, reproduction instructions and limits of the signature example. (accessed 2026-11-21)
Sources & caveats
  • Full primary-paper design and evaluation reviewed. Historical workloads and kernel results are not performance predictions for current systems. [1] [2]
  • The constructed equal-sum case uses invented addresses, not executable traces. It establishes non-unique arithmetic, not observed collisions in PCC. [3]

JSON: /data/terms/program-counter-based-classification.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Program-counter-based classification (PCC). Hesela. 2026-11-21. https://hesela.dev/terms/program-counter-based-classification/