Algorithmes d'ordonnancement Scheduling

**eternalWisdom** · 02/05/2020, 00h08

Bonjour,

Mon problème est simple, j'ai plusieurs tâches dont chacune j'ai estimer son temps d'execution.

Je souhaite répartir ces tâches dans N processeurs, dont le cout du processeur est la somme du temps de ses tâches.

La seule idée simple qui a aboutit c'est de trier les tâches en fonction du temps d'éxecution (le cout), mettre les N premières tâches chacune dans un processeur.

Enfin, à chaque itération sur les tâches restantes, on cherche le processeur qui a le moindre cout, et on la met dedans.

Le résultat est pas mal, pour traiter toutes mes taches dans un seul processeur c'est 400secondes, en mettant N =4 dans mon algorithme, j'ai a peu près un coût de 100secondes pour chaque processeur.

J'essaie d'implémenter d'autres algorithmes plus intelligents, on m'en a un peu parlé de la programmation linéaire mais je ne l'ai jamais faite avant et j'ai du mal à conceptualiser modéliser mon problème en problème algorithmique linéaire.
Est ce que quelques un parmi vous s'y connaissent en modélisation et pourrait me donner une idée d'un algorithme d'ordonnancement en programmation linéaire ?

Au mieux, si vous auriez des références ou des noms d'algorithmes de répartition de plusieurs tâches sur N processeurs je serais très curieux.

Merci bien par avance pour vos réponses

Cordialement

**dev_ggy** · 02/05/2020, 01h54

Bonjour,

Comme je comprends mal ton besoin, je réponds peut-être à côté. J'essaie de lancer des pistes pour la résolution linéaire. Faut-il un système qui gère les taches en parallèle ou doit-on modéliser cela par une matrice qu'on peut résoudre par bloc ensuite ? Il est même peut-être possible de résoudre cela par un GPU.

Si cela peut t'aider,
Cordialement,

**eternalWisdom** · 02/05/2020, 03h41

Merci pour ta réponse. Je vais essayer d'être plus simple et plus abstrait sur le problème.

J'ai un fichier comme tel :
Tache temps_dexecution
T1 100s
T2 25s
T3 25s
T4 50s
au total on a 400s de temps

Mon algorithme doit pouvoir les répartir sur N processeurs.
Par exemple on aura pour N = 2 :

Proc1 200s : T1
Proc2 200s : T2,T3,T4

**dev_ggy** · 02/05/2020, 18h31

Bonjour,

Merci pour ton explication. Je pense mieux comprendre ton problème.

C'est probablement un problème complexe d’algorithmique qu'on résout de façon non optimale par des algorithmes gloutons.

Cordialement,

**eternalWisdom** · 03/05/2020, 13h12

Merci. Je crois que l'algo que j'ai implémenté est glouton, mais j'ai pensé à faire un trie puis une recherche dichotomique pour avoir la somme maximum correspondant à la capacité d'un CPU
SI quelqu'un a des exemples d'algo qui peuvent être utiles je suis preneur

**Marlan** · 13/09/2022, 06h03

Bonjour,

Une autre possibilité est de décrire votre algorithme en ne considérant non pas un ensemble de tâches local aux processus, mais plutôt un ensemble de tâches global au système.

Pour ce faire, l'idée est de déclarer vos tâches en mémoire partagée MPI (voir les MPI_Win pour créer des fenêtres de mémoire partagée) et d'indiquer quelle tâche a déjà été résolue ou non.

Lorsqu'un processus finit une tâche, il regarde alors si d'autres tâches sont disponibles dans le tableau global de tâche (celui déclaré dans la fenêtre MPI). Si oui, il prend la première tâche disponible, si non il sort de la boucle des tâches.

Cet algorithme devrait conduire à un équilibrage de charge naturel pour votre problème.

EDIT : la même astuce peut être employée en mémoire partagée classique (avec OpenMP, tbb, les threads C++, pthread, ...) plutôt qu'avec MPI.

**dourouc05** · 14/09/2022, 11h16

