Roubo de trabalho - Work stealing

Na computação paralela , o roubo de trabalho é uma estratégia de agendamento para programas de computador multithread . Ele resolve o problema de execução de uma computação multithread dinamicamente , que pode "gerar" novos threads de execução, em um computador multithread estaticamente , com um número fixo de processadores (ou núcleos ). Ele faz isso de forma eficiente em termos de tempo de execução, uso de memória e comunicação entre processadores.

Em um agendador de roubo de trabalho, cada processador em um sistema de computador tem uma fila de itens de trabalho (tarefas computacionais, threads) para executar. Cada item de trabalho consiste em uma série de instruções, a serem executadas sequencialmente, mas no curso de sua execução, um item de trabalho também pode gerar novos itens de trabalho que podem ser executados em paralelo com seu outro trabalho. Esses novos itens são inicialmente colocados na fila do processador que está executando o item de trabalho. Quando um processador fica sem trabalho, ele olha as filas dos outros processadores e "rouba" seus itens de trabalho. Na verdade, o roubo de trabalho distribui o trabalho de agendamento pelos processadores ociosos e, desde que todos os processadores tenham trabalho a fazer, não ocorre sobrecarga de agendamento.

O roubo de trabalho contrasta com o compartilhamento de trabalho , outra abordagem de agendamento popular para multithreading dinâmico, em que cada item de trabalho é agendado em um processador quando é gerado. Em comparação com essa abordagem, o roubo de trabalho reduz a quantidade de migração de processos entre os processadores, porque essa migração não ocorre quando todos os processadores têm trabalho a fazer.

A ideia de roubo de trabalho remonta à implementação da linguagem de programação Multilisp e ao trabalho em linguagens de programação funcional paralela na década de 1980. Ele é empregado no agendador para a linguagem de programação Cilk , o Java fork / join framework, a .NET Task Parallel Library e o Rust Tokio runtime .

Modelo de execução

O roubo de trabalho é projetado para um modelo "estrito" de junção de bifurcação de computação paralela, o que significa que uma computação pode ser vista como um gráfico acíclico direcionado com uma única fonte (início da computação) e um único coletor (fim da computação). Cada nó neste gráfico representa uma bifurcação ou uma junção . Os garfos produzem vários cálculos logicamente paralelos , chamados de "threads" ou "strands". As bordas representam computação serial.

Como exemplo, considere o seguinte programa trivial de junção de bifurcação na sintaxe semelhante ao Cilk :

function f(a, b):
    c ← fork g(a)
    d ← h(b)
    join
    return c + d

function g(a):
    return a × 2

function h(a):
    b ← fork g(a)
    c ← a + 1
    join
    return b + c

A chamada de função f (1, 2) dá origem ao seguinte gráfico de cálculo:

No gráfico, quando duas arestas deixam um nó, os cálculos representados pelos rótulos das arestas são logicamente paralelos: eles podem ser executados em paralelo ou sequencialmente. O cálculo só pode prosseguir após um nó de junção quando os cálculos representados por suas arestas de entrada estiverem completos. O trabalho de um escalonador, agora, é atribuir os cálculos (arestas) aos processadores de uma forma que faça todo o cálculo ser executado na ordem correta (conforme restrito pelos nós de junção), de preferência o mais rápido possível.

Algoritmo

A versão aleatória do algoritmo de roubo de trabalho apresentado por Blumofe e Leiserson mantém vários threads de execução e os programa para os processadores. Cada um dos processadores tem uma fila dupla (deque) de threads. Chame as extremidades do deque de "superior" e "inferior". ${\ displaystyle P}$

Cada processador que possui um thread atual para executar, executa as instruções no thread uma por uma, até encontrar uma instrução que causa um dos quatro comportamentos "especiais":

Uma instrução de spawn faz com que um novo encadeamento seja criado. O encadeamento atual é colocado na parte inferior do deque e o processador começa a executar o novo encadeamento.
Uma instrução de travamento é aquela que interrompe temporariamente a execução de seu thread. O processador tira um thread da parte inferior de seu deque e começa a executar esse thread. Se o seu deque estiver vazio, ele começa a roubar, explicado a seguir.
Uma instrução pode fazer com que um thread morra . O comportamento, neste caso, é o mesmo de uma instrução que fica paralisada.
Uma instrução pode habilitar outro encadeamento. O outro encadeamento é empurrado para a parte inferior do deque, mas o processador continua a execução de seu encadeamento atual.

Inicialmente, um cálculo consiste em um único thread e é atribuído a algum processador, enquanto os outros processadores começam ociosos. Qualquer processador que ficar ocioso inicia o processo real de roubo de trabalho, o que significa o seguinte:

ele escolhe outro processador uniformemente ao acaso;
se o deque do outro processador não estiver vazio, ele retira o thread superior do deque e começa a executá-lo;
mais, repita.

Roubo de crianças vs. roubo de continuação

