Aquest estudi descriu els principis de funcionament i validació d'un model d'ordinador de dinàmica de fluids computacional del procés de caiguda de neu sobre una orografia complexa. Es discretitza el domini espacial amb l'èmfasi principal sobre una topografia dificultosa que tendeix a produir volums deformes en la graella de càlcul. Es defineix una nova mesura de la deformació dels elements de la graella, i s'aplica per la discussió de diferents estratègies d'optimització de la graella per reduir el cost del càlcul paral·lel per ordinador de solucions a les equacions de transport de fluids de Navier-Stokes. Es dissenya un model per ordinador que resolgui les equacions Navier-Stokes per un fluid incompressible i torbulent. Es debat de l'eficiència de la caixa d'eines CFD. Es treballa el grau de connexió necessari entre les dues fases de neu i d'aire del fluid durant la modelització de la caiguda de neu mitjançant ordinador. S'implementa una metodologia Euler-Lagrangian de dos fluids. Es presenten aplicacions de caiguda de neu en relació amb la planificació de pistes d'esquí, la treta de neu de carreteres d'alta muntanya, i la planificació de la producció d'energia eòlica. / El estudio describe los principios de funcionamiento ya validación de un modelo para ordenador de dinámica de fluidos computacional del proceso de caída de nieve sobre una orografía compleja. Se discretea el dominio espacial con énfasis principal sobre una topografía dificultosa que tiende a producir volúmenes deformes en la cuadrícula de cálculo. Se define una nueva mesura de la deformación de los elementos de la cuadrícula, y se aplica en la discusión de diferentes estrategias de optimización de la cuadrícula para reducir el coste del cálculo paralelo por ordenador de soluciones de las ecuaciones de transporte de fluidos de Navier-Stokes. Se diseña un modelo por ordenador que resuelve las ecuaciones Navier-Stokes para un fluido incomprensible y turbulento. Se discute la eficiencia de la caja de herramientas CFD. Se trabaja el grado de conexión necesario entre las dos fases de nieve y de aire del fluido durante la modelización de la caída de nieve por ordenador. Se implementa una metodología Euler-Lagrangian de dos fluidos. Se presentan aplicaciones de caída de nieve en relación con la planificación de pistas de esquí, sacar la nieve de carreteras de alta momntaña, y la planificación de la producción de energía eólica. / This study describes the working principles and validation of a Computational Fluid Dynamics computer model of snowfall over a complex orography, for optimizing ski slope or other installations according to local weather patterns. The spatial domain is discretized, focusing on challenging topography that tends to produce deformed mesh volumes. A novel measure od mesh deformation is defined and applied to discuss different strategies of mesh optimization with the goal of facilitating parallel computer solutions of the Navier-Stokes fluid transport equations. A computer model is designed to solve the Navier-Stokes incompressible turbulent fluid equations. The efficiency of the CFD computational toolkit is discussed. The degree od coupling required between the snow – and air-phases of the fluid during the computer modeling of snowfall is discussed. A two-fluid (Euler-Lagrangian) methodology is implemented. Applications of such snowfall models are discussed in relation to ski-slope planning and high-altitude road snow clearing. An application of the model to wind energy production planning is presented.

Aquesta tesi adreça el problema de l'assignació eficient de recursos en sistemes de computació contributius. Aquest tipus de sistemes estan formats únicament per nodes no dedicats i requereixen de mecanismes adequats per a optimitzar l'ús dels recursos disponibles. La tesi proposa algorismes que optimitzen diferents aspectes d'aquest tipus de sistemes, com la disponibilitat de serveis compostos, el consum energètic originat per un servei o la distància entre qualsevol client i una rèplica en una topologia de xarxa coneguda. Aquests algorismes es basen en la combinació de meta-heurístiques i tècniques de simulació, cosa que permet que es puguin adaptar a situacions molt diverses i ser aprofitats pels sistemes contributius. / Esta tesis trata el problema de la asignación eficiente de recursos en sistemas de computación contributivos. Este tipo de sistemas estan compuestos de manera exclusiva por nodos no dedicados y requieren de mecanismos orientados a optimizar el uso de los recursos disponibles. La tesis propone algoritmos que optimizan diferentes aspectos de este tipo de sistemas, como la disponibilidad de servicios compuestos, el consumo energético de un servicio o la distancia entre cualquier cliente y una réplica en una topologia de red conocida. Estos algoritmos se basan en la combinación de metaheurísticas y tecnicas de simulación, cosa que permite que puedan adaptar su funcionamiento a situaciones muy diversas i así ser aprovechados por los sistemas contributivos. / This thesis addresses the efficient allocation problem in contributory computing systems. These systems are built only from non-dedicated nodes and require proper mechanisms in order to optimize the resource utilization. The thesis proposes algorithms that optimize different aspects of these systems, such as the availability of composite services, the energy consumptions of a service or the network distance between any client and a service replica in a known network topology. The algorithms are based in metaheuristics combines with simulation techniques, which allows them to adapt to very different scenarios and to be harnessed by contributory systems.

