Inteligência na Web e Big Data

Paralelismo em Haskell

Uma das grandes vantagens das linguagens puramente funcionais é a falta de efeitos colaterais da função. Isso garante que uma função não irá alterar nenhum estado global do sistema.

Como as funções são determinísticas, a execução de uma versão paralela sempre retorna o mesmo que a versão sequencial, portanto sendo mais fácil de ser debugada. Em muitos casos, a paralelização pode ser feita de maneira automatica apenas com anotações para que o compilador saiba o que paralelizar.

Em primeiro momento vamos relembrar o conceito de avaliação preguiçosa, quando fazemos:

x = 5 + 10

O programa não avalia a expressão imediatamente, apenas armazena a sequência de cálculos que deve realizar. Uma vez que o valor de x é requisitado:

print x

Seu valor é computado e, a partir daquele instante, o valor final é armazenado em x. No GHCi podemos verificar isso com o comando :sprint:

Prelude> let x = 5 + 10
Prelude> :sprint x
x = _

Prelude> x
3
Prelude> :sprint x
x = 3

Digamos que temos:

Prelude> let x = 1 + 1
Prelude> y = x * 3
Prelude> :sprint x
x = _
Prelude> :sprint y
y = _

Obviamente, nem x e nem y estão computados. Reparem que para computar y, necessariamente precisamos também computar x. Nesse caso:

Prelude> y
6
Prelude> :sprint x
x = 2

Para forçar o cálculo de uma variável podemos utilizar a função seq:

seq x () -- avalia x e retorna ()

O que acontece se forçarmos a avaliação de:

Prelude> let l = map (+1) [1..10] :: [Int]
Prelude> :sprint l
l = _
Prelude> seq l ()
Prelude> :sprint l
l = _ : _

A função seq apenas avaliou que l é uma lista, mas não seu conteúdo.

Prelude> length l
Prelude> :sprint l
l = [_,_,_,_,_,_,_,_,_,_]
Prelude> sum l
Prelude> :sprint l
l = [2,3,4,5,6,7,8,9,10,11]

Percebemos que o Haskell avalia apenas quando realmente necessário.

composições delas são seguras de serem executadas em paralelo. Vamos tomar como exemplo o cálculo de Fib(n):

fib 0 = 0
fib 1 = 1
fib 2 = 1
fib n = (fib n - 1) + (fib n - 2)

Note que o cálculo de (fib n - 1) independe do cálculo de (fib n - 2) e, portanto, essas operações podem ser executadas em paralelo. No Haskell podemos indicar ao compilador as partes paralelizáveis e deixar que ele cuide dos detalhes. Para isso utilizamos o comando par da biblioteca Control.Parallel:

import Control.Parallel

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = n1 `par` (n1 + n2) 
  where
    n1 = fib (n - 1)
    n2 = fib (n - 2)

main = do
    print (fib 36)

Para instalar a biblioteca digite:

cabal install parallel

Esse comandos indica que fn1 pode ser enviado a uma outra thread do sistema operacional. Compilando e executando com:

ghc -o parN1 parN1.hs -threaded -eventlog -rtsopts
./parN1 +RTS -N1 -s -ls -M2g

Temos que o tempo de execução total foi (esse número vai variar dependendo da máquina):

Total   time    2.585s  (  2.588s elapsed)

Alterando a opção N1 para N2, indicamos que desejamos utilizar duas threads do processador, e temos:

Total   time    2.766s  (  1.388s elapsed)

O valor entre parênteses é o tempo real de processamento, enquanto o outro é a soma das threads. Percebemos que embora não tenha caido pela metade, o tempo real reduziu bastante em relação ao uso de uma thread apenas. Alterando o programa para:

import Control.Parallel

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = n1 `par` (n2 + n1) 
  where
    n1 = fib (n - 1)
    n2 = fib (n - 2)

main = do
    print (fib 36)

e realizando o mesmo procedimento, percebemos que agora no obtemos ganho no tempo de execução. Isso ocorre pois o operador + nessa versão do compilador avalia primeiro o elemento da direita. Então enquanto uma thread executa o cálculo de n1, a outra thread irá efetuar o mesmo cálculo!

