Please use this identifier to cite or link to this item: http://ri.ufs.br/jspui/handle/riufs/12494
Document Type: Monografia
Title: Implementação e avaliação de algoritmos sequencial e paralelo para descoberta de rotas ótimas para veículos
Authors: Costa, Jackson Tavares da
Issue Date: 11-Oct-2019
Advisor: Salgueiro, Ricardo José Paiva de Britto
Co-advisor: Souza, Thiago Xavier Rocha de
Resumo : O aumento significativo da população nos grandes centros urbanos, criou algumas problemáticas analisadas e tratadas nesse trabalho como a mobilidade urbana e sua eficiência, devido a necessidade cada vez maior de uma locomoção rápida e de baixo custo. Nesse cenário, as Smart Cities (Cidades Inteligentes) disponibilizam uma variedade de soluções que possibilitam reduzir tais problemas, gerando soluções diversas e de maneira sustentável. A partir disso, realizou-se uma simulação de tráfego de veículos em regiões da cidade de Aracaju no estado de Sergipe - Brasil e em Manhattan no estado de Nova Iorque - EUA, na ferramenta de simulação de tráfego SUMO (Simulation of Urban MObility), onde se deu a execução do algoritmo A-Star clássico na literatura, implementado de forma paralela, utilizando CUDA da NVIDIA e uma GPU (Graphics Processing Unit) que por sua vez, realiza cálculos complexos de forma eficiente quando comparada a CPU (Central Process Unit) e também implementado de forma sequencial, que executa uma instrução por vez na CPU. A utilização de GPU em si, além de vantajosa devido ao seu poder de realizar operação de ponto flutuante, é também uma solução de dispositivo viável pelo seu baixo custo financeiro, evitando assim uma infraestrutura de supercomputadores para realizar tal tarefa. Dessa forma, o algoritmo implementado de forma paralela neste trabalho e executado na GPU, gerou resultados satisfatórios quando comparados aos algoritmos implementados sequenciais. Esses resultados obtidos, nos mostram o poder e eficiência do paralelismo ao gerar soluções rápidas e de forma eficiente. Os resultados demonstram que é possível vislumbrar a execução dessa solução em Smart Cities para milhares de veículos, ao propor algoritmos de baixo custo para a definição de rotas otimizadas no ambito do algoritmo A-Star e o Dijkstra, podendo dessa forma, substituir toda uma infraestrutura de supercomputadores por GPUs.
Abstract: The significant increase in the population in large urban centers has created some problems analyzed and addressed in this work as urban mobility and its efficiency, due to the increasing need for fast and low cost mobility. In this scenario, Smart Cities offers a variety of solutions that enable you to reduce all problems, generating diverse and sustainable solutions. From this, a vehicle traffic simulation was performed in regions of the city of Aracaju in the state of Sergipe - Brazil and in Manhattan in the state of New York - USA, in the traffic simulation tool SUMO (Simulation of Urban MObility), where the classic in the literature A-Star algorithm was executed, implemented in parallel, using NVIDIA’s CUDA and a Graphics Processing Unit (GPU) which in turn performs complex calculations efficiently when compared to the CPU (Central Process Unit) and also implemented sequentially, which executes one instruction at a time on the CPU. The use of GPU itself, as well as being advantageous due to its power to perform floating point operation, is also a viable device solution for its low financial cost, thus avoiding a supercomputer infrastructure to accomplish such a task. Thus, the algorithm implemented in parallel in this work and executed in the GPU, generated satisfactory results when compared to the implemented sequential algorithms. These results show us the power and efficiency of parallelism to generate fast and efficient solutions. The results show that it is possible to envision the implementation of this solution in Smart Cities for thousands of vehicles, by proposing low cost algorithms for the definition of optimized routes within the scope of the A-Star algorithm and Dijkstra, thus replacing an entire infrastructure. of supercomputers by GPUs.
Keywords: Ciência da computação
Ensino de ciência da computação
Graphics Processing Unit (GPU)
CUDA
Simulation of Urban MObility (SUMO)
Smart cites
Rotas
Veículos
Central Process Unit (CPU)
Subject CNPQ: CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAO
Language: por
Institution: Universidade Federal de Sergipe
Department: DCOMP - Departamento de Computação – Ciência da Computação – São Cristóvão - Presencial
Citation: Costa, Jackson Tavares da. Implementação e avaliação de algoritmos sequencial e paralelo para descoberta de rotas ótimas para veículos. São Cristóvão, SE, 2019. Monografia (graduação em Ciência da Computação) – Curso de Ciência da Computação, Departamento de Computação, Centro de Ciências Exatas e Tecnologia, Universidade Federal de Sergipe, São Cristóvão, 2019
URI: http://ri.ufs.br/jspui/handle/riufs/12494
Appears in Collections:Computação

Files in This Item:
File Description SizeFormat 
Jackson_Tavares_Costa.pdf1,87 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.