Optimización de aperturas mediante técnicas de algoritmos evolutivos

Los sistemas de imagen por ultrasonidos son hoy una herramienta indispensable en aplicaciones de diagnóstico en medicina y son cada vez más utilizados en aplicaciones industriales en el área de ensayos no destructivos. El array es el elemento primario de estos sistemas y su diseño determina las características de los haces que se pueden construir (forma y tamaño del lóbulo principal, de los lóbulos secundarios y de rejilla, etc.), condicionando la calidad de las imágenes que pueden conseguirse. En arrays regulares la distancia máxima entre elementos se establece en media longitud de onda para evitar la formación de artefactos. Al mismo tiempo, la resolución en la imagen de los objetos presentes en la escena aumenta con el tamaño total de la apertura, por lo que una pequeña mejora en la calidad de la imagen se traduce en un aumento significativo del número de elementos del transductor. Esto tiene, entre otras, las siguientes consecuencias: Problemas de fabricación de los arrays por la gran densidad de conexiones (téngase en cuenta que en aplicaciones típicas de imagen médica, el valor de la longitud de onda es de décimas de milímetro) Baja relación señal/ruido y, en consecuencia, bajo rango dinámico de las señales por el reducido tamaño de los elementos. Complejidad de los equipos que deben manejar un elevado número de canales independientes. Por ejemplo, se necesitarían 10.000 elementos separados λ 2 para una apertura cuadrada de 50 λ. Una forma sencilla para resolver estos problemas existen alternativas que reducen el número de elementos activos de un array pleno, sacrificando hasta cierto punto la calidad de imagen, la energía emitida, el rango dinámico, el contraste, etc. Nosotros planteamos una estrategia diferente, y es desarrollar una metodología de optimización capaz de hallar de forma sistemática configuraciones de arrays de ultrasonido adaptados a aplicaciones específicas. Para realizar dicha labor proponemos el uso de los algoritmos evolutivos para buscar y seleccionar en el espacio de configuraciones de arrays aquellas que mejor se adaptan a los requisitos fijados por cada aplicación. En la memoria se trata el problema de la codificación de las configuraciones de arrays para que puedan ser utilizados como individuos de la población sobre la que van a actuar los algoritmos evolutivos. También se aborda la definición de funciones de idoneidad que permitan realizar comparaciones entre dichas configuraciones de acuerdo con los requisitos y restricciones de cada problema de diseño. Finalmente, se propone emplear el algoritmo multiobjetivo NSGA II como herramienta primaria de optimización y, a continuación, utilizar algoritmos mono-objetivo tipo Simulated Annealing para seleccionar y retinar las soluciones proporcionadas por el NSGA II. Muchas de las funciones de idoneidad que definen las características deseadas del array a diseñar se calculan partir de uno o más patrones de radiación generados por cada solución candidata. La obtención de estos patrones con los métodos habituales de simulación de campo acústico en banda ancha requiere tiempos de cálculo muy grandes que pueden hacer inviable el proceso de optimización con algoritmos evolutivos en la práctica. Como solución, se propone un método de cálculo en banda estrecha que reduce en, al menos, un orden de magnitud el tiempo de cálculo necesario Finalmente se presentan una serie de ejemplos, con arrays lineales y bidimensionales, para validar la metodología de diseño propuesta comparando experimentalmente las características reales de los diseños construidos con las predicciones del método de optimización. ABSTRACT Currently, the ultrasound imaging system is one of the powerful tools in medical diagnostic and non-destructive testing for industrial applications. Ultrasonic arrays design determines the beam characteristics (main and secondary lobes, beam pattern, etc...) which assist to enhance the image resolution. The maximum distance between the elements of the array should be the half of the wavelength to avoid the formation of grating lobes. At the same time, the image resolution of the target in the region of interest increases with the aperture size. Consequently, the larger number of elements in arrays assures the better image quality but this improvement contains the following drawbacks: Difficulties in the arrays manufacturing due to the large connection density. Low noise to signal ratio. Complexity of the ultrasonic system to handle large number of channels. The easiest way to resolve these issues is to reduce the number of active elements in full arrays, but on the other hand the image quality, dynamic range, contrast, etc, are compromised by this solutions In this thesis, an optimization methodology able to find ultrasound array configurations adapted for specific applications is presented. The evolutionary algorithms are used to obtain the ideal arrays among the existing configurations. This work addressed problems such as: the codification of ultrasound arrays to be interpreted as individuals in the evolutionary algorithm population and the fitness function and constraints, which will assess the behaviour of individuals. Therefore, it is proposed to use the multi-objective algorithm NSGA-II as a primary optimization tool, and then use the mono-objective Simulated Annealing algorithm to select and refine the solutions provided by the NSGA I I . The acoustic field is calculated many times for each individual and in every generation for every fitness functions. An acoustic narrow band field simulator, where the number of operations is reduced, this ensures a quick calculation of the acoustic field to reduce the expensive computing time required by these functions we have employed. Finally a set of examples are presented in order to validate our proposed design methodology, using linear and bidimensional arrays where the actual characteristics of the design are compared with the predictions of the optimization methodology.

Run-Time Scalable Hardware for Reconfigurable Systems

