Get best of the week

NPS, convoyeur, calcul automatique et encore ... coroutines

1. Encore une fois sur les coroutines


Dans mon précédent article, cher Habr, je n'ai abordé que les problèmes de connaissance de la programmation moderne. La discussion qui a suivi n'a fait que confirmer les craintes spontanées qui ont surgi: les fameux «fondements théoriques» sont immédiatement devenus une source de désaccord. Le fait qu'ils (désaccords) n'existent pas ou qu'ils soient de nature différente ne semble pas déranger la majeure partie des "vrais" programmeurs. De plus, ce n'est peut-être pas particulièrement intéressant, car les programmeurs sont principalement stimulés par un seul intérêt - le code, le code et le seul code. Eh bien, presque "comme le médecin l'a prescrit" [1] ...

Evoquant le sujet de la corutine dans mon article et mes commentaires, je n'ai pas du tout rêvé de leur place dans la tendance «actuelle». Étonné, cependant, des "pistes d'accompagnement" de mes commentaires avec ou sans. Pour quoi, disent-ils, les programmeurs? Cependant, il me semble que tout est devenu clair après avoir lu l'article sur le C ++ 20 nouvellement approuvé et les perspectives de son développement ultérieur [2]. À ma grande surprise, il s'est avéré que les coroutines sont à l'avant-garde des innovations présentes et futures de mon bien-aimé C ++ (voir aussi la bibliothèque CppCoro ).

Eh bien, dites-moi, est-il possible de prendre au sérieux et / ou calmement un front qui, semble-t-il, s'imagine être n'importe qui? Frappez ce qu'on appelle! :(

