Algoritmos metaheurísticos en el problema del particionado hardware/software de sistemas embebidos

El particionado hardware/software es una tarea fundamental en el co-diseño de sistemas embebidos. En ella se decide, teniendo en cuenta las métricas de diseño, qué componentes se ejecutarán en un procesador de propósito general (software) y cuáles en un hardware específico. En los últimos años se han propuesto diversas soluciones al problema del particionado dirigidas por algoritmos metaheurísticos. Sin embargo, debido a la diversidad de modelos y métricas utilizadas, la elección del algoritmo más apropiado sigue siendo un problema abierto. En este trabajo se presenta una comparación de seis algoritmos metaheurísticos: Búsqueda aleatoria (Random search), Búsqueda tabú (Tabu search), Recocido simulado (Simulated annealing), Escalador de colinas estocástico (Stochastic hill climbing), Algoritmo genético (Genetic algorithm) y Estrategia evolutiva (Evolution strategy). El modelo utilizado en la comparación está dirigido a minimizar el área ocupada y el tiempo de ejecución, las restricciones del modelo son consideradas como penalizaciones para incluir en el espacio de búsqueda otras soluciones. Los resultados muestran que los algoritmos Escalador de colinas estocástico y Estrategia evolutiva son los que mejores resultados obtienen en general, seguidos por el Algoritmo genético.

Simulación de procesos químicos (curso 2011-2012)

Apuntes en formato html que incluyen los siguientes temas de la parte de simulación en la asignatura «simulación y optimización de procesos químicos» TEMA 1. Introducción 1.1 Introducción. 1.2 Desarrollo histórico de la simulación de procesos. Relación entre simulación optimización y síntesis de procesos. 1.3 Tipos de simuladores: Modular secuencial. Modular simultáneo. Basada en ecuaciones. TEMA 2. Simulación Modular Secuencial 2.1 Descomposición de diagramas de flujo (flowsheeting) 2.2 Métodos basados en las matrices booleanas Localización de redes cíclicas máximas. Algoritmo de Sargent y Westerberg. Algoritmo de Tarjan. 2.3 Selección de las corrientes de corte: 2.3.1 Caso general planteamiento como un "set-covering problem" (algoritmo de Pho y Lapidus) 2.3.2 Número mínimo de corrientes de corte (algoritmo de Barkley y Motard) 2.3.3 Conjunto de corrientes de corte no redundante (Algoritmo de Upadhye y Grens) TEMA 3. Simulación Modular Simultánea 3.1 Efecto de las estrategias tipo cuasi Newton sobre la convergencia de los diagramas de flujo. TEMA 4. Simulación Basada en Ecuaciones 4.1 Introducción. Métodos de factorización de matrices dispersas. Métodos a priori y métodos locales. 4.2 Métodos locales: Criterio de Markowitz. 4.3 Métodos a priori: 4.3.1 Triangularización por bloques: a. Base de salida admisible (transversal completo). b. Aplicación de los algoritmos de Sargent y Tarjan a matrices dispersas. c. Reordenación. 4.3.2 Transformación en matriz triangular bordeada. 4.4 Fase numerica. Algoritmo RANKI 4.5 Comparación entre los diferentes sistemas de simulación. Ventajas e Inconvenientes. TEMA 5. Grados de libertad y variables de diseño de un diagrama de flujo 5.1 Teorema de Duhem y regla de las fases 5.2 Grados de libertad de un equipo 5.3 Grados de libertad de un diagrama de flujo 5.4 Elección de las variables de diseño.

Interoperabilidad semántica de ontologías basada en técnicas de procesamiento del lenguaje natural

Se presenta un estudio y propuesta de interoperabilidad semántica entre ontologías del dominio de la salud basada en técnicas de procesamiento del lenguaje natural. El objetivo fundamental ha sido el desarrollo de un algoritmo de interconexión semántica entre los términos de dos ontologías solapadas y heterogéneas, denominadas «fuente» (Clasificación internacional de enfermedades, 9ª revisión, modificación clínica: CIE-9-MC) y «diana» (esquema jerárquico de la asignatura Enfermería Materno-Infantil: EMI). Esta propuesta permite emparejar semánticamente ontologías, a partir de la reutilización de otro recurso ontológico (WordNet español), sin destruir o modificar la semántica de identidad de cada una de las ontologías involucradas. El modelo presentado puede permitir al usuario acceder a la información que necesita en otra clasificación jerárquica, sin precisar de un entrenamiento referido a la conceptualización de cada sistema, pues utilizaría la ontología «diana» con la que está familiarizado para su aplicación a la recuperación de información.

Estrategias para identificar oclusiones y planificación monocular para una mejora de la percepción visual de la escena

