Suchergebnisse

Mapping applications onto parallel platforms is a challenging problem, that becomes even more difficult when platforms are heterogeneous --nowadays a standard assumption. A high-level approach to parallel programming not only eases the application developer's task, but it also provides additional information which can help realize an efficient mapping of the application. In this paper, we discuss the mapping of pipeline skeletons onto different types of platforms: fully homogeneous platforms with identical processors and interconnection links; communication homogeneous platforms, with identical links but different speed processors; and finally, heterogeneous platforms. We assume that a pipeline stage must be mapped on a single processor, and we establish new theoretical complexity results for two different mapping policies: a mapping can be either one-to-one (a processor is assigned at most one stage), or interval-based (a processor is assigned an interval of consecutive stages). We provide several efficient polynomial heuristics for the most important policy/platform combination, namely interval-based mappings on communication homogeneous platforms. ; L'ordonnancement d'applications sur des plates-formes parallèles est un problèmedifficile, et ce d'autant plus si ces plates-formes sont hétérogènes. Une approche de haut niveau à la programmation parallèle, à base de squelettes algorithmiques, permet tout à la fois de faciliter la tâche du développeur, et d'acquérir des informations structurelles supplémentaires sur l'application, qui permettront d'obtenir un meilleur résultat.Dans ce rapport, on discute l'ordonnancement d'applications sous forme du squelette pipeline sur différent types de plateformes: les plateformes totalement homogènes(processeurs et liens de communication identiques), les plateformes à communications homogènes mais avec des vitesses de processeurs différentes, et les plateformes totalement hétérogènes. On suppose qu'une étape de pipeline doit être placée sur un unique processeur, et on établit de nouveaux résultats de complexité pour différentes stratégies d'allocation: on peut imposer qu'au plus une étape de pipeline soit allouée à chaque processeur, ou bien allouer un intervalle d'étapes consécutives aux processeurs.Une troisième politique ne fixe aucune contrainte d'allocation.Nous donnons de nombreuses heuristiques polynomiales efficaces pour la combinaison stratégie/plate-forme la plus importante, à savoir le placement par intervalle sur plateformes à communications homogènes. Ces heuristiques sont comparées au résultat optimal obtenu par une formulation du problème sous forme de programme linéaire, pour de petites instances du problème.

In this paper, we discuss and compare several policies to place replicas in tree networks, subject to server capacity and QoS constraints. The client requests are known beforehand, while the number and location of the servers are to be determined. The standard approach in the literature is to enforce that all requests of a client be served by the closest server in the tree. We introduce and study two new policies. In the first policy, all requests from a given client are still processed by the same server, but this server can be located anywhere in the path from the client to the root. In the second policy, the requests of a given client can be processed by multiple servers. One major contribution of this paper is to assess the impact of these new policies on the total replication cost. Another important goal is to assess the impact of server heterogeneity, both from a theoretical and a practical perspective. In this paper, we establish several new complexity results, and provide several efficient polynomial heuristics for NP-complete instances of the problem. These heuristics are compared to an absolute lower bound provided by the formulation of the problem in terms of the solution of an integer linear program. ; Dans ce rapport nous présentons et comparons plusieurs politiques de placement derépliques sur des arbres, prenant en compte à la fois des contraintes liées à la capacitéde traitement de chaque serveur et des contraintes de type QoS (qualité de service).Les requêtes des clients sont connues avant exécution, alors que le nombre et l'emplacementdes répliques (serveurs) sont à déterminer par l'algorithme de placement.L'approche classique impose que toutes les requêtes d'un client donné soient traitéespar un seul serveur, à savoir le plus proche du client dans l'arbre. Nous introduisonsdeux nouvelles politiques de placement. Dans la première, chaque client a toujours unserveur unique, mais ce dernier peut être situé n'importe où sur le chemin qui mènedu client à la racine dans l'arbre. Avec la deuxième politique, les requêtes d'un mêmeclient peuvent être traitées par plusieurs serveurs sur ce même chemin.Nous montrons que ces deux nouvelles politiques de placement sont à même de réduirefortement le coût total de la réplication. Un autre objectif de ce travail est l'analysede l'impact de l'hétérogénéité de la plate-forme, à la fois d'un point de vue théoriqueet pratique. Sur le plan théorique, nous établissons plusieurs résultats de complexité,dans les cadres homogène et hétérogène, pour l'approche classique et les nouvellespolitiques. Sur le plan pratique, nous concevons des heuristiques polynomiales pourles instances combinatoires du problème. Nous comparons les performances de cesheuristiques en les rapportant à une borne inférieure absolue sur le coût total de laréplication; cette borne est obtenue par relaxation d'un programme linéaire en nombre entiers qui caractérise la solution optimale du problème.

