Paralelizaςão do Algoritmo Harmony Search Utilizando Unidade de Processamento Gráfico

Abstract

O algoritmo Harmony Search (HS) é uma metaheurística baseada em conceitos musicais, sendo inspirada na observação de que o objetivo de um músico é a busca por uma harmonia perfeita. Este trabalho propõe uma abordagem paralela para o algoritmo HS utilizando a arquitetura de programação paralela CUDA (Compute Unified Device Architecture) em uma Unidade de Processamento Gráfico (Graphic Processing Units - GPU). O algoritmo HS foi modificado de modo a permitir que processos implicitamente paralelos inerentes ao algoritmo pudessem ser implementados na arquitetura paralela, mais especificamente, o improviso de novas harmonias e a geração dos valores iniciais na memória harmônica. Duas abordagens de paralelização foram implementadas: primeiro transferindo apenas a função de avaliação para a GPU; e segundo, transferindo todos os passos do algoritmo para a GPU. A última abordagem evita o overhead devido às transferências entre as memórias. Experimentos foram realizados com o algoritmo HS sendo executado tanto em GPU quanto em CPU, para a otimização de várias funções de benchmark. Os resultados mostram que o tempo de execução do algoritmo HS utilizando GPU é significativamente menor quando comparado com os tempos de execução em CPU, ambos com a mesma qualidade de soluções. Observou-se que a influência do número de variáveis sobre o tempo de execução é menos significativa na GPU do que na CPU. Também foi observado que, quanto maior a complexidade dos cálculos envolvidos no processamento, maior é o speed-up proporcionado pelo uso da GPU.