Algorithmes d'ordonnancement Scheduling

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

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,

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

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,

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 :mouarf:

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.

:salut:

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:

---

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:

---

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:

---

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

---

Citation:

---

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).

Citation:

---

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

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

Citation:

---

Envoyé par dourouc05

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).

---

Tu as parfaitement raison, merci pour les références.

Marlan