aco-selection-parallel

Paralelização do Algoritmo de Otimização de Colônia de Formigas (ACO) com CUDA e OpenMP para seleção de instâncias em larga escala.

Disciplina: Computação de Alto Desempenho — UFG 2026
Baseline: Magalhães et al. (PUC Minas)

Equipe

Nome	Matrícula
Wagner Victor Alves de Menezes	202403929
Daniel Rios Borges	202403900
Victor Gabriel Ribeiro Jácome	202403926
Raphael Alves de Lima Soares	202403922

Estrutura do Projeto

├── data/                  # Datasets (9 do baseline + CDC Diabetes)
├── src/
│   ├── sequential/        # C++ sequencial (adaptado do baseline)
│   ├── cuda/              # C++ + CUDA (paralelismo GPU)
│   └── openmp/            # C++ + OpenMP (paralelismo CPU)
├── scripts/               # Benchmark, profiling (Perf), plots
├── results/               # Saídas experimentais
├── docs/                  # Artigo final e apresentação
└── Makefile               # Build unificado

Versões

Versão	Tecnologia	Status
Sequencial	C++	🔲
GPU	C++ + CUDA	🔲
CPU Paralela	C++ + OpenMP	🔲

Datasets

Categoria	Datasets	Instâncias
Pequenos (≤700)	Heart, Haberman, Cirrhosis	299 – 418
Médios (≤1500)	Diabetes, Tic-tac-toe, Yeast	767 – 1.484
Grandes (>1500)	Vaccine, Employee, Brain Stroke	3.152 – 4.981
Larga escala	CDC Diabetes	253.680

Como compilar

make sequential   # compila versão sequencial   -> build/aco_seq
make cuda         # compila versão CUDA          -> build/aco_cuda
make openmp       # compila versão OpenMP        -> build/aco_omp
make all          # compila as 3 versões
make benchmark    # compila e executa as versões disponíveis
make clean        # remove build/

Execução via Containers (Sem Sudo/Root)

Se você estiver rodando em uma máquina compartilhada ou servidor com GPU onde não possui permissões de administrador (sudo), você pode executar as implementações via Docker (se seu usuário fizer parte do grupo docker) ou via Singularity/Apptainer.

O script auxiliar ./run_container.sh simplifica este processo.

Opção A: Docker

1. Construir Imagem (o dataset CDC Diabetes é incorporado automaticamente):

   ./run_container.sh build-docker

2. Executar ACO:
   • Sequencial: ./run_container.sh run-seq (usa subamostragem por padrão)
   • OpenMP (ex: 16 threads): ./run_container.sh run-omp 16
   • CUDA (RTX 4090): ./run_container.sh run-cuda
   • Benchmark Completo: ./run_container.sh run-benchmark (executa e salva os relatórios na pasta ./results/ da sua máquina local)

Opção B: Singularity / Apptainer (Comum em HPC)

1. Construir arquivo de imagem (.sif):

   ./run_container.sh build-singularity

2. Executar ACO:
   • Sequencial: singularity exec aco.sif ./build/aco_seq data/cdc/cdc_diabetes.csv Diabetes_binary --ants 64 --iter 10
   • OpenMP: OMP_NUM_THREADS=16 singularity exec aco.sif ./build/aco_omp data/cdc/cdc_diabetes.csv Diabetes_binary --ants 64 --iter 10
   • CUDA (RTX 4090): singularity exec --nv aco.sif ./build/aco_cuda data/cdc/cdc_diabetes.csv Diabetes_binary --ants 64 --iter 10

CUDA e OpenMP são épicos separados. Enquanto src/cuda/ e src/openmp/ estiverem vazios (ou nvcc não existir), esses targets são pulados sem erro.

Resultados

Redução de Instâncias (%)

Instâncias Absolutas Antes × Depois

Speedup CUDA e OpenMP vs Sequencial

Relatório completo: results/EP04_CUDA_benchmark.md

Referências

• Magalhães, J.M.O. et al. Avaliação de Desempenho e Escalabilidade do ACO em C++ e Python. PUC Minas, 2024.
• CDC Diabetes Health Indicators — UCI ML Repository