Aceleración de algoritmos para imágenes hiperespectrales con OpenCL

En el presente trabajo se propone dar solución a uno de los problemas principales surgido en el campo del análisis de imágenes hiperespectrales. En las últimas décadas este campo está siendo muy activo, por lo que es de vital importancia tratar su problema principal: mezcla espectral. Muchos algoritmos han tratado de solucionar este problema, pero que a través de este trabajo se propone una cadena nueva de desmezclado en paralelo, para ser acelerados bajo el paradigma de programación paralela de OpenCl. Este paradigma nos aporta el modelo de programación unificada para acelerar algoritmos en sistemas heterogéneos. Podemos dividir el proceso de desmezclado espectral en tres etapas. La primera tiene la tarea de encontrar el número de píxeles puros, llamaremos endmembers a los píxeles formados por una única firma espectral, utilizaremos el algoritmo conocido como Geometry-based Estimation of number of endmembers, GENE. La segunda etapa se encarga de identificar los píxel endmembers y extraerlos junto con todas sus bandas espectrales, para esta etapa se utilizará el algoritmo conocido por Simplex Growing Algorithm, SGA. En la última etapa se crean los mapas de abundancia para cada uno de los endmembers encontrados, de esta etapa será encargado el algoritmo conocido por, Sum-to-one Constrained Linear Spectral Unmixing, SCLSU. Las plataformas utilizadas en este proyecto han sido tres: CPU, Intel Xeon E5-2695 v3, GPU, NVidia GeForce GTX 980, Acelerador, Intel Xeon Phi 31S1P. La idea de este proyecto se basa en realizar un análisis exhaustivo de los resultados obtenidos en las diferentes plataformas, con el fin de evaluar cuál se ajusta mejor a nuestras necesidades.

Verificación de algoritmos y estructuras de datos en Dafny

La verificación formal de un programa es la demostración de que este funciona de acuerdo a una descripción del comportamiento esperado en toda posible ejecución. La especificación de lo deseado puede utilizar técnicas diversas y entrar en mayor o menor detalle, pero para ganarse el título de formal esta ha de ser matemáticamente rigurosa. El estudio y ejercicio manual de alguna de esas técnicas forma parte del currículo común a los estudios de grado de la Facultad de Informática y del itinerario de Ciencias de la Computación de la Facultad de Ciencias Matemáticas de la Universidad Complutense de Madrid, como es el caso de la verificación con pre- y postcondiciones o lógica de Hoare. En el presente trabajo se explora la automatización de estos métodos mediante el lenguaje y verificador Dafny, con el que se especifican y verifican algoritmos y estructuras de datos de diversa complejidad. Dafny es un lenguaje de programación diseñado para integrar la especificación y permitir la verificación automática de sus programas, con la ayuda del programador y de un demostrador de teoremas en la sombra. Dafny es un proyecto en desarrollo activo aunque suficientemente maduro, que genera programas ejecutables.

Aceleración de algoritmos de estimación de movimiento mediante OpenCL

El flujo óptico y la estimación de movimiento es área de conocimiento muy importante usado en otros campos del conocimiento como el de la seguridad o el de la bioinformática. En estos sectores, se demandan aplicaciones de flujo óptico que realicen actividades muy importantes con tiempos de ejecución lo más bajos posibles, llegando a tiempo real si es posible. Debido a la gran complejidad de cálculos que siguen a este tipo de algoritmos como se observará en la sección de resultados, la aceleración de estos es una parte vital para dar soporte y conseguir ese tiempo real tan buscado. Por lo que planteamos como objetivo para este TFG la aceleración de este tipo de algoritmos mediante diversos tipos de aceleradores usando OpenCL y de paso demostrar que OpenCL es una buena herramienta que permite códigos paralelizados con un gran Speedup a la par que funcionar en toda una diversa gama de dispositivos tan distintos como un GPU y una FPGA. Para lo anteriormente mencionado trataremos de desarrollar un código para cada algoritmo y optimizarlo de forma no especifica a una plataforma para posteriormente ejecutarlo sobre las diversas plataformas y medir tiempos y error para cada algoritmo. Para el desarrollo de este proyecto partimos de la teoría de dos algoritmos ya existentes: Lucas&Kanade monoescala y el Horn&Schunck. Además, usaremos estímulos para estos algoritmos muy aceptados por la comunidad como pueden ser el RubberWhale o los Grove, los cuales nos ayudarán a establecer la corrección de estos algoritmos y analizar su precisión, dando así un estudio referencia para saber cual escoger.

Métodos heurísticos para un problema multicriterio de distribución de ayuda humanitaria

Large scale disasters, such as the one caused by the Typhoon Haiyan, which devastated portions of the Philippines in 2013, or the catastrophic 2010 Haiti earthquake, which caused major damage in Port-au-Prince and other settlements in the region, have massive and lasting effects on populations. Nowadays, disasters can be considered as a consequence of inappropriately managed risk. These risks are the product of hazards and vulnerability, which refers to the extent to which a community can be affected by the impact of a hazard. In this way, developing countries, due to their greater vulnerability, suffer the highest costs when a disaster occurs. Disaster relief is a challenge for politics, economies, and societies worldwide. Humanitarian organizations face multiple decision problems when responding to disasters. In particular, once a disaster strikes, the distribution of humanitarian aid to the population affected is one of the most fundamental operations in what is called humanitarian logistics. This term is defined as the process of planning, implementing and controlling the effcient, cost-effective ow and storage of goods and materials as well as related information, from the point of origin to the point of consumption, for the purpose of meeting the end bene- ciaries' requirements and alleviate the suffering of vulnerable people, [the Humanitarian Logistics Conference, 2004 (Fritz Institute)]. During the last decade there has been an increasing interest in the OR/MS community in studying this topic, pointing out the similarities and differences between humanitarian and business logistics, and developing models suited to handle the special characteristics of these problems. Several authors have pointed out that traditional logistic objectives, such as minimizing operation cost, are not the most relevant goals in humanitarian operations. Other factors, such as the time of operation, or the design of safe and equitable distribution plans, come to the front, and new models and algorithms are needed to cope with these special features. Up to six attributes related to the distribution plan are considered in our multi-criteria approach. Even though there are usually simple ways to measure the cost of an operation, the evaluation of some other attributes such as security or equity is not easy. As a result, several attribute measures are proposed and developed, focusing on different aspects of the solutions. Furthermore, when metaheuristic solution methods are used, considering non linear objective functions does not increase the complexity of the algorithms significantly, and thus more accurate measures can be utilized...