La optimización de parámetros tales como el consumo de potencia, la cantidad de recursos lógicos empleados o la ocupación de memoria ha sido siempre una de las preocupaciones principales a la hora de diseñar sistemas embebidos. Esto es debido a que se trata de sistemas dotados de una cantidad de recursos limitados, y que han sido tradicionalmente empleados para un propósito específico, que permanece invariable a lo largo de toda la vida útil del sistema. Sin embargo, el uso de sistemas embebidos se ha extendido a áreas de aplicación fuera de su ámbito tradicional, caracterizadas por una mayor demanda computacional. Así, por ejemplo, algunos de estos sistemas deben llevar a cabo un intenso procesado de señales multimedia o la transmisión de datos mediante sistemas de comunicaciones de alta capacidad. Por otra parte, las condiciones de operación del sistema pueden variar en tiempo real. Esto sucede, por ejemplo, si su funcionamiento depende de datos medidos por el propio sistema o recibidos a través de la red, de las demandas del usuario en cada momento, o de condiciones internas del propio dispositivo, tales como la duración de la batería. Como consecuencia de la existencia de requisitos de operación dinámicos es necesario ir hacia una gestión dinámica de los recursos del sistema. Si bien el software es inherentemente flexible, no ofrece una potencia computacional tan alta como el hardware. Por lo tanto, el hardware reconfigurable aparece como una solución adecuada para tratar con mayor flexibilidad los requisitos variables dinámicamente en sistemas con alta demanda computacional. La flexibilidad y adaptabilidad del hardware requieren de dispositivos reconfigurables que permitan la modificación de su funcionalidad bajo demanda. En esta tesis se han seleccionado las FPGAs (Field Programmable Gate Arrays) como los dispositivos más apropiados, hoy en día, para implementar sistemas basados en hardware reconfigurable De entre todas las posibilidades existentes para explotar la capacidad de reconfiguración de las FPGAs comerciales, se ha seleccionado la reconfiguración dinámica y parcial. Esta técnica consiste en substituir una parte de la lógica del dispositivo, mientras el resto continúa en funcionamiento. La capacidad de reconfiguración dinámica y parcial de las FPGAs es empleada en esta tesis para tratar con los requisitos de flexibilidad y de capacidad computacional que demandan los dispositivos embebidos. La propuesta principal de esta tesis doctoral es el uso de arquitecturas de procesamiento escalables espacialmente, que son capaces de adaptar su funcionalidad y rendimiento en tiempo real, estableciendo un compromiso entre dichos parámetros y la cantidad de lógica que ocupan en el dispositivo. A esto nos referimos con arquitecturas con huellas escalables. En particular, se propone el uso de arquitecturas altamente paralelas, modulares, regulares y con una alta localidad en sus comunicaciones, para este propósito. El tamaño de dichas arquitecturas puede ser modificado mediante la adición o eliminación de algunos de los módulos que las componen, tanto en una dimensión como en dos. Esta estrategia permite implementar soluciones escalables, sin tener que contar con una versión de las mismas para cada uno de los tamaños posibles de la arquitectura. De esta manera se reduce significativamente el tiempo necesario para modificar su tamaño, así como la cantidad de memoria necesaria para almacenar todos los archivos de configuración. En lugar de proponer arquitecturas para aplicaciones específicas, se ha optado por patrones de procesamiento genéricos, que pueden ser ajustados para solucionar distintos problemas en el estado del arte. A este respecto, se proponen patrones basados en esquemas sistólicos, así como de tipo wavefront. Con el objeto de poder ofrecer una solución integral, se han tratado otros aspectos relacionados con el diseño y el funcionamiento de las arquitecturas, tales como el control del proceso de reconfiguración de la FPGA, la integración de las arquitecturas en el resto del sistema, así como las técnicas necesarias para su implementación. Por lo que respecta a la implementación, se han tratado distintos aspectos de bajo nivel dependientes del dispositivo. Algunas de las propuestas realizadas a este respecto en la presente tesis doctoral son un router que es capaz de garantizar el correcto rutado de los módulos reconfigurables dentro del área destinada para ellos, así como una estrategia para la comunicación entre módulos que no introduce ningún retardo ni necesita emplear recursos configurables del dispositivo. El flujo de diseño propuesto se ha automatizado mediante una herramienta denominada DREAMS. La herramienta se encarga de la modificación de las netlists correspondientes a cada uno de los módulos reconfigurables del sistema, y que han sido generadas previamente mediante herramientas comerciales. Por lo tanto, el flujo propuesto se entiende como una etapa de post-procesamiento, que adapta esas netlists a los requisitos de la reconfiguración dinámica y parcial. Dicha modificación la lleva a cabo la herramienta de una forma completamente automática, por lo que la productividad del proceso de diseño aumenta de forma evidente. Para facilitar dicho proceso, se ha dotado a la herramienta de una interfaz gráfica. El flujo de diseño propuesto, y la herramienta que lo soporta, tienen características específicas para abordar el diseño de las arquitecturas dinámicamente escalables propuestas en esta tesis. Entre ellas está el soporte para el realojamiento de módulos reconfigurables en posiciones del dispositivo distintas a donde el módulo es originalmente implementado, así como la generación de estructuras de comunicación compatibles con la simetría de la arquitectura. El router has sido empleado también en esta tesis para obtener un rutado simétrico entre nets equivalentes. Dicha posibilidad ha sido explotada para aumentar la protección de circuitos con altos requisitos de seguridad, frente a ataques de canal lateral, mediante la implantación de lógica complementaria con rutado idéntico. Para controlar el proceso de reconfiguración de la FPGA, se propone en esta tesis un motor de reconfiguración especialmente adaptado a los requisitos de las arquitecturas dinámicamente escalables. Además de controlar el puerto de reconfiguración, el motor de reconfiguración ha sido dotado de la capacidad de realojar módulos reconfigurables en posiciones arbitrarias del dispositivo, en tiempo real. De esta forma, basta con generar un único bitstream por cada módulo reconfigurable del sistema, independientemente de la posición donde va a ser finalmente reconfigurado. La estrategia seguida para implementar el proceso de realojamiento de módulos es diferente de las propuestas existentes en el estado del arte, pues consiste en la composición de los archivos de configuración en tiempo real. De esta forma se consigue aumentar la velocidad del proceso, mientras que se reduce la longitud de los archivos de configuración parciales a almacenar en el sistema. El motor de reconfiguración soporta módulos reconfigurables con una altura menor que la altura de una región de reloj del dispositivo. Internamente, el motor se encarga de la combinación de los frames que describen el nuevo módulo, con la configuración existente en el dispositivo previamente. El escalado de las arquitecturas de procesamiento propuestas en esta tesis también se puede beneficiar de este mecanismo. Se ha incorporado también un acceso directo a una memoria externa donde se pueden almacenar bitstreams parciales. Para acelerar el proceso de reconfiguración se ha hecho funcionar el ICAP por encima de la máxima frecuencia de reloj aconsejada por el fabricante. Así, en el caso de Virtex-5, aunque la máxima frecuencia del reloj deberían ser 100 MHz, se ha conseguido hacer funcionar el puerto de reconfiguración a frecuencias de operación de hasta 250 MHz, incluyendo el proceso de realojamiento en tiempo real. Se ha previsto la posibilidad de portar el motor de reconfiguración a futuras familias de FPGAs. Por otro lado, el motor de reconfiguración se puede emplear para inyectar fallos en el propio dispositivo hardware, y así ser capaces de evaluar la tolerancia ante los mismos que ofrecen las arquitecturas reconfigurables. Los fallos son emulados mediante la generación de archivos de configuración a los que intencionadamente se les ha introducido un error, de forma que se modifica su funcionalidad. Con el objetivo de comprobar la validez y los beneficios de las arquitecturas propuestas en esta tesis, se han seguido dos líneas principales de aplicación. En primer lugar, se propone su uso como parte de una plataforma adaptativa basada en hardware evolutivo, con capacidad de escalabilidad, adaptabilidad y recuperación ante fallos. En segundo lugar, se ha desarrollado un deblocking filter escalable, adaptado a la codificación de vídeo escalable, como ejemplo de aplicación de las arquitecturas de tipo wavefront propuestas. El hardware evolutivo consiste en el uso de algoritmos evolutivos para diseñar hardware de forma autónoma, explotando la flexibilidad que ofrecen los dispositivos reconfigurables. En este caso, los elementos de procesamiento que componen la arquitectura son seleccionados de una biblioteca de elementos presintetizados, de acuerdo con las decisiones tomadas por el algoritmo evolutivo, en lugar de definir la configuración de las mismas en tiempo de diseño. De esta manera, la configuración del core puede cambiar cuando lo hacen las condiciones del entorno, en tiempo real, por lo que se consigue un control autónomo del proceso de reconfiguración dinámico. Así, el sistema es capaz de optimizar, de forma autónoma, su propia configuración. El hardware evolutivo tiene una capacidad inherente de auto-reparación. Se ha probado que las arquitecturas evolutivas propuestas en esta tesis son tolerantes ante fallos, tanto transitorios, como permanentes y acumulativos. La plataforma evolutiva se ha empleado para implementar filtros de eliminación de ruido. La escalabilidad también ha sido aprovechada en esta aplicación. Las arquitecturas evolutivas escalables permiten la adaptación autónoma de los cores de procesamiento ante fluctuaciones en la cantidad de recursos disponibles en el sistema. Por lo tanto, constituyen un ejemplo de escalabilidad dinámica para conseguir un determinado nivel de calidad, que puede variar en tiempo real. Se han propuesto dos variantes de sistemas escalables evolutivos. El primero consiste en un único core de procesamiento evolutivo, mientras que el segundo está formado por un número variable de arrays de procesamiento. La codificación de vídeo escalable, a diferencia de los codecs no escalables, permite la decodificación de secuencias de vídeo con diferentes niveles de calidad, de resolución temporal o de resolución espacial, descartando la información no deseada. Existen distintos algoritmos que soportan esta característica. En particular, se va a emplear el estándar Scalable Video Coding (SVC), que ha sido propuesto como una extensión de H.264/AVC, ya que este último es ampliamente utilizado tanto en la industria, como a nivel de investigación. Para poder explotar toda la flexibilidad que ofrece el estándar, hay que permitir la adaptación de las características del decodificador en tiempo real. El uso de las arquitecturas dinámicamente escalables es propuesto en esta tesis con este objetivo. El deblocking filter es un algoritmo que tiene como objetivo la mejora de la percepción visual de la imagen reconstruida, mediante el suavizado de los "artefactos" de bloque generados en el lazo del codificador. Se trata de una de las tareas más intensivas en procesamiento de datos de H.264/AVC y de SVC, y además, su carga computacional es altamente dependiente del nivel de escalabilidad seleccionado en el decodificador. Por lo tanto, el deblocking filter ha sido seleccionado como prueba de concepto de la aplicación de las arquitecturas dinámicamente escalables para la compresión de video. La arquitectura propuesta permite añadir o eliminar unidades de computación, siguiendo un esquema de tipo wavefront. La arquitectura ha sido propuesta conjuntamente con un esquema de procesamiento en paralelo del deblocking filter a nivel de macrobloque, de tal forma que cuando se varía del tamaño de la arquitectura, el orden de filtrado de los macrobloques varia de la misma manera. El patrón propuesto se basa en la división del procesamiento de cada macrobloque en dos etapas independientes, que se corresponden con el filtrado horizontal y vertical de los bloques dentro del macrobloque. Las principales contribuciones originales de esta tesis son las siguientes: - El uso de arquitecturas altamente regulares, modulares, paralelas y con una intensa localidad en sus comunicaciones, para implementar cores de procesamiento dinámicamente reconfigurables. - El uso de arquitecturas bidimensionales, en forma de malla, para construir arquitecturas dinámicamente escalables, con una huella escalable. De esta forma, las arquitecturas permiten establecer un compromiso entre el área que ocupan en el dispositivo, y las prestaciones que ofrecen en cada momento. Se proponen plantillas de procesamiento genéricas, de tipo sistólico o wavefront, que pueden ser adaptadas a distintos problemas de procesamiento. - Un flujo de diseño y una herramienta que lo soporta, para el diseño de sistemas reconfigurables dinámicamente, centradas en el diseño de las arquitecturas altamente paralelas, modulares y regulares propuestas en esta tesis. - Un esquema de comunicaciones entre módulos reconfigurables que no introduce ningún retardo ni requiere el uso de recursos lógicos propios. - Un router flexible, capaz de resolver los conflictos de rutado asociados con el diseño de sistemas reconfigurables dinámicamente. - Un algoritmo de optimización para sistemas formados por múltiples cores escalables que optimice, mediante un algoritmo genético, los parámetros de dicho sistema. Se basa en un modelo conocido como el problema de la mochila. - Un motor de reconfiguración adaptado a los requisitos de las arquitecturas altamente regulares y modulares. Combina una alta velocidad de reconfiguración, con la capacidad de realojar módulos en tiempo real, incluyendo el soporte para la reconfiguración de regiones que ocupan menos que una región de reloj, así como la réplica de un módulo reconfigurable en múltiples posiciones del dispositivo. - Un mecanismo de inyección de fallos que, empleando el motor de reconfiguración del sistema, permite evaluar los efectos de fallos permanentes y transitorios en arquitecturas reconfigurables. - La demostración de las posibilidades de las arquitecturas propuestas en esta tesis para la implementación de sistemas de hardware evolutivos, con una alta capacidad de procesamiento de datos. - La implementación de sistemas de hardware evolutivo escalables, que son capaces de tratar con la fluctuación de la cantidad de recursos disponibles en el sistema, de una forma autónoma. - Una estrategia de procesamiento en paralelo para el deblocking filter compatible con los estándares H.264/AVC y SVC que reduce el número de ciclos de macrobloque necesarios para procesar un frame de video. - Una arquitectura dinámicamente escalable que permite la implementación de un nuevo deblocking filter, totalmente compatible con los estándares H.264/AVC y SVC, que explota el paralelismo a nivel de macrobloque. El presente documento se organiza en siete capítulos. En el primero se ofrece una introducción al marco tecnológico de esta tesis, especialmente centrado en la reconfiguración dinámica y parcial de FPGAs. También se motiva la necesidad de las arquitecturas dinámicamente escalables propuestas en esta tesis. En el capítulo 2 se describen las arquitecturas dinámicamente escalables. Dicha descripción incluye la mayor parte de las aportaciones a nivel arquitectural realizadas en esta tesis. Por su parte, el flujo de diseño adaptado a dichas arquitecturas se propone en el capítulo 3. El motor de reconfiguración se propone en el 4, mientras que el uso de dichas arquitecturas para implementar sistemas de hardware evolutivo se aborda en el 5. El deblocking filter escalable se describe en el 6, mientras que las conclusiones finales de esta tesis, así como la descripción del trabajo futuro, son abordadas en el capítulo 7. ABSTRACT The optimization of system parameters, such as power dissipation, the amount of hardware resources and the memory footprint, has been always a main concern when dealing with the design of resource-constrained embedded systems. This situation is even more demanding nowadays. Embedded systems cannot anymore be considered only as specific-purpose computers, designed for a particular functionality that remains unchanged during their lifetime. Differently, embedded systems are now required to deal with more demanding and complex functions, such as multimedia data processing and high-throughput connectivity. In addition, system operation may depend on external data, the user requirements or internal variables of the system, such as the battery life-time. All these conditions may vary at run-time, leading to adaptive scenarios. As a consequence of both the growing computational complexity and the existence of dynamic requirements, dynamic resource management techniques for embedded systems are needed. Software is inherently flexible, but it cannot meet the computing power offered by hardware solutions. Therefore, reconfigurable hardware emerges as a suitable technology to deal with the run-time variable requirements of complex embedded systems. Adaptive hardware requires the use of reconfigurable devices, where its functionality can be modified on demand. In this thesis, Field Programmable Gate Arrays (FPGAs) have been selected as the most appropriate commercial technology existing nowadays to implement adaptive hardware systems. There are different ways of exploiting reconfigurability in reconfigurable devices. Among them is dynamic and partial reconfiguration. This is a technique which consists in substituting part of the FPGA logic on demand, while the rest of the device continues working. The strategy followed in this thesis is to exploit the dynamic and partial reconfiguration of commercial FPGAs to deal with the flexibility and complexity demands of state-of-the-art embedded systems. The proposal of this thesis to deal with run-time variable system conditions is the use of spatially scalable processing hardware IP cores, which are able to adapt their functionality or performance at run-time, trading them off with the amount of logic resources they occupy in the device. This is referred to as a scalable footprint in the context of this thesis. The distinguishing characteristic of the proposed cores is that they rely on highly parallel, modular and regular architectures, arranged in one or two dimensions. These architectures can be scaled by means of the addition or removal of the composing blocks. This strategy avoids implementing a full version of the core for each possible size, with the corresponding benefits in terms of scaling and adaptation time, as well as bitstream storage memory requirements. Instead of providing specific-purpose architectures, generic architectural templates, which can be tuned to solve different problems, are proposed in this thesis. Architectures following both systolic and wavefront templates have been selected. Together with the proposed scalable architectural templates, other issues needed to ensure the proper design and operation of the scalable cores, such as the device reconfiguration control, the run-time management of the architecture and the implementation techniques have been also addressed in this thesis. With regard to the implementation of dynamically reconfigurable architectures, device dependent low-level details are addressed. Some of the aspects covered in this thesis are the area constrained routing for reconfigurable modules, or an inter-module communication strategy which does not introduce either extra delay or logic overhead. The system implementation, from the hardware description to the device configuration bitstream, has been fully automated by modifying the netlists corresponding to each of the system modules, which are previously generated using the vendor tools. This modification is therefore envisaged as a post-processing step. Based on these implementation proposals, a design tool called DREAMS (Dynamically Reconfigurable Embedded and Modular Systems) has been created, including a graphic user interface. The tool has specific features to cope with modular and regular architectures, including the support for module relocation and the inter-module communications scheme based on the symmetry of the architecture. The core of the tool is a custom router, which has been also exploited in this thesis to obtain symmetric routed nets, with the aim of enhancing the protection of critical reconfigurable circuits against side channel attacks. This is achieved by duplicating the logic with an exactly equal routing. In order to control the reconfiguration process of the FPGA, a Reconfiguration Engine suited to the specific requirements set by the proposed architectures was also proposed. Therefore, in addition to controlling the reconfiguration port, the Reconfiguration Engine has been enhanced with the online relocation ability, which allows employing a unique configuration bitstream for all the positions where the module may be placed in the device. Differently to the existing relocating solutions, which are based on bitstream parsers, the proposed approach is based on the online composition of bitstreams. This strategy allows increasing the speed of the process, while the length of partial bitstreams is also reduced. The height of the reconfigurable modules can be lower than the height of a clock region. The Reconfiguration Engine manages the merging process of the new and the existing configuration frames within each clock region. The process of scaling up and down the hardware cores also benefits from this technique. A direct link to an external memory where partial bitstreams can be stored has been also implemented. In order to accelerate the reconfiguration process, the ICAP has been overclocked over the speed reported by the manufacturer. In the case of Virtex-5, even though the maximum frequency of the ICAP is reported to be 100 MHz, valid operations at 250 MHz have been achieved, including the online relocation process. Portability of the reconfiguration solution to today's and probably, future FPGAs, has been also considered. The reconfiguration engine can be also used to inject faults in real hardware devices, and this way being able to evaluate the fault tolerance offered by the reconfigurable architectures. Faults are emulated by introducing partial bitstreams intentionally modified to provide erroneous functionality. To prove the validity and the benefits offered by the proposed architectures, two demonstration application lines have been envisaged. First, scalable architectures have been employed to develop an evolvable hardware platform with adaptability, fault tolerance and scalability properties. Second, they have been used to implement a scalable deblocking filter suited to scalable video coding. Evolvable Hardware is the use of evolutionary algorithms to design hardware in an autonomous way, exploiting the flexibility offered by reconfigurable devices. In this case, processing elements composing the architecture are selected from a presynthesized library of processing elements, according to the decisions taken by the algorithm, instead of being decided at design time. This way, the configuration of the array may change as run-time environmental conditions do, achieving autonomous control of the dynamic reconfiguration process. Thus, the self-optimization property is added to the native self-configurability of the dynamically scalable architectures. In addition, evolvable hardware adaptability inherently offers self-healing features. The proposal has proved to be self-tolerant, since it is able to self-recover from both transient and cumulative permanent faults. The proposed evolvable architecture has been used to implement noise removal image filters. Scalability has been also exploited in this application. Scalable evolvable hardware architectures allow the autonomous adaptation of the processing cores to a fluctuating amount of resources available in the system. Thus, it constitutes an example of the dynamic quality scalability tackled in this thesis. Two variants have been proposed. The first one consists in a single dynamically scalable evolvable core, and the second one contains a variable number of processing cores. Scalable video is a flexible approach for video compression, which offers scalability at different levels. Differently to non-scalable codecs, a scalable video bitstream can be decoded with different levels of quality, spatial or temporal resolutions, by discarding the undesired information. The interest in this technology has been fostered by the development of the Scalable Video Coding (SVC) standard, as an extension of H.264/AVC. In order to exploit all the flexibility offered by the standard, it is necessary to adapt the characteristics of the decoder to the requirements of each client during run-time. The use of dynamically scalable architectures is proposed in this thesis with this aim. The deblocking filter algorithm is the responsible of improving the visual perception of a reconstructed image, by smoothing blocking artifacts generated in the encoding loop. This is one of the most computationally intensive tasks of the standard, and furthermore, it is highly dependent on the selected scalability level in the decoder. Therefore, the deblocking filter has been selected as a proof of concept of the implementation of dynamically scalable architectures for video compression. The proposed architecture allows the run-time addition or removal of computational units working in parallel to change its level of parallelism, following a wavefront computational pattern. Scalable architecture is offered together with a scalable parallelization strategy at the macroblock level, such that when the size of the architecture changes, the macroblock filtering order is modified accordingly. The proposed pattern is based on the division of the macroblock processing into two independent stages, corresponding to the horizontal and vertical filtering of the blocks within the macroblock. The main contributions of this thesis are: - The use of highly parallel, modular, regular and local architectures to implement dynamically reconfigurable processing IP cores, for data intensive applications with flexibility requirements. - The use of two-dimensional mesh-type arrays as architectural templates to build dynamically reconfigurable IP cores, with a scalable footprint. The proposal consists in generic architectural templates, which can be tuned to solve different computational problems. •A design flow and a tool targeting the design of DPR systems, focused on highly parallel, modular and local architectures. - An inter-module communication strategy, which does not introduce delay or area overhead, named Virtual Borders. - A custom and flexible router to solve the routing conflicts as well as the inter-module communication problems, appearing during the design of DPR systems. - An algorithm addressing the optimization of systems composed of multiple scalable cores, which size can be decided individually, to optimize the system parameters. It is based on a model known as the multi-dimensional multi-choice Knapsack problem. - A reconfiguration engine tailored to the requirements of highly regular and modular architectures. It combines a high reconfiguration throughput with run-time module relocation capabilities, including the support for sub-clock reconfigurable regions and the replication in multiple positions. - A fault injection mechanism which takes advantage of the system reconfiguration engine, as well as the modularity of the proposed reconfigurable architectures, to evaluate the effects of transient and permanent faults in these architectures. - The demonstration of the possibilities of the architectures proposed in this thesis to implement evolvable hardware systems, while keeping a high processing throughput. - The implementation of scalable evolvable hardware systems, which are able to adapt to the fluctuation of the amount of resources available in the system, in an autonomous way. - A parallelization strategy for the H.264/AVC and SVC deblocking filter, which reduces the number of macroblock cycles needed to process the whole frame. - A dynamically scalable architecture that permits the implementation of a novel deblocking filter module, fully compliant with the H.264/AVC and SVC standards, which exploits the macroblock level parallelism of the algorithm. This document is organized in seven chapters. In the first one, an introduction to the technology framework of this thesis, specially focused on dynamic and partial reconfiguration, is provided. The need for the dynamically scalable processing architectures proposed in this work is also motivated in this chapter. In chapter 2, dynamically scalable architectures are described. Description includes most of the architectural contributions of this work. The design flow tailored to the scalable architectures, together with the DREAMs tool provided to implement them, are described in chapter 3. The reconfiguration engine is described in chapter 4. The use of the proposed scalable archtieectures to implement evolvable hardware systems is described in chapter 5, while the scalable deblocking filter is described in chapter 6. Final conclusions of this thesis, and the description of future work, are addressed in chapter 7.

