algorithm - Efficient reordering of large dataset to maximize memory cache effectiveness -

I am working on a problem I thought people might find interesting (and perhaps a pre- Existing solution).

I have a large dataset that contains a long list of pairs of objects of objects, something like this:

  [(a8576, b3295), (a7856, b2365) , (A3566, b5464), ...]  

There are so many objects to keep in memory at any time (possibly hundreds of gigabytes), so they can be stored on disk, But can be cached in memory (possibly using an LRU cache).

I need to run this list through the processing of each pair, for which pair needs to be loaded in both object memory (if they are not already cached there ). Then, question: There is a way to reorder pairs in the list to maximize the effectiveness of the in-memory cache (in other words: at least the number of cache misses). ?

Note

1. Obviously, the rearranging algorithm should be as fast as possible, and should not be dependent on being enabled To keep the entire list in memory once (because we do not have enough RAM for it) - but if needed, the list can be repeated several times.

2. If we were not working with different objects, do not add them, then their answer would be simple. This clearly will not work in this situation because you need to consider both the elements in the pair.

3. The problem may be related to the detection, but even if the problems are equal, I do not think the least solution

< Li>

My impression is that the estimated number will stream the data from the disk, and it will write back in one part, the better order it may need to be repeated several times. Actually it can not be just added, it can be three times, quadruple, or more I hope that such algorithm for the couple is easily normalized. can go.

Your problem relates to computer graphics hardware similar to:

When a triangle provides indexed sugars in the mesh, usually the most recently converted corners in the hardware (~ 128 is the cache of the last time I had to worry about it, but It is doubt that these numbers are big these days). To cache frequencies, a relatively expensive transform operation is required to calculate. To optimize the cache usage, "Aries Optimization" is considered to be a very hot research topic for the reconstruction of triangle meses. Googling top cache optimization (or optimization: ^) can get you some interesting content related to your problem, as the other poster suggests, I suspect that it effectively exploits any inherent similarities in your data Will depend.

One more thing to keep in mind: because an LRU cache gets overloaded because it is an MRU replacement strategy to keep at least some items in memory (instead of turning on each pass full cache) . I remember that John Carmack has written some good material on this subject in relation to Direct 3D Texture Caching Strategies.