This paper discusses and compares several policies to place replicas in tree networks, subject to server capacity and QoS constraints. The client requests are known beforehand, while the number and location of the servers are to be determined. We study three strategies. The first two strategies assign each client to a unique server while the third allows requests of a client to be processed by multiple servers. The main contribution of this paper is to assess the impact of QoS constraints on the total replication cost. In this paper, we establish the NP-completeness of the problem on homogeneous networks when the requests of a given client can be processed by multiple servers. We provide several efficient polynomial heuristic algorithms for NP-complete instances of the problem. These heuristics are compared to the optimal solution provided by the formulation of the problem in terms of the solution of an integer linear program. ; Dans ce rapport, on discute et compare plusieurs politiques de placement de répliques dans les arbres, en prenant en compte à la fois des contraintes de capacité de traitement de chaque serveur et des contraintes de type QoS (Qualité de Service). Les requêtes des clients sont connues avant exécution, alors que le nombre et l'emplacement des répliques (serveurs) sont déterminés par l'algorithme de placement. Nous étudions trois stratégies. Les deux premières stratégies assignent chaque client à un serveur unique alors que la troisième permet que les requêtes d'un client soient traitées par plusieurs serveurs. L'objectif principal de ce travail est l'étude de l'impact des contraintes de qualité de service sur le coût total. Nous établissons la NP-complétude du problème sur des réseaux homogènes quand les requêtes d'un client peuvent être traitées par des serveurs multiples. Nous présentons plusieurs heuristiques polynomiales et efficaces pour les instances NP-complètes du problème sur plateformes hétérogènes. Ces heuristiques sont comparées à la solution optimale obtenue grâce à la formulation du problème en terme d'un programme linéaire en nombres entiers.

This paper discusses and compares several policies to place replicas in tree networks, subject to server capacity and QoS constraints. The client requests are known beforehand, while the number and location of the servers are to be determined. We study three strategies. The first two strategies assign each client to a unique server while the third allows requests of a client to be processed by multiple servers. The main contribution of this paper is to assess the impact of QoS constraints on the total replication cost. In this paper, we establish the NP-completeness of the problem on homogeneous networks when the requests of a given client can be processed by multiple servers. We provide several efficient polynomial heuristic algorithms for NP-complete instances of the problem. These heuristics are compared to the optimal solution provided by the formulation of the problem in terms of the solution of an integer linear program. ; Dans ce rapport, on discute et compare plusieurs politiques de placement de répliques dans les arbres, en prenant en compte à la fois des contraintes de capacité de traitement de chaque serveur et des contraintes de type QoS (Qualité de Service). Les requêtes des clients sont connues avant exécution, alors que le nombre et l'emplacement des répliques (serveurs) sont déterminés par l'algorithme de placement. Nous étudions trois stratégies. Les deux premières stratégies assignent chaque client à un serveur unique alors que la troisième permet que les requêtes d'un client soient traitées par plusieurs serveurs. L'objectif principal de ce travail est l'étude de l'impact des contraintes de qualité de service sur le coût total. Nous établissons la NP-complétude du problème sur des réseaux homogènes quand les requêtes d'un client peuvent être traitées par des serveurs multiples. Nous présentons plusieurs heuristiques polynomiales et efficaces pour les instances NP-complètes du problème sur plateformes hétérogènes. Ces heuristiques sont comparées à la solution optimale obtenue grâce à la ...

