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.

With the growth of the Internet, computational systems have become more and more complex, often including complicate interconnected networks of autonomous components. The need to bring some organisational structure into autonomous systems becomes urgent, as this allows regulating the behaviour of the different autonomous components to ensure their objectives are aligned with the holistic objectives of the system. Normative Systems are one of the mechanisms that can be applied to define and enforce acceptable behaviour within distributed electronic systems which should comply with some (human) regulations. One of the requirements to effectively implement Normative Systems is to be able to assess, at runtime, the state of the normative environment. Existing lines of research have already tried to tackle this issue on some simple scenarios. However, more complex scenarios may appear, for instance, scenarios where the normative context is not static, but it expands and contracts as new norms are added to the institution and removed from it respectively. As in human legal systems, it is easy to foresee that some of these electronic normative environments will not be static. They should be able to evolve through time as regulations change, effectively adapting to new situations and behaviours. Under these conditions, a monitoring system must be able to continue computing the state of the normative environment at runtime, as often we can not afford to perform the changes on the normative context off-line. Furthermore, it must be guaranteed the monitoring system can keep producing states of the normative environment that are consistent with the changes performed on the normative context. For instance, if a norm has been removed from the normative context, it does not make sense anymore to compute normative states where the norm has been violated. In this thesis we present NoMoDEI, a normative monitoring framework for dynamic Electronic Institutions. We formalize and develop an extended normative framework and architecture to cope with scenarios where the normative context is dynamic, therefore norms can be added, removed and updated. The operations are to be performed at run-time, without having to stop computing the normative state. The normative states computed are consistent with the expansion and contraction operations. NoMoDEI is introduced in three steps. First, we formally define the operations to be supported in order to allow for expanding and contracting the normative context. Then, we instantiate the formal operations, providing implementation details. Finally, we demonstrate our framework by applying it to two use cases: E-health systems and waste-water management on a river basin. / Amb l'expansió d'Internet els sistemes computacionals han esdevingut més complexos, sovint incorporant complicades xarxes interconnectades de components autònoms. Es per això que la necessitat d'incorporar estructures organitzacionals en el sistemes autònoms s 'accentua, donat que aquestes estructures permeten regular el comportament dels diferents components autònoms, tot assegurant que els seus objectius es troben alineats amb els objectius generals del sistema. Els Sistemes Normatius (i.e. Normative Systems) són un dels mecanismes que podem aplicar per definir i imposar patrons acceptables de comportament dintre de sistemes electrònics distribuïts. Això esdevé especialment important quan el sistema es troba regimentat per regulacions (normalment humanes). Un dels requeriments per implementar Sistemes Normatius és ser capaços de determinar, en temps d'execució, l'estat de l'entorn normatiu. Existeixen línies de recerca que ja han tractat aquest problema en alguns escenaris simples. El món real però ens ofereix escenaris més complexes, com per exemple, escenaris on el context normatiu no és estàtic, si no que s'expandeix i contrau a mesura que noves normes són afegides o eliminades de la institució. Tal com passa als sistemes legals humans, és fàcil preveure que alguns contextos normatius electrònics no seran estàtics. Aquests contextos haurien de ser capaços d'evolucionar a través del temps a mesura que les regulacions canvien, adaptant-se a noves situacions i comportaments. Sota aquestes condicions, un sistema de monitorització ha de ser capaç de continuar calculant l'estat de l'entorn normatiu en temps d'execució, ja que sovint no ens podem permetre realitzar els canvis a l'entorn normatiu aturant el procés de monitorització. És més s'ha de garantir que el sistema de monitorització sigui capaç de continuar produint es tats de l’entorn normatiu de forma consistent amb els canvis realitzats. Per exemple, el fet d'eliminar una norma fa que no tingui gaire sentit continuar calculant es tats normatius on aquesta norma ha es tat violada. A aquesta Tesi presentem NoMoDEI, una infraestructura de monitorització normativa per institucions electròniques dinàmiques. Formalitzem i desenvolupem una infraestructura de monitorització normativa estesa capaç d'operar en escenaris on el context normatiu es dinàmic. Es a dir, diverses normes poden ser introduïdes, eliminades o actualitzades del context normatiu en qualsevol moment. Aquestes operacions s'han de poder realitzar en temps d'execució, es a dir, sense deixar de calcular l'estat normatiu. Es més, els estats normatius calculats han de ser consistents amb les respectives operacions d'extensió o contracció del context. Durant la Tesi presentem NoMoDEI en tres passos. Primer proporcionem una definició formal de les operacions que la infraestructura ha de suportar per permetre expandir i contraure el context normatiu. A continuació instanciem aquestes operacions proporcionant detalls d'implementació. Finalment demostrem que la nostra infraestructura pot ser aplicada a casos d'ús del món real introduint dos casos: sistemes de salut electrònics (i.e. E-health) i sistemes de tractament d’aigües residuals a la conca d’un riu

