Monday, July 24, 2017

Eviction, and the Belady Algorithm



"Depend upon it: there comes a time when, for every addition of knowledge, you forget something that you knew before. It is of highest importance, therefore, not to have useless facts elbowing out the useful ones"
Sherlock Holmes

Keep it short
In computer science and data communications, the word "cache" describes memory used to store the stuff you are going to need right away, or nearly so. There are similar storage and rapid access  requirements in the PMO: all manner of metrics, action items, staffing plans, budgets, etc fill up short term memory -- stuff you need handy to work effectively each day.

And so, in describing this it's pretty clear that there are some stand-out needs for a memory system (*):
  • Fast put-away and retrieval
  • Handy and accessible -- you don't have to go looking for it
  • Near-term stuff is always right on top -- at your finger tips, as it were
  • And, whatever you are looking for is actually in the cache -- no "cache misses"
Eviction:
But, what do you do if/when the cache fills up? 50+ years ago a IBM researcher Laszlo Belady wrote a paper which more or less described an algorithm for the optimum cache eviction protocol -- after all, cache is by its nature limited in scope (it's not a cache if it holds everything)
When the cache fills up, evict that which is not going to be needed the longest from now

Good theory; not practical, actually. How would you ever know what you are going to need longest in the future? After all, we're seeking minimum cache misses, no matter when. Several eviction protocols have been invented and tested: Random eviction (just pick something and throw it out); First In - First Out (FIFO), or the oldest stuff goes out first.

It turns out that the strategy that comes closest to the Belady optimization for minimizing cache misses is "Least Recently Used". As the name implies, if you don't use it, lose it!

Keep it local
In these days of "the cloud", what does local mean? Behind the Internet scenes, there's a lot of action on that point. "Store Forward" and local servers, etc manage latency. And of course, physical fulfillment centers, whether it's physical documents or other other stuff, are now routinely popping up about the countryside. (One should not forget the local thumb drive, or (gasp!) a file cabinet)

Size the cache
Enter: Theory of Constraints. If the cache is actually a buffer or collector ahead of downstream production -- task orders, or parts and assemblies (code units, etc count here) aka "inventory", and the cache is larger than the downstream capacity it's serving, then the cache just fills up.

There's actually no point in taking orders -- or creating inventory -- you can't address. Send people away or refuse delivery! Building inventory before a constraint may make the upstream widgets/hour look good, but overall it detracts from the project effective use of resources. ToC has been around at least 30+ years; it's amazing how it seems like "new news" to so many.

--------------------------------------
For more: check out the chapter on caching in the book "Algorithms to Live By" by Christians and Griffiths

(*)
And, with recent events, we might add:
  • Secure from hackers
  • Private as required


Read in the library at Square Peg Consulting about these books I've written
Buy them at any online book retailer!
http://www.sqpegconsulting.com
Read my contribution to the Flashblog

No comments:

Post a Comment