Struttura dei dati per un piccolo numero di agenti in un mondo 2D relativamente grande

Sembra che tu abbia fondamentalmente un automa cellulare. Dai un'occhiata a Hashlife : un algoritmo basato su un albero quad che può essere usato per simulare automi cellulari spazialmente sparsi, strutturalmente simili molto molto velocemente. A seconda del tuo problema, puoi utilizzarlo direttamente o almeno trarre ispirazione.

Hai citato i seguenti paramenters per il tuo mondo,

• Hai un mondo 2D (griglia NxN dove N = 1000).
• Ci sono agenti situati nel mondo, ogni agente in una posizione di griglia.
• Gli agenti possono spostarsi.
• Ci possono essere pochi agenti (5) per molti agenti (1M).
• Il mondo potrebbe essere scarsamente popolato.
• Devi trovare le posizioni che dispongono di agenti e poi elaborarle.
• Devi coprire tutti gli agenti.
• Vorresti elaborare il minor numero possibile di elementi della griglia.
• Vuoi una struttura dati suscettibile di parallelizzazione
• Devi essere in grado di trovare i vicini e gli agenti nei vicini

Una scansione esaustiva dell'intero mondo 2D ti troverà agenti, ma potrebbe essere inefficiente (osservare le posizioni della griglia 1M per soli 5 agenti è uno spreco).

Domande:

• C'è una priorità per gli agenti? assumere no.
• Puoi saltare alcuni agenti? assumere no,.
• È importante quale ordine si esaminano gli agenti? presumo qualsiasi.
• Qual è il maggior numero di agenti che ti aspetti da una qualsiasi posizione della griglia? supponiamo 50.

Suggerimenti:

Mantieni una struttura dati (griglia o albero) contando il numero di agenti in una data posizione della griglia. Solo le posizioni 1M sono abbastanza semplici e potresti utilizzare un singolo byte per posizione della griglia per contare fino a 2 ^ 7 (0-127), agenti. Utilizzare un'area di overflow per le posizioni con più agenti (presumendo che in un luogo siano presenti più di 127 agenti: si ha una media prevista?). bloccare / parallelizzare in base alle regioni delle aree della griglia (10x10).

Mantieni gli agenti ordinati in qualche albero (quadruplo, trie in base alla posizione della griglia), ma l'albero non è più parallelizzabile. Il mio suggerimento qui sarebbe un elenco 2D di elenchi (o vettore di vettori) ordinati per coordinate di griglia.

Vuoi scegliere un sistema di coordinate in cui puoi facilmente calcolare i vicini e scoprire se gli agenti si trovano nei vicini - nota che la struttura dei conteggi citata sarà preziosa qui.

Quello che stai cercando è un tipo topologico dei tuoi dati, e un quadruplo è un approccio. Ma ti importa di tutti 'vicini'. Il problema che discuti è simile sotto alcuni aspetti all'analisi degli elementi finiti.

Hai menzionato lo spostamento e la replica, che cambiano sia stato non solo di sé, ma altri elementi della griglia e analisi dell'albero. Questi metodi influenzano il modo in cui viene eseguita la parallelizzazione.

La struttura dei dati diventerà evidente dopo aver analizzato il problema e i vincoli.

Hai tre obiettivi di implementazione: sequenziale, OpenMP e MPI. Di questi, MPI è il più vincolato, IMO. Lavora attraverso come la simulazione può essere costruita usando MPI, e vedrai che un problema chiave è il modello di controllo del processo (hai già accennato a questo). Da quello che hai detto, IMO gli attori dovrebbero essere gli elementi attivi. Sfida questa idea.

Man mano che sviluppi il tuo modello concettuale dei processi e della loro comunicazione, incontrerai problemi di concorrenza, localizzazione dei dati e larghezza di banda dei messaggi. Lavora attraverso questi e avrai le tue strutture dati.

Gli altri due modelli ne saranno versioni semplificate.

Per cominciare, tieni solo un elenco di tutti gli agenti con le loro posizioni. Quando si lavora con un agente, scansionare l'elenco per trovare tutti gli altri agenti abbastanza vicini da essere interessanti. Salta la creazione di una vera griglia della griglia mondiale; ti limita troppo e spreca troppa memoria.

Quindi, dato che il tuo elenco di agenti diventa davvero grande e perdi troppo tempo a guardare agenti troppo lontani, imponi una griglia al tuo mondo. Con un mondo 1000x1000, potrebbe funzionare una griglia 100x100. Ogni elemento contiene un elenco di agenti che si trovano all'interno delle sue 100 celle del mondo. Ora per controllare i vicini, guarda nella cella della griglia dell'agente e prendi tutti gli occupanti che si trovano anche nelle celle del mondo adiacenti. In alcuni casi, potrebbe essere necessario controllare anche alcune celle della griglia adiacenti. Questa griglia ti consente di gestire 100.000 elementi come se fossero solo 100 circa riguardo a quali agenti si trovano in celle del mondo adiacenti o addirittura vicine.

Un quadrifoglio potrebbe funzionare meglio se i tuoi agenti tendono a raggrupparsi insieme, ma questo diventa complicato anche senza il "parallelismo". La mia ipotesi è la combinazione di un elenco di tutti agenti, ogni agente con la sua posizione di cella della griglia mondiale e la griglia di medie dimensioni con elenchi di agenti all'interno di ogni limite di cella, dovrebbe funzionare correttamente.

(Le dimensioni della griglia di medie dimensioni devono basarsi su una combinazione delle dimensioni del tuo mondo e del numero totale di agenti. Ottenere le dimensioni perfette è difficile, ma quasi tutte le dimensioni saranno di gran lunga superiori agli estremi del non utilizzando una griglia e utilizzando una griglia di dimensioni mondiali.)

(nota che con questa tecnica la tua griglia del mondo potrebbe diventare veramente vasta - trilioni di cellule su un lato - senza causare alcuna difficoltà.) Mente, i tuoi agenti dovrebbero essere in grado di vedere attraverso un bel registro di celle in per trovare l'altro.)