HPC - Insieme di Mandelbrot

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-10-28

Benoit Mandelbrot (1924--2010)
Benoit Mandelbrot (1924--2010)

Il file mpi-mandelbrot.c contiene lo scheletro di una implementazione MPI dell'algoritmo che calcola l'insieme di Mandelbrot. Non si tratta di una versione realmente parallela, in quanto il processo master è l'unico che esegue computazioni.

Il programma accetta come parametro opzionale la dimensione verticale dell'immagine, ossia il numero di righe (default 1024). La risoluzione orizzontale viene calcolata automaticamente dal programma in modo da includere l'intero insieme. Il programma produce un file mandebrot.ppm contenente una immagine dell'insieme di Mandelbrot in formato PPM (Portable Pixmap). Se non si dispone di un programma per visualizzare questo formato, lo si può convertire, ad esempio, in PNG dando sul server il comando:

    convert mandelbrot.ppm mandelbrot.png

Scopo di questo esercizio è quello di sviluppare una versione realmente parallela, in cui tutti i processi MPI cooperino al calcolo dell'immagine. Per fare questo, si partizioni l'immagine a blocchi per righe, dove il numero di blocchi è uguale al numero di processi MPI, in modo che ogni processo calcoli una porzione dell'immagine come schematizzato nella Figura 1.

Figura 1: Esempio di suddivisione del dominio per il calcolo dell'insieme di Mandelbrot con 4 processi MPI
Figura 1: Esempio di suddivisione del dominio per il calcolo dell'insieme di Mandelbrot con 4 processi MPI

Più in dettaglio, ciascun processo calcola una porzione di immagine di dimensione \(\mathit{xsize} \times (\mathit{ysize}/P)\), dove \(P\) è il numero di processi; per questa fase non serve alcuna comunicazione. Successivamente, il processo 0 assembla le porzioni di immagine calcolate dai vari processi mediante la funzione MPI_Gather(). Poiché l'immagine è stata decomposta in blocchi per righe, ciascuna porzione è rappresentata da un array di \((3 \times \mathit{xsize} \times \mathit{ysize} / P)\) elementi di tipo MPI_BYTE (ogni pixel è composto da 3 byte).

Si assuma che ysize sia un multiplo di \(P\); una volta ottenuto un programma corretto, lo si modifichi per gestire dimensioni verticali arbitrarie; per fare ciò è possibile delegare al processo 0 il calcolo della porzione di immagine corrispondente alle ultime (ysize % P) righe, oppure usare MPI_Gatherv() per riassemblare l'immagine a partire da frammenti di dimensione diversa.

Suggerisco di conservare la versione seriale del programma per usarla come riferimento. Per verificare in modo empirico la correttezza del programma parallelo, consiglio di confrontare il risultato con quello prodotto dalla versione seriale: le due immagini devono risultare identiche byte per byte. Per confrontare due immagini si può usare il comando cmp dalla shell di Linux:

    cmp file1 file2

stampa un messaggio se e solo se file1 e file2 differiscono.

Per compilare:

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

Per eseguire:

    mpirun -n NPROC ./mpi-mandelbrot [ysize]

Esempio:

    mpirun -n 4 ./mpi-mandelbrot 800

scrive il risultato sul file mandelbrot.ppm

File