In this paper, we discuss and compare several policies to place replicas in tree networks, subject to server capacity and QoS constraints. The client requests are known beforehand, while the number and location of the servers are to be determined. The standard approach in the literature is to enforce that all requests of a client be served by the closest server in the tree. We introduce and study two new policies. In the first policy, all requests from a given client are still processed by the same server, but this server can be located anywhere in the path from the client to the root. In the second policy, the requests of a given client can be processed by multiple servers. One major contribution of this paper is to assess the impact of these new policies on the total replication cost. Another important goal is to assess the impact of server heterogeneity, both from a theoretical and a practical perspective. In this paper, we establish several new complexity results, and provide several efficient polynomial heuristics for NP-complete instances of the problem. These heuristics are compared to an absolute lower bound provided by the formulation of the problem in terms of the solution of an integer linear program. ; Dans ce rapport nous présentons et comparons plusieurs politiques de placement derépliques sur des arbres, prenant en compte à la fois des contraintes liées à la capacitéde traitement de chaque serveur et des contraintes de type QoS (qualité de service).Les requêtes des clients sont connues avant exécution, alors que le nombre et l'emplacementdes répliques (serveurs) sont à déterminer par l'algorithme de placement.L'approche classique impose que toutes les requêtes d'un client donné soient traitéespar un seul serveur, à savoir le plus proche du client dans l'arbre. Nous introduisonsdeux nouvelles politiques de placement. Dans la première, chaque client a toujours unserveur unique, mais ce dernier peut être situé n'importe où sur le chemin qui mènedu client à la racine dans l'arbre. Avec la deuxième ...

This paper introduces and assesses novel strategies to schedule firm real-time jobs on an overloaded server. The jobs are released periodically and have the same relative deadline. Job execution times obey an arbitrary probability distribution and can take unbounded values (no WCET). We introduce three control parameters to decide when to start or interrupt a job. We couple this dynamic scheduling with several admission policies and investigate several optimization criteria, the most prominent being the Deadline Miss Ratio (DMR). Then we derive a Markov model and use its stationary distribution to determine the best value of each control parameter. Finally we conduct an extensive simulation campaign with 14 different probability distributions; the results nicely demonstrate how the new control parameters help improve system performance compared with traditional approaches. In particular, we show that (i) the best admission policy is to admit all jobs; (ii) the key control parameter is to upper bound the start time of each job; (iii) the best scheduling strategy decreases the DMR by up to 0.35 over traditional competitors. ; Ce travail présente et évalue de nouvelles stratégies d'ordonnancement pour exécuter des tâches périodiques en temps réel sur une plate-forme surchargée. Les tâches arrivent périodiquement et ont le même délai relatif pour leur exécution. Les temps d'exécution des tâches obéissent à une distribution de probabilité arbitraire et peuvent prendre des valeurs illimitées (pas de WCET). Certaines tâches peuvent être interrompues à leur admission dans le système ou bien en cours d'exécution. Nous introduisons trois paramètres de contrôle pour décider quand démarrer ou interrompre une tâche. Nous associons cet ordonnancement dynamique à plusieurs politiques d'admission et étudions plusieurs critères d'optimisation, le plus important étant le Deadline Miss Ratio (DMR). Ensuite, nous dérivons un modèle deMarkov et utilisons sa distribution stationnaire pour déterminer la meilleure valeur de chaque ...

