IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
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
    Homme Profil pro
    Étudiant
    Inscrit en
    mai 2020
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 23
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mai 2020
    Messages : 3
    Points : 1
    Points
    1
    Par défaut 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é

    Homme Profil pro
    Data Ingénieur & Scientist
    Inscrit en
    février 2009
    Messages
    476
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Data Ingénieur & Scientist
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : février 2009
    Messages : 476
    Points : 1 159
    Points
    1 159
    Billets dans le blog
    2
    Par défaut
    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
    Homme Profil pro
    Étudiant
    Inscrit en
    mai 2020
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 23
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mai 2020
    Messages : 3
    Points : 1
    Points
    1
    Par défaut
    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é

    Homme Profil pro
    Data Ingénieur & Scientist
    Inscrit en
    février 2009
    Messages
    476
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Data Ingénieur & Scientist
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : février 2009
    Messages : 476
    Points : 1 159
    Points
    1 159
    Billets dans le blog
    2
    Par défaut
    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
    Homme Profil pro
    Étudiant
    Inscrit en
    mai 2020
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 23
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mai 2020
    Messages : 3
    Points : 1
    Points
    1
    Par défaut
    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

Discussions similaires

  1. Ordonnancement de tâches dans GWT avec la classe Scheduler
    Par Mickael Baron dans le forum GWT et Vaadin
    Réponses: 0
    Dernier message: 03/04/2012, 23h37
  2. Scheduled Task
    Par wiglaft dans le forum API, COM et SDKs
    Réponses: 1
    Dernier message: 22/12/2005, 05h49
  3. DTS package scheduling problems
    Par jhaythem dans le forum MS SQL Server
    Réponses: 5
    Dernier message: 10/08/2005, 14h22
  4. ordonnancement entre xmlService
    Par pram dans le forum XMLRAD
    Réponses: 9
    Dernier message: 25/04/2003, 10h57

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo