Application of GPU Computing to Some Urban Traffic Problems

• Ano de defesa: 2016
• Autor(a) principal: Jradi, Walid Abdala Rfaei
• Orientador(a): Nascimento, Hugo Alexandre Dantas do
• 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: Tráfego urbano; Alocação macroscópica de tráfego; Computação paralela; GPU
• Palavras-chave em Inglês: Urban traffic; Macroscopic traffic assignment; Parallel computing
• Área do conhecimento CNPq: CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://repositorio.bc.ufg.br/tede/handle/tede/6695

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.