Skip to content

Latest commit

 

History

History
52 lines (41 loc) · 2.89 KB

README.md

File metadata and controls

52 lines (41 loc) · 2.89 KB
Raw

Pagerank + PThread

Implementazione in C dell'algoritmo "Pagerank", parallelizzato con thread POSIX.

INPUT

./pagerank -d D -t T -e E -k K -m M filename.mtx

Paramtri opzionali:

  • D dumping factor
  • T number thread aux
  • E max error
  • M max iteration
  • K number of best rank

Parametri obbligatori: filename.mtx, formattato nel seguente modo:

  • % righe di commento iniziali
  • la prima riga non commentata contiene 3 interi (r c n) dove i primi due sono il numero di nodi e il terzo è il numero di archi
  • elenco di archi nel formato "%d %d\n"

OUTPUT

Number of nodes: V
Number of dead-end nodes: V
Did not converge after V iterations / Converged after V iterations
Sum of ranks: V (should be V)
Top V nodes:
ind1) rank[ind1]
ind2) rank[ind2]
ind3) rank[ind3]

FUNZIONAMENTO

  1. La lettura del file.mtx avviene tramite lo schema produttore / consumatore, dove l'unico produttore (main) inserisce gli archi nel buffer, e i consumatori leggono gli archi e creano il grafo;
  2. La parallelizzazione del calcolo del pagerank avviene nel seguente modo:
    1. Il thread principale crea i thread aux necessari per eseguire i calcoli del pagerank ad ogni iterazione T, T+1, ..., fino a raggiungere la convergenza;
    2. Il thread principale avvia i thread aux e segnala l'inizio di una nuova iterazione tramite un semaforo posix (sem_start);
    3. I thread ausiliari, dopo aver ricevuto il segnale, procedono con i calcoli. Ognuno di essi ha accesso ad una variabile condivisa atomica (atomic_int *pos) da cui preleva il valore e incrementa con il batch_size. Dopo aver prelevato il batch il thread aux correte calcola i componenti del pagerank dall'indice start all'indice end e poi riprova ad acquisire un nuovo batch;
    4. Dopo che gli indici sono stati esauriti i thread ausiliari si mettono in coda per incrementare l'errore al passo corrente e il contributo dei nodi dead-end per il T+1. Poi segnalano la fine del lavoro al tempo T con un semaforo posix (sem_end);
    5. Il controllo passa al thread principale che verifica la convergenza e comunica se continuare il calcolo (ripartire dal punto 2.2) o terminare;

Funzionamento del BATCH
I thread lavorano su piccoli intervalli, cercando un compromesso tra "lentessa se acquisissero un indice per volta" e "dividere gli indici staticamente vuol dire non parallelizzare".

GESTIONE DEI SEGNALI

Nel programma è prevista l'interazione mediante il segnale SIGUSR1, in particolare, ogni volta che il thread incaricato di gestire i segnali riceve questo segnale stamperà su stdout il rank massimo dell'iterazione corrente (del calcolo del pagerank).

TEST

make
valgrind ./pagerank -e 1e-9 -k5 9nodi.mtx 1> 9nodi.rk 2> 9nodi.log
diff -bB 9nodi.rk 9nodi.sol

In un altro terminale lanciare il comando "pkill -SIGUSR1 pagerank".