Estratégias paralelas inteligentes para o método Branch-And-Bound aplicadas ao problema do caixeiro viajante assimétrico

• Ano de defesa: 2012
• Autor(a) principal: Pessoa, Tiago Carneiro
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Estadual do Ceará
• Palavras-chave em Português: Caixeiro viajante; Ciência da computação; Estrategias Paralelas Inteligentes
• Link de acesso: https://siduece.uece.br/siduece/trabalhoAcademicoPublico.jsf?id=72340

<div style=""><font face="Arial, Verdana"><span style="font-size: 13.3333px;">É chamada computação heterogênea a utilização de diversas arquiteturas computacionais&nbsp;</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&nbsp;</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&nbsp;</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&nbsp;</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&nbsp;</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&nbsp;</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&amp;B, independente de problema, que envolve conceitos tão elementares,&nbsp;</span></font><span style="font-size: 13.3333px; font-family: Arial, Verdana;">tal que qualquer algoritmo B&amp;B baseado na estratégia de busca em profundidade pode ser facilmente&nbsp;</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&amp;B sequencialmente até determinada&nbsp;</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&nbsp;</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&amp;B concorrentes. Duas implementações do esquema proposto,&nbsp;</span></font><span style="font-size: 13.3333px; font-family: Arial, Verdana;">para a resolução exata do PCVA, foram concebidas: um DFS-B&amp;B massivamente paralelo e&nbsp;</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,&nbsp;</span></font><span style="font-size: 13.3333px; font-family: Arial, Verdana;">em dois cenários: enumeração explícita e implícita (B&amp;B). Os resultados evidenciaram a superioridade&nbsp;</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&nbsp;</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&nbsp;</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,&nbsp;</span></font><span style="font-size: 13.3333px; font-family: Arial, Verdana;">apenas, ligeiramente superior ao DFS-B&amp;B massivamente paralelo.&nbsp;</span><span style="font-size: 13.3333px; font-family: Arial, Verdana;">Palavras-chave: Branch-and-bound. GPGPU. caixeiro viajante assimétrico. CUDA.</span></div>