Mobile devices are often expected to perform computational tasks that may be beyond their processing or battery capability. Cloud computing techniques have been proposed as a means to offload a mobile device's computation to more powerful resources. In this thesis, we consider the case where powerful computing resources are made available by utilizing vehicles. These vehicles can be repositioned in real time to receive computational tasks from user-carried devices. They can be either equipped with rugged high-performance computers to provide both computation and communication service, or they can be simple message ferries that facilitate communication with a more powerful computing resource. These scenarios find application in challenged environments and may be used in a military or disaster relief settings. It is further enabled by increasing feasibility of (i) constructing a Mobile High Performance Computer (MHPC) using rugged computer hardware with form factors that can be deployed in vehicles and (ii) Message Ferries (MF) that provide communication service in disruption tolerant networks. By analogy to prior work on message ferries and data mules, one can refer to the use of our first schema, MHPCs, as computational ferrying. After illustrating and motivating the computational ferrying concept, we turn our attention into the challenges facing such a deployment. These include the well known challenges of operating an opportunistic and intermittently connected network using message ferries -- such as devising an efficient mobility plan for MHPCs and developing techniques for proximity awareness. In this thesis, first we propose an architecture for the system components to be deployed on the mobile devices and the MHPCs. We then focus on defining and solving the MHPC movement scheduling problem with sufficient generality to describe a number of plausible deployment scenarios. After thorough examination of the MHPC concepts, we propose a scheme in which MHPCs are downgraded to be simple MFs that instead provide communication to a stationary HPC with powerful computing resources. Similar to the MPHCs, we provide a framework for this problem and then describe heuristics to solve it. We conduct a number of experiments that provide an understanding of how the performance of the system using MHPCs or MFs is affected by various parameters. We also provide a thorough comparison of the system in the dimensions of Computation on the Move and Controlling the Mobility.

Recent increase in performance of High Performance Computing (HPC) systems has been followed by even higher increase in power consumption. Power draw of modern supercomputers leads to very high operating costs and reliability concerns. Furthermore, it has negative consequences on the environment. Accordingly, over the last decade there have been many works dealing with power/energy management in HPC systems. Since CPUs accounts for a high portion of the total system power consumption, our work aims at CPU power reduction. Dynamic Voltage Frequency Scaling (DVFS) is a widely used technique for CPU power management. Running an application at lower frequency/voltage reduces its power consumption. However, frequency scaling should be used carefully since it has negative effects on the application performance. We argue that the job scheduler level presents a good place for power management in an HPC center having in mind that a parallel job scheduler has a global overview of the entire system. In this thesis we propose power-aware parallel job scheduling policies where the scheduler determines the job CPU frequency, besides the job execution order. Based on the goal, the proposed policies can be classified into two groups: energy saving and power budgeting policies. The energy saving policies aim to reduce CPU energy consumption with a minimal job performance penalty. The first of the energy saving policies assigns the job frequency based on system utilization while the other makes job performance predictions. While for less loaded workloads these policies achieve energy savings, highly loaded workloads suffer from a substantial performance degradation because of higher job wait times due to an increase in load caused by longer job run times. Our results show higher potential of the DVFS technique when applied for power budgeting. The second group of policies are policies for power constrained systems. In contrast to the systems without a power limitation, in the case of a given power budget the DVFS technique even improves overall job performance reducing the average job wait time. This comes from a lower job power consumption that allows more jobs to run simultaneously. The first proposed policy from this group assigns CPU frequency using the job predicted performance and current power draw of already running jobs. The other power budgeting policy is based on an optimization problem which solution determines the job execution order, as well as power distribution among jobs selected for execution. This policy fully exploits available power and leads to further performance improvements. The last contribution of the thesis is an analysis of the DVFS technique potential for energyperformance trade-off in current and future HPC systems. Ongoing changes in technology decrease the DVFS applicability for energy savings but the technique still reduces power consumption making it useful for power constrained systems. In order to analyze DVFS potential, a model of frequency scaling impact on MPI application execution time has been proposed and validated against measurements on a large-scale system. This parametric analysis showed for which application/platform characteristic, frequency scaling leads to energy savings. / El aumento de rendimiento que han experimentado los sistemas de altas prestaciones ha venido acompañado de un aumento aún mayor en el consumo de energía. El consumo de los supercomputadores actuales implica unos costes muy altos de funcionamiento. Estos costes no tienen simplemente implicaciones a nivel económico sino también implicaciones en el medio ambiente. Dado la importancia del problema, en los últimos tiempos se han realizado importantes esfuerzos de investigación para atacar el problema de la gestión eficiente de la energía que consumen los sistemas de supercomputación. Dado que la CPU supone un alto porcentaje del consumo total de un sistema, nuestro trabajo se centra en la reducción y gestión eficiente de la energía consumida por la CPU. En concreto, esta tesis se centra en la viabilidad de realizar esta gestión mediante la técnica de Dynamic Voltage Frequency Scalingi (DVFS), una técnica ampliamente utilizada con el objetivo de reducir el consumo energético de la CPU. Sin embargo, esta técnica puede implicar una reducción en el rendimiento de las aplicaciones que se ejecutan, ya que implica una reducción de la frecuencia. Si tenemos en cuenta que el contexto de esta tesis son sistemas de alta prestaciones, minimizar el impacto en la pérdida de rendimiento será uno de nuestros objetivos. Sin embargo, en nuestro contexto, el rendimiento de un trabajo viene determinado por dos factores, tiempo de ejecución y tiempo de espera, por lo que habrá que considerar los dos componentes. Los sistemas de supercomputación suelen estar gestionados por sistemas de colas. Los trabajos, dependiendo de la política que se aplique y el estado del sistema, deberán esperar más o menos tiempo antes de ser ejecutado. Dado las características del sistema objetivo de esta tesis, nosotros consideramos que el Planificador de trabajo (o Job Scheduler), es el mejor componente del sistema para incluir la gestión de la energía ya que es el único punto donde se tiene una visión global de todo el sistema. En este trabajo de tesis proponemos un conjunto de políticas de planificación que considerarán el consumo energético como un recurso más. Estas políticas decidirán que trabajo ejecutar, el número de cpus asignadas y la lista de cpus (y nodos) sino también la frecuencia a la que estas cpus se ejecutarán. Estas políticas estarán orientadas a dos objetivos: reducir la energía total consumida por un conjunto de trabajos y controlar en consumo puntual de un conjunto puntual para evitar saturaciones del sistema en aquellos centros que puedan tener una capacidad limitada (permanente o puntual). El primer grupo de políticas intentará reducir el consumo total minimizando el impacto en el rendimiento. En este grupo encontramos una primera política que asigna la frecuencia de las cpus en función de la utilización del sistema y una segunda que calcula una estimación de la penalización que sufrirá el trabajo que va a empezar para decidir si reducir o no la frecuencia. Estas políticas han mostrado unos resultados aceptables con sistemas poco cargados, pero han mostrado unas pérdidas de rendimiento significativas cuando el sistema está muy cargado. Estas pérdidas de rendimiento no han sido a nivel de incremento significativo del tiempo de ejecución de los trabajos, pero sí de las métricas de rendimiento que incluyen el tiempo de espera de los trabajos (habituales en este contexto). El segundo grupo de políticas, orientadas a sistemas con limitaciones en cuanto a la potencia que pueden consumir, han mostrado un gran potencial utilizando DVFS como mecanismo de gestión. En este caso, comparado con un sistema que no incluya esta gestión, han demostrado mejoras en el rendimiento ya que permiten ejecutar más trabajos de forma simultánea, reduciendo significativamente el tiempo de espera de los trabajos. En este segundo grupo proponemos una política basada en el rendimiento del trabajo que se va a ejecutar y una segunda que considera la asignación de todos los recursos como un problema de optimización lineal. Esta última política es la contribución más importante de la tesis ya que demuestra un buen comportamiento en todos los casos evaluados. La última contribución de la tesis es un estudio del potencial de DVFS como técnica de gestión de la energía en un futuro próximo, en función de un estudio de las características de las aplicaciones, de la reducción de DVFS en el consumo de la CPU y del peso de la CPU dentro de todo el sistema. Este estudio indica que la capacidad de DVFS de ahorrar energía será limitado pero sigue mostrando un gran potencial de cara al control del consumo energético.

