Journal Exécution concurrente vs parallèle

Posté par . Licence CC by-sa.
Tags : aucun
13
28
nov.
2018

Chères lectrices,

tl;dr L'exécution concurrente c'est quand deux tâches sont exécutées logiquement en même temps et l'exécution parallèle est un cas particulier d'exécution concurrente où les tâches sont exécutées physiquement en même temps.

Ces derniers jours je suis tombé sur des tweets m'expliquant que parallélisme et concurrences étaient deux choses bien différentes et me proposait de m'expliquer cette différence par ce genre de schéma et je n'ai rien compris

Concurrency vs Parallelism

En effet, les deux exemples sont des traitements concurrents. Ce n'est pas très clair sur le dessin. J'etais tout confus. Et il y a plein de variations de ce même schéma sur internet.

De plus j'ai vu passer la question à une interview aujourd'hui.

Alors je me suis dit, cette fois c'est décidé je check la définition sur wikipédia:

Concurrent computing is a form of computing in which several computations are executed during overlapping time periods—concurrently—instead of sequentially (one completing before the next starts)

Traduction: L'exécution concurrente est une forme d'exécution dans laquelle plusieurs calculs sont exécutés au cours de périodes de temps se chevauchant au lieu d'une exécution séquentielle.

Pendant que pour l'exécution parallèle on a:

In parallel computing, execution occurs at the same physical instant: for example, on separate processors of a multi-processor machine, with the goal of speeding up computations—parallel computing is impossible on a (one-core) single processor, as only one computation can occur at any instant (during any single clock cycle).

Traduction: En calcul parallèle, l'exécution se déroule au cours du même instant physique.

