Notes #1

New issue

Closed

opened 2024-03-11 10:21:22 +01:00 by Anri · 1 comment

Anri commented

2024-03-11 10:21:22 +01:00

Owner

Modèle par tâche

1 tâche = morceau de code : exemple : fn principale d'un thread
Cette tâche peut créer de nouvelles tâches, l'ordre d'exécution des tâches est désordonnées.
Si on veut faire B avec A, alors on crée B dans A car on ne peut pas exécuter une tâche avant sa création.

Soit f, c
Tâche : exécuter f(c)
Solution 1
- pthread + join them pour être sûr que le programme ne termine pas avant d'avoir terminé et c'est bon
- Problème : on schedule rien, autant utiliser pthread directement
Solution 2
- Prendre une pile de tâche, à chaque sched_spawn, on empile la tâche sur la pile
- Problème : c'est séquentiel
- Pile : avec un mutex
Solution 3
- On fait comme la solution 2, mais on ne prend pas la dernière tâche, on en prend 1 au hasard
- Problème : s'il n'y a plus rien à faire on ne peut pas terminer parce que l'on ne sait pas si les autres tâches font encore des trucs
- Variable de condition ou sleep (sale) pour attendre une nouvelle tâche ?

Question ouverte : pourquoi une pile au lieu d'une file ?

En java, c'est un thread_pool, et ça marche très bien sur 2 cœurs, relativement 4 et plus du tout sur 16

C'est cher quand il y a de la contention, dû aux mutex
Solution 4
- Au lieu de faire 1 seule pile, on en met une sur chaque cœur. Chaque cœur a donc ses tâches, chaque thread fait un pop de sa pile et exécute sa tâche. On récupère les tâches par le bas de la pile
- Problème : initialement il y a qu'une seule tâche ?
- Problème : Un cœur peut terminer toutes ses tâches
  - Solution : tirer au hasard un k et essayer de piquer du travail à t_k+1 jusqu'à ce qu'il revienne à lui, s'il n'a rien trouvé, c'est qu'il n'y a rien à faire donc il s'endort. S'il trouve, alors il prend la tâche en haut de la pile.
- \Rightarrow On a donc plus une pile, mais un deck.
- Efficace parce que généralement le gros du travail est en haut et quand on n'a rien à faire autant prendre le plus gros du travail
- Problème : Quand on crée un thread, il se trouve sur le même cœur ; on a une localité anormale, mais ça rend le tout + efficace

Notes

État de l'art en 2017.
Le code du prof fait 270 lignes de code, le + dur est de comprendre l'algorithme (et l'algo n'est pas compliqué)
Si on n'écrit que ça on n'a pas la moyenne, le but est de faire le programme le + rapide via un jeu de test et un jeu de résultat
Sur le rapport il faut des jolies graphiques, des jolies courbes :
- Sur 2 cœurs
- Sur 8 cœurs
- Analyse intéressante sur le rapport + explication de la méthodologie

Tout ça donne : 13/20

Pour avoir + il faut faire des extensions.
À l'oral pour la démo, il faut faire une démo cool qui utilises tous les cœurs ; apparemment il y a plein d'algo qui le font.

ChatGPT interdits, il faut tout créditer
Toutes les questions sont sur la mailing list

Date de rendu

" Je sais pas "
" Le plus tard que possible "

Modèle par tâche 1 tâche = morceau de code : exemple : fn principale d'un thread Cette tâche peut créer de nouvelles tâches, l'ordre d'exécution des tâches est désordonnées. Si on veut faire $B$ avec $A$, alors on crée $B$ dans $A$ car on ne peut pas exécuter une tâche avant sa création. - Soit `f`, `c` - Tâche : exécuter `f(c)` - **Solution 1** - `pthread` + `join them` pour être sûr que le programme ne termine pas avant d'avoir terminé et c'est bon - Problème : on schedule rien, autant utiliser `pthread` directement - **Solution 2** - Prendre une pile de tâche, à chaque `sched_spawn`, on empile la tâche sur la pile - Problème : c'est séquentiel - Pile : avec un mutex - **Solution 3** - On fait comme la solution 2, mais on ne prend pas la dernière tâche, on en prend 1 au hasard - Problème : s'il n'y a plus rien à faire on ne peut pas terminer parce que l'on ne sait pas si les autres tâches font encore des trucs - Variable de condition ou sleep (sale) pour attendre une nouvelle tâche ? Question ouverte : pourquoi une pile au lieu d'une file ? En java, c'est un `thread_pool`, et ça marche très bien sur 2 cœurs, relativement 4 et plus du tout sur 16 - C'est cher quand il y a de la contention, dû aux mutex - **Solution 4** - Au lieu de faire 1 seule pile, on en met une sur chaque cœur. Chaque cœur a donc ses tâches, chaque thread fait un pop de sa pile et exécute sa tâche. On récupère les tâches par le bas de la pile - Problème : initialement il y a qu'une seule tâche ? - Problème : Un cœur peut terminer toutes ses tâches - Solution : tirer au hasard un `k` et essayer de piquer du travail à `t_k+1` jusqu'à ce qu'il revienne à lui, s'il n'a rien trouvé, c'est qu'il n'y a rien à faire donc il s'endort. S'il trouve, alors il prend la tâche en _haut_ de la pile. - $\Rightarrow$ On a donc plus une pile, mais un deck. - Efficace parce que généralement le gros du travail est en haut et quand on n'a rien à faire autant prendre le plus gros du travail - Problème : Quand on crée un thread, il se trouve sur le même cœur ; on a une localité anormale, mais ça rend le tout + efficace ## Notes - État de l'art en 2017. - Le code du prof fait 270 lignes de code, le + dur est de comprendre l'algorithme (et l'algo n'est pas compliqué) - Si on n'écrit que ça on n'a pas la moyenne, le but est de faire le programme le + rapide via un jeu de test et un jeu de résultat - Sur le rapport il faut des jolies graphiques, des jolies courbes : - Sur 2 cœurs - Sur 8 cœurs - Analyse intéressante sur le rapport + explication de la méthodologie Tout ça donne : 13/20  Pour avoir + il faut faire des extensions. À l'oral pour la démo, il faut faire une démo cool qui utilises tous les cœurs ; apparemment il y a plein d'algo qui le font. - ChatGPT interdits, il faut tout créditer  - Toutes les questions sont sur la mailing list # Date de rendu - " Je sais pas " - " Le plus tard que possible "

Anri pinned this 2024-03-15 12:00:42 +01:00

Anri commented

2024-04-25 13:35:56 +02:00

Author

Owner

On vise le 10

Anri closed this issue

2024-04-25 13:35:57 +02:00

This repo is archived. You cannot comment on issues.

No labels

No milestone

No project

No assignees

1 participant

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference: Paris7/work-stealing-scheduler#1

No description provided.