This paper introduces and assesses novel strategies to schedule firm real-time jobs on an overloaded server. The jobs are released periodically and have the same relative deadline. Job execution times obey an arbitrary probability distribution and can take unbounded values (no WCET). We introduce three control parameters to decide when to start or interrupt a job. We couple this dynamic scheduling with several admission policies and investigate several optimization criteria, the most prominent being the Deadline Miss Ratio (DMR). Then we derive a Markov model and use its stationary distribution to determine the best value of each control parameter. Finally we conduct an extensive simulation campaign with 14 different probability distributions; the results nicely demonstrate how the new control parameters help improve system performance compared with traditional approaches. In particular, we show that (i) the best admission policy is to admit all jobs; (ii) the key control parameter is to upper bound the start time of each job; (iii) the best scheduling strategy decreases the DMR by up to 0.35 over traditional competitors. ; Ce travail présente et évalue de nouvelles stratégies d'ordonnancement pour exécuter des tâches périodiques en temps réel sur une plate-forme surchargée. Les tâches arrivent périodiquement et ont le même délai relatif pour leur exécution. Les temps d'exécution des tâches obéissent à une distribution de probabilité arbitraire et peuvent prendre des valeurs illimitées (pas de WCET). Certaines tâches peuvent être interrompues à leur admission dans le système ou bien en cours d'exécution. Nous introduisons trois paramètres de contrôle pour décider quand démarrer ou interrompre une tâche. Nous associons cet ordonnancement dynamique à plusieurs politiques d'admission et étudions plusieurs critères d'optimisation, le plus important étant le Deadline Miss Ratio (DMR). Ensuite, nous dérivons un modèle deMarkov et utilisons sa distribution stationnaire pour déterminer la meilleure valeur de chaque ...

This paper introduces and assesses novel strategies to schedule firm real-time jobs on an overloaded server. The jobs are released periodically and have the same relative deadline. Job execution times obey an arbitrary probability distribution and can take unbounded values (no WCET). We introduce three control parameters to decide when to start or interrupt a job. We couple this dynamic scheduling with several admission policies and investigate several optimization criteria, the most prominent being the Deadline Miss Ratio (DMR). Then we derive a Markov model and use its stationary distribution to determine the best value of each control parameter. Finally we conduct an extensive simulation campaign with 14 different probability distributions; the results nicely demonstrate how the new control parameters help improve system performance compared with traditional approaches. In particular, we show that (i) the best admission policy is to admit all jobs; (ii) the key control parameter is to upper bound the start time of each job; (iii) the best scheduling strategy decreases the DMR by up to 0.35 over traditional competitors. ; Ce travail présente et évalue de nouvelles stratégies d'ordonnancement pour exécuter des tâches périodiques en temps réel sur une plate-forme surchargée. Les tâches arrivent périodiquement et ont le même délai relatif pour leur exécution. Les temps d'exécution des tâches obéissent à une distribution de probabilité arbitraire et peuvent prendre des valeurs illimitées (pas de WCET). Certaines tâches peuvent être interrompues à leur admission dans le système ou bien en cours d'exécution. Nous introduisons trois paramètres de contrôle pour décider quand démarrer ou interrompre une tâche. Nous associons cet ordonnancement dynamique à plusieurs politiques d'admission et étudions plusieurs critères d'optimisation, le plus important étant le Deadline Miss Ratio (DMR). Ensuite, nous dérivons un modèle deMarkov et utilisons sa distribution stationnaire pour déterminer la meilleure valeur de chaque ...

