Nowadays crowd simulation is becoming more important in computer applications such as building evacuation planning, training, videogames, etc., presenting hundreds or thousands of agents navigating in virtual environments. Some of these applications need to run in real time in order to offer complete interaction with the user. Simulated crowds should seem natural and give a good looking impression to the user. The goal should be to produce both the best motion and animation, while minimizing the awkwardness of movements and eliminating or hiding visual artifacts. Achieving simulation, animation and rendering of crowds in real-time becomes thus a major challenge. Although each of these areas has been studied individually and improvements have been made in the literature, its integration in one real-time system is not straight forward. In the process of integrating animation, simulation and rendering of real time crowds, we need to assume some trade-offs between accuracy and quality of results. The main goal of this thesis is to work on those three aspects of a real-time crowd visualization (simulation, animation and rendering) seeking for possible speed-ups and optimizations allowing us to further increase the number of agents in the simulation, to then integrate them in a real-time system, with the maximum number possible of high quality and natural looking animated agents. In order to accomplish our goal we present new techniques to achieve improvements in each one of these areas: In crowd simulation we work on a multi-domain planning approach and on planning using footsteps instead of just root velocities and positions; in animation we focus on a framework to eliminate foot sliding artifacts and on synthesizing motions of characters to follow footsteps; in rendering we provide novel techniques based on per joint impostors. Finally we present a novel framework to progressively integrate different methods for crowd simulation, animation and rendering. The framework offers level-of-detail for each of these areas, so that as new methods are integrated they can be combined efficiently to improve performance. / Avui dia la simulació de multituds està agafant importància en aplicacions per computador, com la planificació d'evacuacions d'edificis, entrenament, videojocs, etc., presentant centenars o milers d'agents navegant en entorns virtuals. Algunes d'aquestes aplicacions necessiten ser executades en temps real per poder oferir una interacció completa amb l'usuari. Les multituds simulades han de resultar naturals i fer una bona impressió a l'usuari. L'objectiu ha de ser produir a la vegada tant els millors moviments com la millor animació, mentre es minimitzen els moviments estranys i s'eliminen o amaguen defectes visuals. Aconseguir la simulació, animació i visualització de multituds en temps real esdevé llavors un repte major. Encara que cadascuna d'aquestes àrees ha estat estudiada individualment i que s'han fet millores en la literatura, la seva integració en un sistema en temps real no és directa. En el procés d'integrar l'animació, la simulació i la visualització de multituds en temps real, necessitem assumir alguns equilibris entre la precisió i la qualitat dels resultats. El principal objectiu d'aquesta tesi és treballar en aquests tres aspectes de les multituds en temps real (simulació, animació i visualització) buscant possibles acceleracions i optimitzacions que ens permetin augmentar encara més el nombre d'agents simulats, per després integrar-los en un sistema en temps real, amb el màxim nombre possible de personatges d'alta qualitat i d'aspecte natural. Per aconseguir el nostre objectiu presentem noves tècniques per obtenir millores en cadascuna d'aquestes àrees: En la simulació de multituds treballem en una aproximació on es planifica en múltiples dominis, i en una planificació fent servir petjades en comptes de només velocitats i posicions dels personatges; en animació ens centrem en una arquitectura per a eliminar els problemes de lliscament dels peus i en sintetitzar els moviments d'un personatge perquè segueixi petjades; en visualització aportem noves tècniques basades en impostors per articulació. Finalment presentem una nova plataforma per a integrar progressivament diferents mètodes per a la simulació, animació i visualització de multituds. La plataforma ofereix nivells de detall per a cadascuna d'aquestes àrees, de manera que a mesura que s'integrin nous mètodes, aquests puguin ser combinats de forma eficient per a millorar el rendiment.

