Le topic de la programmation: Et envoyez des sioux!

[Patate]

Et sinon ce dev et son code en mode "tout l'univers" en 5 tomes. Il a trouvé la solution??

[Møgluglu]

Merci pour la solution, je voulais éviter de rajouter des semaphores/mutex, mais bon, ça marche aussi

Le code avec des mutex revient en gros à implémenter à la main un sem_getvalue sur un second sémaphore.

Par curiosité, dans quel cas tu as besoin de récupérer la valeur de l'état "réveillé" sans synchroniser ? Et quand est-ce que tu remets à zéro la variable partagée ?

[Nilsou]

Le code avec des mutex revient en gros à implémenter à la main un sem_getvalue sur un second sémaphore.

Ben tu vois, c"est exactement ce que j'ai fait au final

[Nilsou]

Par curiosité, dans quel cas tu as besoin de récupérer la valeur de l'état "réveillé" sans synchroniser ? Et quand est-ce que tu remets à zéro la variable partagée ?

Bah en fait c'est dans le cadre d'un gestionnaire de réseaux de neurones (c'est mon taf en labo). Je "réveille" des groupes de neurone, en gros ça se passe ainsi :

Thread principal : séquenceur.
-> vérifie chez tout les groupes ceux qui ont vérifié leur conditions pour se lancer (souvent qu'un groupe précédent ai finit de taffer)
-> lance ceux qui peuvent se lancer
-> attends qu'au moins un groupe ai fini de bosser
-> rebelotes

Thread des groupes :
-> Attends d'être éveillée par le séquenceur.
-> s’exécute (fonctionnement, apprentissage, tout ça, dépends des groupes, ça appelle juste un pointeur de fonction)
-> signale sa fin d’exécution

Voila, le soucis c'était que le séquenceur peut se faire relancer par n'importe quel groupe ayant fini (tout les groupes sont en parallèle, et bien souvent sur des cœurs différents). Dans ce cas quand le séquenceur s’exécute la partie en gras devient critique. Il doit faire attention au fait que des groupes peuvent être en train de taffer. Ce qui n'est pas critique, mais il doit en être informé (par exemple si tout le programme à fini de faire un tour complet des groupes il est de bon tons d'attendre que ceux qui trainent ai finit à la fin avant de relancer le programme). Il doit aussi être informé des groupes qu'il a déjà éveillé pour ne pas réveiller une seconde fois.

Pour le moment la solution potable mais encore faillible c'était de faire ainsi :

Thread principal : séquenceur.
-> LOCK SEMAPHORE3
-> vérifie chez tout les groupes ceux qui ont vérifié leur conditions pour se lancer (souvent qu'un groupe précédent ai finit de taffer) en testant groupe.TEST et SEMAPHORE2
-> MET groupe.TEST à 0
-> lance ceux qui peuvent se lancer via SEMAPHORE1
-> attends qu'au moins un groupe ai fini de bosser via SEMAPHORE3
-> rebelotes

Thread des groupes (un par groupe):
-> Attends d'être éveillée par le séquenceur via SEMAPHORE1
INCRÉMENTE SEMAPHORE2
-> s’exécute (fonctionnement, apprentissage, tout ça, dépends des groupes, ça appelle juste un pointeur de fonction)
-> signale sa fin d’exécution en mettant TEST à 1
DÉCRÉMENTE SEMAPHORE2
INCRÉMENTE SEMAPHORE3

En gros ce qui est en bleu n'est pas utile ici dans notre problème. Sur le reste en gras et en rouge c'est un autre soucis ...
TEST permet de savoir si un groupe est fini d’exécuter ou dans un autre état (qui peut aller d'avant le top départ du séquenceur jusqu'a une instruction avant la fin notée par SEMAPHORE2)
SEMAPHORE2 permet de tester si on est dans un état éveillé (en cours de fonctionnement) du point de vue du groupe éveillé.

Par exemple si je suis en cours d’exécution sur le thread d'un groupe et que je cherche à tester si ce groupe est en fonctionnement ou a fini son taf, ben normalement ça passe, puisque soit il n'a pas fini, soit il a fini (TEST à 1) mais est toujours en cours d’exécution (à une instruction prêt vu que SEMAPHORE2 n'est pas décrémenté) soit il n'a pas fini et est en cours d’exécution, soit il a fini et n'est plus en cours d’exécution. Pour le test de la fin d'un groupe ça passe.

Pour le test du début par contre c'est une autre histoire. Il y a toujours une faille à ce niveau là. Puisque typiquement on a un enchainement, du point de vue su thread "groupe" : SEMAPHORE1 (signal de départ) --> verification semaphore valide --> SEMAPHORE2.
Il y a donc un intervalle chiant entre les deux qui peut être source d'erreur. Par exemple si le séquenceur est appelé deux fois très très rapidement. on pourrais avoir un thread "réveillé" mais non noté comme "en travail" par la SEMAPHORE2.
Les solutions que j'ai trouve ne sont malheureusement pas très propre. Soit j'utilise "TEST" avec une 3eme valeur (jamais lancé :-1 -> lancé : 0 -> fini : 1) mais par design c'est relou parce que j'ai des conditions sur cette variables dans des milliers de lignes du programmes un peu partout.
Soit j'implémente votre solution donc un sémaphores par groupe en plus.

En réalité je n'aurais pas vraiment de problème si je pouvais toucher à "Test", changer sa valeur de départ par exemple... alors que la en l’occurrence je compte sur semaphore2 qui n'est pas super fiable.


Faut bien comprendre que jusqu'ici ça marche en réalité parce qu'on bosse sur des neurones, alors si un groupes était appelé une fois de trop régulièrement ce n'était pas trop problématique. C'est le défaut de l'apprentissage, ça compense ce genre de défaut en compensant l'erreur de dynamique récurrente introduite, du coups difficile de le voir sauf à coups de printf et de comptage précis de ce qui a été exécuté.

Ha et PS: ce n'est pas moi qui ai conçu ça comme ça à l'origine

[William Vaurien]

Et sinon ce dev et son code en mode "tout l'univers" en 5 tomes. Il a trouvé la solution??

Oui, c'était 42.

En fait il a laissé son tas de feuilles en plan. Et il attend la retraite.

[Lazyjoe]

Oui, c'était 42.

En fait il a laissé son tas de feuilles en plan. Et il attend la retraite.

Ptêtre qu'il n'avait pas fini d'imprimer et attend une livrison de toner.

[Dross]

Et il attend la retraite.

Il a déjà choisi un héritier ?

[Raplonu]

Spoiler pour les programmeurs CUDA : les cooperative groups de CUDA 9, c'est super cool sur le papier, mais c'est pas encore tout à fait sec. Il va falloir attendre CUDA 10 pour en profiter.

Tu as un retour sur leurs utilisations ? Pour le moment, j'utilise une solution maison pour faire un boulot similaire (synchronisation d'un kernel, synchronisation multi GPU, etc.) compatible kepler.-Ce qui m’intéresse surtout c'est latence de ces mécanismes de synchro.

[Patate]

Oui, c'était 42.

En fait il a laissé son tas de feuilles en plan. Et il attend la retraite.

[William Vaurien]

Il a déjà choisi un héritier ?

je crois que ça va me tomber sur le coin de la gueule: équipe de 3 ( plus moi ) avec mon chef actuel qui est sur ce projet depuis 1992 et qui touche encore pas mal au code, mais qui ne va pas rester encore très longtemps, et l'autre dev qui est ambivalent: il répète à longueur de temps qu'il voudrait bien faire du dev un peu plus moderne (Java c'est moderne dans notre référentiel...) mais il ne se forme pas vraiment non plus et ne supporte aucune critique sur son code et le projet en C, pourtant complètement dépassé en terme de 'bonne pratiques'.

C'est à priori lui qui deviendra le pilier du projet dans quelques années... Je sais pas très bien dans quoi je me suis engagé


Petite question : vous utilisez quoi pour faire des diagrammes, genre schéma d'archi général pour faire de la documentation.

J'utilise le plugin 'officiel' de ma boite pour Confluence : Gliffy, mais je trouve que c'est une énorme bouse: ça rame, c'est par ergonomique, faire un petit schéma prend des heures, il n'y a pas de layout auto.
Et j'aime bien Yed que je trouve plutôt efficace au niveau du layout justement, mais qui est parfois un peu moche (il demande beaucoup de customisation pour avoir un look sympa), et un peu trop complexe pour certaines opérations simples.
Je voudrais faire des trucs de ce genre:

[rOut]

Perso je trouve que PlantUML c'est cool.

[William Vaurien]

Ah oui j'utilise aussi et j'adore pour faire des diagrammes de séquence. C'est un peu moche mais le fait de passer par tu texte est un gros plus.
Il y a en plus un très bon plugin pour Intellij qui permet de visualiser en temps réel ce que l'on écrit et de faire un peu de complétion auto.

Là je dois représenter les interactions de différents scripts shell et batch qui collaborent (c'est pas ma faute) et se synchronisent à travers des fichiers (informatique de 92, désolé).
Donc il me faut quelques icônes (fichier / serveurs / db ) et des boites et de quoi représenter des flux et leur synchronisation. Sans compter les événements système et les scheduler externe (cron, inittab et autres outils de monitoring qui lancent ces scripts, qui vont à leur tour appeler des batchs et se synchroniser avec des fichiers...)
Donc un espèce de diagramme bâtard sans normalisation.

Sur le papier c'est 10mn mais généralement quand j'essaie de passer mes petit schémas de ce genre vers une version numérique les ennuis commencent. Surtout avec cette merde de gliffy...
Je vais le tenter sur Yed en essayant de ne pas y passer la journée...

[rOut]

Y'a un plugin confluence aussi pour PlantUML, et pour les icones, il y a l'air d'avoir ça aussi : https://github.com/tupadr3/plantuml-icon-font-sprites

[William Vaurien]

Seulement confluence c'est pas moi qui l'administre et seuls les plugins 'officiels' de ma boite ont droit de citer
Généralement pour les schémas PlantUML (ou yed) je mets une image et le code dans un fichier joint ou une référence vers un repo git.

Mais là je crois que PlantUML ne pourra pas beaucoup m'aider à dessiner ce que je veux !

[Møgluglu]

Bah en fait c'est dans le cadre d'un gestionnaire de réseaux de neurones (c'est mon taf en labo). Je "réveille" des groupes de neurone, en gros ça se passe ainsi :

OK, c'est un scheduler glouton qui assigne des tâches indépendantes sur un nombre fixe de threads.

Il y a une obligation pour que ce soit le thread maître qui assigne les tâches aux threads ? Parce que le plus simple dans ce cas est une file de commandes avec 1 écrivain à un bout et n lecteurs à l'autre bout. Le maître insère les tâches dans la file (ça bloque quand elle est pleine). Les travailleurs popent une tâche dans la file dès qu'ils ont finit la précédente (ça bloque quand elle est vide). Et tu peux utiliser une FIFO synchronisée de ta bibliothèque préférée sans avoir à l'écrire à la main. Avec une seule entrée dans la file ça revient à peu près au même que ton code, mais avoir plusieurs entrées permet de lisser les à-coups et minimiser les temps d'attente.

[Nilsou]

L'obligation pour le thread maitre vient du fait qu'on passe de toute façon par un arrêt final et un relancement de tout le "script", ainsi on est certains que l'ensemble s'est exécuté X fois. Le thread maitre est alors chargé de vérifier la pertinence de "si il faut démarrer un groupe ou non".
Après oui, en pratique ça pourrait être totalement desynchronisé sans thread maitre avec chaque thread qui appelle la vérification lui même lorsqu'il a fini le taf. Mais je préfère garder en main la fréquence max de passage d'un groupe à un autre qui peut alors être facilement paramétré via la fréquence d'appel au thread maitre, si on veut. Après dans le programme c'est aussi pour des raisons historique.

Le soucis avec le coté FIFO c'est que mes threads vont "manger" mes taches, mais que pour un thread donné je pourrait avoir n'importe quel groupe logique de neurone non ? Alors que dans mon fonctionnement actuel il y a un liens explicite entre un thread et le groupe de neurone qu'il gère. J'avoue que je préfère cette dernière solution. Par ailleurs ici les taches ne sont pas vraiment indépendantes puisque leur ordre d’exécution dépends de l’exécution ou non des taches précédentes (selon les liens neuronaux présents) .

[Møgluglu]

Tu as un retour sur leurs utilisations ? Pour le moment, j'utilise une solution maison pour faire un boulot similaire (synchronisation d'un kernel, synchronisation multi GPU, etc.) compatible kepler.-Ce qui m’intéresse surtout c'est latence de ces mécanismes de synchro.

J'ai regardé surtout les petits groupes à l'intérieur d'un thread-block. Pour les groupes grid et multi-grid, l'implémentation de Nvidia s'appuie sur une API avec des fonctions cudaCG* qui n'est pas documenté pour l'instant (une recherche sur cudaCGGetRank renverra bientôt vers ce topic).
Donc pour l'instant il faut se contenter de la doc des thread groups et des quelques exemples du SDK.

Le soucis avec le coté FIFO c'est que mes threads vont "manger" mes taches, mais que pour un thread donné je pourrait avoir n'importe quel groupe logique de neurone non ? Alors que dans mon fonctionnement actuel il y a un liens explicite entre un thread et le groupe de neurone qu'il gère. J'avoue que je préfère cette dernière solution. Par ailleurs ici les taches ne sont pas vraiment indépendantes puisque leur ordre d’exécution dépends de l’exécution ou non des taches précédentes (selon les liens neuronaux présents) .

Ça ressemble à de l'ordancement de synchronous data flow ou de réseau de Kahn du coup, non ? Tu as un graphe de tâches que tu veux placer sur des ressources (threads) en respectant les dépendances et les contraintes sur le type de ressource (groupe de neurone). Avec aussi des barrières de synchro avec le thread maître, que tu peux exprimer comme une tâche qui dépend de toutes celles qui précèdent.

[Thingazazi]

On peut poser des questions techniques en programmation python sur ce topic ? J'ai un problème de temps de calcul que je n'arrives pas à résoudre alors que la solution est peut être super simple pour les pros de ce langage.

[Lazyjoe]

Facile : change de langage.

Sinon le topic est précisément là pour ce genre de question.

[Thingazazi]

Mais, cet homme est partout

Voici donc l'exposé de mon soucis :

Je dispose de 38 array M de dimensions m*n répartis en 8 matrices différentes pour des raisons de limitation de l'espace mémoire alloué. Chaque array correspondant à autant de fonctions coût différente d'une méthode de détermination de deux paramètres A et B de dimensions respectives m et n (chaque fonctions étant calculée d'une manière spécifique, je ne peux pas en réduire le nombre).
Ce qui m'intéresse est de connaître pour chaque fonction les valeurs x et y des paramètres A et B tels que M[x,y] = max(M)

Pour faire ça, j'utilise classiquement un argmax qui me retourne x et y moyennant un petit unravel.index. Rien de bien sorcier jusque là.

L'opération est également réalisée environ 150 000 fois par analyse à travers une boucle for.

Jusqu'à récemment, les dimensions m et n avaient pour valeurs 100 et 75 mais pour des questions de qualité des résultats, nous avons du les augmenter jusque 991 et 778 et c'est là qu'est mon problème...

Auparavant, la résolution de l'ensemble de mon problème prenait 30 min pour une analyse, désormais il faut compter plus de 30h. Sachant qu'il y a des milliers d'analyses à faire et que l'objectif est de pouvoir faire l'analyse en moins d'une heure pour que l'algo puisse être passé en production

La chute de perf vient du argmax dont les perfs baissent logiquement fortement avec l'augmentation de la dimension des tableaux : de 10s environ par tableau auparavant pour 150 000 itérations, je suis passé à plus de 15min.

Mon problème est donc de trouver un moyen de rendre le tout beaucoup plus efficace sachant que le traitement se fait obligatoirement en python sur un thread et que le projet devait être terminé vendredi dernier et que je ne peux donc pas tout ré-écrire de zéro pour prendre en compte les nouveaux besoins.

Il y a des équivalents plus rapides au argmax ou des moyens simple d’accéléré tout ça en ordonnant différemment les dimensions ? Pour le moment, je n'ai pas trouvé d'alternative.

Je ne sais pas si c'est bien compréhensible, ni si une solution peut être trouvée vu les contraintes techniques du projet

[Møgluglu]

Si tu utilises déjà numpy, ça semble difficile de faire beaucoup mieux sans changer de langage ou d'algo. Comment est-ce que les tableaux sont mis à jour ?

[Thingazazi]

J'utilise déjà numpy oui. Pour les tableaux, ils sont supprimés à la fin de chacune des itérations pour laisser de l'espace mémoire à d'autres variables utilisées pour d'autres méthodes de philosophie différente.

J'avais pensé découper mes tableaux en sous-éléments, comparer les maximums des sous éléments puis ne faire la recherche que dans celui qui contient le max. Seulement, à ajouter ce genre d'étape, je ne suis pas convaincu que ça fasse gagner du temps puisque chaque tableau étant indépendant, je suis obligé de répéter l'opération à chaque fois.

[Møgluglu]

Qu'est-ce qui te fait dire que c'est le calcul du max qui prend du temps, plutôt la création et le remplissage des tableaux à chaque itération ?

Tu aurais un pseudo-code avec les grandes lignes de l'algo ?

[ducon]

Oui, je pensais plutôt à la manipulation (suppression de lignes) des tableaux.

[vectra]

Perso je trouve que PlantUML c'est cool.

Et c'est supporté par org-mode sous emacs

Org-mode
Comment j'ai pu vivre sans pendant tout ce temps

[vectra]

J'utilise déjà numpy oui. Pour les tableaux, ils sont supprimés à la fin de chacune des itérations pour laisser de l'espace mémoire à d'autres variables utilisées pour d'autres méthodes de philosophie différente.

J'avais pensé découper mes tableaux en sous-éléments, comparer les maximums des sous éléments puis ne faire la recherche que dans celui qui contient le max. Seulement, à ajouter ce genre d'étape, je ne suis pas convaincu que ça fasse gagner du temps puisque chaque tableau étant indépendant, je suis obligé de répéter l'opération à chaque fois.

Si t'as pas timé un peu décemment ton code, tu n'as aucune idée d'où vient ton bottleneck.
En tous cas, si tu persistes à allouer et désallouer itérativement de grands volumes de données par manque de place, faut pas venir te plaindre après du résultat. Je ne sais pas quel est le code C de ta lib Python et comment il fait dedans, mais c'est généralement une très mauvaise idée.

Tu as aussi des limites physiques lorsque tu parcours des gros volumes mémoire. Compte 20 Go/s de bande passante pour un bon code C++ bien optimisé sur un PC standard. Au doigt mouillé dans les 5-10 Go/s avec un code C++ immédiat, et disons 1 Go/s pour un code Python parce que c'est Python

A 10 Go/s, il te faut déjà 2 dixièmes de secondes pour (disons) incrémenter les valeurs d'un tableau qui fait 1 Go en mémoire...
Là, avec 38*1000*1000*150 000, tu as 5700 Go de parcourus rien que pour faire un incrément des valeurs à chacune de tes 150k itérations. Ca fait déjà 19 minutes à 10 Go/s, en supposant que tu aies des valeurs sur un octet (4 en flottants 32 bits, par exemple).
Si tu fais en plus des argmin, tu fais bien plus d'opérations mémoire à chaque itération. Ca finit par taper.

Ca sent quand-même fortement la solution GPU, qui te permet de tabler sur 200Go/s de BP pour commencer. Je suis sûr qu'il y a moyen de faire ça, même dans le langage impie qu'est Python.

[Thingazazi]

Qu'est-ce qui te fait dire que c'est le calcul du max qui prend du temps, plutôt la création et le remplissage des tableaux à chaque itération ?

Tu aurais un pseudo-code avec les grandes lignes de l'algo ?

Quelques tests fait sur un script simplifié du problème. Mais à vrai dire, je n'ai pas pensé à regarder le remplissage et la suppression des tableaux. Le remplissage se fait par calcul d'une fonction densité de probabilité avec loi normale suivant un ou deux axes, avec réplication du résultat dans le second axe pour le cas du 1d. Mais je n'ai pas ça dans le script simple avec lequel j'ai tester le argmax.

Je vous mettrai le pseudo code demain ouais, ça sera sans doute plus clair.

- - - Mise à jour - - -

@ Vectra
Ah bah c'est un soupçon, mais comme je suis loin d'être un as de la programmation, je peux me planter dans les grandes largeurs

Intéressant la problématique de la lecture du volume de données, je ne connaissait pas ces ordre de grandeur. Pour les vidages mémoire, c'est si impactant que ça ? C'est plus rapide de remplir de nouveau un tableau existant que d'en recréer un nouveau ?

[vectra]

Tu as un coût minimal dès que tu lis / écris en mémoire. Si tu comptes tous tes accès, rien qu'avec la BP mémoire maximale de ton processeur + mémoire, tu sais déjà le temps incompressible en deça duquel ton aglo n'ira jamais.

Je m'imaginais qu'allouer de la mémoire itérativement lorsqu'il y a de grandes plages libres, ça coûtait rien. En pratique, c'est souvent infernal / horrible mais je ne sais plus dans quelles proportions parce que je n'ose plus. Pour avoir codé en Common Lisp dans ma jeunesse, je me souviens que le consing (l'allocation) était souvent le premier bottleneck.

[Thingazazi]

Ca sent quand-même fortement la solution GPU, qui te permet de tabler sur 200Go/s de BP pour commencer. Je suis sûr qu'il y a moyen de faire ça, même dans le langage impie qu'est Python.

Il faudra que j'apprenne à faire du code parallèle déjà avant d'en arriver là. Et le code final devra pouvoir tourner sur un petit serveur de calcul une fois en production, pas une machine de guerre. En plus, je ne sais même pas si le calcul GPU se fait déjà chez nous.

Déjà, le passage : script de bidouille perso pour traiter de petits volumes de données (qqes Go) pour mes besoin de recherche -> script de production avec 20 étapes de traitements, des tests et vérifications dans tous les sens pour enfin en arriver au coeur du problème, ça nécessite des connaissances techniques que je ne maîtrise pas encore pour rendre le tout efficace.

[vectra]

Tu dois avoir du PyCuda. Ca devrait encapsuler la plupart de tes opérations avec des appels de CUDA C++ sans que tu aies besoin de coder du massivement parallèle.
Tu peux faire des appels séquentiels de méthodes qui, elles, seront implémentées de manière massivement parallèle. C'est pas forcément top (streaming?) mais ça aide énormément.

Avant de partir dans les tours, faire un timing précis et sérieux de tout le programme. Je ne sais pas comment on fait sous Python.