Modelo Fork-Join

Uma ilustração do paradigma fork-join, no qual três regiões do programa permitem a execução paralela dos blocos coloridos. A execução sequencial é exibida na parte superior, enquanto o a execução fork-join equivalente é exibida em baixo.

Na computação paralela, o modelo fork-join (bifurcar-juntar) é uma forma de configurar e executar programas em paralelo de tal forma que a execução das tarefas concorrentes "juntam-se" (join) em um ponto subsequente, onde a execução passa a ser sequencial. As seções paralelas podem se bifurcar recursivamente até que uma determinada granularidade da tarefa seja atingida. Fork-join pode ser considerado como um padrão de projeto paralelo. Foi formulado já em 1963.

Ao realizar o aninhamento recursivo de cálculos com fork-join, obtém-se uma versão paralela do paradigma divisão e conquista, expresso pelo seguinte pseudocódigo genérico:

resolver(problema):
   se problema é pequeno o suficiente:
      resolver o problema diretamente (algoritmo sequencial)
  senão:
      para parte em subdividir(problema)
           fork subtarefa para resolver(parte)
      join todas as subtarefas gerado no laço anterior
      retornar resultados combinados

Exemplos

O merge sort do livro Algoritmos: teoria e prática é um algoritmo fork-join.

mergesort(A, inicio, fim):
 se inicio < fim:        // pelo menos um elemento de entrada
    meio = ⌊inicio + (fim - inicio) / 2⌋
    fork mergesort(A, inicio, meio) // processo (potencialmente) em paralelo com a tarefa principal
    mergesort(A, meio, fim) // a tarefa principal realiza segunda recursão
    join   merge(A, inicio, meio, fim)

A primeira chamada recursiva foi bifurcada, isso significa que sua execução por rodar de forma paralela (em uma thread separada) com a parte seguinte da função, até o comando join, que faz todas as threads sincronizarem. Enquanto o join pode parecer uma barreira, ele é diferente porque as threads continuarão trabalhando depois de uma barreira, enquanto depois de um join somente uma thread continua.

A segunda chamada recursiva não é uma bifurcação no pseudocódigo acima; isso é intencional, pois bifurcar tarefas pode ser custoso. Se ambas as chamadas recursivas foram configuradas como subtarefas, a tarefa principal não teria nenhum trabalho adicional para executar antes de ser bloqueada no join.

Implementações

Implementações do modelo fork-join tipicamente bifurcam as tarefas, fibers ou threads "leves" (lightweight threads), não em threads "pesadas" do nível do sistema operacional ou processos, e usam um um pool de threads para executar essas tarefas: a bifurcação primitiva permite que o programador determine o potencial paralelismo, que a implementação então mapeia na execução paralela real. A razão para esse design é que a criação de novas threads tende a resultar em muita sobrecarga.

As threads leves usadas na programação fork-join tipicamente irão possuir o seu próprio escalonador (normalmente, um work stealing) que as mapeia no pool de threads subjacente. Esse escalonador pode ser muito mais simples do que um escalonador de sistema operacional preventivo cheio de recursos: os escalonadores de threads para propósitos gerais precisam lidar com bloqueios por locks, mas, no paradigma fork-join, threads só bloqueiam no ponto de junção (join).

Fork-join é o principal modelo de execução paralela no framework OpenMP, embora implementações OpenMP podem ou não suportar o aninhamento de seções paralelas. É também suportado pela framework Java concurrency, o Task Parallel Library da .NET, e a Threading Building Blocks (TBB) da Intel. A linguagem de programação Cilk tem suporte em nível de linguagem para o modelo fork-join, na forma das palavras-chave spawn e sync , ou cilk_spawn e cilk_sync no Cilk Plus.

Veja também

• MapReduce

Ligações externas

• A Primer on Scheduling Fork–Join Parallelism with Work Stealing
• Merge Sort paralelo em Java (fork-join) (em português)