Loading...
Publication
Massively parallel GPU acceleration of population-based optimization metaheuristics: application to the solution large-scale systems of nonlinear equations
| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 26.98 MB | Adobe PDF |
Authors
Abstract(s)
High-dimensional problems, such as large-scale Systems of Nonlinear Equations, are
challenging due to their complexity and nonlinear solution spaces. Population-based
optimization metaheuristics, such as Particle Swarm Optimization and Gray Wolf
Optimizer, can offer effective approaches. However, their computational demands
often exceed the capacity of traditional methods, particularly when addressing these
problems at large scales.
To address these challenges, parallelization constitutes a promising strategy. Due
to the massive parallel processing capabilities, a Graphics Processing Unit (GPU)
is well-adapted to the acceleration of population-based metaheuristic optimization
algorithms. Thus, employing GPU parallelism can substantially reduce computational
time and enable the solution of larger and more complex problems that would be
impractical on conventional Central Processing Units (CPUs).
GPU-based parallelization of metaheuristic optimization algorithms faces several
challenges due to algorithmic diversity and heterogeneous hardware architectures.
Different metaheuristics exhibit distinct computational patterns, memory access
requirements, and degrees of inherent parallelism, which complicates efficient mapping
to GPU architectures. Moreover, variations in GPU hardware can substantially affect
performance, often requiring algorithm-specific adaptations and hardware-aware
optimizations to fully exploit GPU resources.
This research proposes GPU-based parallelization strategies for population-based
metaheuristic algorithms to enhance performance on large-scale, high-dimensional
optimization problems. It uses GPU parallelism to manage increasing problem sizes
while preserving convergence behavior and solution quality. A central goal is a
hardware-agnostic model that enables scalable acceleration across diverse computa tional environments, providing a general framework for GPU-based metaheuristic
acceleration applicable to various algorithmic paradigms and problem domains.
Experimental results indicate that GPU-accelerated metaheuristics using the
proposed framework substantially outperform their sequential counterparts, achieving
significant speedups. The framework scaled effectively across ten population-based
algorithms and ten benchmark problems of increasing dimensionality, utilizing five
GPU models, including both consumer-grade and professional-grade hardware. In
multi-GPU tests, the framework exhibited superlinear speedup in certain cases.
This study highlights the value of modular, reproducible frameworks for GPU based metaheuristics and provides a base for future research in high-dimensional,
computationally intensive optimization.
Os problemas de elevada dimensionalidade, como os Sistemas de Equações Não Lineares de larga escala, apresentam desafios significativos devido à sua complexidade e aos espaços de solução não lineares. Metaheurísticas populacionais de optimização, como Particle Swarm Optimization e Gray Wolf Optimizer, proporcionam abordagens eficazes, mas exigem mais capacidade computacional do que os métodos tradicionais, sobretudo quando aplicados a problemas de larga escala. Para enfrentar esses desafios, a paralelização é uma estratégia promissora. As Unidades de Processamento Gráfico (Graphics Processing Units (GPUs)), com elevado poder de processamento paralelo, são adequadas para acelerar metaheurísticas populacionais. O paralelismo em GPU pode reduzir significativamente o tempo computacional e permitir resolver problemas maiores e mais complexos, inviáveis em Unidades Centrais de Processamento (CPUs) convencionais. No entanto, a paralelização em GPU de algoritmos metaheurísticos enfrenta desafios devido à diversidade algorítmica e às arquitecturas de hardware heterogéneas. Diferentes metaheurísticas têm padrões computacionais, acesso à memória e níveis de paralelismo distintos, dificultando o mapeamento eficiente para GPUs. Além disso, variações no hardware podem afectar o desempenho, exigindo adaptações e optimizações específicas para explorar plenamente os recursos disponíveis. Esta investigação propõe estratégias de paralelização em GPU para algoritmos metaheurísticos populacionais, visando melhorar o desempenho em problemas de elevada dimensionalidade e grande escala. A abordagem aproveita o paralelismo da GPU para gerir o aumento do tamanho dos problemas, preservando simultaneamente o comportamento de convergência e a qualidade das soluções. Um dos objectivos centrais consiste na criação de um modelo independente do hardware, que permita aceleração escalável em diferentes ambientes computacionais, fornecendo um modelo geral para a aceleração de metaheurísticas baseadas em GPU aplicável a diferentes paradigmas algorítmicos e domínios de problemas. Os resultados experimentais demonstram que as metaheurísticas aceleradas por GPU, utilizando o modelo proposto, superam substancialmente as suas versões sequenciais, alcançando melhorias significativas na velocidade de processamento. O modelo mostrou escalabilidade eficaz em dez algoritmos baseados em populações e dez problemas de referência de dimensionalidade crescente, utilizando cinco modelos de GPU, abrangendo tanto hardware de consumo como profissional. Em testes realizados com múltiplas GPUs, o modelo exibiu aceleração superlinear em determinados casos. Este estudo evidencia a relevância de modelos modulares e reprodutíveis para metaheurísticas baseadas em GPU, estabelecendo uma base sólida para investigações futuras em optimização de elevada dimensionalidade e alto custo computacional.
Os problemas de elevada dimensionalidade, como os Sistemas de Equações Não Lineares de larga escala, apresentam desafios significativos devido à sua complexidade e aos espaços de solução não lineares. Metaheurísticas populacionais de optimização, como Particle Swarm Optimization e Gray Wolf Optimizer, proporcionam abordagens eficazes, mas exigem mais capacidade computacional do que os métodos tradicionais, sobretudo quando aplicados a problemas de larga escala. Para enfrentar esses desafios, a paralelização é uma estratégia promissora. As Unidades de Processamento Gráfico (Graphics Processing Units (GPUs)), com elevado poder de processamento paralelo, são adequadas para acelerar metaheurísticas populacionais. O paralelismo em GPU pode reduzir significativamente o tempo computacional e permitir resolver problemas maiores e mais complexos, inviáveis em Unidades Centrais de Processamento (CPUs) convencionais. No entanto, a paralelização em GPU de algoritmos metaheurísticos enfrenta desafios devido à diversidade algorítmica e às arquitecturas de hardware heterogéneas. Diferentes metaheurísticas têm padrões computacionais, acesso à memória e níveis de paralelismo distintos, dificultando o mapeamento eficiente para GPUs. Além disso, variações no hardware podem afectar o desempenho, exigindo adaptações e optimizações específicas para explorar plenamente os recursos disponíveis. Esta investigação propõe estratégias de paralelização em GPU para algoritmos metaheurísticos populacionais, visando melhorar o desempenho em problemas de elevada dimensionalidade e grande escala. A abordagem aproveita o paralelismo da GPU para gerir o aumento do tamanho dos problemas, preservando simultaneamente o comportamento de convergência e a qualidade das soluções. Um dos objectivos centrais consiste na criação de um modelo independente do hardware, que permita aceleração escalável em diferentes ambientes computacionais, fornecendo um modelo geral para a aceleração de metaheurísticas baseadas em GPU aplicável a diferentes paradigmas algorítmicos e domínios de problemas. Os resultados experimentais demonstram que as metaheurísticas aceleradas por GPU, utilizando o modelo proposto, superam substancialmente as suas versões sequenciais, alcançando melhorias significativas na velocidade de processamento. O modelo mostrou escalabilidade eficaz em dez algoritmos baseados em populações e dez problemas de referência de dimensionalidade crescente, utilizando cinco modelos de GPU, abrangendo tanto hardware de consumo como profissional. Em testes realizados com múltiplas GPUs, o modelo exibiu aceleração superlinear em determinados casos. Este estudo evidencia a relevância de modelos modulares e reprodutíveis para metaheurísticas baseadas em GPU, estabelecendo uma base sólida para investigações futuras em optimização de elevada dimensionalidade e alto custo computacional.
Description
Keywords
Computational intelligence Metaheuristic optimization Parallel GPU algorithms GPU computing Nonlinear equation systems Inteligência computacional Otimização meta-heurística Algoritmos paralelos em GPU Computação em GPU Sistemas de equações não lineares Informatics Engineering specialization: Artificial Intelligence . Faculdade de Ciências Exatas e da Engenharia