Search

In this paper, we design and analyze strategies to replicate the execution of an application on two different platformssubject to failures, using checkpointing on a shared stable storage. We derive the optimal pattern size~$W$for a periodic checkpointing strategy where both platforms concurrently try and execute $W$ units of work before checkpointing. The first platform that completes its pattern takes a checkpoint,and the other platform interrupts its execution to synchronize from that checkpoint.We compare this strategy to a simpler on-failure checkpointing strategy, where a checkpoint is taken by one platformonly whenever the other platform encounters a failure. We use first or second-order approximations to computeoverheads and optimal pattern sizes, and show through extensive simulationsthat these models are very accurate. The simulations show the usefulness of a secondary platform to reduce execution time, even when the platforms have relatively different speeds: in average, over a wide range of scenarios, the overhead is reduced by $30\%$.The simulations alsodemonstrate that the periodic checkpointing strategy is globally more efficient, unless platform speeds are quite close.; Ce rapport propose un modèle et une étude analytique de deux stratégies de réplication, combinée avec des prises de checkpoint, sur plates-formes hétérogènes. L'application s'exécute sur deux plates-formes de vitesses et taux de fautes différents, et qui partagent unespace de stockage stable. Nous déterminons la taille optimale du travail $W$ pour une stratégie périodique où les deux plates-formes tentent d'exécuter $W$ unités de travail avant de prendre un checkpoint. La première plate-forme qui réussit prend ce checkpoint, et l'autre s'interromptet se resynchronise avec la première à partir du checkpoint. Nous comparons cette stratégie avec une stratégie plus simple, dite de checkpoint-sur-faute, où un checkpoint n'est pris sur une plate-forme que quand l'autre est sujette à une faute. Nous calculons des approximations du premier et deuxième ordre pour la taille optimale W, et montrons par simulationque celles-ci sont très précises. Les simulations montrent l'utilité d'une seconde plate-forme, même lorsqu'elle a une vitesse relativement différente, puisqu'on gagne 30% en moyenne. En- n, la stratégie périodique est la plus efficace globalement, sauf si les deux plates-formes sont des vitesses très proches.

In this paper, we study the problem of finding optimal mappings for several independent but concurrent workflow applications, in order to optimize performance-related criteria together with energy consumption. Each application consists in a linear chain graph with several stages, and processes successive data sets in pipeline mode, from the first to the last stage. The problem is to decide which processors to enroll, at which speed (or mode) to use them, and which stages they should execute. There is a clear trade-off to reach, since running faster and/or more processors leads to better performance, but energy consumption is then very high. Energy savings can be achieved at the price of a lower performance, by reducing processor speeds or enrolling fewer resources. We study the problem complexity on different target execution platforms, ranking from fully homogeneous platforms to fully heterogeneous ones. We consider three mapping strategies: (i) one-to-one mappings, where a processor is assigned a single stage; (ii) interval mappings, where a processor may process an interval of consecutive stages of the same application; and (iii) general mappings, which are fully arbitrary, i.e., a processor may process stages of several distinct applications. Finally, we compare two different models for the computation of the latency, which is the time elapsed between the beginning and the end of the execution of a given data set: with the Path model, it is computed as the length of the path taken by this data set, while with the Wavefront model, each data set progresses concurrently within a period. For all platform types, all mapping strategies and both latency models, we establish the complexity of several multi-criteria optimization problems, whose objective functions combine period, latency and energy criteria. In particular, we exhibit instances where the problem is NP-hard with concurrent applications, while it can be solved in polynomial time for a single application, and instances whose problem complexity depends upon the latency model.