Para evitar isso podemos utilizar o comando pseq que indica o que deve ser calculado enquanto aguarda o retorno da thread:

import Control.Parallel

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = n1 `par` n2 `pseq` (n2 + n1) 
  where
    n1 = fib (n - 1)
    n2 = fib (n - 2)

main = do
    print (fib 36)

Em maiores detalhes a `par` b significa: crie um spark para calcular a e retorne b. Um spark é uma possibilidade de criar uma thread, se o programa julgar necessário ou tiver oportunidade para tal. De tal forma estaríamos tentados em fazer:

fib n = fn1 `par` fn1 + fn2

Porém, a ordem de execução da função soma não está especificado na linguagem, uma possível execução seria:

  • Cria uma thread para calcular fn1
  • Na thread principal calcula fn1 + fn2, computando primeiro fn2
  • Ao terminar o cálculo de fn2, caso a thread de fn1 tenha terminado, utilize a resposta para calcular o resultado da soma.

ou:

  • Cria uma thread para calcular fn1
  • Na thread principal calcula fn1 + fn2, computando primeiro fn1
  • Ao terminar o cálculo de fn1, calcule fn2 e efetue a soma, desperdiçando o cálculo de fn1 em sua thread específica.

A função pseq indica para esperar que se tenha o resultado das threads ANTES de efetuar o cálculo requisitado, ou seja, a `par` b `pseq` a+b fala para calcular a em uma thread, retornar b na principal e, somente após isso tudo terminar, calcule a+b.

Lembre-se: no Haskell uma vez que uma expresso é avaliada, seu resultado é armazenado em memória. Ou seja, caso uma spark já tenha calculado fib 5, ele reaproveitará o resultado se esse valor for requisitado novamente. Isso é possível graças ao determinismo das funções.

Estratégias de paralelismo

Uma outra forma de anotar os pontos próprios para paralelismo é utilizando as estratégias. Uma estratégia é definida por:

 type Strategy a = a -> Eval a

Ou seja, estratégia é uma função que pega um valor de um tipo qualquer e envolve no tipo Eval. A ideia geral é que a estratégia pegue uma estrutura de dados e envolva em uma estratégia básica par e/ou pseqe devolva essa mesma estrutura envolvida com o sinal Eval para ser avaliado.

Por exemplo, vamos definir a estratégia parPair que avalia uma tupla de dois elementos em paralelo:

 import Control.Parallel.Strategies
 
parPair :: Strategy (a,b)
parPair (a,b) = do
    a' <- rpar a
    b' <- rpar b
    return (a',b')

Repare que agora utilizamos rpar que faz parte da biblioteca Strategies ao invés de par. Essa função indica que devemos criar um spark para calcular a, outro para b e, então, retornar a tupla avaliada. Como exemplo, vamos calcular em paralelo o valor de fib 35 e fib 36:

 runEval (parPair (fib 35, fib 36))

Para tornar o código mais legível, foi criada a função using:

using :: a -> Strategy a -> a
x `using` s = runEval (s x)

Com isso podemos escrever:

(fib 35, fib 36) `using` parPair

Vale lembrar que se o resultado de fib 35 fosse um tipo mais complexo como lista ou tupla, a estratégia rpar não avaliaria a expressão. Para resolver esse problema podemos utilizar rdeepseq que força a avaliação para a forma Normal da expressão.

Da mesma forma que parPair temos tambm a estratégia parList que age sobre listas e necessita de uma estratégia secundária para aplicar em cada elemento:

[2*i | i <- [1..100000]] `using` parList rseq

irá calcular cada elemento da lista em uma thread. Alternativamente se cada elemento da lista for outra lista podemos substituir rseq por rdeepseq. Uma outra estratégia é :

[2*i | i <- [1..100000]] `using` parListChunk 500 rseq

em que o compilador distribui pedaços de tamanho 500 para cada spark.

Exercício 01: Aplique estratégias de paralelismo para o jogo da Zebra. Mensure o tempo ganho pela paralelizaço.

Exercício 02: Crie uma lista booleana indicando se os números de 1 a 10000 são primos. Paralelize a criação dessa lista.