The first chapter introduces an approach to machine learning (ML) were data is understood as a network of connected entities. This strategy seeks inter-entity information for knowledge discovery, in contrast with traditional intra-entity approaches based on instances and their features. We discuss the importance of this connectivist ML (which we refer to as graph mining) in the current context where large, topology-based data sets have been made available. Chapter ends by introducing the Link Prediction (LP) problem, together with its current computational and performance limitations. The second chapter discusses early contributions to graph mining, and introduces problems frequently tackled through this paradigm. Later the chapter focuses on the state-of-the-art of LP. It presents three different approaches to the problem of finding links in a relational set, and argues about the importance of the most computationally scalable one: similarity-based algorithms. It categorizes similarity-based algorithms in three types of LP scores. For the most scalable type, local similarity-based algorithms, the chapter identifies and formally describes the most competitive proposals according to the bibliography. Chapter three analyses the LP problem, partly as a classic binary classification problem. A list of graph properties such as directionality, weights and time are discussed in the context of LP. Follows a formal time and space complexity analysis of similarity-based scores of LP. The chapter ends with an study of the class imbalance found in LP problems. In chapter four a novel similarity-based score of LP is introduced. The chapter first elaborates on the importance of hierarchies for representing knowledge through directed graphs. Several modifications to the proposed score are also defined. This chapter presents a modified version of the most competitive undirected scores of LP, to adapt them to directed graphs. The evaluation methodologies of LP are analyzed in the fifth chapter. It starts by discussing the problem of evaluating domains with a huge class imbalance, identifying the most appropriate methodologies for it. A modification of the most appropriate evaluation methodology according to the bibliography is presented, with the goal of focusing on relevant predictions. Follows a discussion on the faithful estimation of the precision of predictors. Chapter six describes the graphs used for score evaluation, as well as how data was transformed into a directed graph. Reasons on why these particular domains were chosen are given, making a special case of webgraphs and their well known relation with hierarchies. The most basic properties of each resultant graph are shown. Tests performed are presented in chapter seven. The three most competitive LP scores currently available are tested among themselves, and against a proposed version of those same scores for directed graphs. Our proposed score and its modifications are tested against the scores obtaining the best results in the previous tests. The case of LP in webgraphs is considered separately, testing six different webgraphs. The chapter ends with a discussion on the limitations of this formal analysis, showing examples of predictions obtained. Chapter eight includes the computational aspects of the work done. It starts with a discussion on the importance of memory management for determining the computational cost of LP algorithms. A proposal on how to reduce this cost through precision reduction is presented. Follows a section focused on the parallelization of code, which includes two different implementations on one graph-specific programming model (Pregel) and on one generic programming model (OpenMP). The chapter ends with a specification of the computational resources used for the tests done. The conclusions of this thesis proposal are presented in nine. Chapter ten contains several future lines of work. / El primer capítol introdueix una perspectiva de l'aprenentatge automàtic on les dades s'entén com una xarxa d'entitats connectades. Aquesta estratègia es centra en les relacions entre entitats per aprendre, en contrast amb les solucions tradicionals basades en instancies i els seus atributs. Discutim sobre la importància d'aquesta perspectiva connectivista (a la que ens referim com mineria de grafs) en el context actual on grans conjunts de dades basats en xarxes estan apareixent. El capítol finalitza amb la presentació del problema de Predicció d'Arestes (PA), junt amb una primera anàlisi de les seves limitacions actuals. El segon capítol presenta les primeres contribucions a la mineria de grafs, introduint problemes típicament solucionats mitjançant aquest paradigma. El capítol es centra en l'estat de l'art de PA. Presenta tres solucions diferents per al problema i argumenta la importància del més computacionalment escalable: els algoritmes basats en similitud. Categoritza aquests en tres tipus, i per als més escalables d'aquests, els algoritmes locals, s'identifica i es descriu formalment les propostes més competitives d'acord amb la bibliografia. El tercer capítol analitza el problema de PA, inicialment com a problema de classificació binari. Una llista de propietats de grafs són discutides en el context de la PA, com la direccionalitat o els pesos. Segueix una anàlisi del cost computacional en temps com en espai, dels algorismes basats en similitud. El capítol finalitza amb un estudi del desbalanceig de classes, freqüent en la PA. Al capítol quatre es presenta un nou algorisme basat en similitud per la PA. El capítol elabora sobre la importància de les jerarquies a la representació del coneixement a través de grafs dirigits. Varies modificacions es proposen per al nou algorisme. Aquest capítol també inclou una modificació sobre els actuals algorismes de similitud per a grafs no dirigits, per adaptar-los per a grafs dirigits. Les metodologies d'avaluació de la PA s'analitzen al cinquè capítol. Comença amb una discussió sobre els problemes que suposa avaluar un context amb un gran desbalanceig de classes, identificant les metodologies apropiades per aquests casos. Es proposa una modificació sobre el mètode més apropiat actualment disponible, per tal de centrar-se en les prediccions rellevants. Segueix una discussió sobre l'estimació fidedigna de la precisió dels predictors. El sisè capítol descriu els grafs usats per avaluar els algorismes, així com la metodologia usada per transformar-los en grafs dirigits. Les raons per triar aquest conjunt de grafs són exposades, posant especial interès al cas dels grafs web i a la seva ben coneguda relació amb les jerarquies. Les propietats més bàsiques de cada graf resultant són descrites. Els tests efectuats es mostren al capítol setè. Els tres algorismes actuals de PA més competitius són comparats amb ells mateixos i amb la versió per a grafs dirigits definida anteriorment. L'algorisme proposat anteriorment i les seves modificacions també són avaluats. El problema de la PA en grafs web es considera per separat, avaluant sis grafs web diferents. El capítol acaba amb una discussió sobre les limitacions de les avaluacions formals, mostrant exemples de prediccions obtingudes. El vuitè capítol inclou els aspectes computacionals de la tesi. Comença amb una discussió sobre la importància de la gestió de memòria per a la definició del cost computacional dels algorismes de PA. Inclou una proposta sobre com reduir aquest cost mitjançant una reducció en la precisió. Segueix una secció centrada en la paral·lelització del codi, que inclou dues implementacions diferents, una en un model de programació específic per grafs (Pregel) i una amb un model de programació paral·lela genèric (OpenMP). El capítol finalitza amb una especificació dels recursos computacionals usats per als tests realitzats. Les conclusions de la tesi es presenten al capítol novè, i les línies de treball futur al desè

