Análise do desempenho de um algoritmo genético paralelizado com OpenMP baseado em rastros de execução

Abstract

This work condutcs an analysis of the performance of a Genetic Algorithm (GA) parallelized with the Application Program Interface (API) Open Multi Processing (OpenMP) from their execution traces. This GA proposing a solution to the Vehicle Routing Problem (VRP). The VRP is a combinatorial optimization problem, which is to route vehicles with a certain transport capacity to meet requests from a group of cities. And the cost each city can be visited only once and only one vehicle. And the total cost of the route can not exceed the capacity of the vehicle. The solution comprises a set of routes capable of satisfying the demand of all the customers with the minimum cost. The results performance obtained by parallelization of GA, although it has reduced the running time, they were not ideally expected. Therefore, the general objective of this work is to investigate the causes of the low performance obtained by the GA, performing a performance analysis from the execution traces. From this analysis, propose improvements to this algorithm. In this work the collection technique used is the trace, which is the most comprehensive way to obtain data on the behavior of parallel applications. To analyze the data collected will use interactive analysis technique for trace display. In this technical, data collected from the tracking are converted into visual representations. The tool that will be used to perform a scan is the Score-P, which is a highly scalable tool for measuring highperformance application performance. For data analysis we used the Vampir visualization tool. Our results showed that the parallelization of GA is according to the model in which it was implemented and to the set of VRP instances used, no possible improvements were identified.