of 15 /15
Programação paralela em Haskell Ben Hur Bahia do Nascimento Giovanni Viol Assis Rodrigo Ferreira dos Santos Gonçalves DCC/UFLA – Programação Paralela e Distribuída Prof.: Marluce Rodrigues Pereira

Programação paralela em Haskell

  • Upload
    oxydron

  • View
    67

  • Download
    0

Embed Size (px)

DESCRIPTION

Breve apresentação de como usar paralelismo na linguagem funcional Haskell

Citation preview

  • Programao paralela em Haskell

    Ben Hur Bahia do Nascimento Giovanni Viol Assis Rodrigo Ferreira dos Santos Gonalves

    DCC/UFLA Programao Paralela e Distribuda Prof.: Marluce Rodrigues Pereira

  • Haskell Linguagem funcional.

    A computao vista como a avaliao de funes matemticas.

    No existe efeitos colaterais, logo a ordem da execuo das funes no importante.

    Avaliao Preguiosa. A computao de uma expresso somente ocorre quando o seu valor necessrio.

    Linguagem de alto nvel.

    Linguagem declarativa. Descreve O QUE deve ser feito ao invs DE COMO as instrues devem ser

    executadas.

  • Paralelismo em Haskell

    Determinstico: Um programa paralelo sempre produz o mesmo resultado, independente de quantos

    ncleos de processamento so usados para execut-los.

    Programas paralelizados podem ser depurados (Debugged) sem a necessidade de execut-los em paralelo.

    No necessrio se preocupar com comunicao e nem com sincronizao. O programador indica onde o paralelismo est, deixando os detalhes de como executar

    o programa em paralelo para o sistema de execuo (runtime system).

  • Paralelismo em Haskell

    Por possuir menos detalhes operacionais, programas em Haskell so abstratos, portanto tem maior probabilidade de funcionar em uma maior variedade de hardwares paralelos.

    Programas paralelos em Haskell podem tirar vantagem de tecnologias altamente adaptadas ao sistema de execuo (runtime system), como por exemplo o Garbage Collection em paralelo.

    A desvantagem: devido a vrios detalhes de execuo estarem escondidos, problemas de desempenho so difceis de serem entendidos.

  • Problema escolhido: Sudoku

    Dado um arquivo contendo vrias instncias do problema Sudoku, dizer quantos deles possuem soluo

    Escolhemos esse problema, pois cada instncia do problema pode ser resolvido em tempos diferentes

    NP-Completo

  • Abordagem Sequencial

    1. Atribui a f o nome do arquivo

    2. L o contedo do arquivo

    3. Divide o arquivo em linhas, cada linha uma instncia do problema

    4. Soluciona os problemas

    5. Imprime quantos instncias do problema possuem soluo

  • Como paralelizar?!Monad Eval: rpar e rseq

    Paralelismo expressado usando o mnade Eval que vem com 2 operaes: rpar e rseq.

    rpar: meu argumento pode ser avaliado em paralelo

    rseq: avalie meu argumento e espere pelo resultado

  • rpar/rpar

  • rpar/rseq

  • rpar/rseq/rseq

  • Abordagem por diviso de conjuntos de instncias(particionamento esttico)

    1. Divide-se a lista de problemas em duas partes

    2. Resolva em paralelo o conjunto as

    3. Resolva em paralelo o conjunto bs

    4. Aguardando terminar o processamento paralelo

    5. Aguardando terminar o processamento paralelo

    6. Retorna a concatenao das solues

  • Particionamento Dinmico

  • Abordagem por diviso de instncias

    1. A funo runEval avalia cada um dos Evals

  • Concluso

    Existe paralelismo para linguagens funcionais, logo se seu problema possui uma natureza funcional, no necessrio adapat-lo para uma linguagem procedural apenas pelo paralelismo

  • Referncia

    Marlow, Simon. Parallel and Concurrent Programming in Haskell: Techniques for Multicore and Multithreaded Programming. OReilly Media, Inc. 2012.