Inteligência na Web e Big Data
Published:
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.