Esta Tesis doctoral está orientada al estudio de estrategias y técnicas para el tratamiento de oclusiones. Las oclusiones suponen uno de los principales problemas en la percepción de una escena mediante visión por computador. Las condiciones de luz, los puntos de vista con los que se captura información de la escena, las posiciones y orientaciones de los objetos presentes en la escena son algunas de las causas que provocan que los objetos puedan quedar ocluidos parcialmente. Las investigaciones expuestas en esta Tesis se pueden agrupar en función de su objetivo en dos grupos: técnicas cuya finalidad es detectar la presencia de oclusiones y estrategias que permiten mejorar la percepción de un sistema de visión por computador, aun en el caso de la presencia de oclusiones. En primer lugar, se han desarrollado una serie de técnicas orientadas a la detección de oclusiones a partir de procesos de extracción de características y de segmentación color en imágenes. Estas técnicas permiten definir qué regiones en la imagen son susceptibles de considerarse zonas de oclusión, debido a una mala percepción de la escena, como consecuencia de observarla con un mal punto de vista. Como aplicación de estas técnicas se han desarrollado algoritmos basados en la segmentación color de la imagen y en la detección de discontinuidades mediante luz estructurada. Estos algoritmos se caracterizan por no incluir conocimiento previo de la escena. En segundo lugar, se han presentado una serie de estrategias que permiten corregir y/o modificar el punto de vista de la cámara con la que se observa la escena. De esta manera, las oclusiones identificadas, mediante los métodos expuestos en la primera parte de la Tesis, y que generalmente son debidas a una mala localización de la cámara pueden ser eliminadas o atenuadas cambiando el punto de vista con el que se produce la observación. En esta misma línea se presentan dos estrategias para mejorar la posición y orientación espacial de la cámara cuando ésta se emplea para la captura de imágenes en procesos de reconocimiento. La primera de ellas se basa en la retroproyección de características obtenidas de una imagen real, a partir de una posición cualquiera, en imágenes virtuales correspondientes a las posibles posiciones que puede adoptar la cámara. Este algoritmo lleva a cabo la evaluación de un mapa de distancias entre estas características buscando en todo momento, maximizar estas distancias para garantizar un mejor punto de vista. La ventaja radica en que en ningún caso se hace necesario mover la cámara para determinar una nueva posición que mejore la percepción de la escena. La segunda de estas estrategias, busca corregir la posición de la cámara buscando la ortogonalidad. En este caso, se ha partido de la hipótesis inicial de que la mayor superficie visible siempre se suele conseguir situando la cámara ortogonalmente al plano en el que se sitúa el objeto.

An application of fuzzy logic for hardware/software partitioning in embedded systems

Hardware/Software partitioning (HSP) is a key task for embedded system co-design. The main goal of this task is to decide which components of an application are to be executed in a general purpose processor (software) and which ones, on a specific hardware, taking into account a set of restrictions expressed by metrics. In last years, several approaches have been proposed for solving the HSP problem, directed by metaheuristic algorithms. However, due to diversity of models and metrics used, the choice of the best suited algorithm is an open problem yet. This article presents the results of applying a fuzzy approach to the HSP problem. This approach is more flexible than many others due to the fact that it is possible to accept quite good solutions or to reject other ones which do not seem good. In this work we compare six metaheuristic algorithms: Random Search, Tabu Search, Simulated Annealing, Hill Climbing, Genetic Algorithm and Evolutionary Strategy. The presented model is aimed to simultaneously minimize the hardware area and the execution time. The obtained results show that Restart Hill Climbing is the best performing algorithm in most cases.

Optimización de áreas funcionales espaciales mediante algoritmos evolutivos multioperador. Aplicación a la delimitación de mercados locales de trabajo

El documento de esta tesis por compendio de publicaciones se divide en dos partes: la síntesis donde se resume la fundamentación, resultados y conclusiones de esta tesis, y las propias publicaciones en su formato original, que se incluyen como apéndices. Dado que existen acuerdo de confidencialidad (véase "Derechos" más adelante) que impiden su publicación en formato electrónico de forma pública y abierta (como es el repositorio de la UA), y acorde con lo que se dictamina en el punto 6 del artículo 14 del RD 99/2011, de 28 de enero, no se incluyen estos apéndices en el documento electrónico que se presenta en cedé, pero se incluyen las referencias completas y sí se incluyen integramente en el ejemplar encuadernado. Si el CEDIP y el RUA así lo decidiesen más adelante, podría modificarse este documento electrónico para incluir los enlaces a los artículos originales.

Partición hardware software de un codificador JPEG utilizando escalador de colinas estocástico

La partición hardware/software es una etapa clave dentro del proceso de co-diseño de los sistemas embebidos. En esta etapa se decide qué componentes serán implementados como co-procesadores de hardware y qué componentes serán implementados en un procesador de propósito general. La decisión es tomada a partir de la exploración del espacio de diseño, evaluando un conjunto de posibles soluciones para establecer cuál de estas es la que mejor balance logra entre todas las métricas de diseño. Para explorar el espacio de soluciones, la mayoría de las propuestas, utilizan algoritmos metaheurísticos; destacándose los Algoritmos Genéticos, Recocido Simulado. Esta decisión, en muchos casos, no es tomada a partir de análisis comparativos que involucren a varios algoritmos sobre un mismo problema. En este trabajo se presenta la aplicación de los algoritmos: Escalador de Colinas Estocástico y Escalador de Colinas Estocástico con Reinicio, para resolver el problema de la partición hardware/software. Para validar el empleo de estos algoritmos se presenta la aplicación de este algoritmo sobre un caso de estudio, en particular la partición hardware/software de un codificador JPEG. En todos los experimentos es posible apreciar que ambos algoritmos alcanzan soluciones comparables con las obtenidas por los algoritmos utilizados con más frecuencia.

