Parallélisation inefficace
Fermé
gti94
Messages postés
4
Date d'inscription
dimanche 15 juin 2014
Statut
Membre
Dernière intervention
15 juin 2014
-
Modifié par gti94 le 15/06/2014 à 16:22
gti94 Messages postés 4 Date d'inscription dimanche 15 juin 2014 Statut Membre Dernière intervention 15 juin 2014 - 15 juin 2014 à 19:04
gti94 Messages postés 4 Date d'inscription dimanche 15 juin 2014 Statut Membre Dernière intervention 15 juin 2014 - 15 juin 2014 à 19:04
2 réponses
KX
Messages postés
16733
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 janvier 2024
3 015
15 juin 2014 à 16:52
15 juin 2014 à 16:52
Bonjour,
Si je comprends bien tu cherches un exemple d'algorithme qui serait moins rapide en parallèle qu'en séquentiel ?
Pour un problème donné, le meilleur algorithme en parallèle aura toujours une complexité supérieure au meilleur algorithme conçu pour un seul thread (c'est un raisonnement par l'absurde, si ce n'était pas le cas ça voudrait que l'algorithme en parallèle serait meilleur que celui que l'on postule comme étant déjà le meilleur).
Ce qui fait la force d'un algorithme en parallèle ce n'est donc pas sa complexité, le nombre de calculs total qu'il va effectuer, mais sa rapidité puisque les calculs seront partagés sur plusieurs threads.
Si tu veux un exemple d'algorithme parallèle plus long qu'un algorithme séquentiel, je pense que la seule manière d'y arriver c'est de prendre un nombre de machine en parallèle égal à 1... puisque dans ce cas ton algorithme séquentiel sera plus rapide.
Remarque : "une approximation de racine(5) par dichotomie" ça n'a pas l'air super compliqué ! Tu peux regarder cette discussion : La fonction factorielle: Fact(N) = N!, c'est un exemple qui sera peut-être un peu plus intéressant...
Si je comprends bien tu cherches un exemple d'algorithme qui serait moins rapide en parallèle qu'en séquentiel ?
Pour un problème donné, le meilleur algorithme en parallèle aura toujours une complexité supérieure au meilleur algorithme conçu pour un seul thread (c'est un raisonnement par l'absurde, si ce n'était pas le cas ça voudrait que l'algorithme en parallèle serait meilleur que celui que l'on postule comme étant déjà le meilleur).
Ce qui fait la force d'un algorithme en parallèle ce n'est donc pas sa complexité, le nombre de calculs total qu'il va effectuer, mais sa rapidité puisque les calculs seront partagés sur plusieurs threads.
Si tu veux un exemple d'algorithme parallèle plus long qu'un algorithme séquentiel, je pense que la seule manière d'y arriver c'est de prendre un nombre de machine en parallèle égal à 1... puisque dans ce cas ton algorithme séquentiel sera plus rapide.
Remarque : "une approximation de racine(5) par dichotomie" ça n'a pas l'air super compliqué ! Tu peux regarder cette discussion : La fonction factorielle: Fact(N) = N!, c'est un exemple qui sera peut-être un peu plus intéressant...
gti94
Messages postés
4
Date d'inscription
dimanche 15 juin 2014
Statut
Membre
Dernière intervention
15 juin 2014
15 juin 2014 à 17:17
15 juin 2014 à 17:17
Merci de ta réponse :)
L'idée de la dichotomie, c'est que chaque itération a besoin du résultat de la précédente pour être effectuée, ainsi la mise en parallèle n'apporte rien, si ce n'est un coût supplémentaire du à elle-même. Seulement je n'ai pas réussi à la faire tourner plus d'une demi seconde...
Pour ce qui est de faire tourner un programme en parallèle avec un seul thread, ce n'est pas vraiment ce que je cherche...
En fait il s'agit de montrer que le parallélisme a ses "limites", et que certains algorithmes ne peuvent pas (ou plutôt ne doivent pas) être parallélisés. Donc il faudrait un programme (modeste) qui tourne plus vite, ou aussi vite, en version séquentielle que parallèle (vraiment en parallèle, avec plusieurs coeurs ;) )...
L'idée de la dichotomie, c'est que chaque itération a besoin du résultat de la précédente pour être effectuée, ainsi la mise en parallèle n'apporte rien, si ce n'est un coût supplémentaire du à elle-même. Seulement je n'ai pas réussi à la faire tourner plus d'une demi seconde...
Pour ce qui est de faire tourner un programme en parallèle avec un seul thread, ce n'est pas vraiment ce que je cherche...
En fait il s'agit de montrer que le parallélisme a ses "limites", et que certains algorithmes ne peuvent pas (ou plutôt ne doivent pas) être parallélisés. Donc il faudrait un programme (modeste) qui tourne plus vite, ou aussi vite, en version séquentielle que parallèle (vraiment en parallèle, avec plusieurs coeurs ;) )...
KX
Messages postés
16733
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 janvier 2024
3 015
15 juin 2014 à 17:57
15 juin 2014 à 17:57
"L'idée de la dichotomie, c'est que chaque itération a besoin du résultat de la précédente pour être effectuée, ainsi la mise en parallèle n'apporte rien"
Je ne suis pas d'accord. La dichotomie c'est tout le contraire, c'est le découpage du problème en deux branches indépendantes qui peuvent être calculées séparément sur deux machines différentes, donc la mise en parallèle est tout à fait pertinente !
En fait la parallélisation est toujours pertinente, si tu cherches des limites c'est soit avec un seul processeur, soit en explosant la quantité de messages inter-processeurs, puisque que c'est ce qui génère le plus de latences vu que les communications entre deux ordinateurs sont nettement moins rapides que les communications au sein d'un même processeur, donc s'il y a plus de communications que de calculs, le temps global sera plus long.
Mais là ce serait une mauvaise gestion de ton programme parallèle. S'il est bien géré, un programme en parallèle sera toujours plus judicieux qu'un programme en séquentiel...
Je ne suis pas d'accord. La dichotomie c'est tout le contraire, c'est le découpage du problème en deux branches indépendantes qui peuvent être calculées séparément sur deux machines différentes, donc la mise en parallèle est tout à fait pertinente !
En fait la parallélisation est toujours pertinente, si tu cherches des limites c'est soit avec un seul processeur, soit en explosant la quantité de messages inter-processeurs, puisque que c'est ce qui génère le plus de latences vu que les communications entre deux ordinateurs sont nettement moins rapides que les communications au sein d'un même processeur, donc s'il y a plus de communications que de calculs, le temps global sera plus long.
Mais là ce serait une mauvaise gestion de ton programme parallèle. S'il est bien géré, un programme en parallèle sera toujours plus judicieux qu'un programme en séquentiel...
gti94
Messages postés
4
Date d'inscription
dimanche 15 juin 2014
Statut
Membre
Dernière intervention
15 juin 2014
15 juin 2014 à 18:06
15 juin 2014 à 18:06
Pour la dichotomie: On part de l'intervalle [2;3]
Première itération : On regarde le signe de (2.5² - 5), c'est positif
Donc racine(5) est entre 2 et 2.5
Deuxième itération: On regarde (2.25² - 5), c'est négatif
Donc racine(5) est entre 2.25 et 2.5
etc...
Désolé s'il y a quelque chose d'évident qui ne me saute pas aux yeux, mais je ne vois pas comment paralléliser ça de façon intelligente;
si je fais traiter la première itération par le thread 1 et la deuxième par le thread 2, il faudra que le 2 attende que le 1 ait déterminé le bon intervalle ([2, 2.5] ou [2.5, 3]), et donc on perd tout l'intérêt de partager les tâches...
Désolé si je prends cet exemple bête, mais au vu de ton message j'ai l'impression que quelque chose m'échappe et j'aimerai vraiment comprendre ^^
Première itération : On regarde le signe de (2.5² - 5), c'est positif
Donc racine(5) est entre 2 et 2.5
Deuxième itération: On regarde (2.25² - 5), c'est négatif
Donc racine(5) est entre 2.25 et 2.5
etc...
Désolé s'il y a quelque chose d'évident qui ne me saute pas aux yeux, mais je ne vois pas comment paralléliser ça de façon intelligente;
si je fais traiter la première itération par le thread 1 et la deuxième par le thread 2, il faudra que le 2 attende que le 1 ait déterminé le bon intervalle ([2, 2.5] ou [2.5, 3]), et donc on perd tout l'intérêt de partager les tâches...
Désolé si je prends cet exemple bête, mais au vu de ton message j'ai l'impression que quelque chose m'échappe et j'aimerai vraiment comprendre ^^
KX
Messages postés
16733
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 janvier 2024
3 015
15 juin 2014 à 18:57
15 juin 2014 à 18:57
Pour un problème donné, trouver un algorithme parallèle ce n'est pas juste prendre l'algorithme séquentiel et le paralléliser, c'est vraiment trouver un nouvel algorithme.
Là tu es partie sur la méthode de Héron (méthode de Newton) qui est sûrement l'un des meilleurs algorithmes en séquentiel, mais la dichotomie dont tu parles n'est utilisé qu'à moitié.
Une fois que tu as pris la moitié de l'intervalle tu n'en gardes qu'une partie, alors que pour paralléliser il faudrait avoir un algorithme où tu calcules les deux sous-parties, chacune sur une machine différente.
Alors comme ça je n'ai pas d'algorithme qui me vient en tête pour le calcul de racine de 5 en parallèle, mais dès lors que tu en auras un, il sera forcément meilleur que ton algorithme séquentiel.
Là tu es partie sur la méthode de Héron (méthode de Newton) qui est sûrement l'un des meilleurs algorithmes en séquentiel, mais la dichotomie dont tu parles n'est utilisé qu'à moitié.
Une fois que tu as pris la moitié de l'intervalle tu n'en gardes qu'une partie, alors que pour paralléliser il faudrait avoir un algorithme où tu calcules les deux sous-parties, chacune sur une machine différente.
Alors comme ça je n'ai pas d'algorithme qui me vient en tête pour le calcul de racine de 5 en parallèle, mais dès lors que tu en auras un, il sera forcément meilleur que ton algorithme séquentiel.
gti94
Messages postés
4
Date d'inscription
dimanche 15 juin 2014
Statut
Membre
Dernière intervention
15 juin 2014
15 juin 2014 à 19:04
15 juin 2014 à 19:04
Ah je comprends, on est d'accord ! Tu parlais de résoudre un problème, je parle de paralléliser un algorithme, et non pas de trouver comment résoudre le problème de la meilleure façon possible grâce à un algorithme parallèle.
Bon merci de ton aide en tout cas :)
Bon merci de ton aide en tout cas :)
