Métodos acotados de aplicación de reglas de evolución para la implementación de Sistemas P de Transición

La característica fundamental de la Computación Natural se basa en el empleo de conceptos, principios y mecanismos del funcionamiento de la Naturaleza. La Computación Natural -y dentro de ésta, la Computación de Membranas- surge como una posible alternativa a la computación clásica y como resultado de la búsqueda de nuevos modelos de computación que puedan superar las limitaciones presentes en los modelos convencionales. En concreto, la Computación de Membranas se originó como un intento de formular un nuevo modelo computacional inspirado en la estructura y el funcionamiento de las células biológicas: los sistemas basados en este modelo constan de una estructura de membranas que actúan a la vez como separadores y como canales de comunicación, y dentro de esa estructura se alojan multiconjuntos de objetos que evolucionan de acuerdo a unas determinadas reglas de evolución. Al conjunto de dispositivos contemplados por la Computación de Membranas se les denomina genéricamente como Sistemas P. Hasta el momento los Sistemas P sólo han sido estudiados a nivel teórico y no han sido plenamente implementados ni en medios electrónicos, ni en medios bioquímicos, sólo han sido simulados o parcialmente implementados. Por tanto, la implantación de estos sistemas es un reto de investigación abierto. Esta tesis aborda uno de los problemas que debe ser resuelto para conseguir la implantación de los Sistemas P sobre plataformas hardware. El problema concreto se centra en el modelo de los Sistemas P de Transición y surge de la necesidad de disponer de algoritmos de aplicación de reglas que, independientemente de la plataforma hardware sobre la que se implementen, cumplan los requisitos de ser no deterministas, masivamente paralelos y además su tiempo de ejecución esté estáticamente acotado. Como resultado se ha obtenido un conjunto de algoritmos (tanto para plataformas secuenciales, como para plataformas paralelas) que se adecúan a las diferentes configuraciones de los Sistemas P. ABSTRACT The main feature of Natural Computing is the use of concepts, principles and mechanisms inspired by Nature. Natural Computing and within it, Membrane Computing emerges as an potential alternative to conventional computing and as from the search for new models of computation that may overcome the existing limitations in conventional models. Specifically, Membrane Computing was created to formulate a new computational paradigm inspired by the structure and functioning of biological cells: it consists of a membrane structure, which acts as separators as well as communication channels, and within this structure are stored multisets of objects that evolve according to certain evolution rules. The set of computing devices addressed by Membrane Computing are generically known P systems. Up to now, no P systems have been fully implemented yet in electronic or biochemical means. They only have been studied in theory, simulated or partially implemented. Therefore, the implementation of these systems is an open research challenge. This thesis addresses one of the problems to be solved in order to deploy P systems on hardware platforms. This specific problem is focused on the Transition P System model and emerges from the need of providing application rules algorithms that independently on the hardware platform on which they are implemented, meets the requirements of being nondeterministic, massively parallel and runtime-bounded. As a result, this thesis has developed a set of algorithms for both platforms, sequential and parallel, adapted to all possible configurations of P systems.

Análisis y diseño de un patrón de ruido térmico de 10 MHz a 26,5 GHz en tecnología coaxial

Esta Tesis Doctoral presenta las investigaciones y los trabajos desarrollados durante los años 2008 a 2012 para el análisis y diseño de un patrón primario de ruido térmico de banda ancha en tecnología coaxial. Para ubicar esta Tesis en su campo científico es necesario tomar conciencia de que la realización de mediciones fiables y trazables forma parte del sostenimiento del bienestar de una sociedad moderna y juega un papel crítico en apoyo de la competitividad económica, la fabricación y el comercio, así como de la calidad de vida. En el mundo moderno actual, una infraestructura de medición bien desarrollada genera confianza en muchas facetas de nuestra vida diaria, porque nos permite el desarrollo y fabricación de productos fiables, innovadores y de alta calidad; porque sustenta la competitividad de las industrias y su producción sostenible; además de contribuir a la eliminación de barreras técnicas y de dar soporte a un comercio justo, garantizar la seguridad y eficacia de la asistencia sanitaria, y por supuesto, dar respuesta a los grandes retos de la sociedad moderna en temas tan complicados como la energía y el medio ambiente. Con todo esto en mente se ha desarrollado un patrón primario de ruido térmico con el fin de aportar al sistema metrológico español un nuevo patrón primario de referencia capaz de ser usado para desarrollar mediciones fiables y trazables en el campo de la medida y calibración de dispositivos de ruido electromagnético de radiofrecuencia y microondas. Este patrón se ha planteado para que cumpla en el rango de 10 MHz a 26,5 GHz con las siguientes especificaciones: Salida nominal de temperatura de ruido aproximada de ~ 83 K. Incertidumbre de temperatura de ruido menor que ± 1 K en todo su rango de frecuencias. Coeficiente de reflexión en todo su ancho de banda de 0,01 a 26,5 GHz lo más bajo posible. Se ha divido esta Tesis Doctoral en tres partes claramente diferenciadas. La primera de ellas, que comprende los capítulos 1, 2, 3, 4 y 5, presenta todo el proceso de simulaciones y ajustes de los parámetros principales del dispositivo con el fin de dejar definidos los que resultan críticos en su construcción. A continuación viene una segunda parte compuesta por el capítulo 6 en donde se desarrollan los cálculos necesarios para obtener la temperatura de ruido a la salida del dispositivo. La tercera y última parte, capítulo 7, se dedica a la estimación de la incertidumbre de la temperatura de ruido del nuevo patrón primario de ruido obtenida en el capítulo anterior. Más concretamente tenemos que en el capítulo 1 se hace una exhaustiva introducción del entorno científico en donde se desarrolla este trabajo de investigación. Además se detallan los objetivos que se persiguen y se presenta la metodología utilizada para conseguirlos. El capítulo 2 describe la caracterización y selección del material dieléctrico para el anillo del interior de la línea de transmisión del patrón que ponga en contacto térmico los dos conductores del coaxial para igualar las temperaturas entre ambos y mantener la impedancia característica de todo el patrón primario de ruido. Además se estudian las propiedades dieléctricas del nitrógeno líquido para evaluar su influencia en la impedancia final de la línea de transmisión. En el capítulo 3 se analiza el comportamiento de dos cargas y una línea de aire comerciales trabajando en condiciones criogénicas. Se pretende con este estudio obtener la variación que se produce en el coeficiente de reflexión al pasar de temperatura ambiente a criogénica y comprobar si estos dispositivos resultan dañados por trabajar a temperaturas criogénicas; además se estudia si se modifica su comportamiento tras sucesivos ciclos de enfriamiento – calentamiento, obteniendo una cota de la variación para poder así seleccionar la carga que proporcione un menor coeficiente de reflexión y una menor variabilidad. En el capítulo 4 se parte del análisis de la estructura del anillo de material dieléctrico utilizada en la nota técnica NBS 1074 del NIST con el fin de obtener sus parámetros de dispersión que nos servirán para calcular el efecto que produce sobre el coeficiente de reflexión de la estructura coaxial completa. Además se realiza un estudio posterior con el fin de mejorar el diseño de la nota técnica NBS 1074 del NIST, donde se analiza el anillo de material dieléctrico, para posteriormente realizar modificaciones en la geometría de la zona donde se encuentra éste con el fin de reducir la reflexión que produce. Concretamente se estudia el ajuste del radio del conductor interior en la zona del anillo para que presente la misma impedancia característica que la línea. Y para finalizar se obtiene analíticamente la relación entre el radio del conductor interior y el radio de la transición de anillo térmico para garantizar en todo punto de esa transición la misma impedancia característica, manteniendo además criterios de robustez del dispositivo y de fabricación realistas. En el capítulo 5 se analiza el comportamiento térmico del patrón de ruido y su influencia en la conductividad de los materiales metálicos. Se plantean las posibilidades de que el nitrógeno líquido sea exterior a la línea o que éste penetre en su interior. En ambos casos, dada la simetría rotacional del problema, se ha simulado térmicamente una sección de la línea coaxial, es decir, se ha resuelto un problema bidimensional, aunque los resultados son aplicables a la estructura real tridimensional. Para la simulación térmica se ha empleado la herramienta PDE Toolbox de Matlab®. En el capítulo 6 se calcula la temperatura de ruido a la salida del dispositivo. Se parte del estudio de la aportación a la temperatura de ruido final de cada sección que compone el patrón. Además se estudia la influencia de las variaciones de determinados parámetros de los elementos que conforman el patrón de ruido sobre las características fundamentales de éste, esto es, el coeficiente de reflexión a lo largo de todo el dispositivo. Una vez descrito el patrón de ruido electromagnético se procede, en el capítulo 7, a describir los pasos seguidos para estimar la incertidumbre de la temperatura de ruido electromagnético a su salida. Para ello se utilizan dos métodos, el clásico de la guía para la estimación de la incertidumbre [GUM95] y el método de simulación de Monte Carlo. En el capítulo 8 se describen las conclusiones y lo logros conseguidos. Durante el desarrollo de esta Tesis Doctoral se ha obtenido un dispositivo novedoso susceptible de ser patentado, que ha sido registrado en la Oficina Española de Patentes y Marcas (O.E.P.M.) en Madrid, de conformidad con lo establecido en el artículo 20 de la Ley 11/1986, de 20 de Marzo, de Patentes, con el título Patrón Primario de Ruido Térmico de Banda Ancha (Referencia P-101061) con fecha 7 de febrero de 2011. ABSTRACT This Ph. D. work describes a number of investigations that were performed along the years 2008 to 2011, as a preparation for the study and design of a coaxial cryogenic reference noise standard. Reliable and traceable measurement underpins the welfare of a modern society and plays a critical role in supporting economic competitiveness, manufacturing and trade as well as quality of life. In our modern world, a well developed measurement infrastructure gives confidence in many aspects of our daily life, for example by enabling the development and manufacturing of reliable, high quality and innovative products; by supporting industry to be competitive and sustainable in its production; by removing technical barriers to trade and supporting fair trade; by ensuring safety and effectiveness of healthcare; by giving response to the major challenges in key sectors such energy and environment, etc. With all this in mind we have developed a primary standard thermal noise with the aim of providing the Spanish metrology system with a new primary standard for noise reference. This standard will allow development of reliable and traceable measurements in the field of calibration and measurement of electromagnetic noise RF and microwave devices. This standard has been designed to work in the frequency range from 10 MHz to 26.5 GHz, meeting the following specifications: 1. Noise temperature output is to be nominally ~ 83 K. 2. Noise temperature uncertainty less than ± 1 K in the frequency range from 0.01 to 26.5 GHz. 3. Broadband performance requires as low a reflection coefficient as possible from 0.01 to 26.5 GHz. The present Ph. D. work is divided into three clearly differentiated parts. The first one, which comprises Chapters 1 to 5, presents the whole process of simulation and adjustment of the main parameters of the device in order to define those of them which are critical for the manufacturing of the device. Next, the second part consists of Chapter 6 where the necessary computations to obtain the output noise temperature of the device are carried out. The third and last part, Chapter 7, is devoted to the estimation of the uncertainty related to the noise temperature of the noise primary standard as obtained in the preceding chapter. More specifically, Chapter 1 provides a thorough introduction to the scientific and technological environment where this research takes place. It also details the objectives to be achieved and presents the methodology used to achieve them. Chapter 2 describes the characterization and selection of the bead dielectric material inside the transmission line, intended to connect the two coaxial conductors equalizing the temperature between the two of them and thus keeping the characteristic impedance constant for the whole standard. In addition the dielectric properties of liquid nitrogen are analyzed in order to assess their influence on the impedance of the transmission line. Chapter 3 analyzes the behavior of two different loads and of a commercial airline when subjected to cryogenic working conditions. This study is intended to obtain the variation in the reflection coefficient when the temperature changes from room to cryogenic temperature, and to check whether these devices can be damaged as a result of working at cryogenic temperatures. Also we try to see whether the load changes its behavior after successive cycles of cooling / heating, in order to obtain a bound for the allowed variation of the reflection coefficient of the load. Chapter 4 analyzes the ring structure of the dielectric material used in the NBS technical note 1074 of NIST, in order to obtain its scattering parameters that will be used for computation of its effect upon the reflection coefficient of the whole coaxial structure. Subsequently, we perform a further investigation with the aim of improving the design of NBS technical note 1074 of NIST, and modifications are introduced in the geometry of the transition area in order to reduce the reflection it produces. We first analyze the ring, specifically the influence of the radius of inner conductor of the bead, and then make changes in its geometry so that it presents the same characteristic impedance as that of the line. Finally we analytically obtain the relationship between the inner conductor radius and the radius of the transition from ring, in order to ensure the heat flow through the transition thus keeping the same reflection coefficient, and at the same time meeting the robustness requirements and the feasibility of manufacturing. Chapter 5 analyzes the thermal behavior of the noise standard and its influence on the conductivity of metallic materials. Both possibilities are raised that the liquid nitrogen is kept outside the line or that it penetrates inside. In both cases, given the rotational symmetry of the structure, we have simulated a section of coaxial line, i.e. the equivalent two-dimensional problem has been resolved, although the results are applicable to the actual three-dimensional structure. For thermal simulation Matlab™ PDE Toolbox has been used. In Chapter 6 we compute the output noise temperature of the device. The starting point is the analysis of the contribution to the overall noise temperature of each section making up the standard. Moreover the influence of the variations in the parameters of all elements of the standard is analyzed, specifically the variation of the reflection coefficient along the entire device. Once the electromagnetic noise standard has been described and analyzed, in Chapter 7 we describe the steps followed to estimate the uncertainty of the output electromagnetic noise temperature. This is done using two methods, the classic analytical approach following the Guide to the Estimation of Uncertainty [GUM95] and numerical simulations made with the Monte Carlo method. Chapter 8 discusses the conclusions and achievements. During the development of this thesis, a novel device was obtained which was potentially patentable, and which was finally registered through the Spanish Patent and Trademark Office (SPTO) in Madrid, in accordance with the provisions of Article 20 of Law 11/1986 about Patents, dated March 20th, 1986. It was registered under the denomination Broadband Thermal Noise Primary Standard (Reference P-101061) dated February 7th, 2011.

Side-Channel Attack Protection Techniques in FPGA Systems using Enhanced Dual-Rail Solutions