Un Multi-Cluster és un entorn de còmput distribuït en el que els diferents elements de còmput, agrupats en clústers, estàn repartits en diferents departaments d’una mateixa institució. La tasca de planificar aplicacions paral•leles a un Multi-Cluster és complexa, amb nombroses línies d’investigació obertes a l’actualitat. En primer lloc, la quantitat de recursos que han de ser gestionats pot ser elevada, amés que aquests poden ser heterogenis. En segon lloc, els diferents clústers estan connectats mitjançant un enllaç de xarxa, i si les aplicacions paral•leles no són assignades adequadament, el seu rendiment es degradarà si aquests enllaços es saturen. A la literatura, les estratègies més comuns avaluen les aplicacions de forma aïllada, sense tenir en compte els requisits de la resta d’aplicacions presents a la cua d’espera del sistema. Alguns estudis han conclòs que avaluar grups d’aplicacions permet prendre decisions de planificació que poden millorar el rendiment del conjunt d’aplicacions, i millorar la utilització dels recursos.Al present treball de tesi s’aborda el problema de la planificació on-line de múltiples aplicacions paral•leles a entorns Multi-Cluster heterogenis i amb co-assignació. Es proposen noves tècniques que tracten tant l’agrupació de les aplicacions com la seva assignació, considerant les característiques dels recursos del sistema, així com els requisits del grup d’aplicacions en quant al còmput i la comunicació. S’avaluen la complexitat i el rendiment de les tècniques proposades, comparant-les amb altres tècniques utilitzades a la literatura, usant traces d’entorns reals. Amés s’estudia la seva aplicabilitat a entorns reals i es presenten possibles línies de treball futur a considerar. / Un Multi-Cluster es un entorno de cómputo distribuido en el que los diferentes elementos de cómputo, agrupados en clusters, están repartidos en diferentes departamentos de una misma institución. La tarea de planificar aplicaciones paralelas en un Multi-Cluster es compleja, con numerosas líneas de investigación abiertas en la actualidad. En primer lugar, la cantidad de recursos que han de ser gestionados puede ser elevada, y además estos pueden ser heterogéneos. En segundo lugar, los diferentes clusters están conectados mediante un enlace de red, y si las aplicaciones paralelas no son asignadas adecuadamente, su rendimiento se degradará si estos enlaces se saturan. En la literatura, las estrategias más comunes evalúan las aplicaciones de forma aislada, sin tener en cuenta los requisitos de las otras aplicaciones presentes en la cola de espera del sistema. Algunos estudios han concluido que evaluar grupos de aplicaciones permite tomar decisiones de planificación que pueden mejorar el rendimiento del conjunto de aplicaciones, y mejorar la utilización de los recursos. En el presente trabajo de tesis se aborda el problema de la planificación on-line de múltiples aplicaciones paralelas en entornos Multi-Cluster heterogéneos y con co-asignación. Se proponen nuevas técnicas que tratan tanto la agrupación de las aplicaciones como su asignación, considerando las características de los recursos del sistema, así como los requisitos del grupo de aplicaciones en cuanto al cómputo y la comunicación. Se evalúan la complejidad y el rendimiento de las técnicas propuestas, comparándolas con otras técnicas utilizadas en la literatura, usando trazas de entornos reales. Se estudia además su aplicabilidad en entornos reales y se presentan posibles líneas de trabajo futuro a considerar. / A Multi-Cluster is a distributed computing environment in which the different computing elements, grouped in clusters, are spread across different departments of a same institution. The scheduling of parallel applications on a Multi-Cluster is complex. In first place, the amount of resources to be managed can be high, and also, those resource can be heterogeneous. Secondly, the different clusters are connected through a network link. If the parallel applications are not allocated correctly, its performance will be degraded if those links become saturated. On the literature, the most common strategies evaluate the applications in an isolated way, without taking into account the requirements of the other applications present on the system’s waiting queue. Some studies have concluded that to evaluate groups of applications allows taking scheduling decissions that could improve the performance of the set of applications, and to improve resource usage. On the present thesis work, the problem of on-line scheduling of multile parallel applications on heterogeneous Multi-Cluster environments with co-allocation, is addressed. New strategies are proposed which treat both application grouping and its allocation, as well as the set of applications processing and communication requierements. The complexity and the performance of the proposed strategies are evaluated, comparing them with other strategies from the literature, using real environment races. Furthermore, its applicability on real envionments is studied, and also possible future work to consider is presented.