Tal com es veurà en el següent capítol d'antecedents, existeixen formes molt variades d'afrontar l'anàlisi de textures però cap d'elles està orientada al càlcul en temps real (video rate). Degut a la manca de mètodes que posin tant d'èmfasi en el temps de processat, l'objectiu d'aquesta tesi és definir i desenvolupar un nou mètode d'extracció de característiques de textura que treballi en temps real. Per aconseguir aquesta alta velocitat d'operació, un altre objectiu és presentar el disseny d'una arquitectura específica per implementar l'algorisme de càlcul dels paràmetres de textura definits, així com també l'algorisme de classificació dels paràmetres i la segmentació de la imatge en regions de textura semblant.En el capítol 2 s'expliquen els diversos mètodes més rellevants dins la caracterització de textures. Es veuran els mètodes més importants tant pel que fa als enfocaments estadístics com als estructurals. També en el mateix capítol se situa el nou mètode presentat en aquesta tesi dins els diferents enfocaments principals que existeixen. De la mateixa manera es fa una breu ressenya a la síntesi de textures, una manera d'avaluar quantitativament la caracterització de la textura d'una imatge. Ens centrarem principalment, en el capítol 3, en l'explicació del mètode presentat en aquest treball: s'introduiran els paràmetres de textura proposats, la seva necessitat i definicions. Al ser paràmetres altament perceptius i no seguir cap model matemàtic, en aquest mateix capítol s'utilitza una tècnica estadística anomenada anàlisi discriminant per demostrar que tots els paràmetres introdueixen suficient informació per a la separabilitat de regions de textura i veure que tots ells són necessaris en la discriminació de les textures.Dins el capítol 4 veurem com es tracta la informació subministrada pel sistema d'extracció de característiques per tal de classificar les dades i segmentar la imatge en funció de les seves textures. L'etapa de reconeixement de patrons es durà a terme en dues fases: aprenentatge i treball. També es presenta un estudi comparatiu entre diversos mètodes de classificació de textures i el mètode presentat en aquesta tesi; en ell es veu la bona funcionalitat del mètode en un temps de càlcul realment reduït. S'acaba el capítol amb una anàlisi de la robustesa del mètode introduint imatges amb diferents nivells de soroll aleatori. En el capítol 5 es presentaran els resultats obtinguts mitjançant l'extracció de característiques de textura a partir de diverses aplicacions reals. S'aplica el nostre mètode en aplicacions d'imatges aèries i en entorns agrícoles i sobre situacions que requereixen el processament en temps real com són la segmentació d'imatges de carreteres i una aplicació industrial d'inspecció i control de qualitat en l'estampació de teixits. Al final del capítol fem unes consideracions sobre dos efectes que poden influenciar en l'obtenció correcta dels resultats: zoom i canvis de perspectiva en les imatges de textura.En el capítol 6 es mostrarà l'arquitectura que s'ha dissenyat expressament per al càlcul dels paràmetres de textura en temps real. Dins el capítol es presentarà l'algorisme per a l'assignació de grups de textura i es demostrarà la seva velocitat d'operació a video rate.Finalment, en el capítol 7 es presentaran les conclusions i les línies de treball futures que es deriven d'aquesta tesi, així com els articles que hem publicat en relació a aquest treball i a l'anàlisi de textures. Les referències bibliogràfiques i els apèndixs conclouen el treball.