This paper introduces and assesses novel strategies to schedule firm real-time jobs on an overloaded server. The jobs are released periodically and have the same relative deadline. Job execution times obey an arbitrary probability distribution and can take unbounded values (no WCET). We introduce three control parameters to decide when to start or interrupt a job. We couple this dynamic scheduling with several admission policies and investigate several optimization criteria, the most prominent being the Deadline Miss Ratio (DMR). Then we derive a Markov model and use its stationary distribution to determine the best value of each control parameter. Finally we conduct an extensive simulation campaign with 14 different probability distributions; the results nicely demonstrate how the new control parameters help improve system performance compared with traditional approaches. In particular, we show that (i) the best admission policy is to admit all jobs; (ii) the key control parameter is to upper bound the start time of each job; (iii) the best scheduling strategy decreases the DMR by up to 0.35 over traditional competitors. ; Ce travail présente et évalue de nouvelles stratégies d'ordonnancement pour exécuter des tâches périodiques en temps réel sur une plate-forme surchargée. Les tâches arrivent périodiquement et ont le même délai relatif pour leur exécution. Les temps d'exécution des tâches obéissent à une distribution de probabilité arbitraire et peuvent prendre des valeurs illimitées (pas de WCET). Certaines tâches peuvent être interrompues à leur admission dans le système ou bien en cours d'exécution. Nous introduisons trois paramètres de contrôle pour décider quand démarrer ou interrompre une tâche. Nous associons cet ordonnancement dynamique à plusieurs politiques d'admission et étudions plusieurs critères d'optimisation, le plus important étant le Deadline Miss Ratio (DMR). Ensuite, nous dérivons un modèle deMarkov et utilisons sa distribution stationnaire pour déterminer la meilleure valeur de chaque ...

In this short note, we provide some comments on the recent paper ''Improving the computing efficiency of HPC systems using a combination of proactive and preventive checkpointing'' by Bouguerra et al. We start by identifying some errors in their equations. Then we explain that they do not actually use the distribution of lead times, contrary to statements by the authors. Finally, we show that their algorithm does not change policy at the best possible moment, and we point to our own work~\cite{rr-journal-prediction} for the (correct version of the) optimal algorithm. ; Dans cette courte note nous commentons l'article ''Improving the computing efficiency of HPC systems using a combination of proactive and preventive checkpointing'' de Bouguerra et al.~\cite{SlimIPDPS13}. Nous commençons par identifier des erreurs dans la mise en équation du problème. Nous expliquons ensuite que, contrairement à ce qu'ils prétendent, les auteurs n'utilisent pas la distribution du délai de prédiction (\emph{lead time}). Finalement, nous montrons que leur algorithme ne change pas de politique au moment optimum, et nous indiquons que nous avons présenté l'algorithme optimal dans un précédent rapport de recherche.

In this short note, we provide some comments on the recent paper ''Improving the computing efficiency of HPC systems using a combination of proactive and preventive checkpointing'' by Bouguerra et al. We start by identifying some errors in their equations. Then we explain that they do not actually use the distribution of lead times, contrary to statements by the authors. Finally, we show that their algorithm does not change policy at the best possible moment, and we point to our own work~\cite{rr-journal-prediction} for the (correct version of the) optimal algorithm. ; Dans cette courte note nous commentons l'article ''Improving the computing efficiency of HPC systems using a combination of proactive and preventive checkpointing'' de Bouguerra et al.~\cite{SlimIPDPS13}. Nous commençons par identifier des erreurs dans la mise en équation du problème. Nous expliquons ensuite que, contrairement à ce qu'ils prétendent, les auteurs n'utilisent pas la distribution du délai de prédiction (\emph{lead time}). Finalement, nous montrons que leur algorithme ne change pas de politique au moment optimum, et nous indiquons que nous avons présenté l'algorithme optimal dans un précédent rapport de recherche.

In this short note, we provide some comments on the recent paper ''Improving the computing efficiency of HPC systems using a combination of proactive and preventive checkpointing'' by Bouguerra et al. We start by identifying some errors in their equations. Then we explain that they do not actually use the distribution of lead times, contrary to statements by the authors. Finally, we show that their algorithm does not change policy at the best possible moment, and we point to our own work~\cite{rr-journal-prediction} for the (correct version of the) optimal algorithm. ; Dans cette courte note nous commentons l'article ''Improving the computing efficiency of HPC systems using a combination of proactive and preventive checkpointing'' de Bouguerra et al.~\cite{SlimIPDPS13}. Nous commençons par identifier des erreurs dans la mise en équation du problème. Nous expliquons ensuite que, contrairement à ce qu'ils prétendent, les auteurs n'utilisent pas la distribution du délai de prédiction (\emph{lead time}). Finalement, nous montrons que leur algorithme ne change pas de politique au moment optimum, et nous indiquons que nous avons présenté l'algorithme optimal dans un précédent rapport de recherche.

