La situazione:
Ho 68 GB di dati concettualmente realizzati come una matrice 3D di valori a 8 bit con dimensione 4096 * 4096 * 4096.
Ho bisogno di accedere a più sezioni di questi dati per l'elaborazione in un'impostazione di tempo critico (multipli come in sequenza uno dopo l'altro). Ogni sezione avrà una dimensione di circa 50 MB.
Le sezioni possono essere considerate come sezioni planari arbitrarie attraverso il cubo (ma vincolate al suo interno). Le sezioni possono passare attraverso il cubo in qualsiasi posizione e orientamento, non si allineano con i 3 assi spesso.
Non riesco a caricare 68 GB nella RAM - Diciamo che ho solo 8 GB, di cui il sistema operativo e così via sta già usando.
Ho bisogno di un modo per efficientemente partizionare i 68 GB di dati in modo da poter accedere ai dati richiesti dalle sezioni.
Proposta:
Poiché i dati sono concettualmente in 3D, propongo di dividerlo ricorsivamente come ottanti (2 ^ 3 = 8). A partire da "i dati" nel livello superiore e spostandosi completamente verso il basso fino agli stessi punti dati.
Ogni livello di dettagli ricorsivi avrebbe un indirizzo a 3 bit per ciascuno dei suoi ottanti, quindi se i dati originali fossero solo un cubo 4 * 4 * 4, ogni punto di dati avrebbe un "indirizzo" a 6 bit:
Perilveroesempioavremmobisognodilog2(4096*4096*4096)=36bitperindirizzareognipuntodidati.
Piùsituazione:
Sebbenegliorientamentieleposizionidellesezionisianoarbitrari,duefattorifunzionanoamiofavore:
- Ipuntidatirichiestisonovincolatisulpiano,(ovvioforse,masiripete)
- Lesezionirichiestesarannoragionevolmentevicinel'unaall'altraneltempo-cioèlasezionerichiesta1saràvicinaallasezionerichiesta2chesaràvicinaallasezione3richiesta.Con"vicino" intendo che è molto probabile che ci sarà un crossover nei punti dati richiesti per le sezioni. Molto probabilmente anche, ma meno , quella sezione3 avrà una sovrapposizione con la sezione 1 ... e così via.
Altre proposte:
Vedo il potenziale per una cache LRU (Least Recently Used) qui dove ad una certa "profondità" dell'ottante ricorsivo partizionamento Mi fermo e decido che questo è il nuovo elemento 'più piccolo'. Sono questi chunk di dati che vengono effettivamente caricati e scaricati nella RAM. (potrebbe valere la pena sottolineare che non sto memorizzando i risultati nella cache, sto memorizzando nella cache i dati di input in una funzione)
Ad esempio, supponiamo di averlo partizionato in blocchi 32 * 32 * 32, avrei bisogno di log2 (32 * 32 * 32) = 15 bit di dati per indirizzare ogni chunk. Questi contengono ciascuno 4096 ^ 3/32 ^ 3 = 2097152 punti di dati (log2 (2097152) = 128) e sono approssimativamente (4096 ^ 3/32 ^ 3) * 8 = 2MB di grandi dimensioni.
(Dimensioni sperimentate con)
Sono questi blocchi che verrebbero caricati dentro e fuori la RAM tramite la cache LRU - l'idea è che i dati nella cache da iterazioni precedenti contengano già i blocchi che contenevano i punti dati necessari per l'iterazione corrente.
Win! (Giusto?)
Man mano che le sezioni richieste si spostavano prima o poi sarebbe necessario un nuovo 32 * 32 * 32 chunk di dati - supponendo che la RAM assegnata all'attività fosse già piena, la nuova sezione sarebbe stata caricata (facendo un colpo sull'accesso al disco ), e prenderebbe il posto nella RAM del chunk 'usato meno di recente', che è probabile ( ma non fornito ) per essere quello che meno probabilmente sarà necessario in futuro.
Le domande (mi dispiace, no TL; DR qui):
Non vedo che la gestione di LRU sia un problema - tuttavia, quello che mi interessa è:
- È fattibile?
- Come posso gestire al meglio i dati in termini di strutture dei dati, sia su disco che nella RAM?
- Come posso sfruttare al meglio la natura ricorsiva di questo codice?
- Come non far esplodere la RAM occupandoti solo dell'indirizzamento?
Probabilmente userò openCV in ambiente C ++ o Python.