Jouer en triant, ou trier en jouant ? Ou la course contre la montre.

Objectif : découvrir la notion de parallélisme en informatique au travers d’une activité ludique et vivante, où les participants jouent eux-même le rôle de l’ordinateur.

Résumé : les ordinateurs sont rapides, mais la vitesse à laquelle ils peuvent exécuter leurs programmes (nombre de calculs par seconde par exemple) est certes grande mais bornée. Pour de très grands problèmes nécessitant une quantité de calcul colossale, il est possible d’accélérer les choses en utilisant plusieurs ordinateurs, ou plusieurs processeurs, pour résoudre les différentes parties d’un problème. Cette méthode s’appelle le parallélisme. Dans cette activité, tirée de la traduction française de l’ouvrage de Tim Bell Computer Science Unpluged, on va découvrir le parallélisme à travers une activité sur les réseaux de tri, qui effectuent plusieurs comparaisons en même temps.

Exemple de drap bricolé pour l’activité, on prend un vieux drap (ici une housse de couette décousue pour doubler la surface, de presque 2m50 sur 5mètres) et on peint le motif en laissant au moins 50 cm entre les carrés pour que les gens puissent se placer.

Liens pédagogiques :

mathématiques : comparer les nombres, supérieur à (>), inférieur à (<)

Compétences :

comparer
se repérer dans l’espace, s’orienter
résoudre des problèmes en coopération

Âge :

6 ans et plus (testé en demi-classe en grande section de maternelle)
différent niveaux de difficultés/extension possibles en fonction de l’âge

Matériel :

craie (en extérieur) ou drap + feutres/peinture (en intérieur)
deux jeux de six cartes
- photocopiez l’exemplaire du descriptif de cette activité destiné au professeur sur du papier épais et découpez les cartes (page 72)
chronomètre

Description du problème : on veut trier 6 valeurs, des entiers par exemple, par ordre croissant. Il existe de nombreux algorithmes permettant de trier ces valeurs. Ces algorithmes sont corrects et leur rapidité varie, mais s’ils sont appliqués sur un seul processeur, la durée d’exécution sera égale à la somme du temps de chacune des opérations à effectuer (comparaison de valeurs, échange,…). Avec le parallélisme, l’idée est de partager le travail entre plusieurs processeurs/ordinateurs différents qui vont donc travailler en même temps, et ainsi diminuer le temps nécessaire pour finir le tri.

Déroulé de l’activité : les règles sont décrites dans le manuel (voir lien dans le paragraphe matériel). Une fois les règles données il faut bien insister sur la solidarité. Arriver le premier n’est pas une victoire, et c’est même un échec si on a laissé quelqu’un derrière soi ou si on est allé trop vite pour comparer et qu’on s’est trompé. L’activité peut se lancer assez rapidement, peut se faire avec des groupes assez grands car il est possible de faire tourner les groupes assez rapidement (après quelques tentatives d’un même groupe). Le manuel propose deux jeux de cartes, mais en fonction du temps disponible et du public on peut décliner cela en tout plein d’autres cartes (au passage il est intéressant d’avoir des jeux de plus de 6 cartes, pour que les joueurs ne sachent pas à l’avance dans quelle case d’arrivée ils vont aller) :

pour les petits (maternelle) des cartes avec des points, par exemple 0 (aucun point), 1, 2 , 3, 4, 5, 6, 7, 8 et une carte avec beaucoup de points (permet de préciser qu’il n’est pas nécessaire de compter les points, mais juste de comparer les valeurs, et savoir que « tout plein » est plus grand que 6 par exemple)
toujours pour les petits, on peut trier des dessins par taille (le même dessin mais de taille différente), ou mettre des cartes de tailles différentes
pour les élèves de primaire, on peut écrire de plus grands nombres que ceux des cartes, ou mettre des calculs (additions sans retenue pour les plus petits, opérations plus complexes pour les plus grands) à trier selon la valeur du résultat du calcul, mettre des lettres ou des mots à trier (bien préciser de quel côté on va quand on est vers le début de l’alphabet)
pour les encore plus grands on peut laisser aller son imagination : donner un objet plus complexe, par exemple un mail, qu’il faut trier suivant un critère qu’on donne au début (la taille, l’expéditeur, la date d’envoi,…), calculer la valeur d’une fonction en un point donné, évaluer le poids de différents objets très variés (un livre, une botte, …), trier des événements historiques en fonction de leur date etc. Voir aussi les activités supplémentaires du manuel (conception de réseaux avec plus/moins de valeurs à trier etc.).

En fonction de ce que l’on trie, on voit que la difficulté n’est pas seulement d’enchaîner les comparaisons, mais de décider si un objet est plus petit ou plus grand qu’un autre (par exemple pour le calcul).

Dans tous les cas, on peut comparer le temps sans parallélisme (compter le nombre de cercles dans le graphe, le nombre de comparaisons à effectuer l’une après l’autre) et le temps avec parallélisme (plusieurs comparaisons se font ensemble, et il suffit juste de compter le nombre de lignes, car toutes les comparaisons d’une même ligne se font ensemble). Sur le réseau de tri de l’exemple, la différence est 12 contre 5. On voit bien que cela accélère les choses.

Quelques précisions

Non, un ordinateur avec 5 processeurs ne va pas 5 fois plus vite qu’un ordinateur avec un seul processeur, et ce pour deux raisons :

un travail ne se découpe pas toujours en 5 parts égales (voir exemple ci-dessous)
entre deux étapes de calcul il faut que les processeurs/ordinateurs communiquent entre eux, pour se transmettre le résultat des calculs précédents. Dans notre exemple c’est le temps de suivre les chemins dans le réseau pour arriver au prochain cercle.

Pour ce qui est du partage des tâches, on peut faire plusieurs calculs en même temps s’ils sont indépendants. Cela ne fonctionne pas si on a besoin du résultat du premier calcul pour faire le deuxième. L’exemple du manuel est très parlant. On peut mettre 10 personnes pour creuser un trou de 1 mètre de profondeur et 10 mètres de long, ça ira environ 10 fois plus vite. Par contre pour creuser un trou d’un mètre de long et 10 mètres de profondeur, on ne peut pas creuser le mètre du fond tant qu’on n’a pas creusé les 9 mètres au-dessus.

Dans la plupart des problèmes, on peut faire une partie des choses en parallèle, mais parfois certains processeurs ont fini et doivent attendre le résultat des autres pour continuer

En vidéo, l’explication de cette activité par Marie Duflot : Comprendre l’informatique en jouant à courir sur un réseau de tri