Objetivos Con el fin de los beneficios energéticos del escalado clásico de los transistores, la eficiencia energética se convirtió en el principal objetivo de los diseños de microprocesador. Las mejoras de los transistores no pueden compensar al mismo ritmo que en el pasado los costes energéticos de mejorar el rendimiento con frecuencias mayores y microarquitecturas más complejas. Ahora más que nunca, los arquitectos de computadores deben proporcionar el crecimiento de rendimiento esperado a través de diseños más eficientes energéticamente. Hace algunos años los multiprocesadores en un chip (CMPs), formados por núcleos relativamente simples, se adoptaron como una arquitectura con mayor eficiencia energética, convirtiéndose en la principal corriente de diseño. Sin embargo, los CMPs plantean dificultades particulares en su diseño. En esta tesis abordamos dos cuestiones con creciente importancia al escalar los CMPs: el consumo de energía de la red del chip (NoC) y la escalabilidad de la coherencia de caché, y proponemos mecanismos para mitigar su impacto en la eficiencia energética. Al aumentar la cantidad de núcleos, la información de coherencia de caché llegaría a ocupar la mayor parte del área de almacenamiento del chip si no somos capaces de desarrollar esquemas de coherencia escalables y eficientes energéticamente. Además, las tendencias actuales indican que la NoC acabaría usando la mayor parte de la energía del chip si no se toman medidas para evitarlo. Metodología Cada propuesta de esta tesis fue evaluada contra otras soluciones recientes, demostrando su eficacia, y puesta en contexto con el estado del arte. Para ello se utilizó un extenso conjunto de herramientas, incluyendo simuladores detallados como Simics, GEMS y GEM5 para modelar el rendimiento de los CMPs, simuladores de red como GARNET y simuladores de consumo energético como McPAT, Orion o CACTI. Un diseño tiled-CMP, representativo de los multiprocesadores actuales en cualquier segmento de mercado, se usó como base sobre la que implementar nuestras propuestas. Resultados Para mejorar la escalabilidad de la coherencia de caché proponemos un nuevo esquema de coherencia basado en un chip dividido en áreas enlazadas que reduce notablemente el tamaño del almacenamiento usado por la información de compartición. También proponemos una organización de caché unificada que elimina la sobrecarga y complejidad de las estructuras de almacenamiento de directorio aprovechando los recursos compartidos de caché para almacenar alternativamente datos o información de directorio con granularidad de entrada de caché. Esta organización usa eficientemente los recursos de almacenamiento, asignando a información de directorio sólo el (pequeño) número de entradas necesarias de la memoria caché unificada. Demostramos que esta organización es escalable a grandes números de núcleos (e.g., 512 trivialmente y 1 millón con códigos compartidos elaborados). Para reducir el impacto del escalado de la NoC desarrollamos técnicas para aumentar la proximidad entre datos y núcleos a nivel de la arquitectura y políticas para utilizar de manera eficiente la novedosa tecnología de transmisión fotónica en silicio de bajo consumo. Para aumentar la cercanía de datos, proponemos un mecanismo que obtiene datos de un proveedor cercano en la zona en que se encuentra el núcleo que solicita los datos, a nivel de protocolo de coherencia de caché. A nivel de organización de caché proponemos una nueva organización cuyo objetivo es minimizar la distancia media para acceder al último nivel de cache, reduciendo la energía necesaria para alimentar los núcleos con datos. Para permitir la explotación de la fotónica en silicio abrimos el campo de las políticas dinámicas de gestión de NoCs híbridas fotónicas-electrónicas, haciendo uso eficiente de las propiedades particulares de cada tecnología con fina granularidad de mensaje, resultando en importantes beneficios en rendimiento, energía y latencia. / Objectives With the end of the energy benefits of classical transistor scaling, energy-efficiency became the driving factor of microprocessor design. The energy costs of increasing operating frequencies and using more aggressive microarchitectures to improve performance can no longer be compensated by transistor technology advances at the same rate as in the past. Now more than ever, computer architects are left in charge of providing the expected growth of microprocessor performance by means of more energy-efficient designs, in order to make cost-effective use of the ever-increasing transistor density in chips within a limited power budget. Otherwise, microprocessor evolution would be doomed to hit the power wall. Some years back, chip multiprocessors (CMPs) containing relatively simple cores were deemed a suitable architecture in the search for energy-efficiency and went mainstream. However, CMPs pose particular challenges in their design. In this thesis we tackle two paramount issues with growing importance as we scale out CMPs, namely network-on-chip power consumption and cache coherence scalability, and we propose mechanisms to alleviate their impact on the energy-efficiency of CMPs. As the core count increases, cache coherence information may eventually account for most storage area on chip if we fail to provide scalable and energy-efficient coherence schemes. In addition, current trends indicate that networks-on-chip (NoCs) would end up taking up most of the chip energy budget unless measures are taken to prevent it. Methodology To carry out this research, a comprehensive set of tools was used, including detailed simulators such as Simics, GEMS and GEM5 to model the timing of CMPs, network simulators such as GARNET, as well as power simulators such as McPAT, Orion or CACTI. A tiled-CMP design, representative of current multiprocessors in every market segment, was used as a baseline with realistic features on which to implement our proposals. Every proposal was evaluated against state of the art counterparts to prove their effectiveness. Results To improve the scalability of cache coherence, we propose a new coherence scheme based on a chip divided in linked areas that noticeably reduces the size of the storage used to maintain sharing information. Then, we propose a unified cache organization that eliminates the overhead and complexity of directory storage structures by leveraging shared cache resources to alternately store data or directory information at a cache entry granularity. This organization makes efficient use of storage resources as just the required (small) number of entries are allocated for directory information in the unified cache. We show that this organization is scalable to very large core counts (e.g. 512 trivially and one million with elaborate sharing codes). To reduce the impact of network scaling, we develop techniques to increase the proximity of data to cores at the architecture level, and policies to efficiently use disruptive low-power transmission technologies such as silicon photonics. For increasing data proximity, in this thesis we propose a mechanism that retrieves data from a close provider in the area in which the core requesting the data is located, working at the cache coherence protocol level. At the cache organization level, we propose a new organization that aims at minimizing the average distance to access the last level cache, reducing the energy required to feed the cores with data. To enable the exploitation of photonics, we open the field of dynamic policies for arbitrating hybrid photonic-electronic NoCs, making energy-efficient use of the particular properties of both technologies at a fine message granularity, resulting in important benefits in throughput, energy and latency.

