2

The Situation:

I have 68GB of data that is conceptually realized as a 3D matrix of 8-bit values with dimension 4096*4096*4096.

I need to access multiple sections of this data for processing in a time critical setting (multiple as in sequential one after another). Each section would be approximately 50MB in size.

The sections can be thought of as arbitrary planar slices through the cube (but constrained within it). The sections can go through the cube at any orientation and placement, they will not line up with the 3-axes often.

I cannot load 68GB in to RAM – Let's say I only have 8GB, of which the OS etc. is using already.

I need a way to efficiently partition the 68GB of data so that I can access the data required by the sections.

Proposal:

As the data is conceptually 3D I propose to recursively partition it as octants (2^3=8). Starting at ‘the data’ at the top layer, and moving all the way down the octree to the data points themselves.

Each layer of recursive detail would have a 3-bit address for each of its octants – so if the original data were just a 4*4*4 cube, each data point would have a 6-bit ‘address’:

enter image description here

For the real example we would need log2(4096*4096*4096) = 36bits to address each data-point.


More Situation:

While the section orientations and positions are arbitrary – two factors work in my favor:

  1. The data points required are constrained on the plane, (obvious maybe, but it bears repeating)
  2. The required sections will be reasonably close to each other over time - i.e. requiredSection1 will be close to requiredSection2 which will be close to requiredSection3. By ‘close’ I mean that it is very likely there will be crossover in data points required for the sections. It is very likely also, but less so, that section3 will have an overlap with section1 … and so on.

More Proposal:

I see potential for a Least Recently Used (LRU) cache here where at some ‘depth’ of the recursive octant partitioning I stop and decide that this is the new ‘smallest’ element. It is these chunks of data that are actually loaded and unloaded into RAM. (might be worth pointing out I'm not caching results, I'm caching input data to a function)

As an example, say I partitioned it into 32*32*32 chunks, I would need log2(32*32*32) = 15bits of data to address each chunk. These would each contain 4096^3/32^3 = 2097152 points of data (log2(2097152)=128) and be approximately (4096^3/32^3)*8 = 2MB large.

(Size would be experimented with)

It is these chunks that would be loaded into and out of the RAM via the LRU cache - the idea being that the data in the cache from prior iterations would already contain the chunks that contained the required data points for the current iteration.

Win! (right?)

As the required sections moved about sooner or later a new 32*32*32 chunk of data would be required - assuming the RAM allocated to the task was full already, the new section would be loaded (taking a hit on disk access), and it would take the place in RAM of the ‘least recently used’ chunk, which is likely (but not garunteed) to be the one least likely to be needed in the future.


The Questions (sorry, no TL;DR here):

I don’t see the LRU management to be an issue - however, what I am interested in is:

  • Is this viable?
  • How can I best manage the data in terms of data-structures, both on disk and while in RAM?
  • How can I best leverage the recursive nature of this in code?
  • How not to blow up RAM just dealing with addressing itself?

Likely I'll be using openCV in either a C++ or Python environment.

1

What I would do.

Repackage the data on disk in small cubes, a few KB each. That is, if the data are represented as a typical array of arrays of arrays, the points that are close in the 3D space are not close in the representation. I'd try to overcome that. The result would be a the same amount of data, addressable in two steps. First step would be finding the address of the small cube, the next (slightly trickier) step would be finding the point within that cube. You already have a right picture, it's just has too many levels. Just one additional level may be enough.

If we make the small cube's dimension 16 * 16 * 16, it will take up 4 KB. To find the address of the cube, each coordinate would have to be shifted left 4 bits. Coincidentally, 4 KB is the typical OS RAM page size.

The repackaging process would need to keep in RAM the amount of data one small cube thick, that is 4096 * 4096 * 16 = 256 MB. Quite doable; several small cube layers can be calculated at once with a few GBs available.

Now I would plainly access the new file that uses small cubes, translating the coordinates.

The OS cache would keep the small cubes in RAM for me pretty efficiently. Since one layer of cubes is merely 256 MB, and an arbitrary planar section cannot require more that 2 layers worth of small cubes to include all the points, the whole working set would require 512 MB worth of small cubes.

The OS cache would happily keep all of them in RAM for you, provided that your program leaves slightly more than 512 MB of RAM free when running. Now, when you try to access data for a particular cube, it will be served from RAM, provided that it has been touched in the past.

You can make things even more explicit by memory-mapping your file (read-only) and accessing the whole 64 GB worth of address space of it; only the pages (small cubes) you actually access will be mapped, that is, loaded from the disk.

This rids you of implementing any caching yourself (always tricky), and rids you of spending RAM on an explicit octree structure. With a space as regular and simple as a cube, you can as well use an implicit pre-built one :)

  • Hi, addressing (pun intended) your first three paras: The plan was that addressing the 'small cube' within the data and then the point within the cube would be a very similar process, but I'm not so sure about what you mean by 'finding' those cubes/points, wouldn't that be explicit? ... Yes, great point re. bit shifting, that's the kind of level I think this needs to be. Page size, great, exactly the stuff I need to know ... Yes, I agree re. repackaging... It's dawned on me that managing the addressing 'data' may be more of a concern than managing the data it represents. – Lamar Latrell Apr 17 '16 at 5:57
  • 4th para: Yes, that's reasonable logic. 5th para: this is the crux of the problem, the sections will certainly move out of the cache eventually, in fact, if I were forced to make a prediction with 16^3 cubes, I'd say there will be ~25% frame to frame cache misses in the total of cubes/points required. Using that magic 16^3 may not be optimal (my initial guess would have opted for a larger cube, but that was always going to be determined by experimentation). Maybe I could 'atomise' the 16^3 cubes themselves? (treat them as 'points') and have recursively recursive aggregates... ugh, head hurts – Lamar Latrell Apr 17 '16 at 6:15
  • Last 2 paras: Topics I need to learn about... Reading reading reading. +1 though - thanks much :) – Lamar Latrell Apr 17 '16 at 6:39
  • 1
    Have done some reading. It appears I have reinvented the concept of virtual memory (without realising 99.9% of the complexity, considerations and not to mention actual implementation issues ;). So, OK I hear what you're saying, one question though: Does virtual memory management use LRU, LFU, perhaps some kind of hybrid/adaptive system? – Lamar Latrell Apr 17 '16 at 22:14
  • Virtual memory uses something close to LRU, because once a page needs to be used, it needs to be pulled to RAM anyway. There's a complex interplay between virtual memory paging (pushing out pages that don't fit physical RAM at the moment), disk cache, and the need to minimize I/O while switching between processes that have pages outside RAM. I'm totally not an expert in the matter. What I offered to use is the ready-made I/O cache built into the OS by making data that are likely to be used together stored on the disk together. – 9000 Apr 18 '16 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.