Curriculum and Labs for Engineering Education

cancel
Showing results for 
Search instead for 
Did you mean: 

Challenge mathématiques #10 : Fabrication multitâches des jouets du Père Noël par les lutins

Père noel.jpg

Le Père Noël est très occupé avant noël, il doit livrer des jouets le plus vite possible suite à la commande des enfants.

Il est aidé de 4 lutins pour la fabrication. (Certains sont plus lents que d'autres à la tâche : 1 à 4 ms et les 4 lutins sont indépendant = équivalent aux 4 cœurs de mon PC de test)

Le Père Noël doit ouvrir 1000 lettres (fichier lettres.txt) qui contiennent les jouets à fabriquer de type 1 à 4. (Par exemple : Nounours, hélicoptère, tablette tactile, téléphone)

Le Père Noël répartit les jouets à fabriquer et les attributions des lutins au travail (Ils sont des Sous VIs non réentrants car les lutins ne se dupliquent pas non plus dans la réalité...)

Il doit mettre ensuite dans un sac (fichier "sac.txt") les jouets dans l'ordre des commandes.

Pour fabriquer chaque jouet il faut un processus de fabrication utilisant plusieurs lutins de suite.

Le premier doit prendre un ingrédient qui est une valeur donnée (double =  2) et l'utiliser pour la réalisation du jouet  (calcul) et la transmettre à un autre lutin.

Le dernier lutin ajoute le jouet final (résultat des calculs) dans le sac (fichier "sac.txt").

Méthode de fabrication des jouets :

Type 1 = Lutin 3 calcule la donnée puis transmet au lutin  1 et met dans le sac

Type 2 = Lutin 2 calcule la donnée puis transmet au lutin 4 et met dans le sac

Type 3 = Lutin 1 calcule la donnée puis transmet au lutin 2 et met dans le sac

Type 4 = Lutin 1 calcule puis transmet à 2 puis 3 puis 4 et met dans le sac

Le fichier "sac" contiendra les données des jouets dans l'ordre des commandes.

L'assistant du Père noël (moi) vérifiera que les jouets sont conforme et dans l'ordre des commandes.

Aidez le Père Noel à créer tous les jouets le plus vite possible. (Le temps du VI Père Noël sera compté).

Il existe un grand nombre de solutions pour éviter qu'un lutin n'est rien à faire ou pour préparer une liste de jouet à réaliser dans un ordre précis plus optimisé. (Pipelining)

Il faudra commenter dans le VI la stratégie faite par le Père Noel pour arriver au résultat. Ceci afin d'être validé.

Si problème, demander à l'assistant du Père noël de préciser un point particulier.

Règles :

- Utiliser les 4 sous-VI Lutins de 1 à 4 sans les modifier (surtout pas réentants)

- Utiliser le fichier "Lettres.txt" qui contient les jouets à fabriquer dans l'ordre des commandes (premier en haut)

- Retourner votre VI complété (ou projet avec les 4 lutins) : Pere Noel_Mon pseud_V1.vi à mon adresse emmanuel.roset@ni.com. Celui-ci doit écrire un fichier "sac.txt" dans le même répertoire (même format que lettres.txt) qui sera comparé au résultat attendu

- Le gagnant sera celui qui prendra le moins de temps pour réaliser les 1000 jouets (écritures et lectures incluses) soit le VI Père Noel au complet.

Votre cadeau à vous sera la possibilité de passer une certification de son choix gratuitement

Amusez vous bien.

Même si le VI n'est pas super optimisé, envoyez !!!

05/12 : Précision énoncé

Il n'est pas dans les règles du processus de fabrication de l'usine du pole nord de pré-fabriquer une seule fois un seul type particulier de jouet et d'y faire référence par la suite par index.

Le flux normal est de : Ouvrir les lettres ->  Fabriquer chaque jouets correspondant en parallèle ->  les mettre dans le sac dès que fabriqué.

Cela implique forcément des boucles ou processus parallèle.

Voici un exemple de principe des taches basiques sans appel de VI dynamique, ni boucles, ni machine d'état, ni producteur consommateur, ni Pipelining...

30/12

Fin du défi de Noel le 5 janvier !

exemple code.png

06/01/2014 L'heure des résultats

8 courageux Père Noel ont présentés leurs programmes de fabrique de jouets et ont fait efficacement travailler les lutins. Tous les codes fournis fonctionnement et répondent au défi.

Certaines architectures sont non seulement rapides mais en plus facilement maintenable. Même si ce n'est pas ce qui était demandé, ca a le mérite d'être souligné et je vous encourage à regarder les programmes des autres.

Bref voici le tableau des résulats :

Syx19431943,8
adcpc19441944,8
xavhendrix10491949,7
AntoineM19491950,2
Nico_EMC19521952,9
MaximeR19571959,5
Micael19621962,8
cisco19621963,9

Le gagnant est donc le Père Noel Syx qui est le seul à avoir adopté une architecture "manuelle" d'optimisation des lutins. Moins évidente elle opte pour une analyse du nombre de jouets par catégorie et une fabrication en série ce ceux-ci par une stratégie identique pour chaque catégorie.

La plupart des autres programmes sont très proches en temps car ils utilisent l'efficacité du multitâche par des producteurs/consommateurs et des FIFO pour laisser les lutins travailler dès qu'un d'entre eux est disponible. Ce qui est efficace et maintenable.

Bravo à Syx et bonne année 2014 à tous !

Emmanuel

Comments
Cisco
Active Participant
Active Participant
on

Bonjour,

Voici un challenge assez "épicé" pour préparer Noël... J'ai croisé dimanche le père Noël au marché de Noël de Colmar, si j'avais su, je lui aurais demandé un tuyau...

Francis M
emmanuel-fr
Member
Member
on

Le Père Noel va en arracher des poils de sa barbe du coup on saura qui c'est !

Comme d'habitude c'est pas trop difficile de faire une première version sans optimisation juste pour voir et que la majorité puisse participer.

Puis ensuite trouver des stratégies pour arranger les exécutions parallèles (euh le travail des lutins...)

Du coup j'en profite pour évoquer la présence d'une machine de défi de codage sympa sur NIDays (au CNIT la Défense à la journée du 11 février). En libre service car tout sera autonome. Il y aura 4 petits codes à réaliser le plus vite possible (2 à 3 min chaque) et un test unitaire vérifiera les résultats du VI (1 entrée/1 sortie). Un tableau sera mis a jour par la machine toute la journée et un vainqueur sera désigné dans l'après midi.

Je pense qu'il y aura du monde pour tester sa rapididé de réflexion de programmation

Cisco
Active Participant
Active Participant
on

Petite question au nouvel assistant du Père Noël: quel format pour les résultast ds le fichier sac? (nombre de décimales, type de séparateur). Je ne pense pas que ça change bcp le tps d'exécution, mais bon...

Francis M
emmanuel-fr
Member
Member
on

Bonjour le format de sortie sera : 0,000  soit 1 chiffre, une virgule, 3 chiffres de précision suivi d'une fin de ligne (retour à la ligne)

emmanuel-fr
Member
Member
on

Précision sur l'énoncé.

Il n'est pas dans les règles du processus de fabrication de l'usine du pole nord de pré-fabriquer une seule fois un seul type particulier de jouet et d'y faire référence par la suite par index.

Le flux normal est de : Ouvrir les lettres ->  Fabriquer chaque jouets correspondant en parallèle ->  les mettre dans le sac dès que fabriqué.

Cela implique forcément des boucles ou processus parallèle.

Cisco
Active Participant
Active Participant
on

Autrement dit, il faut traiter les lettres dans l'ordre. Interdit de les numéroter, de les produire dans l'ordre qui nous arrange et de les ranger ensuite dans le sac en fonction de leur numéro. C'est bien ça?

Francis M
emmanuel-fr
Member
Member
on

Pour répondre à votre question, c'est possible tout en respectant le flux.

Le challenge implique une exécution d'au moins 1000 x (de 2 à 4 lutins) pour produire les jouets. Reste à optimiser quel lutin travaille en même temps qu'un autre. (Par exemple le lutin 4 prend le même temps que les lutins 3 et 1 ensemble. C'est mieux de les faire travailler en parallèle)

Donc Il est possible de : Ouvrir les lettres (leur attribuer un numéro) ->  Fabriquer chaque jouets correspondant en parallèle (dans l'ordre de réalisation qui est le plus approprié/optimisé par exemple tous les modèles 4 à la suite ou les modèles 1 et 4 à la suite en parallèle...) ->  les mettre dans le sac dès que fabriqué (en réutilisant l'ordre de départ).

L'idée du challenge est l'optimisation des tâches parallèles qui ont des durées différentes d'occupation. Cela se retrouve souvent dans les processus où il y a des calculs séquentiels à faire (filtrage+ FFT, isolation de signaux,...) sur plusieurs signaux en parrallèle.

Pour simplifier le challenge, j'ai proposé des constantes pour l'entrée (valeur 2)  et aussi des lettres de jouets dans un ordre fixe (ce qui permet de voir un schéma d'arrivée optimisé). Ainsi il est tentant de pré-calculer les valeurs des 4 résultats 1 seule fois avec les lutins comme dans l'exemple donné et de créer un tableau de sortie seulement avec les valeurs des résultats dans l'ordre de départ. Ici, il n'y a pas challenge de parallélisme.

Le défi se corserai si les valeurs d'entrée de chaque fabrication était variable et que l'ordre des lettres aussi, ce qui ce rapproche des applications réelles.

Mais même si le Père Noel n'a pas optimisé le travail des lutins, Je suis preneur de tous les programmes de création des sacs de jouets qu'il pourra fabriquer !!

adcpc
Member
Member
on

Si j'ai bien compris, il y a une durée d'exécution minimale qu'il n'est pas possible de franchir ? Il suffit de prendre le Lutin le plus lent, calculer le nombre d'exécutions qu'il va devoir faire en se basant sur les lettres reçues et on obtient la durée minimale. Est-ce que je me trompe quelque part ?

emmanuel-fr
Member
Member
on

Intéressente réflexion. C'est juste, Il est possible de calculer  le temps théorique minimal mais je pense que cela peut être plus compliqué car cela dépend du nombre de fois que chaque lutin va devoir travailler au total.

Si les 3 lutins qui sont plus rapides travaillent en même temps que le 4e, alors en effet on a le temps miminum pour cette phase, cependant le nombre de fois que le lutin le plus lent (4e) a besoin de travailler est peut être inférieur aux nombre de fois des 3 autres. Et il faut alors optimiser pour faire travailler en même temps le 2 eme plus rapides avec le reste des autres plus lents en fonction de leur nombre de fois à travailler.

Il est également possible de faire travailler à la suite les lutins 3 et 1 en parallèle du 4 et également le 1 et 2 d'affilée en parralèle du 3... et à chaque boucle gagner du temps.

Sans optimisation "controlée" le temps/moment d'exécution des boucles (travail des lutins) va commencer aléatoirement (système multitache) et le temps total peut varier du tout au tout (chance ou pas du travail parallèle).

Enfin, il reste le temps de transition entre les processus des jouets (suivant méthode). Le temps au lutin de donner un jouet pas encore fini au prochain. Et le temps d'ouverture et écriture du fichier.

Pour info, j'ai déjà reçu un premier code fonctionnel d'un père noel et qui est bien pensé...

Nico_EMC
Member
Member
on

D'après le fichier lettres fourni, ça devrai être 1.940 secondes. J'en suis pas si loin (soft envoyé à l'instant)

adcpc
Member
Member
on

C'est également la valeur théorique que j'obtiens. J'en suis également tout près mais ça me semble un peu trop facile donc je fais peut-être quelque chose de non autorisé.

J'ai également fait un profiler pour voir l'activité des lutins et on voit clairement que le temps d'exécution dépend vraiment du lutin le plus lent. Pourtant mon algorithme n'est pas optimal vu que parfois certains Lutins n'ont rien à faire pendant de longues périodes :

Activité.jpg

Edit : Il me semble que le challenge devient clairement plus compliqué si les lutins travaillent à la même vitesse (même délai d'attente).

Cisco
Active Participant
Active Participant
on

Je viens aussi d'envoyer un code, ça marche mais j'ai du mal à me rapprocher des 1940ms... En même tps, il faut bien que le laisse gagner les autres aussi!

Francis M
xavhendrix
Member
Member
on

En fait le temps minimum d'exécution est de 1940 ms + 6 ms qui est le temps de traitement des lutins 1+2+3 avant le premier traitement du lutin 4 (le type 4 arrive avant le type 2). Le lutin 4 ne peut pas entrer en action dès la première itération du programme d'après les règles.

Nico_EMC
Member
Member
on

En fait, non. Le premier paquet du fichier étant de type 2, le temps mini est de 1940 + 2 = 1942ms.

Pour adcpc, il est normal que les lutins ne prennent pas beaucoup de CPU, puisque ce qui prend le plus de temps, c'est le "wait" (qui n'utilise pas de CPU)

adcpc
Member
Member
on

Mon profiler n'indique pas le temps CPU utilisé mais bien le temps pendant lequel les lutins sont actifs avec une granularité de 1us, plus ou moins la précision autorisée par le système d'exploitation (ce n'est pas du temps-réel).

xavhendrix
Member
Member
on

Je crois que nous n'avons pas les mêmes lettres car le fichier que j'ai, commence par 4,3,1,3,4 ... Une erreur de la poste?

Nico_EMC
Member
Member
on

Ah, non, ça vient de moi. J'ai cru voir ça en débug. Du coup, je pense que je peux arrêter l'optimisation, je suis vraiement proche du temps mini.

emmanuel-fr
Member
Member
on

HOHOHO, Bonsoir...

Je ne suis pas sûr que cela soit facile pour tout le monde (en réponse à adcpc) car l'assistant du Père Noel n'a pas reçu beaucoup de codes encore. Sinon, en effet le lutin 4 travaille suffisamment lentement (le bougre) pour que les autres aient tous le temps de créer les autres parties des jouets même en se donnant des éléments d’affilé (merci LabVIEW quand même qui rend pas mal de choses transparentes comme la glace).

Reste que les temps mesurés jusque ici sont encore différents du temps théorique absolu, qui ne tient compte que du travail des 4 lutins sans parler des autres tâches et de la méthode de mise dans le sac qui diffère suivant les codes. Pour le moment je compare le temps mini et moyen sur 10 exécutions ainsi que la validité des jouets.

Merci déjà à ceux qui ont envoyé leur VI Père Noel. J'espère que d'autres essaieront de tenter l'aventure et de les soumettre, même sans "stratégie". Rien n'est joué.

emmanuel-fr
Member
Member
on

Petit status après une semaine de fabrication de jouets.

J'ai reçu 2 nouveaux VI de 2 Père Noël qui apparemment savent bien gérer l'atelier du Pole Nord. Je croirais entendre une musique de noel quand je vois les noms des boucles "Fabrique du lutin 1", ou "Atelier de mise en sac".

Pour info dans les plus rapides cela se joue a quelques 10 aines de millisecondes du temps théorique, avec des méthodes parfois complètement différentes sur les outils du Père Noel pour guider les lutins. Ca reste cependant toujours dans le travail de lutins parallèles qui seront surement épuisés...

Cisco
Active Participant
Active Participant
on

Je viens d'envoyer une version améliorée, mais pour le fun car je pêche un peu... j'ai hâte d'étudier vos solutions pour apprendre comment bien gérer ces tâches en parallèle!

Joyeuses fêtes de fiin d'année à tous!!

Francis M
emmanuel-fr
Member
Member
on

Cette Version 5 est amélioré en efficacité en effet, mais je résiste pas à partager tout de suite les efforts sur les couleurs de noel pour les boucles et les personalisations des Sous-VI  (Sans rien dévoiler de l'atelier du Père Noel...)

Images.png

emmanuel-fr
Member
Member
on

Juste un petit message pour vous remercier d'avoir réfléchi à ce challenge Père Noel, j'ai reçu encore 2 nouveaux programmes la veille de Noel !! alors

Joyeux NOEL !!

Syx
Member
Member
on

Bonjour

Code envoyé.

Bonnes fêtes.

emmanuel-fr
Member
Member
on

Bonsoir aux participants de la fabrique de jouets,

Le délai pour rendre les codes du Père Noel est jusqu'au Dimanche 5 janvier.

Ca laissera le temps de digérer...

Bonnes fêtes de fin d'année

Emmanuel

MaximeR
Active Participant
Active Participant
on

Bonjour à tous et bonne année!!!

Code envoyé.

MaximeR

Maxime R.  

  CLA - Certified LabVIEW Architect / Architecte LabVIEW Certifié
  CTA - Certified TestStand Architect / Architecte TestStand Certifié

emmanuel-fr
Member
Member
on

Résulats et commentaires publiés à la suite de l'énoncé !

Syx remporte le Challenge de Noel

emmanuel-fr
Member
Member
on

Information qui ne change rien au résultat final mais un méchant grimlins c'est inséré dans le PC de test et a ralenti les deux derniers résultats, aussi veuillez trouvez le nouveau classement mis a jour, suite au reboot de la machine de test.

adcpc et xavhendrix avaient largement été mal positionnés puisqu'ils se retrouvent sur le podium ! Du coup tous les tests ont été refaits par sécurité.

Syx19431943,8
adcpc19441944,8
xavhendrix10491949,7
AntoineM19491950,2
Nico_EMC19521952,9
MaximeR19571959,5
Micael19621962,8
cisco19621963,9
Cisco
Active Participant
Active Participant
on

En bon dernier, j'ai au moins la satisfaction d'avoir fait un joli vi.... j'attends le prochain challenge pour essayer de me rattrapper! Bravo aux autres challengers, en vous souhaitant une bonne et heureuse année à tous!

Francis M
Contributors