How to set the value of Belady boundary?

[zztaki]

In the paper of LRB, the Belady boundary is defined as the minimum time-to-next-request of objects evicted by Belady’s MIN algorithm. However, the MIN algorithm is offline, so it is reasonable to assume that the Belady boundary is approximately stationary and is updated continuously during the machine learning warmup period.

But in practice, Belady boundary is set to the length of sliding memory window which is equal to 67108864. I am confused whether the Belady boundary should be implicitly related to the cache capacity and the average size of cached objects.

Thank you and have a nice day!

[zztaki]

Maybe 67108864 means that the working set in the sliding window is already on the order of terabytes, but if the cache capacity is tens of terabytes or even hundreds of terabytes, is it unreasonable to set a constant like this?

[sunnyszy]

Hi @zztaki , The Belady boundary is set to 2x cache size (see paper Table 2). In the implementation, it is a constant per trace/cache size calculated by cache size and average object size in the trace.

[zztaki]

Hi, @sunnyszy Can I understand it as: if the cache size is 1TB and the average object size is 32KB, then the Belady boundary is equal to 2TB, and the sliding window length is set to 64MB?

[sunnyszy]

@zztaki your understanding is basically correct. Nits: the length is 64M instead of 64MB, as the unit is the number of requests. And note here our focus is on the Belady boundary instead of the memory window.

[zztaki]

Yes, thank you for your answering! I'm wonder whether to edit it 😄hh.