É chamada computação heterogênea a utilização de diversas arquiteturas computacionais para processar diferentes regiões de um mesmo código, a fim de maximizar a performance do mesmo. A computação heterogênea está intimamente ligada à computação de alto desempenho,
e o seu surgimento deu-se em um momento onde os computadores paralelos, que possuíam apenas um tipo de execução, não estavam mais suprindo as necessidades computacionais de aplicações cada vez mais heterogêneas e computacionalmente intensivas. O emprego de unidades
de processamento gráfico para cálculos de propósito geral, a fim de acelerar rotinas computacionalmente intensivas, tem sido a arquitetura heterogênea que mais vem se destacando no área da computação de alto desempenho. Este trabalho apresenta uma nova abordagem GPGPU
para algoritmos DFS-B&B, independente de problema, que envolve conceitos tão elementares, tal que qualquer algoritmo B&B baseado na estratégia de busca em profundidade pode ser facilmente adaptado para ser processado por unidades de processamento gráfico. A estratégia
massivamente paralela consiste em, inicialmente, realizar B&B sequencialmente até determinada profundidade no espaço de soluções, e salvar essa trajetória como nós em um conjunto ativo. Cada nó desse conjunto ativo será uma thread processada pela unidade de processamento
gráfico, na forma de DFS-B&B concorrentes. Duas implementações do esquema proposto, para a resolução exata do PCVA, foram concebidas: um DFS-B&B massivamente paralelo e uma versão massivamente paralela do Método Jurema, batizada de Juremal. Comparamos as
implementações massivamente paralelas com versões seriais e multicore do Jurema e da DFS, em dois cenários: enumeração explícita e implícita (B&B). Os resultados evidenciaram a superioridade dos algoritmos massivamente paralelos, principalmente na enumeração explícita. Na
enumeração implícita os algoritmos massivamente paralelos saíram-se largamente superiores em instâncias onde o limite inferior inicial obtido é distante do ótimo. Também foi evidenciado nos testes que o método Jurema mantém sua superioridade, em relação ao DFS, em ambientes
massivamente paralelos. Mas, diferentemente do método Jurema serial, o Juremal saiu-se, apenas, ligeiramente superior ao DFS-B&B massivamente paralelo. Palavras-chave: Branch-and-bound. GPGPU. caixeiro viajante assimétrico. CUDA.
