Research Program:  a universal Cache Miss Equation for the Memory Hierarchy

This program was described in a  tech talk  at Google

The work started during a sabbatical visit to Microsoft (Redmond), resulting in a patent:
J.F. Pang, M. Raghuraman and Y.C. Tay.  
Method and system for allocating cache memory for a network database service.
Patent Number US 6,493,810 (Dec. 2002).

The simple model in the patent was further developed in:
Y.C. Tay and M. Zou. 
A page fault equation for modeling the effect of memory size.
Performance Evaluation 63, 2(Feb. 2006), 99--130.
This model views the entire main memory as a cache for pages retrieved from disk, 
and works for different application patterns, replacement policies and operating systems.

The model is reinterpreted for the record buffer in a database system:
D.N. Tran, P.C. Huynh, Y.C. Tay and A.K.H. Tung. 
A new approach to dynamic self-tuning of database buffers.
ACM Transactions on Storage 4, 1(May 2008), Article 3.
The equation is used to dynamically size a buffer 
for a mix of multiple transaction classes.

Essentially the same equation is used for heap sizing:
Y.C. Tay and X.R. Zong. 
A page fault equation for dynamic heap sizing.
Proc. WOSP/SIPEW Int.  Conf. on Performance Engineering,
San Jose, CA, USA (Jan 2010), 201--206.
In this case, the access pattern mixes references 
from the mutator and the garbage collector, 
so it changes when the heap is resized.

To demonstrate the top-down approach for the equation, 
it is further refined by expressing its parameters in terms of heap size:
Y.C. Tay, X.R. Zong and X. He. 
An equation-based heap sizing rule.
Performance Evaluation 70, 11 (Nov. 2013), 948--964.
The resulting parameters can be interpreted in terms of the garbage collector
(generational or copying), space overhead, freelist usage, etc.

The equation makes very weak assumptions about 
the reference patterns and replacement policies,
so it works even for network routers in Named Data Networking (NDN):
M. Rezazad and Y.C. Tay. 
A cache miss equation for partitioning an NDN content store.
Proc. Asian Internet Engineering Conference (AINTEC),
Bangkok, Thailand (Nov. 2013)., 1--8.
In particular, it can be used to partition the router cache among traffic classes.

The equations for adjacent levels in the memory hierarchy are coupled,
and their relationship is examined in:
V. Venkatesan, Y.C. Tay, I.Y. Zhang and Q. Wei.  
A 3-level cache miss model for a nonvolatile extension to transcendent memory. 
Proc. IEEE CloudCom, Singapore (Dec. 2014), 218--225.
Nonvolatile memory requires special replacement policies 
that take into account its short life; in this paper, the replacement policy
is a mix of LRU, FIFO and LFU, but this is not an issue for the equation.

Transcendent memory is a recent addition to the memory hierarchy
that facilitates the sharing of pageframes among virtual machines.
It has a cleancache with unusual properties, 
but that is also not an issue for the equation:
V. Venkatesan, Y.C. Tay and Q. Wei. 
Sizing cleancache allocation for virtual machines' transcendent memory.
IEEE Trans. Computers 65, 6 (May 2016), 1949--1963.

There is a widely-used Che Approximation for cache misses.
Both equations were implemented and tested with Apache Flink for streaming applications.  
A comparison for some workloads was presented in:  
R. Dou, R.T.B. Ma and Y.C. Tay.  
Dynamic equation-based memory allocation for stream processing engines (invited talk).
MAKI Scientific Workshop 2024. TU Darmstadt, Germany (March 2024).
This application of the equation also shows that it works for objects of unequal sizes.