Este repositório contém a implementação e a análise comparativa de desempenho entre os algoritmos de busca em grafos de grande escala, Busca em Largura (BFS) e Busca em Profundidade (DFS), em suas versões sequenciais e paralelas. O projeto utiliza o framework nativo Java Fork/Join para explorar a escalabilidade e a eficiência do processamento em arquiteturas multicore.
O processamento de estruturas de dados irregulares, como grafos massivos (redes sociais, rotas, etc.), apresenta um grande desafio para o balanceamento de carga de CPU. Este projeto resolve esse gargalo aplicando o padrão Divisão e Conquista aliado ao algoritmo de Work-Stealing, garantindo que nenhuma thread fique ociosa durante a travessia do grafo.
- Java Fork/Join Framework: Orquestração do pool de threads através de
RecursiveTaskeRecursiveActionpara divisão recursiva do trabalho. - Controle de Granularidade Vertical (VGC): Implementação de um ponto de corte (Cutoff) inteligente para decidir matematicamente quando uma tarefa deve ser paralelizada ou executada sequencialmente, reduzindo o overhead de criação de threads.
- Fallback Iterativo na DFS: Criação de um limite máximo de profundidade para evitar o esgotamento da pilha de execução da JVM (
StackOverflowError), alternando dinamicamente para uma busca iterativa local em ramos muito profundos. - Concorrência Segura na Memória: Uso de
ConcurrentHashMappara rastreamento thread-safe dos vértices já visitados, eliminando condições de corrida sem bloquear toda a estrutura. - Simulação Real de Gargalo de Memória: O sistema aplica cargas reais de acesso à memória (evitando o mascaramento de resultados por operações sintéticas de CPU), forçando o algoritmo a lidar com o autêntico custo de Cache Misses inerente aos grafos.
O projeto foi validado utilizando grafos sintéticos massivos gerados inteiramente in-memory. O desempenho foi medido em um processador Intel Core i5-13600KF (14 núcleos físicos, 20 threads) com 16 GB de RAM.
As análises baseiam-se em duas métricas principais:
-
Speedup:
$S = \frac{T_s}{T_p}$ -
Eficiência Paralela:
$E = \frac{S}{P}$
| Algoritmo | Tempo Sequencial | Tempo Paralelo | Speedup ( |
Eficiência ( |
|---|---|---|---|---|
| BFS | 339 ms | 135 ms | 2.51x | 12.56% |
| DFS | 370 ms | 218 ms | 1.70x | 8.49% |
A Busca em Largura obteve maior facilidade de paralelização devido à sua natureza de distribuição por fronteiras (níveis). A Busca em Profundidade apresentou um ganho ligeiramente menor devido à intervenção do limite de profundidade (Cutoff) necessário para proteger a memória da máquina.