Esta tesis doctoral se centra principalmente en técnicas de ataque y contramedidas relacionadas con ataques de canal lateral (SCA por sus siglas en inglés), que han sido propuestas dentro del campo de investigación académica desde hace 17 años. Las investigaciones relacionadas han experimentado un notable crecimiento en las últimas décadas, mientras que los diseños enfocados en la protección sólida y eficaz contra dichos ataques aún se mantienen como un tema de investigación abierto, en el que se necesitan iniciativas más confiables para la protección de la información persona de empresa y de datos nacionales. El primer uso documentado de codificación secreta se remonta a alrededor de 1700 B.C., cuando los jeroglíficos del antiguo Egipto eran descritos en las inscripciones. La seguridad de la información siempre ha supuesto un factor clave en la transmisión de datos relacionados con inteligencia diplomática o militar. Debido a la evolución rápida de las técnicas modernas de comunicación, soluciones de cifrado se incorporaron por primera vez para garantizar la seguridad, integridad y confidencialidad de los contextos de transmisión a través de cables sin seguridad o medios inalámbricos. Debido a las restricciones de potencia de cálculo antes de la era del ordenador, la técnica de cifrado simple era un método más que suficiente para ocultar la información. Sin embargo, algunas vulnerabilidades algorítmicas pueden ser explotadas para restaurar la regla de codificación sin mucho esfuerzo. Esto ha motivado nuevas investigaciones en el área de la criptografía, con el fin de proteger el sistema de información ante sofisticados algoritmos. Con la invención de los ordenadores se ha acelerado en gran medida la implementación de criptografía segura, que ofrece resistencia eficiente encaminada a obtener mayores capacidades de computación altamente reforzadas. Igualmente, sofisticados cripto-análisis han impulsado las tecnologías de computación. Hoy en día, el mundo de la información ha estado involucrado con el campo de la criptografía, enfocada a proteger cualquier campo a través de diversas soluciones de cifrado. Estos enfoques se han fortalecido debido a la unificación optimizada de teorías matemáticas modernas y prácticas eficaces de hardware, siendo posible su implementación en varias plataformas (microprocesador, ASIC, FPGA, etc.). Las necesidades y requisitos de seguridad en la industria son las principales métricas de conducción en el diseño electrónico, con el objetivo de promover la fabricación de productos de gran alcance sin sacrificar la seguridad de los clientes. Sin embargo, una vulnerabilidad en la implementación práctica encontrada por el Prof. Paul Kocher, et al en 1996 implica que un circuito digital es inherentemente vulnerable a un ataque no convencional, lo cual fue nombrado posteriormente como ataque de canal lateral, debido a su fuente de análisis. Sin embargo, algunas críticas sobre los algoritmos criptográficos teóricamente seguros surgieron casi inmediatamente después de este descubrimiento. En este sentido, los circuitos digitales consisten típicamente en un gran número de celdas lógicas fundamentales (como MOS - Metal Oxide Semiconductor), construido sobre un sustrato de silicio durante la fabricación. La lógica de los circuitos se realiza en función de las innumerables conmutaciones de estas células. Este mecanismo provoca inevitablemente cierta emanación física especial que puede ser medida y correlacionada con el comportamiento interno del circuito. SCA se puede utilizar para revelar datos confidenciales (por ejemplo, la criptografía de claves), analizar la arquitectura lógica, el tiempo e incluso inyectar fallos malintencionados a los circuitos que se implementan en sistemas embebidos, como FPGAs, ASICs, o tarjetas inteligentes. Mediante el uso de la comparación de correlación entre la cantidad de fuga estimada y las fugas medidas de forma real, información confidencial puede ser reconstruida en mucho menos tiempo y computación. Para ser precisos, SCA básicamente cubre una amplia gama de tipos de ataques, como los análisis de consumo de energía y radiación ElectroMagnética (EM). Ambos se basan en análisis estadístico y, por lo tanto, requieren numerosas muestras. Los algoritmos de cifrado no están intrínsecamente preparados para ser resistentes ante SCA. Es por ello que se hace necesario durante la implementación de circuitos integrar medidas que permitan camuflar las fugas a través de "canales laterales". Las medidas contra SCA están evolucionando junto con el desarrollo de nuevas técnicas de ataque, así como la continua mejora de los dispositivos electrónicos. Las características físicas requieren contramedidas sobre la capa física, que generalmente se pueden clasificar en soluciones intrínsecas y extrínsecas. Contramedidas extrínsecas se ejecutan para confundir la fuente de ataque mediante la integración de ruido o mala alineación de la actividad interna. Comparativamente, las contramedidas intrínsecas están integradas en el propio algoritmo, para modificar la aplicación con el fin de minimizar las fugas medibles, o incluso hacer que dichas fugas no puedan ser medibles. Ocultación y Enmascaramiento son dos técnicas típicas incluidas en esta categoría. Concretamente, el enmascaramiento se aplica a nivel algorítmico, para alterar los datos intermedios sensibles con una máscara de manera reversible. A diferencia del enmascaramiento lineal, las operaciones no lineales que ampliamente existen en criptografías modernas son difíciles de enmascarar. Dicho método de ocultación, que ha sido verificado como una solución efectiva, comprende principalmente la codificación en doble carril, que está ideado especialmente para aplanar o eliminar la fuga dependiente de dato en potencia o en EM. En esta tesis doctoral, además de la descripción de las metodologías de ataque, se han dedicado grandes esfuerzos sobre la estructura del prototipo de la lógica propuesta, con el fin de realizar investigaciones enfocadas a la seguridad sobre contramedidas de arquitectura a nivel lógico. Una característica de SCA reside en el formato de las fuentes de fugas. Un típico ataque de canal lateral se refiere al análisis basado en la potencia, donde la capacidad fundamental del transistor MOS y otras capacidades parásitas son las fuentes esenciales de fugas. Por lo tanto, una lógica robusta resistente a SCA debe eliminar o mitigar las fugas de estas micro-unidades, como las puertas lógicas básicas, los puertos I/O y las rutas. Las herramientas EDA proporcionadas por los vendedores manipulan la lógica desde un nivel más alto, en lugar de realizarlo desde el nivel de puerta, donde las fugas de canal lateral se manifiestan. Por lo tanto, las implementaciones clásicas apenas satisfacen estas necesidades e inevitablemente atrofian el prototipo. Por todo ello, la implementación de un esquema de diseño personalizado y flexible ha de ser tomado en cuenta. En esta tesis se presenta el diseño y la implementación de una lógica innovadora para contrarrestar SCA, en la que se abordan 3 aspectos fundamentales: I. Se basa en ocultar la estrategia sobre el circuito en doble carril a nivel de puerta para obtener dinámicamente el equilibrio de las fugas en las capas inferiores; II. Esta lógica explota las características de la arquitectura de las FPGAs, para reducir al mínimo el gasto de recursos en la implementación; III. Se apoya en un conjunto de herramientas asistentes personalizadas, incorporadas al flujo genérico de diseño sobre FPGAs, con el fin de manipular los circuitos de forma automática. El kit de herramientas de diseño automático es compatible con la lógica de doble carril propuesta, para facilitar la aplicación práctica sobre la familia de FPGA del fabricante Xilinx. En este sentido, la metodología y las herramientas son flexibles para ser extendido a una amplia gama de aplicaciones en las que se desean obtener restricciones mucho más rígidas y sofisticadas a nivel de puerta o rutado. En esta tesis se realiza un gran esfuerzo para facilitar el proceso de implementación y reparación de lógica de doble carril genérica. La viabilidad de las soluciones propuestas es validada mediante la selección de algoritmos criptográficos ampliamente utilizados, y su evaluación exhaustiva en comparación con soluciones anteriores. Todas las propuestas están respaldadas eficazmente a través de ataques experimentales con el fin de validar las ventajas de seguridad del sistema. El presente trabajo de investigación tiene la intención de cerrar la brecha entre las barreras de implementación y la aplicación efectiva de lógica de doble carril. En esencia, a lo largo de esta tesis se describirá un conjunto de herramientas de implementación para FPGAs que se han desarrollado para trabajar junto con el flujo de diseño genérico de las mismas, con el fin de lograr crear de forma innovadora la lógica de doble carril. Un nuevo enfoque en el ámbito de la seguridad en el cifrado se propone para obtener personalización, automatización y flexibilidad en el prototipo de circuito de bajo nivel con granularidad fina. Las principales contribuciones del presente trabajo de investigación se resumen brevemente a continuación: Lógica de Precharge Absorbed-DPL logic: El uso de la conversión de netlist para reservar LUTs libres para ejecutar la señal de precharge y Ex en una lógica DPL. Posicionamiento entrelazado Row-crossed con pares idénticos de rutado en redes de doble carril, lo que ayuda a aumentar la resistencia frente a la medición EM selectiva y mitigar los impactos de las variaciones de proceso. Ejecución personalizada y herramientas de conversión automática para la generación de redes idénticas para la lógica de doble carril propuesta. (a) Para detectar y reparar conflictos en las conexiones; (b) Detectar y reparar las rutas asimétricas. (c) Para ser utilizado en otras lógicas donde se requiere un control estricto de las interconexiones en aplicaciones basadas en Xilinx. Plataforma CPA de pruebas personalizadas para el análisis de EM y potencia, incluyendo la construcción de dicha plataforma, el método de medición y análisis de los ataques. Análisis de tiempos para cuantificar los niveles de seguridad. División de Seguridad en la conversión parcial de un sistema de cifrado complejo para reducir los costes de la protección. Prueba de concepto de un sistema de calefacción auto-adaptativo para mitigar los impactos eléctricos debido a la variación del proceso de silicio de manera dinámica. La presente tesis doctoral se encuentra organizada tal y como se detalla a continuación: En el capítulo 1 se abordan los fundamentos de los ataques de canal lateral, que abarca desde conceptos básicos de teoría de modelos de análisis, además de la implementación de la plataforma y la ejecución de los ataques. En el capítulo 2 se incluyen las estrategias de resistencia SCA contra los ataques de potencia diferencial y de EM. Además de ello, en este capítulo se propone una lógica en doble carril compacta y segura como contribución de gran relevancia, así como también se presentará la transformación lógica basada en un diseño a nivel de puerta. Por otra parte, en el Capítulo 3 se abordan los desafíos relacionados con la implementación de lógica en doble carril genérica. Así mismo, se describirá un flujo de diseño personalizado para resolver los problemas de aplicación junto con una herramienta de desarrollo automático de aplicaciones propuesta, para mitigar las barreras de diseño y facilitar los procesos. En el capítulo 4 se describe de forma detallada la elaboración e implementación de las herramientas propuestas. Por otra parte, la verificación y validaciones de seguridad de la lógica propuesta, así como un sofisticado experimento de verificación de la seguridad del rutado, se describen en el capítulo 5. Por último, un resumen de las conclusiones de la tesis y las perspectivas como líneas futuras se incluyen en el capítulo 6. Con el fin de profundizar en el contenido de la tesis doctoral, cada capítulo se describe de forma más detallada a continuación: En el capítulo 1 se introduce plataforma de implementación hardware además las teorías básicas de ataque de canal lateral, y contiene principalmente: (a) La arquitectura genérica y las características de la FPGA a utilizar, en particular la Xilinx Virtex-5; (b) El algoritmo de cifrado seleccionado (un módulo comercial Advanced Encryption Standard (AES)); (c) Los elementos esenciales de los métodos de canal lateral, que permiten revelar las fugas de disipación correlacionadas con los comportamientos internos; y el método para recuperar esta relación entre las fluctuaciones físicas en los rastros de canal lateral y los datos internos procesados; (d) Las configuraciones de las plataformas de pruebas de potencia / EM abarcadas dentro de la presente tesis. El contenido de esta tesis se amplia y profundiza a partir del capítulo 2, en el cual se abordan varios aspectos claves. En primer lugar, el principio de protección de la compensación dinámica de la lógica genérica de precarga de doble carril (Dual-rail Precharge Logic-DPL) se explica mediante la descripción de los elementos compensados a nivel de puerta. En segundo lugar, la lógica PA-DPL es propuesta como aportación original, detallando el protocolo de la lógica y un caso de aplicación. En tercer lugar, dos flujos de diseño personalizados se muestran para realizar la conversión de doble carril. Junto con ello, se aclaran las definiciones técnicas relacionadas con la manipulación por encima de la netlist a nivel de LUT. Finalmente, una breve discusión sobre el proceso global se aborda en la parte final del capítulo. El Capítulo 3 estudia los principales retos durante la implementación de DPLs en FPGAs. El nivel de seguridad de las soluciones de resistencia a SCA encontradas en el estado del arte se ha degenerado debido a las barreras de implantación a través de herramientas EDA convencionales. En el escenario de la arquitectura FPGA estudiada, se discuten los problemas de los formatos de doble carril, impactos parásitos, sesgo tecnológico y la viabilidad de implementación. De acuerdo con estas elaboraciones, se plantean dos problemas: Cómo implementar la lógica propuesta sin penalizar los niveles de seguridad, y cómo manipular un gran número de celdas y automatizar el proceso. El PA-DPL propuesto en el capítulo 2 se valida con una serie de iniciativas, desde características estructurales como doble carril entrelazado o redes de rutado clonadas, hasta los métodos de aplicación tales como las herramientas de personalización y automatización de EDA. Por otra parte, un sistema de calefacción auto-adaptativo es representado y aplicado a una lógica de doble núcleo, con el fin de ajustar alternativamente la temperatura local para equilibrar los impactos negativos de la variación del proceso durante la operación en tiempo real. El capítulo 4 se centra en los detalles de la implementación del kit de herramientas. Desarrollado sobre una API third-party, el kit de herramientas personalizado es capaz de manipular los elementos de la lógica de circuito post P&R ncd (una versión binaria ilegible del xdl) convertido al formato XDL Xilinx. El mecanismo y razón de ser del conjunto de instrumentos propuestos son cuidadosamente descritos, que cubre la detección de enrutamiento y los enfoques para la reparación. El conjunto de herramientas desarrollado tiene como objetivo lograr redes de enrutamiento estrictamente idénticos para la lógica de doble carril, tanto para posicionamiento separado como para el entrelazado. Este capítulo particularmente especifica las bases técnicas para apoyar las implementaciones en los dispositivos de Xilinx y su flexibilidad para ser utilizado sobre otras aplicaciones. El capítulo 5 se enfoca en la aplicación de los casos de estudio para la validación de los grados de seguridad de la lógica propuesta. Se discuten los problemas técnicos detallados durante la ejecución y algunas nuevas técnicas de implementación. (a) Se discute el impacto en el proceso de posicionamiento de la lógica utilizando el kit de herramientas propuesto. Diferentes esquemas de implementación, tomando en cuenta la optimización global en seguridad y coste, se verifican con los experimentos con el fin de encontrar los planes de posicionamiento y reparación optimizados; (b) las validaciones de seguridad se realizan con los métodos de correlación y análisis de tiempo; (c) Una táctica asintótica se aplica a un núcleo AES sobre BCDL estructurado para validar de forma sofisticada el impacto de enrutamiento sobre métricas de seguridad; (d) Los resultados preliminares utilizando el sistema de calefacción auto-adaptativa sobre la variación del proceso son mostrados; (e) Se introduce una aplicación práctica de las herramientas para un diseño de cifrado completa. Capítulo 6 incluye el resumen general del trabajo presentado dentro de esta tesis doctoral. Por último, una breve perspectiva del trabajo futuro se expone, lo que puede ampliar el potencial de utilización de las contribuciones de esta tesis a un alcance más allá de los dominios de la criptografía en FPGAs. ABSTRACT This PhD thesis mainly concentrates on countermeasure techniques related to the Side Channel Attack (SCA), which has been put forward to academic exploitations since 17 years ago. The related research has seen a remarkable growth in the past decades, while the design of solid and efficient protection still curiously remain as an open research topic where more reliable initiatives are required for personal information privacy, enterprise and national data protections. The earliest documented usage of secret code can be traced back to around 1700 B.C., when the hieroglyphs in ancient Egypt are scribed in inscriptions. Information security always gained serious attention from diplomatic or military intelligence transmission. Due to the rapid evolvement of modern communication technique, crypto solution was first incorporated by electronic signal to ensure the confidentiality, integrity, availability, authenticity and non-repudiation of the transmitted contexts over unsecure cable or wireless channels. Restricted to the computation power before computer era, simple encryption tricks were practically sufficient to conceal information. However, algorithmic vulnerabilities can be excavated to restore the encoding rules with affordable efforts. This fact motivated the development of modern cryptography, aiming at guarding information system by complex and advanced algorithms. The appearance of computers has greatly pushed forward the invention of robust cryptographies, which efficiently offers resistance relying on highly strengthened computing capabilities. Likewise, advanced cryptanalysis has greatly driven the computing technologies in turn. Nowadays, the information world has been involved into a crypto world, protecting any fields by pervasive crypto solutions. These approaches are strong because of the optimized mergence between modern mathematical theories and effective hardware practices, being capable of implement crypto theories into various platforms (microprocessor, ASIC, FPGA, etc). Security needs from industries are actually the major driving metrics in electronic design, aiming at promoting the construction of systems with high performance without sacrificing security. Yet a vulnerability in practical implementation found by Prof. Paul Kocher, et al in 1996 implies that modern digital circuits are inherently vulnerable to an unconventional attack approach, which was named as side-channel attack since then from its analysis source. Critical suspicions to theoretically sound modern crypto algorithms surfaced almost immediately after this discovery. To be specifically, digital circuits typically consist of a great number of essential logic elements (as MOS - Metal Oxide Semiconductor), built upon a silicon substrate during the fabrication. Circuit logic is realized relying on the countless switch actions of these cells. This mechanism inevitably results in featured physical emanation that can be properly measured and correlated with internal circuit behaviors. SCAs can be used to reveal the confidential data (e.g. crypto-key), analyze the logic architecture, timing and even inject malicious faults to the circuits that are implemented in hardware system, like FPGA, ASIC, smart Card. Using various comparison solutions between the predicted leakage quantity and the measured leakage, secrets can be reconstructed at much less expense of time and computation. To be precisely, SCA basically encloses a wide range of attack types, typically as the analyses of power consumption or electromagnetic (EM) radiation. Both of them rely on statistical analyses, and hence require a number of samples. The crypto algorithms are not intrinsically fortified with SCA-resistance. Because of the severity, much attention has to be taken into the implementation so as to assemble countermeasures to camouflage the leakages via "side channels". Countermeasures against SCA are evolving along with the development of attack techniques. The physical characteristics requires countermeasures over physical layer, which can be generally classified into intrinsic and extrinsic vectors. Extrinsic countermeasures are executed to confuse the attacker by integrating noise, misalignment to the intra activities. Comparatively, intrinsic countermeasures are built into the algorithm itself, to modify the implementation for minimizing the measurable leakage, or making them not sensitive any more. Hiding and Masking are two typical techniques in this category. Concretely, masking applies to the algorithmic level, to alter the sensitive intermediate values with a mask in reversible ways. Unlike the linear masking, non-linear operations that widely exist in modern cryptographies are difficult to be masked. Approved to be an effective counter solution, hiding method mainly mentions dual-rail logic, which is specially devised for flattening or removing the data-dependent leakage in power or EM signatures. In this thesis, apart from the context describing the attack methodologies, efforts have also been dedicated to logic prototype, to mount extensive security investigations to countermeasures on logic-level. A characteristic of SCA resides on the format of leak sources. Typical side-channel attack concerns the power based analysis, where the fundamental capacitance from MOS transistors and other parasitic capacitances are the essential leak sources. Hence, a robust SCA-resistant logic must eliminate or mitigate the leakages from these micro units, such as basic logic gates, I/O ports and routings. The vendor provided EDA tools manipulate the logic from a higher behavioral-level, rather than the lower gate-level where side-channel leakage is generated. So, the classical implementations barely satisfy these needs and inevitably stunt the prototype. In this case, a customized and flexible design scheme is appealing to be devised. This thesis profiles an innovative logic style to counter SCA, which mainly addresses three major aspects: I. The proposed logic is based on the hiding strategy over gate-level dual-rail style to dynamically overbalance side-channel leakage from lower circuit layer; II. This logic exploits architectural features of modern FPGAs, to minimize the implementation expenses; III. It is supported by a set of assistant custom tools, incorporated by the generic FPGA design flow, to have circuit manipulations in an automatic manner. The automatic design toolkit supports the proposed dual-rail logic, facilitating the practical implementation on Xilinx FPGA families. While the methodologies and the tools are flexible to be expanded to a wide range of applications where rigid and sophisticated gate- or routing- constraints are desired. In this thesis a great effort is done to streamline the implementation workflow of generic dual-rail logic. The feasibility of the proposed solutions is validated by selected and widely used crypto algorithm, for thorough and fair evaluation w.r.t. prior solutions. All the proposals are effectively verified by security experiments. The presented research work attempts to solve the implementation troubles. The essence that will be formalized along this thesis is that a customized execution toolkit for modern FPGA systems is developed to work together with the generic FPGA design flow for creating innovative dual-rail logic. A method in crypto security area is constructed to obtain customization, automation and flexibility in low-level circuit prototype with fine-granularity in intractable routings. Main contributions of the presented work are summarized next: Precharge Absorbed-DPL logic: Using the netlist conversion to reserve free LUT inputs to execute the Precharge and Ex signal in a dual-rail logic style. A row-crossed interleaved placement method with identical routing pairs in dual-rail networks, which helps to increase the resistance against selective EM measurement and mitigate the impacts from process variations. Customized execution and automatic transformation tools for producing identical networks for the proposed dual-rail logic. (a) To detect and repair the conflict nets; (b) To detect and repair the asymmetric nets. (c) To be used in other logics where strict network control is required in Xilinx scenario. Customized correlation analysis testbed for EM and power attacks, including the platform construction, measurement method and attack analysis. A timing analysis based method for quantifying the security grades. A methodology of security partitions of complex crypto systems for reducing the protection cost. A proof-of-concept self-adaptive heating system to mitigate electrical impacts over process variations in dynamic dual-rail compensation manner. The thesis chapters are organized as follows: Chapter 1 discusses the side-channel attack fundamentals, which covers from theoretic basics to analysis models, and further to platform setup and attack execution. Chapter 2 centers to SCA-resistant strategies against generic power and EM attacks. In this chapter, a major contribution, a compact and secure dual-rail logic style, will be originally proposed. The logic transformation based on bottom-layer design will be presented. Chapter 3 is scheduled to elaborate the implementation challenges of generic dual-rail styles. A customized design flow to solve the implementation problems will be described along with a self-developed automatic implementation toolkit, for mitigating the design barriers and facilitating the processes. Chapter 4 will originally elaborate the tool specifics and construction details. The implementation case studies and security validations for the proposed logic style, as well as a sophisticated routing verification experiment, will be described in Chapter 5. Finally, a summary of thesis conclusions and perspectives for future work are included in Chapter 5. To better exhibit the thesis contents, each chapter is further described next: Chapter 1 provides the introduction of hardware implementation testbed and side-channel attack fundamentals, and mainly contains: (a) The FPGA generic architecture and device features, particularly of Virtex-5 FPGA; (b) The selected crypto algorithm - a commercially and extensively used Advanced Encryption Standard (AES) module - is detailed; (c) The essentials of Side-Channel methods are profiled. It reveals the correlated dissipation leakage to the internal behaviors, and the method to recover this relationship between the physical fluctuations in side-channel traces and the intra processed data; (d) The setups of the power/EM testing platforms enclosed inside the thesis work are given. The content of this thesis is expanded and deepened from chapter 2, which is divided into several aspects. First, the protection principle of dynamic compensation of the generic dual-rail precharge logic is explained by describing the compensated gate-level elements. Second, the novel DPL is originally proposed by detailing the logic protocol and an implementation case study. Third, a couple of custom workflows are shown next for realizing the rail conversion. Meanwhile, the technical definitions that are about to be manipulated above LUT-level netlist are clarified. A brief discussion about the batched process is given in the final part. Chapter 3 studies the implementation challenges of DPLs in FPGAs. The security level of state-of-the-art SCA-resistant solutions are decreased due to the implementation barriers using conventional EDA tools. In the studied FPGA scenario, problems are discussed from dual-rail format, parasitic impact, technological bias and implementation feasibility. According to these elaborations, two problems arise: How to implement the proposed logic without crippling the security level; and How to manipulate a large number of cells and automate the transformation. The proposed PA-DPL in chapter 2 is legalized with a series of initiatives, from structures to implementation methods. Furthermore, a self-adaptive heating system is depicted and implemented to a dual-core logic, assumed to alternatively adjust local temperature for balancing the negative impacts from silicon technological biases on real-time. Chapter 4 centers to the toolkit system. Built upon a third-party Application Program Interface (API) library, the customized toolkit is able to manipulate the logic elements from post P&R circuit (an unreadable binary version of the xdl one) converted to Xilinx xdl format. The mechanism and rationale of the proposed toolkit are carefully convoyed, covering the routing detection and repairing approaches. The developed toolkit aims to achieve very strictly identical routing networks for dual-rail logic both for separate and interleaved placement. This chapter particularly specifies the technical essentials to support the implementations in Xilinx devices and the flexibility to be expanded to other applications. Chapter 5 focuses on the implementation of the case studies for validating the security grades of the proposed logic style from the proposed toolkit. Comprehensive implementation techniques are discussed. (a) The placement impacts using the proposed toolkit are discussed. Different execution schemes, considering the global optimization in security and cost, are verified with experiments so as to find the optimized placement and repair schemes; (b) Security validations are realized with correlation, timing methods; (c) A systematic method is applied to a BCDL structured module to validate the routing impact over security metric; (d) The preliminary results using the self-adaptive heating system over process variation is given; (e) A practical implementation of the proposed toolkit to a large design is introduced. Chapter 6 includes the general summary of the complete work presented inside this thesis. Finally, a brief perspective for the future work is drawn which might expand the potential utilization of the thesis contributions to a wider range of implementation domains beyond cryptography on FPGAs.

