La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Semi-Dynamic Multiprocessor Scheduling with an Asymptotically Optimal Performance Ratio Planification multiprocesseur semi-dynamique avec un rapport de performances asymptotiquement optimal

Satoshi FUJITA

  • Vues en texte intégral

    0

  • Citer

Résumé:

Dans cet article, nous considérons un problème d’attribution n tâches indépendantes sur m processeurs identiques de manière à minimiser le temps d'exécution global des tâches. Contrairement aux problèmes d'affectation de tâches classiques, nous supposons que le temps d'exécution de chaque tâche n'est pas fixé à l'avance, et que seules les limites supérieure et inférieure du temps d'exécution sont données au moment de la compilation. Dans ce qui suit, nous fournissons d’abord une analyse théorique de plusieurs politiques de planification conventionnelles en termes de ralentissement dans le pire des cas par rapport au résultat d’une politique de planification hors ligne optimale. Il est démontré que l'algorithme le plus connu dans la littérature atteint un rapport de performance dans le pire des cas de 1 + 1/f(n) où f(n) = O(n2/3) pour tout fixe m, qui se rapproche de un en augmentant n à l'infini. Nous proposons ensuite un nouveau schéma qui permet d'obtenir le meilleur ratio du pire cas de 1 + 1/g(n) où g(n) = Θ (n/Journal n) pour tout fixe m, qui s'en rapproche plus rapidement que les schémas précédents.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.8 pp.1764-1770
Date de publication
2009/08/01
Publicisé
ISSN en ligne
1745-1337
DOI
10.1587/transfun.E92.A.1764
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories
Théorie

Auteurs

Mots-clés

Table des matières