A Lock-Free Work-Stealing Algorithm for Bulk Operations

Este artigo apresenta uma nova fila de roubo de trabalho sem bloqueio otimizada para um framework mestre-trabalhador em solvers de programação inteira mista, que suporta operações em lote nativas e demonstra desempenho superior em latência e escalabilidade em comparação com implementações existentes como a do C++ Taskflow.

O essencial

Imagine que você tem uma equipe de 100 trabalhadores (os "núcleos" do seu computador) tentando resolver um quebra-cabeça gigante. O problema é que alguns trabalhadores ficam superocupados, enquanto outros ficam parados, sem nada para fazer. Para resolver isso, usamos uma técnica chamada "Roubo de Trabalho" (Work-Stealing).

A ideia é simples: se um trabalhador está sem tarefas, ele vai até a pilha de tarefas de um colega ocupado e "rouba" um pouco do trabalho para si.

No entanto, a maioria dos sistemas de computador hoje usa uma versão genérica e um pouco lenta desse processo. É como se, para pegar uma tarefa, o trabalhador precisasse abrir uma porta trancada, esperar a chave, pegar uma única peça do quebra-cabeça, fechar a porta e repetir isso 100 vezes. Isso gera muito atrito e demora.

Este artigo apresenta uma nova e mais inteligente maneira de fazer esse roubo de trabalho, feita especificamente para um tipo de problema matemático complexo (otimização de decisões).

Aqui está a explicação dos principais pontos, usando analogias do dia a dia:

1. O Problema: A "Fila de Supermercado" Lenta

Imagine que o seu computador tem uma fila de tarefas.

• O Dono da Fila (Owner): É quem coloca as tarefas na fila.
• O Ladrão (Stealer): É quem pega as tarefas quando está sem trabalho.

Nos sistemas antigos (como os usados em bibliotecas comuns de programação), se o "Dono" quisesse colocar 100 tarefas de uma vez, ele tinha que abrir a porta da fila, colocar uma, fechar, abrir de novo, colocar a segunda... e assim por diante. Se o "Ladrão" quisesse pegar 50 tarefas, ele tinha que fazer o mesmo processo de abrir e fechar a porta 50 vezes.
Resultado: Muito tempo perdido apenas abrindo e fechando portas (sincronização), em vez de trabalhar.

2. A Solução: O "Caminhão de Mudanças"

Os autores criaram uma nova fila (uma "fila de roubo de trabalho") feita sob medida para o problema deles. Pense nela como um caminhão de mudanças em vez de uma fila de supermercado.

• Operações em Lote (Bulk Operations):

  • Antes: O Dono colocava 100 caixas uma por uma.
  • Agora: O Dono joga todas as 100 caixas de uma vez no caminhão. É como se ele dissesse: "Aqui está o lote todo!".
  • O Ladrão: Em vez de pegar uma caixa por vez, ele pega metade do caminhão de uma só vez.
  • Vantagem: Menos tempo abrindo portas, muito mais tempo movendo caixas.

• Crescimento Infinito:

  • Algumas filas têm um tamanho máximo (como uma caixa de sapatos). Se encher, você precisa comprar uma caixa maior e transferir tudo (o que é lento).
  • A nova fila é como um tubo de mangueira infinito. Ela cresce conforme necessário sem precisar ser cortada ou transferida. Isso é perfeito para problemas onde você não sabe quantas tarefas vão surgir.

• O "Ladrão Único":

  • Em muitos sistemas, vários ladrões podem tentar roubar da mesma fila ao mesmo tempo, causando brigas e confusão (concorrência).
  • Neste sistema, há apenas um gerente (Master) que decide quem rouba e de quem. É como se houvesse apenas um policial distribuindo o trabalho. Isso elimina a briga entre ladrões, tornando o processo muito mais rápido e seguro, sem precisar de "trancas" pesadas.

3. Os Resultados: Velocidade e Estabilidade

Os autores testaram essa nova fila comparando com as filas tradicionais (usadas em ferramentas populares como C++ Taskflow).