Aquesta tesi adreça les mancances de la computació en núvol, els desktop grids i les xarxes d'igual a igual envers l'ús de recursos no dedicats per a computació de propòsit general mitjançant la proposta del model de computació contributiva, en que els usuaris contribueixen els seus recursos per tal de ser usats de manera col•lectiva. Una comunitat contributiva (agregació de recursos contribuïts) es pot utilitzar com una plataforma per a desplegar serveis, sent una alternativa a l'ús de grans centres de processament de dades. Aquests serveis fan possible la utilització de recursos sobrers de manera general, en comptes de limitar el seu ús a l'execució de tasques massives. Aquesta tesi desenvolupa el concepte de computació contributiva presentant un middleware per a la construcció de comunitats contributives i el desplegament de serveis en els recursos contribuïts. Aquest middleware, anomenat CoDeS, permet afegir recursos a la comunitat i desplegar serveis en ells, encarregant-se de mantenir els serveis disponibles utilitzant els recursos contribuïts. És auto-gestionat, descentralitzat, escalable, tolerant a fallades i pot tractar amb recursos heterogenis. / Esta tesis aborda las carencias de la computación en nube, los desktop grids y las redes de igual a igual con respecto al uso de recursos no dedicados para la computación de propósito general mediante la propuesta del modelo de computación contributiva, en que los usuarios contribuyen sus recursos para ser usados de manera colectiva. Una comunidad contributiva (agregación de recursos contribuidos) se puede utilizar como una plataforma para desplegar servicios, siendo una alternativa al uso de grandes centros de procesado de datos. Estos servicios hacen posible la utilización de recursos sobrantes de manera general, en lugar de limitar su uso a la ejecución de tareas masivas. Esta tesis desarrolla el concepto de computación contributiva presentando un middleware para la construcción de comunidades contributivas y el despliegue de servicios en los recursos contribuidos. Este middleware, llamado CoDeS, permite añadir recursos a la comunidad y desplegar servicios en ellos, encargándose de mantener los servicios disponibles utilizando los recursos contribuidos. Es auto-gestionado, descentralizado, escalable, tolerante a fallos y puede tratar con recursos heterogéneos. / This thesis addresses the lacks of cloud computing, desktop grids and peer-to-peer networks to use non-dedicated resources for general purpose computing by proposing the model of contributory computing, where users contribute their resources to be used collectively. A contributory community (aggregation of contributed resources) can be used as a platform to deploy services, as an alternative to large data centers. These services make it possible to use surplus resources in a general way, instead of limiting its use to the execution batch tasks. This thesis develops the concept of contributory computing by presenting a middleware for building contributory communities and deploying services on the contributed resources. This middleware, called CoDeS, allows resources to be put into the community and services deployed on it, and takes care of keeping the services available using the contributed resources. It is self-managed, decentralized, scalable, fault-tolerant and can deal with heterogeneous resources.

El objeto de estudio de esta investigación son las Redes Temáticas, concretamente las Redes Temáticas en la Web y su potencial para extraer datos objetivos de las corrientes de opinión que se generan en torno a un tema de discusión o controversia social. Esta investigación se estructura a través de cuatro objetivos: caracterizar los componentes de las redes temáticas; caracterizar y evaluar las herramientas para el análisis de redes temáticas en la web; diseñar un Sistema de Análisis de Redes Temáticas en la Web; y aplicar el Sistema de Análisis al caso de estudio de la Red Temática de la Transparencia en Chile. Como conclusiones, presentamos y caracterizamos los componentes de una red temática en la web: redes de hiperenlaces, actores y temas; analizamos los resultados de la evaluación de las herramientas que consideramos más adecuadas para el de análisis de redes temáticas en la web: IssueCrawler, SocSciBot, Webometric Analyst y VOSON; construimos un sistema de análisis dividido en tres fases: análisis de redes de hiperenlaces, análisis de actores y análisis de temas; y finalmente discutimos los resultados del análisis de la Red Temática de la Transparencia en Chile y los posibles desarrollos futuros de la investigación. / The object of study of this research are Issue Networks, namely the Issue networks that are active within the domain of the Internet and their potential to extract objective data from the opinion flows that are generated in regard to an issue of discussion or social controversy. This research is founded on four objectives: the characterization of the components of issue networks; the identification, description and evaluation of existing tools for the analysis of issue networks on the Internet; creation of an Analysis System of Issue Networks on the Internet; and, lastly, the application of the Analysis System to the case study of the Issue Network for Transparency in Chile. In conclusion, we introduce the characteristics of the components of an Issue Network on the Internet: hyperlinks, actors and issue networks; we present the results of the evaluation of the tools that we consider most suitable for the analysis of Issue Networks on the Internet: IssueCrawler, SocSciBot, Webometric Analyst and VOSON; we build an analysis system divided into three parts: network analysis of hyperlinks, stakeholder analysis and issue analysis; and finally we discuss the results of the analysis of the Issue Network for Transparency in Chile and the possible future developments of the investigation.