Et voilà: l'exécution parallèle est juste un cas particulier d'exécution concurrente.

  • # Un petit dessin vaut mieux qu'un long discours ...

    Posté par . Évalué à 10.

    … mais ce dessin est particulièrement propice à la malcomprenance. Il est notoire que si il y a une gamelle pleine de croquettes et quatre chats, ils se répartissent en cercle autour de la gamelle et s'empiffrent simultanément (parallélisme). Si tu prévois une gamelle par chat, dès que tu verses quelques croquettes dans la première gamelle, ils accourent pour être les premiers servis (concurrence).

    Pour être plus sérieux (quoique), si tu as un processeur qui contient 4 cœurs, et que tu vois 4 process qui tournent, si les 4 process tournent sur le même cœur (par tranche de 100µs par exemple), c'est concurrent, si il tournent chacun sur un cœur différent, c'est du parallélisme.

    Ensuite, si le parallélisme à "plus grande échelle" t'intéresse (on appelle ça "HPC" de nos jours), sache c'est une discipline à part entière car les architectures utilisées sont assez spécifiques, les algorithmes employés ont des noms bizarres, il faut souvent des outils dédiés ou bien être créatif.

    • [^] # Re: Un petit dessin vaut mieux qu'un long discours ...

      Posté par . Évalué à 2.

      Ensuite, si le parallélisme à "plus grande échelle" t'intéresse (on appelle ça "HPC" de nos jours), sache c'est une discipline à part entière car les architectures utilisées sont assez spécifiques.

      Non pas forcément ça peut être de simples serveurs voire des postes de travail. Tu peux faire des architectures très hétérogènes, voire sur des pc classiques et même raspberry Pi.

      Tu peux réaliser un cluster de calcul sous linux

      sinon Blender fait par exemple du rendu réseau en parallèle sur plusieurs machine.

      Des projets comme seti@home l'on fait

      • [^] # Re: Un petit dessin vaut mieux qu'un long discours ...

        Posté par . Évalué à 1.

        Soit, mais c'est pas tout à fait le même "parallélisme" à mon goût. De même, 2 raspberrys derrière une freebox, ça ne fait pas du cloud pour moi. Je pense que je deviens vieux.

        • [^] # Re: Un petit dessin vaut mieux qu'un long discours ...

          Posté par . Évalué à 1. Dernière modification le 29/11/18 à 08:13.

          Le parallélisme et les calculateurs distribué sont des concepts différents du cloud.
          Les clusters de calculateur existent depuis très longtemps sous Linux depuis la fin des années 1990.

          Le cloud est à mon avis qu'un concept marketing reprenant le concept de mainframe, certe en utilisant des couches d'abstraction mais ça c'est une autre discution.

          Et en informatique, le parallélismes est maintenant présent partout et surtout permet l'augmentation des performances là où on se heurte aux limites physiques des technologie.

          • [^] # Re: Un petit dessin vaut mieux qu'un long discours ...

            Posté par . Évalué à 1.

            Pour en savoir un peu plus sur le "cloud", il suffit de lire les journaux 1 et 2.

            Sinon je suis un peu au courant pour le projet Seti@Home ou les initiatives comme BOINC ou Folding@home, c'est très intéressant et très utile, mais encore une fois, ce n'est tout à fait le même sujet.

            Quant "aux clusters de calcul sous linux depuis les années 90", je ne dis pas le contraire :)

            Si tu avais monté chez toi un joli cluster de 8 nœuds fin 90 (exemple tout à fait fortuit), tu
            avais du te rendre compte que pour de nombreux algos, ça coinçait au niveau du réseau …

            De nos jours, on va aussi parler d'efficacité énergétique comme l'oncle bob.
            C'est pas le tout de pouvoir fournir de la puissance de calcul, encore faut il rester "frugal".
            Le tableau du top500 a une colonne qui indique la puissance nécessaire "Power".
            C'est toujours instructif de benchmarker son petit cluster avec ces grosses installations.

      • [^] # Re: Un petit dessin vaut mieux qu'un long discours ...

        Posté par . Évalué à 1.

        Attention, dans ce cas c'est du HTC, et non du HPC, le HPC nécessite des infrastructures spécifiques, chaque coeur de calcul devant pouvoir accéder à toute la mémoire.

        • [^] # Re: Un petit dessin vaut mieux qu'un long discours ...

          Posté par (page perso) . Évalué à 2.

          NUMA, avec un réseau d'interco, qui peut être du simple gigabit, ça reste du HPC…

          C'est pas aussi "performant" qu'un SMP, mais ça fait le taf.

          • [^] # Re: Un petit dessin vaut mieux qu'un long discours ...

            Posté par (page perso) . Évalué à 3.

            De simples machines mono-processeur modernes peuvent être vues comme du NUMA par le système : c'est le cas des derniers processeurs AMD – au moins EPYC et Threadripper, je n'en suis pas certain pour Ryzen. C'est dû à l'architecture interne de la puce (plusieurs contrôleurs mémoire), qui implique réellement des accès mémoires non uniformes (NUMA donc).

            La connaissance libre : https://zestedesavoir.com

  • # Je ne suis pas certain de ta conclusion

    Posté par . Évalué à 5. Dernière modification le 28/11/18 à 23:52.

    L'exécution concurrente c'est quand une file d'instructions se partage une ressource unique par exemple un processeur avec une seul unité de calcul entier ( c'est un exemple théorique).

    L’exécution parallèle c'est quand plusieurs instructions peuvent être exécutées simultanément. Par exemple on peut avoir une file d'instructions et les instructions s'exécutent sur plusieurs unités de calcul.

    Dans un calculateur ce phénomène peut être présent à plusieurs niveaux.

    Pour résumé quand on ne peut pas faire de parallélisme on fait du concurrentiel.

    l'un est l'opposé de l'autre

    • [^] # Re: Je ne suis pas certain de ta conclusion

      Posté par . Évalué à 3.

      Pour revenir à l'image des chats :
      - les deux chats se chipent la gamelle en permanence (qui n'a jamais vu ça?): concurrence
      - les deux chats ont chacun une gamelle : parallélisme

      J'ai bon ?

      • [^] # Re: Je ne suis pas certain de ta conclusion

        Posté par . Évalué à 1.

        oui ç'est tout à fait ça :D

      • [^] # Re: Je ne suis pas certain de ta conclusion

        Posté par (page perso) . Évalué à 4. Dernière modification le 29/11/18 à 08:58.

        non ils se battent et le vainqueur mange les deux gamelles, ok je sors ->[]

        Autrement pour rester sérieux, et l'hyperthreading, c'est quoi concurrent ou parallèle ?

        • [^] # Re: Je ne suis pas certain de ta conclusion

          Posté par . Évalué à 10.

          Autrement pour rester sérieux, et l'hyperthreading, c'est quoi concurrent ou parallèle ?

          L’hyperthreading c’est du BTP… le but est de boucher les trous. Pour rester sur l’analogie des gamelles de chats, c’est quand un chat mange, il lève la tête le temps de mâcher, ça permet à un autre de mettre sa tête dans la gamelle, quand il lèvera la tête à son tour, le premier à fini de mâcher, donc il remet la tête dans la gamelle.

          On maximise ainsi le temps d’utilisation de la gamelle.

        • [^] # Re: Je ne suis pas certain de ta conclusion

          Posté par (page perso) . Évalué à 10.

          Autrement pour rester sérieux, et l'hyperthreading, c'est quoi concurrent ou parallèle ?
          

          C'est du calcul hongrois. Hongrois qu'on fait du parallèle, alors qu'en vrai, c'est concurrent.

    • [^] # Re: Je ne suis pas certain de ta conclusion

      Posté par . Évalué à 2.

      Je crois que le rédacteur du journal tenait juste à montrer sa confusion quant au fait qu'il trouve des définitions différentes en fonction des sources.

      Ta définition (qui correspond à celle illustrée par des chats) n'est pas celle qu'on voit partout (notamment, celle de Wikipedia est plus générale).

      Maintenant, laquelle est-elle la plus courante ?

      • [^] # Re: Je ne suis pas certain de ta conclusion

        Posté par . Évalué à 2.

        Ta définition (qui correspond à celle illustrée par des chats) n'est pas celle qu'on voit partout (notamment, celle de Wikipedia est plus générale).

        Merci de mettre un lien vers la définition que tu as trouvé sur Wikipédia.
        Et peux-tu développer ta remarque.

        Voici un complément à ma définition de la concurrence qui était valable déjà en économie par exemple dans la gestion des ressources dans une entreprise.

        J'ai volontairement réduit l'exemple au domaine informatique et si l'auteur était en pleine confusion sur le sujet un éclaircissement des concept ne fera de mal à personne. :D

        Le parallélisme et la concurrence sur des ressources quelles qu'elles soit sont un concept général.

        Si tu as trop peu de ressources , les utilisateurs doivent se les partager les ressources pour y accéder concurrence.

        Même des ressources parallèles peuvent être soumises à concurrence.
        Si tu as deux vélos et que 25 cyclistes tu pourras utiliser les vélo en parallèle mais il y a quand même concurrence car pas assez de ressource.

        Pour dans cet exemple supprimer la concurrence, il faut autant de vélos que de cyclistes.

        Imaginer un compromis acceptable entre concurrence (temps d'attente) et ressources à mettre en œuvre c'est le problème qu'on essaye de résoudre en générale en créant un architecture informatique.

        • [^] # Re: Je ne suis pas certain de ta conclusion

          Posté par . Évalué à 3.

          La définition de Wikipedia à laquelle je faisais allusion est celle citée dans le journal. Voilà la raison pour laquelle je n'ai pas mis de lien.

          En gros, selon cette définition, et celle que l'auteur du journal avait en tête :
          - concurrence : le fait que deux traitements puissent s'exécuter non-séquentiellement ("en même temps" : que ce soit par entrelacement sur une ressource partagée, ou bien en réelle simultanéité)
          - parallélisme : le fait que la concurrence se matérialise par des exécutions réellement simultanées (ce qui implique matériellement séparées).

          Je pense que ta définition (bien que courante et admissible) est biaisée par le Français, où concurrence prend aussi un autre sens (compétition, rivalité, etc… ).

          En anglais, la concurrence des marchés se dit "competition" et non concurrency. Ce biais n'existe donc pas.

      • [^] # Re: Je ne suis pas certain de ta conclusion

        Posté par . Évalué à 1. Dernière modification le 29/11/18 à 08:50.

        Je n'avais pas vu le lien vers wikipédia dans le journal de départ :
        cet article parle avant tout de programmation concurrentielle donc surtout de l'organisation que l'on peut mettre en place pour gérer du multitâche multithread et des languages qui le supportent.

        ce qui n'invalide pas la définition de concurrence et de parallelisme.

        • [^] # Re: Je ne suis pas certain de ta conclusion

          Posté par . Évalué à 3.

          Je n'avais pas vu ta deuxième réponse non plus avant de répondre à la première. Au temps pour moi.

          Du coup, une question. Si concurrence désigne seulement les situations de calculs non-séquentiels avec compétition pour l'accès aux ressources, comment appellerait-t-on la situation qui regroupe à la fois concurrence et parallélisme ?

          • [^] # Re: Je ne suis pas certain de ta conclusion

            Posté par . Évalué à 1. Dernière modification le 29/11/18 à 19:14.

            Les deux situations dépendent du nombre de ressources :

            si tu as assez de ressource par exemple un cycliste et un vélo ( toujours en théorie) tu n'as ni concurrence, ni parallélisme.

            Si un autre cycliste arrive à pied, il y a concurrence en français pour le velos

            on ajoute une bicyclette et on a du parallélisme seulement

            Si un autre cycliste arrive nous avons parallélisme et concurrence en simultanément.

            Je crois que ça s'appelle une situation de manque de ressources.

            Il faut juste noté que les cyclistes ici sont indépendants et vont dans des directions différentes

            :P

    • [^] # Re: Je ne suis pas certain de ta conclusion

      Posté par . Évalué à 2. Dernière modification le 30/11/18 à 07:34.

      Pour résumé quand on ne peut pas faire de parallélisme on fait du concurrentiel.

      l'un est l'opposé de l'autre

      Tu as choisi des définitions différentes de celles de wikipédia citées dans mon journal.

      Qui d'autre utilise cette définition plus restreinte de la concurrence?

      Si je lis un article, ou que j'utilise une bibliothèque sur la programmation concurrente, je m'attend à entendre parler d'exécution parallèle aussi.

  • # Concurrence libre et non faussée

    Posté par (page perso) . Évalué à 8.

    Si j'ai bien compris en situation de concurrence, un seul chat (qui n'est pas dans les files d'attente) devient gros.

    Incubez l'excellence sur https://linuxfr.org/board/

  • # Une explication à mon avis plus claire...

    Posté par (page perso) . Évalué à 5.

    • [^] # Re: Une explication à mon avis plus claire...

      Posté par . Évalué à 2.

      Ben du coup sa présentation est en contradiction avec ce qui est présenté dans ce journal.

      Ici, quand on parle de concurrence, on parle de ressources qu'il faut se partager (la gamelle), et pour ça organiser les différents "consommateurs" (les chats) pour que ça se passe au mieux.

      Dans sa définition, la présence de ressources à partager est totalement absente. C'est juste "programmer une composition de processus qui s'exécutent indépendamment les uns des autres" :

      Concurrency: Programming as the composition of independently executing processes.

      Il insiste sur cette indépendance en plus, en faisant une des différences notables avec le parallélisme.

      Je sais pas qui a tort, qui a raison, mais clairement c'est pas clair. On a une gamelle ou pas ? Ils bouffent comment les chats ?

      • [^] # Re: Une explication à mon avis plus claire...

        Posté par . Évalué à 4. Dernière modification le 29/11/18 à 11:36.

        En informatique théorique, la relation de concurrence désigne souvent la simple absence de causalité entre deux évènements d'une exécution donnée.

        Maintenant, c'est une définition parmi tant d'autres…

      • [^] # Re: Une explication à mon avis plus claire...

        Posté par . Évalué à 1. Dernière modification le 29/11/18 à 17:13.

        D'après ce que j'en comprend, le parallélisme est une forme triviale de concurrence où la même opération est appliquée séparément (et simultanément?) à des données différentes.

        • [^] # Re: Une explication à mon avis plus claire...

          Posté par . Évalué à 1. Dernière modification le 29/11/18 à 17:34.

          Ce n'est pas forcément la même opération …

          Quand on utilise un terme, il y a une notion de "contexte". Le journal de départ est assez
          généraliste, mais plusieurs commentaires ont dérivé sur des sujets connexes (grid, architecture
          des processeurs, etc.) et dans ce thread, dans le cadre de développement en "go".

      • [^] # Re: Une explication à mon avis plus claire...

        Posté par . Évalué à 2. Dernière modification le 29/11/18 à 23:44.

        Dans sa définition, la présence de ressources à partager est totalement absente. C'est juste "programmer une composition de processus qui s'exécutent indépendamment les uns des autres" :

        Concurrency: Programming as the composition of independently executing processes.

        Pour le coup ça resssemble à la définition de wikipedia que j'ai utilisée pour tirer ma conclusion.

        Le titre, notamment ne contredis pas ma conclusion: concurrency is not parallelism -> ok, puisque il existe des exécutions concurrentes qui ne sont pas parallèles (quand l'exécution à lieu sur le même coeur). Le parallélisme est un sous ensemble de concurrence.

        Mais je trouve wikipedia beaucoup plus clair que Rob.

        Après comme le dis Aldoo il doit y avoir plusieurs définitions.

        Je ferai attentation de ne pas être trop péremptoire quand j'explique ma conclusion. Mais finalement, j'ai vu des définitions alternative dans les commentaires mais je n'ai aucune idée de qui utilise ces définitions. Si des articles classiques l'utilisent, ou uniquement des articles récents ou alors une définition pourrait être utilisés seulement par des électroniciens…

  • # Parallélisme vs. Concurrence : même machine, différent point de vue !

    Posté par . Évalué à 3.

    Tout à fait d'accord sur le fait que la programmation parallèle est un sous-ensemble (important !) de la programmation concurrente. Après, comme d'autres l'ont fait remarquer, il existe plusieurs sortes de parallélisme. En calcul scientifique, on utilise souvent le parallélisme de données – c'est l'exemple qu'avait donné quelqu'un ici à propos des chats qui mangeraient dans la même gamelle. Un autre type de parallélisme est celui des tâches : c'est ce qu'on fait, par exemple, lorsqu'on repasse une chemise tout en écoutant la télé/radio, et possiblement en parlant avec quelqu'un. Enfin, il y a le parallélisme de pipeline, qui « chaîne » différentes tâches pour qu'elles traitent un bout de donnée successivement. Évidemment, on va fournir un autre bout de donnée à la première tâche dès qu'elle aura passé son bout de donnée traité à la suivante, etc. On peut imaginer une chaîne de montage façon « Les temps modernes », par exemple. Évidemment, on peut mélanger les trois (sinon ce ne serait pas drôle !).

    Lors d'une conférence il y a longtemps, le keynote speaker avait proposé une illustration de la différence entre programmation parallèle et programmation concurrente en pratique :

    En voyant une nouvelle machine de type supercalculateur, data center, etc., le programmeur parallèle s'extasie et s'écrire : « Ouahou, quelle puissance potentielle ! On va pouvoir faire des choses formidables avec ça ! »

    En voyant la même machine, le programmeur concurrent prend une expression horrifiée, et se lamente : « Regardez toutes les possibilités de panne dans cette machine ! »

    Un bon exemple de la différence de point de vue est dans l'utilisation d'une bibliothèque de communication et calcul très utilisée en calcul intensif/haute-performance : MPI. Les utilisateurs de MPI le font généralement sur une machine avec réseau d'interconnexion dédié (pas de TCP, trop lourd; pas d'Ethernet, trop lent – au moins niveau latences). Ils se posent des questions compliquées liées à la topologie sur le réseau, combien de sauts il faudra peut-être faire en regardant les machines utilisées, etc.1 Au contraire, les programmeurs de la bibliothèque MPI locale doivent tenir compte de toutes les possibilités de panne temporaire ou permanente (les appels MPI de base sont bloquants, et attendent des acquittements de bonne réception/terminaison d'envoi de données; même la version asynchrone de ces appels fait de même, peu ou prou). Ils doivent composer avec les possibilités de congestion sur le réseau, et pour les versions les plus sophistiquées, prennent en compte tout un tas de possibilités de pannes transitoires ou temporaires.2

    Le programmeur parallèle d'une grappe de calcul essaie de trouver des algorithmes et des implémentations qui iront vite pour une application donnée, en considérant que tout ira bien, c'est-à-dire, en faisant abstraction quasi-complètement de la couche réseau (et en-dessous). Le programmeur concurrent va devoir considérer que les latences d'envoi/réception peuvent varier, et même imaginer quel genre de panne peut survenir, et s'il veut y remédier.


    1. Du moins, ceux qui en sont à l'optimisation de leur programme le font; les autres (la majorité) exploitent une machine à 1% max de la capacité crête…  

    2. Il existe des versions (de recherche) qui font même de la tolérance aux pannes (je n'ai pas entendu parler de version de production dans ce cas). La plupart des versions utilisées se contentent de planter si jamais un timeout s'est écoulé cependant… 

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.