Tesis por compendio de publicaciones / Percibir el contexto de un vehıculo de una manera precisa y detallada es extremadamente util para permitir el desarrollo de servicios ubicuos vehiculares que hagan el transporte por carretera más seguro y confortable. Por ello, la presente tesis doctoral se centra en el diseño de una novedosa solución de carácter general para gestionar el entorno de un vehículo que cubra tanto los aspectos teóricos como prácticos relacionados con la percepción del contexto vehicular. Esta nueva solución Context-Awareness dentro del contexto vehicular ha sido llamada Intra-vehicular Context Awareness (IvCA). En este sentido, la linea de trabajo ha tenido dos vertientes. Por un lado, se diseñó un modelo de carácter general del contexto de un vehículo. Por otro lado, se ha realizado un enfoque práctico con el fin de desarrollar diferentes soluciones para percibir dicho modelo contextual. / The development of on-board services in the vehicular scope is an important line of work in the ITS field. In this scope, the perception of the context is a paramount factor so as to come up with more complex and advanced services. Thus, the present PhD thesis pursues to define a general-purpose platform to perceive the context related to a vehicle given a familiar scope. In that sense, the line of work has been twofold. On the one hand, a general model for the context of a vehicle has been designed. On the other hand, a practical approach has been carried out to develop several solutions to perceive the target context model. These solutions have been implemented by mainly taking advantage of low-cost equipments a common vehicle includes by default.

