Detalhes bibliográficos
Ano de defesa: |
2012 |
Autor(a) principal: |
Pessoa, Tiago Carneiro |
Orientador(a): |
Não Informado pela instituição |
Banca de defesa: |
Não Informado pela instituição |
Tipo de documento: |
Dissertação
|
Tipo de acesso: |
Acesso aberto |
Idioma: |
por |
Instituição de defesa: |
Universidade Estadual do Ceará
|
Programa de Pós-Graduação: |
Não Informado pela instituição
|
Departamento: |
Não Informado pela instituição
|
País: |
Não Informado pela instituição
|
Palavras-chave em Português: |
|
Link de acesso: |
https://siduece.uece.br/siduece/trabalhoAcademicoPublico.jsf?id=72340
|
Resumo: |
<div style=""><font face="Arial, Verdana"><span style="font-size: 13.3333px;">É chamada computação heterogênea a utilização de diversas arquiteturas computacionais </span></font><span style="font-size: 13.3333px; font-family: Arial, Verdana;">para processar diferentes regiões de um mesmo código, a fim de maximizar a performance </span><span style="font-size: 13.3333px; font-family: Arial, Verdana;">do mesmo. A computação heterogênea está intimamente ligada à computação de alto desempenho,</span></div><div style=""><font face="Arial, Verdana"><span style="font-size: 13.3333px;">e o seu surgimento deu-se em um momento onde os computadores paralelos, que possuíam </span></font><span style="font-size: 13.3333px; font-family: Arial, Verdana;">apenas um tipo de execução, não estavam mais suprindo as necessidades computacionais de </span><span style="font-size: 13.3333px; font-family: Arial, Verdana;">aplicações cada vez mais heterogêneas e computacionalmente intensivas. O emprego de unidades</span></div><div style=""><font face="Arial, Verdana"><span style="font-size: 13.3333px;">de processamento gráfico para cálculos de propósito geral, a fim de acelerar rotinas computacionalmente </span></font><span style="font-size: 13.3333px; font-family: Arial, Verdana;">intensivas, tem sido a arquitetura heterogênea que mais vem se destacando no </span><span style="font-size: 13.3333px; font-family: Arial, Verdana;">área da computação de alto desempenho. Este trabalho apresenta uma nova abordagem GPGPU</span></div><div style=""><font face="Arial, Verdana"><span style="font-size: 13.3333px;">para algoritmos DFS-B&B, independente de problema, que envolve conceitos tão elementares, </span></font><span style="font-size: 13.3333px; font-family: Arial, Verdana;">tal que qualquer algoritmo B&B baseado na estratégia de busca em profundidade pode ser facilmente </span><span style="font-size: 13.3333px; font-family: Arial, Verdana;">adaptado para ser processado por unidades de processamento gráfico. A estratégia</span></div><div style=""><font face="Arial, Verdana"><span style="font-size: 13.3333px;">massivamente paralela consiste em, inicialmente, realizar B&B sequencialmente até determinada </span></font><span style="font-size: 13.3333px; font-family: Arial, Verdana;">profundidade no espaço de soluções, e salvar essa trajetória como nós em um conjunto </span><span style="font-size: 13.3333px; font-family: Arial, Verdana;">ativo. Cada nó desse conjunto ativo será uma thread processada pela unidade de processamento</span></div><div style=""><font face="Arial, Verdana"><span style="font-size: 13.3333px;">gráfico, na forma de DFS-B&B concorrentes. Duas implementações do esquema proposto, </span></font><span style="font-size: 13.3333px; font-family: Arial, Verdana;">para a resolução exata do PCVA, foram concebidas: um DFS-B&B massivamente paralelo e </span><span style="font-size: 13.3333px; font-family: Arial, Verdana;">uma versão massivamente paralela do Método Jurema, batizada de Juremal. Comparamos as</span></div><div style=""><font face="Arial, Verdana"><span style="font-size: 13.3333px;">implementações massivamente paralelas com versões seriais e multicore do Jurema e da DFS, </span></font><span style="font-size: 13.3333px; font-family: Arial, Verdana;">em dois cenários: enumeração explícita e implícita (B&B). Os resultados evidenciaram a superioridade </span><span style="font-size: 13.3333px; font-family: Arial, Verdana;">dos algoritmos massivamente paralelos, principalmente na enumeração explícita. Na</span></div><div style=""><font face="Arial, Verdana"><span style="font-size: 13.3333px;">enumeração implícita os algoritmos massivamente paralelos saíram-se largamente superiores </span></font><span style="font-size: 13.3333px; font-family: Arial, Verdana;">em instâncias onde o limite inferior inicial obtido é distante do ótimo. Também foi evidenciado </span><span style="font-size: 13.3333px; font-family: Arial, Verdana;">nos testes que o método Jurema mantém sua superioridade, em relação ao DFS, em ambientes</span></div><div style=""><font face="Arial, Verdana"><span style="font-size: 13.3333px;">massivamente paralelos. Mas, diferentemente do método Jurema serial, o Juremal saiu-se, </span></font><span style="font-size: 13.3333px; font-family: Arial, Verdana;">apenas, ligeiramente superior ao DFS-B&B massivamente paralelo. </span><span style="font-size: 13.3333px; font-family: Arial, Verdana;">Palavras-chave: Branch-and-bound. GPGPU. caixeiro viajante assimétrico. CUDA.</span></div> |