Le succès dans l'utilisation de méthodes exactes d’optimisation combinatoire pour des problèmes de grande taille est encore limité à certains problèmes ou à des classes spécifiques d'instances de problèmes. Une approche alternative consiste soit à utiliser des métaheuristiques ou des matheuristiques qui reposent en partie sur des méthodes exactes. Dans le contexte de l'optimisation combinatoire, nous nous intéressons des heuristiques permettant de choisir les heuristiques appliquées au problème traité. Dans cette thèse, nous nous concentrons sur l'optimisation à l’aide d’hyperheuristiques pour des problèmes logistiques. Nous proposons un cadre hyperheuristique qui effectue une recherche dans l'espace des algorithmes heuristiques et apprend comment changer l'heuristique courante systématiquement tout au long du processus de telle sorte qu'une bonne séquence d'heuristiques permet d’obtenir des solutions de haute qualité. Nous étudions plus particulièrement deux problèmes en logistique pour lesquels nous proposons des HHs: un problème de planification d’interventions sur des puits de forage et un problème conjoint de localisation de hubs et de routage. Ensuite, nous comparons les performances de plusieurs HH décrites dans la littérature pour le second problème abordé reposant sur différentes méthodes de sélection heuristique telles que la sélection aléatoire, la fonction de choix, une approche de Q-Learning et un algorithme de colonie de fourmis. Les résultats numériques prouvent l'efficacité de HHs pour les deux problèmes traités, et la pertinence d'inclure l'information venant d’une relaxation de Lagrangienne pour le deuxième problème. / Success in using exact methods for large scale combinatorial optimization is still limited to certain problems or to specific classes of instances of problems. The alternative way is either using metaheuristics or matheuristics that rely on exact methods in some ways. In the context of combinatorial optimization, we are interested in heuristics to choose heuristics invoked to solve the addressed problem. In this thesis, we focus on hyperheuristic optimization in logistic problems. We focus on proposing a hyperheuristic framework that carries out a search in the space of heuristic algorithms and learns how to change the incumbent heuristic in a systematic way along the process in such a way that a good sequence of heuristics produces high quality solutions. We propose HHs for two problems in logistics: the workover rig scheduling problem and the hub location routing problem. Then, we compare the performances of several HHs described in the literature for the latter problem, which embed different heuristic selection methods such as a random selection, a choice function, a Q-Learning approach, and an ant colony based algorithm. The computational results prove the efficiency of HHs for the two problems in hand, and the relevance of including Lagrangian relaxation information for the second problem.