• Colocar tarefas (Push):
  • Sistemas antigos: Quanto mais tarefas você tenta colocar de uma vez, mais lento fica (a fila "engasga").
  • Sistema novo: A velocidade é constante. Seja 1 tarefa ou 1.000, o tempo é quase o mesmo. É como se o caminhão de mudanças fosse tão eficiente que não importa o tamanho da carga.
• Roubar tarefas (Steal):
  • Sistemas antigos: Se você tentar roubar 60% da fila, demora muito.
  • Sistema novo: O tempo de roubo permanece estável, não importa se você rouba 10% ou 60%.
  • Otimização: Eles descobriram que, se o "Dono" não estiver mexendo na fila no momento do roubo, o "Ladrão" pode pular uma etapa de verificação e roubar 3 vezes mais rápido.

4. Por que isso importa?

Imagine que você está resolvendo um problema de logística (como rotas de caminhões) ou um quebra-cabeça complexo.

• Em problemas simples, onde as tarefas são todas iguais e rápidas, a diferença não é tão grande.
• Mas, no mundo real, algumas tarefas são fáceis e outras são pesadíssimas. Quando as tarefas são irregulares, a "velocidade de abrir e fechar a porta" (sincronização) dos sistemas antigos se torna um gargalo enorme.

A nova fila dos autores foi desenhada para eliminar esse gargalo. Ela permite que o computador gaste a maior parte do tempo resolvendo o problema, e não apenas organizando a fila de espera.

Resumo em uma frase

Os autores criaram um sistema de distribuição de tarefas que troca a "caixa de correio" lenta e individual por um "caminhão de carga" rápido e em lote, permitindo que computadores resolvam problemas matemáticos complexos muito mais rápido, especialmente quando o trabalho vem em grandes quantidades de uma só vez.

Resumo técnico

Aqui está um resumo técnico detalhado do artigo "A Lock-Free Work-Stealing Algorithm for Bulk Operations", apresentado em português:

Título: Um Algoritmo de Work-Stealing sem Bloqueio para Operações em Lote (Bulk Operations)

1. Problema e Motivação

O work-stealing (roubo de trabalho) é uma técnica fundamental para balancear cargas de trabalho paralelas irregulares, sendo amplamente adotada em sistemas de tempo de execução modernos (como Cilk, Intel TBB e Go). No entanto, os algoritmos existentes são projetados para propósitos gerais e assumem cenários com múltiplos "ladrões" (stealers) concorrentes e operações de tarefa única.

Os autores identificam que essas soluções genéricas introduzem sobrecargas desnecessárias em ambientes especializados, especificamente na paralelização de um solver de programação inteira mista (MIP) baseado em Diagramas de Decisão (DDs). As limitações dos algoritmos atuais para este cenário incluem:

• Ineficiência em Operações em Lote: A geração de novos nós (tarefas) ocorre em grandes lotes (centenas de nós), mas os algoritmos existentes tratam cada nó individualmente, gerando alta latência e contenção.
• Crescimento Limitado: Muitas filas têm tamanhos fixos ou exigem redimensionamento dinâmico custoso (cópias de elementos), o que é inadequado para problemas onde o número de nós pode crescer exponencialmente.
• Sincronização Excessiva: Algoritmos genéricos suportam múltiplos ladrões concorrentes, exigindo sincronização complexa, embora o modelo do solver tenha um único "mestre" responsável pelo balanceamento de carga.

2. Metodologia e Proposta

Os autores propõem uma nova fila de work-stealing sem bloqueio (lock-free) otimizada para um modelo Mestre-Trabalhador com as seguintes características:

• Estrutura de Dados: Implementada como uma lista encadeada simples (singly linked list) com dois variáveis atômicas: head (cabeça) e size (tamanho).
• Modelo de Concorrência Restrito: Assume-se no máximo um proprietário (o trabalhador que gera tarefas) e um ladrão (o mestre que redistribui tarefas). Isso permite simplificar drasticamente a sincronização.
• Operações Nativas em Lote (Bulk Operations):
  • Push (Empurrar): O proprietário insere uma lista inteira de nós na cabeça da fila de forma atômica, atualizando o ponteiro head e o contador size uma única vez para o lote, em vez de iterar por cada nó.
  • Pop (Remover): O proprietário remove um nó da cabeça.
  • Steal (Roubar): O mestre rouba uma proporção (ex: 50%) dos nós do final da fila em uma única operação. O algoritmo calcula um ponto de corte, percorre a lista até lá, corta a conexão e retorna o subconjunto roubado como uma nova lista.