Sensing Aeropolis. Urban air monitoring devices in Madrid, 2006-2010

Esta tesis examina las implicaciones técnicas, políticas y espaciales del aire urbano, y en concreto, de la calidad del aire, para tenerlo en cuenta desde una perspectiva arquitectónica. En oposición a formas de entender el aire como un vacío o como una metáfora, este proyecto propone abordarlo desde un acercamiento material y tecnológico, trayendo el entorno al primer plano y reconociendo sus múltiples agencias. Debido a la escasa bibliografía detectada en el campo de la arquitectura, el objetivo es construir un marco teórico-analítico para considerar el aire urbano. Para ello el trabajo construye Aeropolis, una metáfora heurística que describe el ensamblaje sociotecnico de la ciudad. Situada en la intersección de determinadas ramas de la filosofía de la cultura, los estudios sobre ciencia y tecnología y estudios feministas de la ciencia este nuevo paisaje conceptual ofrece una metodología y herramientas para abordar el objeto de estudio desde distintos ángulos. Estas herramientas metodológicas han sido desarrolladas en el contexto específico de Madrid, ciudad muy contaminada cuyo aire ha sido objeto de controversias políticas y sociales, y donde las políticas y tecnologías para reducir sus niveles no han sido exitosas. Para encontrar una implicación alternativa con el aire esta tesis propone un método de investigación de agentes invisibles a partir del análisis de sus dispositivos epistémicos. Se centra, en concreto, en los instrumentos que miden, visualizan y comunican la calidad del aire, proponiendo que no sólo lo representan, sino que son también instrumentos que diseñan el aire y la ciudad. La noción de “sensing” (en castellano medir y sentir) es expandida, reconociendo distintas prácticas que reconstruyen el aire de Madrid. El resultado de esta estrategia no es sólo la ampliación de los espacios desde los que relacionarnos con el aire, sino también la legitimación de prácticas existentes fuera de contextos científicos y administrativos, como por ejemplo prácticas relacionadas con el cuerpo, así como la redistribución de agencias entre más actores. Así, esta tesis trata sobre toxicidad, la Unión Europea, producción colaborativa, modelos de computación, dolores de cabeza, kits DIY, gases, cuerpos humanos, salas de control, sangre o políticos, entre otros. Los dispositivos que sirven de datos empíricos sirven como un ejemplo excepcional para investigar infraestructuras digitales, permitiendo desafiar nociones sobre Ciudades Inteligentes. La tesis pone especial atención en los efectos del aire en el espacio público, reconociendo los procesos de invisibilización que han sufrido sus infraestructuras de monitorización. Para terminar se exponen líneas de trabajo y oportunidades para la arquitectura y el diseño urbano a través de nuevas relaciones entre infraestructuras urbanas, el medio construido, espacios domésticos y públicos y humanos y no humanos, para crear nuevas ecologías políticas urbanas (queer). ABSTRACT This thesis examines the technical, political and spatial implications of urban air, and more specifically "air quality", in order to consider it from an architectural perspective. In opposition to understandings of the air either as a void or as a metaphor, this project proposes to inspect it from a material and technical approach, bringing the background to the fore and acknowledging its multiple agencies. Due to the scarce bibliography within the architectural field, its first aim is to construct a theoretical and analytical framework from which to consider urban air. For this purpose, the work attempts the construction of Aeropolis, a heuristic metaphor that describes the city's aero socio-material assemblage. Located at the intersection of certain currents in cultural philosophy, science and technology studies as well as feminist studies in technoscience, this framework enables a methodology and toolset to be extracted in order to approach the subject matter from different angles. The methodological tools stemming from this purpose-built framework were put to the test in a specific case study: Madrid, a highly polluted city whose air has been subject to political and social controversies, and where no effective policies or technologies have been successful in reducing its levels of pollution. In order to engage with the air, the thesis suggests a method for researching invisible agents by examining the epistemic devices involved. It locates and focuses on the instruments that sense, visualise and communicate urban air, claiming that they do not only represent it, but are also instruments that design the air and the city. The notion of "sensing" is then expanded by recognising different practices which enact the air in Madrid. The work claims that the result of this is not only the opening up of spaces for engagement but also the legitimisation of existing practices outside science and policymaking environments, such as embodied practices, as well as the redistribution of agency among more actors. So this is a thesis about toxicity, the European Union, collaborative production, scientific computational models, headaches, DIY kits, gases, human bodies, control rooms, blood, or politicians, among many others. The devices found throughout the work serve as an exceptional substrate for an investigation of digital infrastructures, enabling to challenge Smart City tropes. There is special attention paid to the effects of the air on the public space, acknowledging the silencing processes these infrastructures have been subjected to. Finally there is an outline of the opportunities arising for architecture and urban design when taking the air into account, to create new (queer) urban political ecologies between the air, urban infrastructures, the built environment, public and domestic spaces, and humans and more than humans.

High Efficiency Envelope Amplifier based on a Ripple Cancellation Buck Converter. Design, Optimization and Integration in an EER RFPA

Durante los últimos años la tendencia en el sector de las telecomunicaciones ha sido un aumento y diversificación en la transmisión de voz, video y fundamentalmente de datos. Para conseguir alcanzar las tasas de transmisión requeridas, los nuevos estándares de comunicaciones requieren un mayor ancho de banda y tienen un mayor factor de pico, lo cual influye en el bajo rendimiento del amplificador de radiofrecuencia (RFPA). Otro factor que ha influido en el bajo rendimiento es el diseño del amplificador de radiofrecuencia. Tradicionalmente se han utilizado amplificadores lineales por su buen funcionamiento. Sin embargo, debido al elevado factor de pico de las señales transmitidas, el rendimiento de este tipo de amplificadores es bajo. El bajo rendimiento del sistema conlleva desventajas adicionales como el aumento del coste y del tamaño del sistema de refrigeración, como en el caso de una estación base, o como la reducción del tiempo de uso y un mayor calentamiento del equipo para sistemas portátiles alimentados con baterías. Debido a estos factores, se han desarrollado durante las últimas décadas varias soluciones para aumentar el rendimiento del RFPA como la técnica de Outphasing, combinadores de potencia o la técnica de Doherty. Estas soluciones mejoran las prestaciones del RFPA y en algún caso han sido ampliamente utilizados comercialmente como la técnica de Doherty, que alcanza rendimientos hasta del 50% para el sistema completo para anchos de banda de hasta 20MHz. Pese a las mejoras obtenidas con estas soluciones, los mayores rendimientos del sistema se obtienen para soluciones basadas en la modulación de la tensión de alimentación del amplificador de potencia como “Envelope Tracking” o “EER”. La técnica de seguimiento de envolvente o “Envelope Tracking” está basada en la modulación de la tensión de alimentación de un amplificador lineal de potencia para obtener una mejora en el rendimiento en el sistema comparado a una solución con una tensión de alimentación constante. Para la implementación de esta técnica se necesita una etapa adicional, el amplificador de envolvente, que añade complejidad al amplificador de radiofrecuencia. En un amplificador diseñado con esta técnica, se aumentan las pérdidas debido a la etapa adicional que supone el amplificador de envolvente pero a su vez disminuyen las pérdidas en el amplificador de potencia. Si el diseño se optimiza adecuadamente, puede conseguirse un aumento global en el rendimiento del sistema superior al conseguido con las técnicas mencionadas anteriormente. Esta técnica presenta ventajas en el diseño del amplificador de envolvente, ya que el ancho de banda requerido puede ser menor que el ancho de banda de la señal de envolvente si se optimiza adecuadamente el diseño. Adicionalmente, debido a que la sincronización entre la señal de envolvente y de fase no tiene que ser perfecta, el proceso de integración conlleva ciertas ventajas respecto a otras técnicas como EER. La técnica de eliminación y restauración de envolvente, llamada EER o técnica de Kahn está basada en modulación simultánea de la envolvente y la fase de la señal usando un amplificador de potencia conmutado, no lineal y que permite obtener un elevado rendimiento. Esta solución fue propuesta en el año 1952, pero no ha sido implementada con éxito durante muchos años debido a los exigentes requerimientos en cuanto a la sincronización entre fase y envolvente, a las técnicas de control y de corrección de los errores y no linealidades de cada una de las etapas así como de los equipos para poder implementar estas técnicas, que tienen unos requerimientos exigentes en capacidad de cálculo y procesamiento. Dentro del diseño de un RFPA, el amplificador de envolvente tiene una gran importancia debido a su influencia en el rendimiento y ancho de banda del sistema completo. Adicionalmente, la linealidad y la calidad de la señal de transmitida deben ser elevados para poder cumplir con los diferentes estándares de telecomunicaciones. Esta tesis se centra en el amplificador de envolvente y el objetivo principal es el desarrollo de soluciones que permitan el aumento del rendimiento total del sistema a la vez que satisfagan los requerimientos de ancho de banda, calidad de la señal transmitida y de linealidad. Debido al elevado rendimiento que potencialmente puede alcanzarse con la técnica de EER, esta técnica ha sido objeto de análisis y en el estado del arte pueden encontrarse numerosas referencias que analizan el diseño y proponen diversas implementaciones. En una clasificación de alto nivel, podemos agrupar las soluciones propuestas del amplificador de envolvente según estén compuestas de una o múltiples etapas. Las soluciones para el amplificador de envolvente en una configuración multietapa se basan en la combinación de un convertidor conmutado, de elevado rendimiento con un regulador lineal, de alto ancho de banda, en una combinación serie o paralelo. Estas soluciones, debido a la combinación de las características de ambas etapas, proporcionan un buen compromiso entre rendimiento y buen funcionamiento del amplificador de RF. Por otro lado, la complejidad del sistema aumenta debido al mayor número de componentes y de señales de control necesarias y el aumento de rendimiento que se consigue con estas soluciones es limitado. Una configuración en una etapa tiene las ventajas de una mayor simplicidad, pero debido al elevado ancho de banda necesario, la frecuencia de conmutación debe aumentarse en gran medida. Esto implicará un bajo rendimiento y un peor funcionamiento del amplificador de envolvente. En el estado del arte pueden encontrarse diversas soluciones para un amplificador de envolvente en una etapa, como aumentar la frecuencia de conmutación y realizar la implementación en un circuito integrado, que tendrá mejor funcionamiento a altas frecuencias o utilizar técnicas topológicas y/o filtros de orden elevado, que permiten una reducción de la frecuencia de conmutación. En esta tesis se propone de manera original el uso de la técnica de cancelación de rizado, aplicado al convertidor reductor síncrono, para reducir la frecuencia de conmutación comparado con diseño equivalente del convertidor reductor convencional. Adicionalmente se han desarrollado dos variantes topológicas basadas en esta solución para aumentar la robustez y las prestaciones de la misma. Otro punto de interés en el diseño de un RFPA es la dificultad de poder estimar la influencia de los parámetros de diseño del amplificador de envolvente en el amplificador final integrado. En esta tesis se ha abordado este problema y se ha desarrollado una herramienta de diseño que permite obtener las principales figuras de mérito del amplificador integrado para la técnica de EER a partir del diseño del amplificador de envolvente. Mediante el uso de esta herramienta pueden validarse el efecto del ancho de banda, el rizado de tensión de salida o las no linealidades del diseño del amplificador de envolvente para varias modulaciones digitales. Las principales contribuciones originales de esta tesis son las siguientes: La aplicación de la técnica de cancelación de rizado a un convertidor reductor síncrono para un amplificador de envolvente de alto rendimiento para un RFPA linealizado mediante la técnica de EER. Una reducción del 66% en la frecuencia de conmutación, comparado con el reductor convencional equivalente. Esta reducción se ha validado experimentalmente obteniéndose una mejora en el rendimiento de entre el 12.4% y el 16% para las especificaciones de este trabajo. La topología y el diseño del convertidor reductor con dos redes de cancelación de rizado en cascada para mejorar el funcionamiento y robustez de la solución con una red de cancelación. La combinación de un convertidor redactor multifase con la técnica de cancelación de rizado para obtener una topología que proporciona una reducción del cociente entre frecuencia de conmutación y ancho de banda de la señal. El proceso de optimización del control del amplificador de envolvente en lazo cerrado para mejorar el funcionamiento respecto a la solución en lazo abierto del convertidor reductor con red de cancelación de rizado. Una herramienta de simulación para optimizar el proceso de diseño del amplificador de envolvente mediante la estimación de las figuras de mérito del RFPA, implementado mediante EER, basada en el diseño del amplificador de envolvente. La integración y caracterización del amplificador de envolvente basado en un convertidor reductor con red de cancelación de rizado en el transmisor de radiofrecuencia completo consiguiendo un elevado rendimiento, entre 57% y 70.6% para potencias de salida de 14.4W y 40.7W respectivamente. Esta tesis se divide en seis capítulos. El primer capítulo aborda la introducción enfocada en la aplicación, los amplificadores de potencia de radiofrecuencia, así como los principales problemas, retos y soluciones existentes. En el capítulo dos se desarrolla el estado del arte de amplificadores de potencia de RF, describiéndose las principales técnicas de diseño, las causas de no linealidad y las técnicas de optimización. El capítulo tres está centrado en las soluciones propuestas para el amplificador de envolvente. El modo de control se ha abordado en este capítulo y se ha presentado una optimización del diseño en lazo cerrado para el convertidor reductor convencional y para el convertidor reductor con red de cancelación de rizado. El capítulo cuatro se centra en el proceso de diseño del amplificador de envolvente. Se ha desarrollado una herramienta de diseño para evaluar la influencia del amplificador de envolvente en las figuras de mérito del RFPA. En el capítulo cinco se presenta el proceso de integración realizado y las pruebas realizadas para las diversas modulaciones, así como la completa caracterización y análisis del amplificador de RF. El capítulo seis describe las principales conclusiones de la tesis y las líneas futuras. ABSTRACT The trend in the telecommunications sector during the last years follow a high increase in the transmission rate of voice, video and mainly in data. To achieve the required levels of data rates, the new modulation standards demand higher bandwidths and have a higher peak to average power ratio (PAPR). These specifications have a direct impact in the low efficiency of the RFPA. An additional factor for the low efficiency of the RFPA is in the power amplifier design. Traditionally, linear classes have been used for the implementation of the power amplifier as they comply with the technical requirements. However, they have a low efficiency, especially in the operating range of signals with a high PAPR. The low efficiency of the transmitter has additional disadvantages as an increase in the cost and size as the cooling system needs to be increased for a base station and a temperature increase and a lower use time for portable devices. Several solutions have been proposed in the state of the art to improve the efficiency of the transmitter as Outphasing, power combiners or Doherty technique. However, the highest potential of efficiency improvement can be obtained using a modulated power supply for the power amplifier, as in the Envelope Tracking and EER techniques. The Envelope Tracking technique is based on the modulation of the power supply of a linear power amplifier to improve the overall efficiency compared to a fixed voltage supply. In the implementation of this technique an additional stage is needed, the envelope amplifier, that will increase the complexity of the RFPA. However, the efficiency of the linear power amplifier will increase and, if designed properly, the RFPA efficiency will be improved. The advantages of this technique are that the envelope amplifier design does not require such a high bandwidth as the envelope signal and that in the integration process a perfect synchronization between envelope and phase is not required. The Envelope Elimination and Restoration (EER) technique, known also as Kahn’s technique, is based on the simultaneous modulation of envelope and phase using a high efficiency switched power amplifier. This solution has the highest potential in terms of the efficiency improvement but also has the most challenging specifications. This solution, proposed in 1952, has not been successfully implemented until the last two decades due to the high demanding requirements for each of the stages as well as for the highly demanding processing and computation capabilities needed. At the system level, a very precise synchronization is required between the envelope and phase paths to avoid a linearity decrease of the system. Several techniques are used to compensate the non-linear effects in amplitude and phase and to improve the rejection of the out of band noise as predistortion, feedback and feed-forward. In order to obtain a high bandwidth and efficient RFPA using either ET or EER, the envelope amplifier stage will have a critical importance. The requirements for this stage are very demanding in terms of bandwidth, linearity and quality of the transmitted signal. Additionally the efficiency should be as high as possible, as the envelope amplifier has a direct impact in the efficiency of the overall system. This thesis is focused on the envelope amplifier stage and the main objective will be the development of high efficiency envelope amplifier solutions that comply with the requirements of the RFPA application. The design and optimization of an envelope amplifier for a RFPA application is a highly referenced research topic, and many solutions that address the envelope amplifier and the RFPA design and optimization can be found in the state of the art. From a high level classification, multiple and single stage envelope amplifiers can be identified. Envelope amplifiers for EER based on multiple stage architecture combine a linear assisted stage and a switched-mode stage, either in a series or parallel configuration, to achieve a very high performance RFPA. However, the complexity of the system increases and the efficiency improvement is limited. A single-stage envelope amplifier has the advantage of a lower complexity but in order to achieve the required bandwidth the switching frequency has to be highly increased, and therefore the performance and the efficiency are degraded. Several techniques are used to overcome this limitation, as the design of integrated circuits that are capable of switching at very high rates or the use of topological solutions, high order filters or a combination of both to reduce the switching frequency requirements. In this thesis it is originally proposed the use of the ripple cancellation technique, applied to a synchronous buck converter, to reduce the switching frequency requirements compared to a conventional buck converter for an envelope amplifier application. Three original proposals for the envelope amplifier stage, based on the ripple cancellation technique, are presented and one of the solutions has been experimentally validated and integrated in the complete amplifier, showing a high total efficiency increase compared to other solutions of the state of the art. Additionally, the proposed envelope amplifier has been integrated in the complete RFPA achieving a high total efficiency. The design process optimization has also been analyzed in this thesis. Due to the different figures of merit between the envelope amplifier and the complete RFPA it is very difficult to obtain an optimized design for the envelope amplifier. To reduce the design uncertainties, a design tool has been developed to provide an estimation of the RFPA figures of merit based on the design of the envelope amplifier. The main contributions of this thesis are: The application of the ripple cancellation technique to a synchronous buck converter for an envelope amplifier application to achieve a high efficiency and high bandwidth EER RFPA. A 66% reduction of the switching frequency, validated experimentally, compared to the equivalent conventional buck converter. This reduction has been reflected in an improvement in the efficiency between 12.4% and 16%, validated for the specifications of this work. The synchronous buck converter with two cascaded ripple cancellation networks (RCNs) topology and design to improve the robustness and the performance of the envelope amplifier. The combination of a phase-shifted multi-phase buck converter with the ripple cancellation technique to improve the envelope amplifier switching frequency to signal bandwidth ratio. The optimization of the control loop of an envelope amplifier to improve the performance of the open loop design for the conventional and ripple cancellation buck converter. A simulation tool to optimize the envelope amplifier design process. Using the envelope amplifier design as the input data, the main figures of merit of the complete RFPA for an EER application are obtained for several digital modulations. The successful integration of the envelope amplifier based on a RCN buck converter in the complete RFPA obtaining a high efficiency integrated amplifier. The efficiency obtained is between 57% and 70.6% for an output power of 14.4W and 40.7W respectively. The main figures of merit for the different modulations have been characterized and analyzed. This thesis is organized in six chapters. In Chapter 1 is provided an introduction of the RFPA application, where the main problems, challenges and solutions are described. In Chapter 2 the technical background for radiofrequency power amplifiers (RF) is presented. The main techniques to implement an RFPA are described and analyzed. The state of the art techniques to improve performance of the RFPA are identified as well as the main sources of no-linearities for the RFPA. Chapter 3 is focused on the envelope amplifier stage. The three different solutions proposed originally in this thesis for the envelope amplifier are presented and analyzed. The control stage design is analyzed and an optimization is proposed both for the conventional and the RCN buck converter. Chapter 4 is focused in the design and optimization process of the envelope amplifier and a design tool to evaluate the envelope amplifier design impact in the RFPA is presented. Chapter 5 shows the integration process of the complete amplifier. Chapter 6 addresses the main conclusions of the thesis and the future work.