Increasingly High-Performance Computing (HPC) applications run on heterogeneous multi-core platforms. The basic reason of the growing popularity of these architectures is their low power consumption, and high throughput oriented nature. However, this throughput imposes a requirement on the data to be supplied in a high throughput manner for the multi-core system. This results in the necessity of an efficient management of on-chip and off-chip memory data transfers, which is a significant challenge. Complex regular and irregular memory data transfer patterns are becoming widely dominant for a range of application domains including the scientific, image and signal processing. Data accesses can be arranged in independent patterns that an efficient memory management can exploit. The software based approaches using general purpose caches and on-chip memories are beneficial to some extent. However, the task of efficient data management for the throughput oriented devices could be improved by providing hardware mechanisms that exploit the knowledge of access patterns in memory management and scheduling of accesses for a heterogeneous multi-core architecture. The focus of this thesis is to present architectural explorations for a novel access pattern-based multi-core memory architecture. In general, the thesis covers four main aspects of memory system in this research. These aspects can be categorized as: i) Uni-core Memory System for Regular Data Pattern. ii) Multi-core Memory System for Regular Data Pattern. iii) Uni-core Memory System for Irregular Data Pattern. and iv) Multi-core Memory System for Irregular Data Pattern. / Les aplicacions de computació d'alt rendiment (HPC) s'executen cada vegada més en plataformes heterogènies de múltiples nuclis. El motiu bàsic de la creixent popularitat d'aquestes arquitectures és el seu baix consum i la seva natura orientada a alt throughput. No obstant, aquest thoughput imposa el requeriment de que les dades es proporcionin al sistema també amb alt throughput. Això resulta en la necessitat de gestionar eficientment les trasferències de memòria (dins i fora del chip), un repte significatiu. Els patrons de transferències de memòria regulars però complexos així com els irregulars són cada vegada més dominants per a diversos dominis d'aplicacions, incloent el científic i el processat d'imagte i senyals. Aquests accessos a dades poden ser organitzats en patrons independents que un gestor de memòria eficient pot explotar. Els mètodes basats en programari emprant memòries cau de propòsit general i memòries al chip són beneficioses fins a cert punt. No obstant, la tasca de gestionar eficientment les transferències de dades per a dispositius orientats a throughput pot ser millorada oferint mecanismes hardware que explotin el coneixement dels patrons d'accés de les aplicacions, així com la planificació dels accessos a una arquitectura de múltiples nuclis. Aquesta tesis està enfocada a explorar una arquitectura de memòria novedosa per a processadors de múltiples nuclis, basada en els patrons d'accés. En general, la recerca de la tesis cobreix quatres aspectes principals del sistema de memòria. Aquests aspectes són: i) sistema de memòria per a un únic nucli amb patrons regulars, ii) sistema de memòria per a múltiples nuclis amb patrons regulars, iii) sistema de memòria per a un únic nucli amb patrons irregulars, iv) sistema de memòria per a múltiples nuclis amb patrons irregulars.

Network interference of nearby jobs has been recently identified as the dominant reason for the high performance variability of parallel applications running on High Performance Computing (HPC) systems. Typically, HPC systems are dynamic with multiple jobs coming and leaving in an unpredictable fashion, sharing simultaneously the system interconnection network. In such environment contention for network resources is causing random stalls in the progress of application execution degrading application's performance. Eliminating interactions between jobs is the key for guaranteeing both high performance and performance predictability of applications. These interactions are determined by the job location in the system. Upon arriving to the system, the job is allocated the computing and network resources by resource managers. Based on the job size requirements, the job scheduler finds a set of available computing nodes. In addition, the subnet manager determines the allocation of the network resources such as paths between nodes, virtual lanes, link bandwidth. Typically, resource managers are mainly focused on increasing utilization of the resources while neglecting job interactions. In this thesis, we propose techniques for both, job scheduler and subnet manager, able to mitigate job interactions: 1) a job scheduling policy that reduces the node fragmentation in the system, and 2) a quality-of-service (QoS) policy based on a characterization of job's network load; this policy is relaying on the virtual lanes mechanism provided by modern interconnection network (e.g. InfiniBand). In order to evaluate our job scheduling policy we use a simulator developed for this thesis that takes as an input the job scheduler log from a production HPC system. This simulator performs the node allocation for the jobs from the log. The proposed QoS policy is evaluated using a flit-level network simulator that is able to replay multiple traces from real executions of MPI applications. Experimental results show that the proposed job scheduling policy leads to few jobs sharing network resources and thus having fewer job's interactions while the QoS policy is able to effectively reduce the degradation from the remaining job's interactions. These two software techniques are complementary and could be used together without additional hardware.

