Time aware genetic algorithm for forest fire propagationrnprediction: exploiting multi-core platforms

摘要

Forest fire propagation prediction is a crucial issue when fighting these hazards as efficiently as possible.rnSeveral propagation models have been developed and integrated in computer simulators. Such modelsrnrequire a set of input parameters that, in some cases, are difficult to know or even estimate preciselyrnbeforehand Therefore, a calibration technique based on genetic algorithm (GA) was introduced to reducernthe uncertainty in input parameters values and improve the accuracy of the predictions. Such a techniquernrequires the execution of a set of simulations and several iterations of the process to calibrate the values ofrnthe input parameters. To reduce the execution time of this calibration stage, an Message Passing Interfacernmaster/worker scheme was developed to distribute the simulations of one iteration among the workerrnprocesses. However, the execution time of each simulation varies drastically depending on the particularrninput parameters used, provoking a significant load imbalance. To overcome this imbalance and reducernexecution time to operational requirements, core allocation policies have been developed. These policies arernbased on execution time estimation and classification of simulations according to the estimated executionrntime. Then, multicore capabilities of the current systems are applied to devote more resources (cores) to thernlongest simulations reducing the load imbalance. These simulations that are estimated as taking too long,rneven when many resources are devoted to them, require especial consideration. So, a generation time limitrnhas been introduced, and three different strategies have been designed considering individuals that exceed therngeneration execution time limit. In the first one, the longest individuals are replaced before starting thernexecution with shorter individuals (Time Aware Core allocation with replacement). In the second one,rnthese individuals are executed, but when the generation limit is reached, the individuals still executing arernkilled (Time Aware Core allocation without replacement). In the third one, all the individuals are executedrnnormally, and when the generation time limit is reached, the GA is applied considering the individuals thatrnhave finished their executions, while the individuals still executing are allowed to continue running and arernconsidered by the GA when they finish. The three strategies have been tested in real scenarios, and thernresults show these policies significantly improve the calibration accuracy within the superimposed deadlines.rn© 2016 The Authors. Concurrency and Computation: Practice and Experience Published by John Wiley &rnSons Ltd.