Sign in to follow this  
implicit

Optimal caching in practice

Recommended Posts

I'm working on a simple game for a system with fairly limited VRAM, and I'd like to try to make the most of it by loading new content in-game. The good news is that the game runs entirely on rails, so I can perfectly predict what's going to be needed when and for how long, and thus hopefully avoid ever stalling the game. Furthermore the hardware platform, source medium, frame rate and most everything else about the game is fixed and predictable. Now the big question becomes how to decide just what to load and when. The 'clairvoyant' algorithm they taught us in school simply always replaces the piece of data which has a "next use" the furthest into the future. This scheme is optimal in the sense that the minimum number of replacements are made, but in reality there are other considerations to take into account. For one thing the VRAM upload speed is limited, so you can't expect to replace all of the graphics from one frame to the next. Similarly the IO/decompression speed is also limited, but here there's a fairly large read buffer which nevertheless shouldn't be allowed to run too low. Finally any repeated data would have to be replicated, since any seeking back would be too slow and complicated. Now just how much VRAM bandwidth there is depends on what's going on in the game, but to simplify things lets say I reserve the time to transfer some small fixed quantum every frame. Then lets also say the reading speed and read buffer sizes are fixed, and the buffer should simply not be allowed to become empty. Then I suppose what we're left with is minimizing the size of the level stream (e.g. the amount of duplicate data) while keeping these constraints in mind. But to be honest I just don't know to tackle this kind of problem. I guess any game with an in-game cut scene would have to deal with the same issues, so I'm hoping someone has thought out some clever methods already. Also I figure you'd want to be able to give some feedback back to the artist (well, when I find one again..) such as where the loading hotspots are, how much VRAM any particular frame uses, and so on. Any thoughts? It feels like there ought to be some good and straightforward heuristic here, or perhaps a common and well-researched problem it can be translated into, but I'm pretty much stumped.

Share this post


Link to post
Share on other sites
The clairvoyant algorithm you mention keeps every resource in cache for as long as possible. You wish to do the reverse: remove every resource from cache as soon as possible (that is, as soon as it's not used anymore). This will leave room from elements which predictably will appear soon (load them based on next-use time). Keep the loading a side-task to eliminate performance hits and keep your buffers full, and only use full processing power if you need the data (as opposed to precaching it).

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
The clairvoyant algorithm you mention keeps every resource in cache for as long as possible. You wish to do the reverse: remove every resource from cache as soon as possible (that is, as soon as it's not used anymore). This will leave room from elements which predictably will appear soon (load them based on next-use time). Keep the loading a side-task to eliminate performance hits and keep your buffers full, and only use full processing power if you need the data (as opposed to precaching it).
Well, merely throwing out data when it's never going to be used again usually won't be enough as e.g. keeping (say) an enemy that's used both at the very beginning and the very end of a level around would be wasteful, as well as not allow the VRAM to be fully utilized in between. I guess you could design the levels to work that way, or let the artist have a flag to manually flush such data when necessary, but I'm hoping that there's more of an automated method..
Plus what I'm dealing with here is hundreds of small background tiles, often reused in odds ways all over the level, so managing them manually would get messy fast.

Share this post


Link to post
Share on other sites
I didn't make myself clear, sorry.

What I mean is that the clairvoyant algorithm says 'replace resource Old with resource New', which means the sequence of events will be:

- Old is used
- Old is not used for a while
- New is loaded into the cache
- New is used

You want the sequence to be:

- Old is used
- New is loaded into the cache
- New is not used for a while
- New is used

Because, this way, you can delay the loading of the new resource until you have the bandwidth or time to load it, instead of having to load it exactly when necessary.

In short, every time you use a cached resource, determine if that resource's "next use" time is further into the future than the other resources, and if it is then replace it with an uncached resource with a closer "next use" time.

Share this post


Link to post
Share on other sites
In other words run the clairvoyant algorithm as usual, but spread out the replacements as evenly as possible. I'm also reading script data and other things from the same stream so replacing them as early possible doesn't quite make sense, but pacing out the data surely does.
I can't believe it might be this simple, but it sounds like it ought to be optimal. Then the only problem remaining is given an ordered sequence of events (loads), each with an earliest and a latest possible execution time, to figure out the most "even" distribution.

Thank you :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this