In the last decades, the computing technology experienced tremendous developments. For instance, transistors' feature size shrank to half at every two years as consistently from the first time Moore stated his law. Consequently, number of transistors and core count per chip doubles at each generation. Similarly, petascale systems that have the capability of processing more than one billion calculation per second have been developed. As a matter of fact, exascale systems are predicted to be available at year 2020. However, these developments in computer systems face a reliability wall. For instance, transistor feature sizes are getting so small that it becomes easier for high-energy particles to temporarily flip the state of a memory cell from 1-to-0 or 0-to-1. Also, even if we assume that fault-rate per transistor stays constant with scaling, the increase in total transistor and core count per chip will significantly increase the number of faults for future desktop and exascale systems. Moreover, circuit ageing is exacerbated due to increased manufacturing variability and thermal stresses, therefore, lifetime of processor structures are becoming shorter. On the other side, due to the limited power budget of the computer systems such that mobile devices, it is attractive to scale down the voltage. However, when the voltage level scales to beyond the safe margin especially to the ultra-low level, the error rate increases drastically. Nevertheless, new memory technologies such as NAND flashes present only limited amount of nominal lifetime, and when they exceed this lifetime, they can not guarantee storing of the data correctly leading to data retention problems. Due to these issues, reliability became a first-class design constraint for contemporary computing in addition to power and performance. Moreover, reliability even plays increasingly important role when computer systems process sensitive and life-critical information such as health records, financial information, power regulation, transportation, etc. In this thesis, we present several different reliability designs for detecting and correcting errors occurring in processor pipelines, L1 caches and non-volatile NAND flash memories due to various reasons. We design reliability solutions in order to serve three main purposes. Our first goal is to improve the reliability of computer systems by detecting and correcting random and non-predictable errors such as bit flips or ageing errors. Second, we aim to reduce the energy consumption of the computer systems by allowing them to operate reliably at ultra-low voltage level. Third, we target to increase the lifetime of new memory technologies by implementing efficient and low-cost reliability schemes.

Cotutela Universitat Politècnica de Catalunya i Alpen-Adria-Universität Klagenfurt, Austria / Rather than adapt human behavior to suit a life surrounded by computerized systems, is it possible to adapt the systems to suit humans? Mark Weiser called for this fundamental change to the design and engineering of computer systems nearly twenty years ago. We believe it is possible and offer a series of related theoretical developments and practical experiments designed in an attempt to build a system that can meet his challenge without resorting to black box design principles or Wizard of Oz protocols. This culminated in a trial involving 32 participants, each of whom used two different multimodal interactive techniques, based on our novel interaction paradigm, to intuitively control nine distributed devices in a smart home setting. The theoretical work and practical developments have led to our proposal of seven contributions to the state of the art.