Le fond de ma connaissance des coroutines (je les appellerai tout de même à l'ancienne) est le suivant. Il fallait paralléliser, mais quelque chose de convenable ne l'était pas. J'ai dû inventer, étudier la littérature disponible. En conséquence, les coroutines ont été rejetées immédiatement et les discussions plus tard. La raison en est que les deux sont des méthodes structurelles de parallélisation des programmes, et non des modèles de calcul. Mais je ne voulais pas ça.

La description de ce à quoi je suis finalement arrivé est donnée dans mes précédents articles sur Habré. Cette conversation est loin d'être terminée, mais pour l'instant, comment se souvient-on des coroutines, puisqu'elles sont déjà devenues le sujet d'une discussion aussi animée? La seule chose est les «points» des processus d'arrêt / de commutation. Contrairement aux threads, ils ont permis de prédire le comportement de processus simulant un fonctionnement parallèle. En théorie, cela a également réduit les pertes de système pour la mise en œuvre du parallélisme. Mais, néanmoins, en somme, tout cela fondamentalement n'a pas changé. Et comme les «points» étaient simplement imités par les états du modèle de programmation d'automate (AP), ma connaissance des coroutines était terminée pour sept.

Mais je ne pouvais pas supposer que l'incarnation des coroutines, maintenant appelées coroutines, m'atteindrait ainsi. De cela, et le mien, peut-être des «attaques» injustifiées contre eux, pour lesquelles je présente mes excuses les plus sincères aux apologistes de Corutin. Probablement pressé. Néanmoins, les circonstances récemment découvertes n'ont pas affecté mon attitude envers les coroutines. Pour le nouveau code, pour raisonner en leur faveur, je n'ai jamais rien vu de fondamentalement nouveau. Cependant, je tiens à noter que les coroutines sont néanmoins plus proches et plus claires pour moi que les threads, car contient, comme je l'ai dit plus haut, un analogue de l'ensemble des états internes des automates finis (CA).

Cependant, arrêtez de vous repentir. Revenons à des automates qui couvrent complètement le «thème coroutine». Ensuite, je présenterai les capacités de l'AP associées à la modélisation de modèles parallèles qui sont assez bien connus en théorie et en pratique - des modèles d'algorithmes parallèles et en pipeline. À mon avis, leur solution automatique semble plus visuelle, naturelle et simple qu'elle ne serait basée sur les mêmes coroutines.

2. Formes d'algorithmes en parallèle et en pipeline


Supposons que vous devez calculer l'expression:

y = (((a + b) * (c + d)) + ((e * f) + (q + h))).

Aussi, laissez le temps d'exécution de l'opération être défini, défini en unités arbitraires de temps discret - mesures où l'addition prend 1 mesure et la multiplication prend 5 mesures.
Sur la base de la logique de calcul de l'expression, du temps d'exécution des opérations et du nombre de variables intermédiaires, dans un mode de réalisation, la distribution des opérations par niveaux et le nombre de niveaux lui-même peuvent ressembler, par exemple, comme suit:

t1 = a + b; t2 = c + d; t3 = e * f; t4 = q + h;
Tier0: t1; t2; t3; t4;
Niveau 1: t5 = t1 * t2; t6 = t3 + t4;
Niveau 2: t7 = t5 + t6;

Graphiquement, cela est illustré à la fig. 1, qui montre deux options pour la distribution des calculs en niveaux et le temps de calcul fixé en ticks. Leur comparaison montre que dans le cas général, une diminution du nombre de niveaux ne signifie pas automatiquement une réduction du temps de calcul.

image
Figure. 1. Forme parallèle à

plusieurs niveaux de calcul d'une expression, mais une autre option peut être envisagée, qui est déjà représentée par une multitude de formes parallèles à plusieurs niveaux qui résolvent un seul problème. En figue. La figure 2 montre une telle solution. Le temps de calcul a diminué. La parallélisation des NPS peut également être intéressante compte tenu de leur exécution sur des systèmes multiprocesseurs.

image
Figure. 2. NPS parallèle

Si vous faites pivoter le graphique JPF, vous pouvez obtenir le schéma de calcul de pipeline. Dans ce document, les éléments du convoyeur seront des niveaux, dont le temps de fonctionnement est réduit au niveau le plus lent. En figue. La figure 3 montre un tel schéma de pipeline de l'expression originale.

image
Figure. 3. Modèle de pipeline

Étant donné que pour cet exemple le temps de convoyeur discret est de 5 cycles d'horloge, le temps de calcul sera encore pire que la pire version du NPS. Avantages du pipeline uniquement dans la continuité des calculs.

3. Un modèle d'automate pour calculer les expressions


Si vous supprimez les restrictions sur la synchronisation des opérations, le NPS peut être transformé en un circuit qui générera le résultat sous forme de pipeline, mais sans restrictions associées à la séquence et à l'heure des opérations. Un tel schéma de réseau logique avec une démonstration de l'opération d'addition (la mise en œuvre de la multiplication est similaire) sous la forme d'un modèle de réseau de vaisseau spatial est représenté sur la Fig. 4.

image
Fig. 4. Calculs d'expressions basés sur un réseau de machines à états finis

Vous pouvez voir que le réseau produira constamment un résultat avec un retard de 7 cycles d'horloge, c'est-à-dire ainsi que le modèle NPS le plus rapide (Fig. 7). Ses inconvénients incluent l'instabilité de sortie associée aux courses de données. Par exemple, un changement simultané de la valeur des variables par paires de variables g, h et e, f entraînera un changement de t4 au cycle d'horloge suivant, après un cycle d'horloge pour un changement de variable t6 et un autre cycle d'horloge pour la variable de sortie t7 (voir Fig.1 et Fig.4) . Dans le même temps, après 5 cycles d'horloge, la variable t3 changera, ce qui entraînera une modification et la sortie des valeurs finalement établies des variables t6, t7.

image
Figure. 5. Modélisation de NPS avec un réseau d'automates

En figue. La figure 5 montre comment l'introduction d'un bloc supplémentaire permet de simuler le calcul de NPS. De même, vous pouvez simuler le modèle de calcul en pipeline, ainsi que bloquer le changement de sortie associé aux courses de données.

3. Conclusions


Il serait étrange de douter que les «images» ci-dessus ne puissent pas être réalisées à l'aide de coroutines. C'est juste, pour être honnête, je ne voudrais pas faire ça. Pour moi, il est beaucoup plus facile de créer des automates qui implémentent les opérations nécessaires, puis, en ne modifiant que leur nombre et les relations entre eux, implémentent le calcul de toute expression.

Je ne me lasserai pas de répéter que je suis attiré par le concept de programmation visuelle implémenté dans le package Stateflow de MATLAB. Ici, vous pouvez également créer les opérations d'automate nécessaires, puis, en les utilisant, comme des blocs standard, «dessiner» un schéma de calcul pour n'importe quelle expression, qui après la compilation se transformera en programme de travail (par exemple, dans le même C ++). Parallèlement, au cours du processus de conception, des outils de visualisation et de débogage seront disponibles, spécifiques à la technologie de programmation automatisée.

Certes, la question peut se poser - pourquoi des liens permanents avec un certain environnement inconnu du PCUS, s'il y a Stateflow? Mais nous en parlerons encore séparément ...

C'est une chose ingrate de faire des prédictions, mais néanmoins, sur la base de mon expérience, j'exprimerai une pensée séditieuse: en tant que langages de haut niveau utilisés pour nier la programmation en langage assembleur, donc la programmation visuelle tôt ou tard et non moins d'éviction de la programmation dans des langages de haut niveau.

Littérature

1. Programmeurs, étudions les sources des programmes classiques. [Ressource électronique], Mode d'accès: habr.com/en/post/488808 gratuit. Yaz. russe (date du traitement 22.02.2020).
2. Approuvé C ++ 20! À quoi s'attendre et quoi préparer pour les développeurs C ++ 23. [Ressource électronique], Mode d'accès:habr.com/en/company/yandex/blog/488588 gratuit. Yaz. russe (date du traitement 02.20.2020).

More articles:


All Articles