Discussion :

[wassim_boy]

Bonjour,

J'ai du mal à comprendre la différence entre un algorithme parallèle et séquentiel. En théorie j'ai compris la différence mais lorsque je souhaite écrire un algorithme (en pseudo-code) je n'arrive pas à illustrer le principe du parallèle avec du pseudo-code.

Par exemple, si je lis un algorithme je suis incapable de dire s'il est parallèle ou séquentiel (lorsqu'il n'y a pas l'instruction faire en parallèle).

Est ce que quelqu'un peut-il m'aider SVP? J'aimerai apprendre à écrire des algorithme parallèle en pseudo-code.

Merci et à bientôt.

[davcha]

Quand tu écris un algo en pseudocode, c'est dans un but pédagogique. Donc tu te dois avant tout d'être clair. Donc, si tu souhaites qu'une partie soit parallèle, le mieux est certainement de le dire explicitement.

La preuve est que tu as du mal à deviner si un algo est parallèle si ce n'est pas explicitement spécifié.

[Gakusei]

Bonjour,
Concrêtement algorithme séquentiel:
Le SISD (Single Instruction, Single Data)

En revanche les algorithme parallèles sont diverses (et lié à l'architecture de l'ordinateur):
-> MIMD (Multiple Instruction, Multiple Data): C'est du "multi-processing" (sur CPU). On peux utiliser une instruction par "processeurs" sur différentes données.

-> SIMD (Single Instruction, Multiple Data): C'est généralement utilisée dans du GPGPU ( programmation sur carte graphique). L'idée ici est d'utiliser une unique instruction ( fonction kernel ) sur différentes données stoquées en mémoire partagée ( mémoire texture ). Moins évident que le précédent.

-> MISD: Je n'ai jamais eu à l'utiliser mais c'est peu utiliser apparemment.

Finalement, si tu veux reconnaître si un algorithme utilise du parallèle en pseudo code, il faut regarder comment sont gérées les données d'entrées ( si elles sont découpé par exemple).
Mais ta question reste relativement vague. Tout dépend à quel niveau de programmation (proche de la machine ou Orienté Objet) tu te places.
Je suppose que tu utiliseras un langage haut niveau donc en général les fonction sont suffisamment explicites pour savoir si un algorithme est en parallèle dans le cas du MIMD. Donc je ne vois pas d'aspect réellement intéressant dans l'utilisation en pseudo code à part peut être dans le cas d'interaction par évènement entre les processeurs et l'utilisation des sémaphores ( Permet de gérer des synchronisations entre les différents processus).

Pour le SIMD je ne sais pas si c'est intéressant de programmer en pseudo code car les scripts sont fortement liés aux librairies/cartes graphiques ( OpenCL ou Cuda par exemple) de ce que je me souvienne.

[Franck Dernoncourt]

Quand tu écris un algo en pseudocode, c'est dans un but pédagogique. Donc tu te dois avant tout d'être clair. Donc, si tu souhaites qu'une partie soit parallèle, le mieux est certainement de le dire explicitement.

Exemple :

[srvremi]

Si tu te limites à une parallélisation multi-coeurs, tu peux aussi le mettre facilement en pseudo-code.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
/* boucle for repartie sur n coeurs */
for i:=1 to 100 do
begin
   /* instructions */
end;

@+
Rémi

[souviron34]

Est ce que quelqu'un peut-il m'aider SVP? J'aimerai apprendre à écrire des algorithme parallèle en pseudo-code.

Outre ce qu"on a dit plus haut, voici un petit exemple. Le parallèlisme est la utilisé pour effectuer en prallèle des tâches indépendantes. Ces tâches peuvent être réellement indépendantes (par exemple lire N fichiers différents), ou potentielllement indépendantes (une boucle où chaque itération est indépendante de la précédente, pur l'exemple le plus simple).

Si l'on prend l'exemple le plus courant d'une boucle. Si mon algo initial est :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
pour i = 0 jusqu'à i = N
 
    Faire a[i] = a[i] * 10
 
fin pour

Cette formulation est séquentielle : on calcule a[2] une fois qu'on a calculé a[1], puis a[3], etc etc..

Maintenant, on peut le parallèliser par exemple en fonction du nombre de CPUs, puisque chaque itération est indépendante des autres :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
start = 0
pour i = 0 jusqu'à i = N
 
    if (  ( i % NCPU) == 0 )
           start = i 
 
    num_cpu = (i - start) / NCPU
 
    affecter CPU num_cpu 
    a[i] = a[i] * 10
 
fin pour

qu'on pourrait aussi écrire comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
start = 0
pour j = 0 jusqu'à j = NCPU
 
    pour i = start jusqu'à i = (start+NCPU)
 
      affecter CPU à j 
      a[i] = a[i]*10
 
   fin pour
 
   start = start + NCPU
 
fin pour

Dans cette boucle, chaque instruction a[i] va être affctée à un CPU, jusqu'à concurrence des NCPUS. Puis on recommencera. Alors dans ce cas c'est peu important. Mais si le calcul signifié par "a[i] = ..." est lourd, on gagnera énormément (un facteur NCPU fois le temps normal)

Maintenant, ceic n'est vrai QUE pour des opérations indépendantes..

Si ma boucle initiale était :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
pour i = 1 jusqu'à i = N
 
    Faire a[i] = a[i] * 10 + a[i-1]
 
fin pour

cela devient impossible de parallèliser car chaque itération dépend de la précédente.. Là on a un algorithme purement séquentiel, qu'on ne peut pas parallèliser..

Donc un algorithme parallèlle ou parallèlisable est composé de sections/instructuons INDEPENDANTES les unes des autres. Cela peut être des sections entières de code, ou des instructions particulières..

En écriture, peu importe qu'on l'écrive comme une simple boucle ou une double (ou plus).. L'important c'est qu'il n'y ait pas de dépendances.. Evidemment l'écriture du PROGRAMME devra tenir compte de la double boucle.. L'écriture de l'ALGORITHME est indépendante.