As distributed electronic systems grow to include thousands of components, from grid to peer-to-peer nodes, from (Semantic) Web services to web-apps to computation in the cloud, governance of such systems is becoming a real challenge. Modern approaches ensuring appropriate individual entities' behaviour in distributed systems, which comes from multi-agent systems (MAS) research, use norms (or regulations or policies) and/or communication protocols to express a different layer of desired or undesired states. From the individuals perspective, an agent needs to be able to function in an environment where norms act as behavioural restrictions or guidelines as to what is appropriate, not only for the individual but also for the community. In the literature the concept of norms has been defined from several perspectives: as a rule or standard of behaviour shared by members of a social group, as an authoritative rule or standard by which something is judged, approved or disapproved, as standards of right and wrong, beauty and ugliness, and truth and falsehood, or even as a model of what should exist or be followed, or an average of what currently does exist in some context. Currently there exist in the literature: 1) some treatments that formally connect the deontic aspects of norms with their operationalisation; 2) some treatments that properly distinguish between abstract norms and their (multiple) instantiations at runtime; 3) little work that formalises the operational semantics in a way that ensures flexibility in their translation to actual implementations while ensuring unambiguous interpretations of the norms; 4) little work that is suitable for both institutional-level norm monitoring and individual agent norm-aware reasoning to ensure that both are aligned; 5) few works that explore how the norms may affect the decision making process of an agent when the process includes planning mechanisms at runtime for means-ends reasoning. However, currently there is no work that includes both a formalism and an implementation covering 1-5 altogether. This thesis presents work towards the above five areas. We give a proposal to bridge the gap between a single norm formalisation and the actual mechanisms used for norm-aware planning, in order to create a normative practical reasoning mechanism. One way to do this is by reducing deontic-based norm definitions to temporal logic formulas which, in turn, can be translated into planning operational semantics. Based on these semantics, we create a mechanism to support practical normative reasoning that can be used by agents to produce and evaluate their plans. We construct a norm-oriented agent that takes into consideration operationalised norms during the plan generation phase, using them as guidelines to decide the agents future action path. To make norms influence plan generation, our norm operational semantics is expressed as an extension of the planning domain, acting as a form of temporal restrictions over the trajectories (plans) computed by the planner. We consider two approaches to do so. One implementing the semantics by using planning with constraints through paths and the other by directly translating the norms into domain knowledge to be included into the planning domain. We explore a scenario based on traffic laws in order to demonstrate the usability of our proposal. We also show how our normative frameworks are successfullyintegrated into an existing BDI agent implementation, 2APL. For each approach taken, we present quantitative experimental results and illustrate the opportunities for further research. / La gestión de sistemas electrónicos distribuidos se está convirtiendo en un auténtico reto a medida que dichos sistemas crecen incluyendo múltiples componentes, desde nodos grid a peer-to-peer, servicios de la Web semántica, aplicaciones web o computación en la nube. Los enfoques modernos que aseguran un comportamiento adecuado de las entidades individuales en sistemas distribuidos, y que provienen de la investigación en sistemas multi-agentes (MAS), utilizan normas (o regulaciones o políticas) para expresar un nivel diferente de estados deseados o no deseados. Desde la perspectiva del individuo, un agente necesita poder funcionar en un entorno donde las normas actúen como restricciones o directrices de comportamiento respecto a lo que es apropiado,no únicamente para el individuo sino para la comunidad en su conjunto. En la literatura el concepto de norma se ha definido desde varias perspectivas: como una regla o estándar de comportamiento compartida por los miembros de un grupo social, como estándar de lo correcto o incorrecto, belleza o fealdad, o incluso, como un modelo que debería existir o ser seguido. En la actualidad se pueden encontrar en la literatura: 1) trabajos que conectan formalmente los aspectos deónticos de las normas con su operacionalización; 2) trabajos que distinguen adecuadamente entre normas abstractas y sus (múltiples) instanciaciones en tiempo de ejecución; 3) algún ejemplo que formaliza las semánticas operacionales de manera que se asegura la flexibilidad en su traducción a implementaciones garantizando a su vez interpretaciones no ambiguas de las normas; 4) algún trabajo que se adecúa tanto a la monitorización de normas a nivel institucional como al razonamiento basado en normas a nivel de los agentes individuales y que asegura que ambos están alineados; 5) algún trabajo que explora como las normas pueden afectar al proceso de toma de decisiones de un agente cuando el proceso incluye mecanismos de planificación en tiempo real para un razonamiento medios-fines. Sin embargo, actualmente no existe ningún enfoque que incluya formalismos e implementaciones abordando los 5 puntos al mismo tiempo. La presente tesis propone contribuciones en las cinco áreas mencionadas. Se presenta una propuesta para establecer un enlace entre la formalización de una norma y los mecanismos utilizados en la planificación basada en normas con el objetivo de crear un mecanismo de razonamiento práctico normativo. Una forma de conseguirlo es mediante la reducción de las definiciones de normas basadas en deóntica a fórmulas de lógica temporal que, a su vez, pueden ser traducidas a semánticas operacionales de planificación. Basándose en estas semánticas, se ha creado un mecanismo para dar soporte al razonamiento normativo práctico que puede ser utilizado por los agentes para producir y evaluar sus planes. Se ha construido un agente orientado a normas que tiene en consideración las normas operacionalizadas durante la fase de generación de planes, utilizándolas como directrices para decidir el futuro curso de acción del agente. Nuestras semánticas operacionales de normas se expresan como una extensión del dominio de la planificación, actuando como una forma de restricciones temporales sobre las trayectorias (planes) computadas por el planificador. Se han considerado dos enfoques para realizarlo. Uno, implementando las semánticas utilizando planificación con restricciones a través de caminos y otro, traduciendo directamente las normas en conocimiento del dominio que se incluirá en el dominio de planificación. Se explora un escenario basado en normas de circulación de tráfico para demostrar la usabilidad de nuestra propuesta. Se mostrará también como nuestro marco normativo se integra satisfactoriamente en una implementación existente de agentes BDI, 2APL. Para cada enfoque considerado, se presentan resultados experimentales cuantitativos y se ilustran las oportunidades para futuros trabajos de investigación. / A mesura que els sistemes electrònics distribuïts creixen per incloure milers de components,des de nodes grid a peer-to-peer fins a serveis de la Web semàntica, aplicacions web o computació al núvol, la gestió d’aquests sistemes s’està convertint en un autèntic repte. Els enfocs moderns que asseguren el comportament apropiat de lesentitats individuals en sistemes distribuïts, que prové de la recerca en sistemes multiagents, utilitzen normes (o regulacions o polítiques) i/o protocols de comunicació perexpressar una capa diferent d’estats desitjats o no desitjats. Des de la perspectiva de l’individu, un agent necessita poder funcionar en un entorn on les normes actuïn coma restriccions de comportament o guies respecte al que és apropiat, no només per al individu sinó per a la comunitat.En la literatura el concepte de normes s’ha tractat des de diferents perspectives: com una regla o estàndard de comportament compartida pels membres d’un grup social, com una regla o estàndard autoritari pel qual alguna cosa és jutjada, aprovada o desaprovada,com estàndard del correcte i del incorrecte, bellesa i lletjor, veritat i falsedat, o inclús com un model del que hauria d’existir o ser seguit, o com una mitjana del que actualment existeix en un context donat. Actualment trobem en la literatura:1) alguns tractaments que connecten formalment els aspectes deòntics de les normes amb la seva operacionalització; 2) alguns tractaments que distingeixen adequadament entre normes abstractes i les seves (múltiples) instanciacions en temps real; 3) alguns exemples que formalitzen les semàntiques operacionals de manera que asseguren flexibilitaten la seva traducció a implementacions garantint interpretacions no ambigües de les normes; 4) alguns treballs adequats per a la monitorització de normes a nivell institucional i per al raonament basat en normes en agents individuals assegurant que ambdós estan alineats; 5) alguns treballs que exploren com les normes poden afectar el procés de presa de decisions d’un agent quan el procés inclou mecanismes de planificació en temps real per a raonament mitjans-finalitats. D’altra banda, actualment noexisteix cap enfoc que inclogui formalismes i implementacions cobrint els punts 1-5 a la vegada.Aquesta tesi presenta contribucions en les cinc àrees esmentades. Presentem una proposta per establir un enllaç entre la formalització d’una norma i els mecanismes emprats en la planificació basada en normes per tal de crear un mecanisme de raonament pràctic normatiu. Una manera d’aconseguir-ho és reduint les definicions de normes deòntiques a fórmules de lògica temporal les quals poden ser traduïdes asemàntiques de planificació operacional. Basant-nos en aquestes semàntiques, hem creat un mecanisme per donar suport al raonament normatiu pràctic que pot ser emprat per agents per produir i avaluar els seus plans. Hem construït un agent orientat a normes que pren en consideració durant la fase de generació de plans les normes operacionalitzades, utilitzant-les com a guia per decidir el futur curs d’acció de l’agent.Per tal de fer que les normes influenciïn la generació de plans, les nostres semàntiques operacionals de normes s’expressen com una extensió del domini de la planificació,actuant com una mena de restriccions temporals sobre les trajectòries (plans) computadespel planificador. Considerem dos enfocs per dur-ho a terme. Un implementant les semàntiques emprant planificació amb restriccions per mitjà de camins i l’altre traduint directament les normes en coneixement del domini a ser inclòs en el domini de planificació. Explorem un escenari basat en les normes de circulació de tràfic per demostrar la usabilitat de la nostra proposta. Mostrarem també com el nostre marc normatiu s’integra satisfactòriament en una implementació existent d’agentBDI, 2APL. Per cada enfoc considerat, presentem resultats experimentals quantitatius i il.lustrem les oportunitats per treballs de recerca futurs.

