| 0 |
ALLEF KRISTIAN TAVARES ROCHA |
|
| 1 |
ANTONIO DUARTE CANTANHEDE NETO |
|
| 3 |
BRUNA ISHIDA |
Em várias linguagens funcionais é possível encontrar a Avaliação preguiçosa, a qual tem como objetivo
de retornar um resultado, porém, realizará na "medida do possível", ou seja, podendo suspender uma
expressão ou atrasá-la até que a resposta esteja disponível. Além disso, uma vez que a resposta estiver
calculada, ele é memoizado (o qual funciona como um cache), se for necessária novamente, a resposta já
estará disponível.
Temos também os Streams, os quais são similares as listas, porém, a avaliação de cada item é realizada
"perigosamente". São listas normalmente de valor de comprimento desconhecido a priori, ou tomado como
valor infinito. Alguns exemplos de implementação são: lista com todos os números primos e sequência de
Fibonacci
Há a possibilidade de criação de paralelismo dentro do Haskell, sendo possível utilizando do Eval Monad.
Com o auxílio da biblioteca Control.Parallel.Strategies, são disponibilizadas funçõees para a realização
de paralelismo. Segue alguns exemplos:
- função rpar indica se um argumento em específico pode ser executado em paralelo
- função rseq notifica que um argumento deve ser aguardado para ser retornado o resultado
- função runEval executa a expressão e retorna os dados da resposta
rpar e rseq muito parecido com os métodos síncronos e assíncronos.
Em métodos, há a possibilidade de separar a parte sequencial da parte paralela, fazendo com que seja
possível adicionar paralelismo em um método já sequencial sem quebrar o mesmo.
Existe um programa chamado Threadscope, o qual tem como objetivo realizar debugs de performances paralelas
em Haskell.
Sparks são criados para realizar o paralelismo no Haskell, sendo o mesmo uma "promessa" de algo que pode ser
ou que será computado em paralelo. Esses sparks são adicionados a uma pool que gerencia e alimenta os processos
em paralelo |
| 4 |
BRUNA MIRELLI XAVIER GONCALVES |
12.1 Laziness
Avaliação preguiçosa: Uma variável guarda apenas a referência à expressão enquanto não houver
necessidade desta ser avaliada.
- sprint no Ghci: mostra o estado da variável> avaliada ou não (thunk, cujo estado é _).
- Para forçar a avaliação: função seq (Recebe dois parâmetros, avaliando o primeiro como efeito colateral,
e retornando o segundo. Avalia apenas o primeiro nível da expressão, forma normal fraca - Weak Head Normal Form).
- Forçar a execução completa para sua forma normal: force e
12.2 Primo Folgado
Streams: Em Haskell as listas podem ser infinitas, mas seus elementos são avaliados de modo preguiçoso.
Uso da lista de primos gerada para fazer a fatoração dos próximos candidatos a primos, gerando novos primos
conforme necessário.
“Memoização” dos resultados, reaproveitados quando há chamadas para nova avaliação da expressão.
12.3 Fibonacci
Criação recursiva da lista da sequência de Fibonacci utilizando ela mesma para sua geração graças a avaliação preguiçosa.
13.1 Eval Monad
Seja um tipo de dado Eval, um monad de Eval e as funções:
>runEval: para rodar em paralelo e devolver o “a” avaliado em WHNF.
A seguir, ambas devem receber um thunk, e devolver uma expressão ainda não avaliada:
rpar: começa a execução da expressão, devolve o controle.
rseq: espera a expressão ser avaliada antes de devolver o controle.
>rpar-rpar: não aguarda o fim da computação para liberar a execução.
>rpar-rseq: aguarda o fim seq para liberar.
>rpar-rpar-rseq-rseq: runEval aguarda o fim de todas as threads para liberar.
13.2 Estratégias
type Strategies a = a -> Eval equivalente a rpar e rseq, permite o uso da estratégia de paralelismo para tipos de dados,
e os valores podem ser descritos em tuplas.
13.3 Threadscope
Com este programa podemos ver o workload dos cores ao executar o programa com paralelismo.
Spark: promessa de uma computação paralela.
|
| 5 |
BRUNO STORER FRANCO MARTINS |
Essa semana aprendemos sobre avaliação preguiçosa,
que se trata de um padrão comum de avaliação entre linguagens
funcionais.
Como primeira caracerística da avaliação preguiçosa
é o fato de que uma expressão apenas terá seu
valor calculado no momento em que ela é necessária, ou
seja, seu cálculo é atrasado até o ponto que seja de fato
necessário. Por fim, quando calculado o resultado da expressão
é guardado em cache.
Durante as aulas através da função sprint
conseguimos monitorar a aplicação de avaliação preguiçosa.
Quando uma variavel é forçada a assumir
uma estrutura sem ter valores cálculados é o caso de
Weak Head Normal Form . Um exemplo está abaixo:
> z = (2, 3)
> :sprint z
z = _
> z `seq` ()
()
> :sprint z
z = (_,_)
Por último neste tópico, aprendemos sobre streams, que se tratam de listas
com avaliação preguiçosa implementada em cada célula. Em haskell
felizmente toda lista é implementada dessa forma.
Aprendemos também sobre paralelismo em haskell. No caso,
rpar indica que um argumento pode ser executado em paralelo
e rseq indica se um argumento deve ser avaliado e seu resultado deve ser aguardado
Por último, runEval executa e retorna o resultado das expressões
sendo paralelas ou não.
A biblioteca Control.Parallel.Strategies permite a abstração
de estratégias de paralelismo para tipos de dados, permitindo
que paralelismo possa ser adicionado em programas originalmente não paralelos
de forma mais simples.
|
| 2 |
CAIO HENRIQUE DOS SANTOS RIBEIRO |
|
| 11 |
GABRIEL ALBANO SANTOS |
Avaliação Preguiçosa
Em linguagens que utilizam avaliação preguiçosa, como o Haskell, ao colocarmos, por exemplo, o valor de uma expressão em uma variável, o valor dessa variável não será o valor da avaliação expressão, e sim a própria expressão. Ou seja, a expressão só será avaliada caso seja necessário, e no caso de não haver necessidade, temos apenas a referência à expressão nessa variável.
Podemos forçar a avaliação de uma expressão de algumas formas:
- Imprimindo a variável associada à expressão (com a função sprint)
- Quando precisamos de um valor que necessita desse outro valor, fazendo com que este seja calculado
- Utilizando a função seq :: a → b → b, que simplesmente devolve o segundo parâmetro passado, mas também avalia o primeiro. No entanto, o seq consegue avaliar apenas no primeiro nível. Ou seja, uma expressão z = 5 * 6 + 2 é avaliada, mas uma l = map (+1) [1..10] não é (Weak Head Form - WHF)
A existência da avaliação preguiçosa em Haskell permite a existência de Streams, que são similares a listas comuns, mas diferentemente destas, normalmente são infinitas ou de tamanho desconhecido. Utilizando streams, podemos implementar funções que fazem uso de listas infinitas para devolver uma lista finita, como uma lista de números primos ou a sequência de Fibonacci.
Paralelismo
Importando a biblioteca Control.Parallel.Strategies, temos em mãos algumas ferramentas que possibilitam executar tarefas em paralelo em Haskell.
data Eval = a ...
instance Monad Eval where ...
runEval :: Eval a -> a
rpar :: a -> Eval a
rseq :: a -> Eval a
- A função runEval retorna um valor a que está dentro do Monad Eval.
- A função rpar retorna um Eval a dado uma expressão do tipo a que pode ser executada em paralelo. Ou seja, a expressão não é avaliada no exato momento em que Eval a é criado, e sim apenas quando runEval for rodado e forçar a avaliação dessa expressão. Dessa forma, o controle é devolvido ao usuário logo que a execução da expressão é iniciado
- A função rseq retorna um Eval a, mas diferentemente de rpar, o resultado da expressão deve ser avaliado para então o controle ser devolvido.
- Tanto em rpar como em rseq, o parâmetro a deve ser um thunk
Ao compilar o projeto com stack build —profile, podemos executá-lo especificando a quantidade de processadores que irão atuar com o parâmetro -N{numero}.
stack exec paralelo -- +RTS -N2
Dentro dessa biblioteca também temos a definifição do tipo type Strategy a = a -> Eval a, o mesmo tipo de rpar e rseq. Então, uma função do tipo fparpar :: Eval (Integer, Integer) é igual à função parPair :: Strategy (a,b).
Para tornar o código mais legível, podemos então criar uma função chamada using, que tem como parâmetros a expressão e a estratégia de paralelismo a ser utilizada:
using' :: a -> Strategy a -> a
x `using'`s = runEval (s x)
(fib 41, fib 40) `using'` parPair
A biblioteca também inclui a estratégia ParList para aplicar parelismo em listas:
parMap :: (a -> b) -> [a] -> [b]
parMap f xs = map f xs `using`parList rseq
Spark é uma expressão que precisa ser avaliada e é colocada numa fila. Essa fila é consumida por threads, podendo ou não ser computada em paralelo. Numa lista, cada elemento gera um spark, que são inseridos num pool que alimenta os processos paralelos. É necessário cuidado ao se trabalhar com sparks, pois pode haver tanto um número muito pequeno deles (o que indica que o código pode ser mais otimazado), quanto um número muito alto (paralelismo em excesso, pode causar overflow). |
| 7 |
GABRIEL DE MELLO FIALI |
Avaliação preguiçosa
- Expressões são avaliadas somente quando necessário.
- São representadas por (_) e recebem o nome thunk
- Seu comportamento pode ser verificado com a função :sprint do ghci
- Após serem avaliados, os valores da expressão são perdidos para dar lugar ao seu resultado.
- Pode-se verificar quais são as expressões com a função seq.
- Efeito colateral força a avaliação do primeiro parâmetro recebido enquanto retorna o segundo.
- A avaliação só opera sobre 1 nível (weak head normal form). Para expressões que contam com várias camadas de avaliação há um retorno na forma (_ : _).
- Resultados não precisam necessariamente do cálculo de expressões para serem obtidos (exemplo: comprimento de lista formada por expressão).
- É possível forçar a avaliaçao com :force do ghci ou force, do pacote DeepSeq.
- Streams são listas cujos elementos são individualmente avaliados de forma preguiçosa.
- A pureza da linguagem se associa ao tempo de execução. Um comando executado anteriormente à avaliação é mais lento que um comando executado depois, com seus resultados já disponíveis a partir da segunda vez.
Eval Monad
- Utilizado para operações em paralelo.
- Conta com as funções runEval, rpar e rseq.
- runEval: retorna o valor de dentro um Eval com o uso de sparks, em WHNF.
- rpar e rsec: montam o container Eval com uma expressão não-avaliada. rpar inicia a verificação da expressão sem interrupções e rsec espera esse processo acabar. rsec pode limitar rpar dependendo de como são utilizados em conjunto.
- Permite se aproveitar do paralelismo para ganho de desempenho em alguns casos.
Strategy e using
- Define um modelo de avaliação para determinada função.
- Forma de tornar o código mais conciso e enxuto. Estratégias podem ser combinadas para contribuir com essa ideia.
- Listas já contam com estratégias definidas.
Spark
- Expressão em fila para ser avaliada em paralelo que conta com um ciclo de vida. |
| 9 |
GABRIEL MENDONÇA FARIAS |
Avaliação preguiçosa é a forma que as linguagens funcionais avaliam os códigos de programação. Isso é definido por manter o foco apenas nas tarefas necessárias, como calcular valores que serão usados e memoizar informações de cálculos já executados previamente. Para verificar o estado atual de uma variável, se utiliza a função sprint e se nota que, por exemplo, ao definir uma expressão igual a um valor x, a menos que o retorno de x seja necessário, este valor não será calculado, mesmo que a expressão de seu valor já faça parte do código. A função seq, pode retornar o valor já calculado da função, logo, se uma expressão é igual a x, seq x retornará a resposta do calculo desta função. E o comando force mostra a forma natural da função.
Streams são como listas, mas neste caso, cada célula da lista é apenas avaliada quando requerida pelo programa e como Haskell é uma linguagem funcional (possuindo avaliação preguiçosa), todas as listas funcionam desta maneira.
Para tarefas em paralelo em Haskell, é necessário à biblioteca Control.Parallel.Strategies, permitindo o uso de funções rpar, concedendo o funcionamento de um argumento em paralelo, rseq, que indica que um argumento precisa ser avaliado e o programa só segue depois desta avaliação e runEval que executa uma função e retorna o resultado. Por Monad Eval ser pura, pode ser usada em conjunto com funções do tipo IO. A estratégia rpar-rpar, é utilizada para liberar a execução de outras funções antes que outras sejam terminadas, rpar-rseq aguarda o fim da avaliação em seq para prosseguir com o programa, rpar-rpar-rseq-rseq aguarda o resultado de todos os threads para prosseguir. A biblioteca Control.Parallel.Strategies define estratégias de avaliação. Spark permite que algo seja computado (mas não necessariamente) em paralelo, o que permite a aplicação de funções paralelas em Haskell.
|
| 10 |
GABRIEL MURAKAMI ALVES |
No Haskell nós temos um tipo de avaliação de código que nos possibilita trabalhar
poupando gasto computacional e abstrações de conjuntos infinitos. Essa avaliação
se chama "preguiçosa", ou "lazy evaluation" em inglês. A vantagem desse tipo de
avaliação é somente executar certa expressão quando a mesma for necessária, ou seja,
se eu declaro que x é igual a 1 + 1, só terei a execução da soma, quando x for solicitado
em alguma outra parte do código, por exemplo com um y = x + 1. Além disso o Haskell
possui um esquema de memoize, que funciona como uma espécie de cache, então uma
vez que um valor é calculado ele não precisará ser computado novamente caso seja
chamado, fazendo uma economia computacional e ganho de perfomance para ações repetitivas.
Com a função `sprint` nós podemos verficar o estado de uma expressão no momento.
No exemplo dado acima, se declarmos x = 1 + 1, e rodarmos `:sprint x`, teremos o
resultado de x = _, ou seja, o mesmo ainda não foi avaliado. Agora se chamarmos
diretamente x ou indiretamente por exemplo por uma expressão y = x + 1, e em
seguida rodarmos novamente `:sprint x`, teremos a resposta de x = 2, já que x
precisou ser computado anteriormente.
Para trabalhar com paralelismo temos a biblioteca `Control.Parallel.Strategies`.
Dentro temos 3 principais funções e dois tipos. data Eval a, Monad Eval, runEval,
rpar e rseq. runEval executa uma expressão e retorna o resultado da mesma. rpar
serve para indicar o paralelismo. rseq serve para indicar que o argumento tem que
ser avaliado e então deve aguardar pelo resultado.
Dentro das Estratégias temos algumas definidas. rpar-rpar não aguarda o final da
execução para liberar outras tarefas. rpar-rseq irá aguardar a execução do segundo
argumento antes de liberar outros processos. rpar-rpar-rseq-rseq, dessa forma
o runEval irá aguardar todos os resultados disponíveis antes de retornar. |
| 13 |
GEORGE HARRISON ROCHA |
• Avaliação preguiçosa
- A avaliação preguiçosa (lazy evaluation) é uma estratégia de avaliação presente em várias linguagens funcionais, em que:
- A avaliação de uma expressão é "atrasada" até que seu resultado seja necessário;
- Uma vez que o a expressão é avaliada, seu resultado fica "memorizado", de modo que se se esse resultado for necessário novamente, ele será reutilizado e não recomputado;
- Em Haskell temos a função sprint que mostra o estado atual da variável;
- A função seq recebe dois parâmetros, avalia o primeiro e retorna o segundo;
- Avalia a expressão até a forma normal fraca na cabeça (Weak Head Normal Form - WHNF).
- Para forçar a execução completa para forma normal (Normal Form), podemos usar a função force;
- Streams:
- São listas em que a avaliação de cada elemento é feita de maneira preguiçosa;
- As listas em Haskell são assim;
- Em aula vimos aplicações muito interessantes da avaliação preguiçosa na geração de uma lista com todos os números primos e na geração de uma lista com a sequência de Fibonacci.
• Paralelismo
-Em Haskell temos, entre outras, as seguintes funções da biblioteca Control.Parallel.Strategies para criar paralelismo:
- rpar:
- Indica que o argumento pode ser executado em paralelo.
- rseq:
- Indica que o argumento deve ser avaliado e esperar pelo resultado.
- O tipo Strategies permite a abstração de estratégias de paralelismo.
- Threadscope:
- Sparks:
- É uma promessa de algo a ser computado e que pode ser computado em paralelo;
- Em Haskell o paralelismo é feito através de criação de sparks.
- Alguns sinais de problemas:
- Poucos sparks: pode ser paralelizado ainda mais;
- Muitos sparks: paralelizando demais.
|
| 14 |
GIANCARLO KAMI DELL ARINGA VIANA |
|
| 30 |
GIOVANNA NOGUEIRA |
Avaliação preguiçosa: - Muito comum em linguagens funcionais;
- Caracterizada por avaliar uma expressão somente quando seu resultado é necessário. Como esse resultado é memoizado, ele não será recalculado quando for necessário novamente;
- O comando "seq" força a avaliação da estrutura dos parâmetros passados, enquanto "force" avalia sua forma normal;
- Streams são listas onde cada célula é avaliada de forma preguiçosa, sendo a forma padrão das listas em haskell.
Paralelismo: - "rpar" indica que o parâmetro (que não pode já ter sido avaliado) pode ser executado em paralelo;
- "rseq" indica que o parâmetro deve ser avaliado e é necessário aguardar o resultado;
- "runEval" avalia uma expressão e retorna o resultado;
- O tipo "Strategies" permite a abstração de estratégias de paralelismo para tipos de dados;
- Em haskell, o paralelismo é feito a partir de sparks, uma promessa de algo a ser computado e que pode ser feito em paralelismo;
|
| 15 |
GUILHERME FERREIRA GALDINO |
Avaliação preguiçosa
Atrasa um avaliação de uma expressão até que seu resultado seja realmente necessário, gerando um thunk (expressão que não foi avaliada).
Quando calcula o resultado, este é memoizado (cached) para que não seja calculado novamente.
:sprint expr
Mostra o estado atual da avaliação da expressão
>x = 1+1
>:sprint x
x = _
Weak Head Normal Form (WHNF)
Avalia apenas um nivel a expressão, sendo na maioria das vezes sem chegar a forma normal dela.
Seq é uma função que executa o primeiro argumento até a WHNF e retorna o segundo.
>z = (2,3)
>z `seq` ()
()
>:sprint z
z = (_, _)
Streams
Lista comum porém com avaliação preguiçosa.
Pode-se representar listas infinitas.
fibos :: [Integer]
fibos = 0 : 1 : zipWith (+) fibos (tail fibos)
> take 10 fibos
[0,1,1,2,3,5,8,13,21,34]
Paralelismo
Control.Parallel.Strategies é um biblioteca que fornece funções para criar paralelismo.
data Eval a = ...
instance Monad Eval where ...
runEval :: Eval a -> a
rpar :: a -> Eval a -- executa em paralelo (obs: expressão ainda não avaliada)
rseq :: a -> Eval a -- espera o resulado
Obs (incluir no projeto):
Edite o arquivo paralelo.cabal e na linha build-depends acrescente as bibliotecas parallel, time.
Na linha anterior a hs-source-dirs acrescente a linha ghc-options: -threaded -rtsopts -with-rtsopts=-N -eventlog
Estretégias
Abstração de estratégias de paralelismo.
type Strategies a = a -> Eval a
-- :: (a,b) -> Eval (a,b)
parPair :: Strategy (a,b)
parPair (a,b) = do a' <- rpar a
b' <- rpar b
return (a',b')
Parametrizadas
evalPair :: Strategy a -> Strategy b -> Strategy (a,b)
evalPair sa sb (a,b) = do a' <- sa a
b' <- sb b
return (a',b')
Threadscope
Ferramenta gráfica para criar perfis de programas parelelos em Haskell.
Paralelismo em Haskell é feito através da criação de sparks.
Spark: promessa de algo a ser computado paralelamente.
Na execução paralela em uma lista, cada elemento gerado é um spark, que são inseridos em um pool (fila)
alimentando os processos paralelos.
Antes de criar o spark, se ele já foi avaliado é considerado um dud apontando para avaliação prévia.
Se o pool estiver cheio, não cria o spark retornando status de overflow.
Ao ser retirado do pool e já tiver sido avaliado retorna status fizzled.
Caso a expressão nunca foi requisitada, o garbage collector desloca sua memória.
Se nenhum dos casos acima ocorrer, um processo pega um spark do pool e é executado.
|
| 12 |
GaMendes |
Nessa semana vimos sobre avaliação preguiçosa e paralelismo.
A avaliação preguiçosa ou em inglês lazy evaluation é a estratégia de avaliação padrão de várias linguagens funcionais, dentre elas, a linguagem Haskell. Ela pode ser caracterizada em duas propriedades essenciais:
A avaliação de uma expressão é suspensa, ou atrasada (delayed) até que resultado seja necessário;
A partir do momento que o resultado tiver sido calculado ele é memoizado (en: memoized), i.e. armazenado em cache, de modo que se ele for preciso novamente ele será reutilizado e não re-computado.
Ainda no tópico de avaliação preguiçosa, vimos um pouco sobre streams, que são listas similares a listas comuns. Contudo a avaliação de cada célula é feita de maneira preguiçosa.Em Haskell todas as listas são assim, já em outras linguagens pode ser necessário fazer alguma ginástica para implementá-las.
Depois de vermos como funciona a avaliação preguiçosa em Haskell, passamos para o tópico de paralelismo, e vimos algumas estratégias de avaliação serem implementadas utilizando a biblioteca Control.Parallel.Strategies.
data Eval a = ...
instance Monad Eval where ...
runEval :: Eval a -> a
rpar :: a -> Eval a
rseq :: a -> Eval a
A função rpar indica que meu argumento pode ser executado em paralelo.
A função rseq diz meu argumento deve ser avaliado e o programa deve esperar pelo resultado.
Em ambos os casos a avaliação é para WHNF . Além disso, o argumento de rpar deve ser uma expressão ainda não avaliada, ou nada útil será feito.
Finalmente, a função runEval executa uma expressão (em paralelo ou não) e retorna o resultado dessa computação.
Note que a Monad Eval é pura e pode ser utilizada fora de funções com IO.
Depois de vermos algumas estratégias de avaliação demonstradas, fomos introduzidos ao threadscope, para ajudar a perceber melhor os recursos consumidos por cada uma das estratégias.
|
| 16 |
HENRIQUE AUGUSTO DE OLIVEIRA |
A ideia da Avaliação Preguiçosa é que, ao invés de colocar o valor a uma variável, é colocado a expressao que referencia uma determinada variável, por exemplo. Caso seja necessário utilizar aquele valor, é feito a avaliação da expressão.
Por exemplo, se for colocado x = 10 + 10, o valor não vai ser avaliado caso não seja pedido. Para avaliar um valor que, possivelmente, não tenha sido avaliado antes, é utilizado :sprint x. Se x já tiver sido avaliado, o valor é apresentado. Caso contrário, um underline é apresentada, pois x ainda é uma expressão. Thunk são expressões não avaliadas.
O uso da função seq faz com que uma determinada função seja avaliação até Weak Head Normal Form, ou seja, até a primeira camada de uma informação solicitada. Já o force, faz com com que toda a expressão seja avaliada.
Streams são fluxos de dados. O java implementou Streams recentemente e o Haskell funciona de maneira similar. As Streams são listas no qual o fluxo é avaliado de forma preguiçosa. Quando uma Stream é calculada, a lista fica toda calculada em memória e, caso solicitada, é apresentado de imediato pois parte da lista já está memoizada.
Para usar paralelismo em Haskell, é necessário adicionar a biblioteca Control.Parallel.Strategies, que contém a maior parte das funções que utilizam de paralelismo.
Existe o tipo Eval, que é um container para nosso valor. O monad de eval possui as funções runEval, rpar e rseq. Tanto rpar quanto rseq recebem expressões, mas essas expressões devem ser thunk, não podendo ter sido avaliadas.
O paralelismo em Haskell é feito utilizando Sparks, que são promessas de possíveis execuções em paralelo. Ou seja, que pode ser ou não ser computado em paralelo. |
| 17 |
HENRIQUE FANTATO SILVA DE ALBUQUERQUE |
A avaliação preguiçosa, lazy evaluation, é a estratégia padrão de avaliação de expressões de várias linguagens funcionais.
Suas propriedades são:
- Atrasar a avaliação de uma expressão até que o resultado seja extritamente necessário.
- Memoizar todas avaliações, afim de reutilizar resultados prévios e evitar recálculos.
A função seq recebe dois parâmetros, avalia o primeiro e retorna o segundo, retornando a WHNF,
Weak Head Normal Form, avaliando apenas a primeira camada necessária. Caso seja necessário o resultado completo da
avaliação, podemos usar a função force.
Streams são listas similares a listas comuns, porém a avaliação de cada célula é feita de maneira preguiçosa.
Com essas listas especiais, podemos resolver de forma preguiçosa a lista de primos, ou até mesmo criar uma função
que retorne a sequência de Fibonacci.
Para realizar paralelismo em Haskell, podemos usar a Monad Eval, que utiliza outras funções auxiliares para realizar
a avaliação de expressões sequencialmente ou paralelamente. Para realizar a avaliação de expressões paralelamente,
devemos utilizar a função rpar, e rseq para avaliações que necessitam ser sequenciais. Importante notar que as expressões
que serão argumentos de rpar e/ou rseq, devem ser expressões ainda não avaliadas, caso contrário, não haverá impacto nenhum.
Ambas funções avaliam as expressões para a forma WHNF. Caso seja necessário o resultado final da expressão, devemos utilizar
a função runEval.
Podemos ter diversas estratégias de avaliação, e para isso, utilizamos a abstração de estratégias da biblioteca
Control.Parallel.Strategies. Com a utilização desse tipo, podemos abstrair as estratégias de paralelismo para tipos de dados.
Como listas são uma estrutra muito importante em Haskell, a biblioteca já vem com a estratégia de lista já implementada, a
parList.
|
| 18 |
IGOR SAWAKI |
|
| 20 |
LEANDRO RIBEIRO DE ALMEIDA |
|
| 35 |
LOUIS PHILLIPE SARDA DUBOIS |
Avalição preguiçosa:
Tem duas propriedades essenciais:
- é suspensa até que o resultado seja necessário.
- o resultado é memoizado, ou seja, ele só será colocado em cache e só será recalculado se realmente necessário.
Uma maneira de verificar a avalição preguiçosa em Haskell é utilizando a função sprint, se fizermos por exemplo:
x = 5 + 10
:sprint x
-> x = _
x
-> 15
:sprint x
-> x = 15
Streams:
São listas similares a listas comuns. Contudo a avaliação de cada célula é feita de maneira preguiçosa, e quando falamos de stream,
normalmente falamos de listas infinitas, cujo comprimento é desconhecido a priori:
[1..] -- todos os número positivos
[2,4..] -- todos os número pares positivos
Paralelismo
Eval Monad: biblioteca Control.Parallel.Strategies fornece os seguintes tipos e funções para criar paralelismo:
data Eval a = ...
instance Monad Eval where ...
runEval :: Eval a -> a -- executa uma expressão (em paralelo ou não) e retorna o seu resultado
rpar :: a -> Eval a -- indica que meu argumento pode ser executado em paralelo
rseq :: a -> Eval a -- indica que meu argumento deve ser avaliado e o programa deve esperar pelo resultado
Estratégias de Avalição
type Strategies a = a -> Eval a
A ideia desse tipo é permitir a abstração de estratégias de paralelismo para tipos de dados:
parPair :: Strategy (a,b)
parPair (a,b) = do a' <- rpar a
b' <- rpar b
return (a',b')
Dessa forma poderíamos escrever:
runEval (parPair (fib 41, fib 40))
E se quisermos separar a parte sequencial da parte paralela podemos definir:
using :: a -> Strategy a -> a
x `using` s = runEval (s x)
Threadscope: performance profiling de código paralelo |
| 23 |
LUCAS DAVID VADILHO |
# Resumo - Semana 09
## Lazyness
- Atribuímos uma expressão à uma variável, e não um valor como em linguages mais comuns
- Precisamos forçar a execução de um expressão
- `sprint` imprime o valor sem forçar a execução, podendo imprimir `_` (um _thunk_)
- Depois de avaliado, o valor passa a ser o resultado da execução
- `seq :: a -> b -> b` tem um efeito colateral no primeiro elemento, a primeira _camada_ será avaliada (WHNF - Weak Head Normal Form)
- No cabal, `buil depends: deepseq`, podemos usar o `force` de `import Control.DeepSeq` para levar um _thunk_ para a forma normal
### _Streams_
- Basicamente listas com elemento:como gerar o próximo elementos, dessa maneira podemos construir listas infinitas
## Paralelismo
### Monad Eval
- No cabal `build-depends: parallel` e `ghc-options: -threaded -rtsopts - with-rtsopts=-N -eventlog`
```haskell
import Control.Parallel.Strategies
import Control.Exception
import Control.DeepSeq
```
- A Monad Eval está no `Control.Parallel.Strategies`
- Temos 3 funções principais:
- `runEval :: Eval a -> a` (devolve o `a` em WHNF)
- `rpar :: a -> Eval a` (~libera o controle antes de obter o resultado)
- `rseq :: a -> Eval a` (~trava o controle até obter o resultado)
- `rpar` e `rseq` recebem um _thunk_
- `evaluate` força a execução para WHNF
### Combinações de Estratégias
Temos `type Strategy :: a -> Eval a`
- Permite passar como parâmetros
Temos `using :: a -> Strategy a -> a`
- Generaliza processamento paralelo (`tupla `using` parPair`)
### Com Listas
```haskell
parMap :: (a -> b) -> [a] -> [b]
parMap f xs = map f xs `using` parList rseq
```
Cada elemento da lista gera um spark
## Spark
O paralelismo é feito via sparks, são promessas de algo que pode ser computado em paralelo. Os sparks são inseridos numa pool e consumidos.
par
-> spark criado (add na pool)
-> dud (já foi avaliado na WHNF)
-> overflow (pool está cheia)
-> converted (avaliado por um core)
-> fizzled (já havia sido avaliado)
-> garbage collected (não era necessário)
- Poucos sparks: pode ser paralelizado mais
- Muitos sparks: paralelizado demais
- Duds e fizzles: estratégia não otimizada |
| 22 |
LUCAS SILVA AMORIM |
Avaliação preguicosa
- Adia a computação de um dado até que ele seja necessário, esse dado é cacheado para futuras utilizações (evita reprocessamento)
- 'seq' força avaliação imediata para funões em WHNF, force avalia o valor em sua forma normal.
- Lista onde a avaliação de cada célula é preguiçosa ("lista infinita").
Paralelismo
- Classe de tipo para execução paralela: instance Monad Eval where ...
- Função similar a 'future': rpar; Função similar ao 'wait': rseq
- Estrategias de avaliação:
- O tipo Stategies permite abstrair a implementação das diferentes estratégias de paralelismo
- Thread Scope: permite debugar os dados sobre seu código paralelo
- O paralelismo é feito através de sparks, promessa de algo que pode ser computado (como um future) |
| 24 |
LUCAS YUDI FUKAZAWA CASSIN |
Avaliação preguiçosa
Quando o código é compilado, valores de variáveis não são calculadas e guardadas. É guardado uma referência para a expressão, que será calculada quando necessária.
Expressões não avaliadas são thunks, seq força a avaliação (primeiro nível - WHNK) de uma expressão sem precisar mostrar na tela, force faz a avaliação completa.
A avaliação de uma expressão é feita apenas até o nível necessário.
A avaliação preguiçosa pode ser explorada na utilização de funções que dependem de si próprias para serem calculadas.
Eval Monad
Utilizado para executar ações em paralelo. (Control.Parallel.strategies).
Tipo Eval, que possui uma instancia de Monad. Possui três funções importantes: runEval (para retirar o encapsulamento, só faz sentido se for passado thunks), rpar que encapsula a função e já devolve o controle e a rseq que também encapsula, porém antes de devolver o controle, avalia a função.
Spark é uma expressão que precisa ser avaliada e é colocada dentro de uma fila. A fila é consumida conforme existem threads disponíveis para consumi-la.
|
| 19 |
LUCAS ZOCCHIO |
A avalição preguiçosa, diferente da "avaliação ávida", avalia cada valor somente quando necessário.
Antes de ser avaliado, um certo valor é somente aponta para uma dada computação. Esse valor antes de ser calculado é chamado de thunk.
A representação de dada variável em certo momento pode ser obtida pelo comando ":sprint" no gchi. A função "force" força a avaliação completa de dado valor e não somente da forma normal fraca (WHNF, Weak Head Normal Form).
Esse tipo de avaliação é interessante por evitar cálculos desnecessários. Por exemplo é possível saber o tamanho de uma lista sem ter que avaliar todos os valores que a compoem.
Também é interessante para o uso de funções recursivas. Ao implementar um "stream" que retorna os valores da sequência de Fibonacci,
desde que se tenha os primeiros elementos da sequÊncia é possível utilizar uma chamada recursiva da função, pois cada elemento acaba sendo definido antes de ser usado na avaliação,
o que permite criar uma implementação de tempo linear para a geração dessa sequência.
O Haskell também permite paralelismo. Para tanto é necessário adicionar "parallel" às bibliotecas de que o projeto depende e fazer a importação de "Control.Parallel.Strategies".
Nessa biblioteca estão definidas as funções rpar e rseq, que são estratégias (tipo Strategy, também definido na biblioteca) de avaliação paralela.
Ambas relizam a avaliação somente até a WHNF, portanto para forçar a avaliação de toda a expressão utiliza-se a função "force".
Através dessas estretégias é possível deixar uma tarefa executando em paralelo sem interromper o funcionamento do programa (rpar) ou aguardar a conclusão (rseq).
É necessário ter o cuidado de avaliar como os "sparks" criados são usados pelos processadores, o que pode ser feito com o programa Threadscope. |
| 25 |
LUCCA IANAGUIVARA KISANUCKI |
Lazy evaluation
Estratégia de avaliação padrão de várias linguagens funcionais
A avaliação de uma expressão é suspensa, ou atrasada (delayed) até que resultado seja necessário
A partir do momento que o resultado tiver sido calculado ele é memoizado/cached
Função sprint
Mostra o estado atual da variável
Função seq
Recebe dois parâmetros, avalia o primeiro e retorna o segundo
Normal Form
Função force
Para avaliar uma expressão em sua forma normal
Streams
Listas comuns. Contudo a avaliação de cada célula é feita de maneira preguiçosa
Em Haskell todas as listas são assim
Paralelismo
data Eval a = ...
instance Monad Eval where ...
runEval :: Eval a -> a
rpar :: a -> Eval a
rseq :: a -> Eval a
Eval Monad
Control.Parallel.Strategies
Biblioteca que fornece suporte a paralelismo
Função rpar
Pode ser executado em paralelo
Função rseq
Deve ser avaliado e deve esperar o resultado
Função runEval
Executa uma função em paralelo ou não, e retorna o resultado
rpar-rpar
Não aguarda o final da computação para liberar a execução de outras tarefas
rpar-rseq
Aguarda a finalização do processamento seq
rpar-rpar-rseq-rseq
Aguarda o resultado de todos os threads antes de retornar
Threadscope
Programa para ver os cores executando em paralelismo
Sparks
Um spark é uma promessa de algo a ser computado e que pode ser computado em paralelo
|
| 26 |
LUIZ FELIPE LEAL GOMES AZZOLINI |
# Avaliação Preguiçosa
- Propriedade de linguagens funcionais de atrasar a computação de uma operação até que seu resultado seja realmente utilizado.
- O resultado a partir do momento que é computado, é guardado em memória caso precise ser utilizado novamente sem ser recomputado
- No haskell a avaliação preguiçosa funciona de forma “parcelada”, de modo que a depender da operação é computado apenas parte da propriedade de uma variável, por exemplo ao se ter uma lista L = fmap (+1) [1..10] e rodarmos um length L, será computado apenas o comprimento da lista, mas não o valor de cada número dentro, após isso, ao verificar no ghci com “:sprint l” temos o resultado [_,_,_,_,_,_,_,_,_,_]
# Paralelismo
- Em haskell podemos utilizar a biblioteca Control.Parallel.Strategies para usar paralelismo em sua execução
- A função rpar indica que o argumento pode ser executado em uma thread separada, permitindo assim utilização de programação assíncrona, diferente da função rseq que indica uma computação sequencial de forma a fazer o programa esperar o processamento terminar para prosseguir com a execução
- Ao fazer testes em um ambiente Linux emulado por Windows o teste sem programação paralela terminou em 36.5466722s, utilizando programação paralela com 1 thread o teste terminou em 22.4527593s, já com 2 threads terminou em 15.5318344s
- Em haskell o paralelismo é feito por meio de sparks, uma estrtura de promessas que pode mas não necessariamente será computada em paralelo
- Os sparks são inseridos em um pool de modo a acionar processos paralelos.
|
| 27 |
MARCELO CECILIO FAGUNDES DA SILVA FILHO |
Em haskell existe algo chamado avaliação preguiçosa. Nela as expressões são calculadas conforme o seu uso. Por exemplo, ao criar uma função que soma dois números, seu valor só irá ser avaliado quando ele for necessária, seja para imprimir ou para usar o valor em outra expressão. Quando uma expressão é avaliada ela fica salva na memória até o fim da execução do programa, tornando sua próxima execução mais rápida.
No caso das listas primeiramente é avaliado se é uma lista, depois seu tamanho e depois seus valores. Com isso, ao executar o length em uma lista obtemos o seu tamanho, porém os valores contidos nela não são avaliados. Além disso, graças a avaliação preguiçosa podemos fazer o uso de listas infinitas e o uso da própria lista para calcular seus próximos valores, uma vez que, apenas os valores usados são avaliados.
Para forçar a avaliação de uma expressão podemos usar duas funções:
seq: recebe dois valores e retorna o segundo, porém isso faz com que o primeiro valor seja avaliado. Porém ela só avalia o primeiro nível, por exemplo, em uma lista só irá ser avaliado que o valor é uma lista.
force: executa a expressão até sua forma normal, ou seja, avaliando-a completamente.
A biblioteca Control.Parallel.Strategies permite executar mais de uma expressão ao mesmo tempo (em paralelo). Isso é feito usando diferentes cores do processador para cada expressão.
Há duas funções que executam expressões em paralelo:
rpar: executa a expressão em paralelo sem interromper o programa.
rseq: força o programa a esperar a avaliação.
O paralelismo é feito através de criação de sparks, que são promessas de algo a ser computado.
O programa threadscope avalia a execução do programa, mostrando inclusive a execução dos processos em paralelos, permitindo avaliar a estrategia e assim melhora-la.
|
| 31 |
MARIANA MIWA OKUMA MIYASHIRO |
Avaliação Preguiçosa
- Estratégia de avaliação padrão de várias linguagens funcionais
- Propriedades:
- avaliação suspensa/atrasada até o resultado ser necessário
- resultado calculado -> memoizado (cached) para ser reutilizado, não recompilado
- Expressão sprint (ghci): mostra estado atual da variável, retorna _ até o elemento ser avaliado
- Função seq:
- recebe dois parâmetros, avalia o primeiro (primeira camada) e retorna o segundo
- force (ghci ou Control.DeepSeq):
- avalia expressão até o final
- Streams: listas cuja avaliação de cada célula é preguiçosa (todas em Haskell)
- exemplo lista de primos:
cada valor é calculado quando é pedido e cada valor até o maior valor calculado já está memoizado
- exemplo fibonacci: feito utilizando a ideia: fib + fib deslocada em 1 posição = fib
implementação mais rápida que se utiliza da aval preguiçosa
Paralelismo
Eval Monad
- Adicionar no .cabal:
- build-depends: paralle,time
- ghc-options: -threaded -rtsopts -with-rtsopts=-N -eventlog
- Control.Parallel.Strategies:
- runEval :: Eval -> a --executa ação
- rpar :: a -> Eval a --paralelo
- rseq :: a -> Eval a --espera pelo resultado
- Monad Eval = pura
- compilar: stack build
- executar: stack exec <nome> --RTS -- +RTS -N1
- Nx: nº de processadores
- exemplo: fparseq (rpar-rseq)
fparseq :: Eval (Integer, Integer)
- uso: runEval (fparseq)
Estratégias de Avaliação
- type Strategies a = a -> Eval a
- abstrai estratégias usando paralelismo
- exemplo parPair (ambos em rpar)
parPair :: Strategy (a,b)
- separando parte sequencial da paralela:
using :: a -> Strategy a -> a
- parametrizar estratégias:
evalPair :: Strategy a -> Strategy b -> Strategy (a,b)
- lista:
map f xs `using` parList rseq (definição de parMap)
Threadscope
- execução: com -ls threadscope media.eventlog
- gráficos com trabalho de cada core
- Sparks: promessa de algo a ser executado
- elemento passado para rpar cria um spark e é inserido no pool
- spark é pego do pool, convertido em processo e executado
- Sinais de problemas:
- Poucos sparks → paralelizar mais
- Muitos sparks → paralelizado demais
- Muitos duds e fizzles → estratégia não otimizada
|
| 29 |
NATALIA LEITE VARES DE SOUZA |
AVALIAÇÃO PREGUIÇOSA
Avaliação preguiçosa é a estratégia de avaliação padrão de várias linguagens funcionais.
Na avaliação preguiçosa, uma expressão será avaliada apenas quando o seu resultado por necessário.
Quando esse resultado for calculado, ele será memorizado e sempre que for preciso ele será reutilizado, sem necessidade de um novo processamento.
No Haskell podemos usar a função sprint para analisarmos o estado atual da variável e assim podemos verificar a existência da avaliação preguiçosa nessa linguagem.
A partir da função seq é possível avaliar uma variável e imprimir outra, durante a mesma execução, por exemplo:
Prelude> x = 1 + 1
Prelude> y = 2 * 3
Prelude> :sprint x
x = _
Prelude> :sprint y
y = _
Prelude> seq x y
6
Prelude> :sprint x
x = 2
STREAMS
Aproveitando o conceito de avaliação preguiçosa, temos a implementação das streams, que são listas parecidas com listas comuns, porém a avaliação de cada célula é feita de maneira preguiçosa.
Na linguagem do Haskell todas as listas implementadas podem ser chamadas de streams.
PARALELISMO
- Eval Monad
No Haskell, a partir da biblioteca Control.Parallel.Strategies temos acesso à tipos e funções para criar paralelismo.
• rpar indica que meu argumento pode ser executado em paralelo.
• rseq diz meu argumento deve ser avaliado e o programa deve esperar pelo resultado.
• runEval executa uma expressão (em paralelo ou não) e retorna o resultado dessa computação.
- Estratégias de avaliação
No Haskell a partir da biblioteca anterior, podemos definir o tipo:
type Strategies a = a -> Eval a
A ideia desse tipo é permitir a abstração de estratégias de paralelismo para tipos de dados.
- ThreadScope
É uma ferramenta para análise de desempenho de programas paralelos Haskell , podemos verificar se o trabalho está bem equilibrado entre os processadores disponíveis e identificar problemas de desempenho.
|
| 28 |
NATHALIA CORREA DOS SANTOS |
|
| 34 |
PAULO GABRIEL MASSA |
|
| 32 |
PEDRO BRAGA DOS SANTOS BACELLAR |
|
| 33 |
PEDRO MACHADO NERY DOS SANTOS |
Avaliação preguiçosa (Laziness) se refere à computação apenas em casos estritamente necessários (dependência do valor), com a avaliação de expressões antes apenas referenciadas (potencialmente infinitas). A função sprint mostra o estado de uma expressão em haskell sem forçar seu cálculo como um print comum. O valor thunk é usado para sinalizar que ainda não se realizou computação. O comando seq (a->b->b) causa o efeito colateral de calcular uma expressão (Ex.: seq exp ()). Em Haskell tipicamente apenas a camada mais externa de avaliação (apenas até onde é necessário) é informada (Weak Head Normal Form (WHNF)). force (do pacote Control.DeepSeq) força a avaliação até a forma normal. Streams são similares a listas e podem ser representadas de forma preguiçosa.
A avaliação paralela de expressões em Haskell pode ser realizada pela Eval Monad. Para usar o paralelismo, deve-se adicionar a biblioteca parallel e fazer import Control.Parallel.Strategies. A monad Eval se baseia num tipo de dados paramétrico (também Monad) chamado Eval com métodos runEval, rpar e rseq. rpar (retorna o controle e avalia expressão) e rseq (avalia expressão e retorna o controle) introduzem uma função na Monad Eval para que possa ser avaliada (até a forma normal fraca) por runEval. A função "using" permite separar uma estratégia Strategy para o cálculo de expressões predefinidas. Listas já tem a estratégia parList implementada para maps (map f xs `using` parList rseq ou, de forma equivalente, parMap f xs). Usando o threadscope, podemos analisar a carga de trabalho distribuídas em cores. Em Haskell, o paralelismo é feito através de sparks (uma promessa de computação colocada numa fila). Cada elemento de uma lista gera um spark. É necessário obter um equilíbrio entre a alocação paralela e a execução de computação, de forma que segmentar estruturas pode ser útil e possivelmente forçar a execução em suas partes. |
| 36 |
PIETRO DI CONSOLO GREGORIO |
Em linguagens funcionais, como no caso do Haskell, a avaliação preguiçosa é a estratégia padrão da avaliação, ou seja, diferente de outras linguagens que armazenam o valor da expressão avaliada, o Haskell armazena a expressão até que o resultado seja necessário (avaliação suspensa ou atrasada) e quando a expressão é avaliada o resultado é armazenado (memoized), podendo ser reutilizado e não tendo a necessidade de ser recalculado.
Ao utilizar o método sprint para apresentar o estado atual da variável é possível notar que uma expressão realmente só será avaliada quando requisitado. A função seq pode ser usada para forçar a avaliação em um "nível" (Weak Head Normal Form) de uma expressão. Para forçar a avaliação completa (Normal Form) pode-se usar force (import Control.DeepSeq). Alguns exemplos de aplicação: lista de números primos e sequência de Fibonacci
Para usar o paralelismo é necessário usar a biblioteca parallel (Control.Parallel.Strategies), a qual fornece o tipo Eval, que fornece um contêiner para o valor e é uma Monad pura, a função runEval (WHNF), rpar (argumento pode ser executado em paralelo) e rseq (argumento deve ser avaliado e deve aguardar resultado).
O tipo Strategies permite que a estratégia de paralelismo adotada (rpar-rpar, rpar-rseq, rpar-rpar-rseq-rseq) possa ser abstraída para tipos de dados. Além disso é possível criar outras funções que consigam adotar a estratégia passada como parâmetro, como no exemplo da função evalPair.
O paralelismo no Haskell é feito através do spark, uma promessa de algo que pode ser computado em paralelo. Durante a criação do spark ele pode virar um dud se já processado, retornar status overflow e não ser criado, ou ser criado e inserido em um pool, de onde será convertido e executado, se já tiver sido executado retorna status fizzled e caso a expressão não seja requisitada ela é desalocada pelo garbage collector. |
| 6 |
RAFAEL BRUNO FERREIRA FIGUEIREDO |
Lazy vs Eager Evaluation:
Eager: faz a avaliação da expressão e coloca valores em variáveis.
Lazy: Troca as variáveis por referencias para as expressões e só as calcula quando o resultado final é desejado. Permite streams.
Em geral, a avaliação preguiçosa faz que o sistema só consuma processamento com as funções estritamente necessárias. Na avaliação ávida o fluxo de execução é dado pelo programador (CODE IS THE LAW).
sprint -> mostra o valor de uma variável/expressão sem forçar a avaliação.
seq -> Avalia um valor e devolve o segundo. seq x () devolve apenas o unity mas força a avaliação de x. Essa função causa efeito colateral em x.
Weak head normal form (WHNF): Avaliação da primeira camada da expressao.
:force k -> força a avaliação de k no GHCI, levando a expressão pra forma normal (não normal fraca). No programa existe a função force que depende de importar a biblioteca Control.DeepSeq no pacote deepseq.
"memoizar": como haskell é uma linguagem pura não á conceito de "memorizar", pois nao se "guarda" o resultado.
Haskell Paralelo:
O Eval pode ser entendido como um conteiner de "configuração" de avaliação. A função runEval roda a avaliação.
rpar: devolve o controle da avaliação antes de terminar a execução.
rseq: devolve o controle da avaliação só depois de avaliar a execução.
Using: using a b = runEval (b a). Função para aplicar a estratégia em uma expressao.
parList: Paraleliza uma lista. A função parMap faz um map paralelo em uma lista.
spark: são as expressões em fila para serem realizadas que podem ser realizadas em paralelo. Tem um equilibrio entre a criação e consumo de sparks e a melhoria em gerar esses sparks. Além disso em alguns casos é interessante forçar a avaliação de expressoes em paralelo (deepseq) |
| 37 |
RAFAEL PAUWELS DE MACEDO |
O primeiro assunto que tratamos foi a avaliação preguiçosa. Dentro de linguagens preguiçosas as funções que definem uma variável só são avaliadas quando necessário, por exemplo, só avaliamos o "thunk" de x = 1 + 2 quando usamos x.
Para vermos o status de uma variável dentro do ghci usamos o comando :sprint e caso eu queira forçar a avaliação da variável podemos usar a função seq, mas é importante notar que o seq só avalia a forma normal fraca da função. Caso queira avaliar mais fundo é necessário calcular a variável ou usar a função force da biblioteca deepseq.
Usando o conceito de laziness vimos como construir na prática funções para calcular números primos e também como calcular a sequência de Fibonacci.
A segunda sequência de aulas foi sobre paralelismo no Haskell, começando pela Eval Monad. Para usar o paralelismo precisamos adicionar no cabal a biblioteca parallel e com a opção threaded no ghc.
A Monad Eval disponibiliza duas formas de receber uma função, o rpar e o rseq. O rpar não espera a execução ser finalizada antes de liberar o runEval já o rseq aguarda a execução.
Representando como um gráfico de barras teríamos algo do tipo
========== fib 41
======= fib 40
^ runEval caso fib41 e fib40 sejam passados com rpar
^ runEval caso fib40 seja passado com rseq e fib41 com rpar
Na sequência vimos como melhor organizar o código, separando a Strategy de processamento a ser usada da expressão. E por fim vimos como utilizar o threadscope para analisar como o paralelismo aconteceu e como podemos otimizar melhor os sparks, não é vantajoso ter poucos sparks mas também não podemos ter muitos sparks para evitar o overflow. |
| 38 |
RAPHAEL RAMOS DA SILVA |
------------------------------------------- Avaliação Preguiçosa --------------------------------------
- A avaliação da expressão ocorre apenas quando for necessário (para realizar o processamento).
- Após o processamento, o resultado é armazenado para ser utilizado quando for necessário.
(evitando assim, uma reavaliação desnecessária/repetida).
- função sprint: mostra o estado atual da variável passada como parâmetro
(conseguimos saber no ghci, se a variável já foi avaliada ou não).
- função seq: recebe 2 valores como parâmetro, avalia o primeiro e processa o segundo.
- Streams: listas avaliadas de forma preguiçosa (permite a criação de listas infinitas).
(só utilizamos o valor da próxima posição quando for necessário).
---------------------------------------------- Paralelismo --------------------------------------------
- O paralelismo é pautado na criação de sparks (promessa de algo que pode ser processado em paralelo).
- Os sparks (desde que não tenham sidos processados anteriormente -> avaliação preguiçosa)
são inseridos em um pool, que alimenta os processos paralelos.
Pool cheio -> overflow (spark não é criado)
- Na blibioteca Control.Parallel.Strategies temos duas funções que viabilizam o paralelismo:
(rpar) - indica que o argumento pode ser processado em partalelo (criação de um spark).
(rser) - indica que o programa deve esperar a finalização do processamento do argumento.
- Na biblioteca acima também temos o tipo Strategies, que permite abstrair as estratégias de
paralelismo para tipos de dados.
|
| 21 |
RENAN FERREIRA LIMA |
Em linguagens com avaliação preguiçosa, como o Haskell, no momento da execução do programa, o que é colocado dentro das variáveis, em um primeiro momento, é a expressão correspondente e não o resultado da expressão como nas linguagens tradicionais. Assim, o cálculo só é realizado quando for realmente necessário, uma maneira de avaliar esse comportamento é utilizando o sprint do ghci, caso o retorno seja underscore, o valor da variável ainda não foi avaliado, i .e., a expressão é um thunk.
Destacamos também o conceito de stream que são listas em que a avaliação de cada célula é feita de maneira preguiçosa. Em Haskell todas as listas são stream, podemos analisar isso utilizando uma lista de números primos, se quisermos os primeiros 100 números, a linguagem vai avaliar somente o resultado das 100 primeiras posições, em seguida, por ser uma linguagem pura, vai memoizá-los, de modo a aproveitá-los eventualmente sem a necessidade de recalcular aquelas posições. Uma vantagem desse tipo de implementação, é que podemos usar a recursividade e ganhar muita performance, i.e., usar a própria lista de primos que estamos gerando para verificar a primalidade. Poderíamos usar esse mesmo artifício para o cálculo dos números de Fibonacci, por exemplo.
Para processamento em paralelo temos o Eval Monad, destacando-se as funções runEval, rpar e rseq, sendo que a primeira roda a entrada recebida de acordo com a estratégia definida, criando um spark e retornando um a, sendo que a estratégia é definida por rpar ou rseq, as quais devem receber uma expressão thunk e retornar um Eval de a. Quanto a diferença entre elas, a rpar inicia a execução da expressão e devolve o controle logo em seguida, enquanto que o rseq espera a expressão ser avaliada para devolver o controle. Para avaliar o processamento podemos utilizar o Threadscope.
|
| 40 |
VITOR RUBENS SNIQUER LEAO MARTINS |
|
| 39 |
VITTORIA ARIEL DOS SANTOS BOROTTO |
=>Avaliação Preguiçosa: estrategia de avaliacao que normalmente é o
padrao de diversas linguagens funcionais.
Propriedades essenciais:
- A avaliação de uma expressão é suspensa, ou atrasada até que resultado seja necessário,
ou seja nao executa sem necessidade
- A partir do momento que o resultado tiver sido calculado ele é "cacheado", para que se ele for utilizado novamente nao seja calculado denovo.
Funcao seq:
Recebe dois parametros, avalia o primeiro e retorna o segundo
=> Weak Head Normal Form (WHNF)
Mostra que seq apenas forcou a avalizacao da estrutura de tupla, isso chamase de WHNF
Para avaliar a expressao em forma normal pode-se usar o force:
import Control.DeepSeq
=>Streams: sao parecidas com listas que ja acostumanos, porem com avaliacao de maneira Preguiçosa
- em haskell todas as listas sao assim
- normalmente sao listas finitas ou sem definicao do comprimento
==>Paralelismo
O haskell com bibliotecas fornece tipos e funcoes para criar o paralelismo:
Algumas funcoes do Control.Parallel.Strategies:
rpar :: a -> Eval a
indica que o argumento pode ser executado em paralelo, o argumento deve ser uma expressao nao avaliada
rseq :: a -> Eval a
indica que o argumento dever ser avaliado e o programa deve esperar o resultado
Aqui podemos reparar que ambos sao o que ja citamos assima WHNF.
runEval :: Eval a -> a
que executa uma expressão em paralelo ou nao e retorna o resultado
Alem disso tem o Monad Eval:
que é pura
=>Estrategias paralelismo:
1.rpar-rpar não aguarda o final da computação para liberar a execução de outras tarefas
2.rpar-rseq aguarda a finalização do processamento seq
3.rpar-rpar-rseq-rseq:aguarda o resultado de todos os threads antes de retornar
gerar mais paralelismo e não dependemos dos resultados anteriores:rpar-rpar.
já geramos todo o paralelismo desejado e precisamos aguardar o resultado:rpar-rpar-rseq-rseq |
| 41 |
WESLEY AXEL DE BARROS |
Para esta semana 09, tivemos dois topicos importantes para o estudo de Haskell na disciplina de Paradigmas de Programação.
Verificamos como primeiro topico como funciona a avaliação preguiçosa em Haskell, como a linguagem avalia expressões/funções e como as mesmas são armazenadas para evitar a avaliação novamente.
Analisamos isso através no terminal através do GHCI, através da função sprint, que mostra o estado atual da variavel, utilizando também a função seq, que recebe dois parametros, avalia o primeiro
e retorna o segundo, fazendo com que o através da avaliação preguiçosa, o resultado seja apenas a parte basica da estrutura já avaliada (WHNF). Vimos a função force que força a avaliação completa de uma função.
Aprendemos que todas as listas em Haskell são streams, ou seja, listas aonde cada celula será avaliada de maneira preguiçosa. E verificamos isso em dois exemplos, aonde nesses dois exemplos,
a avaliação da lista é a sua propria geração na hora de analisar e requisitar um valor.
Para o segundo topico, vimos o conceito de Paralelismo aplicado em Haskell, aonde através de bibliotecas externas, conseguimos fazer com que uma função ou diferente funções sejam avaliadas
de maneira paralela, fazendo com que cada avaliação seja feita em um nucleo separado. Vimos diferentes estrategias de avaliação, através de dois funções, "rpar", que indica que o argumento
pode ser executado em paralelo, e "rseq", que faz com que o argumento seja avaliado, e que a função principal aguarde o resultado da mesma.
Analisamos as diferentes estrategias de avaliação através do progama Threadscope, que através de um grafico gerado com base na execução de uma função, mostra o resultado e desempenho da mesma,
mostrando por exemplo, o tempo decorrido para a execução, e como cada "core" do processador desempenhou na execução da mesma.
Vimos o conceito de Sparks, que é como o parelelismo funciona em Haskell, que é uma promessa de algo a ser computado, e que pode ser computado em paralelo, vimos como funciona,
e seu "ciclo de vida", aonde quando um spark é proposto, ele é criado podendo ser convertido e devolvido, ou posto na lista de overflow caso a lista de sparks criados esteja cheia, ou recolhido pelo
"garbage collector", que coleta sparks que já foram avaliados e que não necessitam ser avaliados novamente.
|
| 42 |
WILLIAM SENA SILVA |
|
| 8 |
francesquini |
|