Paralelismo

É a abstração/ideia/o conceito de executar várias operações ao mesmo tempo.

Computação Paralela

O termo designado a área que estuda a aplicação do paralelismo em abstrações computacionais.

Programação Paralela

Fork-Join

É o pattern mais simples. Uma main thread dispara (fork) várias worker threads e ao final de cada thread elas sincronizam de volta para (join) para a main thread. O tempo de execução em paralelo fica limitado pelo maior tempo de execução dentre as workers threads.

Map

É a implementação paralela do map do paradigma de programação funcional. Ou seja, de forma paralela, aplicar uma mesma função pura (chamada de função kernel) em cada um dos elementos de uma coleção. Cada thread pode ficar responsável por aplicar uma função em um elemento.

Exemplos: parallel for (OpenMP) ou map nativo de LPs.

Function<Integer, Integer> kernel = x -> x * x;

List<Integer> quadrados = Arrays.asList(1, 2, 3, 4, 5).parallelStream()
								 .map(x -> x * x)
	                             .collect(Collectors.toList());

System.out.println(quadrados); // [1, 4, 9, 16, 25]

Podemos dizer que o Map é uma abstração alto nível implementado por Fork-join por "debaixo dos panos". Com o Map não é preciso se preocupar em criar threads (fork), gerenciar a divisão dos dados ou sincronizar os resultados (join). Apenas fornece a coleção e a função, chama a API map e a biblioteca cuida do resto.

Reduce

É a implementação paralela do reduce do paradigma de programação funcional. Ou seja, de forma paralela, reduzir/agregar elementos para um único valor. Para o resultado ser determinístico, a função reduce deve ser obrigatoriamente associativa (Ex: $(a \cdot b) \cdot c=a \cdot (b \cdot c)$, a ordem do agrupamento não importa). Além disso, é desejável que essa função seja comutativa (Ex: $a \cdot b = b \cdot a$, a ordem dos operandos não importa) para execução mais eficiente (runtime consegue reordenar os operandos e distribuir melhor a carga de trabalho).

Cada thread pode ficar responsável por aplicar uma função em dois elemento.

Stencil

É uma generalização do Map, onde a função acessar não somente um único elemento da coleção, mas também seus vizinhos. Normalmente, o array de entrada é uma matriz (2D, uma imagem por exemplo). Defini-se uma janela (Ex: $3 \times 3$, 8-neighbors) com um elemento centro do stencil e para cada $I[i][j]$ a janela "desliza". Como não há dependências de dados entre a aplicação da função para cada $I[i][j]$ threads podem executar a aplicação da função stencil de forma paralela.

Muito comum na área de processamento de imagem, blur.

Scan

Ou prefix sum, à primeira vista parece impossível de se paralelizar (parece ser inerentemente sequencial).

Referências

• YT - Explicação Rede TOR - Dark web