The last decade has witnessed unprecedented changes in parallel and distributed infrastructures. Due to the diminished gains in processor performance from increasing clock frequency, manufacturers have moved from uniprocessor architectures to multicores; as a result, clusters of computers have incorporated such new CPU designs. Furthermore, the ever-growing need of scienti c applications for computing and storage capabilities has motivated the appearance of grids: geographically-distributed, multi-domain infrastructures based on sharing of resources to accomplish large and complex tasks. More recently, clouds have emerged by combining virtualisation technologies, service-orientation and business models to deliver IT resources on demand over the Internet. The size and complexity of these new infrastructures poses a challenge for programmers to exploit them. On the one hand, some of the di culties are inherent to concurrent and distributed programming themselves, e.g. dealing with thread creation and synchronisation, messaging, data partitioning and transfer, etc. On the other hand, other issues are related to the singularities of each scenario, like the heterogeneity of Grid middleware and resources or the risk of vendor lock-in when writing an application for a particular Cloud provider. In the face of such a challenge, programming productivity - understood as a tradeo between programmability and performance - has become crucial for software developers. There is a strong need for high-productivity programming models and languages, which should provide simple means for writing parallel and distributed applications that can run on current infrastructures without sacri cing performance. In that sense, this thesis contributes with Java StarSs, a programming model and runtime system for developing and parallelising Java applications on distributed infrastructures. The model has two key features: first, the user programs in a fully-sequential standard-Java fashion - no parallel construct, API call or pragma must be included in the application code; second, it is completely infrastructure-unaware, i.e. programs do not contain any details about deployment or resource management, so that the same application can run in di erent infrastructures with no changes. The only requirement for the user is to select the application tasks, which are the model's unit of parallelism. Tasks can be either regular Java methods or web service operations, and they can handle any data type supported by the Java language, namely les, objects, arrays and primitives. For the sake of simplicity of the model, Java StarSs shifts the burden of parallelisation from the programmer to the runtime system. The runtime is responsible from modifying the original application to make it create asynchronous tasks and synchronise data accesses from the main program. Moreover, the implicit inter-task concurrency is automatically found as the application executes, thanks to a data dependency detection mechanism that integrates all the Java data types. This thesis provides a fairly comprehensive evaluation of Java StarSs on three di erent distributed scenarios: Grid, Cluster and Cloud. For each of them, a runtime system was designed and implemented to exploit their particular characteristics as well as to address their issues, while keeping the infrastructure unawareness of the programming model. The evaluation compares Java StarSs against state-of-the-art solutions, both in terms of programmability and performance, and demonstrates how the model can bring remarkable productivity to programmers of parallel distributed applications.