Estudio y mejora de métodos de registro 3D: aceleración sobre unidades de procesamiento gráfico y caracterización del espacio de transformaciones iniciales

Durante los últimos años ha sido creciente el uso de las unidades de procesamiento gráfico, más conocidas como GPU (Graphic Processing Unit), en aplicaciones de propósito general, dejando a un lado el objetivo para el que fueron creadas y que no era otro que el renderizado de gráficos por computador. Este crecimiento se debe en parte a la evolución que han experimentado estos dispositivos durante este tiempo y que les ha dotado de gran potencia de cálculo, consiguiendo que su uso se extienda desde ordenadores personales a grandes cluster. Este hecho unido a la proliferación de sensores RGB-D de bajo coste ha hecho que crezca el número de aplicaciones de visión que hacen uso de esta tecnología para la resolución de problemas, así como también para el desarrollo de nuevas aplicaciones. Todas estas mejoras no solamente se han realizado en la parte hardware, es decir en los dispositivos, sino también en la parte software con la aparición de nuevas herramientas de desarrollo que facilitan la programación de estos dispositivos GPU. Este nuevo paradigma se acuñó como Computación de Propósito General sobre Unidades de Proceso Gráfico (General-Purpose computation on Graphics Processing Units, GPGPU). Los dispositivos GPU se clasifican en diferentes familias, en función de las distintas características hardware que poseen. Cada nueva familia que aparece incorpora nuevas mejoras tecnológicas que le permite conseguir mejor rendimiento que las anteriores. No obstante, para sacar un rendimiento óptimo a un dispositivo GPU es necesario configurarlo correctamente antes de usarlo. Esta configuración viene determinada por los valores asignados a una serie de parámetros del dispositivo. Por tanto, muchas de las implementaciones que hoy en día hacen uso de los dispositivos GPU para el registro denso de nubes de puntos 3D, podrían ver mejorado su rendimiento con una configuración óptima de dichos parámetros, en función del dispositivo utilizado. Es por ello que, ante la falta de un estudio detallado del grado de afectación de los parámetros GPU sobre el rendimiento final de una implementación, se consideró muy conveniente la realización de este estudio. Este estudio no sólo se realizó con distintas configuraciones de parámetros GPU, sino también con diferentes arquitecturas de dispositivos GPU. El objetivo de este estudio es proporcionar una herramienta de decisión que ayude a los desarrolladores a la hora implementar aplicaciones para dispositivos GPU. Uno de los campos de investigación en los que más prolifera el uso de estas tecnologías es el campo de la robótica ya que tradicionalmente en robótica, sobre todo en la robótica móvil, se utilizaban combinaciones de sensores de distinta naturaleza con un alto coste económico, como el láser, el sónar o el sensor de contacto, para obtener datos del entorno. Más tarde, estos datos eran utilizados en aplicaciones de visión por computador con un coste computacional muy alto. Todo este coste, tanto el económico de los sensores utilizados como el coste computacional, se ha visto reducido notablemente gracias a estas nuevas tecnologías. Dentro de las aplicaciones de visión por computador más utilizadas está el registro de nubes de puntos. Este proceso es, en general, la transformación de diferentes nubes de puntos a un sistema de coordenadas conocido. Los datos pueden proceder de fotografías, de diferentes sensores, etc. Se utiliza en diferentes campos como son la visión artificial, la imagen médica, el reconocimiento de objetos y el análisis de imágenes y datos de satélites. El registro se utiliza para poder comparar o integrar los datos obtenidos en diferentes mediciones. En este trabajo se realiza un repaso del estado del arte de los métodos de registro 3D. Al mismo tiempo, se presenta un profundo estudio sobre el método de registro 3D más utilizado, Iterative Closest Point (ICP), y una de sus variantes más conocidas, Expectation-Maximization ICP (EMICP). Este estudio contempla tanto su implementación secuencial como su implementación paralela en dispositivos GPU, centrándose en cómo afectan a su rendimiento las distintas configuraciones de parámetros GPU. Como consecuencia de este estudio, también se presenta una propuesta para mejorar el aprovechamiento de la memoria de los dispositivos GPU, permitiendo el trabajo con nubes de puntos más grandes, reduciendo el problema de la limitación de memoria impuesta por el dispositivo. El funcionamiento de los métodos de registro 3D utilizados en este trabajo depende en gran medida de la inicialización del problema. En este caso, esa inicialización del problema consiste en la correcta elección de la matriz de transformación con la que se iniciará el algoritmo. Debido a que este aspecto es muy importante en este tipo de algoritmos, ya que de él depende llegar antes o no a la solución o, incluso, no llegar nunca a la solución, en este trabajo se presenta un estudio sobre el espacio de transformaciones con el objetivo de caracterizarlo y facilitar la elección de la transformación inicial a utilizar en estos algoritmos.