El objetivo principal fijado al inicio de esta tesis era la definición de una metodología para la descripción y seguimiento de caminos mal o débilmente estructurados (como por ejemplo los caminos de montaña, agrícolas o vecinales y las pistas forestales), orientada a un sistema de navegación autónomo. Como objetivo secundario, se había fijado el poder obtener la descripción de este tipo de entorno utilizando un sistema sensorial i computacional tan simple como fuese posible, tratando de obtener la máxima fiabilidad del sistema. Algunas de las aplicaciones donde sería de interés el sistema propuesto son el guiado de vehículos agrícolas, sistemas autónomos de extinción de incendios forestales, la ingeniería civil o la minería. La metodología que se ha seguido en la realización de la tesis se puede resumir en cuatro etapas: 1) estudio de los métodos existentes orientados a operar en otros tipos de entornos, constatando sus limitaciones para trabajar en entornos mal o débilmente estructurados. 2) análisis de que información es necesaria para navegar de forma autónoma en este tipo de entorno, y que sensores nos la pueden suministrar. 3) definición y implementación de los diferentes pasos necesarios para obtener una descripción de caminos mal o débilmente estructurados, como son el prepocesado de la imagen color, la segmentación de la imagen, la detección de obstáculos y la integración de la información presente en la secuencia de imágenes. 4) validación del método propuesto, en esta etapa se han utilizado secuencia de imágenes sintéticas, secuencia de imágenes captadas en un entorno conocido y controlado (una maqueta), y secuencia de imágenes captadas en entornos naturales. Durante la realización de esta tesis, se han analizado las diferentes alternativas que llevan a la solución del problema de la descripción del tipo de entorno considerado. Las soluciones seleccionadas están en la dirección de minimizar el coste del sistema, reducir el tiempo de proceso (y así permitir al vehículo que se desplace, dentro de las posibilidades del entorno, a mayor velocidad), garantizando, la fiabilidad de la solución adoptada. Las principales aportaciones y contribuciones realizadas a los métodos y técnicas en el ámbito de la navegación y de la visión por ordenador, resultado de la realización de esta tesis doctoral son: . Definición de un nuevo espacio de representación de la información color a partir del espacio HSI, el espacio H/I, que permite representar y analizar imágenes captadas en entornos naturales de forma eficiente. . Definición de una nueva técnica para la detección de obstáculos basada en el análisis de la evolución del tamaño de las regiones, definidas en la segmentación de la secuencia de imágenes. . Adaptación de la técnica de segmentación de crecimiento de regiones para el análisis de imágenes provenientes de escenas naturales, utilizando el color como característica. . Adaptación de un modelo para la descripción del entorno basado en matrices, para la descripción de un entorno mal o débilmente estructurado, orientado a la navegación de vehículos autónomos. Este trabajo se enmarca dentro de una temática de remarcable interés dentro de la visión por ordenador y la robótica móvil, y que también es motivo de estudio en otras universidades. Los aspectos más originales del trabajo realizado radican en la propuesta de una metodología para la descripción de caminos mal o débilmente estructurados implementable con un sistema sensorial y computacional de bajo coste, respecto otras soluciones a problemas similares.