Uno de los problemas a los que las tecnologías de la información han tenido que enfrentarse en los últimos años es el análisis de una enorme cantidad de datos originada en las actividades cotidianas de organizaciones o personas. Este análisis puede consistir en la búsqueda tanto de modelos como patrones que ayuden en la comprensión de los datos o el comportamiento de estas organizaciones o personas. Una componente esencial asociada a este tipo de conocimiento es la dimensión temporal, que cuando es tenida en cuenta en los patrones, no sólo proporciona mucha más información, sino también los convierte en más complejos. La minería de datos de secuencias (SDM) es un área en el campo de la detección de conocimiento en bases de datos (KDD) cuyo objetivo es extraer los conjuntos de patrones frecuentes que se encuentran, ordenados en el tiempo, en una base de datos. Algunas técnicas de SDM han sido empleadas en una amplia variedad de dominios de aplicación, tales como el descubrimiento de patrones en secuencias de ADN, el análisis de secuencias de compras de clientes, número de clics en una web, etcétera. Los patrones que se obtienen en estos dominios dependen de la naturaleza de los datos que son objeto de análisis y del propósito de dicho análisis. Por un lado, hay patrones sencillos que sólo contienen eventos que denotan puntos ordenados en el tiempo. Por ejemplo, un patrón puede modelar el comportamiento de una persona que, durante la noche, se despierta, toma agua, va al baño, y luego regresa a la cama. Por otra parte, otros patrones mucho más complejos incluyen eventos que denotan intervalos con distancias temporales entre ellos. Por ejemplo, una persona duerme durante 3 horas, seguidamente pasa 3 minutos en la cocina y, después de ver la televisión durante 40 minutos, vuelve a dormir durante 2 horas más. Entre estos dos extremos existe una amplia gama de diferentes patrones. Esta tesis supone distintas aportaciones al campo de la SDM. En primer lugar, proponemos una clasificación clara de los patrones y algoritmos dentro de la SDM. Hacemos un estudio claramente diferenciado en tres distintas dimensiones: representación de los patrones, su expresividad y la estrategia de búsqueda utilizada para la extracción de patrones frecuentes. En esta clasificación hemos encontrado algunas lagunas en los algoritmos existentes en el estado del arte. En segundo lugar, con el fin de completar las lagunas que aún no han sido exploradas, ofrecemos cinco nuevos algoritmos que utilizan diferentes representaciones y estrategias. Finalmente, discutimos la conveniencia de utilizar un algoritmo determinado en función de las propiedades de la base de datos y los patrones que son objeto de nuestro interés. / One of the problems that information technologies have had to confront in recent years is the analysis of the huge amount of data that originates during the daily activities of organisations or people. This analysis may consist of searching for models or patterns that will assist in understanding the data or behaviour of these organisations or people. One essential component in this kind of knowledge is the temporal dimension. When time is included in the patterns, they provide much more information but also become more complex. Sequence Data Mining (SDM) is an area in the field of Knowledge Discovery whose aim is to extract sets of frequent patterns that occur, ordered in time, in a database. SDM techniques have been used in a wide array of application domains, such as the discovery of motifs in DNA sequences, the analysis of customer purchase sequences, web click streams, and so forth. The patterns obtained in these domains depend on the nature of the data under analysis and the purpose of the analysis. On the one hand, there are simple patterns that only contain point events ordered in time. For example, a pattern can model the behavior of a person who, during the night, wakes up, drinks water, goes to the bathroom, and then goes back to bed again. On the other hand, much more complex patterns include interval events with temporal distances between them. For example, a person sleeps for 3 hours, then spends 3 minutes in the kitchen and, after watching TV for 40 minutes, goes back to sleep for 2 more hours. There is a wide range of patterns between these two extremes. This thesis presents a number of contributions to the SDM field. Firstly, we propose a clear categorisation of patterns and algorithms within SDM. We principally study three different dimensions: the representation of the patterns, their expressiveness and the search strategy used to mine patterns. In this categorisation we have found certain gaps in the state-of-the-art algorithms. Secondly, in order to complete those gaps that have not yet been explored, we provide five new algorithms that use different representations and strategies. Finally, we discuss the convenience of using a particular algorithm depending on the properties of the database and the patterns that we are interested in finding.

Resumen En esta tesis proponemos GEA (Global Epipolar Adjustment), un método de corrección de movimiento para aplicaciones de Visual SLAM y SfM altamente eficiente basado en restricciones algebraicas epipolares, que no hace uso de la información sobre la estructura. Este método obtiene resultados muy cercanos, y en muchos casos equivalentes a los obtenidos mediante bundle adjustment (BA), a pesar de su naturaleza algebraica, requiriendo por contra un coste computacional mucho menor. En este trabajo describimos cómo usar esa técnica para estimar las poses de cámara de forma incremental en aplicaciones SfM, sin necesidad de estimar en el proceso información sobre la estructura tal como correspondencias multivista de características de imagen. Estas poses de cámara pueden ser usadas a posteriori para obtener una estimación de alta precisión para la estructura. Demostramos que las técnicas descritas son robustas a los errores típicos de correspondencia obtenidos por los métodos habituales usados en SfM. / In this work we propose GEA (Global Epipolar Adjustment), a high-performance structureless BA correction method based on algebraic epipolar constraints. The GEA cost can be optimized very efficiently, in most cases using a small fraction of the time required by BA to obtain the optimal configuration. Despite of the algebraic nature of the cost, under general circumstances the accuracy of the obtained camera poses is very close to that obtained with classical BA methods. We also describe how to obtain accurate initializations for the camera poses incrementally using GEA and pairwise image feature correspondences, without requiring the composition of feature trackings or triangulation of scene landmarks. The resulting camera poses can be used afterwards to obtain highly accurate sparse or dense estimations of the scene structure. The techniques described are robust against outliers found by common pairwise image matching techniques.

