Multi-core hybrid architectures applied to forest fire spread prediction

Premi Extraordinari de Doctorat concedit pels programes de doctorat de la UAB per curs acadèmic 2017-2018Els incendis forestals són un tipus de desastre natural que representa un gran repte per a la societat a causa dels seus elevats costos econòmics i humans. Amb l'objectiu d'evitar els costos derivats d'aquest desastre natural i millorar l'extinció dels mateixos, els simuladors de propagació d'incendis es poden utilitzar per intentar anticipar el comportament de l'incendi i ajudar a aconseguir una extinció de l'incendi més eficient i segura. Quan es propociona una predicció de la propagació d'un incendi forestal existeixen dos elements claus: la precisió i el temps necessari per computar la predicció. Sota el context de la simulació de desastres naturals, és ben conegut que part de l'error de la predicció estàsubjecta a la incertesa en les dades d'entrada utilitzades pel simulador. Per aquesta raó, la comunitat científica ha creat diferents mètodes de calibratge per reduir la incertesa de les dades d'entrada i així millorar l'error de la predicció. En aquest treball s'utilitza una metodologia de predicció basada en dues etapes que ha estat provada en treballs previs amb bons resultats. Aquest mètode de calibratge implica una necessitat considerable de recursos computacionals i eleva el temps de còmput a causa de l'ús d'un Algorisme Genètic com a mètode de cerca de les millors dades d'entrada del simulador. S'ha de tenir en compte les restriccions de temps sota les quals treballa un sistema de predicció d'incendis. Es necessari mantenir un equilibri adequat entre precisió i temps de còmput utilitzat per poder proporcionar una bona predicció a temps. Per poder utilitzar la tècnica de calibratge esmentat, s'ha de solucionar el problema que representa que algunes solucions siguin inviables ja que impliquen temps d'execució molt llargs, fet que pot impedir que es pugui donar resposta a temps en un suposat context operacional. La present Tesi Doctoral utilitza les arquitectures multi-core amb l'objectiu d'accelerar el mètode de predicció basat en dues etapes per poder proporcionar una predicció sota temps de lliurament que es donarien en un context real. Per aquesta raó, es defineix una política d'assignació de nuclis basada en el temps disponible d'execució. Aquesta política d'assignació assignaràun nombre determinat de recursos a una determinada simulació prèviament a ser executada. La política d'assignació es basa en arbres de decisió creats amb els paràmetres de simulació utilitzats. No obstant això, es pro¬posen dos mètodes per a aquells casos on l'Algorisme Genètic tendeix a crear individus el temps d'execució dels quals provoquen que sigui impossible acabar el calibratge a temps: ReTAC i SoftTAC. La proposta ReTAC utilitza la resolució de les simulacions per solucionar el problema. En concret, ReTAC tracta de trobar la mínima reducció de la resolució que permeti que aquelles simulacions que són massa llargues puguin ser executades mantenint la precisió sota control. D'altra banda, SoftTAC utilitza poblacions de grandària dinàmica. Es a dir, els individus no es maten en arribar al límit de temps d'execució assignat a una generació de l'AG, sino que es permet l'execució simultanea d'individus de diferents generacions de l'algorisme genètic. Totes les estratègies de predicció proposades han estat provades amb casos reals obtenint resultats satisfactoris en termes de precisió i de temps de còmput utilitzat.Los incendios forestales son un tipo de catástrofe natural que representa un gran reto para sociedad debido a sus elevados costes económicos y humanos. Con el objetivo de evitar los costes derivados de dicho desastre natural y mejorar la extinción de éstos, los simuladores de propagación de incendios se pueden utilizar para intentar anticipar el comportamiento del incendio y ayudar a conseguir una extinción del incendio más eficiente y segura. Cuando se propociona una predicción de la propagación de un incendio forestal existen dos elementos clave: la precisión y el tiempo necesario para computar la predicción. Bajo el contexto de la simulación de desastres naturales, es bien conocido que parte del error de la predicción está sujeta a la incertidumbre en los datos de entrada utilizados por el simulador. Por esta razón, la comunidad científica ha creado distintos métodos de calibración para reducir la incertidumbre de los datos de entrada y así mejorar el error de la predicción. En este trabajo se utiliza una metodología de calibración basada en dos etapas que ha sido probada en trabajos previos con buenos resultados. Este método de calibración implica una necesidad considerable de recursos computacionales y eleva el tiempo de cómputo debido al uso de un Algoritmo Genético como método de búsqueda de los mejores datos de entrada del simulador. Se debe tener en cuenta las restricciones de tiempo bajo las que trabaja un sistema de predicción de incendios. Es necesario mantener un equilibrio adecuado entre precisión y tiempo de cómputo utilizado para poder proporcionar una buena predicción a tiempo. Para poder utilizar la técnica de calibración mencionada, se debe solucionar el problema que representa que algunas soluciones sean inviables debido a que implican tiempos de ejecución muy largos, lo que puede impedir que se pueda dar respuesta a su debido tiempo en un supuesto contexto operacional. La presente Tesis Doctoral utiliza las arquitecturas multi-core con el objetivo de acelerar el método de calibración basado en dos etapas y poder proporcionar una predicción bajo tiempos de entrega que se darían en un contexto real. Por esta razón, se define una política de asignación de núcleos basada en el tiempo disponible de ejecución . Esta política de asignación asignará un número determinado de recursos a una determinada simulación previamente a ser ejecutada. La política de asignación se basa en árboles de decisión creados con los parametros de simulación n utilizados. Sin embargo, se proponen dos métodos para aquellos casos donde el algoritmo genético tienda a crear individuos cuyo tiempo de ejecución provocan que sea imposible acabar la calibración a tiempo: Re-TAC y Soft-TAC. La propuesta ReTAC utiliza la resolución de las simulaciones para solucionar el problema. En concreto, Re-TAC trata de encontrar la mínima reducción de la resolución que permita que aquellas simulaciones que son demasiado largas puedan ser ejecutadas manteniendo la precisión bajo control. Por otro lado, Soft-TAC utiliza poblaciones de tamaño dinámico. Es decir, los individuos no se matan al alcanzar el límite de timepo de ejecución asignado a una generación del Algoritmo Genético, sino que se permite la ejecución simultanea de individuos de distintas generaciones haciendo que el tamaño de la población sea dinámico. Todas la estrategias de predicción propuestas han sido probadas con casos reales obteniendo resultados satisfactorios en términos de precisión y de tiempo de cómputo utilizado.Large forest fires are a kind of natural hazard that represents a big threat for the society because it implies a significant number of economic and human costs. To avoid major damages and to improve forest fire management, one can use forest fire spread simulators to predict fire behaviour. When providing forest fire predictions, there are two main considerations: accuracy and computation time. In the context of natural hazards simulation, it is well known that part of the final forecast error comes from uncertainty in the input data. For this reason several input data calibration methods have been developed by the scientific community. In this work, we use the Two-Stage calibration methodology, which has been shown to provide good results. This calibration strategy is computationally intensive and timeconsuming because it uses a Genetic Algorithm as an optimization strategy. Taking into account the aspect of urgency in forest fire spread prediction, we need to maintain a balance between accuracy and the time needed to calibrate the input parameters. In order to take advantage of this technique, we must deal with the problem that some of the obtained solutions are impractical, since they involve simulation times that are too long, preventing the prediction system from being deployed at an operational level. This PhD Thesis exploits the benefits of current multi-core architectures with the aim of accelerating the Two-Stage forest fire prediction scheme being able to deliver predictions under strict real time constraints. For that reason, a Time-Aware Core allocation (TAC) policy has been defined to determine in advance the more appropriate number of cores assigned to a given forest fire spread simulation. Each execution configuration is obtained considering the particular values of the input data needed for each simulation by applying a dynamic decision tree. However, in those cases where the optimization process will drive the system to solutions whose simulation time will prevent the system to finish on time, two different enhanced schemes have been defined: Re-TAC and Soft-TAC. Re-TAC approach deals with the resolution of the simulation. In particular, Re-TAC finds the minimum resolution reduction for such long simulations, keeping accuracy loss to a known interval. On the other hand, Soft-TAC considers the GA's population size as dynamic in the sense that none individual will be killed for over passing the internal generations deadline, but it will be keep executing and the population size for the subsequent GA's generation is modified according to that. All proposed prediction strategies have been tested with past real cases obtaining satisfactory results both in terms of prediction accuracy and in the time required to deliver the prediction