Algoritmo parallelo - Struttura
Per applicare correttamente qualsiasi algoritmo, è molto importante selezionare una struttura dati adeguata. È perché una particolare operazione eseguita su una struttura dati può richiedere più tempo rispetto alla stessa operazione eseguita su un'altra struttura dati.
Example- Per accedere all'i- esimo elemento di un insieme utilizzando un array, potrebbe essere necessario un tempo costante ma utilizzando un elenco collegato, il tempo necessario per eseguire la stessa operazione potrebbe diventare un polinomio.
Pertanto, la selezione di una struttura dati deve essere fatta considerando l'architettura e il tipo di operazioni da eseguire.
Le seguenti strutture di dati sono comunemente utilizzate nella programmazione parallela:
- Lista collegata
- Arrays
- Rete Hypercube
Lista collegata
Un elenco collegato è una struttura di dati con zero o più nodi collegati da puntatori. I nodi possono o meno occupare posizioni di memoria consecutive. Ogni nodo ha due o tre parti: unadata part che memorizza i dati e gli altri due lo sono link fieldsche memorizzano l'indirizzo del nodo precedente o successivo. L'indirizzo del primo nodo è memorizzato in un puntatore esterno chiamatohead. L'ultimo nodo, noto cometail, generalmente non contiene alcun indirizzo.
Esistono tre tipi di elenchi collegati:
- Elenco collegato singolarmente
- Elenco doppiamente collegato
- Elenco collegato circolare
Elenco collegato singolarmente
Un nodo di un elenco collegato singolarmente contiene i dati e l'indirizzo del nodo successivo. Un puntatore esterno chiamatohead memorizza l'indirizzo del primo nodo.
Elenco doppiamente collegato
Un nodo di una lista doppiamente collegata contiene i dati e l'indirizzo sia del nodo precedente che di quello successivo. Un puntatore esterno chiamatohead memorizza l'indirizzo del primo nodo e il puntatore esterno chiamato tail memorizza l'indirizzo dell'ultimo nodo.
Elenco collegato circolare
Un elenco collegato circolare è molto simile all'elenco collegato singolarmente tranne per il fatto che l'ultimo nodo ha salvato l'indirizzo del primo nodo.
Array
Un array è una struttura di dati in cui possiamo memorizzare tipi di dati simili. Può essere unidimensionale o multidimensionale. Gli array possono essere creati staticamente o dinamicamente.
In statically declared arrays, dimensione e dimensione degli array sono note al momento della compilazione.
In dynamically declared arrays, dimensione e dimensione della matrice sono note in fase di esecuzione.
Per la programmazione della memoria condivisa, gli array possono essere utilizzati come una memoria comune e per la programmazione parallela dei dati, possono essere utilizzati partizionando in sotto-array.
Rete Hypercube
L'architettura Hypercube è utile per quegli algoritmi paralleli in cui ogni attività deve comunicare con altre attività. La topologia dell'ipercubo può facilmente incorporare altre topologie come anello e mesh. È anche noto come n-cubi, dovenè il numero di dimensioni. Un ipercubo può essere costruito ricorsivamente.