Diseño de un Procesador de Membranas Paralelo para los Sistemas P de Transición

La computación con membranas surge como una alternativa a la computación tradicional. Dentro de este campo se sitúan los denominados Sistemas P de Transición que se basan en la existencia de regiones que contienen recursos y reglas que hacen evolucionar a dichos recursos para poder llevar a cada una de las regiones a una nueva situación denominada configuración. La sucesión de las diferentes configuraciones conforman la computación. En este campo, el Grupo de Computación Natural de la Universidad Politécnica de Madrid lleva a cabo numerosas investigaciones al amparo de las cuales se han publicado numerosos artículos y realizado varias tesis doctorales. Las principales vías de investigación han sido, hasta el momento, el estudio del modelo teórico sobre el que se definen los Sistemas P, el estudio de los algoritmos que se utilizan para la aplicación de las reglas de evolución en las regiones, el diseño de nuevas arquitecturas que mejoren las comunicaciones entre las diferentes membranas (regiones) que componen el sistema y la implantación de estos sistemas en dispositivos hardware que pudiesen definir futuras máquinas basadas en este modelo. Dentro de este último campo, es decir, dentro del objetivo de construir finalmente máquinas que puedan llevar a cabo la funcionalidad de la computación con Sistemas P, la presente tesis doctoral se centra en el diseño de dos procesadores paralelos que, aplicando variantes de algoritmos existentes, favorezcan el crecimiento en el nivel de intra-paralelismo a la hora de aplicar las reglas. El diseño y creación de ambos procesadores presentan novedosas aportaciones al entorno de investigación de los Sistemas P de Transición en tanto en cuanto se utilizan conceptos que aunque previamente definidos de manera teórica, no habían sido introducidos en el hardware diseñado para estos sistemas. Así, los dos procesadores mantienen las siguientes características: - Presentan un alto rendimiento en la fase de aplicación de reglas, manteniendo por otro lado una flexibilidad y escalabilidad medias que son dependientes de la tecnología final sobre la que se sinteticen dichos procesadores. - Presentan un alto nivel de intra-paralelismo en las regiones al permitir la aplicación simultánea de reglas. - Tienen carácter universal en tanto en cuanto no depende del carácter de las reglas que componen el Sistema P. - Tienen un comportamiento indeterminista que es inherente a la propia naturaleza de estos sistemas. El primero de los circuitos utiliza el conjunto potencia del conjunto de reglas de aplicación así como el concepto de máxima aplicabilidad para favorecer el intra-paralelismo y el segundo incluye, además, el concepto de dominio de aplicabilidad para determinar el conjunto de reglas que son aplicables en cada momento con los recursos existentes. Ambos procesadores se diseñan y se prueban mediante herramientas de diseño electrónico y se preparan para ser sintetizados sobre FPGAs. ABSTRACT Membrane computing appears as an alternative to traditional computing. P Systems are placed inside this field and they are based upon the existence of regions called “membranes” that contain resources and rules that describe how the resources may vary to take each of these regions to a new situation called "configuration". Successive configurations conform computation. Inside this field, the Natural Computing Group of the Universidad Politécnica of Madrid develops a large number of works and researches that provide a lot of papers and some doctoral theses. Main research lines have been, by the moment, the study of the theoretical model over which Transition P Systems are defined, the study of the algorithms that are used for the evolution rules application in the regions, the design of new architectures that may improve communication among the different membranes (regions) that compose the whole system and the implementation of such systems over hardware devices that may define machines based upon this new model. Within this last research field, this is, within the objective of finally building machines that may accomplish the functionality of computation with P Systems, the present thesis is centered on the design of two parallel processors that, applying several variants of some known algorithms, improve the level of the internal parallelism at the evolution rule application phase. Design and creation of both processors present innovations to the field of Transition P Systems research because they use concepts that, even being known before, were never used for circuits that implement the applying phase of evolution rules. So, both processors present the following characteristics: - They present a very high performance during the application rule phase, keeping, on the other hand, a level of flexibility and scalability that, even known it is not very high, it seems to be acceptable. - They present a very high level of internal parallelism inside the regions, allowing several rule to be applied at the same time. - They present a universal character meaning this that they are not dependent upon the active rules that compose the P System. - They have a non-deterministic behavior that is inherent to this systems nature. The first processor uses the concept of "power set of the application rule set" and the concept of "maximal application" number to improve parallelism, and the second one includes, besides the previous ones, the concept of "applicability domain" to determine the set of rules that may be applied in each moment with the existing resources.. Both processors are designed and tested with the design software by Altera Corporation and they are ready to be synthetized over FPGAs.

Technology and characterization of GaN-HEMTs devices: high temperature and trapping effects

Los transistores de alta movilidad electrónica basados en GaN han sido objeto de una extensa investigación ya que tanto el GaN como sus aleaciones presentan unas excelentes propiedades eléctricas (alta movilidad, elevada concentración de portadores y campo eléctrico crítico alto). Aunque recientemente se han incluido en algunas aplicaciones comerciales, su expansión en el mercado está condicionada a la mejora de varios asuntos relacionados con su rendimiento y habilidad. Durante esta tesis se han abordado algunos de estos aspectos relevantes; por ejemplo, la fabricación de enhancement mode HEMTs, su funcionamiento a alta temperatura, el auto calentamiento y el atrapamiento de carga. Los HEMTs normalmente apagado o enhancement mode han atraído la atención de la comunidad científica dedicada al desarrollo de circuitos amplificadores y conmutadores de potencia, ya que su utilización disminuiría significativamente el consumo de potencia; además de requerir solamente una tensión de alimentación negativa, y reducir la complejidad del circuito y su coste. Durante esta tesis se han evaluado varias técnicas utilizadas para la fabricación de estos dispositivos: el ataque húmedo para conseguir el gate-recess en heterostructuras de InAl(Ga)N/GaN; y tratamientos basados en flúor (plasma CF4 e implantación de F) de la zona debajo de la puerta. Se han llevado a cabo ataques húmedos en heteroestructuras de InAl(Ga)N crecidas sobre sustratos de Si, SiC y zafiro. El ataque completo de la barrera se consiguió únicamente en las muestras con sustrato de Si. Por lo tanto, se puede deducir que la velocidad de ataque depende de la densidad de dislocaciones presentes en la estructura, ya que el Si presenta un peor ajuste del parámetro de red con el GaN. En relación a los tratamientos basados en flúor, se ha comprobado que es necesario realizar un recocido térmico después de la fabricación de la puerta para recuperar la heteroestructura de los daños causados durante dichos tratamientos. Además, el estudio de la evolución de la tensión umbral con el tiempo de recocido ha demostrado que en los HEMTs tratados con plasma ésta tiende a valores más negativos al aumentar el tiempo de recocido. Por el contrario, la tensión umbral de los HEMTs implantados se desplaza hacia valores más positivos, lo cual se atribuye a la introducción de iones de flúor a niveles más profundos de la heterostructura. Los transistores fabricados con plasma presentaron mejor funcionamiento en DC a temperatura ambiente que los implantados. Su estudio a alta temperatura ha revelado una reducción del funcionamiento de todos los dispositivos con la temperatura. Los valores iniciales de corriente de drenador y de transconductancia medidos a temperatura ambiente se recuperaron después del ciclo térmico, por lo que se deduce que dichos efectos térmicos son reversibles. Se han estudiado varios aspectos relacionados con el funcionamiento de los HEMTs a diferentes temperaturas. En primer lugar, se han evaluado las prestaciones de dispositivos de AlGaN/GaN sobre sustrato de Si con diferentes caps: GaN, in situ SiN e in situ SiN/GaN, desde 25 K hasta 550 K. Los transistores con in situ SiN presentaron los valores más altos de corriente drenador, transconductancia, y los valores más bajos de resistencia-ON, así como las mejores características en corte. Además, se ha confirmado que dichos dispositivos presentan gran robustez frente al estrés térmico. En segundo lugar, se ha estudiado el funcionamiento de transistores de InAlN/GaN con diferentes diseños y geometrías. Dichos dispositivos presentaron una reducción casi lineal de los parámetros en DC en el rango de temperaturas de 25°C hasta 225°C. Esto se debe principalmente a la dependencia térmica de la movilidad electrónica, y también a la reducción de la drift velocity con la temperatura. Además, los transistores con mayores longitudes de puerta mostraron una mayor reducción de su funcionamiento, lo cual se atribuye a que la drift velocity disminuye más considerablemente con la temperatura cuando el campo eléctrico es pequeño. De manera similar, al aumentar la distancia entre la puerta y el drenador, el funcionamiento del HEMT presentó una mayor reducción con la temperatura. Por lo tanto, se puede deducir que la degradación del funcionamiento de los HEMTs causada por el aumento de la temperatura depende tanto de la longitud de la puerta como de la distancia entre la puerta y el drenador. Por otra parte, la alta densidad de potencia generada en la región activa de estos transistores conlleva el auto calentamiento de los mismos por efecto Joule, lo cual puede degradar su funcionamiento y Habilidad. Durante esta tesis se ha desarrollado un simple método para la determinación de la temperatura del canal basado en medidas eléctricas. La aplicación de dicha técnica junto con la realización de simulaciones electrotérmicas han posibilitado el estudio de varios aspectos relacionados con el autocalentamiento. Por ejemplo, se han evaluado sus efectos en dispositivos sobre Si, SiC, y zafiro. Los transistores sobre SiC han mostrado menores efectos gracias a la mayor conductividad térmica del SiC, lo cual confirma el papel clave que desempeña el sustrato en el autocalentamiento. Se ha observado que la geometría del dispositivo tiene cierta influencia en dichos efectos, destacando que la distribución del calor generado en la zona del canal depende de la distancia entre la puerta y el drenador. Además, se ha demostrado que la temperatura ambiente tiene un considerable impacto en el autocalentamiento, lo que se atribuye principalmente a la dependencia térmica de la conductividad térmica de las capas y sustrato que forman la heterostructura. Por último, se han realizado numerosas medidas en pulsado para estudiar el atrapamiento de carga en HEMTs sobre sustratos de SiC con barreras de AlGaN y de InAlN. Los resultados obtenidos en los transistores con barrera de AlGaN han presentado una disminución de la corriente de drenador y de la transconductancia sin mostrar un cambio en la tensión umbral. Por lo tanto, se puede deducir que la posible localización de las trampas es la región de acceso entre la puerta y el drenador. Por el contrario, la reducción de la corriente de drenador observada en los dispositivos con barrera de InAlN llevaba asociado un cambio significativo en la tensión umbral, lo que implica la existencia de trampas situadas en la zona debajo de la puerta. Además, el significativo aumento del valor de la resistencia-ON y la degradación de la transconductancia revelan la presencia de trampas en la zona de acceso entre la puerta y el drenador. La evaluación de los efectos del atrapamiento de carga en dispositivos con diferentes geometrías ha demostrado que dichos efectos son menos notables en aquellos transistores con mayor longitud de puerta o mayor distancia entre puerta y drenador. Esta dependencia con la geometría se puede explicar considerando que la longitud y densidad de trampas de la puerta virtual son independientes de las dimensiones del dispositivo. Finalmente se puede deducir que para conseguir el diseño óptimo durante la fase de diseño no sólo hay que tener en cuenta la aplicación final sino también la influencia que tiene la geometría en los diferentes aspectos estudiados (funcionamiento a alta temperatura, autocalentamiento, y atrapamiento de carga). ABSTRACT GaN-based high electron mobility transistors have been under extensive research due to the excellent electrical properties of GaN and its related alloys (high carrier concentration, high mobility, and high critical electric field). Although these devices have been recently included in commercial applications, some performance and reliability issues need to be addressed for their expansion in the market. Some of these relevant aspects have been studied during this thesis; for instance, the fabrication of enhancement mode HEMTs, the device performance at high temperature, the self-heating and the charge trapping. Enhancement mode HEMTs have become more attractive mainly because their use leads to a significant reduction of the power consumption during the stand-by state. Moreover, they enable the fabrication of simpler power amplifier circuits and high-power switches because they allow the elimination of negativepolarity voltage supply, reducing significantly the circuit complexity and system cost. In this thesis, different techniques for the fabrication of these devices have been assessed: wet-etching for achieving the gate-recess in InAl(Ga)N/GaN devices and two different fluorine-based treatments (CF4 plasma and F implantation). Regarding the wet-etching, experiments have been carried out in InAl(Ga)N/GaN grown on different substrates: Si, sapphire, and SiC. The total recess of the barrier was achieved after 3 min of etching in devices grown on Si substrate. This suggests that the etch rate can critically depend on the dislocations present in the structure, since the Si exhibits the highest mismatch to GaN. Concerning the fluorine-based treatments, a post-gate thermal annealing was required to recover the damages caused to the structure during the fluorine-treatments. The study of the threshold voltage as a function of this annealing time has revealed that in the case of the plasma-treated devices it become more negative with the time increase. On the contrary, the threshold voltage of implanted HEMTs showed a positive shift when the annealing time was increased, which is attributed to the deep F implantation profile. Plasma-treated HEMTs have exhibited better DC performance at room temperature than the implanted devices. Their study at high temperature has revealed that their performance decreases with temperature. The initial performance measured at room temperature was recovered after the thermal cycle regardless of the fluorine treatment; therefore, the thermal effects were reversible. Thermal issues related to the device performance at different temperature have been addressed. Firstly, AlGaN/GaN HEMTs grown on Si substrate with different cap layers: GaN, in situ SiN, or in situ SiN/GaN, have been assessed from 25 K to 550 K. In situ SiN cap layer has been demonstrated to improve the device performance since HEMTs with this cap layer have exhibited the highest drain current and transconductance values, the lowest on-resistance, as well as the best off-state characteristics. Moreover, the evaluation of thermal stress impact on the device performance has confirmed the robustness of devices with in situ cap. Secondly, the high temperature performance of InAlN/GaN HEMTs with different layouts and geometries have been assessed. The devices under study have exhibited an almost linear reduction of the main DC parameters operating in a temperature range from room temperature to 225°C. This was mainly due to the thermal dependence of the electron mobility, and secondly to the drift velocity decrease with temperature. Moreover, HEMTs with large gate length values have exhibited a great reduction of the device performance. This was attributed to the greater decrease of the drift velocity for low electric fields. Similarly, the increase of the gate-to-drain distance led to a greater reduction of drain current and transconductance values. Therefore, this thermal performance degradation has been found to be dependent on both the gate length and the gate-to-drain distance. It was observed that the very high power density in the active region of these transistors leads to Joule self-heating, resulting in an increase of the device temperature, which can degrade the device performance and reliability. A simple electrical method have been developed during this work to determine the channel temperature. Furthermore, the application of this technique together with the performance of electro-thermal simulations have enabled the evaluation of different aspects related to the self-heating. For instance, the influence of the substrate have been confirmed by the study of devices grown on Si, SiC, and Sapphire. HEMTs grown on SiC substrate have been confirmed to exhibit the lowest self-heating effects thanks to its highest thermal conductivity. In addition to this, the distribution of the generated heat in the channel has been demonstrated to be dependent on the gate-to-drain distance. Besides the substrate and the geometry of the device, the ambient temperature has also been found to be relevant for the self-heating effects, mainly due to the temperature-dependent thermal conductivity of the layers and the substrate. Trapping effects have been evaluated by means of pulsed measurements in AlGaN and InAIN barrier devices. AlGaN barrier HEMTs have exhibited a de crease in drain current and transconductance without measurable threshold voltage change, suggesting the location of the traps in the gate-to-drain access region. On the contrary, InAIN barrier devices have showed a drain current associated with a positive shift of threshold voltage, which indicated that the traps were possibly located under the gate region. Moreover, a significant increase of the ON-resistance as well as a transconductance reduction were observed, revealing the presence of traps on the gate-drain access region. On the other hand, the assessment of devices with different geometries have demonstrated that the trapping effects are more noticeable in devices with either short gate length or the gate-to-drain distance. This can be attributed to the fact that the length and the trap density of the virtual gate are independent on the device geometry. Finally, it can be deduced that besides the final application requirements, the influence of the device geometry on the performance at high temperature, on the self-heating, as well as on the trapping effects need to be taken into account during the device design stage to achieve the optimal layout.

Low-cost manufacturing by fused filament fabrication of microwave waveguide passive devices for space applications

Presentación en poster de impresión 3D de guias de onda.

A proposal for an Internet of Things-based monitoring system composed by low capability, open source and open hardware devices

The Internet of Things makes use of a huge disparity of technologies at very different levels that help one to the other to accomplish goals that were previously regarded as unthinkable in terms of ubiquity or scalability. If the Internet of Things is expected to interconnect every day devices or appliances and enable communications between them, a broad range of new services, applications and products can be foreseen. For example, monitoring is a process where sensors have widespread use for measuring environmental parameters (temperature, light, chemical agents, etc.) but obtaining readings at the exact physical point they want to be obtained from, or about the exact wanted parameter can be a clumsy, time-consuming task that is not easily adaptable to new requirements. In order to tackle this challenge, a proposal on a system used to monitor any conceivable environment, which additionally is able to monitor the status of its own components and heal some of the most usual issues of a Wireless Sensor Network, is presented here in detail, covering all the layers that give it shape in terms of devices, communications or services.