Current distributed systems that are capable of sharing resources in a distributed manner are experiencing an increase in their use and scope.This increased use in various application areas is largely due to the low cost of deployment and maintenance of a distributed environment, when compared to architectures like supercomputers. Then, many research efforts today are focused on providing solutions for distributed systems. It is essential that the solutions proposed allow for the sharing of a very large number of resources. This is a complex challenge to tackle since we do not want the solution to degrade as the number of system resources increase. It is also imperative that the solutions proposed, adapt to failures that occur both in the network and in the hardware and / or software that form the distributed system. This does not imply that the components should be universally available, but that the solution should be able to adapt to obtain the highest possible performance from all the components available at a given time. This is a more complex challenge. This thesis proposes a Resource Discovery Service (of services or resources) for large-scale distributed systems that are able to adapt to failures that occur in the system. By large scale systems, we mean systems that may be made up of hundreds, thousands or millions of machines. Failures refer to components that are not accessible through the network, components that are not working, or are overloaded, etc. It should be mentioned that in this work we found that in a real environment of geographically distributed resources, it is essential for service discovery to be fault tolerant. In one of the evaluations of our proposed discovery service, we chose 150 machines distributed geographically throughout Europe at random, without knowing if they were in a state of failure or not. We found that 24'67% of them were unavailable because they were in a failed state or because they failed during the evaluation of our service discovery. In this thesis, the proposed discovery service is based on an overlay that has a hypercube topology that interconnects nodes / intermediaries (brokers). The term overlay is used to describe a virtual network constructed at the application layer, above the level of TCP / IP. It acts as an intermediary component that mediates between service consumers (or clients) and service providers (or servers). / Actualmente los sistemas distribuidos, capaces de compartir de forma distribuida recursos están experimentando un incremento en su uso y en sus ámbitos de aplicación. Este aumento de uso y de ámbitos de aplicación es, en buena medida, debido al bajo coste que supone el despliegue y mantenimiento de un entorno distribuido, si se compara con arquitecturas como los supercomputadores. Así, múltiples esfuerzos de investigación se centran hoy en día en aportar soluciones para sistemas distribuidos.Por un lado, es esencial que las soluciones aportadas permitan compartir un número muy alto de recursos. Este es un reto complejo de abordar ya que plantea el problema de que la solución no se degrade a medida que el número de recursos del sistema aumente.Por otro lado, también es imprescindible que las soluciones aportadas se adapten a los fallos que se producen tanto en la red como en los componentes de hardware y/o software que forman el sistema distribuido. Esto no implica que los componentes deban estar universalmente disponibles, sino que la solución debe adaptarse para obtener el rendimiento más alto posible de los componentes disponibles en cada momento. Este es un reto aún más complejo.El trabajo de esta tesis propone un servicio de descubrimiento de servicios (o recursos) para sistemas distribuidos de gran escala, capaz de adaptarse a los fallos que se producen en el sistema. Por gran escala, se entiende sistemas formados por cientos, miles o millones de máquinas y por fallos, se entiende componentes que no son accesibles a través de la red, componentes que no están funcionando, que están sobrecargados, etc. Cabe comentar que en este trabajo se ha constatado que en un entorno real distribuido geográficamente es imprescindible que el servicio de descubrimiento se adapte a los fallos que se producen en el sistema. En una de las evaluaciones del servicio de descubrimiento propuesto, escogiendo 150 máquinas distribuidas geográficamente a lo largo de Europa, de forma aleatoria sin conocer si se encontraban en estado de fallo o no, un 24,67% de ellas fallaron, bien porque ya estaban en fallo o bien porque fallaron durante la evaluación del servicio de descubrimiento. El servicio de descubrimiento propuesto está basado en una red overlay con la topología de un hipercubo que interconecta nodos/intermediarios (brokers). El término overlay se usa como red virtual construida en la capa de aplicación, por encima del nivel de TCP/IP, y se entiende un intermediario como un componente que media entre consumidores de servicios (o clientes) y proveedores de servicios (o servidores).