Frontiers of computational fluid dynamics (CFD) are constantly expanding and eagerly demanding more computational resources. Currently, we are experiencing an rapid evolution in the high performance computing systems driven by power consumption constraints. New HPC nodes incorporate accelerators that are used as math co-processors for increasing the throughput and the FLOP per watt ratio. On the other hand, multi-core CPUs have turned into energy efficient system-on-chip architectures. By doing so, the main components of the node are fused and integrated into a single chip reducing the energy costs. Nowadays, several institutions and governments are investing in the research and development of different aspects of HPC that could lead to the next generations of supercomputers. This initiatives have entitled the problem as the exascale challenge. This goal can only be achieved by incorporating major changes in computer architecture, memory design and network interfaces. The CFD community faces an important challenge: keep the pace at the rapid changes in the HPC resources. The codes and formulations need to be re-design in other to exploit the different levels of parallelism and complex memory hierarchies of the new heterogeneous systems. The main characteristics demanded to the new CFD software are: memory awareness, extreme concurrency, modularity and portability. This thesis is devoted to the study of a CFD algorithm re-factoring for the adoption of new technologies. Our application context is the solution of incompressible flows (DNS or LES) on unstructured meshes. The first approach was using GPUs for accelerating the Poisson solver, that is the most computational intensive part of our application. The positive results obtained in this first step motivated us to port the complete time integration phase of our application. This requires a major redesign of the code. We propose a portable implementation model for CFD applications. The main idea was substituting stencil data structures and kernels by algebraic storage formats and operators. By doing so, the algorithm was restructured into a minimal set of algebraic operations. The implementation strategy consisted in the creation of a low-level algebraic layer for computations on CPUs and GPUs, and a high-level user-friendly discretization layer for CPUs that is fully localized at the preprocessing stage where performance does not play an important role. As a result, at the time-integration phase the code relies only on three algebraic kernels: sparse-matrix-vector product (SpMV), linear combination of two vectors (AXPY) and dot product (DOT). Such a simple set of basic linear algebra operations naturally provides the desired portability to any computing architecture. Special attention was paid at the development of data structures compatibles with the stream processing model. A detailed performance analysis was studied in both sequential and parallel execution engaging up to 128 GPUs in a hybrid CPU/GPU supercomputer. Moreover, we tested the portable implementation model of TermoFluids code in the Mont-Blanc mobile-based supercomputer. The re-design of the kernels exploits a heterogeneous execution model using both computing devices CPU and GPU of the ARM-based nodes. The load balancing between the two computing devices exploits a tabu search strategy that tunes the workload distribution during the preprocessing stage. A comparison of the Mont-Blanc prototypes with high-end supercomputers in terms of the achieved net performance and energy consumption provided some guidelines of the behavior of CFD applications in ARM-based architectures. Finally, we present a memory aware auto-tuned Poisson solver for problems with one Fourier diagonalizable direction. This work was developed and tested in the BlueGene/Q Vesta supercomputer, and aims at demonstrating the relevance of vectorization and memory awareness for fully exploiting the modern energy efficient CPUs. / Las fronteras de la dinámica de fluidos computacional (CFD) están en constante expansión y demandan más y más recursos computacionales. Actualmente, estamos experimentando una evolución en los sistemas de computación de alto rendimiento (HPC) impulsado por restricciones de consumo de energía. Los nuevos nodos HPC incorporan aceleradores que se utilizan como co-procesadores para incrementar el rendimiento y la relación FLOP por vatio. Por otro lado, CPUs multi-core se han convertido en arquitecturas system-on-chip. Hoy en día, varias instituciones y gobiernos están invirtiendo en la investigación y desarrollo de los diferentes aspectos de HPC que podrían llevar a las próximas generaciones de superordenadores. Estas iniciativas han titulado el problema como el "exascale challenge". Este objetivo sólo puede lograrse mediante la incorporación de cambios importantes en: la arquitectura de ordenador, diseño de la memoria y las interfaces de red. La comunidad de CFD se enfrenta a un reto importante: mantener el ritmo a los rápidos cambios en las infraestructuras de HPC. Los códigos y formulaciones necesitan ser rediseñados para explotar los diferentes niveles de paralelismo y complejas jerarquías de memoria de los nuevos sistemas heterogéneos. Las principales características exigidas al nuevo software CFD son: estructuras de datos, la concurrencia extrema, modularidad y portabilidad. Esta tesis está dedicada al estudio de un modelo de implementation CFD para la adopción de nuevas tecnologías. Nuestro contexto de aplicación es la solución de los flujos incompresibles (DNS o LES) en mallas no estructuradas. El primer enfoque se basó en utilizar GPUs para acelerar el solver de Poisson. Los resultados positivos obtenidos en este primer paso nos motivaron a la portabilidad completa de la fase de integración temporal de nuestra aplicación. Esto requiere un importante rediseño del código. Proponemos un modelo de implementacion portable para aplicaciones de CFD. La idea principal es sustituir las estructuras de datos de los stencils y kernels por formatos de almacenamiento algebraicos y operadores. La estrategia de implementación consistió en la creación de una capa algebraica de bajo nivel para los cálculos de CPU y GPU, y una capa de discretización fácil de usar de alto nivel para las CPU. Como resultado, la fase de integración temporal del código se basa sólo en tres funciones algebraicas: producto de una matriz dispersa con un vector (SPMV), combinación lineal de dos vectores (AXPY) y producto escalar (DOT). Además, se prestó especial atención en el desarrollo de estructuras de datos compatibles con el modelo stream processing. Un análisis detallado de rendimiento se ha estudiado tanto en ejecución secuencial y paralela utilizando hasta 128 GPUs en un superordenador híbrido CPU / GPU. Por otra parte, hemos probado el nuevo modelo de TermoFluids en el superordenador Mont-Blanc basado en tecnología móvil. El rediseño de las funciones explota un modelo de ejecución heterogénea utilizando tanto la CPU y la GPU de los nodos basados en arquitectura ARM. El equilibrio de carga entre las dos unidades de cálculo aprovecha una estrategia de búsqueda tabú que sintoniza la distribución de carga de trabajo durante la etapa de preprocesamiento. Una comparación de los prototipos Mont-Blanc con superordenadores de alta gama en términos de rendimiento y consumo de energía nos proporcionó algunas pautas del comportamiento de las aplicaciones CFD en arquitecturas basadas en ARM. Por último, se presenta una estructura de datos auto-sintonizada para el solver de Poisson en problemas con una dirección diagonalizable mediante una descomposicion de Fourier. Este trabajo fue desarrollado y probado en la superordenador BlueGene / Q Vesta, y tiene por objeto demostrar la relevancia de vectorización y las estructuras de datos para aprovechar plenamente las CPUs de los superodenadores modernos.

