Submitted by Erika Demachki (erikademachki@gmail.com) on 2017-01-06T16:59:11Z
No. of bitstreams: 2
Tese - Walid Abdala Rfaei Jradi - 2016.pdf: 5339936 bytes, checksum: 0a0a6bdc4791ee31c229b5175ae3af03 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-01-09T09:29:25Z (GMT) No. of bitstreams: 2
Tese - Walid Abdala Rfaei Jradi - 2016.pdf: 5339936 bytes, checksum: 0a0a6bdc4791ee31c229b5175ae3af03 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-01-09T09:29:25Z (GMT). No. of bitstreams: 2
Tese - Walid Abdala Rfaei Jradi - 2016.pdf: 5339936 bytes, checksum: 0a0a6bdc4791ee31c229b5175ae3af03 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2016-11-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / 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. / O presente trabalho estuda e propõe algoritmos e implementações paralelas baseadas em
GPU para o problema de alocação macroscópica de tráfego urbano em redes de grande porte,
promovendo uma investigação aprofundada de cada sub-problema que deve ser resolvido de
forma eficiente durante o processo de atribuição de tráfego. Entre as principais contribuições
deste trabalho, estão: 1) o primeiro algoritmo baseado em GPU para a enumeração de ciclos
sem corda; 2) um novo algoritmo de caminho mínimo paralelo que tira vantagem de algumas
propriedades comuns das redes de tráfego urbano; Um refinamento na implementação de
redução paralela proposta por um dos líderes no mercado de GPU, o que resultou em uma
aceleração de 2,8x em relação à sua versão original; 3) e, finalmente, um algoritmo paralelo
para o problema de alocação macroscópica de tráfego, 39x mais rápido do que a abordagem
equivalente sequencial quando aplicado a redes de larga escala.
O objetivo principal desta tese é de contribuir para a expansão do software PET-Gyn,
propondo estruturas de dados de GPU eficientes e algoritmos paralelos para uma resolução
mais rápida de dois problemas bem conhecidos na literatura: O Problema de Alocação de
Tráfego e a Enumeração de Ciclos sem Corda. Quando aplicados a conjuntos de entrada
difíceis, os experimentos realizados mostraram uma clara vantagem dos algoritmos paralelos
sobre suas versões sequenciais.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/6695 |
| Date | 30 November 2016 |
| Creators | Jradi, Walid Abdala Rfaei |
| Contributors | Nascimento, Hugo Alexandre Dantas do, Martins, Wellington Santos, Camponogara, Eduardo, Clua, Esteban Walter Gonzalez, Mongelli , Henrique, Costa, Fábio Moreira |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, -7712266734633644768, 3671711205811204509, 2075167498588264571 |
Page generated in 0.1441 seconds