Multi-GPU systems are widely used in High Performance Computing environments to accelerate scientific computations. This trend is expected to continue as integrated GPUs will be introduced to processors used in multi-socket servers and servers will pack a higher number of GPUs per node. GPUs are currently connected to the system through the PCI Express interconnect, which provides limited bandwidth (compared to the bandwidth of the memory in GPUs) and it often becomes a bottleneck for performance scalability. Current programming models present GPUs as isolated devices with their own memory, even if they share the host memory with the CPU. Programmers explicitly manage allocations in all GPU memories and use primitives to communicate data between GPUs. Furthermore, programmers are required to use mechanisms such as command queues and inter-GPU synchronization. This explicit model harms the maintainability of the code and introduces new sources for potential errors. The first proposal of this thesis is the HPE model. HPE builds a simple, consistent programming interface based on three major features. (1) All device address spaces are combined with the host address space to form a Unified Virtual Address Space. (2) Programs are provided with an Asymmetric Distributed Shared Memory system for all the GPUs in the system. It allows to allocate memory objects that can be accessed by any GPU or CPU. (3) Every CPU thread can request a data exchange between any two GPUs, through simple memory copy calls. Such a simple interface allows HPE to provide always the optimal implementation; eliminating the need for application code to handle different system topologies. Experimental results show improvements on real applications that range from 5% in compute-bound benchmarks to 2.6x in communication-bound benchmarks. HPE transparently implements sophisticated communication schemes that can deliver up to a 2.9x speedup in I/O device transfers. The second proposal of this thesis is a shared memory programming model that exploits the new GPU capabilities for remote memory accesses to remove the need for explicit communication between GPUs. This model turns a multi-GPU system into a shared memory system with NUMA characteristics. In order to validate the viability of the model we also perform an exhaustive performance analysis of remote memory accesses over PCIe. We show that the unique characteristics of the GPU execution model and memory hierarchy help to hide the costs of remote memory accesses. Results show that PCI Express 3.0 is able to hide the costs of up to a 10% of remote memory accesses depending on the access pattern, while caching of remote memory accesses can have a large performance impact on kernel performance. Finally, we introduce AMGE, a programming interface, compiler support and runtime system that automatically executes computations that are programmed for a single GPU across all the GPUs in the system. The programming interface provides a data type for multidimensional arrays that allows for robust, transparent distribution of arrays across all GPU memories. The compiler extracts the dimensionality information from the type of each array, and is able to determine the access pattern in each dimension of the array. The runtime system uses the compiler-provided information to automatically choose the best computation and data distribution configuration to minimize inter-GPU communication and memory footprint. This model effectively frees programmers from the task of decomposing and distributing computation and data to exploit several GPUs. AMGE achieves almost linear speedups for a wide range of dense computation benchmarks on a real 4-GPU system with an interconnect with moderate bandwidth. We show that irregular computations can also benefit from AMGE, too. / Los sistemas multi-GPU son muy comúnmente utilizados en entornos de computación de altas prestaciones para acelerar cálculos científicos. Esta tendencia continuará con la introducción de GPUs integradas en los procesadores de los servidores procesador y con una mayor densidad de GPUs por nodo. Las GPUs actualmente se contectan al sistema a través de una interconexión PCI Express, que provee un ancho de banda reducido (comparado con las memorias de las GPUs) y habitualmente se convierte en el cuello de botella para escalar el rendimiento. Los modelos de programación actuales exponen las GPUs como dispositivos aislados con su propia memoria, incluso si comparten la memoria física con la CPU. Los programadores manejan diferentes reservas en todas las memorias de GPU y usan primitivas para comunicar datos entre GPUs. Además, los programadores deben utilizar mecanismos como colas de comandos y sincronicación entre GPUs. Este modelo explícito empeora la programabilidad del código e introduce nuevas fuentes de errores potenciales. La primera propuesta de esta tesis es el modelo HPE. HPE construye una interfaz de programaci ón consistente basada en tres características principales. (1) Todos los espacios de direcciones de los dispositivos son combinados para formar un espacio de direcciones unificado. (2) Los programas usan un sistema asimétrico distribuido de memoria compartida para todas las GPUs del sistema, que permite declarar objetos de memoria que pueden ser accedidos por cualquier GPU o CPU. (3) Cada hilo de ejecución de la CPU puede lanzar un intercambio de datos entre dos GPUs a través de simples llamadas de copia de memoria. Esta interfaz simplificada permite a HPE usar la implementaci ón óptima; sinque la aplicación contemple diferentes topologías de sistema. Los resultados experimentales muestran mejoras en aplicaciones reales que van desde un 5% en aplicaciones limitadas por el cómputo a 2.6x aplicaciones imitadas por la comunicación. HPE implementa sofisticados esquemas de transferencia para dispositivos de E/S que proporcionan mejoras de rendimiento de 2.9x. La segunda propuesta de esta tesis es un modelo de programación basado en memoria compartida que aprovecha las nuevas capacidades acceso remoto de memoria de las GPUs para eliminar la comunicación explícita entre memorias de GPU. Este modelo convierte un sistema multi-GPU en un sistema de memoria compartida con características NUMA. Para validar la viabilidad del modelo realizamos un anlásis exhaustivo del rendimiento los accessos de memoria remotos sobre PCIe. Los resultados muestran que PCI Express 3.0 elimina los costes de hasta un 10% de accesos remotos, dependiendo en el patrón de acceso, mientras que guardar los accesos remotos en memorias cache tiene un gran inpacto en el rendimiento de las computaciones. Finalmente, presentamos AMGE, una interfaz de programación con soporte de compilación y un sistema que ejecuta, de forma automática, computaciones programadas para una única GPU en todas las GPUs del sistema. La interfaz de programación proporciona un tipo de datos para arreglos multidimensionales que permite una distribuci ón transparente y robusta de los datos en todas las memorias de GPU. El compilador extrae la información sobre la dimensionalidad de cada arreglo y puede determinar el patrón de acceso en cada dimensión de forma individual. El sistema utiliza, en tiempo de ejecución, la información del compilador para elegir la mejor descomposición de la computación y los datos para minimizar la comunicación entre GPUs y el uso de memoria. AMGE consigue mejoras de rendimiento que crecen de forma lineal con el número de GPUs para un amplio abanico de computaciones densas en un sistema real con 4 GPUs. También mostramos que las computaciones con patrones irregulares también se pueden beneficiar de AMGE.

