Application of GPU Computing to Some Urban Traffic Problems

Detalhes bibliográficos
Ano de defesa: 2016
Autor(a) principal: Jradi, Walid Abdala Rfaei lattes
Orientador(a): Nascimento, Hugo Alexandre Dantas do lattes
Banca de defesa: Camponogara, Eduardo, Clua, Esteban Walter Gonzalez, Mongelli , Henrique, Costa, Fábio Moreira
Tipo de documento: Tese
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Universidade Federal de Goiás
Programa de Pós-Graduação: Programa de Pós-graduação em Ciência da Computação (INF)
Departamento: Instituto de Informática - INF (RG)
País: Brasil
Palavras-chave em Português:
GPU
Palavras-chave em Inglês:
Área do conhecimento CNPq:
Link de acesso: http://repositorio.bc.ufg.br/tede/handle/tede/6695
Resumo: The present work studies and proposes GPU-based parallel algorithms and implementations for the problem of macroscopic assignment of urban traffic on large-scale networks, promoting an in-depth investigation on each sub-problem that must be efficiently solved during the traffic assignment process. Among the main contributions of this work, there are: 1) the first GPU-based algorithm for the enumeration of chordless cycles; 2) a new parallel GPU-based shortest path algorithm that takes advantage of some common properties of urban traffic networks; a refinement in the parallel reduction implementation proposed by one of the leaders in the GPU market, which resulted in a 2.8x speedup relative to its original version; and finally, 3) a parallel algorithm for the macroscopic traffic assignment problem, 39x faster than the equivalent sequential approach when applied to large scale networks. The main goal of this thesis is to contribute to the extension of the PET-Gyn software, proposing efficient GPU data structures and parallel algorithms for a faster resolution of two well known problems in the literature: The Traffic Assignment Problem (TAP) and the Enumeration of Chordless Cycles. When applied to difficult input sets, the performed experiments showed a clear advantage of the parallel algorithms over their sequential versions.