Tu ne peux pas modéliser ce problème en programmation linéaire, vu que tu as des choix discrets (une tâche est exécutée par un CPU ou elle ne l'est pas). Par contre, tu peux modéliser ça en MIP (programmation linéaire en nombres entiers).

L'idée : une variable par paire tâche-processeur x[i,j], qui prend la valeur 1 quand tu assignes une tâche à un processeur, 0 sinon. Ensuite, des contraintes pour dire qu'une tâche est assignée à un seul processeur. Si j'ai bien compris, l'objectif est de répartir de manière égale les tâches sur les processeurs (autant que possible) : plutôt que de modéliser ça directement, je te propose de minimiser le maximum sur un processeur, donc de s'assurer que la charge du processeur le plus chargé sera aussi petite que possible (la seule manière de procéder étant de distribuer les tâches sur d'autres processeurs, idéalement sans faire qu'ils deviennent les processeurs les plus chargés) — d'où le deuxième jeu de variables.

En Julia, voici ce que ça donne (j'ai la flemme de l'écrire de manière mathématique, mais c'est de toute façon très proche).

Code julia :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
using JuMP
 
N = 2
tasks = [100, 50, 25, 25]
 
m = Model()
 
@variable(m, assign[i in 1:N, t in 1:length(tasks)], Bin)
@variable(m, load[i in 1:N] >= 0)
@variable(m, max_load >= 0)
 
@constraint(m, task_scheduled_once[t in 1:length(tasks)], sum(assign[:, t]) == 1)
@constraint(m, set_sum_load[i in 1:N], load[i] == sum(tasks[t] * assign[i, t] for t in 1:length(tasks)))
@constraint(m, set_max_load[i in 1:N], max_load >= load[i])
 
@objective(m, Min, max_load)

Pour ton exemple, voici le modèle complet :

Code julia :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
julia> print(m)
Min max_load
Subject to
 task_scheduled_once[1] : assign[1,1] + assign[2,1] == 1.0
 task_scheduled_once[2] : assign[1,2] + assign[2,2] == 1.0
 task_scheduled_once[3] : assign[1,3] + assign[2,3] == 1.0
 task_scheduled_once[4] : assign[1,4] + assign[2,4] == 1.0
 sum_load[1] : -100 assign[1,1] - 50 assign[1,2] - 25 assign[1,3] - 25 assign[1,4] + load[1] == 0.0
 sum_load[2] : -100 assign[2,1] - 50 assign[2,2] - 25 assign[2,3] - 25 assign[2,4] + load[2] == 0.0
 set_max_load[1] : -load[1] + max_load >= 0.0
 set_max_load[2] : -load[2] + max_load >= 0.0
 load[1] >= 0.0
 load[2] >= 0.0
 max_load >= 0.0
 assign[1,1] binary
 assign[2,1] binary
 assign[1,2] binary
 assign[2,2] binary
 assign[1,3] binary
 assign[2,3] binary
 assign[1,4] binary
 assign[2,4] binary

Voici la solution avec Cbc (solveur gratuit et libre) :

Code julia :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
julia> optimize!(m)
Welcome to the CBC MILP Solver
Version: 2.10.5
Build Date: Jan  1 1970
 
command line - Cbc_C_Interface -solve -quit (default strategy 1)
Continuous objective value is 100 - 0.01 seconds
Cgl0004I processed model has 2 rows, 4 columns (3 integer (2 of which binary)) and 8 elements
Cutoff increment increased from 1e-05 to 0.9999
Cbc0038I Initial state - 0 integers unsatisfied sum - 1.11022e-16
Cbc0038I Solution found of 100
Cbc0038I Relaxing continuous gives 100
Cbc0038I Cleaned solution of 100
Cbc0038I Before mini branch and bound, 3 integers at bound fixed and 0 continuous
Cbc0038I Mini branch and bound did not improve solution (0.04 seconds)
Cbc0038I After 0.04 seconds - Feasibility pump exiting with objective of 100 - took 0.01 seconds
Cbc0012I Integer solution of 100 found by feasibility pump after 0 iterations and 0 nodes (0.05 seconds)
Cbc0001I Search completed - best objective 100, took 0 iterations and 0 nodes (0.05 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Cuts at root node changed objective from 100 to 100
Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Gomory was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Clique was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
FlowCover was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
ZeroHalf was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
 
Result - Optimal solution found
 
Objective value:                100.00000000
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             0.11
Time (Wallclock seconds):       0.11
 
Total time (CPU seconds):       0.13   (Wallclock seconds):       0.13
 
 
julia> value.(assign)
2×4 Matrix{Float64}:
 1.0  0.0  0.0  0.0
 0.0  1.0  1.0  1.0

Envoyé par Marlan

Cet algorithme devrait conduire à un équilibrage de charge naturel pour votre problème.

Pas forcément. Ta solution est équivalent à un algorithme glouton : ça fonctionne très bien avec un seul processeur, mais il existe des cas où cette technique sera mauvaise (formellement : tu auras au pire une charge double de la solution optimale).

**Mat.M** · 14/09/2022, 11h44

Envoyé par eternalWisdom

Est ce que quelques un parmi vous s'y connaissent en modélisation et pourrait me donner une idée d'un algorithme d'ordonnancement en programmation linéaire ?
Au mieux, si vous auriez des références ou des noms d'algorithmes de répartition de plusieurs tâches sur N processeurs je serais très curieux.

La modélisation c'est une chose c'est la vision abstraite des fonctionnalités du projet.
Après l'ordonnancement des processus ça dépend étroitement des fonction de l'OS ( bref des API windows sous Windows) c'est un truc qu'il ne faut pas perdre de vue.
En raisonnant trop dans l'abstrait on ne prend pas en compte des spécificités des microprocesseurs.

Ensuite si le projet est destiné à tourner sous Intel regarder Intel Threading Building Blocks par exemple

**mach1974** · 14/09/2022, 17h29

il faut aussi tenir compte de la vitesse d'accès mémoires, RAM ETC CECI dit la théorie de la complexité donne des clés avec ROY CHARLES OU FORD DIJIKSTRA