HPC - Automa cellulare della "regola 30"

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-11-10

Quando abbiamo parlato dei pattern per la programmazione parallela abbiamo introdotto gli automi cellulari (CA) come semplice esempio di computazioni di tipo stencil. In questo esercizio consideriamo l'automa cellulare prodotto dalla regola 30.

L'automa cellulare è costituito da un array x[N] di \(N\) interi (usiamo il tipo signed char e ll corrispondente MPI_CHAR), ciascuno dei quali può avere valore 0 oppure 1. Lo stato dell'automa evolve durante istanti discreti nel tempo: lo stato di una cella al tempo \(t+1\) dipende dal suo stato e da quello dei due vicini al tempo \(t\). Assumiamo un dominio ciclico, per cui i vicini della cella \(x[0]\) sono \(x[N-1]\) e \(x[1]\) e i vicini della cella \(x[N-1]\) sono \(x[N-2]\) e \(x[0]\) (Figura 1).

Figura 1: Computazione stencil della Regola 30
Figura 1: Computazione stencil della Regola 30

Dati i valori correnti \(pqr\) di tre celle adiacenti, il nuovo valore \(q'\) della cella centrale è determinato in base alla Tabella 1.

Tabella 1: Regola 30 (■ = 1, □ = 0):
Configurazione corrente (\(pqr\)) ■■■ ■■□ ■□■ ■□□ □■■ □■□ □□■ □□□
Nuovo stato della cella centrale (\(q'\))

(si noti che la sequenza □□□■■■■□ = 00011110, che si legge sulla seconda riga della tabella, rappresenta il numero 30 in binario, da cui il nome "regola 30"). Qualche ulteriore informazione su questo automa cellulare si può trovare in queste slide.

Il file mpi-rule30.c contiene lo scheletro di una implementazione seriale del calcolo dell'evoluzione dell'automa. Inizialmente tutte le celle sono nello stato 0, ad eccezione di quella in posizione \(N/2\). Il programma accetta sulla riga di comando la dimensione del dominio \(N\) e il numero di passi da calcolare (se non indicati, si usano dei valori di default). Al termine dell'esecuzione il processo 0 produce un file rule30.pbm contenente una immagine simile alla Figura 2.

Figura 2: Evoluzione dell'automa cellulare della "regola 30" partendo da una singola cella attiva al centro
Figura 2: Evoluzione dell'automa cellulare della "regola 30" partendo da una singola cella attiva al centro

È curioso osservare che il pattern della Figura 2 è simile a quello presenti nelle conchiglie del Conus Textile, un mollusco marino altamente velenoso (Figura 3) che fortunatamente si trova solo nei mari tropicali.

Figura 3: Conus Textile Di Richard Ling - Own work; Location: Cod Hole, Great Barrier Reef, Australia, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=293495
Figura 3: Conus Textile Di Richard Ling - Own work; Location: Cod Hole, Great Barrier Reef, Australia, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=293495

Ogni riga dell'immagine rappresenta lo stato dell'automa in un istante di tempo; il colore dei pixel rappresenta lo stato di ciascuna cella (1 = nero, 0 = bianco). Il tempo avanza dall'alto verso il basso, quindi la prima riga rappresenta lo stato al tempo 0, la seconda riga lo stato al tempo 1 e così via.

Lo scopo di questo esercizio è di sviluppare una versione realmente parallela del programma, in cui il calcolo di ogni riga dell'immagine venga effettuato in parallelo da tutti i processi MPI. Il programma deve operare secondo i passi mostrati in Figura 4.

Figura 4: Schema di calcolo dell'evoluzione di un automa cellulare usando MPI
Figura 4: Schema di calcolo dell'evoluzione di un automa cellulare usando MPI
  1. Il dominio viene distribuito ai \(P\) processi MPI usando MPI_Scatter(); si assuma che \(N\) sia multiplo di \(P\). Ciascuna partizione deve includere due ghost cell (una a sinistra e una a destra, mostrate tratteggiate in figura) che sono necessarie per calcolare lo stato successivo, come discusso a lezione.

  2. Ogni processo comunica ai vicini i valori delle celle sul proprio bordo usando MPI_Sendrecv(). Questa fase serve per riempire le ghost cell delle partizioni locali.

  3. Ciascun processo calcola la configurazione successiva della propria porzione di dominio, sfruttando i valori delle ghost cell. Si può fare riferimento alla funzione step() inclusa nello scheletro di programma.

  4. Ciascun processo invia la propria porzione di dominio, contenente la nuova configurazione, al master che le assembla usando MPI_Gather() per poi salvarla sul file di output.

Al termine del passo 4 si riparte dal passo 2; dato che il nuovo stato dell'automa è già presente nella memoria di ciascun processo, non serve rifare MPI_Scatter() ogni volta. Per i dettagli si rimanda ai lucidi in cui abbiamo discusso i pattern per la programmazione parallela. Il file mpi-rule30.c va usato come indicazione di massima su come procedere; sarà necessario modificarne pesantemente la struttura per poter realizzare lo schema parallelo descritto sopra.

I punti critici di questo esercizio sono: (i) l'uso di MPI_Scatter() e MPI_Gather() per distribuire e concatenare i sottodomini, e (ii) l'uso di MPI_Sendrecv() per consentire ai processi lo scambio delle ghost cell.

Per quanto riguarda il punto (i), ciascun sottodominio dovrà essere composto da (\(\mathit{local\_width} = N/\mathit{comm\_sz} + 2\)) elementi (i due elementi aggiuntivi rappresentano le ghost cell). Indichiamo con cur[] il dominio completo usato dal processo 0 e con local_cur[] la porzione di dominio assegnata a ciascun processo.

Sebbene non sia necessario per la versione MPI, supponiamo che anche cur[] sia esteso con due ghost cell. Allora la distribuzione di cur[] avrà la forma:

MPI_Scatter( &cur[LEFT],        /* sendbuf    */
             N/comm_sz,         /* Sendcount  */
             MPI_INT,           /* sendtype   */
             &local_cur[LOCAL_LEFT],/* recvbuf    */
             N/comm_sz,         /* recvcount  */
             MPI_INT,           /* recvtype   */
             0,                 /* root       */
             MPI_COMM_WORLD     /* comm       */
             );

L'istruzione precedente distribuisce \(N/\mathit{comm\_sz}\) elementi di cur[] tra i processi MPI in modo ciclico: ciascun processo riceve il proprio blocco a partire dall'indirizzo di memoria &local_cur[LEFT], lasciando invariato il valore delle ghost cell di sinistra e di destra.

Figura 5: Uso di MPI_Sendrecv() per lo scambio di ghost cell
Figura 5: Uso di MPI_Sendrecv() per lo scambio di ghost cell

Per quanto riguarda il punto (ii), lo scambio di celle sul bordo tra processi adiacenti mediante MPI_Sendrecv() richiede due fasi (cioè occorre usare due operazioni MPI_Sendrecv(), si veda la Figura 5): nella prima fase ogni processo invia il valore dell'ultima cella a destra del dominio locale al processo successivo, e riceve il valore della ghost cell di sinistra dal processo precedente. Di conseguenza, la chiamata MPI_Sendrecv() deve avere come destinatario il processo successivo e come mittente il processo precedente. Nella seconda fase ogni processo invia il contenuto della prima cella al processo precedente, e riceve il valore della ghost cell di destra dal processo successivo.

Per compilare:

    mpicc -std=c99 -Wall -Wpedantic mpi-rule30.c -o mpi-rule30

Per eseguire:

    mpirun -n P ./mpi-rule30 [width [steps]]

Esempio, usando 4 processi MPI:

    mpirun -n 4 ./mpi-rule30 1024 1024

Il risultato sarà nel file rule30.pbm

File