A Multi Ant Colony Optimization algorithm for a Mixed Car Assembly Line

This paper presents an ant colony optimization algorithm to sequence the mixed assembly lines considering the inventory and the replenishment of components. This is a NP-problem that cannot be solved to optimality by exact methods when the size of the problem growth. Groups of specialized ants are implemented to solve the different parts of the problem. This is intended to differentiate each part of the problem. Different types of pheromone structures are created to identify good car sequences, and good routes for the replenishment of components vehicle. The contribution of this paper is the collaborative approach of the ACO for the mixed assembly line and the replenishment of components and the jointly solution of the problem.

Diseño de nuevas técnicas evolutivas para videojuegos de lucha

El objetivo de esta tesis fin de máster es la construcción mediante técnicas evolutivas de bases de conocimiento con reglas difusas para desarrollar un sistema autónomo que sea capaz de jugar con destreza a un videojuego de lucha en 2D. El uso de la lógica difusa permite manejar imprecisión, la cual está implícita en las variables de entrada al sistema y favorece la comprensión a nivel humano del comportamiento general del controlador. Se ha diseñado, para obtener la base de conocimiento que permita al sistema tomar las decisiones adecuadas durante el combate, un nuevo operador para algoritmos evolutivos. Se ha observado que la programación genética guiada por gramáticas (PGGG) muestra un sesgo debido al cruce que se suele emplear para obtener nuevos individuos en el proceso evolutivo. Para solventar este problema, se propone el método de sedimentación, capaz de evitar la tendencia que tiene la PGGG a generar bases de conocimiento con pocas reglas, de forma independiente a la gramática. Este método se inspira en la sedimentación que se produce en el fondo de los lechos marinos y permite obtener un sustrato de reglas óptimas que forman la solución final una vez que converge el algoritmo.---ABSTRACT---The objective of this thesis is the construction by evolutionary techniques of fuzzy rule-base system to develop an autonomous controller capable of playing a 2D fighting game. The use of fuzzy logic handles imprecision, which is implicit in the input variables of the system and makes the behavior of the controller easier to understand by humans. A new operator for evolutionary algorithms is designed to obtain the knowledge base that allows the system to take appropriate decision during combat. It has been observed that the grammar guided genetic programming (GGGP) shows a bias due to the crossing that is often used for obtaining new individuals in the evolutionary process. To solve this problem, the sedimentation method, able to avoid the tendency of the PGGG to generate knowledge bases with few rules, independently of the grammar is proposed. This method is inspired by the sedimentation that occurs on the bottom of the seabed and creates an optimal rules substrate that ends on the final solution once the algorithm converges.

Parametric and structural self-adaptation of embedded systems using evolvable hardware