Nous nous intéressons au routage des communications dans un processeur multi-cœur (CMP). Le but est de trouver un routage valide, c'est-à-dire un routage dans lequel la quantité de données routée entre deux cœurs voisins ne dépasse pas la bande passante maximale, et tel que la puissance dissipée dans les communications est minimale. Nous nous positionnons au niveau système : nous supposons que des applications, sous forme de graphes de tâches, s'exécutent sur le CMP, chaque tâche étant déjà assignée à un cœur. Nous avons donc un ensemble de communications à router entre les cœurs. Nous utilisons un modèle classique, dans lequel la puissance dissipée par un lien de communication est la somme d'une partie statique et d'une partie dynamique, cette dernière dépendant de la fréquence du lien. Cette fréquence est ajustable et proportionnelle à la bande passante. La politique la plus utilisée est le routage XY : chaque communication est en- voyée horizontalement, puis verticalement. Cependant si nous nous autorisons à utiliser les chemins de Manhattan entre la source et la destination, la puissance dissipée peut être considérablement réduite. De plus, il est parfois possible de trouver une solution, alors qu'il n'en existait pas avec un routage XY. Dans ce papier, nous comparons le routage XY et le routage via des chemins de Manhattan, aussi bien d'un point de vue théorique que d'un point de vue pratique. Nous considérons deux variantes du routage par chemins de Manhattan : dans un routage à chemin unique, un seul chemin peut être utilisé pour chaque communication, tandis que le routage à chemin multiples nous permet d'éclater une communication et de lui faire emprunter plusieurs routes. Nous établissons la NP-complétude du problème consistant à trouver un routage Manhattan qui minimise la puissance dissipée, exhibons la borne supérieure minimale du ratio entre la puissance dissipée par un routage XY et celle dissipée par un routage Manhattan, et pour terminer, nous effectuons des simulations pour étudier les ...

Nous nous intéressons au routage des communications dans un processeur multi-cœur (CMP). Le but est de trouver un routage valide, c'est-à-dire un routage dans lequel la quantité de données routée entre deux cœurs voisins ne dépasse pas la bande passante maximale, et tel que la puissance dissipée dans les communications est minimale. Nous nous positionnons au niveau système : nous supposons que des applications, sous forme de graphes de tâches, s'exécutent sur le CMP, chaque tâche étant déjà assignée à un cœur. Nous avons donc un ensemble de communications à router entre les cœurs. Nous utilisons un modèle classique, dans lequel la puissance dissipée par un lien de communication est la somme d'une partie statique et d'une partie dynamique, cette dernière dépendant de la fréquence du lien. Cette fréquence est ajustable et proportionnelle à la bande passante. La politique la plus utilisée est le routage XY : chaque communication est en- voyée horizontalement, puis verticalement. Cependant si nous nous autorisons à utiliser les chemins de Manhattan entre la source et la destination, la puissance dissipée peut être considérablement réduite. De plus, il est parfois possible de trouver une solution, alors qu'il n'en existait pas avec un routage XY. Dans ce papier, nous comparons le routage XY et le routage via des chemins de Manhattan, aussi bien d'un point de vue théorique que d'un point de vue pratique. Nous considérons deux variantes du routage par chemins de Manhattan : dans un routage à chemin unique, un seul chemin peut être utilisé pour chaque communication, tandis que le routage à chemin multiples nous permet d'éclater une communication et de lui faire emprunter plusieurs routes. Nous établissons la NP-complétude du problème consistant à trouver un routage Manhattan qui minimise la puissance dissipée, exhibons la borne supérieure minimale du ratio entre la puissance dissipée par un routage XY et celle dissipée par un routage Manhattan, et pour terminer, nous effectuons des simulations pour étudier les performances de nos heuristiques de routage Manhattan.