El uso de los entornos virtualizados de ejecución se ha extendido a todos los ámbitos y, en particular, se está utilizando para el desarrollo y la ejecución de aplicaciones con un alto consumo de recursos. Por lo tanto, se hace necesario evaluar si estas plataformas ofrecen un rendimiento adecuado para este tipo de programas y si es posible aprovechar las características de estas plataformas para favorecer su ejecución.El objetivo principal de este trabajo ha sido ha sido demostrar que es posible explotar las características de los entornos virtualizados de ejecución para ofrecer a los programas una gestión de recursos que se adapte mejor a sus características.En este trabajo demostramos que el modelo de ejecución de este tipo de entornos, basado en la ejecución sobre máquinas virtuales, ofrece una nueva oportunidad para implementar una gestión específica de recursos, que permite mejorar el rendimiento de los programas sin renunciar a las numerosas ventajas de este tipo de plataformas como, por ejemplo, una portabilidad total del código de los programas.Para demostrar los beneficios de esta estrategia hemos seleccionado como caso de estudio la gestión del recurso memoria para los programas de cálculo científico en el entorno de ejecución de Java. Después de un análisis detallado de la influencia que tiene la gestión de memoria sobre este tipo de programas, hemos visto que añadir en el entorno de ejecución una política de prefetch de páginas que se adapte al comportamiento de los programas es una posible vía para mejorar su rendimiento.Por este motivo, hemos analizado detalladamente los requerimientos que debe cumplir esta política y cómo repartir las tareas entre los diferentes componentes del entorno de ejecución de Java para cumplir estos requerimientos.Como consecuencia, hemos diseñado una política de prefetch basada en la cooperación entre la máquina virtual y el sistema operativo. En nuestra propuesta, por un lado, las decisiones de prefetch se llevan a cabo utilizando todo el conocimiento que la máquina virtual tiene sobre el comportamiento dinámico de los programas y el conocimiento que el sistema operativo tiene sobre las condiciones de ejecución. Por otro lado, el encargado de llevar a cabo las decisiones de gestión es el sistema operativo, lo que garantiza la fiabilidad de la máquina.Además, esta estrategia es totalmente transparente al programador y al usuario, respetando el paradigma de portabilidad de los entornos de ejecución virtualizados.Hemos implementado y evaluado esta estrategia para demostrar los beneficios que ofrece al tipo de programas seleccionado y, aunque estos beneficios dependen de las características del programa, la mejora del rendimiento ha alcanzado hasta un 40% si se compara con el rendimiento obtenido sobre el entorno original de ejecución.