Algorithme parallèle - Introduction

Un algorithmest une séquence d'étapes qui prennent des entrées de l'utilisateur et, après quelques calculs, produit une sortie. UNEparallel algorithm est un algorithme qui peut exécuter plusieurs instructions simultanément sur différents appareils de traitement, puis combiner toutes les sorties individuelles pour produire le résultat final.

Traitement simultané

La facilité d'accès aux ordinateurs et la croissance d'Internet ont changé la façon dont nous stockons et traitons les données. Nous vivons à une époque où les données sont disponibles en abondance. Chaque jour, nous traitons d'énormes volumes de données qui nécessitent un calcul complexe et cela aussi, en un temps record. Parfois, nous devons extraire des données d'événements similaires ou interdépendants qui se produisent simultanément. C'est là que nous avons besoinconcurrent processing qui peut diviser une tâche complexe et la traiter plusieurs systèmes pour produire la sortie en un temps record.

Le traitement simultané est essentiel lorsque la tâche implique le traitement d'une énorme masse de données complexes. Les exemples incluent - l'accès à de grandes bases de données, les tests d'aéronefs, les calculs astronomiques, la physique atomique et nucléaire, l'analyse biomédicale, la planification économique, le traitement d'images, la robotique, les prévisions météorologiques, les services Web, etc.

Qu'est-ce que le parallélisme?

Parallelismest le processus de traitement simultané de plusieurs ensembles d'instructions. Cela réduit le temps de calcul total. Le parallélisme peut être implémenté en utilisantparallel computers,c'est à dire un ordinateur avec de nombreux processeurs. Les ordinateurs parallèles nécessitent un algorithme parallèle, des langages de programmation, des compilateurs et un système d'exploitation prenant en charge le multitâche.

Dans ce tutoriel, nous aborderons uniquement parallel algorithms. Avant d'aller plus loin, parlons d'abord des algorithmes et de leurs types.

Qu'est-ce qu'un algorithme?

Un algorithmest une séquence d'instructions suivies pour résoudre un problème. Lors de la conception d'un algorithme, nous devons considérer l'architecture de l'ordinateur sur lequel l'algorithme sera exécuté. Selon l'architecture, il existe deux types d'ordinateurs -

• Ordinateur séquentiel
• Ordinateur parallèle

En fonction de l'architecture des ordinateurs, nous avons deux types d'algorithmes -

• Sequential Algorithm - Un algorithme dans lequel certaines étapes consécutives d'instructions sont exécutées dans un ordre chronologique pour résoudre un problème.

• Parallel Algorithm- Le problème est divisé en sous-problèmes et est exécuté en parallèle pour obtenir des sorties individuelles. Plus tard, ces sorties individuelles sont combinées ensemble pour obtenir la sortie finale souhaitée.

Il n'est pas facile de diviser un gros problème en sub-problems. Les sous-problèmes peuvent avoir une dépendance de données entre eux. Par conséquent, les processeurs doivent communiquer entre eux pour résoudre le problème.

Il s'est avéré que le temps nécessaire aux processeurs pour communiquer entre eux est supérieur au temps de traitement réel. Ainsi, lors de la conception d'un algorithme parallèle, une utilisation appropriée du processeur doit être envisagée pour obtenir un algorithme efficace.

Pour concevoir correctement un algorithme, nous devons avoir une idée claire de la base model of computation dans un ordinateur parallèle.

Modèle de calcul

Les ordinateurs séquentiels et parallèles fonctionnent sur un ensemble (flux) d'instructions appelées algorithmes. Cet ensemble d'instructions (algorithme) indique à l'ordinateur ce qu'il doit faire à chaque étape.

En fonction du flux d'instructions et du flux de données, les ordinateurs peuvent être classés en quatre catégories -

• Ordinateurs à flux d'instructions unique, flux de données unique (SISD)
• Flux d'instructions unique, ordinateurs à flux de données multiples (SIMD)
• Ordinateurs à flux d'instructions multiples et à flux de données unique (MISD)
• Flux d'instructions multiples, ordinateurs à flux de données multiples (MIMD)

Ordinateurs SISD

Les ordinateurs SISD contiennent one control unit, one processing unit, et one memory unit.

Dans ce type d'ordinateurs, le processeur reçoit un seul flux d'instructions de l'unité de contrôle et fonctionne sur un seul flux de données de l'unité de mémoire. Lors du calcul, à chaque étape, le processeur reçoit une instruction de l'unité de contrôle et opère sur une seule donnée reçue de l'unité mémoire.

Ordinateurs SIMD

Les ordinateurs SIMD contiennent one control unit, multiple processing units, et shared memory or interconnection network.

Ici, une seule unité de contrôle envoie des instructions à toutes les unités de traitement. Lors du calcul, à chaque étape, tous les processeurs reçoivent un seul ensemble d'instructions de l'unité de contrôle et opèrent sur différents ensembles de données de l'unité mémoire.

Chacune des unités de traitement a sa propre unité de mémoire locale pour stocker à la fois des données et des instructions. Dans les ordinateurs SIMD, les processeurs doivent communiquer entre eux. Ceci est fait parshared memory ou par interconnection network.

Alors que certains processeurs exécutent un ensemble d'instructions, les processeurs restants attendent leur prochain ensemble d'instructions. Les instructions de l'unité de contrôle déterminent quel processeur seraactive (exécuter des instructions) ou inactive (attendez la prochaine instruction).

Ordinateurs MISD

Comme son nom l'indique, les ordinateurs MISD contiennent multiple control units, multiple processing units, et one common memory unit.

Ici, chaque processeur a sa propre unité de contrôle et ils partagent une unité de mémoire commune. Tous les processeurs reçoivent des instructions individuellement de leur propre unité de contrôle et ils fonctionnent sur un seul flux de données selon les instructions qu'ils ont reçues de leurs unités de contrôle respectives. Ce processeur fonctionne simultanément.

Ordinateurs MIMD

Les ordinateurs MIMD ont multiple control units, multiple processing units, et un shared memory ou interconnection network.

Ici, chaque processeur possède sa propre unité de commande, une unité de mémoire locale et une unité arithmétique et logique. Ils reçoivent différents ensembles d'instructions de leurs unités de contrôle respectives et fonctionnent sur différents ensembles de données.

Remarque

• Un ordinateur MIMD qui partage une mémoire commune est appelé multiprocessors, tandis que ceux qui utilisent un réseau d'interconnexion sont appelés multicomputers.

• Sur la base de la distance physique des processeurs, les multi-ordinateurs sont de deux types -

  • Multicomputer - Lorsque tous les processeurs sont très proches les uns des autres (par exemple, dans la même pièce).

  • Distributed system - Lorsque tous les processeurs sont éloignés les uns des autres (par exemple dans les différentes villes)