Observe que, na regra para spawn , Blumofe e Leiserson sugerem que a thread "pai" execute sua nova thread, como se estivesse realizando uma chamada de função (no programa tipo C f (x); g (y);, a função a chamada para f é concluída antes que a chamada para g seja realizada). Isso é chamado de "roubo de continuação", porque a continuação da função pode ser roubada enquanto o thread gerado é executado e é o algoritmo de escalonamento usado no Cilk Plus . Não é a única maneira de implementar o roubo de trabalho; a estratégia alternativa é chamada de "roubo de crianças" e é mais fácil de implementar como uma biblioteca , sem suporte do compilador . O roubo de crianças é usado por Threading Building Blocks , Task Parallel Library da Microsoft e OpenMP , embora o último dê ao programador o controle sobre qual estratégia é usada.

Eficiência

Várias variantes de roubo de trabalho foram propostas. A variante aleatória devido a Blumofe e Leiserson executa uma computação paralela no tempo esperado nos processadores; aqui, está o trabalho , ou a quantidade de tempo necessária para executar a computação em um computador serial, e é o intervalo , a quantidade de tempo necessária em uma máquina infinitamente paralela. Isso significa que, na expectativa , o tempo necessário é no máximo um fator constante vezes o mínimo teórico. No entanto, o tempo de execução (em particular, o número de roubos executados) pode ser exponencial no pior caso. Uma variante localizada, na qual um processador tenta roubar de volta seu próprio trabalho sempre que está livre, também foi analisada teórica e praticamente. ${\ displaystyle T_ {1} / P + O (T _ {\ infty})}$ ${\ displaystyle P}$ ${\ displaystyle T_ {1}}$ ${\ displaystyle T _ {\ infty}}$ ${\ displaystyle T _ {\ infty}}$

Uso do espaço

Um cálculo programado pela versão Blumofe-Leiserson de roubo de trabalho usa o espaço da pilha , se fosse o uso da pilha do mesmo cálculo em um único processador, ajustando-se à definição anterior dos próprios autores de eficiência de espaço. Este limite requer roubo de continuação; em um planejador de roubo de criança, ele não se sustenta, como pode ser visto no exemplo a seguir: ${\ displaystyle O (S_ {1} P)}$ ${\ displaystyle S_ {1}}$

for i = 0 to n:
    fork f(i)
join

Em uma implementação de roubo de filhos, todas as chamadas "bifurcadas" para f são colocadas em uma fila de trabalho que, portanto, cresce para o tamanho n , que pode ser arbitrariamente grande.

Variante de multiprogramação

O algoritmo de roubo de trabalho, conforme descrito anteriormente, e sua análise, pressupõem um ambiente de computação onde uma computação é agendada em um conjunto de processadores dedicados. Em um ambiente de multiprogramação (multitarefa), o algoritmo deve ser modificado para agendar tarefas de computação em um pool de threads de trabalho , que por sua vez são agendadas nos processadores reais por um agendador do sistema operacional . A qualquer momento, o planejador do SO atribuirá ao processo de roubo de trabalho algum número $P A \leq P$ dos processadores $P$ no computador, porque outros processos podem estar usando os processadores restantes. Nessa configuração, o roubo de trabalho com um pool de threads de trabalho $P$ tem o problema de que os workers agindo como ladrões podem causar livelock : eles podem bloquear a execução de workers que na verdade gerariam tarefas úteis.

Uma variante do roubo de trabalho foi concebida para esta situação, que executa um cálculo no tempo esperado

{\ displaystyle O \ left ({\ frac {T_ {1}} {P _ {\ mathrm {avg}}}} + {\ frac {T _ {\ infty} P} {P _ {\ mathrm {avg}}}} \direito),}

onde $P avg$ é o número médio de processadores alocados para a computação pelo agendador do sistema operacional durante o tempo de execução da computação. O agendador de trabalho de multiprogramação difere da versão tradicional em dois aspectos:

Suas filas não bloqueiam . Enquanto em processadores dedicados, o acesso para as filas podem ser sincronizados usando bloqueios , isso não é aconselhável em um ambiente de multiprogramação desde que o sistema operacional pode antecipar o segmento de trabalho segurando o bloqueio, bloqueando o progresso de quaisquer outros trabalhadores que tentam acessar a mesma fila .
Antes de cada tentativa de roubar trabalho, um thread de trabalho chama uma chamada de sistema " yield " que produz o processador no qual está programado para o sistema operacional, a fim de evitar fome .

As tentativas de melhorar o ladrão de trabalho de multiprogramação se concentraram em problemas de localidade de cache e estruturas de dados de fila aprimoradas.

Alternativas

Vários algoritmos de agendamento para cálculos multithread dinamicamente competem com o roubo de trabalho. Além da abordagem tradicional de compartilhamento de trabalho, existe um escalonador chamado de profundidade paralela (PDF) que melhora os limites de espaço do roubo de trabalho, além de oferecer melhor desempenho em algumas situações em que os núcleos de um multiprocessador de chip compartilham um cache.

Languages

In other projects