Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Programmation parallèle, calcul scientifique et de haute performance (HPC) Discussion :

Algortihmes d'ordonnancement Scheduling


Sujet :

Programmation parallèle, calcul scientifique et de haute performance (HPC)

  1. #1
    Nouveau Candidat au Club
    Algortihmes 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

  2. #2
    Membre éprouvé
    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,

  3. #3
    Nouveau Candidat au Club
    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

  4. #4
    Membre éprouvé
    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,

  5. #5
    Nouveau Candidat au Club
    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