Modelo de computación conexionista inspirado en las redes de procesadores evolutivos y su aprendizaje

La informática teórica es una disciplina básica ya que la mayoría de los avances en informática se sustentan en un sólido resultado de esa materia. En los últimos a~nos debido tanto al incremento de la potencia de los ordenadores, como a la cercanía del límite físico en la miniaturización de los componentes electrónicos, resurge el interés por modelos formales de computación alternativos a la arquitectura clásica de von Neumann. Muchos de estos modelos se inspiran en la forma en la que la naturaleza resuelve eficientemente problemas muy complejos. La mayoría son computacionalmente completos e intrínsecamente paralelos. Por este motivo se les está llegando a considerar como nuevos paradigmas de computación (computación natural). Se dispone, por tanto, de un abanico de arquitecturas abstractas tan potentes como los computadores convencionales y, a veces, más eficientes: alguna de ellas mejora el rendimiento, al menos temporal, de problemas NPcompletos proporcionando costes no exponenciales. La representación formal de las redes de procesadores evolutivos requiere de construcciones, tanto independientes, como dependientes del contexto, dicho de otro modo, en general una representación formal completa de un NEP implica restricciones, tanto sintácticas, como semánticas, es decir, que muchas representaciones aparentemente (sintácticamente) correctas de casos particulares de estos dispositivos no tendrían sentido porque podrían no cumplir otras restricciones semánticas. La aplicación de evolución gramatical semántica a los NEPs pasa por la elección de un subconjunto de ellos entre los que buscar los que solucionen un problema concreto. En este trabajo se ha realizado un estudio sobre un modelo inspirado en la biología celular denominado redes de procesadores evolutivos [55, 53], esto es, redes cuyos nodos son procesadores muy simples capaces de realizar únicamente un tipo de mutación puntual (inserción, borrado o sustitución de un símbolo). Estos nodos están asociados con un filtro que está definido por alguna condición de contexto aleatorio o de pertenencia. Las redes están formadas a lo sumo de seis nodos y, teniendo los filtros definidos por una pertenencia a lenguajes regulares, son capaces de generar todos los lenguajes enumerables recursivos independientemente del grafo subyacente. Este resultado no es sorprendente ya que semejantes resultados han sido documentados en la literatura. Si se consideran redes con nodos y filtros definidos por contextos aleatorios {que parecen estar más cerca a las implementaciones biológicas{ entonces se pueden generar lenguajes más complejos como los lenguajes no independientes del contexto. Sin embargo, estos mecanismos tan simples son capaces de resolver problemas complejos en tiempo polinomial. Se ha presentado una solución lineal para un problema NP-completo, el problema de los 3-colores. Como primer aporte significativo se ha propuesto una nueva dinámica de las redes de procesadores evolutivos con un comportamiento no determinista y masivamente paralelo [55], y por tanto todo el trabajo de investigación en el área de la redes de procesadores se puede trasladar a las redes masivamente paralelas. Por ejemplo, las redes masivamente paralelas se pueden modificar de acuerdo a determinadas reglas para mover los filtros hacia las conexiones. Cada conexión se ve como un canal bidireccional de manera que los filtros de entrada y salida coinciden. A pesar de esto, estas redes son computacionalmente completas. Se pueden también implementar otro tipo de reglas para extender este modelo computacional. Se reemplazan las mutaciones puntuales asociadas a cada nodo por la operación de splicing. Este nuevo tipo de procesador se denomina procesador splicing. Este modelo computacional de Red de procesadores con splicing ANSP es semejante en cierto modo a los sistemas distribuidos en tubos de ensayo basados en splicing. Además, se ha definido un nuevo modelo [56] {Redes de procesadores evolutivos con filtros en las conexiones{ , en el cual los procesadores tan solo tienen reglas y los filtros se han trasladado a las conexiones. Dicho modelo es equivalente, bajo determinadas circunstancias, a las redes de procesadores evolutivos clásicas. Sin dichas restricciones el modelo propuesto es un superconjunto de los NEPs clásicos. La principal ventaja de mover los filtros a las conexiones radica en la simplicidad de la modelización. Otras aportaciones de este trabajo ha sido el dise~no de un simulador en Java [54, 52] para las redes de procesadores evolutivos propuestas en esta Tesis. Sobre el término "procesador evolutivo" empleado en esta Tesis, el proceso computacional descrito aquí no es exactamente un proceso evolutivo en el sentido Darwiniano. Pero las operaciones de reescritura que se han considerado pueden interpretarse como mutaciones y los procesos de filtrado se podrían ver como procesos de selección. Además, este trabajo no abarca la posible implementación biológica de estas redes, a pesar de ser de gran importancia. A lo largo de esta tesis se ha tomado como definición de la medida de complejidad para los ANSP, una que denotaremos como tama~no (considerando tama~no como el número de nodos del grafo subyacente). Se ha mostrado que cualquier lenguaje enumerable recursivo L puede ser aceptado por un ANSP en el cual el número de procesadores está linealmente acotado por la cardinalidad del alfabeto de la cinta de una máquina de Turing que reconoce dicho lenguaje L. Siguiendo el concepto de ANSP universales introducido por Manea [65], se ha demostrado que un ANSP con una estructura de grafo fija puede aceptar cualquier lenguaje enumerable recursivo. Un ANSP se puede considerar como un ente capaz de resolver problemas, además de tener otra propiedad relevante desde el punto de vista práctico: Se puede definir un ANSP universal como una subred, donde solo una cantidad limitada de parámetros es dependiente del lenguaje. La anterior característica se puede interpretar como un método para resolver cualquier problema NP en tiempo polinomial empleando un ANSP de tama~no constante, concretamente treinta y uno. Esto significa que la solución de cualquier problema NP es uniforme en el sentido de que la red, exceptuando la subred universal, se puede ver como un programa; adaptándolo a la instancia del problema a resolver, se escogerín los filtros y las reglas que no pertenecen a la subred universal. Un problema interesante desde nuestro punto de vista es el que hace referencia a como elegir el tama~no optimo de esta red.---ABSTRACT---This thesis deals with the recent research works in the area of Natural Computing {bio-inspired models{, more precisely Networks of Evolutionary Processors first developed by Victor Mitrana and they are based on P Systems whose father is Georghe Paun. In these models, they are a set of processors connected in an underlying undirected graph, such processors have an object multiset (strings) and a set of rules, named evolution rules, that transform objects inside processors[55, 53],. These objects can be sent/received using graph connections provided they accomplish constraints defined at input and output filters processors have. This symbolic model, non deterministic one (processors are not synchronized) and massive parallel one[55] (all rules can be applied in one computational step) has some important properties regarding solution of NP-problems in lineal time and of course, lineal resources. There are a great number of variants such as hybrid networks, splicing processors, etc. that provide the model a computational power equivalent to Turing machines. The origin of networks of evolutionary processors (NEP for short) is a basic architecture for parallel and distributed symbolic processing, related to the Connection Machine as well as the Logic Flow paradigm, which consists of several processors, each of them being placed in a node of a virtual complete graph, which are able to handle data associated with the respective node. All the nodes send simultaneously their data and the receiving nodes handle also simultaneously all the arriving messages, according to some strategies. In a series of papers one considers that each node may be viewed as a cell having genetic information encoded in DNA sequences which may evolve by local evolutionary events, that is point mutations. Each node is specialized just for one of these evolutionary operations. Furthermore, the data in each node is organized in the form of multisets of words (each word appears in an arbitrarily large number of copies), and all the copies are processed in parallel such that all the possible events that can take place do actually take place. Obviously, the computational process just described is not exactly an evolutionary process in the Darwinian sense. But the rewriting operations we have considered might be interpreted as mutations and the filtering process might be viewed as a selection process. Recombination is missing but it was asserted that evolutionary and functional relationships between genes can be captured by taking only local mutations into consideration. It is clear that filters associated with each node allow a strong control of the computation. Indeed, every node has an input and output filter; two nodes can exchange data if it passes the output filter of the sender and the input filter of the receiver. Moreover, if some data is sent out by some node and not able to enter any node, then it is lost. In this paper we simplify the ANSP model considered in by moving the filters from the nodes to the edges. Each edge is viewed as a two-way channel such that the input and output filters coincide. Clearly, the possibility of controlling the computation in such networks seems to be diminished. For instance, there is no possibility to loose data during the communication steps. In spite of this and of the fact that splicing is not a powerful operation (remember that splicing systems generates only regular languages) we prove here that these devices are computationally complete. As a consequence, we propose characterizations of two complexity classes, namely NP and PSPACE, in terms of accepting networks of restricted splicing processors with filtered connections. We proposed a uniform linear time solution to SAT based on ANSPFCs with linearly bounded resources. This solution should be understood correctly: we do not solve SAT in linear time and space. Since any word and auxiliary word appears in an arbitrarily large number of copies, one can generate in linear time, by parallelism and communication, an exponential number of words each of them having an exponential number of copies. However, this does not seem to be a major drawback since by PCR (Polymerase Chain Reaction) one can generate an exponential number of identical DNA molecules in a linear number of reactions. It is worth mentioning that the ANSPFC constructed above remains unchanged for any instance with the same number of variables. Therefore, the solution is uniform in the sense that the network, excepting the input and output nodes, may be viewed as a program according to the number of variables, we choose the filters, the splicing words and the rules, then we assign all possible values to the variables, and compute the formula.We proved that ANSP are computationally complete. Do the ANSPFC remain still computationally complete? If this is not the case, what other problems can be eficiently solved by these ANSPFCs? Moreover, the complexity class NP is exactly the class of all languages decided by ANSP in polynomial time. Can NP be characterized in a similar way with ANSPFCs?

Methodologies for Collision Risk Computation = Metodologías para Cálculo de Riesgo de Colisión

Esta tesis aborda metodologías para el cálculo de riesgo de colisión de satélites. La minimización del riesgo de colisión se debe abordar desde dos puntos de vista distintos. Desde el punto de vista operacional, es necesario filtrar los objetos que pueden presentar un encuentro entre todos los objetos que comparten el espacio con un satélite operacional. Puesto que las órbitas, del objeto operacional y del objeto envuelto en la colisión, no se conocen perfectamente, la geometría del encuentro y el riesgo de colisión deben ser evaluados. De acuerdo con dicha geometría o riesgo, una maniobra evasiva puede ser necesaria para evitar la colisión. Dichas maniobras implican un consumo de combustible que impacta en la capacidad de mantenimiento orbital y por tanto de la visa útil del satélite. Por tanto, el combustible necesario a lo largo de la vida útil de un satélite debe ser estimado en fase de diseño de la misión para una correcta definición de su vida útil, especialmente para satélites orbitando en regímenes orbitales muy poblados. Los dos aspectos, diseño de misión y aspectos operacionales en relación con el riesgo de colisión están abordados en esta tesis y se resumen en la Figura 3. En relación con los aspectos relacionados con el diseño de misión (parte inferior de la figura), es necesario evaluar estadísticamente las características de de la población espacial y las teorías que permiten calcular el número medio de eventos encontrados por una misión y su capacidad de reducir riesgo de colisión. Estos dos aspectos definen los procedimientos más apropiados para reducir el riesgo de colisión en fase operacional. Este aspecto es abordado, comenzando por la teoría descrita en [Sánchez-Ortiz, 2006]T.14 e implementada por el autor de esta tesis en la herramienta ARES [Sánchez-Ortiz, 2004b]T.15 proporcionada por ESA para la evaluación de estrategias de evitación de colisión. Esta teoría es extendida en esta tesis para considerar las características de los datos orbitales disponibles en las fases operacionales de un satélite (sección 4.3.3). Además, esta teoría se ha extendido para considerar riesgo máximo de colisión cuando la incertidumbre de las órbitas de objetos catalogados no es conocida (como se da el caso para los TLE), y en el caso de querer sólo considerar riesgo de colisión catastrófico (sección 4.3.2.3). Dichas mejoras se han incluido en la nueva versión de ARES [Domínguez-González and Sánchez-Ortiz, 2012b]T.12 puesta a disposición a través de [SDUP,2014]R.60. En fase operacional, los catálogos que proporcionan datos orbitales de los objetos espaciales, son procesados rutinariamente, para identificar posibles encuentros que se analizan en base a algoritmos de cálculo de riesgo de colisión para proponer maniobras de evasión. Actualmente existe una única fuente de datos públicos, el catálogo TLE (de sus siglas en inglés, Two Line Elements). Además, el Joint Space Operation Center (JSpOC) Americano proporciona mensajes con alertas de colisión (CSM) cuando el sistema de vigilancia americano identifica un posible encuentro. En función de los datos usados en fase operacional (TLE o CSM), la estrategia de evitación puede ser diferente debido a las características de dicha información. Es preciso conocer las principales características de los datos disponibles (respecto a la precisión de los datos orbitales) para estimar los posibles eventos de colisión encontrados por un satélite a lo largo de su vida útil. En caso de los TLE, cuya precisión orbital no es proporcionada, la información de precisión orbital derivada de un análisis estadístico se puede usar también en el proceso operacional así como en el diseño de la misión. En caso de utilizar CSM como base de las operaciones de evitación de colisiones, se conoce la precisión orbital de los dos objetos involucrados. Estas características se han analizado en detalle, evaluando estadísticamente las características de ambos tipos de datos. Una vez concluido dicho análisis, se ha analizado el impacto de utilizar TLE o CSM en las operaciones del satélite (sección 5.1). Este análisis se ha publicado en una revista especializada [Sánchez-Ortiz, 2015b]T.3. En dicho análisis, se proporcionan recomendaciones para distintas misiones (tamaño del satélite y régimen orbital) en relación con las estrategias de evitación de colisión para reducir el riesgo de colisión de manera significativa. Por ejemplo, en el caso de un satélite en órbita heliosíncrona en régimen orbital LEO, el valor típico del ACPL que se usa de manera extendida es 10-4. Este valor no es adecuado cuando los esquemas de evitación de colisión se realizan sobre datos TLE. En este caso, la capacidad de reducción de riesgo es prácticamente nula (debido a las grandes incertidumbres de los datos TLE) incluso para tiempos cortos de predicción. Para conseguir una reducción significativa del riesgo, sería necesario usar un ACPL en torno a 10-6 o inferior, produciendo unas 10 alarmas al año por satélite (considerando predicciones a un día) o 100 alarmas al año (con predicciones a tres días). Por tanto, la principal conclusión es la falta de idoneidad de los datos TLE para el cálculo de eventos de colisión. Al contrario, usando los datos CSM, debido a su mejor precisión orbital, se puede obtener una reducción significativa del riesgo con ACPL en torno a 10-4 (considerando 3 días de predicción). Incluso 5 días de predicción pueden ser considerados con ACPL en torno a 10-5. Incluso tiempos de predicción más largos se pueden usar (7 días) con reducción del 90% del riesgo y unas 5 alarmas al año (en caso de predicciones de 5 días, el número de maniobras se mantiene en unas 2 al año). La dinámica en GEO es diferente al caso LEO y hace que el crecimiento de las incertidumbres orbitales con el tiempo de propagación sea menor. Por el contrario, las incertidumbres derivadas de la determinación orbital son peores que en LEO por las diferencias en las capacidades de observación de uno y otro régimen orbital. Además, se debe considerar que los tiempos de predicción considerados para LEO pueden no ser apropiados para el caso de un satélite GEO (puesto que tiene un periodo orbital mayor). En este caso usando datos TLE, una reducción significativa del riesgo sólo se consigue con valores pequeños de ACPL, produciendo una alarma por año cuando los eventos de colisión se predicen a un día vista (tiempo muy corto para implementar maniobras de evitación de colisión).Valores más adecuados de ACPL se encuentran entre 5•10-8 y 10-7, muy por debajo de los valores usados en las operaciones actuales de la mayoría de las misiones GEO (de nuevo, no se recomienda en este régimen orbital basar las estrategias de evitación de colisión en TLE). Los datos CSM permiten una reducción de riesgo apropiada con ACPL entre 10-5 y 10-4 con tiempos de predicción cortos y medios (10-5 se recomienda para predicciones a 5 o 7 días). El número de maniobras realizadas sería una en 10 años de misión. Se debe notar que estos cálculos están realizados para un satélite de unos 2 metros de radio. En el futuro, otros sistemas de vigilancia espacial (como el programa SSA de la ESA), proporcionarán catálogos adicionales de objetos espaciales con el objetivo de reducir el riesgo de colisión de los satélites. Para definir dichos sistemas de vigilancia, es necesario identificar las prestaciones del catalogo en función de la reducción de riesgo que se pretende conseguir. Las características del catálogo que afectan principalmente a dicha capacidad son la cobertura (número de objetos incluidos en el catalogo, limitado principalmente por el tamaño mínimo de los objetos en función de las limitaciones de los sensores utilizados) y la precisión de los datos orbitales (derivada de las prestaciones de los sensores en relación con la precisión de las medidas y la capacidad de re-observación de los objetos). El resultado de dicho análisis (sección 5.2) se ha publicado en una revista especializada [Sánchez-Ortiz, 2015a]T.2. Este análisis no estaba inicialmente previsto durante la tesis, y permite mostrar como la teoría descrita en esta tesis, inicialmente definida para facilitar el diseño de misiones (parte superior de la figura 1) se ha extendido y se puede aplicar para otros propósitos como el dimensionado de un sistema de vigilancia espacial (parte inferior de la figura 1). La principal diferencia de los dos análisis se basa en considerar las capacidades de catalogación (precisión y tamaño de objetos observados) como una variable a modificar en el caso de un diseño de un sistema de vigilancia), siendo fijas en el caso de un diseño de misión. En el caso de las salidas generadas en el análisis, todos los aspectos calculados en un análisis estadístico de riesgo de colisión son importantes para diseño de misión (con el objetivo de calcular la estrategia de evitación y la cantidad de combustible a utilizar), mientras que en el caso de un diseño de un sistema de vigilancia, los aspectos más importantes son el número de maniobras y falsas alarmas (fiabilidad del sistema) y la capacidad de reducción de riesgo (efectividad del sistema). Adicionalmente, un sistema de vigilancia espacial debe ser caracterizado por su capacidad de evitar colisiones catastróficas (evitando así in incremento dramático de la población de basura espacial), mientras que el diseño de una misión debe considerar todo tipo de encuentros, puesto que un operador está interesado en evitar tanto las colisiones catastróficas como las letales. Del análisis de las prestaciones (tamaño de objetos a catalogar y precisión orbital) requeridas a un sistema de vigilancia espacial se concluye que ambos aspectos han de ser fijados de manera diferente para los distintos regímenes orbitales. En el caso de LEO se hace necesario observar objetos de hasta 5cm de radio, mientras que en GEO se rebaja este requisito hasta los 100 cm para cubrir las colisiones catastróficas. La razón principal para esta diferencia viene de las diferentes velocidades relativas entre los objetos en ambos regímenes orbitales. En relación con la precisión orbital, ésta ha de ser muy buena en LEO para poder reducir el número de falsas alarmas, mientras que en regímenes orbitales más altos se pueden considerar precisiones medias. En relación con los aspectos operaciones de la determinación de riesgo de colisión, existen varios algoritmos de cálculo de riesgo entre dos objetos espaciales. La Figura 2 proporciona un resumen de los casos en cuanto a algoritmos de cálculo de riesgo de colisión y como se abordan en esta tesis. Normalmente se consideran objetos esféricos para simplificar el cálculo de riesgo (caso A). Este caso está ampliamente abordado en la literatura y no se analiza en detalle en esta tesis. Un caso de ejemplo se proporciona en la sección 4.2. Considerar la forma real de los objetos (caso B) permite calcular el riesgo de una manera más precisa. Un nuevo algoritmo es definido en esta tesis para calcular el riesgo de colisión cuando al menos uno de los objetos se considera complejo (sección 4.4.2). Dicho algoritmo permite calcular el riesgo de colisión para objetos formados por un conjunto de cajas, y se ha presentado en varias conferencias internacionales. Para evaluar las prestaciones de dicho algoritmo, sus resultados se han comparado con un análisis de Monte Carlo que se ha definido para considerar colisiones entre cajas de manera adecuada (sección 4.1.2.3), pues la búsqueda de colisiones simples aplicables para objetos esféricos no es aplicable a este caso. Este análisis de Monte Carlo se considera la verdad a la hora de calcular los resultados del algoritmos, dicha comparativa se presenta en la sección 4.4.4. En el caso de satélites que no se pueden considerar esféricos, el uso de un modelo de la geometría del satélite permite descartar eventos que no son colisiones reales o estimar con mayor precisión el riesgo asociado a un evento. El uso de estos algoritmos con geometrías complejas es más relevante para objetos de dimensiones grandes debido a las prestaciones de precisión orbital actuales. En el futuro, si los sistemas de vigilancia mejoran y las órbitas son conocidas con mayor precisión, la importancia de considerar la geometría real de los satélites será cada vez más relevante. La sección 5.4 presenta un ejemplo para un sistema de grandes dimensiones (satélite con un tether). Adicionalmente, si los dos objetos involucrados en la colisión tienen velocidad relativa baja (y geometría simple, Caso C en la Figura 2), la mayor parte de los algoritmos no son aplicables requiriendo implementaciones dedicadas para este caso particular. En esta tesis, uno de estos algoritmos presentado en la literatura [Patera, 2001]R.26 se ha analizado para determinar su idoneidad en distintos tipos de eventos (sección 4.5). La evaluación frete a un análisis de Monte Carlo se proporciona en la sección 4.5.2. Tras este análisis, se ha considerado adecuado para abordar las colisiones de baja velocidad. En particular, se ha concluido que el uso de algoritmos dedicados para baja velocidad son necesarios en función del tamaño del volumen de colisión proyectado en el plano de encuentro (B-plane) y del tamaño de la incertidumbre asociada al vector posición entre los dos objetos. Para incertidumbres grandes, estos algoritmos se hacen más necesarios pues la duración del intervalo en que los elipsoides de error de los dos objetos pueden intersecar es mayor. Dicho algoritmo se ha probado integrando el algoritmo de colisión para objetos con geometrías complejas. El resultado de dicho análisis muestra que este algoritmo puede ser extendido fácilmente para considerar diferentes tipos de algoritmos de cálculo de riesgo de colisión (sección 4.5.3). Ambos algoritmos, junto con el método Monte Carlo para geometrías complejas, se han implementado en la herramienta operacional de la ESA CORAM, que es utilizada para evaluar el riesgo de colisión en las actividades rutinarias de los satélites operados por ESA [Sánchez-Ortiz, 2013a]T.11. Este hecho muestra el interés y relevancia de los algoritmos desarrollados para la mejora de las operaciones de los satélites. Dichos algoritmos han sido presentados en varias conferencias internacionales [Sánchez-Ortiz, 2013b]T.9, [Pulido, 2014]T.7,[Grande-Olalla, 2013]T.10, [Pulido, 2014]T.5, [Sánchez-Ortiz, 2015c]T.1. ABSTRACT This document addresses methodologies for computation of the collision risk of a satellite. Two different approaches need to be considered for collision risk minimisation. On an operational basis, it is needed to perform a sieve of possible objects approaching the satellite, among all objects sharing the space with an operational satellite. As the orbits of both, satellite and the eventual collider, are not perfectly known but only estimated, the miss-encounter geometry and the actual risk of collision shall be evaluated. In the basis of the encounter geometry or the risk, an eventual manoeuvre may be required to avoid the conjunction. Those manoeuvres will be associated to a reduction in the fuel for the mission orbit maintenance, and thus, may reduce the satellite operational lifetime. Thus, avoidance manoeuvre fuel budget shall be estimated, at mission design phase, for a better estimation of mission lifetime, especially for those satellites orbiting in very populated orbital regimes. These two aspects, mission design and operational collision risk aspects, are summarised in Figure 3, and covered along this thesis. Bottom part of the figure identifies the aspects to be consider for the mission design phase (statistical characterisation of the space object population data and theory computing the mean number of events and risk reduction capability) which will define the most appropriate collision avoidance approach at mission operational phase. This part is covered in this work by starting from the theory described in [Sánchez-Ortiz, 2006]T.14 and implemented by this author in ARES tool [Sánchez-Ortiz, 2004b]T.15 provided by ESA for evaluation of collision avoidance approaches. This methodology has been now extended to account for the particular features of the available data sets in operational environment (section 4.3.3). Additionally, the formulation has been extended to allow evaluating risk computation approached when orbital uncertainty is not available (like the TLE case) and when only catastrophic collisions are subject to study (section 4.3.2.3). These improvements to the theory have been included in the new version of ESA ARES tool [Domínguez-González and Sánchez-Ortiz, 2012b]T.12 and available through [SDUP,2014]R.60. At the operation phase, the real catalogue data will be processed on a routine basis, with adequate collision risk computation algorithms to propose conjunction avoidance manoeuvre optimised for every event. The optimisation of manoeuvres in an operational basis is not approached along this document. Currently, American Two Line Element (TLE) catalogue is the only public source of data providing orbits of objects in space to identify eventual conjunction events. Additionally, Conjunction Summary Message (CSM) is provided by Joint Space Operation Center (JSpOC) when the American system identifies a possible collision among satellites and debris. Depending on the data used for collision avoidance evaluation, the conjunction avoidance approach may be different. The main features of currently available data need to be analysed (in regards to accuracy) in order to perform estimation of eventual encounters to be found along the mission lifetime. In the case of TLE, as these data is not provided with accuracy information, operational collision avoidance may be also based on statistical accuracy information as the one used in the mission design approach. This is not the case for CSM data, which includes the state vector and orbital accuracy of the two involved objects. This aspect has been analysed in detail and is depicted in the document, evaluating in statistical way the characteristics of both data sets in regards to the main aspects related to collision avoidance. Once the analysis of data set was completed, investigations on the impact of those features in the most convenient avoidance approaches have been addressed (section 5.1). This analysis is published in a peer-reviewed journal [Sánchez-Ortiz, 2015b]T.3. The analysis provides recommendations for different mission types (satellite size and orbital regime) in regards to the most appropriate collision avoidance approach for relevant risk reduction. The risk reduction capability is very much dependent on the accuracy of the catalogue utilized to identify eventual collisions. Approaches based on CSM data are recommended against the TLE based approach. Some approaches based on the maximum risk associated to envisaged encounters are demonstrated to report a very large number of events, which makes the approach not suitable for operational activities. Accepted Collision Probability Levels are recommended for the definition of the avoidance strategies for different mission types. For example for the case of a LEO satellite in the Sun-synchronous regime, the typically used ACPL value of 10-4 is not a suitable value for collision avoidance schemes based on TLE data. In this case the risk reduction capacity is almost null (due to the large uncertainties associated to TLE data sets, even for short time-to-event values). For significant reduction of risk when using TLE data, ACPL on the order of 10-6 (or lower) seems to be required, producing about 10 warnings per year and mission (if one-day ahead events are considered) or 100 warnings per year (for three-days ahead estimations). Thus, the main conclusion from these results is the lack of feasibility of TLE for a proper collision avoidance approach. On the contrary, for CSM data, and due to the better accuracy of the orbital information when compared with TLE, ACPL on the order of 10-4 allows to significantly reduce the risk. This is true for events estimated up to 3 days ahead. Even 5 days ahead events can be considered, but ACPL values down to 10-5 should be considered in such case. Even larger prediction times can be considered (7 days) for risk reduction about 90%, at the cost of larger number of warnings up to 5 events per year, when 5 days prediction allows to keep the manoeuvre rate in 2 manoeuvres per year. Dynamics of the GEO orbits is different to that in LEO, impacting on a lower increase of orbits uncertainty along time. On the contrary, uncertainties at short prediction times at this orbital regime are larger than those at LEO due to the differences in observation capabilities. Additionally, it has to be accounted that short prediction times feasible at LEO may not be appropriate for a GEO mission due to the orbital period being much larger at this regime. In the case of TLE data sets, significant reduction of risk is only achieved for small ACPL values, producing about a warning event per year if warnings are raised one day in advance to the event (too short for any reaction to be considered). Suitable ACPL values would lay in between 5•10-8 and 10-7, well below the normal values used in current operations for most of the GEO missions (TLE-based strategies for collision avoidance at this regime are not recommended). On the contrary, CSM data allows a good reduction of risk with ACPL in between 10-5 and 10-4 for short and medium prediction times. 10-5 is recommended for prediction times of five or seven days. The number of events raised for a suitable warning time of seven days would be about one in a 10-year mission. It must be noted, that these results are associated to a 2 m radius spacecraft, impact of the satellite size are also analysed within the thesis. In the future, other Space Situational Awareness Systems (SSA, ESA program) may provide additional catalogues of objects in space with the aim of reducing the risk. It is needed to investigate which are the required performances of those catalogues for allowing such risk reduction. The main performance aspects are coverage (objects included in the catalogue, mainly limited by a minimum object size derived from sensor performances) and the accuracy of the orbital data to accurately evaluate the conjunctions (derived from sensor performance in regards to object observation frequency and accuracy). The results of these investigations (section 5.2) are published in a peer-reviewed journal [Sánchez-Ortiz, 2015a]T.2. This aspect was not initially foreseen as objective of the thesis, but it shows how the theory described in the thesis, initially defined for mission design in regards to avoidance manoeuvre fuel allocation (upper part of figure 1), is extended and serves for additional purposes as dimensioning a Space Surveillance and Tracking (SST) system (bottom part of figure below). The main difference between the two approaches is the consideration of the catalogue features as part of the theory which are not modified (for the satellite mission design case) instead of being an input for the analysis (in the case of the SST design). In regards to the outputs, all the features computed by the statistical conjunction analysis are of importance for mission design (with the objective of proper global avoidance strategy definition and fuel allocation), whereas for the case of SST design, the most relevant aspects are the manoeuvre and false alarm rates (defining a reliable system) and the Risk Reduction capability (driving the effectiveness of the system). In regards to the methodology for computing the risk, the SST system shall be driven by the capacity of providing the means to avoid catastrophic conjunction events (avoiding the dramatic increase of the population), whereas the satellite mission design should consider all type of encounters, as the operator is interested on avoiding both lethal and catastrophic collisions. From the analysis of the SST features (object coverage and orbital uncertainty) for a reliable system, it is concluded that those two characteristics are to be imposed differently for the different orbital regimes, as the population level is different depending on the orbit type. Coverage values range from 5 cm for very populated LEO regime up to 100 cm in the case of GEO region. The difference on this requirement derives mainly from the relative velocity of the encounters at those regimes. Regarding the orbital knowledge of the catalogues, very accurate information is required for objects in the LEO region in order to limit the number of false alarms, whereas intermediate orbital accuracy can be considered for higher orbital regimes. In regards to the operational collision avoidance approaches, several collision risk algorithms are used for evaluation of collision risk of two pair of objects. Figure 2 provides a summary of the different collision risk algorithm cases and indicates how they are covered along this document. The typical case with high relative velocity is well covered in literature for the case of spherical objects (case A), with a large number of available algorithms, that are not analysed in detailed in this work. Only a sample case is provided in section 4.2. If complex geometries are considered (Case B), a more realistic risk evaluation can be computed. New approach for the evaluation of risk in the case of complex geometries is presented in this thesis (section 4.4.2), and it has been presented in several international conferences. The developed algorithm allows evaluating the risk for complex objects formed by a set of boxes. A dedicated Monte Carlo method has also been described (section 4.1.2.3) and implemented to allow the evaluation of the actual collisions among a large number of simulation shots. This Monte Carlo runs are considered the truth for comparison of the algorithm results (section 4.4.4). For spacecrafts that cannot be considered as spheres, the consideration of the real geometry of the objects may allow to discard events which are not real conjunctions, or estimate with larger reliability the risk associated to the event. This is of particular importance for the case of large spacecrafts as the uncertainty in positions of actual catalogues does not reach small values to make a difference for the case of objects below meter size. As the tracking systems improve and the orbits of catalogued objects are known more precisely, the importance of considering actual shapes of the objects will become more relevant. The particular case of a very large system (as a tethered satellite) is analysed in section 5.4. Additionally, if the two colliding objects have low relative velocity (and simple geometries, case C in figure above), the most common collision risk algorithms fail and adequate theories need to be applied. In this document, a low relative velocity algorithm presented in the literature [Patera, 2001]R.26 is described and evaluated (section 4.5). Evaluation through comparison with Monte Carlo approach is provided in section 4.5.2. The main conclusion of this analysis is the suitability of this algorithm for the most common encounter characteristics, and thus it is selected as adequate for collision risk estimation. Its performances are evaluated in order to characterise when it can be safely used for a large variety of encounter characteristics. In particular, it is found that the need of using dedicated algorithms depend on both the size of collision volume in the B-plane and the miss-distance uncertainty. For large uncertainties, the need of such algorithms is more relevant since for small uncertainties the encounter duration where the covariance ellipsoids intersect is smaller. Additionally, its application for the case of complex satellite geometries is assessed (case D in figure above) by integrating the developed algorithm in this thesis with Patera’s formulation for low relative velocity encounters. The results of this analysis show that the algorithm can be easily extended for collision risk estimation process suitable for complex geometry objects (section 4.5.3). The two algorithms, together with the Monte Carlo method, have been implemented in the operational tool CORAM for ESA which is used for the evaluation of collision risk of ESA operated missions, [Sánchez-Ortiz, 2013a]T.11. This fact shows the interest and relevance of the developed algorithms for improvement of satellite operations. The algorithms have been presented in several international conferences, [Sánchez-Ortiz, 2013b]T.9, [Pulido, 2014]T.7,[Grande-Olalla, 2013]T.10, [Pulido, 2014]T.5, [Sánchez-Ortiz, 2015c]T.1.

Propuesta de Mecanismos de Verificación de Integridad de Plataformas Móviles de Computación basados en Entornos Seguros de Ejecución

Las prestaciones y características de los dispositivos móviles actuales los sitúa a un nivel similar a los ordenadores de escritorio tradicionales en cuanto a funcionalidad y posibilidades de uso, añadiendo además la movilidad y la sensación de pertenencia al usuario que se deriva de ésta. Estas cualidades convierten a las plataformas móviles de computación en verdaderos ordenadores personales, y cada día es más popular su utilización en ámbitos distintos del ocio y las comunicaciones propiamente dichas, pasando a convertirse en herramientas de apoyo a la productividad también en el entorno profesional y corporativo. La utilización del dispositivo móvil como parte de una infraestructura de telecomunicaciones da lugar a nuevas expresiones de problemas clásicos de gestión y seguridad. Para tratar de abordarlos con la flexibilidad y la escalabilidad necesarias se plantean alternativas novedosas que parten de enfoques originales a estos problemas, como las ideas y conceptos que se engloban en la filosofía del Control de Acceso a la Red (Network Access Control, o NAC). La mayoría de los planteamientos de NAC se basan, en el ámbito de la seguridad, en comprobar ciertas características del dispositivo móvil para tratar de determinar hasta qué punto puede éste suponer una amenaza para los recursos de la red u otros usuarios de la misma. Obtener esta información de forma fiable resulta extremadamente difícil si se caracteriza el dispositivo mediante un modelo de caja blanca, muy adecuado dada la apertura propia de los sistemas operativos móviles actuales, muy diferentes de los de antaño, y la ausencia de un marco de seguridad efectivo en ellos. Este trabajo explora el Estado de la Técnica en este ámbito de investigación y plantea diferentes propuestas orientadas a cubrir las deficiencias de las soluciones propuestas hasta el momento y a satisfacer los estrictos requisitos de seguridad que se derivan de la aplicación del modelo de caja blanca, materializándose en última instancia en la definición de un mecanismo de evaluación de características arbitrarias de un cierto dispositivo móvil basado en Entornos Seguros de Ejecución (Trusted Execution Environments, o TEEs) con elevadas garantías de seguridad compatible con los planteamientos actuales de NAC. ABSTRACT The performance and features of today’s mobile devices make them able to compete with traditional desktop computers in terms of functionality and possible usages. In addition to this, they sport mobility and the stronger sense of ownership that derives from it. These attributes change mobile computation platforms into truly personal computers, allowing them to be used not only for leisure or as mere communications devices, but also as supports of productivity in professional and corporative environments. The utilization of mobile devices as part of a telecommunications infrastructure brings new expressions of classic management and security problems with it. In order to tackle them with appropriate flexibility and scalability, new alternatives are proposed based on original approaches to these problems, such as the concepts and ideas behind the philosophy of Network Access Control (NAC). The vast majority of NAC proposals are based, security-wise, on checking certain mobile device’s properties in order to evaluate how probable it is for it to become a threat for network resources or even other users of the infrastructure. Obtaining this information in a reliable and trustworthy way is extremely difficult if the device is characterized using a white-box model, which is the most appropriate if the openness of today’s mobile operating systems, very different from former ones, and the absence of an effective security framework are taken into account. This work explores the State of the Art related with the aforementioned field of research and presents different proposals targeted to overcome the deficiencies of current solutions and satisfy the strict security requirements derived from the application of the white box model. These proposals are ultimately materialized in the definition of a high-security evaluation procedure of arbitrary properties of a given mobile device based on Trusted Execution Environments (TEEs) which is compatible with modern NAC approaches.

Run-Time Dynamically-Adaptable FPGA-Based Architecture for High-Performance Autonomous Distributed Systems

Esta tesis doctoral se enmarca dentro del campo de los sistemas embebidos reconfigurables, redes de sensores inalámbricas para aplicaciones de altas prestaciones, y computación distribuida. El documento se centra en el estudio de alternativas de procesamiento para sistemas embebidos autónomos distribuidos de altas prestaciones (por sus siglas en inglés, High-Performance Autonomous Distributed Systems (HPADS)), así como su evolución hacia el procesamiento de alta resolución. El estudio se ha llevado a cabo tanto a nivel de plataforma como a nivel de las arquitecturas de procesamiento dentro de la plataforma con el objetivo de optimizar aspectos tan relevantes como la eficiencia energética, la capacidad de cómputo y la tolerancia a fallos del sistema. Los HPADS son sistemas realimentados, normalmente formados por elementos distribuidos conectados o no en red, con cierta capacidad de adaptación, y con inteligencia suficiente para llevar a cabo labores de prognosis y/o autoevaluación. Esta clase de sistemas suele formar parte de sistemas más complejos llamados sistemas ciber-físicos (por sus siglas en inglés, Cyber-Physical Systems (CPSs)). Los CPSs cubren un espectro enorme de aplicaciones, yendo desde aplicaciones médicas, fabricación, o aplicaciones aeroespaciales, entre otras muchas. Para el diseño de este tipo de sistemas, aspectos tales como la confiabilidad, la definición de modelos de computación, o el uso de metodologías y/o herramientas que faciliten el incremento de la escalabilidad y de la gestión de la complejidad, son fundamentales. La primera parte de esta tesis doctoral se centra en el estudio de aquellas plataformas existentes en el estado del arte que por sus características pueden ser aplicables en el campo de los CPSs, así como en la propuesta de un nuevo diseño de plataforma de altas prestaciones que se ajuste mejor a los nuevos y más exigentes requisitos de las nuevas aplicaciones. Esta primera parte incluye descripción, implementación y validación de la plataforma propuesta, así como conclusiones sobre su usabilidad y sus limitaciones. Los principales objetivos para el diseño de la plataforma propuesta se enumeran a continuación: • Estudiar la viabilidad del uso de una FPGA basada en RAM como principal procesador de la plataforma en cuanto a consumo energético y capacidad de cómputo. • Propuesta de técnicas de gestión del consumo de energía en cada etapa del perfil de trabajo de la plataforma. •Propuestas para la inclusión de reconfiguración dinámica y parcial de la FPGA (por sus siglas en inglés, Dynamic Partial Reconfiguration (DPR)) de forma que sea posible cambiar ciertas partes del sistema en tiempo de ejecución y sin necesidad de interrumpir al resto de las partes. Evaluar su aplicabilidad en el caso de HPADS. Las nuevas aplicaciones y nuevos escenarios a los que se enfrentan los CPSs, imponen nuevos requisitos en cuanto al ancho de banda necesario para el procesamiento de los datos, así como en la adquisición y comunicación de los mismos, además de un claro incremento en la complejidad de los algoritmos empleados. Para poder cumplir con estos nuevos requisitos, las plataformas están migrando desde sistemas tradicionales uni-procesador de 8 bits, a sistemas híbridos hardware-software que incluyen varios procesadores, o varios procesadores y lógica programable. Entre estas nuevas arquitecturas, las FPGAs y los sistemas en chip (por sus siglas en inglés, System on Chip (SoC)) que incluyen procesadores embebidos y lógica programable, proporcionan soluciones con muy buenos resultados en cuanto a consumo energético, precio, capacidad de cómputo y flexibilidad. Estos buenos resultados son aún mejores cuando las aplicaciones tienen altos requisitos de cómputo y cuando las condiciones de trabajo son muy susceptibles de cambiar en tiempo real. La plataforma propuesta en esta tesis doctoral se ha denominado HiReCookie. La arquitectura incluye una FPGA basada en RAM como único procesador, así como un diseño compatible con la plataforma para redes de sensores inalámbricas desarrollada en el Centro de Electrónica Industrial de la Universidad Politécnica de Madrid (CEI-UPM) conocida como Cookies. Esta FPGA, modelo Spartan-6 LX150, era, en el momento de inicio de este trabajo, la mejor opción en cuanto a consumo y cantidad de recursos integrados, cuando además, permite el uso de reconfiguración dinámica y parcial. Es importante resaltar que aunque los valores de consumo son los mínimos para esta familia de componentes, la potencia instantánea consumida sigue siendo muy alta para aquellos sistemas que han de trabajar distribuidos, de forma autónoma, y en la mayoría de los casos alimentados por baterías. Por esta razón, es necesario incluir en el diseño estrategias de ahorro energético para incrementar la usabilidad y el tiempo de vida de la plataforma. La primera estrategia implementada consiste en dividir la plataforma en distintas islas de alimentación de forma que sólo aquellos elementos que sean estrictamente necesarios permanecerán alimentados, cuando el resto puede estar completamente apagado. De esta forma es posible combinar distintos modos de operación y así optimizar enormemente el consumo de energía. El hecho de apagar la FPGA para ahora energía durante los periodos de inactividad, supone la pérdida de la configuración, puesto que la memoria de configuración es una memoria volátil. Para reducir el impacto en el consumo y en el tiempo que supone la reconfiguración total de la plataforma una vez encendida, en este trabajo, se incluye una técnica para la compresión del archivo de configuración de la FPGA, de forma que se consiga una reducción del tiempo de configuración y por ende de la energía consumida. Aunque varios de los requisitos de diseño pueden satisfacerse con el diseño de la plataforma HiReCookie, es necesario seguir optimizando diversos parámetros tales como el consumo energético, la tolerancia a fallos y la capacidad de procesamiento. Esto sólo es posible explotando todas las posibilidades ofrecidas por la arquitectura de procesamiento en la FPGA. Por lo tanto, la segunda parte de esta tesis doctoral está centrada en el diseño de una arquitectura reconfigurable denominada ARTICo3 (Arquitectura Reconfigurable para el Tratamiento Inteligente de Cómputo, Confiabilidad y Consumo de energía) para la mejora de estos parámetros por medio de un uso dinámico de recursos. ARTICo3 es una arquitectura de procesamiento para FPGAs basadas en RAM, con comunicación tipo bus, preparada para dar soporte para la gestión dinámica de los recursos internos de la FPGA en tiempo de ejecución gracias a la inclusión de reconfiguración dinámica y parcial. Gracias a esta capacidad de reconfiguración parcial, es posible adaptar los niveles de capacidad de procesamiento, energía consumida o tolerancia a fallos para responder a las demandas de la aplicación, entorno, o métricas internas del dispositivo mediante la adaptación del número de recursos asignados para cada tarea. Durante esta segunda parte de la tesis se detallan el diseño de la arquitectura, su implementación en la plataforma HiReCookie, así como en otra familia de FPGAs, y su validación por medio de diferentes pruebas y demostraciones. Los principales objetivos que se plantean la arquitectura son los siguientes: • Proponer una metodología basada en un enfoque multi-hilo, como las propuestas por CUDA (por sus siglas en inglés, Compute Unified Device Architecture) u Open CL, en la cual distintos kernels, o unidades de ejecución, se ejecuten en un numero variable de aceleradores hardware sin necesidad de cambios en el código de aplicación. • Proponer un diseño y proporcionar una arquitectura en la que las condiciones de trabajo cambien de forma dinámica dependiendo bien de parámetros externos o bien de parámetros que indiquen el estado de la plataforma. Estos cambios en el punto de trabajo de la arquitectura serán posibles gracias a la reconfiguración dinámica y parcial de aceleradores hardware en tiempo real. • Explotar las posibilidades de procesamiento concurrente, incluso en una arquitectura basada en bus, por medio de la optimización de las transacciones en ráfaga de datos hacia los aceleradores. •Aprovechar las ventajas ofrecidas por la aceleración lograda por módulos puramente hardware para conseguir una mejor eficiencia energética. • Ser capaces de cambiar los niveles de redundancia de hardware de forma dinámica según las necesidades del sistema en tiempo real y sin cambios para el código de aplicación. • Proponer una capa de abstracción entre el código de aplicación y el uso dinámico de los recursos de la FPGA. El diseño en FPGAs permite la utilización de módulos hardware específicamente creados para una aplicación concreta. De esta forma es posible obtener rendimientos mucho mayores que en el caso de las arquitecturas de propósito general. Además, algunas FPGAs permiten la reconfiguración dinámica y parcial de ciertas partes de su lógica en tiempo de ejecución, lo cual dota al diseño de una gran flexibilidad. Los fabricantes de FPGAs ofrecen arquitecturas predefinidas con la posibilidad de añadir bloques prediseñados y poder formar sistemas en chip de una forma más o menos directa. Sin embargo, la forma en la que estos módulos hardware están organizados dentro de la arquitectura interna ya sea estática o dinámicamente, o la forma en la que la información se intercambia entre ellos, influye enormemente en la capacidad de cómputo y eficiencia energética del sistema. De la misma forma, la capacidad de cargar módulos hardware bajo demanda, permite añadir bloques redundantes que permitan aumentar el nivel de tolerancia a fallos de los sistemas. Sin embargo, la complejidad ligada al diseño de bloques hardware dedicados no debe ser subestimada. Es necesario tener en cuenta que el diseño de un bloque hardware no es sólo su propio diseño, sino también el diseño de sus interfaces, y en algunos casos de los drivers software para su manejo. Además, al añadir más bloques, el espacio de diseño se hace más complejo, y su programación más difícil. Aunque la mayoría de los fabricantes ofrecen interfaces predefinidas, IPs (por sus siglas en inglés, Intelectual Property) comerciales y plantillas para ayudar al diseño de los sistemas, para ser capaces de explotar las posibilidades reales del sistema, es necesario construir arquitecturas sobre las ya establecidas para facilitar el uso del paralelismo, la redundancia, y proporcionar un entorno que soporte la gestión dinámica de los recursos. Para proporcionar este tipo de soporte, ARTICo3 trabaja con un espacio de soluciones formado por tres ejes fundamentales: computación, consumo energético y confiabilidad. De esta forma, cada punto de trabajo se obtiene como una solución de compromiso entre estos tres parámetros. Mediante el uso de la reconfiguración dinámica y parcial y una mejora en la transmisión de los datos entre la memoria principal y los aceleradores, es posible dedicar un número variable de recursos en el tiempo para cada tarea, lo que hace que los recursos internos de la FPGA sean virtualmente ilimitados. Este variación en el tiempo del número de recursos por tarea se puede usar bien para incrementar el nivel de paralelismo, y por ende de aceleración, o bien para aumentar la redundancia, y por lo tanto el nivel de tolerancia a fallos. Al mismo tiempo, usar un numero óptimo de recursos para una tarea mejora el consumo energético ya que bien es posible disminuir la potencia instantánea consumida, o bien el tiempo de procesamiento. Con el objetivo de mantener los niveles de complejidad dentro de unos límites lógicos, es importante que los cambios realizados en el hardware sean totalmente transparentes para el código de aplicación. A este respecto, se incluyen distintos niveles de transparencia: • Transparencia a la escalabilidad: los recursos usados por una misma tarea pueden ser modificados sin que el código de aplicación sufra ningún cambio. • Transparencia al rendimiento: el sistema aumentara su rendimiento cuando la carga de trabajo aumente, sin cambios en el código de aplicación. • Transparencia a la replicación: es posible usar múltiples instancias de un mismo módulo bien para añadir redundancia o bien para incrementar la capacidad de procesamiento. Todo ello sin que el código de aplicación cambie. • Transparencia a la posición: la posición física de los módulos hardware es arbitraria para su direccionamiento desde el código de aplicación. • Transparencia a los fallos: si existe un fallo en un módulo hardware, gracias a la redundancia, el código de aplicación tomará directamente el resultado correcto. • Transparencia a la concurrencia: el hecho de que una tarea sea realizada por más o menos bloques es transparente para el código que la invoca. Por lo tanto, esta tesis doctoral contribuye en dos líneas diferentes. En primer lugar, con el diseño de la plataforma HiReCookie y en segundo lugar con el diseño de la arquitectura ARTICo3. Las principales contribuciones de esta tesis se resumen a continuación. • Arquitectura de la HiReCookie incluyendo: o Compatibilidad con la plataforma Cookies para incrementar las capacidades de esta. o División de la arquitectura en distintas islas de alimentación. o Implementación de los diversos modos de bajo consumo y políticas de despertado del nodo. o Creación de un archivo de configuración de la FPGA comprimido para reducir el tiempo y el consumo de la configuración inicial. • Diseño de la arquitectura reconfigurable para FPGAs basadas en RAM ARTICo3: o Modelo de computación y modos de ejecución inspirados en el modelo de CUDA pero basados en hardware reconfigurable con un número variable de bloques de hilos por cada unidad de ejecución. o Estructura para optimizar las transacciones de datos en ráfaga proporcionando datos en cascada o en paralelo a los distinto módulos incluyendo un proceso de votado por mayoría y operaciones de reducción. o Capa de abstracción entre el procesador principal que incluye el código de aplicación y los recursos asignados para las diferentes tareas. o Arquitectura de los módulos hardware reconfigurables para mantener la escalabilidad añadiendo una la interfaz para las nuevas funcionalidades con un simple acceso a una memoria RAM interna. o Caracterización online de las tareas para proporcionar información a un módulo de gestión de recursos para mejorar la operación en términos de energía y procesamiento cuando además se opera entre distintos nieles de tolerancia a fallos. El documento está dividido en dos partes principales formando un total de cinco capítulos. En primer lugar, después de motivar la necesidad de nuevas plataformas para cubrir las nuevas aplicaciones, se detalla el diseño de la plataforma HiReCookie, sus partes, las posibilidades para bajar el consumo energético y se muestran casos de uso de la plataforma así como pruebas de validación del diseño. La segunda parte del documento describe la arquitectura reconfigurable, su implementación en varias FPGAs, y pruebas de validación en términos de capacidad de procesamiento y consumo energético, incluyendo cómo estos aspectos se ven afectados por el nivel de tolerancia a fallos elegido. Los capítulos a lo largo del documento son los siguientes: El capítulo 1 analiza los principales objetivos, motivación y aspectos teóricos necesarios para seguir el resto del documento. El capítulo 2 está centrado en el diseño de la plataforma HiReCookie y sus posibilidades para disminuir el consumo de energía. El capítulo 3 describe la arquitectura reconfigurable ARTICo3. El capítulo 4 se centra en las pruebas de validación de la arquitectura usando la plataforma HiReCookie para la mayoría de los tests. Un ejemplo de aplicación es mostrado para analizar el funcionamiento de la arquitectura. El capítulo 5 concluye esta tesis doctoral comentando las conclusiones obtenidas, las contribuciones originales del trabajo y resultados y líneas futuras. ABSTRACT This PhD Thesis is framed within the field of dynamically reconfigurable embedded systems, advanced sensor networks and distributed computing. The document is centred on the study of processing solutions for high-performance autonomous distributed systems (HPADS) as well as their evolution towards High performance Computing (HPC) systems. The approach of the study is focused on both platform and processor levels to optimise critical aspects such as computing performance, energy efficiency and fault tolerance. HPADS are considered feedback systems, normally networked and/or distributed, with real-time adaptive and predictive functionality. These systems, as part of more complex systems known as Cyber-Physical Systems (CPSs), can be applied in a wide range of fields such as military, health care, manufacturing, aerospace, etc. For the design of HPADS, high levels of dependability, the definition of suitable models of computation, and the use of methodologies and tools to support scalability and complexity management, are required. The first part of the document studies the different possibilities at platform design level in the state of the art, together with description, development and validation tests of the platform proposed in this work to cope with the previously mentioned requirements. The main objectives targeted by this platform design are the following: • Study the feasibility of using SRAM-based FPGAs as the main processor of the platform in terms of energy consumption and performance for high demanding applications. • Analyse and propose energy management techniques to reduce energy consumption in every stage of the working profile of the platform. • Provide a solution with dynamic partial and wireless remote HW reconfiguration (DPR) to be able to change certain parts of the FPGA design at run time and on demand without interrupting the rest of the system. • Demonstrate the applicability of the platform in different test-bench applications. In order to select the best approach for the platform design in terms of processing alternatives, a study of the evolution of the state-of-the-art platforms is required to analyse how different architectures cope with new more demanding applications and scenarios: security, mixed-critical systems for aerospace, multimedia applications, or military environments, among others. In all these scenarios, important changes in the required processing bandwidth or the complexity of the algorithms used are provoking the migration of the platforms from single microprocessor architectures to multiprocessing and heterogeneous solutions with more instant power consumption but higher energy efficiency. Within these solutions, FPGAs and Systems on Chip including FPGA fabric and dedicated hard processors, offer a good trade of among flexibility, processing performance, energy consumption and price, when they are used in demanding applications where working conditions are very likely to vary over time and high complex algorithms are required. The platform architecture proposed in this PhD Thesis is called HiReCookie. It includes an SRAM-based FPGA as the main and only processing unit. The FPGA selected, the Xilinx Spartan-6 LX150, was at the beginning of this work the best choice in terms of amount of resources and power. Although, the power levels are the lowest of these kind of devices, they can be still very high for distributed systems that normally work powered by batteries. For that reason, it is necessary to include different energy saving possibilities to increase the usability of the platform. In order to reduce energy consumption, the platform architecture is divided into different power islands so that only those parts of the systems that are strictly needed are powered on, while the rest of the islands can be completely switched off. This allows a combination of different low power modes to decrease energy. In addition, one of the most important handicaps of SRAM-based FPGAs is that they are not alive at power up. Therefore, recovering the system from a switch-off state requires to reload the FPGA configuration from a non-volatile memory device. For that reason, this PhD Thesis also proposes a methodology to compress the FPGA configuration file in order to reduce time and energy during the initial configuration process. Although some of the requirements for the design of HPADS are already covered by the design of the HiReCookie platform, it is necessary to continue improving energy efficiency, computing performance and fault tolerance. This is only possible by exploiting all the opportunities provided by the processing architectures configured inside the FPGA. Therefore, the second part of the thesis details the design of the so called ARTICo3 FPGA architecture to enhance the already intrinsic capabilities of the FPGA. ARTICo3 is a DPR-capable bus-based virtual architecture for multiple HW acceleration in SRAM-based FPGAs. The architecture provides support for dynamic resource management in real time. In this way, by using DPR, it will be possible to change the levels of computing performance, energy consumption and fault tolerance on demand by increasing or decreasing the amount of resources used by the different tasks. Apart from the detailed design of the architecture and its implementation in different FPGA devices, different validation tests and comparisons are also shown. The main objectives targeted by this FPGA architecture are listed as follows: • Provide a method based on a multithread approach such as those offered by CUDA (Compute Unified Device Architecture) or OpenCL kernel executions, where kernels are executed in a variable number of HW accelerators without requiring application code changes. • Provide an architecture to dynamically adapt working points according to either self-measured or external parameters in terms of energy consumption, fault tolerance and computing performance. Taking advantage of DPR capabilities, the architecture must provide support for a dynamic use of resources in real time. • Exploit concurrent processing capabilities in a standard bus-based system by optimizing data transactions to and from HW accelerators. • Measure the advantage of HW acceleration as a technique to boost performance to improve processing times and save energy by reducing active times for distributed embedded systems. • Dynamically change the levels of HW redundancy to adapt fault tolerance in real time. • Provide HW abstraction from SW application design. FPGAs give the possibility of designing specific HW blocks for every required task to optimise performance while some of them include the possibility of including DPR. Apart from the possibilities provided by manufacturers, the way these HW modules are organised, addressed and multiplexed in area and time can improve computing performance and energy consumption. At the same time, fault tolerance and security techniques can also be dynamically included using DPR. However, the inherent complexity of designing new HW modules for every application is not negligible. It does not only consist of the HW description, but also the design of drivers and interfaces with the rest of the system, while the design space is widened and more complex to define and program. Even though the tools provided by the majority of manufacturers already include predefined bus interfaces, commercial IPs, and templates to ease application prototyping, it is necessary to improve these capabilities. By adding new architectures on top of them, it is possible to take advantage of parallelization and HW redundancy while providing a framework to ease the use of dynamic resource management. ARTICo3 works within a solution space where working points change at run time in a 3D space defined by three different axes: Computation, Consumption, and Fault Tolerance. Therefore, every working point is found as a trade-off solution among these three axes. By means of DPR, different accelerators can be multiplexed so that the amount of available resources for any application is virtually unlimited. Taking advantage of DPR capabilities and a novel way of transmitting data to the reconfigurable HW accelerators, it is possible to dedicate a dynamically-changing number of resources for a given task in order to either boost computing speed or adding HW redundancy and a voting process to increase fault-tolerance levels. At the same time, using an optimised amount of resources for a given task reduces energy consumption by reducing instant power or computing time. In order to keep level complexity under certain limits, it is important that HW changes are transparent for the application code. Therefore, different levels of transparency are targeted by the system: • Scalability transparency: a task must be able to expand its resources without changing the system structure or application algorithms. • Performance transparency: the system must reconfigure itself as load changes. • Replication transparency: multiple instances of the same task are loaded to increase reliability and performance. • Location transparency: resources are accessed with no knowledge of their location by the application code. • Failure transparency: task must be completed despite a failure in some components. • Concurrency transparency: different tasks will work in a concurrent way transparent to the application code. Therefore, as it can be seen, the Thesis is contributing in two different ways. First with the design of the HiReCookie platform and, second with the design of the ARTICo3 architecture. The main contributions of this PhD Thesis are then listed below: • Architecture of the HiReCookie platform including: o Compatibility of the processing layer for high performance applications with the Cookies Wireless Sensor Network platform for fast prototyping and implementation. o A division of the architecture in power islands. o All the different low-power modes. o The creation of the partial-initial bitstream together with the wake-up policies of the node. • The design of the reconfigurable architecture for SRAM FPGAs: ARTICo3: o A model of computation and execution modes inspired in CUDA but based on reconfigurable HW with a dynamic number of thread blocks per kernel. o A structure to optimise burst data transactions providing coalesced or parallel data to HW accelerators, parallel voting process and reduction operation. o The abstraction provided to the host processor with respect to the operation of the kernels in terms of the number of replicas, modes of operation, location in the reconfigurable area and addressing. o The architecture of the modules representing the thread blocks to make the system scalable by adding functional units only adding an access to a BRAM port. o The online characterization of the kernels to provide information to a scheduler or resource manager in terms of energy consumption and processing time when changing among different fault-tolerance levels, as well as if a kernel is expected to work in the memory-bounded or computing-bounded areas. The document of the Thesis is divided into two main parts with a total of five chapters. First, after motivating the need for new platforms to cover new more demanding applications, the design of the HiReCookie platform, its parts and several partial tests are detailed. The design of the platform alone does not cover all the needs of these applications. Therefore, the second part describes the architecture inside the FPGA, called ARTICo3, proposed in this PhD Thesis. The architecture and its implementation are tested in terms of energy consumption and computing performance showing different possibilities to improve fault tolerance and how this impact in energy and time of processing. Chapter 1 shows the main goals of this PhD Thesis and the technology background required to follow the rest of the document. Chapter 2 shows all the details about the design of the FPGA-based platform HiReCookie. Chapter 3 describes the ARTICo3 architecture. Chapter 4 is focused on the validation tests of the ARTICo3 architecture. An application for proof of concept is explained where typical kernels related to image processing and encryption algorithms are used. Further experimental analyses are performed using these kernels. Chapter 5 concludes the document analysing conclusions, comments about the contributions of the work, and some possible future lines for the work.

Nepfix: on-demand cloud elastic simulation of networks of evolutionary processors

Una Red de Procesadores Evolutivos o NEP (por sus siglas en ingles), es un modelo computacional inspirado por el modelo evolutivo de las celulas, específicamente por las reglas de multiplicación de las mismas. Esta inspiración hace que el modelo sea una abstracción sintactica de la manipulation de information de las celulas. En particu¬lar, una NEP define una maquina de cómputo teorica capaz de resolver problemas NP completos de manera eficiente en tóerminos de tiempo. En la praóctica, se espera que las NEP simuladas en móaquinas computacionales convencionales puedan resolver prob¬lemas reales complejos (que requieran ser altamente escalables) a cambio de una alta complejidad espacial. En el modelo NEP, las cóelulas estóan representadas por palabras que codifican sus secuencias de ADN. Informalmente, en cualquier momento de cómputo del sistema, su estado evolutivo se describe como un coleccion de palabras, donde cada una de ellas representa una celula. Estos momentos fijos de evolucion se denominan configuraciones. De manera similar al modelo biologico, las palabras (celulas) mutan y se dividen en base a bio-operaciones sencillas, pero solo aquellas palabras aptas (como ocurre de forma parecida en proceso de selection natural) seran conservadas para la siguiente configuracióon. Una NEP como herramienta de computation, define una arquitectura paralela y distribuida de procesamiento simbolico, en otras palabras, una red de procesadores de lenguajes. Desde el momento en que el modelo fue propuesto a la comunidad científica en el año 2001, múltiples variantes se han desarrollado y sus propiedades respecto a la completitud computacional, eficiencia y universalidad han sido ampliamente estudiadas y demostradas. En la actualidad, por tanto, podemos considerar que el modelo teórico NEP se encuentra en el estadio de la madurez. La motivación principal de este Proyecto de Fin de Grado, es proponer una aproxi-mación práctica que permita dar un salto del modelo teórico NEP a una implantación real que permita su ejecucion en plataformas computacionales de alto rendimiento, con el fin de solucionar problemas complejos que demanda la sociedad actual. Hasta el momento, las herramientas desarrolladas para la simulation del modelo NEP, si bien correctas y con resultados satisfactorios, normalmente estón atadas a su entorno de ejecucion, ya sea el uso de hardware específico o implementaciones particulares de un problema. En este contexto, el propósito fundamental de este trabajo es el desarrollo de Nepfix, una herramienta generica y extensible para la ejecucion de cualquier algo¬ritmo de un modelo NEP (o alguna de sus variantes), ya sea de forma local, como una aplicación tradicional, o distribuida utilizando los servicios de la nube. Nepfix es una aplicacion software desarrollada durante 7 meses y que actualmente se encuentra en su segunda iteration, una vez abandonada la fase de prototipo. Nepfix ha sido disenada como una aplicacion modular escrita en Java 8 y autocontenida, es decir, no requiere de un entorno de ejecucion específico (cualquier maquina virtual de Java es un contenedor vólido). Nepfix contiene dos componentes o móodulos. El primer móodulo corresponde a la ejecución de una NEP y es por lo tanto, el simulador. Para su desarrollo, se ha tenido en cuenta el estado actual del modelo, es decir, las definiciones de los procesadores y filtros mas comunes que conforman la familia del modelo NEP. Adicionalmente, este componente ofrece flexibilidad en la ejecucion, pudiendo ampliar las capacidades del simulador sin modificar Nepfix, usando para ello un lenguaje de scripting. Dentro del desarrollo de este componente, tambióen se ha definido un estóandar de representacióon del modelo NEP basado en el formato JSON y se propone una forma de representation y codificación de las palabras, necesaria para la comunicación entre servidores. Adicional-mente, una característica importante de este componente, es que se puede considerar una aplicacion aislada y por tanto, la estrategia de distribution y ejecución son total-mente independientes. El segundo moódulo, corresponde a la distribucióon de Nepfix en la nube. Este de-sarrollo es el resultado de un proceso de i+D, que tiene una componente científica considerable. Vale la pena resaltar el desarrollo de este modulo no solo por los resul-tados prócticos esperados, sino por el proceso de investigation que se se debe abordar con esta nueva perspectiva para la ejecución de sistemas de computación natural. La principal característica de las aplicaciones que se ejecutan en la nube es que son gestionadas por la plataforma y normalmente se encapsulan en un contenedor. En el caso de Nepfix, este contenedor es una aplicacion Spring que utiliza el protocolo HTTP o AMQP para comunicarse con el resto de instancias. Como valor añadido, Nepfix aborda dos perspectivas de implementation distintas (que han sido desarrolladas en dos iteraciones diferentes) del modelo de distribution y ejecucion, que tienen un impacto muy significativo en las capacidades y restricciones del simulador. En concreto, la primera iteration utiliza un modelo de ejecucion asincrono. En esta perspectiva asincrona, los componentes de la red NEP (procesadores y filtros) son considerados como elementos reactivos a la necesidad de procesar una palabra. Esta implementation es una optimization de una topologia comun en el modelo NEP que permite utilizar herramientas de la nube para lograr un escalado transparente (en lo ref¬erente al balance de carga entre procesadores) pero produce efectos no deseados como indeterminacion en el orden de los resultados o imposibilidad de distribuir eficiente-mente redes fuertemente interconectadas. Por otro lado, la segunda iteration corresponde al modelo de ejecucion sincrono. Los elementos de una red NEP siguen un ciclo inicio-computo-sincronizacion hasta que el problema se ha resuelto. Esta perspectiva sincrona representa fielmente al modelo teórico NEP pero el proceso de sincronizacion es costoso y requiere de infraestructura adicional. En concreto, se requiere un servidor de colas de mensajes RabbitMQ. Sin embargo, en esta perspectiva los beneficios para problemas suficientemente grandes superan a los inconvenientes, ya que la distribuciín es inmediata (no hay restricciones), aunque el proceso de escalado no es trivial. En definitiva, el concepto de Nepfix como marco computacional se puede considerar satisfactorio: la tecnología es viable y los primeros resultados confirman que las carac-terísticas que se buscaban originalmente se han conseguido. Muchos frentes quedan abiertos para futuras investigaciones. En este documento se proponen algunas aproxi-maciones a la solucion de los problemas identificados como la recuperacion de errores y la division dinamica de una NEP en diferentes subdominios. Por otra parte, otros prob-lemas, lejos del alcance de este proyecto, quedan abiertos a un futuro desarrollo como por ejemplo, la estandarización de la representación de las palabras y optimizaciones en la ejecucion del modelo síncrono. Finalmente, algunos resultados preliminares de este Proyecto de Fin de Grado han sido presentados recientemente en formato de artículo científico en la "International Work-Conference on Artificial Neural Networks (IWANN)-2015" y publicados en "Ad-vances in Computational Intelligence" volumen 9094 de "Lecture Notes in Computer Science" de Springer International Publishing. Lo anterior, es una confirmation de que este trabajo mas que un Proyecto de Fin de Grado, es solo el inicio de un trabajo que puede tener mayor repercusion en la comunidad científica. Abstract Network of Evolutionary Processors -NEP is a computational model inspired by the evolution of cell populations, which might model some properties of evolving cell communities at the syntactical level. NEP defines theoretical computing devices able to solve NP complete problems in an efficient manner. In this model, cells are represented by words which encode their DNA sequences. Informally, at any moment of time, the evolutionary system is described by a collection of words, where each word represents one cell. Cells belong to species and their community evolves according to mutations and division which are defined by operations on words. Only those cells are accepted as surviving (correct) ones which are represented by a word in a given set of words, called the genotype space of the species. This feature is analogous with the natural process of evolution. Formally, NEP is based on an architecture for parallel and distributed processing, in other words, a network of language processors. Since the date when NEP was pro¬posed, several extensions and variants have appeared engendering a new set of models named Networks of Bio-inspired Processors (NBP). During this time, several works have proved the computational power of NBP. Specifically, their efficiency, universality, and computational completeness have been thoroughly investigated. Therefore, we can say that the NEP model has reached its maturity. The main motivation for this End of Grade project (EOG project in short) is to propose a practical approximation that allows to close the gap between theoretical NEP model and a practical implementation in high performing computational platforms in order to solve some of high the high complexity problems society requires today. Up until now tools developed to simulate NEPs, while correct and successful, are usu¬ally tightly coupled to the execution environment, using specific software frameworks (Hadoop) or direct hardware usage (GPUs). Within this context the main purpose of this work is the development of Nepfix, a generic and extensible tool that aims to execute algorithms based on NEP model and compatible variants in a local way, similar to a traditional application or in a distributed cloud environment. Nepfix as an application was developed during a 7 month cycle and is undergoing its second iteration once the prototype period was abandoned. Nepfix is designed as a modular self-contained application written in Java 8, that is, no additional external dependencies are required and it does not rely on an specific execution environment, any JVM is a valid container. Nepfix is made of two components or modules. The first module corresponds to the NEP execution and therefore simulation. During the development the current state of the theoretical model was used as a reference including most common filters and processors. Additionally extensibility is provided by the use of Python as a scripting language to run custom logic. Along with the simulation a definition language for NEP has been defined based on JSON as well as a mechanisms to represent words and their possible manipulations. NEP simulator is isolated from distribution and as mentioned before different applications that include it as a dependency are possible, the distribution of NEPs is an example of this. The second module corresponds to executing Nepfix in the cloud. The development carried a heavy R&D process since this front was not explored by other research groups until now. It's important to point out that the development of this module is not focused on results at this point in time, instead we focus on feasibility and discovery of this new perspective to execute natural computing systems and NEPs specifically. The main properties of cloud applications is that they are managed by the platform and are encapsulated in a container. For Nepfix a Spring application becomes the container and the HTTP or AMQP protocols are used for communication with the rest of the instances. Different execution perspectives were studied, namely asynchronous and synchronous models were developed for solving different kind of problems using NEPs. Different limitations and restrictions manifest in both models and are explored in detail in the respective chapters. In conclusion we can consider that Nepfix as a computational framework is suc-cessful: Cloud technology is ready for the challenge and the first results reassure that the properties Nepfix project pursued were met. Many investigation branches are left open for future investigations. In this EOG implementation guidelines are proposed for some of them like error recovery or dynamic NEP splitting. On the other hand other interesting problems that were not in the scope of this project were identified during development like word representation standardization or NEP model optimizations. As a confirmation that the results of this work can be useful to the scientific com-munity a preliminary version of this project was published in The International Work- Conference on Artificial Neural Networks (IWANN) in May 2015. Development has not stopped since that point and while Nepfix in it's current state can not be consid¬ered a final product the most relevant ideas, possible problems and solutions that were produced during the seven months development cycle are worthy to be gathered and presented giving a meaning to this EOG work.

Parallel Computer Vision Algorithms for Graphics Processing Units

La evolución de los teléfonos móviles inteligentes, dotados de cámaras digitales, está provocando una creciente demanda de aplicaciones cada vez más complejas que necesitan algoritmos de visión artificial en tiempo real; puesto que el tamaño de las señales de vídeo no hace sino aumentar y en cambio el rendimiento de los procesadores de un solo núcleo se ha estancado, los nuevos algoritmos que se diseñen para visión artificial han de ser paralelos para poder ejecutarse en múltiples procesadores y ser computacionalmente escalables. Una de las clases de procesadores más interesantes en la actualidad se encuentra en las tarjetas gráficas (GPU), que son dispositivos que ofrecen un alto grado de paralelismo, un excelente rendimiento numérico y una creciente versatilidad, lo que los hace interesantes para llevar a cabo computación científica. En esta tesis se exploran dos aplicaciones de visión artificial que revisten una gran complejidad computacional y no pueden ser ejecutadas en tiempo real empleando procesadores tradicionales. En cambio, como se demuestra en esta tesis, la paralelización de las distintas subtareas y su implementación sobre una GPU arrojan los resultados deseados de ejecución con tasas de refresco interactivas. Asimismo, se propone una técnica para la evaluación rápida de funciones de complejidad arbitraria especialmente indicada para su uso en una GPU. En primer lugar se estudia la aplicación de técnicas de síntesis de imágenes virtuales a partir de únicamente dos cámaras lejanas y no paralelas—en contraste con la configuración habitual en TV 3D de cámaras cercanas y paralelas—con información de color y profundidad. Empleando filtros de mediana modificados para la elaboración de un mapa de profundidad virtual y proyecciones inversas, se comprueba que estas técnicas son adecuadas para una libre elección del punto de vista. Además, se demuestra que la codificación de la información de profundidad con respecto a un sistema de referencia global es sumamente perjudicial y debería ser evitada. Por otro lado se propone un sistema de detección de objetos móviles basado en técnicas de estimación de densidad con funciones locales. Este tipo de técnicas es muy adecuada para el modelado de escenas complejas con fondos multimodales, pero ha recibido poco uso debido a su gran complejidad computacional. El sistema propuesto, implementado en tiempo real sobre una GPU, incluye propuestas para la estimación dinámica de los anchos de banda de las funciones locales, actualización selectiva del modelo de fondo, actualización de la posición de las muestras de referencia del modelo de primer plano empleando un filtro de partículas multirregión y selección automática de regiones de interés para reducir el coste computacional. Los resultados, evaluados sobre diversas bases de datos y comparados con otros algoritmos del estado del arte, demuestran la gran versatilidad y calidad de la propuesta. Finalmente se propone un método para la aproximación de funciones arbitrarias empleando funciones continuas lineales a tramos, especialmente indicada para su implementación en una GPU mediante el uso de las unidades de filtraje de texturas, normalmente no utilizadas para cómputo numérico. La propuesta incluye un riguroso análisis matemático del error cometido en la aproximación en función del número de muestras empleadas, así como un método para la obtención de una partición cuasióptima del dominio de la función para minimizar el error. ABSTRACT The evolution of smartphones, all equipped with digital cameras, is driving a growing demand for ever more complex applications that need to rely on real-time computer vision algorithms. However, video signals are only increasing in size, whereas the performance of single-core processors has somewhat stagnated in the past few years. Consequently, new computer vision algorithms will need to be parallel to run on multiple processors and be computationally scalable. One of the most promising classes of processors nowadays can be found in graphics processing units (GPU). These are devices offering a high parallelism degree, excellent numerical performance and increasing versatility, which makes them interesting to run scientific computations. In this thesis, we explore two computer vision applications with a high computational complexity that precludes them from running in real time on traditional uniprocessors. However, we show that by parallelizing subtasks and implementing them on a GPU, both applications attain their goals of running at interactive frame rates. In addition, we propose a technique for fast evaluation of arbitrarily complex functions, specially designed for GPU implementation. First, we explore the application of depth-image–based rendering techniques to the unusual configuration of two convergent, wide baseline cameras, in contrast to the usual configuration used in 3D TV, which are narrow baseline, parallel cameras. By using a backward mapping approach with a depth inpainting scheme based on median filters, we show that these techniques are adequate for free viewpoint video applications. In addition, we show that referring depth information to a global reference system is ill-advised and should be avoided. Then, we propose a background subtraction system based on kernel density estimation techniques. These techniques are very adequate for modelling complex scenes featuring multimodal backgrounds, but have not been so popular due to their huge computational and memory complexity. The proposed system, implemented in real time on a GPU, features novel proposals for dynamic kernel bandwidth estimation for the background model, selective update of the background model, update of the position of reference samples of the foreground model using a multi-region particle filter, and automatic selection of regions of interest to reduce computational cost. The results, evaluated on several databases and compared to other state-of-the-art algorithms, demonstrate the high quality and versatility of our proposal. Finally, we propose a general method for the approximation of arbitrarily complex functions using continuous piecewise linear functions, specially formulated for GPU implementation by leveraging their texture filtering units, normally unused for numerical computation. Our proposal features a rigorous mathematical analysis of the approximation error in function of the number of samples, as well as a method to obtain a suboptimal partition of the domain of the function to minimize approximation error.