• Crescimento Ilimitado: A fila cresce dinamicamente sem limites de capacidade pré-definidos, evitando a necessidade de redimensionamento de arrays.
• Garantias de Corretude: O algoritmo é lock-free (sem bloqueio) e linearizável. Os autores fornecem um esboço de prova identificando os pontos de linearização para cada operação, garantindo progresso mesmo sob concorrência restrita.

3. Contribuições Principais

1. Novo Algoritmo Especializado: Introdução de uma fila de work-stealing projetada especificamente para o modelo Mestre-Trabalhador, suportando operações nativas em lote e crescimento ilimitado.
2. Análise de Corretude: Demonstração conceitual de que o algoritmo preserva a segurança e garante progresso lock-free sob o modelo de concorrência de um único ladrão.
3. Otimização de Latência: Exploração de uma variante otimizada da operação de steal que evita a travessia completa da lista se o proprietário não atualizou a fila durante o roubo, reduzindo a latência em até 3x em cenários comuns.
4. Validação Experimental: Benchmarks extensivos comparando a implementação com as filas "Bounded" e "Unbounded" da biblioteca C++ Taskflow.

4. Resultados Experimentais

Os testes foram realizados em um hardware com 64 núcleos (128 threads) e compararam a latência das operações de push, pop e steal:

• Operação Push (Lote):
  • A fila proposta (LF Queue) manteve uma latência constante (abaixo de 500 ns) independentemente do tamanho do lote (de 1 a 1024 nós).
  • As filas do Taskflow mostraram um aumento drástico na latência (chegando a ~5000 ns para 1024 nós) devido à repetição de operações por nó e sobrecarga de redimensionamento.
• Operação Steal (Roubo):
  • Para proporções pequenas de roubo (<30%), o Taskflow foi ligeiramente mais rápido.
  • À medida que a proporção de nós roubados aumentava (até 60%), a latência do Taskflow cresceu linearmente (acima de 112 µs), enquanto a LF Queue manteve uma latência estável (~40 µs).
  • A versão otimizada do steal reduziu a latência em até 3x em proporções maiores, ao evitar a segunda travessia da lista.
• Operação Pop: Todas as implementações tiveram desempenho comparável (~213-216 ns).
• Escalabilidade: Em uma carga de trabalho pseudo-realista baseada na exploração de um grafo acíclico direcionado (DAG) com até 300 milhões de nós, todos os algoritmos escalaram linearmente. No entanto, os autores argumentam que em cargas de trabalho reais do solver (com tempos de processamento de nós altamente irregulares), a vantagem da baixa sobrecarga de agendamento da nova fila seria ainda mais pronunciada.

5. Significado e Conclusão

O trabalho demonstra que adaptar algoritmos de work-stealing às características específicas de um domínio (neste caso, solvers de otimização baseados em diagramas de decisão) pode superar significativamente as soluções de propósito geral.

• Eficiência: A capacidade de realizar operações em lote nativas elimina a sobrecarga de sincronização por tarefa individual.
• Simplicidade: A restrição a um único ladrão permite simplificar a sincronização, eliminando a necessidade de mecanismos complexos de contenção múltipla.
• Aplicabilidade: Embora o algoritmo não seja projetado para substituir filas genéricas em todos os cenários (especialmente aqueles com múltiplos ladrões concorrentes e tarefas finas), ele oferece uma solução superior para sistemas de balanceamento de carga centralizados que lidam com grandes volumes de tarefas geradas em lotes.

Em suma, o artigo valida que a especialização de estruturas de dados concorrentes para padrões de carga de trabalho específicos é uma estratégia viável e eficaz para melhorar o desempenho de solvers de otimização paralela de grande escala.