Continuous improvements in transistor scaling together with microarchitectural advances have made possible the widespread adoption of high-performance processors across all market segments. However, the growing reliability threats induced by technology scaling and by the complexity of designs are challenging the production of cheap yet robust systems. Soft error trends are haunting, especially for combinational logic, and parity and ECC codes are therefore becoming insufficient as combinational logic turns into the dominant source of soft errors. Furthermore, experts are warning about the need to also address intermittent and permanent faults during processor runtime, as increasing temperatures and device variations will accelerate inherent aging phenomena. These challenges specially threaten the commodity segments, which impose requirements that existing fault tolerance mechanisms cannot offer. Current techniques based on redundant execution were devised in a time when high penalties were assumed for the sake of high reliability levels. Novel light-weight techniques are therefore needed to enable fault protection in the mass market segments. The complexity of designs is making post-silicon validation extremely expensive. Validation costs exceed design costs, and the number of discovered bugs is growing, both during validation and once products hit the market. Fault localization and diagnosis are the biggest bottlenecks, magnified by huge detection latencies, limited internal observability, and costly server farms to generate test outputs. This thesis explores two directions to address some of the critical challenges introduced by unreliable technologies and by the limitations of current validation approaches. We first explore mechanisms for comprehensively detecting multiple sources of failures in modern processors during their lifetime (including transient, intermittent, permanent and also design bugs). Our solutions embrace a paradigm where fault tolerance is built based on exploiting high-level microarchitectural invariants that are reusable across designs, rather than relying on re-execution or ad-hoc block-level protection. To do so, we decompose the basic functionalities of processors into high-level tasks and propose three novel runtime verification solutions that combined enable global error detection: a computation/register dataflow checker, a memory dataflow checker, and a control flow checker. The techniques use the concept of end-to-end signatures and allow designers to adjust the fault coverage to their needs, by trading-off area, power and performance. Our fault injection studies reveal that our methods provide high coverage levels while causing significantly lower performance, power and area costs than existing techniques. Then, this thesis extends the applicability of the proposed error detection schemes to the validation phases. We present a fault localization and diagnosis solution for the memory dataflow by combining our error detection mechanism, a new low-cost logging mechanism and a diagnosis program. Selected internal activity is continuously traced and kept in a memory-resident log whose capacity can be expanded to suite validation needs. The solution can catch undiscovered bugs, reducing the dependence on simulation farms that compute golden outputs. Upon error detection, the diagnosis algorithm analyzes the log to automatically locate the bug, and also to determine its root cause. Our evaluations show that very high localization coverage and diagnosis accuracy can be obtained at very low performance and area costs. The net result is a simplification of current debugging practices, which are extremely manual, time consuming and cumbersome. Altogether, the integrated solutions proposed in this thesis capacitate the industry to deliver more reliable and correct processors as technology evolves into more complex designs and more vulnerable transistors. / El continuo escalado de los transistores junto con los avances microarquitectónicos han posibilitado la presencia de potentes procesadores en todos los segmentos de mercado. Sin embargo, varios problemas de fiabilidad están desafiando la producción de sistemas robustos. Las predicciones de "soft errors" son inquietantes, especialmente para la lógica combinacional: soluciones como ECC o paridad se están volviendo insuficientes a medida que dicha lógica se convierte en la fuente predominante de soft errors. Además, los expertos están alertando acerca de la necesidad de detectar otras fuentes de fallos (causantes de errores permanentes e intermitentes) durante el tiempo de vida de los procesadores. Los segmentos "commodity" son los más vulnerables, ya que imponen unos requisitos que las técnicas actuales de fiabilidad no ofrecen. Estas soluciones (generalmente basadas en re-ejecución) fueron ideadas en un tiempo en el que con tal de alcanzar altos nivel de fiabilidad se asumían grandes costes. Son por tanto necesarias nuevas técnicas que permitan la protección contra fallos en los segmentos más populares. La complejidad de los diseños está encareciendo la validación "post-silicon". Su coste excede el de diseño, y el número de errores descubiertos está aumentando durante la validación y ya en manos de los clientes. La localización y el diagnóstico de errores son los mayores problemas, empeorados por las altas latencias en la manifestación de errores, por la poca observabilidad interna y por el coste de generar las señales esperadas. Esta tesis explora dos direcciones para tratar algunos de los retos causados por la creciente vulnerabilidad hardware y por las limitaciones de los enfoques de validación. Primero exploramos mecanismos para detectar múltiples fuentes de fallos durante el tiempo de vida de los procesadores (errores transitorios, intermitentes, permanentes y de diseño). Nuestras soluciones son de un paradigma donde la fiabilidad se construye explotando invariantes microarquitectónicos genéricos, en lugar de basarse en re-ejecución o en protección ad-hoc. Para ello descomponemos las funcionalidades básicas de un procesador y proponemos tres soluciones de `runtime verification' que combinadas permiten una detección de errores a nivel global. Estas tres soluciones son: un verificador de flujo de datos de registro y de computación, un verificador de flujo de datos de memoria y un verificador de flujo de control. Nuestras técnicas usan el concepto de firmas y permiten a los diseñadores ajustar los niveles de protección a sus necesidades, mediante compensaciones en área, consumo energético y rendimiento. Nuestros estudios de inyección de errores revelan que los métodos propuestos obtienen altos niveles de protección, a la vez que causan menos costes que las soluciones existentes. A continuación, esta tesis explora la aplicabilidad de estos esquemas a las fases de validación. Proponemos una solución de localización y diagnóstico de errores para el flujo de datos de memoria que combina nuestro mecanismo de detección de errores, junto con un mecanismo de logging de bajo coste y un programa de diagnóstico. Cierta actividad interna es continuamente registrada en una zona de memoria cuya capacidad puede ser expandida para satisfacer las necesidades de validación. La solución permite descubrir bugs, reduciendo la necesidad de calcular los resultados esperados. Al detectar un error, el algoritmo de diagnóstico analiza el registro para automáticamente localizar el bug y determinar su causa. Nuestros estudios muestran un alto grado de localización y de precisión de diagnóstico a un coste muy bajo de rendimiento y área. El resultado es una simplificación de las prácticas actuales de depuración, que son enormemente manuales, incómodas y largas. En conjunto, las soluciones de esta tesis capacitan a la industria a producir procesadores más fiables, a medida que la tecnología evoluciona hacia diseños más complejos y más vulnerables.

Nowadays, supercomputers deliver an enormous amount of computation power; however, it is well-known that applications only reach a fraction of it. One limiting factor is the single processor performance because it ultimately dictates the overall achieved performance. Performance analysis tools help locating performance inefficiencies and their nature to ultimately improve the application performance. Performance tools rely on two collection techniques to invoke their performance monitors: instrumentation and sampling. Instrumentation refers to inject performance monitors into concrete application locations whereas sampling invokes the installed monitors to external events. Each technique has its advantages. The measurements obtained through instrumentation are directly associated to the application structure while sampling allows a simple way to determine the volume of measurements captured. However, the granularity of the measurements that provides valuable insight cannot be determined a priori. Should analysts study the performance of an application for the first time, they may consider using a performance tool and instrument every routine or use high-frequency sampling rates to provide the most detailed results. These approaches frequently lead to large overheads that impact the application performance and thus alter the measurements gathered and, therefore, mislead the analyst. This thesis introduces the folding mechanism that takes advantage of the repetitiveness found in many applications. The mechanism smartly combines metrics captured through coarse-grain sampling and instrumentation mechanisms to provide instantaneous metric reports within instrumented regions and without perturbing the application execution. To produce these reports, the folding processes metrics from different type of sources: performance and energy counters, source code and memory references. The process depends on their nature. While performance and energy counters represent continuous metrics, the source code and memory references refer to discrete values that point out locations within the application code or address space. This thesis evaluates and validates two fitting algorithms used in different areas to report continuous metrics: a Gaussian interpolation process known as Kriging and piece-wise linear regressions. The folding also takes benefit of analytical performance models to focus on a small set of performance metrics instead of exploring a myriad of performance counters. The folding also correlates the metrics with the source-code using two alternatives: using the outcome of the piece-wise linear regressions and a mechanism inspired by Multi-Sequence Alignment techniques. Finally, this thesis explores the applicability of the folding mechanism to captured memory references to detail which and how data objects are accessed. This thesis proposes an analysis methodology for parallel applications that focus on describing the most time-consuming computing regions. It is implemented on top of a framework that relies on a previously existing clustering tool and the folding mechanism. To show the usefulness of the methodology and the framework, this thesis includes the discussion of multiple first-time seen in-production applications. The discussions include high level of detail regarding the application performance bottlenecks and their responsible code. Despite many analyzed applications have been compiled using aggressive compiler optimization flags, the insight obtained from the folding mechanism has turned into small code transformations based on widely-known optimization techniques that have improved the performance in some cases. Additionally, this work also depicts power monitoring capabilities of recent processors and discusses the simultaneous performance and energy behavior on a selection of benchmarks and in-production applications. / Actualment, els supercomputadors ofereixen una àmplia potència de càlcul però les aplicacions només en fan servir una petita fracció. Un dels factors limitants és el rendiment d'un processador, el qual dicta el rendiment en general. Les eines d'anàlisi de rendiment ajuden a localitzar els colls d'ampolla i la seva natura per a, eventualment, millorar el rendiment de l'aplicació. Les eines d'anàlisi de rendiment empren dues tècniques de recol·lecció de dades: instrumentació i mostreig. La instrumentació es refereix a la capacitat d'injectar monitors en llocs específics del codi mentre que el mostreig invoca els monitors quan ocórren esdeveniments externs. Cadascuna d'aquestes tècniques té les seves avantatges. Les mesures obtingudes per instrumentació s'associen directament a l'estructura de l'aplicació mentre que les obtingudes per mostreig permeten una forma senzilla de determinar-ne el volum capturat. Sigui com sigui, la granularitat de les mesures no es pot determinar a priori. Conseqüentment, si un analista vol estudiar el rendiment d'una aplicació sense saber-ne res, hauria de considerar emprar una eina d'anàlisi i instrumentar cadascuna de les rutines o bé emprar freqüències de mostreig altes per a proveir resultats detallats. En qualsevol cas, aquestes alternatives impacten en el rendiment de l'aplicació i per tant alterar les mètriques capturades, i conseqüentment, confondre a l'analista. Aquesta tesi introdueix el mecanisme anomenat folding, el qual aprofita la repetitibilitat existent en moltes aplicacions. El mecanisme combina intel·ligentment mètriques obtingudes mitjançant mostreig de gra gruixut i instrumentació per a proveir informes de mètriques instantànies dins de regions instrumentades sense pertorbar-ne l'execució. Per a produir aquests informes, el mecanisme processa les mètriques de diferents fonts: comptadors de rendiment i energia, codi font i referències de memoria. El procés depen de la natura de les dades. Mentre que les mètriques de rendiment i energia són valors continus, el codi font i les referències de memòria representen valors discrets que apunten ubicacions dins el codi font o l'espai d'adreces. Aquesta tesi evalua i valida dos algorismes d'ajust: un procés d'interpolació anomenat Kriging i una interpolació basada en regressions lineals segmentades. El mecanisme de folding també s'aprofita de models analítics de rendiment basats en comptadors hardware per a proveir un conjunt reduït de mètriques enlloc d'haver d'explorar una multitud de comptadors. El mecanisme també correlaciona les mètriques amb el codi font emprant dues alternatives: per un costat s'aprofita dels resultats obtinguts per les regressions lineals segmentades i per l'altre defineix un mecanisme basat en tècniques d'alineament de multiples seqüències. Aquesta tesi també explora l'aplicabilitat del mecanisme per a referències de memoria per a informar quines i com s'accessedeixen les dades de l'aplicació. Aquesta tesi proposa una metodología d'anàlisi per a aplicacions paral·leles centrant-se en descriure les regions de càlcul que consumeixen més temps. La metodología s'implementa en un entorn de treball que usa un mecanisme de clustering preexistent i el mecanisme de folding. Per a demostrar-ne la seva utilitat, aquesta tesi inclou la discussió de múltiples aplicacions analitzades per primera vegada. Les discussions inclouen un alt nivel de detall en referencia als colls d'ampolla de les aplicacions i de la seva natura. Tot i que moltes d'aquestes aplicacions s'han compilat amb opcions d'optimització agressives, la informació obtinguda per l'entorn de treball es tradueix en petites modificacions basades en tècniques d'optimització que permeten millorar-ne el rendiment en alguns casos. Addicionalment, aquesta tesi també reporta informació sobre el consum energètic reportat per processadors recents i discuteix el comportament simultani d'energia i rendiment en una selecció d'aplicacions sintètiques i aplicacions en producció.

People with manipulative and locomotive disabilities represents a large fraction of the population classified as disabled, including the elder, injured and other health related issues. Wheelchairs have evolved in order to maintain their mobility, autonomy and independence in the society. Despite important achievements in accessibility in current society (e.g. streets adapted to wheelchairs, or public transportation adapted with ramps and elevators), people with motor disabilities still lack independence in daily activities to improve their quality of life. Shopping is one example, where users can not access products in shelves beyond their arm length. Due to this barrier they often need personal assistance or support to complete all the necessary steps in the shopping activity. However, wheelchair users may prefer to shop individually (that is, without the assistance) in order to maintain their independence and privacy. This dissertation presents a novel systems that allows wheelchair user to interact with items placed beyond their arm length, by means of real-time interactive interfaces collaborated with Radio Frequency Identification (RFID). Our proposal, based on the concept of Smart Spaces, allows the users to interact through Hand-held, Smart Glass or Touch Screen interfaces in real-time with the items present on the shelf. We designed and evaluated the system with the participation of 18 wheelchair users with different degrees of physical disabilities. The obtained results demonstrate the suitability of our proposed system towards an improvement of the independence and empowerment of wheelchair users in shopping activities. / La gent amb deterioraments locomotrius i de manipulació representa una gran fracció de la població classificada com discapacitada, incloent ancians, lesionats i altres problemes de salut relacionats. Les cadires de rodes han evolucionat per mantenir la mobilitat, autonomia i independència a la societat. Malgrat els importants avenços en accessibilitat a l’actual societat (p.e. carrers adaptats per cadires de rodes o transport públic adaptat amb rampes i elevadors), la gent amb problemes motors encara manquen de independència en tasques diàries per millorar la seva qualitat de vida. Anar de compres és un exemple, a on els usuaris no poden accedir a productes als prestatges més enllà de la llargada dels seus braços. Degut a aquesta barrera, sovint necessiten atenció personal o suport per completar tots els passos necessaris en una activitat de compres. Però els usuaris amb cadires de rodes prefereixen anar a comprar individualment (això vol dir, sense assistència) per tal de mantenir la independència i privacitat. Aquesta dissertació presenta un nou sistema que permet als usuaris amb cadira de rodes interactuar amb objectes col•locats més enllà de la llargada dels seus braços, a través d’una interfície interactiva en temps real amb la Identificació per Radiofreqüència o RFID. La nostra proposta, basada en el concepte d´espais intel•ligents, permet als usuaris interactuar mitjançant la mà, ulleres intel•ligents o una interfície web a una pantalla tàctil en temps real amb els objectes presents al prestatge. Hem dissenyat i avaluat el sistema amb la participació de 18 usuaris en cadira de rodes amb diferents graus de discapacitat física. Els resultats obtinguts demostren la idoneïtat de la nostra proposta de sistema cap a una millora de la independència i apoderament dels usuaris en cadira de rodes en activitats de compra.

With the increased number of cores on a single processor chip, an application can achieve good performance if it splits the execution into multiple threads that run on multiple cores at the same time. To synchronize threads, Transactional Memory (TM) allows them to concurrently execute sections of code (transactions) with accesses to shared memory, and requires reexecution of one of the transactions in case of a conflicting access. Even though parallel programming with TM is simpler and less error-prone than with the traditional locking mechanism, concurrent programming errors are hard to avoid in general. The reason is that threads run in parallel and might interleave in a nondeterministic order. As a consequence, an error can occur in one execution but be hidden in another (which makes debugging hard), and the application output might vary (which makes testing and replica-based fault tolerance hard). To help programmers in testing, debugging and providing fault tolerance, researchers have proposed deterministic multithreading, which guarantees that application threads access shared memory in the same order and the application gives the same output whenever it runs with the same input parameters. In this thesis we present DeTrans, a system for deterministic multithreading in transactional applications. DeTrans ensures determinism even in the presence of data races, by executing non-transactional code serially and transactions in parallel. We compare DeTrans with Dthreads, a widely-used deterministic system for lock-based applications, and analyse sources of the overhead caused by deterministic execution. Instead of using memory protection hardware and operating system facilities, DeTrans exploits properties of TM implemented in software and outperforms Dthreads. To allow transactions to invoke standard library functions while running deterministically and to increase parallelism, this thesis proposes TM-dietlibc, a TM-aware standard library. Our experience in modifying a lock-based standard library in order to integrate it in a TM system is applicable for any TM-aware software. TM-dietlibc provides concurrent execution of standard library functions and only in a few cases the execution switches to serial. In comparison to completely serialized execution, TM-dietlibc shows high scalability and performance improvement for benchmarks with short transactions and low contention. Serialization of transactions - which is still required for transactions in TM-dietlibc with non-reversible side effects - might enforce an order of threads execution different from the one enforced by a deterministic system, causing a deadlock. By porting deterministic system DeTrans in TM-dietlibc, we ensure deterministic multithreading at application and standardlibrary level, and avoid deadlocks by serializing transactions in deterministic order. In this thesis we also discuss a common limitation of deterministic systems - ad hoc synchronization. Ad hoc synchronization is in general widely used, but similarly to transaction serialization, it might be prone to deadlocks during deterministic execution. We use hardware performance counters to identify synchronization loops at runtime and to avoid deadlocks by dynamically (but deterministically) changing the order of threads execution. / Con el aumento del número de núcleos en un solo procesador, una aplicación puede lograr un buen rendimiento si se divide la ejecución en múltiples hilos que se ejecutan en múltiples núcleos al mismo tiempo. Para sincronizar estos hilos, memoria transaccional (TM) permite ejecutar simultáneamente secciones de código (transacciones) con accesos a memoria compartida, y requiere re-ejecución de una de las transacciones en caso de un acceso a memoria que causa un conflicto. A pesar de que la programación paralela con TM es más simple y menos propensa a errores que con mecanismos de cerrojos tradicionales, los errores de programación concurrentes son difíciles de evitar en general. La razón es que los hilos se ejecutan en paralelo y pueden intercalar en ordenes no deterministas. Como consecuencia, un error puede ocurrir en una ejecución, pero se oculta en otro (lo que hace que la depuración difícil), y el resultado de la aplicación puede variar (lo que hace el testeo y la tolerancia a fallos basada en réplica difícil). Para ayudar a los programadores en el testeo, depuración y proporcionar tolerancia a fallos, los investigadores han propuesto sistemas multihilos deterministas, que garantizan que los diferentes hilos de las aplicaciones accedan a la memoria compartida en el mismo orden y la aplicación da el mismo resultado cada vez que se ejecuta con los mismos parámetros de entrada. En esta tesis presentamos DeTrans, un sistema determinista para las aplicaciones transaccionales. DeTrans asegura el determinismo incluso en presencia de condiciones de carrera de datos, mediante la ejecución de código no transaccional en serie y las transacciones en paralelo. Comparamos DeTrans con Dthreads, un sistema determinista ampliamente utilizado para aplicaciones basadas en cerrojos, y analizamos las fuentes de coste adicional causadas por la ejecución determinista. En lugar de utilizar hardware de protección de memoria y las funcionalidades del sistema operativo, DeTrans explota las propiedades de TM implementadas en software y rinde mejor que Dthreads. Para permitir que las transacciones puedan invocar funciones de la librería estándar durante la ejecución determinista y aumentar el paralelismo, esta tesis propone TM-dietlibc, una librería estándar consciente de TM. Nuestra experiencia en la modificación de una librería estándar basada en locks con el fin de integrarlo en un sistema de TM es aplicable a cualquier software consciente de TM. TM-dietlibc proporciona ejecución simultánea de funciones de la librería estándar y sólo en unos pocos casos la ejecución pasa a ser en serie. En comparación con la ejecución totalmente serial, TM-dietlibc muestra una alta escalabilidad y una mejora del rendimiento para aplicaciones con transacciones cortas y contención baja. Serialización de transacciones - que todavía se requieren para las transacciones en TM-dietlibc con efectos secundarios no reversibles - podría forzar un orden de ejecución de los hilos distinta de la aplicada por un sistema determinista, causando un deadlock. Portando el sistema determinista DeTrans a TM-dietlibc, aseguramos ejecuciones multihilo deterministas tanto a nivel de la aplicación como de la librería estándar, y evitamos deadlocks serializando transacciones en orden determinista. En esta tesis también discutimos una limitación común de los sistemas deterministas - la sincronización ad-hoc. La sincronización ad-hoc es en general ampliamente utilizada, pero de manera similar a la serialización transacción, puede ser propensa a deadlocks durante la ejecución determinista. Utilizamos contadores de rendimiento hardware para identificar bucles de sincronización durante la ejecución y así evitar deadlocks de forma dinámica (pero determinista) cambiando el orden de ejecución de los hilos.