HPC - La mappa del gatto di Arnold

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-10-22

La mappa del gatto di Arnold è una funzione caotica descritta negli anni '60 dal matematico russo Vladimir Igorevich Arnold (1937-2010). Nella sua versione discreta, la funzione trasforma una immagine \(P\) di dimensioni \(N \times N\) in una nuova immagine \(P'\) delle stesse dimensioni. Per ogni \(0 \leq x < N,\ 0 \leq y < N\), il pixel di coordinate \((x,y)\) in \(P\) viene spostato nella posizione \((x',y')\) di \(P'\) dove:

\[ x' = (2x + y) \bmod N, \qquad y' = (x + y) \bmod N \]

("mod" è l'operatore modulo, corrispondente all'operatore % del linguaggio C). Si può assumere che le coordinate \((0, 0)\) indichino il pixel in alto a sinistra e le coordinate \((N-1, N-1)\) quello in basso a destra, in modo da indicizzare l'immagine come se fosse una matrice in C.

La trasformazione di cui sopra equivale a deformare l'immagine originale, separandola poi in pezzi che vengono ricomposti in una nuova immagine delle dimensioni di quella di partenza. La Figura 1 mostra graficamente la trasformazione.

Figura 1: La mappa del gatto di Arnold
Figura 1: La mappa del gatto di Arnold

La mappa del gatto ha proprietà sorprendenti. Applicata ad una immagine ne produce una versione distorta. Applicata nuovamente a quest'ultima immagine, ne produce una ancora più distorta, e così via. Tuttavia, dopo un certo numero di iterazioni (il cui valore dipende da \(N\), ma che in ogni caso è sempre minore o uguale a \(3N\)) ricompare l'immagine di partenza! (si veda la Figura 2).

Figura 2: Alcune immagini ottenute iterando la mappa del gatto k volte
Figura 2: Alcune immagini ottenute iterando la mappa del gatto \(k\) volte

Il tempo minimo di ricorrenza per una immagine è il minimo numero di iterazioni della mappa del gatto che sono necessarie per riottenere l'immagine di partenza. Per l'immagine di esempio cat1368.pgm di dimensione \(1368 \times 1368\) il tempo minimo di ricorrenza è \(36\). Il tempo minimo di ricorrenza dipende dalla dimensione dell'immagine; non è nota al momento una formula analitica "semplice" per calcolare il tempo minimo di ricorrenza a partire da \(N\).

Viene fornita una implementazione seriale di un programma che calcola la \(k\)-esima iterata della mappa del gatto. Il programma legge da standard input una immagine in formato PGM (Portable GrayMap), e produce su standard output una nuova immagine ottenuta applicando \(k\) volte la mappa del gatto. Ad esempio:

    ./omp-cat-map 100 < cat1368.pgm > cat1368-100.pgm

genera un file cat1368-100.pgm contenente l'immagine che si ottiene iterando \(k=100\) volte la mappa del gatto sull'immagine cat1368.pgm. Per visualizzare il risultato sotto Windows può essere necessario convertire le immagini in un altro formato, ad esempio JPEG:

    convert cat1368-100.pgm cat1368-100.jpeg

Si richiede di parallelizzare il corpo della funzione cat_map() mediante OpenMP. A tale scopo è utile tenere presente che la mappa del gatto è invertibile, il che implica che la funzione sia biiettiva. In particolare, questo garantisce che due punti diversi \((x_1, y_1)\) e \((x_2, y_2)\) verranno sempre mappati in punti diversi (\(x'_1, y'_1)\) e \((x'_2, y'_2)\).

Per compilare:

    gcc -std=c99 -Wall -Wpedantic -fopenmp omp-cat-map.c -o omp-cat-map

Per eseguire:

    ./omp-cat-map k < input_file > output_file

Esempio:

    ./omp-cat-map 100 < cat1368.pgm > cat1368-100.pgm

Estensione

La funzione cat_map() fornita si basa sullo schema seguente:

for (i=0; i<k; i++) {
    for (y=0; y<N; y++) {
        for (x=0; x<N; x++) {
            /* applica la mappa al punto di coord. (x, y) */
        }
    }
}

In questo caso si può applicare la tecnica di loop interchange vista a lezione per riscrivere l'iterazione nel modo seguente:

for (y=0; y<N; y++) {
    for (x=0; x<N; x++) {
        for (i=0; i<k; i++) {
            /* applica la mappa al punto di coord. (x, y) */
        }
    }
}

In questa seconda versione è possibile parallelizzare uno dei due cicli più esterni (o entrambi, usando la clausola collapse(2)). Parallelizzare questa seconda versione, e confrontarne le prestazioni con la precedente.

Per chi vuole approfondire

Qual è il tempo minimo di ricorrenza dell'immagine cat1024.pgm di dimensioni \(1024 \times 1024\)? Per rispondere è possibile procedere per tentativi iterando la mappa del gatto \(1, 2, 3, \ldots\) volte, controllando di volta in volta se si ottiene l'immagine di partenza. Esiste però un metodo migliore che non richiede di conoscere l'immagine di input ma solo la sua dimensione. L'idea è la seguente: supponiamo che un pixel dell'immagine abbia tempo minimo di ricorrenza 15, e un altro pixel abbia tempo minimo di ricorrenza 21. Il tempo minimo necessario affinché entrambi i punti ritornino nelle rispettive posizioni iniziale è il minimo comune multiplo di 21 e 15 (cioè 105). Estendendo il ragionamento, il tempo minimo di ricorrenza dell'immagine è il minimo comune multiplo di tutti i tempi di ricorrenza dei punti.

Il file omp-cat-map-rectime.c contiene lo scheletro di un programma per il calcolo del tempo minimo di ricorrenza di una immagine di dimensioni \(N \times N\), con \(N\) parametro di input. Viene fornita la funzione per calcolare il minimo comune multiplo di due interi. Completare il programma e parallelizzarlo usando le direttive OpenMP che si ritengono appropriate.

La tabella 1 mostra i tempi minimi di ricorrenza per alcuni valori della dimensione \(N\) dell'immagine.

Tabella 1
\(N\) Tempo minimo di ricorrenza
64 48
128 96
256 192
512 384
1368 36

La Figura 3 mostra il tempo minimo di ricorrenza per dimensioni fino a \(1024 \times 1024\); nonostante l'andamento irregolare, si può osservare come i valori tendano ad allinearsi lungo alcune rette.

Figura 3: Tempo minimo di ricorrenza in funzione della dimensione dell'immagine
Figura 3: Tempo minimo di ricorrenza in funzione della dimensione dell'immagine

File