Skip to content

AndreCagg/pagerank

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

12 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

PageRank

Fase di creazione del grafo

Per la lettura è stato utilizzato uno schema produttori-consumatori con un produttore e più consumatori. I consumatori si sincronizzano per accedere al buffer comune attraverso due semafori free_slots e data_items e una lock; i due semafori, rispettivamente, indicano il numero di posizioni libere (che sono già state esaminate) nel buffer circolare e il numero di posizioni occupate (che ancora devono essere esaminate). Dopo aver letto l'arco (una coppia sorgente-destinazione), se non è un arco loop e non è duplicato va inserito nell'array in, per parallelizzare quanto più possibile questa operazione, visto che comunque va eseguita in sezione critica perché si potrebbe voler inserire più archi nello stesso array contemporaneamente, si usano più mutex in modo da non serializzare inserimenti indipendenti, in particolare si usano lo 0,05% (parte superiore) dei mutex rispetto alla quantità dei nodi.

Fase di calcolo

Il thread principale (funzione pagerank) avvia i thread di calcolo e il gestore dei segnali. I thread che si occupano del calcolo (funzione ranker) accedono a un contatore condiviso (protetto con mutex) per sapere quale componente calcolare. Successivamente, calcolano la componente e, in locale, l'errore relativo alle componenti esaminate e il contributo dei dead-end relativo. Man mano che i thread terminano di calcolare le componenti, l'errore complessivo e il contributo complessivo dei dead-end vengono aggiornati. L'ultimo ranker segnala il termine del calcolo dell'errore mediante una postsu un semaforo, nel frattempo che il pagerank controlla se l'errore è minore della tolleranza oppure le iterazioni superano la soglia massima, i ranker si sospendono su una condition variable; dopo che il pagerank ha verificato l'errore e/o la soglia di iterazioni e ha stabilito se sono necessarie ulteriori iterazioni risveglia i ranker che nel caso si renda necessario proseguire accederanno ad un contatore condiviso (protetto con mutex) indicante la componente in esame e si calcolerà il vettore Y (sempre in parallelo). Solo dopo che tutte le componenti di Y sono state calcolate (lo si verifica tramite una barriera fatta con semafori) si può cominciare la successiva iterazione; in questa fase si verifica se è presente un segnale pending che bisogna gestire (lo si verifica tramite la variabile *segnale).

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

 
 
 

Contributors