Avaliação do desempenho de Multilevel Bucket Queues na determinação de caminhos mínimos em arquiteturas modernas - Fernandes, Ana Carla; Miranda, Ricardo; Freitas, Rosiane de (Anais do Workshop em Desempenho de Sistemas Computacionais e de Comunicação (WPerformance), 2026)
Filas compartimentadas (buckets) multinível exploram restrições de pesos inteiros para superar filas de prioridades de propósito geral no Algoritmo de Dijkstra. Entretanto, as razões em nível de hardware para essa vantagem ainda são pouco compreendidas. Neste trabalho são comparadas as filas de buckets de 1 a 6 níveis com heaps binário e de Fibonacci, em doze instâncias de redes viárias do Benchmark DIMACS. A variante de 1 nível com operação decrease-key alcança até 2× de aceleração em relação ao heap binário e 3,2× em relação ao heap de Fibonacci, o que se explica por um menor número de instruções de desvio (branch instructions) e por uma melhor utilização do cache. Para pesos máximos elevados (C ≥ 10 6 ), variantes com menos níveis apresentam degradação devido à manipulação da memória, sendo a variante de 5 níveis a que se observou oferecer melhor escalabilidade.