Algorithme parallèle - Structure

Pour appliquer correctement un algorithme, il est très important que vous sélectionniez une structure de données appropriée. C'est parce qu'une opération particulière effectuée sur une structure de données peut prendre plus de temps par rapport à la même opération effectuée sur une autre structure de données.

Example- Pour accéder au i ème élément d'un ensemble en utilisant un tableau, cela peut prendre un temps constant mais en utilisant une liste chaînée, le temps nécessaire pour effectuer la même opération peut devenir un polynôme.

Par conséquent, la sélection d'une structure de données doit se faire en tenant compte de l'architecture et du type d'opérations à effectuer.

Les structures de données suivantes sont couramment utilisées dans la programmation parallèle -

  • Liste liée
  • Arrays
  • Réseau Hypercube

Liste liée

Une liste chaînée est une structure de données ayant zéro ou plusieurs nœuds connectés par des pointeurs. Les nœuds peuvent ou non occuper des emplacements mémoire consécutifs. Chaque nœud comprend deux ou trois parties - unedata part qui stocke les données et les deux autres sont link fieldsqui stockent l'adresse du nœud précédent ou suivant. L'adresse du premier nœud est stockée dans un pointeur externe appeléhead. Le dernier nœud, appelétail, ne contient généralement aucune adresse.

Il existe trois types de listes liées -

  • Liste liée individuellement
  • Liste doublement liée
  • Liste liée circulaire

Liste liée individuellement

Un nœud d'une liste liée individuellement contient des données et l'adresse du nœud suivant. Un pointeur externe appeléhead stocke l'adresse du premier nœud.

Liste doublement liée

Un nœud d'une liste doublement liée contient des données et l'adresse du nœud précédent et suivant. Un pointeur externe appeléhead stocke l'adresse du premier nœud et le pointeur externe appelé tail stocke l'adresse du dernier nœud.

Liste liée circulaire

Une liste chaînée circulaire est très similaire à la liste chaînée unique sauf le fait que le dernier nœud a enregistré l'adresse du premier nœud.

Tableaux

Un tableau est une structure de données dans laquelle nous pouvons stocker des types de données similaires. Il peut être unidimensionnel ou multidimensionnel. Les tableaux peuvent être créés de manière statique ou dynamique.

  • Dans statically declared arrays, la dimension et la taille des tableaux sont connues au moment de la compilation.

  • Dans dynamically declared arrays, la dimension et la taille du tableau sont connues au moment de l'exécution.

Pour la programmation en mémoire partagée, les tableaux peuvent être utilisés comme mémoire commune et pour la programmation parallèle de données, ils peuvent être utilisés par partitionnement en sous-tableaux.

Réseau Hypercube

L'architecture Hypercube est utile pour les algorithmes parallèles où chaque tâche doit communiquer avec d'autres tâches. La topologie Hypercube peut facilement intégrer d'autres topologies telles que l'anneau et le maillage. Il est également connu sous le nom de n-cubes, oùnest le nombre de dimensions. Un hypercube peut être construit de manière récursive.