Los sistemas empotrados han sido concebidos tradicionalmente como sistemas de procesamiento específicos que realizan una tarea fija durante toda su vida útil. Para cumplir con requisitos estrictos de coste, tamaño y peso, el equipo de diseño debe optimizar su funcionamiento para condiciones muy específicas. Sin embargo, la demanda de mayor versatilidad, un funcionamiento más inteligente y, en definitiva, una mayor capacidad de procesamiento comenzaron a chocar con estas limitaciones, agravado por la incertidumbre asociada a entornos de operación cada vez más dinámicos donde comenzaban a ser desplegados progresivamente. Esto trajo como resultado una necesidad creciente de que los sistemas pudieran responder por si solos a eventos inesperados en tiempo diseño tales como: cambios en las características de los datos de entrada y el entorno del sistema en general; cambios en la propia plataforma de cómputo, por ejemplo debido a fallos o defectos de fabricación; y cambios en las propias especificaciones funcionales causados por unos objetivos del sistema dinámicos y cambiantes. Como consecuencia, la complejidad del sistema aumenta, pero a cambio se habilita progresivamente una capacidad de adaptación autónoma sin intervención humana a lo largo de la vida útil, permitiendo que tomen sus propias decisiones en tiempo de ejecución. Éstos sistemas se conocen, en general, como sistemas auto-adaptativos y tienen, entre otras características, las de auto-configuración, auto-optimización y auto-reparación. Típicamente, la parte soft de un sistema es mayoritariamente la única utilizada para proporcionar algunas capacidades de adaptación a un sistema. Sin embargo, la proporción rendimiento/potencia en dispositivos software como microprocesadores en muchas ocasiones no es adecuada para sistemas empotrados. En este escenario, el aumento resultante en la complejidad de las aplicaciones está siendo abordado parcialmente mediante un aumento en la complejidad de los dispositivos en forma de multi/many-cores; pero desafortunadamente, esto hace que el consumo de potencia también aumente. Además, la mejora en metodologías de diseño no ha sido acorde como para poder utilizar toda la capacidad de cómputo disponible proporcionada por los núcleos. Por todo ello, no se están satisfaciendo adecuadamente las demandas de cómputo que imponen las nuevas aplicaciones. La solución tradicional para mejorar la proporción rendimiento/potencia ha sido el cambio a unas especificaciones hardware, principalmente usando ASICs. Sin embargo, los costes de un ASIC son altamente prohibitivos excepto en algunos casos de producción en masa y además la naturaleza estática de su estructura complica la solución a las necesidades de adaptación. Los avances en tecnologías de fabricación han hecho que la FPGA, una vez lenta y pequeña, usada como glue logic en sistemas mayores, haya crecido hasta convertirse en un dispositivo de cómputo reconfigurable de gran potencia, con una cantidad enorme de recursos lógicos computacionales y cores hardware empotrados de procesamiento de señal y de propósito general. Sus capacidades de reconfiguración han permitido combinar la flexibilidad propia del software con el rendimiento del procesamiento en hardware, lo que tiene la potencialidad de provocar un cambio de paradigma en arquitectura de computadores, pues el hardware no puede ya ser considerado más como estático. El motivo es que como en el caso de las FPGAs basadas en tecnología SRAM, la reconfiguración parcial dinámica (DPR, Dynamic Partial Reconfiguration) es posible. Esto significa que se puede modificar (reconfigurar) un subconjunto de los recursos computacionales en tiempo de ejecución mientras el resto permanecen activos. Además, este proceso de reconfiguración puede ser ejecutado internamente por el propio dispositivo. El avance tecnológico en dispositivos hardware reconfigurables se encuentra recogido bajo el campo conocido como Computación Reconfigurable (RC, Reconfigurable Computing). Uno de los campos de aplicación más exóticos y menos convencionales que ha posibilitado la computación reconfigurable es el conocido como Hardware Evolutivo (EHW, Evolvable Hardware), en el cual se encuentra enmarcada esta tesis. La idea principal del concepto consiste en convertir hardware que es adaptable a través de reconfiguración en una entidad evolutiva sujeta a las fuerzas de un proceso evolutivo inspirado en el de las especies biológicas naturales, que guía la dirección del cambio. Es una aplicación más del campo de la Computación Evolutiva (EC, Evolutionary Computation), que comprende una serie de algoritmos de optimización global conocidos como Algoritmos Evolutivos (EA, Evolutionary Algorithms), y que son considerados como algoritmos universales de resolución de problemas. En analogía al proceso biológico de la evolución, en el hardware evolutivo el sujeto de la evolución es una población de circuitos que intenta adaptarse a su entorno mediante una adecuación progresiva generación tras generación. Los individuos pasan a ser configuraciones de circuitos en forma de bitstreams caracterizados por descripciones de circuitos reconfigurables. Seleccionando aquellos que se comportan mejor, es decir, que tienen una mejor adecuación (o fitness) después de ser evaluados, y usándolos como padres de la siguiente generación, el algoritmo evolutivo crea una nueva población hija usando operadores genéticos como la mutación y la recombinación. Según se van sucediendo generaciones, se espera que la población en conjunto se aproxime a la solución óptima al problema de encontrar una configuración del circuito adecuada que satisfaga las especificaciones. El estado de la tecnología de reconfiguración después de que la familia de FPGAs XC6200 de Xilinx fuera retirada y reemplazada por las familias Virtex a finales de los 90, supuso un gran obstáculo para el avance en hardware evolutivo; formatos de bitstream cerrados (no conocidos públicamente); dependencia de herramientas del fabricante con soporte limitado de DPR; una velocidad de reconfiguración lenta; y el hecho de que modificaciones aleatorias del bitstream pudieran resultar peligrosas para la integridad del dispositivo, son algunas de estas razones. Sin embargo, una propuesta a principios de los años 2000 permitió mantener la investigación en el campo mientras la tecnología de DPR continuaba madurando, el Circuito Virtual Reconfigurable (VRC, Virtual Reconfigurable Circuit). En esencia, un VRC en una FPGA es una capa virtual que actúa como un circuito reconfigurable de aplicación específica sobre la estructura nativa de la FPGA que reduce la complejidad del proceso reconfiguración y aumenta su velocidad (comparada con la reconfiguración nativa). Es un array de nodos computacionales especificados usando descripciones HDL estándar que define recursos reconfigurables ad-hoc: multiplexores de rutado y un conjunto de elementos de procesamiento configurables, cada uno de los cuales tiene implementadas todas las funciones requeridas, que pueden seleccionarse a través de multiplexores tal y como ocurre en una ALU de un microprocesador. Un registro grande actúa como memoria de configuración, por lo que la reconfiguración del VRC es muy rápida ya que tan sólo implica la escritura de este registro, el cual controla las señales de selección del conjunto de multiplexores. Sin embargo, esta capa virtual provoca: un incremento de área debido a la implementación simultánea de cada función en cada nodo del array más los multiplexores y un aumento del retardo debido a los multiplexores, reduciendo la frecuencia de funcionamiento máxima. La naturaleza del hardware evolutivo, capaz de optimizar su propio comportamiento computacional, le convierten en un buen candidato para avanzar en la investigación sobre sistemas auto-adaptativos. Combinar un sustrato de cómputo auto-reconfigurable capaz de ser modificado dinámicamente en tiempo de ejecución con un algoritmo empotrado que proporcione una dirección de cambio, puede ayudar a satisfacer los requisitos de adaptación autónoma de sistemas empotrados basados en FPGA. La propuesta principal de esta tesis está por tanto dirigida a contribuir a la auto-adaptación del hardware de procesamiento de sistemas empotrados basados en FPGA mediante hardware evolutivo. Esto se ha abordado considerando que el comportamiento computacional de un sistema puede ser modificado cambiando cualquiera de sus dos partes constitutivas: una estructura hard subyacente y un conjunto de parámetros soft. De esta distinción, se derivan dos lineas de trabajo. Por un lado, auto-adaptación paramétrica, y por otro auto-adaptación estructural. El objetivo perseguido en el caso de la auto-adaptación paramétrica es la implementación de técnicas de optimización evolutiva complejas en sistemas empotrados con recursos limitados para la adaptación paramétrica online de circuitos de procesamiento de señal. La aplicación seleccionada como prueba de concepto es la optimización para tipos muy específicos de imágenes de los coeficientes de los filtros de transformadas wavelet discretas (DWT, DiscreteWavelet Transform), orientada a la compresión de imágenes. Por tanto, el objetivo requerido de la evolución es una compresión adaptativa y más eficiente comparada con los procedimientos estándar. El principal reto radica en reducir la necesidad de recursos de supercomputación para el proceso de optimización propuesto en trabajos previos, de modo que se adecúe para la ejecución en sistemas empotrados. En cuanto a la auto-adaptación estructural, el objetivo de la tesis es la implementación de circuitos auto-adaptativos en sistemas evolutivos basados en FPGA mediante un uso eficiente de sus capacidades de reconfiguración nativas. En este caso, la prueba de concepto es la evolución de tareas de procesamiento de imagen tales como el filtrado de tipos desconocidos y cambiantes de ruido y la detección de bordes en la imagen. En general, el objetivo es la evolución en tiempo de ejecución de tareas de procesamiento de imagen desconocidas en tiempo de diseño (dentro de un cierto grado de complejidad). En este caso, el objetivo de la propuesta es la incorporación de DPR en EHW para evolucionar la arquitectura de un array sistólico adaptable mediante reconfiguración cuya capacidad de evolución no había sido estudiada previamente. Para conseguir los dos objetivos mencionados, esta tesis propone originalmente una plataforma evolutiva que integra un motor de adaptación (AE, Adaptation Engine), un motor de reconfiguración (RE, Reconfiguration Engine) y un motor computacional (CE, Computing Engine) adaptable. El el caso de adaptación paramétrica, la plataforma propuesta está caracterizada por: • un CE caracterizado por un núcleo de procesamiento hardware de DWT adaptable mediante registros reconfigurables que contienen los coeficientes de los filtros wavelet • un algoritmo evolutivo como AE que busca filtros wavelet candidatos a través de un proceso de optimización paramétrica desarrollado específicamente para sistemas caracterizados por recursos de procesamiento limitados • un nuevo operador de mutación simplificado para el algoritmo evolutivo utilizado, que junto con un mecanismo de evaluación rápida de filtros wavelet candidatos derivado de la literatura actual, asegura la viabilidad de la búsqueda evolutiva asociada a la adaptación de wavelets. En el caso de adaptación estructural, la plataforma propuesta toma la forma de: • un CE basado en una plantilla de array sistólico reconfigurable de 2 dimensiones compuesto de nodos de procesamiento reconfigurables • un algoritmo evolutivo como AE que busca configuraciones candidatas del array usando un conjunto de funcionalidades de procesamiento para los nodos disponible en una biblioteca accesible en tiempo de ejecución • un RE hardware que explota la capacidad de reconfiguración nativa de las FPGAs haciendo un uso eficiente de los recursos reconfigurables del dispositivo para cambiar el comportamiento del CE en tiempo de ejecución • una biblioteca de elementos de procesamiento reconfigurables caracterizada por bitstreams parciales independientes de la posición, usados como el conjunto de configuraciones disponibles para los nodos de procesamiento del array Las contribuciones principales de esta tesis se pueden resumir en la siguiente lista: • Una plataforma evolutiva basada en FPGA para la auto-adaptación paramétrica y estructural de sistemas empotrados compuesta por un motor computacional (CE), un motor de adaptación (AE) evolutivo y un motor de reconfiguración (RE). Esta plataforma se ha desarrollado y particularizado para los casos de auto-adaptación paramétrica y estructural. • En cuanto a la auto-adaptación paramétrica, las contribuciones principales son: – Un motor computacional adaptable mediante registros que permite la adaptación paramétrica de los coeficientes de una implementación hardware adaptativa de un núcleo de DWT. – Un motor de adaptación basado en un algoritmo evolutivo desarrollado específicamente para optimización numérica, aplicada a los coeficientes de filtros wavelet en sistemas empotrados con recursos limitados. – Un núcleo IP de DWT auto-adaptativo en tiempo de ejecución para sistemas empotrados que permite la optimización online del rendimiento de la transformada para compresión de imágenes en entornos específicos de despliegue, caracterizados por tipos diferentes de señal de entrada. – Un modelo software y una implementación hardware de una herramienta para la construcción evolutiva automática de transformadas wavelet específicas. • Por último, en cuanto a la auto-adaptación estructural, las contribuciones principales son: – Un motor computacional adaptable mediante reconfiguración nativa de FPGAs caracterizado por una plantilla de array sistólico en dos dimensiones de nodos de procesamiento reconfigurables. Es posible mapear diferentes tareas de cómputo en el array usando una biblioteca de elementos sencillos de procesamiento reconfigurables. – Definición de una biblioteca de elementos de procesamiento apropiada para la síntesis autónoma en tiempo de ejecución de diferentes tareas de procesamiento de imagen. – Incorporación eficiente de la reconfiguración parcial dinámica (DPR) en sistemas de hardware evolutivo, superando los principales inconvenientes de propuestas previas como los circuitos reconfigurables virtuales (VRCs). En este trabajo también se comparan originalmente los detalles de implementación de ambas propuestas. – Una plataforma tolerante a fallos, auto-curativa, que permite la recuperación funcional online en entornos peligrosos. La plataforma ha sido caracterizada desde una perspectiva de tolerancia a fallos: se proponen modelos de fallo a nivel de CLB y de elemento de procesamiento, y usando el motor de reconfiguración, se hace un análisis sistemático de fallos para un fallo en cada elemento de procesamiento y para dos fallos acumulados. – Una plataforma con calidad de filtrado dinámica que permite la adaptación online a tipos de ruido diferentes y diferentes comportamientos computacionales teniendo en cuenta los recursos de procesamiento disponibles. Por un lado, se evolucionan filtros con comportamientos no destructivos, que permiten esquemas de filtrado en cascada escalables; y por otro, también se evolucionan filtros escalables teniendo en cuenta requisitos computacionales de filtrado cambiantes dinámicamente. Este documento está organizado en cuatro partes y nueve capítulos. La primera parte contiene el capítulo 1, una introducción y motivación sobre este trabajo de tesis. A continuación, el marco de referencia en el que se enmarca esta tesis se analiza en la segunda parte: el capítulo 2 contiene una introducción a los conceptos de auto-adaptación y computación autonómica (autonomic computing) como un campo de investigación más general que el muy específico de este trabajo; el capítulo 3 introduce la computación evolutiva como la técnica para dirigir la adaptación; el capítulo 4 analiza las plataformas de computación reconfigurables como la tecnología para albergar hardware auto-adaptativo; y finalmente, el capítulo 5 define, clasifica y hace un sondeo del campo del hardware evolutivo. Seguidamente, la tercera parte de este trabajo contiene la propuesta, desarrollo y resultados obtenidos: mientras que el capítulo 6 contiene una declaración de los objetivos de la tesis y la descripción de la propuesta en su conjunto, los capítulos 7 y 8 abordan la auto-adaptación paramétrica y estructural, respectivamente. Finalmente, el capítulo 9 de la parte 4 concluye el trabajo y describe caminos de investigación futuros. ABSTRACT Embedded systems have traditionally been conceived to be specific-purpose computers with one, fixed computational task for their whole lifetime. Stringent requirements in terms of cost, size and weight forced designers to highly optimise their operation for very specific conditions. However, demands for versatility, more intelligent behaviour and, in summary, an increased computing capability began to clash with these limitations, intensified by the uncertainty associated to the more dynamic operating environments where they were progressively being deployed. This brought as a result an increasing need for systems to respond by themselves to unexpected events at design time, such as: changes in input data characteristics and system environment in general; changes in the computing platform itself, e.g., due to faults and fabrication defects; and changes in functional specifications caused by dynamically changing system objectives. As a consequence, systems complexity is increasing, but in turn, autonomous lifetime adaptation without human intervention is being progressively enabled, allowing them to take their own decisions at run-time. This type of systems is known, in general, as selfadaptive, and are able, among others, of self-configuration, self-optimisation and self-repair. Traditionally, the soft part of a system has mostly been so far the only place to provide systems with some degree of adaptation capabilities. However, the performance to power ratios of software driven devices like microprocessors are not adequate for embedded systems in many situations. In this scenario, the resulting rise in applications complexity is being partly addressed by rising devices complexity in the form of multi and many core devices; but sadly, this keeps on increasing power consumption. Besides, design methodologies have not been improved accordingly to completely leverage the available computational power from all these cores. Altogether, these factors make that the computing demands new applications pose are not being wholly satisfied. The traditional solution to improve performance to power ratios has been the switch to hardware driven specifications, mainly using ASICs. However, their costs are highly prohibitive except for some mass production cases and besidesthe static nature of its structure complicates the solution to the adaptation needs. The advancements in fabrication technologies have made that the once slow, small FPGA used as glue logic in bigger systems, had grown to be a very powerful, reconfigurable computing device with a vast amount of computational logic resources and embedded, hardened signal and general purpose processing cores. Its reconfiguration capabilities have enabled software-like flexibility to be combined with hardware-like computing performance, which has the potential to cause a paradigm shift in computer architecture since hardware cannot be considered as static anymore. This is so, since, as is the case with SRAMbased FPGAs, Dynamic Partial Reconfiguration (DPR) is possible. This means that subsets of the FPGA computational resources can now be changed (reconfigured) at run-time while the rest remains active. Besides, this reconfiguration process can be triggered internally by the device itself. This technological boost in reconfigurable hardware devices is actually covered under the field known as Reconfigurable Computing. One of the most exotic fields of application that Reconfigurable Computing has enabled is the known as Evolvable Hardware (EHW), in which this dissertation is framed. The main idea behind the concept is turning hardware that is adaptable through reconfiguration into an evolvable entity subject to the forces of an evolutionary process, inspired by that of natural, biological species, that guides the direction of change. It is yet another application of the field of Evolutionary Computation (EC), which comprises a set of global optimisation algorithms known as Evolutionary Algorithms (EAs), considered as universal problem solvers. In analogy to the biological process of evolution, in EHW the subject of evolution is a population of circuits that tries to get adapted to its surrounding environment by progressively getting better fitted to it generation after generation. Individuals become circuit configurations representing bitstreams that feature reconfigurable circuit descriptions. By selecting those that behave better, i.e., with a higher fitness value after being evaluated, and using them as parents of the following generation, the EA creates a new offspring population by using so called genetic operators like mutation and recombination. As generations succeed one another, the whole population is expected to approach to the optimum solution to the problem of finding an adequate circuit configuration that fulfils system objectives. The state of reconfiguration technology after Xilinx XC6200 FPGA family was discontinued and replaced by Virtex families in the late 90s, was a major obstacle for advancements in EHW; closed (non publicly known) bitstream formats; dependence on manufacturer tools with highly limiting support of DPR; slow speed of reconfiguration; and random bitstream modifications being potentially hazardous for device integrity, are some of these reasons. However, a proposal in the first 2000s allowed to keep investigating in this field while DPR technology kept maturing, the Virtual Reconfigurable Circuit (VRC). In essence, a VRC in an FPGA is a virtual layer acting as an application specific reconfigurable circuit on top of an FPGA fabric that reduces the complexity of the reconfiguration process and increases its speed (compared to native reconfiguration). It is an array of computational nodes specified using standard HDL descriptions that define ad-hoc reconfigurable resources; routing multiplexers and a set of configurable processing elements, each one containing all the required functions, which are selectable through functionality multiplexers as in microprocessor ALUs. A large register acts as configuration memory, so VRC reconfiguration is very fast given it only involves writing this register, which drives the selection signals of the set of multiplexers. However, large overheads are introduced by this virtual layer; an area overhead due to the simultaneous implementation of every function in every node of the array plus the multiplexers, and a delay overhead due to the multiplexers, which also reduces maximum frequency of operation. The very nature of Evolvable Hardware, able to optimise its own computational behaviour, makes it a good candidate to advance research in self-adaptive systems. Combining a selfreconfigurable computing substrate able to be dynamically changed at run-time with an embedded algorithm that provides a direction for change, can help fulfilling requirements for autonomous lifetime adaptation of FPGA-based embedded systems. The main proposal of this thesis is hence directed to contribute to autonomous self-adaptation of the underlying computational hardware of FPGA-based embedded systems by means of Evolvable Hardware. This is tackled by considering that the computational behaviour of a system can be modified by changing any of its two constituent parts: an underlying hard structure and a set of soft parameters. Two main lines of work derive from this distinction. On one side, parametric self-adaptation and, on the other side, structural self-adaptation. The goal pursued in the case of parametric self-adaptation is the implementation of complex evolutionary optimisation techniques in resource constrained embedded systems for online parameter adaptation of signal processing circuits. The application selected as proof of concept is the optimisation of Discrete Wavelet Transforms (DWT) filters coefficients for very specific types of images, oriented to image compression. Hence, adaptive and improved compression efficiency, as compared to standard techniques, is the required goal of evolution. The main quest lies in reducing the supercomputing resources reported in previous works for the optimisation process in order to make it suitable for embedded systems. Regarding structural self-adaptation, the thesis goal is the implementation of self-adaptive circuits in FPGA-based evolvable systems through an efficient use of native reconfiguration capabilities. In this case, evolution of image processing tasks such as filtering of unknown and changing types of noise and edge detection are the selected proofs of concept. In general, evolving unknown image processing behaviours (within a certain complexity range) at design time is the required goal. In this case, the mission of the proposal is the incorporation of DPR in EHW to evolve a systolic array architecture adaptable through reconfiguration whose evolvability had not been previously checked. In order to achieve the two stated goals, this thesis originally proposes an evolvable platform that integrates an Adaptation Engine (AE), a Reconfiguration Engine (RE) and an adaptable Computing Engine (CE). In the case of parametric adaptation, the proposed platform is characterised by: • a CE featuring a DWT hardware processing core adaptable through reconfigurable registers that holds wavelet filters coefficients • an evolutionary algorithm as AE that searches for candidate wavelet filters through a parametric optimisation process specifically developed for systems featured by scarce computing resources • a new, simplified mutation operator for the selected EA, that together with a fast evaluation mechanism of candidate wavelet filters derived from existing literature, assures the feasibility of the evolutionary search involved in wavelets adaptation In the case of structural adaptation, the platform proposal takes the form of: • a CE based on a reconfigurable 2D systolic array template composed of reconfigurable processing nodes • an evolutionary algorithm as AE that searches for candidate configurations of the array using a set of computational functionalities for the nodes available in a run time accessible library • a hardware RE that exploits native DPR capabilities of FPGAs and makes an efficient use of the available reconfigurable resources of the device to change the behaviour of the CE at run time • a library of reconfigurable processing elements featured by position-independent partial bitstreams used as the set of available configurations for the processing nodes of the array Main contributions of this thesis can be summarised in the following list. • An FPGA-based evolvable platform for parametric and structural self-adaptation of embedded systems composed of a Computing Engine, an evolutionary Adaptation Engine and a Reconfiguration Engine. This platform is further developed and tailored for both parametric and structural self-adaptation. • Regarding parametric self-adaptation, main contributions are: – A CE adaptable through reconfigurable registers that enables parametric adaptation of the coefficients of an adaptive hardware implementation of a DWT core. – An AE based on an Evolutionary Algorithm specifically developed for numerical optimisation applied to wavelet filter coefficients in resource constrained embedded systems. – A run-time self-adaptive DWT IP core for embedded systems that allows for online optimisation of transform performance for image compression for specific deployment environments characterised by different types of input signals. – A software model and hardware implementation of a tool for the automatic, evolutionary construction of custom wavelet transforms. • Lastly, regarding structural self-adaptation, main contributions are: – A CE adaptable through native FPGA fabric reconfiguration featured by a two dimensional systolic array template of reconfigurable processing nodes. Different processing behaviours can be automatically mapped in the array by using a library of simple reconfigurable processing elements. – Definition of a library of such processing elements suited for autonomous runtime synthesis of different image processing tasks. – Efficient incorporation of DPR in EHW systems, overcoming main drawbacks from the previous approach of virtual reconfigurable circuits. Implementation details for both approaches are also originally compared in this work. – A fault tolerant, self-healing platform that enables online functional recovery in hazardous environments. The platform has been characterised from a fault tolerance perspective: fault models at FPGA CLB level and processing elements level are proposed, and using the RE, a systematic fault analysis for one fault in every processing element and for two accumulated faults is done. – A dynamic filtering quality platform that permits on-line adaptation to different types of noise and different computing behaviours considering the available computing resources. On one side, non-destructive filters are evolved, enabling scalable cascaded filtering schemes; and on the other, size-scalable filters are also evolved considering dynamically changing computational filtering requirements. This dissertation is organized in four parts and nine chapters. First part contains chapter 1, the introduction to and motivation of this PhD work. Following, the reference framework in which this dissertation is framed is analysed in the second part: chapter 2 features an introduction to the notions of self-adaptation and autonomic computing as a more general research field to the very specific one of this work; chapter 3 introduces evolutionary computation as the technique to drive adaptation; chapter 4 analyses platforms for reconfigurable computing as the technology to hold self-adaptive hardware; and finally chapter 5 defines, classifies and surveys the field of Evolvable Hardware. Third part of the work follows, which contains the proposal, development and results obtained: while chapter 6 contains an statement of the thesis goals and the description of the proposal as a whole, chapters 7 and 8 address parametric and structural self-adaptation, respectively. Finally, chapter 9 in part 4 concludes the work and describes future research paths.

Sistemas de gestión de puentes : optimización de estrategias de mantenimiento : implementación en redes locales de carreteras