Tesis por compendio de publicaciones / En la primera década del siglo XXI, la ley de Moore, que ha guiado el desarrollo de procesadores en los últimos cincuenta años, fue puesta en entredicho por la comunidad científica. Esto fue debido principalmente a las limitaciones físicas del silicio que provocaron un cambio de tendencia en el desarrollo de procesadores, tomando como principal estandarte para este cambio el paralelismo. Esta transición ha situado a la programación (masivamente) paralela como la única manera de extraer el máximo rendimiento de las nuevas plataformas de consumo; siendo esto fundamental para abordar los retos científicos de la actualidad. Desafortunadamente, estos retos plantean problemas cuyas necesidades computacionales están fuera del alcance de una sola máquina. Simulaciones como las tratadas en esta Tesis Doctoral, necesitan escalar a grandes centros de cálculo, cuyos costes, sólo están al alcance de grandes instituciones y gobiernos. Sin embargo, la actual situación socio-económica obliga a la utilización eficiente de los recursos. Herramientas como la computación en la nube o voluntaria ofrecen una alternativa para aprovechar al máximo los recursos computacionales de una manera flexible, rápida, económica y respetuosa con el medio ambiente. En esta Tesis Doctoral evaluamos el actual paradigma de computación descrito anteriormente, utilizando como caso de estudio un problema de alta repercusión en la sociedad como es la simulación de cribado virtual, utilizada para el descubrimiento de nuevos fármacos. El estudio ha recorrido los distintos niveles de procesamiento; partiendo por un análisis exhaustivo de las diferentes alternativas a nivel de chip disponibles en el mercado, pasando por la evaluación de los mismos en un entorno clúster, hasta escalar a niveles de computación en la nube y computación voluntaria. Como conclusión de este estudio podemos afirmar que las GPUs están a la vanguardia del desarrollo de aplicaciones científicas con patrones de cómputo masivamente paralelos y altas demandas computacionales, como es el cribado virtual. Además, nos atrevemos a afirmar, con los números mostrados en esta tesis doctoral y los resultados de estas plataformas en los últimos años, que se debería valorar su uso en la gran mayoría de campos científicos que demanden gran capacidad de cómputo. Es posible, sin embargo, que la migración de estas plataformas impliquen replantear el problema desde su origen, pero sin lugar a dudas, esto forma parte del pensamiento computacional, imprescindible en el desarrollo de aplicaciones científica en el estado actual de la computación de altas prestaciones. Por otro lado, si las ejecuciones que se quieren realizar son a mayor escala, se han de valorar diferentes alternativas computacionales diferentes a los tradicionales centros de cómputo; entre ellas la utilización de computación en la nube y la computación voluntaria. La computación en la nube puede ser una opción muy interesante si el cómputo que se desea realizar se desarrolla en periodos de tiempo intermitentes, ya que la no utilización de los recursos locales implica que la inversión económica no quede justificada. Por otro lado, la opción de usar una plataforma de computación voluntaria es muy atractiva, siempre y cuando, la aplicación que se está paralelizando admita ser portada a una plataforma de este tipo; pudiendo conseguir computación de altas prestaciones a un coste cercano a cero. Finalmente, nos gustaría subrayar que esta Tesis Doctoral ha contribuido al desarrollo de una aplicación de cribado virtual y que el uso de la misma debería de ayudar a encontrar nuevos candidatos a fármacos de manera eficiente en términos de rendimiento, energía y costes económicos. / In the first decade of the century, the Moore's Law, which has led the microprocessor design in the last fifty years, was put into question by the scientific community. This was mainly due to the physical limitations of silicon-based architectures, which caused a change in the trend of designing processors, guided by parallelism. This transition has placed (massively) programming parallel as the only way to extract the maximum performance to new consumer platforms; being this essential to address today's scientific challenges. Unfortunately, these challenges propose several issues whose computing needs are our of the scope for a single machine. Simulations, such as those discussed in this PhD Thesis, need to scale to large data centers; whose costs are only affordable for large institutions and governments. However, the current socio-economic situation requires an efficient use of resources. Tools such as cloud computing or volunteer computing offer an alternative to exploit computing resources in a flexible, fast, economical and environmentally friendly way. In this dissertation, we evaluate the current landscape of computation, previously described, using as a case study a high-impact problem for society as virtual screening. Virtual screening is a computational tool extensively used for drug discovery. The study has covered all processing levels, starting with an extensive analysis of the different commercially available alternatives at chip level, through their evaluation in a cluster environment, to scale to cloud computing and volunteer computing levels. This study concludes that GPUs are at the leading-edge of the development of scientific applications with massively parallel computing patterns and high computational demands, such as virtual screening. Moreover, this conclusion can be extended to other application fields with the same characteristics in its computation. However, migration to GPUs may cause an application redesign and even rethought, but this is actually part of computational thinking, which is now essential to develop scientific applications for the current state of high performance computing. Different alternatives to the use of a cluster need to be evaluated, such as the use of cloud computing and volunteer computing for a larger-scale executions. Cloud computing can be an interesting option if the computation you may perform is executed periodically, as the non-use of local resources implies that the economic investment is not justified. On the other hand, the option of using a volunteer computing platform looks interesting for developing some kind of hpc applications, as it is offering huge amount of hardware resource at no cost.