En la actualidad, y en consonancia con la tendencia de “sostenibilidad” extendida a todos los campos y parcelas de la ciencia, nos encontramos con un área de estudio basado en la problemática del inevitable deterioro de las estructuras existentes, y la gestión de las acciones a realizar para mantener las condiciones de servicio de los puentes y prolongar su vida útil. Tal y como se comienza a ver en las inversiones en los países avanzados, con una larga tradición en el desarrollo de sus infraestructuras, se muestra claramente el nuevo marco al que nos dirigimos. Las nuevas tendencias van encaminadas cada vez más a la conservación y mantenimiento, reduciéndose las partidas presupuestarias destinadas a nuevas actuaciones, debido a la completa vertebración territorial que se ha ido instaurando en estos países, entre los que España se encuentra. Este nutrido patrimonio de infraestructuras viarias, que cuentan a su vez con un importante número de estructuras, hacen necesarias las labores de gestión y mantenimiento de los puentes integrantes en las mismas. Bajo estas premisas, la tesis aborda el estado de desarrollo de la implementación de los sistemas de gestión de puentes, las tendencias actuales e identificación de campos por desarrollar, así como la aplicación específica a redes de carreteras de escasos recursos, más allá de la Red Estatal. Además de analizar las diversas metodologías de formación de inventarios, realización de inspecciones y evaluación del estado de puentes, se ha enfocado, como principal objetivo, el desarrollo de un sistema específico de predicción del deterioro y ayuda a la toma de decisiones. Este sistema, adicionalmente a la configuración tradicional de criterios de formación de bases de datos de estructuras e inspecciones, plantea, de forma justificada, la clasificación relativa al conjunto de la red gestionada, según su estado de condición. Eso permite, mediante técnicas de optimización, la correcta toma de decisiones a los técnicos encargados de la gestión de la red. Dentro de los diversos métodos de evaluación de la predicción de evolución del deterioro de cada puente, se plantea la utilización de un método bilineal simplificado envolvente del ajuste empírico realizado y de los modelos markovianos como la solución más efectiva para abordar el análisis de la predicción de la propagación del daño. Todo ello explotando la campaña experimenta realizada que, a partir de una serie de “fotografías técnicas” del estado de la red de puentes gestionados obtenidas mediante las inspecciones realizadas, es capaz de mejorar el proceso habitual de toma de decisiones. Toda la base teórica reflejada en el documento, se ve complementada mediante la implementación de un Sistema de Gestión de Puentes (SGP) específico, adaptado según las necesidades y limitaciones de la administración a la que se ha aplicado, en concreto, la Dirección General de Carreteras de la Junta de Comunidades de Castilla-La Mancha, para una muestra representativa del conjunto de puentes de la red de la provincia de Albacete, partiendo de una situación en la que no existe, actualmente, un sistema formal de gestión de puentes. Tras un meditado análisis del estado del arte dentro de los Capítulos 2 y 3, se plantea un modelo de predicción del deterioro dentro del Capítulo 4 “Modelo de Predicción del Deterioro”. De la misma manera, para la resolución del problema de optimización, se justifica la utilización de un novedoso sistema de optimización secuencial elegido dentro del Capítulo 5, los “Algoritmos Evolutivos”, en sus diferentes variantes, como la herramienta matemática más correcta para distribuir adecuadamente los recursos económicos dedicados a mantenimiento y conservación de los que esta administración pueda disponer en sus partidas de presupuesto a medio plazo. En el Capítulo 6, y en diversos Anexos al presente documento, se muestran los datos y resultados obtenidos de la aplicación específica desarrollada para la red local analizada, utilizando el modelo de deterioro y optimización secuencial, que garantiza la correcta asignación de los escasos recursos de los que disponen las redes autonómicas en España. Se plantea con especial interés la implantación de estos sistemas en la red secundaria española, debido a que reciben en los últimos tiempos una mayor responsabilidad de gestión, con recursos cada vez más limitados. Finalmente, en el Capítulo 7, se plantean una serie de conclusiones que nos hacen reflexionar de la necesidad de comenzar a pasar, en materia de gestión de infraestructuras, de los estudios teóricos y los congresos, hacia la aplicación y la práctica, con un planteamiento que nos debe llevar a cambios importantes en la forma de concebir la labor del ingeniero y las enseñanzas que se imparten en las escuelas. También se enumeran las aportaciones originales que plantea el documento frente al actual estado del arte. Se plantean, de la misma manera, las líneas de investigación en materia de Sistemas de Gestión de Puentes que pueden ayudar a refinar y mejorar los actuales sistemas utilizados. In line with the development of "sustainability" extended to all fields of science, we are faced with the inevitable and ongoing deterioration of existing structures, leading nowadays to the necessary management of maintaining the service conditions and life time extension of bridges. As per the increased amounts of money that can be observed being spent in the countries with an extensive and strong tradition in the development of their infrastructure, the trend can be clearly recognized. The new tendencies turn more and more towards conservation and maintenance, reducing programmed expenses for new construction activities, in line with the already wellestablished territorial structures, as is the case for Spain. This significant heritage of established road infrastructure, consequently containing a vast number of structures, imminently lead to necessary management and maintenance of the including bridges. Under these conditions, this thesis focusses on the status of the development of the management implementation for bridges, current trends, and identifying areas for further development. This also includes the specific application to road networks with limited resources, beyond the national highways. In addition to analyzing the various training methodologies, inventory inspections and condition assessments of bridges, the main objective has been the development of a specific methodology. This methodology, in addition to the traditional system of structure and inspection database training criteria, sustains the classification for the entire road network, according to their condition. This allows, through optimization techniques, for the correct decision making by the technical managers of the network. Among the various methods for assessing the evolution forecast of deterioration of each bridge, a simplified bilinear envelope adjustment made empirical method and Markov models as the most effective solution to address the analysis of predicting the spread of damage, arising from a "technical snapshot" obtained through inspections of the condition of the bridges included in the investigated network. All theoretical basis reflected in the document, is completed by implementing a specific Bridges Management System (BMS), adapted according to the needs and limitations of the authorities for which it has been applied, being in this case particularly the General Highways Directorate of the autonomous region of Castilla-La Mancha, for a representative sample of all bridges in the network in the province of Albacete, starting from a situation where there is currently no formal bridge management system. After an analysis of the state of the art in Chapters 2 and 3, a new deterioration prediction model is developed in Chapter 4, "Deterioration Prediction Model". In the same way, to solve the optimization problem is proposed the use of a singular system of sequential optimization elected under Chapter 5, the "Evolutionary Algorithms", the most suitable mathematical tool to adequately distribute the economic resources for maintenance and conservation for mid-term budget planning. In Chapter 6, and in the various appendices, data and results are presented of the developed application for the analyzed local network, from the optimization model, which guarantees the correct allocation of scarce resources at the disposal of authorities responsible for the regional networks in Spain. The implementation of these systems is witnessed with particular interest for the Spanish secondary network, because of the increasing management responsibility, with decreasing resources. Chapter 7 presents a series of conclusions that triggers to reconsider shifting from theoretical studies and conferences towards a practical implementation, considering how to properly conceive the engineering input and the related education. The original contributions of the document are also listed. In the same way, the research on the Bridges Management System can help evaluating and improving the used systematics.

Brain-Computer Interfaces: Desarrollo de un sistema de identificación de estados mentales alfa

En el mundo actual las aplicaciones basadas en sistemas biométricos, es decir, aquellas que miden las señales eléctricas de nuestro organismo, están creciendo a un gran ritmo. Todos estos sistemas incorporan sensores biomédicos, que ayudan a los usuarios a controlar mejor diferentes aspectos de la rutina diaria, como podría ser llevar un seguimiento detallado de una rutina deportiva, o de la calidad de los alimentos que ingerimos. Entre estos sistemas biométricos, los que se basan en la interpretación de las señales cerebrales, mediante ensayos de electroencefalografía o EEG están cogiendo cada vez más fuerza para el futuro, aunque están todavía en una situación bastante incipiente, debido a la elevada complejidad del cerebro humano, muy desconocido para los científicos hasta el siglo XXI. Por estas razones, los dispositivos que utilizan la interfaz cerebro-máquina, también conocida como BCI (Brain Computer Interface), están cogiendo cada vez más popularidad. El funcionamiento de un sistema BCI consiste en la captación de las ondas cerebrales de un sujeto para después procesarlas e intentar obtener una representación de una acción o de un pensamiento del individuo. Estos pensamientos, correctamente interpretados, son posteriormente usados para llevar a cabo una acción. Ejemplos de aplicación de sistemas BCI podrían ser mover el motor de una silla de ruedas eléctrica cuando el sujeto realice, por ejemplo, la acción de cerrar un puño, o abrir la cerradura de tu propia casa usando un patrón cerebral propio. Los sistemas de procesamiento de datos están evolucionando muy rápido con el paso del tiempo. Los principales motivos son la alta velocidad de procesamiento y el bajo consumo energético de las FPGAs (Field Programmable Gate Array). Además, las FPGAs cuentan con una arquitectura reconfigurable, lo que las hace más versátiles y potentes que otras unidades de procesamiento como las CPUs o las GPUs.En el CEI (Centro de Electrónica Industrial), donde se lleva a cabo este TFG, se dispone de experiencia en el diseño de sistemas reconfigurables en FPGAs. Este TFG es el segundo de una línea de proyectos en la cual se busca obtener un sistema capaz de procesar correctamente señales cerebrales, para llegar a un patrón común que nos permita actuar en consecuencia. Más concretamente, se busca detectar cuando una persona está quedándose dormida a través de la captación de unas ondas cerebrales, conocidas como ondas alfa, cuya frecuencia está acotada entre los 8 y los 13 Hz. Estas ondas, que aparecen cuando cerramos los ojos y dejamos la mente en blanco, representan un estado de relajación mental. Por tanto, este proyecto comienza como inicio de un sistema global de BCI, el cual servirá como primera toma de contacto con el procesamiento de las ondas cerebrales, para el posterior uso de hardware reconfigurable sobre el cual se implementarán los algoritmos evolutivos. Por ello se vuelve necesario desarrollar un sistema de procesamiento de datos en una FPGA. Estos datos se procesan siguiendo la metodología de procesamiento digital de señales, y en este caso se realiza un análisis de la frecuencia utilizando la transformada rápida de Fourier, o FFT. Una vez desarrollado el sistema de procesamiento de los datos, se integra con otro sistema que se encarga de captar los datos recogidos por un ADC (Analog to Digital Converter), conocido como ADS1299. Este ADC está especialmente diseñado para captar potenciales del cerebro humano. De esta forma, el sistema final capta los datos mediante el ADS1299, y los envía a la FPGA que se encarga de procesarlos. La interpretación es realizada por los usuarios que analizan posteriormente los datos procesados. Para el desarrollo del sistema de procesamiento de los datos, se dispone primariamente de dos plataformas de estudio, a partir de las cuales se captarán los datos para después realizar el procesamiento: 1. La primera consiste en una herramienta comercial desarrollada y distribuida por OpenBCI, proyecto que se dedica a la venta de hardware para la realización de EEG, así como otros ensayos. Esta herramienta está formada por un microprocesador, un módulo de memoria SD para el almacenamiento de datos, y un módulo de comunicación inalámbrica que transmite los datos por Bluetooth. Además cuenta con el mencionado ADC ADS1299. Esta plataforma ofrece una interfaz gráfica que sirve para realizar la investigación previa al diseño del sistema de procesamiento, al permitir tener una primera toma de contacto con el sistema. 2. La segunda plataforma consiste en un kit de evaluación para el ADS1299, desde la cual se pueden acceder a los diferentes puertos de control a través de los pines de comunicación del ADC. Esta plataforma se conectará con la FPGA en el sistema integrado. Para entender cómo funcionan las ondas más simples del cerebro, así como saber cuáles son los requisitos mínimos en el análisis de ondas EEG se realizaron diferentes consultas con el Dr Ceferino Maestu, neurofisiólogo del Centro de Tecnología Biomédica (CTB) de la UPM. Él se encargó de introducirnos en los distintos procedimientos en el análisis de ondas en electroencefalogramas, así como la forma en que se deben de colocar los electrodos en el cráneo. Para terminar con la investigación previa, se realiza en MATLAB un primer modelo de procesamiento de los datos. Una característica muy importante de las ondas cerebrales es la aleatoriedad de las mismas, de forma que el análisis en el dominio del tiempo se vuelve muy complejo. Por ello, el paso más importante en el procesamiento de los datos es el paso del dominio temporal al dominio de la frecuencia, mediante la aplicación de la transformada rápida de Fourier o FFT (Fast Fourier Transform), donde se pueden analizar con mayor precisión los datos recogidos. El modelo desarrollado en MATLAB se utiliza para obtener los primeros resultados del sistema de procesamiento, el cual sigue los siguientes pasos. 1. Se captan los datos desde los electrodos y se escriben en una tabla de datos. 2. Se leen los datos de la tabla. 3. Se elige el tamaño temporal de la muestra a procesar. 4. Se aplica una ventana para evitar las discontinuidades al principio y al final del bloque analizado. 5. Se completa la muestra a convertir con con zero-padding en el dominio del tiempo. 6. Se aplica la FFT al bloque analizado con ventana y zero-padding. 7. Los resultados se llevan a una gráfica para ser analizados. Llegados a este punto, se observa que la captación de ondas alfas resulta muy viable. Aunque es cierto que se presentan ciertos problemas a la hora de interpretar los datos debido a la baja resolución temporal de la plataforma de OpenBCI, este es un problema que se soluciona en el modelo desarrollado, al permitir el kit de evaluación (sistema de captación de datos) actuar sobre la velocidad de captación de los datos, es decir la frecuencia de muestreo, lo que afectará directamente a esta precisión. Una vez llevado a cabo el primer procesamiento y su posterior análisis de los resultados obtenidos, se procede a realizar un modelo en Hardware que siga los mismos pasos que el desarrollado en MATLAB, en la medida que esto sea útil y viable. Para ello se utiliza el programa XPS (Xilinx Platform Studio) contenido en la herramienta EDK (Embedded Development Kit), que nos permite diseñar un sistema embebido. Este sistema cuenta con: Un microprocesador de tipo soft-core llamado MicroBlaze, que se encarga de gestionar y controlar todo el sistema; Un bloque FFT que se encarga de realizar la transformada rápida Fourier; Cuatro bloques de memoria BRAM, donde se almacenan los datos de entrada y salida del bloque FFT y un multiplicador para aplicar la ventana a los datos de entrada al bloque FFT; Un bus PLB, que consiste en un bus de control que se encarga de comunicar el MicroBlaze con los diferentes elementos del sistema. Tras el diseño Hardware se procede al diseño Software utilizando la herramienta SDK(Software Development Kit).También en esta etapa se integra el sistema de captación de datos, el cual se controla mayoritariamente desde el MicroBlaze. Por tanto, desde este entorno se programa el MicroBlaze para gestionar el Hardware que se ha generado. A través del Software se gestiona la comunicación entre ambos sistemas, el de captación y el de procesamiento de los datos. También se realiza la carga de los datos de la ventana a aplicar en la memoria correspondiente. En las primeras etapas de desarrollo del sistema, se comienza con el testeo del bloque FFT, para poder comprobar el funcionamiento del mismo en Hardware. Para este primer ensayo, se carga en la BRAM los datos de entrada al bloque FFT y en otra BRAM los datos de la ventana aplicada. Los datos procesados saldrán a dos BRAM, una para almacenar los valores reales de la transformada y otra para los imaginarios. Tras comprobar el correcto funcionamiento del bloque FFT, se integra junto al sistema de adquisición de datos. Posteriormente se procede a realizar un ensayo de EEG real, para captar ondas alfa. Por otro lado, y para validar el uso de las FPGAs como unidades ideales de procesamiento, se realiza una medición del tiempo que tarda el bloque FFT en realizar la transformada. Este tiempo se compara con el tiempo que tarda MATLAB en realizar la misma transformada a los mismos datos. Esto significa que el sistema desarrollado en Hardware realiza la transformada rápida de Fourier 27 veces más rápido que lo que tarda MATLAB, por lo que se puede ver aquí la gran ventaja competitiva del Hardware en lo que a tiempos de ejecución se refiere. En lo que al aspecto didáctico se refiere, este TFG engloba diferentes campos. En el campo de la electrónica:  Se han mejorado los conocimientos en MATLAB, así como diferentes herramientas que ofrece como FDATool (Filter Design Analysis Tool).  Se han adquirido conocimientos de técnicas de procesado de señal, y en particular, de análisis espectral.  Se han mejorado los conocimientos en VHDL, así como su uso en el entorno ISE de Xilinx.  Se han reforzado los conocimientos en C mediante la programación del MicroBlaze para el control del sistema.  Se ha aprendido a crear sistemas embebidos usando el entorno de desarrollo de Xilinx usando la herramienta EDK (Embedded Development Kit). En el campo de la neurología, se ha aprendido a realizar ensayos EEG, así como a analizar e interpretar los resultados mostrados en el mismo. En cuanto al impacto social, los sistemas BCI afectan a muchos sectores, donde destaca el volumen de personas con discapacidades físicas, para los cuales, este sistema implica una oportunidad de aumentar su autonomía en el día a día. También otro sector importante es el sector de la investigación médica, donde los sistemas BCIs son aplicables en muchas aplicaciones como, por ejemplo, la detección y estudio de enfermedades cognitivas.

Diseño para fabricación digital: definición unívoca entre forma y fabricación en arquitectura

La presente investigación se inicia planteando el objetivo de identificar los parámetros geométricos que son exclusivos del proceso de generación de la Forma y relacionarlos con los invariantes relacionados con la Fabricación digital aplicada a la Arquitectura. Con ello se pretende recuperar la geometría como herramienta principal del proceso de Proyecto ampliando su ámbito de actuación al encontrar una relación con los procesos de fabricación digital. El primer capítulo describe los antecedentes y contexto histórico centrándose especialmente en la influencia de la capacidad de definir geometrías complejas digitalmente mediante la aplicación de algoritmos. En los primeros ejemplos la aproximación del Arquitecto a proyectos con geometrías complejas no euclídeas aún se emplea sin precisión en la comunicación de la geometría ideada para su puesta en obra. Las técnicas constructivas obligan a asumir una tolerancia de desviación entre proyecto y obra y la previsión del comportamiento de esa geometría no permite asegurar su comportamiento final. No será hasta la introducción de herramientas CAD en el proceso de ideación arquitectónica cuando el Arquitecto se capacite para generar geometrías no representables de forma analógica. Sin embargo, la imposibilidad de trasladar la geometría proyectada a la praxis constructiva impedirá la plasmación de un proceso completo, salvo en las contadas ocasiones que se recogen en este texto. “El análisis cronológico de las referencias establece como aspecto esencial para la construcción de geometrías complejas la capacidad primero para definir y comunicar de forma precisa e inequívoca la geometría y después la capacidad de analizar el desempeño prestacional de dicha propuesta geométrica”. La presente investigación se inicia planteando el objetivo de identificar los parámetros geométricos que son exclusivos del proceso de generación de la Forma y relacionarlos con los invariantes relacionados con la Fabricación digital aplicada a la Arquitectura. Con ello se pretende recuperar la geometría como herramienta principal del proceso de Proyecto ampliando su ámbito de actuación al encontrar una relación con los procesos de fabricación digital. El primer capítulo describe los antecedentes y contexto histórico centrándose especialmente en la influencia de la capacidad de definir geometrías complejas digitalmente mediante la aplicación de algoritmos. En los primeros ejemplos la aproximación del Arquitecto a proyectos con geometrías complejas no euclídeas aún se emplea sin precisión en la comunicación de la geometría ideada para su puesta en obra. Las técnicas constructivas obligan a asumir una tolerancia de desviación entre proyecto y obra y la previsión del comportamiento de esa geometría no permite asegurar su comportamiento final. No será hasta la introducción de herramientas CAD en el proceso de ideación arquitectónica cuando el Arquitecto se capacite para generar geometrías no representables de forma analógica. Sin embargo, la imposibilidad de trasladar la geometría proyectada a la praxis constructiva impedirá la plasmación de un proceso completo, salvo en las contadas ocasiones que se recogen en este texto. “El análisis cronológico de las referencias establece como aspecto esencial para la construcción de geometrías complejas la capacidad primero para definir y comunicar de forma precisa e inequívoca la geometría y después la capacidad de analizar el desempeño prestacional de dicha propuesta geométrica”. Establecida la primera conclusión, el capítulo de contexto histórico continúa enfocándose sobre la aplicación de las técnicas digitales en el Proceso de proyecto primero, y en la puesta en obra después. Los casos de estudio identifican claramente como un punto de inflexión para la generación de formas complejas mediante un software CAD el Museo Guggenheim de Bilbao en 1992. El motivo esencial para elegir este proyecto como el primer proyecto digital es el uso de la herramienta de definición digital de la geometría para su reproducción inequívoca en obra. “La revolución digital ha aportado al Arquitecto la posibilidad de abandonar las tipologías arquitectónicas basados en restricciones geométricas-constructivas. La aplicación de técnicas de fabricación digital ha permitido la capacidad de diseñar con independencia del sistema constructivo y libertad formal. En este nuevo contexto las prestaciones suponen los nuevos límites conceptuales, ya que el acceso y disposición de la información del comportamiento de las alternativas que cada geometría conlleva demanda del Arquitecto la jerarquización de los objetivos y la formulación en un conjunto coherente de parámetros”. Los proyectos que emplean herramientas digitales para la resolución de las distintas etapas del proceso proyectual se verán incrementados de forma exponencial desde 1992 hasta nuestros días. A pesar del importante auge de las técnicas de diseño asistido por ordenador el principal desafío sigue siendo la vinculación de las geometrías y materiales propuestos con las capacidades de las técnicas de manufactura y puesta en obra. El proceso de diseño para fabricación en un entorno digital es una tecnología madura en otras industrias como la aeroespacial o la automovilística, incluso la de productos de consumo y decoración, sin embargo en el sector de Construcción es un sistema inmaduro e inconexo. Las particularidades de la industria de la construcción aún no han sido abordadas en su totalidad y las propuestas de investigación realizadas en este ámbito se han centrado hasta 2015 en partes del proceso y no en el proceso total. “El principal obstáculo para la estandarización e implantación globalizada de un proceso digital desde el origen de la forma hasta la construcción es la inexistencia de un protocolo integrado que integre las limitaciones de fabricación, económicas y de puesta en obra junto a la evaluación de desempeño prestacional durante la fases iniciales de proyecto”. En el capítulo número 3 se estudian los distintos procesos de generación de la forma. Se propone una definición específica para el ámbito de la investigación de “forma” en el entendemos que se incluye la envolvente exterior y el conjunto organizativo de espacios interiores conectados. Por lo tanto no es excluyente del interior. El objetivo de este estudio es analizar y clasificar los procesos para la generación digital de formas en los distintos proyectos seleccionados como emblemáticos de cada tipología. Se concluye que la aproximación a este proceso es muy variada y compleja, con aplicación segregada y descoordinada entre los distintos agentes que han intervenir. En un proceso de generación formal analógico los parámetros que intervienen son en parte conscientes y en parte inconscientes o aprendidos. El Arquitecto sólo tiene control sobre la parte consciente de los parámetros a integrar en el diseño, de acuerdo a sus conocimientos y capacidades será capaz de manejar un número limitado de parámetros. La parte aprendida permanece en el inconsciente y dirige el proceso analógico, aportando prejuicios estéticos incorporados durante el proceso formativo y propio del entorno cultural. “El empleo de herramientas digitales basadas en la evaluación prestacional durante el proceso de selección formal permite al Arquitecto conocer “en tiempo real” el desempeño en el conjunto de prestaciones evaluadoras del conjunto de alternativas geométricas a la propuesta previamente definida por la intuición arquitectónica. El proceso definido no persigue identificar una solución óptima sino asistir al Arquitecto en el proceso de generación de la forma mediante la evaluación continua de los vectores direccionales más idóneos que el procedimiento generativo plantea”. La definición de complejidad en generación y producción de formas en relación con el proceso de diseño digital paramétrico global o integrado, es esencial para establecer un protocolo que optimice su gestión. “Se propone como definición de complejidad como factor resultante de multiplicar el número de agentes intervinientes por el número de parámetros e interacciones comunes que intervienen en el proceso de generación de la forma, dividido por la complejidad de intercambio de información digital desde el origen hasta la fase de fabricación y construcción”. Una vez analizados los procesos de generación digital de Arquitectura se propone identificar los parámetros geométricos que definen el proceso de Diseño digital, entendiendose por Diseño el proceso que engloba desde la proposición de una forma inicial basada en la intuición del Arquitecto, la generación y evaluación de variantes y posterior definición digital para producción, tanto de un objeto, un sistema o de la totalidad del Proyecto. En la actualidad el proceso de Diseño es discontinuo y lineal organizandose los parámetros por disciplinas en las que está estructurada las atribuciones profesionales en la industria de la construcción. Para simplificar la identificación y listado se han agrupado siguiendo estos grupos de conocimiento. Entendemos parametros invariables aquellos que son independientes de Tipologías arquitectónicas o que dependen del mismo proceso de generación de la Forma. “El listado de los parámetros que intervienen en un proceso de generación formal es una abstracción de una realidad compleja. La parametrización de las decisiones que intervienen en la selección de una forma determinada mediante “well defined problems” es imposible. El proceso que esta tesis describe entiende esta condición como un elemento que pone en valor el propio procedimiento generativo por la riqueza que la subjetividad que el equipo de diseño aporta”. La segunda parte esencial de esta investigación pretende extraer las restricciones propias del estado del arte de la fabricación digital para posteriormente incorporarlos en los procesos digitales de definición de la Forma arquitectónica. “La integración de las restricciones derivadas de las técnicas de fabricación y construcción digitales en el proceso de generación de formas desde el ámbito de la Arquitectura debe referirse a los condicionantes geométricos asociados a cada sistema constructivo, material y técnica de fabricación. La geometría es además el vínculo que permite asociar el conjunto de parámetros prestacionales seleccionados para un Proyecto con los sistemas de fabricación digital”. A estos condicionantes geométricos obtenidos del análisis de cada sistema de fabricación digital se les ha denominado “invariantes geométricos”. Bajo este término se engloban tanto límites dimensionales de fabricación, como materiales compatibles, tolerancias de manufactura e instalación y cualidades prestacionales asociadas. El objetivo de esta propuesta es emplear la geometría, herramienta fundamental y propia del Arquitecto, como nexo de unión entre el conjunto complejo y heterogéneo de parámetros previamente listados y analizados. Para ello se han simplificado en tablas específicas para cada parámetro prestacional los condicionantes geométricos que se derivan de los Sistemas de fabricación digital compatibles (ver apéndice 1). El estudio y evaluación de las capacidades y objetivos de las distintas plataformas de software disponibles y de las experiencias profesionales evaluadas en los proyectos presentados, permiten concluir que la propuesta de plataforma digital de diseño integral multi-paramétrico de formas arquitectónicas requiere de un protocolo de interoperatibilidad específico aún no universalmente establecido. Actualmente el enfoque de la estrategia para normalizar y universalizar el contexto normativo para regular la interoperatibilidad se centra en figura del gestor denominado “BIM manager”. Las atribuciones y roles de esta figura se enfocan a la gestión del continente y no del contenido (Definición de los formatos de intercambio, niveles de desarrollo (LOD) de los componentes o conjuntos constructivos, detección de interferencias y documentación del propio modelo). Siendo este ámbito un desarrollo necesario para la propuesta de universalización del sistema de diseño para fabricación digital integrado, la presente investigación aporta un organigrama y protocolo asociado. El protocolo: 1. Establece la responsabilidad de identificar y definir la Información que debe determinar el proceso de generación y desarrollo de la forma arquitectónica. 2. Define la forma digital apropiada para generar la geometría del Proyecto, incluyendo la precisión necesaria para cada componente y el nivel de detalle necesario para su exportación inequívoca al proceso de fabricación. 3. Define el tempo de cada etapa de diseño identificando un nivel de detalle acorde. 4. Acopla este organigrama dentro de las estructuras nuevas que se proponen en un entorno BIM para asegurar que no se producen solapes o vacíos con las atribuciones que se identifican para el BIM Manager. “El Arquitecto debe dirigir el protocolo de generación coordinada con los sistemas de producción digital para conseguir que la integración completa. El protocolo debe asistir al proceso de generación de forma mediante la evaluación del desempeño prestacional de cada variante en tiempo real. La comunicación entre herramientas digitales es esencial para permitir una ágil transmisión de información. Es necesario establecer un protocolo adaptado a los objetivos y las necesidades operativas de cada proyecto ya que la estandarización de un protocolo único no es posible”. Una decisión estratégica a la hora de planificar una plataforma de diseño digital común es establecer si vamos a optar por un Modelo digital único o diversos Modelos digitales federados. Cada uno de los modos de trabajo tiene fortalezas y debilidades, no obstante en el ámbito de investigación se ha concluido que un proceso integrado de Diseño que incorpore la evaluación prestacional y conceptual definida en el Capítulo 3, requiere necesariamente de varios modelos de software distintos que han de relacionarse entre sí mediante un protocolo de comunicación automatizado. Una plataforma basada en un modelo federado consiste en establecer un protocolo de comunicación entre los programas informáticos empleados por cada disciplina. En este modelo de operación cada equipo de diseño debe establecer las bases de comunicación en función del número y tipo de programas y procesos digitales a emplear. En esta investigación se propone un protocolo basado en los estándares de intercambio de información que estructura cualquier proceso de generación de forma paramétrico “La investigación establece el empleo de algoritmos evolutivos como el sistema actual óptimo para desarrollar un proceso de generación de formas basadas en la integración y coordinación de invariantes geométricos derivados de un conjunto de objetivos prestacionales y constructivos. No obstante, para la aplicación en el caso práctico realizado se ha podido verificar que la evaluación del desempeño aún no puede realizarse en una única herramienta y por lo tanto el proceso de selección de las variantes genéticas óptimas ha de ejecutarse de forma manual y acumulativa. El proceso debe realizarse de manera federada para la selección evolutiva de los invariantes geométricos dimensionales”. La evaluación del protocolo de integración y los condicionantes geométricos obtenidos como parámetros geométricos que controlan las posibles formas compatibles se realiza mediante su aplicación en un caso práctico. El ejercicio simula la colaboración multidisciplinar con modelos federados de plataformas distintas. La elección del tamaño y complejidad constructiva del proyecto se ha modulado para poder alcanzar un desarrollo completo de cada uno de los parámetros prestacionales seleccionados. Continuando con el mismo objetivo propuesto para los parámetros prestacionales, la tipología constructiva-estructural seleccionada para el ejercicio permite la aplicación la totalidad de invariantes geométricos asociados. El objetivo de este caso práctico es evaluar la capacidad alterar la forma inicialmente propuesta mediante la evaluación del desempeño prestacional de conjunto de variantes geométricas generadas a partir de un parámetro dimensional determinado. Para que este proceso tenga sentido, cada una de las variantes debe ser previamente validada conforme a las limitaciones geométricas propias de cada sistema de fabricación y montaje previstos. El interés de las conclusiones obtenidas es la identificación de una variante geométrica distante a la solución simétrica inicialmente como la solución óptima para el conjunto de parámetros seleccionados. Al tiempo se ha comprobado como la participación de un conjunto de parámetros multi-disciplinares que representan la realidad compleja de los objetivos arquitectónicos favorecen la aparición de variaciones genéticas con prestaciones mejoradas a la intuición inicial. “La herencias tipológicas suponen un límite para la imaginación de variantes formales al proceso de ideación arquitectónica. El ejercicio realizado demuestra que incluso en casos donde aparentemente la solución óptima aparenta ser obvia una variante aleatoria puede mejorar su desempeño global. La posibilidad de conocer las condiciones geométricas de las técnicas de fabricación digital compatibles con el conjunto de parámetros seleccionados por el Arquitecto para dirigir el proceso asegura que los resultados del algoritmo evolutivo empleado sean constructivamente viables. La mejora de imaginación humana con la aportación de geometrías realmente construibles supone el objetivo último de esta tesis”. ABSTRACT Architectural form generation process is shifting from analogical to digital. Digital technology has changed the way we design empowering Architects and Engineers to precisely define any complex geometry envisioned. At the same time, the construction industry, following aeronautical and automotive industries, is implementing digital manufacturing techniques to improve efficiency and quality. Consequently construction complexity will no longer be related to geometry complexity and it is associated to coordination with digital manufacturing capacities. Unfortunately it is agreed that non-standard geometries, even when proposed with performance optimization criteria, are only suitable for projects with non-restricted budgets. Furthemore, the lack of coordinated exportation protocol and geometry management between design and construction is avoiding the globalization of emergence process in built projects Present research first objective is to identify exclusive form-generation parameters related to digital manufacturing geometrical restraints. The intention was to use geometry as the form-generation tool and integrate the digital manufacturing capacities at first stages of the project. The first chapter of this text describes the investigation historical context focusing on the influence between accurate geometry definition at non-standard forms and its construction. At first examples of non-Euclidean geometries built the communication between design and construction were based on analogical partial and imprecise documentation. Deficient communication leads to geometry adaptation on site leaving the final form uncontrolled by the Architect. Computer Aided Design enable Architects to define univocally complex geometries that previously where impossible to communicate. “The univocally definition of the Form, and communication between design and construction is essential for complex geometry Projects”. The second chapter is focused on digital technologies application in form finding process and site construction. The case studies selected identifies a clear inflexion node at 1992 with the Guggenheim Museum in Bilbao. The singularity of this project was the use of Aeronautics software to define digitally the external envelope complex geometry to enable the contractor to build it. “The digital revolution has given the Architect the capacity to design buildings beyond the architectural archetypes driven by geometric-constructive limitations. The application of digital manufacturing techniques has enabled a free-form construction without geometrical limitations. In this new context performance shall be the responsible to set new conceptual boundaries, since the behavior of each possible geometry can be compare and analyze beforehand. The role of the Architect is to prioritize the performance and architectural objectives of each project in a complete and coherent set of parameters”. Projects using digital tools for solving various stages of the design process were increased exponentially since 1992 until today. Despite the significant rise of the techniques of computer-aided design the main challenge remains linking geometries and materials proposed at each design with the capabilities of digital manufacturing techniques. Design for manufacturing in a digital environment is a mature technology in other industries such as aerospace and automotive, including consumer products and decoration, but in the construction sector is an immature and disjointed system. The peculiarities of the construction industry have not yet been addressed in its entirety and research proposals made in this area until 2015 have focused in separate parts of the process and not the total process. “The main obstacle to global standardization and implementation of a complete digital process from the form-finding to construction site is the lack of an integrated protocol that integrates manufacturing, economic and commissioning limitations, together with the performance evaluation of each possible form”. The different form generation processes are studied at chapter number 3. At the introduction of this chapter there is a specific definition of "form" for the research field. Form is identified with the outer envelope geometry, including the organizational set of connected indoor spaces connected to it. Therefore it is not exclusive of the interior. The aim of this study is to analyze and classify the main digital form generation processes using different selected projects as emblematic of each type. The approach to this process is complex, with segregated and uncoordinated different actors have to intervene application. In an analogical form-generation process parameters involved are partly conscious and partly unconscious or learned. The architect has control only over limited part of the parameters to be integrated into the design, according to their knowledge and. There is also a learned aesthetical prejudice that leads the form generation process to a specific geometry leaving the performance and optimization criteria apart from the decision making process. “Using performance evaluation digital tools during form finding process provides real-time comparative information to the Architect enabling geometry selection based on its performance. The generative form generation process described at this document does not ambition to identify the optimum geometry for each set of parameters. The objective is to provide quick information at each generation of what direction is most favorable for the performance parameters selected”. Manufacturing complexity definition in relation to a global and integral process of digital design for manufacture is essential for establishing an efficient managing protocol. “The definition of complexity associated to design for production in Architecture is proposed as the factor between number of different agents involved in the process by the number of interactions required between them, divided by the percentage of the interchange of information that is standardized and proof of information loss”. Design in architecture is a multi-objective process by definition. Therefore, addressing generation process linked to a set of non-coherent parameters requires the selection of adequate generative algorithm and the interaction of the architect. During the second half of the twentieth century and early twenty-first century it have been developed various mathematical algorithms for multi-parametric digital design. Heuristic algorithms are the most adequate algorithms for architectural projects due to its nature. The advantage of such algorithms is the ability to efficiently handle large scale optimization cases where a large number of design objectives and variables are involved. These generative processes do not pursue the optimum solution, in fact it will be impossible to proof with such algorithm. This is not a problem in architectural design where the final goal is to guide the form finding process towards a better performance within the initial direction provided by the architect. This research has focused on genetic algorithms due to its capacity to generate geometric alternatives in multiple directions and evaluate the fitness against a set of parameters specified in a single process. "Any protocol seeks to achieve standardization. The design to manufacturing protocol aims to provide a coordinated and coherent form generation process between a set of design parameters and the geometrical requirements of manufacturing technique. The protocol also provides an information exchange environment where there is a communication path and the level of information is ensured. The research is focused on the process because it is considered that each project will have its own singularities and parameters but the process will stay the same. Again the development of a specific tool is not a goal for the research, the intention is to provide an open source protocol that is valid for any set of tools”. Once the digital generation processes are being analized and classified, the next step is to identify the geometric parameters that define the digital design process. The definition of design process is including from the initial shape proposal based on the intuition of the architect to the generation, evaluation, selection and production of alternatives, both of an object , system or of the entire project . The current design process in Architecture is discontinuous and linear, dividing the process in disciplines in which the construction industry is structured. The proposal is to unify all relevant parameters in one process. The parameters are listed in groups of knowledge for internal classification but the matrix used for parameter relationship determination are combined. “A multi-parameter determination of the form-finding process is the integration all the measurable decisions laying behind Architect intuition. It is not possible to formulate and solve with an algorithm the design in Architecture. It is not the intention to do so with the proposal of this research. The process aims to integrate in one open protocol a selection of parameters by using geometry as common language. There is no optimum solution for any step of the process, the outcome is an evaluation of performance of all the form variations to assist the Architect for the selection of the preferable solution for the project”. The research follows with the geometrical restrictions of today Digital manufacturing techniques. Once determined it has been integrated in the form-finding process. “Digital manufacturing techniques are integrated in the form-finding process using geometry as common language. Geometric restraints define the boundary for performance parametric form-finding process. Geometrical limitations are classified by material and constructive system”. Choose between one digital model or several federate models is a strategic decision at planning a digital design for manufacturing protocol. Each one of the working models have strengths and weakens, nevertheless for the research purposes federated models are required to manage the different performance evaluation software platforms. A protocol based on federated models shall establish a communication process between software platforms and consultants. The manager shall integrate each discipline requirements defining the communication basis. The proposed protocol is based on standards on information exchange with singularities of the digital manufacturing industry. “The research concludes evolutionary algorithms as current best system to develop a generative form finding process based on the integration and coordination of a set of performance and constructive objectives. However, for application in professional practice and standardize it, the performance evaluation cannot be done in only one tool and therefore the selection of optimal genetic variants must be run in several iterations with a cumulative result. Consequently, the evaluation process within the geometrical restraints shall be carried out with federated models coordinated following the information exchange protocol”. The integration protocol and geometric constraints evaluation is done by applying in a practical case study. The exercise simulates multidisciplinary collaboration across software platforms with federated models. The choice of size and construction complexity of the project has been modulated to achieve the full development of each of the parameters selected. Continuing with the same objective proposed for the performance parameters the constructive and structural type selected for the exercise allows the application all geometric invariants associated to the set of parameters selected. The main goal of the case study is to proof the capacity of the manufacturing integrated form finding process to generate geometric alternatives to initial form with performance improved and following the restrictions determined by the compatible digital manufacturing technologies. The process is to be divided in consecutive analysis each one limited by the geometrical conditions and integrated in a overall evaluation. The interest of this process is the result of a non-intuitive form that performs better than a double symmetrical form. The second conclusion is that one parameter evaluation alone will not justify the exploration of complex geometry variations, but when there is a set of parameters with multidisciplinary approach then the less obvious solution emerge as the better performing form. “Architectural typologies impose limitation for Architects capacity to imagine formal variations. The case study and the research conclusions proof that even in situations where the intuitive solution apparently is the optimum solution, random variations can perform better when integrating all parameters evaluation. The capacity of foreseing the geometrical properties linking each design parameter with compatible manufacturing technologies ensure the result of the form-finding process to be constructively viable. Finally, the propose of a complete process where the geometry alternatives are generated beyond the Architect intuition and performance evaluated by a set of parameters previously selected and coordinated with the manufacturing requirements is the final objective of the Thesis”.

Análisis comparativo de algoritmos de aprendizaje para predecir la evolución de pacientes con Daño Cerebral Adquirido

ste trabajo presenta un análisis comparativo entre tres algoritmos de aprendizaje diferentes basados en Árboles de Decisión (C4.5) y Redes Neuronales Artificiales (Perceptrón Multicapa MLP y Red Neuronal de Regresión General GRNN) que han sido implementados con el objetivo de predecir los resultados de la rehabilitación cognitiva de personas con daño cerebral adquirido. En el análisis se han incluido datos demográficos del paciente, el perfil de afectación y los resultados provenientes de las tareas de rehabilitación ejecutadas por los pacientes. Los modelos han sido evaluados utilizando la base de datos del Institut Guttmann. El rendimiento de los algoritmos se midió a través del análisis de la especificidad, sensibilidad y exactitud en la precisión y el análisis de la matriz de confusión. Los resultados muestran que la implementación del C4.5 alcanzó una especificidad, sensibilidad y exactitud en la precisión del 98.43%, 83.77% y 89.42% respectivamente. El rendimiento del C4.5 fue significativamente superior al obtenido por el Perceptrón Multicapa y la Red de Regresión General.

Implementación de Algoritmos de Procesado de Señal sobre FPGA: Especificación, Reutilización y Exploración del Espacio de Diseño

Esta Tesis aborda el diseño e implementación de aplicaciones en el campo de procesado de señal, utilizando como plataforma los dispositivos reconfigurables FPGA. Esta plataforma muestra una alta capacidad de lógica, e incorpora elementos orientados al procesado de señal, que unido a su relativamente bajo coste, la hacen ideal para el desarrollo de aplicaciones de procesado de señal cuando se requiere realizar un procesado intensivo y se buscan unas altas prestaciones. Sin embargo, el coste asociado al desarrollo en estas plataformas es elevado. Mientras que el aumento en la capacidad lógica de los dispositivos FPGA permite el desarrollo de sistemas completos, los requisitos de altas prestaciones obligan a que en muchas ocasiones se deban optimizar operadores a muy bajo nivel. Además de las restricciones temporales que imponen este tipo de aplicaciones, también tienen asociadas restricciones de área asociadas al dispositivo, lo que obliga a evaluar y verificar entre diferentes alternativas de implementación. El ciclo de diseño e implementación para estas aplicaciones se puede prolongar tanto, que es normal que aparezcan nuevos modelos de FPGA, con mayor capacidad y mayor velocidad, antes de completar el sistema, y que hagan a las restricciones utilizadas para el diseño del sistema inútiles. Para mejorar la productividad en el desarrollo de estas aplicaciones, y con ello acortar su ciclo de diseño, se pueden encontrar diferentes métodos. Esta Tesis se centra en la reutilización de componentes hardware previamente diseñados y verificados. Aunque los lenguajes HDL convencionales permiten reutilizar componentes ya definidos, se pueden realizar mejoras en la especificación que simplifiquen el proceso de incorporar componentes a nuevos diseños. Así, una primera parte de la Tesis se orientará a la especificación de diseños basada en componentes predefinidos. Esta especificación no sólo busca mejorar y simplificar el proceso de añadir componentes a una descripción, sino que también busca mejorar la calidad del diseño especificado, ofreciendo una mayor posibilidad de configuración e incluso la posibilidad de informar de características de la propia descripción. Reutilizar una componente ya descrito depende en gran medida de la información que se ofrezca para su integración en un sistema. En este sentido los HDLs convencionales únicamente proporcionan junto con la descripción del componente la interfaz de entrada/ salida y un conjunto de parámetros para su configuración, mientras que el resto de información requerida normalmente se acompaña mediante documentación externa. En la segunda parte de la Tesis se propondrán un conjunto de encapsulados cuya finalidad es incorporar junto con la propia descripción del componente, información que puede resultar útil para su integración en otros diseños. Incluyendo información de la implementación, ayuda a la configuración del componente, e incluso información de cómo configurar y conectar al componente para realizar una función. Finalmente se elegirá una aplicación clásica en el campo de procesado de señal, la transformada rápida de Fourier (FFT), y se utilizará como ejemplo de uso y aplicación, tanto de las posibilidades de especificación como de los encapsulados descritos. El objetivo del diseño realizado no sólo mostrará ejemplos de la especificación propuesta, sino que también se buscará obtener una implementación de calidad comparable con resultados de la literatura. Para ello, el diseño realizado se orientará a su implementación en FPGA, aprovechando tanto los elementos lógicos generalistas como elementos específicos de bajo nivel disponibles en estos dispositivos. Finalmente, la especificación de la FFT obtenida se utilizará para mostrar cómo incorporar en su interfaz información que ayude para su selección y configuración desde fases tempranas del ciclo de diseño. Abstract This PhD. thesis addresses the design and implementation of signal processing applications using reconfigurable FPGA platforms. This kind of platform exhibits high logic capability, incorporates dedicated signal processing elements and provides a low cost solution, which makes it ideal for the development of signal processing applications, where intensive data processing is required in order to obtain high performance. However, the cost associated to the hardware development on these platforms is high. While the increase in logic capacity of FPGA devices allows the development of complete systems, high-performance constraints require the optimization of operators at very low level. In addition to time constraints imposed by these applications, Area constraints are also applied related to the particular device, which force to evaluate and verify a design among different implementation alternatives. The design and implementation cycle for these applications can be tedious and long, being therefore normal that new FPGA models with a greater capacity and higher speed appear before completing the system implementation. Thus, the original constraints which guided the design of the system become useless. Different methods can be used to improve the productivity when developing these applications, and consequently shorten their design cycle. This PhD. Thesis focuses on the reuse of hardware components previously designed and verified. Although conventional HDLs allow the reuse of components already defined, their specification can be improved in order to simplify the process of incorporating new design components. Thus, a first part of the PhD. Thesis will focus on the specification of designs based on predefined components. This specification improves and simplifies the process of adding components to a description, but it also seeks to improve the quality of the design specified with better configuration options and even offering to report on features of the description. Hardware reuse of a component for its integration into a system largely depends on the information it offers. In this sense the conventional HDLs only provide together with the component description, the input/output interface and a set of parameters for its configuration, while other information is usually provided by external documentation. In the second part of the Thesis we will propose a formal way of encapsulation which aims to incorporate with the component description information that can be useful for its integration into other designs. This information will include features of the own implementation, but it will also support component configuration, and even information on how to configure and connect the component to carry out a function. Finally, the fast Fourier transform (FFT) will be chosen as a well-known signal processing application. It will be used as case study to illustrate the possibilities of proposed specification and encapsulation formalisms. The objective of the FFT design is not only to show practical examples of the proposed specification, but also to obtain an implementation of a quality comparable to scientific literature results. The design will focus its implementation on FPGA platforms, using general logic elements as base of the implementation, but also taking advantage of low-level specific elements available on these devices. Last, the specification of the obtained FFT will be used to show how to incorporate in its interface information to assist in the selection and configuration process early in the design cycle.

Algoritmos de distribución de cargas de proceso en computación con membranas

Con el surgir de los problemas irresolubles de forma eficiente en tiempo polinomial en base al dato de entrada, surge la Computación Natural como alternativa a la computación clásica. En esta disciplina se trata de o bien utilizar la naturaleza como base de cómputo o bien, simular su comportamiento para obtener mejores soluciones a los problemas que los encontrados por la computación clásica. Dentro de la computación natural, y como una representación a nivel celular, surge la Computación con Membranas. La primera abstracción de las membranas que se encuentran en las células, da como resultado los P sistemas de transición. Estos sistemas, que podrían ser implementados en medios biológicos o electrónicos, son la base de estudio de esta Tesis. En primer lugar, se estudian las implementaciones que se han realizado, con el fin de centrarse en las implementaciones distribuidas, que son las que pueden aprovechar las características intrínsecas de paralelismo y no determinismo. Tras un correcto estudio del estado actual de las distintas etapas que engloban a la evolución del sistema, se concluye con que las distribuciones que buscan un equilibrio entre las dos etapas (aplicación y comunicación), son las que mejores resultados presentan. Para definir estas distribuciones, es necesario definir completamente el sistema, y cada una de las partes que influyen en su transición. Además de los trabajos de otros investigadores, y junto a ellos, se realizan variaciones a los proxies y arquitecturas de distribución, para tener completamente definidos el comportamiento dinámico de los P sistemas. A partir del conocimiento estático –configuración inicial– del P sistema, se pueden realizar distribuciones de membranas en los procesadores de un clúster para obtener buenos tiempos de evolución, con el fin de que la computación del P sistema sea realizada en el menor tiempo posible. Para realizar estas distribuciones, hay que tener presente las arquitecturas –o forma de conexión– de los procesadores del clúster. La existencia de 4 arquitecturas, hace que el proceso de distribución sea dependiente de la arquitectura a utilizar, y por tanto, aunque con significativas semejanzas, los algoritmos de distribución deben ser realizados también 4 veces. Aunque los propulsores de las arquitecturas han estudiado el tiempo óptimo de cada arquitectura, la inexistencia de distribuciones para estas arquitecturas ha llevado a que en esta Tesis se probaran las 4, hasta que sea posible determinar que en la práctica, ocurre lo mismo que en los estudios teóricos. Para realizar la distribución, no existe ningún algoritmo determinista que consiga una distribución que satisfaga las necesidades de la arquitectura para cualquier P sistema. Por ello, debido a la complejidad de dicho problema, se propone el uso de metaheurísticas de Computación Natural. En primer lugar, se propone utilizar Algoritmos Genéticos, ya que es posible realizar alguna distribución, y basada en la premisa de que con la evolución, los individuos mejoran, con la evolución de dichos algoritmos, las distribuciones también mejorarán obteniéndose tiempos cercanos al óptimo teórico. Para las arquitecturas que preservan la topología arbórea del P sistema, han sido necesarias realizar nuevas representaciones, y nuevos algoritmos de cruzamiento y mutación. A partir de un estudio más detallado de las membranas y las comunicaciones entre procesadores, se ha comprobado que los tiempos totales que se han utilizado para la distribución pueden ser mejorados e individualizados para cada membrana. Así, se han probado los mismos algoritmos, obteniendo otras distribuciones que mejoran los tiempos. De igual forma, se han planteado el uso de Optimización por Enjambres de Partículas y Evolución Gramatical con reescritura de gramáticas (variante de Evolución Gramatical que se presenta en esta Tesis), para resolver el mismo cometido, obteniendo otro tipo de distribuciones, y pudiendo realizar una comparativa de las arquitecturas. Por último, el uso de estimadores para el tiempo de aplicación y comunicación, y las variaciones en la topología de árbol de membranas que pueden producirse de forma no determinista con la evolución del P sistema, hace que se deba de monitorizar el mismo, y en caso necesario, realizar redistribuciones de membranas en procesadores, para seguir obteniendo tiempos de evolución razonables. Se explica, cómo, cuándo y dónde se deben realizar estas modificaciones y redistribuciones; y cómo es posible realizar este recálculo. Abstract Natural Computing is becoming a useful alternative to classical computational models since it its able to solve, in an efficient way, hard problems in polynomial time. This discipline is based on biological behaviour of living organisms, using nature as a basis of computation or simulating nature behaviour to obtain better solutions to problems solved by the classical computational models. Membrane Computing is a sub discipline of Natural Computing in which only the cellular representation and behaviour of nature is taken into account. Transition P Systems are the first abstract representation of membranes belonging to cells. These systems, which can be implemented in biological organisms or in electronic devices, are the main topic studied in this thesis. Implementations developed in this field so far have been studied, just to focus on distributed implementations. Such distributions are really important since they can exploit the intrinsic parallelism and non-determinism behaviour of living cells, only membranes in this case study. After a detailed survey of the current state of the art of membranes evolution and proposed algorithms, this work concludes that best results are obtained using an equal assignment of communication and rules application inside the Transition P System architecture. In order to define such optimal distribution, it is necessary to fully define the system, and each one of the elements that influence in its transition. Some changes have been made in the work of other authors: load distribution architectures, proxies definition, etc., in order to completely define the dynamic behaviour of the Transition P System. Starting from the static representation –initial configuration– of the Transition P System, distributions of membranes in several physical processors of a cluster is algorithmically done in order to get a better performance of evolution so that the computational complexity of the Transition P System is done in less time as possible. To build these distributions, the cluster architecture –or connection links– must be considered. The existence of 4 architectures, makes that the process of distribution depends on the chosen architecture, and therefore, although with significant similarities, the distribution algorithms must be implemented 4 times. Authors who proposed such architectures have studied the optimal time of each one. The non existence of membrane distributions for these architectures has led us to implement a dynamic distribution for the 4. Simulations performed in this work fix with the theoretical studies. There is not any deterministic algorithm that gets a distribution that meets the needs of the architecture for any Transition P System. Therefore, due to the complexity of the problem, the use of meta-heuristics of Natural Computing is proposed. First, Genetic Algorithm heuristic is proposed since it is possible to make a distribution based on the premise that along with evolution the individuals improve, and with the improvement of these individuals, also distributions enhance, obtaining complexity times close to theoretical optimum time. For architectures that preserve the tree topology of the Transition P System, it has been necessary to make new representations of individuals and new algorithms of crossover and mutation operations. From a more detailed study of the membranes and the communications among processors, it has been proof that the total time used for the distribution can be improved and individualized for each membrane. Thus, the same algorithms have been tested, obtaining other distributions that improve the complexity time. In the same way, using Particle Swarm Optimization and Grammatical Evolution by rewriting grammars (Grammatical Evolution variant presented in this thesis), to solve the same distribution task. New types of distributions have been obtained, and a comparison of such genetic and particle architectures has been done. Finally, the use of estimators for the time of rules application and communication, and variations in tree topology of membranes that can occur in a non-deterministic way with evolution of the Transition P System, has been done to monitor the system, and if necessary, perform a membrane redistribution on processors to obtain reasonable evolution time. How, when and where to make these changes and redistributions, and how it can perform this recalculation, is explained.

Algoritmos de Planificación y Seguimiento de Trayectorias para Robots Agrícolas

La base para realizar cualquier tarea agrícola mediante robots, es la planificación y seguimiento de rutas o trayectorias. Así, el objetivo de esta investigación es desarrollar e implementar algoritmos de seguimiento y planificación (global y local) de trayectorias de robots agrícolas. La planificación global se realizó mediante el algoritmo A* aplicado sobre mapas de cultivo y la planificación local se realizó aplicando A* sobre un mapa 2D obtenido a partir de imágenes 3D de los obstáculos encontrados en el camino. En cuanto el seguimiento de trayectorias, esta se realizó implementando una aproximación numérica de la trayectoria mediante el método de Euler. Los parámetros correspondientes a la dinámica del controlador de la trayectoria del robot fueron obtenidos mediante algoritmos genéticos. El mapa 3D fue generado a partir del sensor Kinect de Microsoft y sus datos procesados usando Matlab 2010b. Los resultados preliminares muestran que es posible implementar estos algoritmos en pequeños robots diseñados para cultivos hilerados. Proveyendo así, una metodología robusta que permite seguir las rutas asignadas con errores inferiores a RMSE=0.1m en trayectorias de 30m.

Validación de dos algoritmos para la localización 3D del instrumental laparoscópico a partir de la imagen de vídeo endoscópico

Uno de los aspectos fundamentales en un sistema de cirugía guiada por imagen (CGI) es la localización del instrumental quirúrgico con respecto a la anatomía del paciente. Los sistemas basados en sensores ofrecen buenos niveles de precisión, pero son sensibles a distintas fuentes de ruido en el quirófano y contribuyen a la sobrecarga tecnológica del mismo. Una alternativa novedosa es analizar la imagen del vídeo endoscópico para llevar a cabo la detección y localización espacial del instrumental. Se presenta en este trabajo la validación de dos métodos, basados en el diámetro aparente y en la sección transversal del instrumental, para la localización espacial del instrumental a partir de los bordes y la posición 2D de la punta en la imagen. La validación, llevada a cabo en un simulador físico, se realiza comparando los resultados con el sistema Kinescan/IBV. Los resultados muestran para cada método un error medio de 12,7 y 12,8 mm respectivamente. La incorporación de estos algoritmos dentro del paradigma de navegación propuesto en el proyecto THEMIS permitirá al cirujano conocer la posición del instrumental de forma no intrusiva y transparente, sin necesidad de equipamiento adicional en el quirófano.

Comparación de algoritmos detectores de puntos singulares para reconocimiento de objetos en vídeo quirúrgico.

El análisis de vídeo laparoscópico ofrece nuevas posibilidades a la navegación quirúrgica al garantizar una incorporación mínima de tecnología en quirófano, evitando así alterar la ergonomía y los flujos de trabajo de las intervenciones. Una de sus principales ventajas es que puede servir como fuente de datos para reconstruir tridimensionalmente la escena laparoscópica, lo que permite dotar al cirujano de la sensación de profundidad perdida en este tipo de cirugía. En el presente trabajo de investigación se comparan dos detectores de puntos singulares, SIFT y SURF, para estimar cuál de los dos podría integrarse en un algoritmo de cálculo de coordenadas 3D, MonoSLAM, basado en la detección y el seguimiento de estos puntos singulares en los fotogramas del vídeo. Los resultados obtenidos posicionan a SURF como la mejor opción gracias a su rapidez y a su mayor capacidad de discriminación entre estructuras anatómicas e instrumental quirúrgico.

Optimización del diseño geométrico de glorietas mediante algoritmos genéticos

El funcionamiento de las glorietas es sensible a las características geométricas de los elementos que componen el diseño. Generalmente el diseño geométrico es llevado a cabo mediante procedimientos manuales e iterativos, lo que genera un elevado consumo de tiempo del proyectista. Durante el proceso, los ingenieros tratan de encontrar una solución satisfactoria al problema, tanto en planta como en alzado, aplicando unos criterios derivados de normativas y de la propia experiencia del proyectista. Esta tarea es compleja y laboriosa debido al elevado número de variables, y puede ser simplificada mediante la elaboración de unos algoritmos adecuados. En este artículo se presenta el planteamiendo de una metodología que servirá de base para el desarrollo de un modelo de optimización que proporcione la geometría de la glorieta en planta en base a dos objetivos: la consistencia de las velocidades de circulación y la eficiencia operativa. La eficiencia operativa se caracteriza mediante la demora media de los vehículos y su estudio determina el número de carriles necesarios en las entradas y en la calzada anular. La optimización de la consistencia de las velocidades tiene como objetivo reducir los conflictos y la accidentalidad, además de contribuir a la mejora de la eficiencia de la circulación, ya que permite simplificar la tarea de incorporación de los vehículos en el flujo de la calzada anular. Para su cálculo es necesario determinar previamente las trayectorias de los vehículos y los perfiles de velocidades de las trayectorias más rápidas. Una buena consistencia debe minimizar la variación de velocidad entre los elementos geométricos consecutivos y la velocidad relativa entre corrientes de tráfico en conflicto. Para resolver el problema de optimización se plantea un procedimiento heurístico basado en algoritmos genéticos. El modelo requiere de unos procedimientos para la generación de forma aleatoria de la geometría de la glorieta y para el cálculo de las trayectorias de los vehículos y de las funciones objetivo a partir de la geometría, junto al diseño de unos operadores genéticos que tengan en consideración las interacciones que se presentan entre los elementos que definen la geometría de la glorieta.