ANALISE DE DESEMPENHO DE ALGORITMOS DE …tiagodemelo.info/monografias/2013/tcc-juliana-figueira.pdf · inovadores, por exemplo: C criada e usada para a programac~ao do sistema operacional

UNIVERSIDADE DO ESTADO DO AMAZONAS - UEA

ESCOLA SUPERIOR DE TECNOLOGIA - EST

ENGENHARIA DE COMPUTACAO

JULIANA MARTINS FIGUEIRA

ANALISE DE DESEMPENHO DE ALGORITMOS

DE PROGRAMACAO DISTRIBUIDA EM

ERLANG COM INTEL R©MPI BENCHMARKS E

ESQUELETOS ALGORITMICOS EM OOERLANG

Manaus

2013


ANALISE DE DESEMPENHO DE ALGORITMOS DE PROGRAMACAO

DISTRIBUIDA EM ERLANG COM INTEL R©MPI BENCHMARKS E


Trabalho de Conclusao de Curso apresentado

a banca avaliadora do Curso de Engenharia

de Computacao, da Escola Superior de

Tecnologia, da Universidade do Estado do

Amazonas, como pre-requisito para obtencao

do tıtulo de Engenheiro de Computacao.

Orientador: Prof. Dr. Jucimar Maia da Silva Junior

Manaus

2013

ii

Universidade do Estado do Amazonas - UEA

Escola Superior de Tecnologia - EST

Reitor:

Cleinaldo de Almeida Costa

Vice-Reitor:

Raimundo de Jesus Teixeira Barradas

Diretor da Escola Superior de Tecnologia:

Cleto Cavalcante de Souza Leal

Coordenador do Curso de Engenharia de Computacao:

Raimundo Correia de Oliveira

Coordenador da Disciplina Projeto Final:

Tiago Eugenio de Melo

Banca Avaliadora composta por: Data da Defesa: 18/11/2013.

Prof. Dr. Jucimar Maia da Silva Junior (Orientador)

Prof. Dr. Raimundo Correia de Oliveira

Prof. Dr. Ricardo da Silva Barboza

CIP - Catalogacao na Publicacao

F475a FIGUEIRA, M. F.

Analise de Desempenho de Algoritmos de Programacao Distribuıda em Er-

lang com Intel MPI Benchmarks e Esqueletos Algoritmicos em ooErlang/ Juli-

ana Martins Figueira; [orientado por] Prof. Dr. Jucimar Maia da Silva Junior

- Manaus: UEA, 2013.

240 p.: il.; 30cm

Inclui Bibliografia

Trabalho de Conclusao de Curso (Graduacao em Engenharia de Computa-

cao). Universidade do Estado do Amazonas, 2013.

CDU: 004.75

iii


ANALISE DE DESEMPENHO DE ALGORITIMOS DE PROGRAMACAO

DISTRIBUIDA EM ERLANG COM INTEL R©MPI BENCHMARKS E


Trabalho de Conclusao de Curso apresentado

a banca avaliadora do Curso de Engenharia

de Computacao, da Escola Superior de

Tecnologia, da Universidade do Estado do

Amazonas, como pre-requisito para obtencao

do tıtulo de Engenheiro de Computacao.

Aprovado em:18/11/2013BANCA EXAMINADORA

Prof. Jucimar Maia da Silva Junior, Doutor

UNIVERSIDADE DO ESTADO DO AMAZONAS

Prof. Raimundo Correia de Oliveira, Doutor


Prof. Ricardo da Silva Barboza, Doutor


iv

Agradecimentos

Agradeco a minha famılia, amigos, todos que

sempre tiveram fe em mim e ate os que duvi-

daram, mas me ajudaram de alguma forma.

Agradeco tambem ao professor e orientador

Prof. Jucimar Jr. pela paciencia e pelo apoio

no lento desenvolvimento deste trabalho.

v

Resumo

Este artigo apresenta um estudo realizado com algoritmos escritos nas linguagens de

programacao Erlang e ooErlang. Primeiramente sao apresentados os algoritmos de tes-

tes Erlang seguindo a Intel R©MPI Benchmarks com objetivo de medir o desempenho da

linguagem. E entao, pequenos exemplos de programacao distribuıda com esqueletos de

algoritmos em ooErlang para estudos sobre esses conceitos e a extensao da aplicabilidade

desta extensao para Erlang recentemente publicada.

Palavras Chave: erlang, ooerlang, skeletons, mpi

vi

Abstract

This paper gives a study done with algorithms written in the Erlang and ooErlang

programming languages. Firstly presented are the Erlang algorithms tests following the

Intel R©MPI Benchmarks with objective of measuring the performance of the language.

And then, small examples of ooErlang distributed programming with algorithm skeletons

for further studies about those concepts and the extent of applicability of this recently

published Erlang extension.

Key-words: erlang, ooerlang, skeletons, mpi

vii

Sumario

Lista de Figuras x

Lista de Codigos x

1 Introducao 1

1.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Justificativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4 Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.5 Objetivos Especıficos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.6 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Contextualizacao 7

2.1 Programacao Distribuıda . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2 Erlang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.2.1 Erlang e seu Sistema de Concorrencia . . . . . . . . . . . . . . . . . 8

2.3 ooErlang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.4 Desempenho das linguagens de programacao Erlang e ooErlang . . . . . . 9

2.5 Programacao Funcional de Erlang e Programacao Orientada a Objetos de

ooErlang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.6 Taxonomia de Flynn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.6.1 Single-Instruction, Single-Data (SISD) . . . . . . . . . . . . . . . . 12

2.6.2 Multiple-Instruction, Single-Data (MISD) . . . . . . . . . . . . . . 12

2.6.3 Single-Instruction, Multiple-Data (SIMD) . . . . . . . . . . . . . . 13

2.6.4 Multiple-Instruction, Multiple-Data (MIMD) . . . . . . . . . . . . . 14

2.6.5 Single Program, Multiple Data (SPMD) . . . . . . . . . . . . . . . 14

2.6.6 Multiple-Program, Multiple-Data (MPMD) . . . . . . . . . . . . . . 14

2.7 Lei de Anhmdal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

viii

2.8 MPI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.8.1 MPI Benchmark – IMB . . . . . . . . . . . . . . . . . . . . . . . . 16

2.8.2 Pingping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.8.3 Pingpong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.8.4 Threadring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.8.5 Medicoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.9 Esqueletos Algorıtmicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.9.1 Pipe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.9.2 Reduce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.9.3 Fork, Map e Farm . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3 Experimentos 23

3.1 O ambiente de execucao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.2 Conceitos basicos de programacao em Erlang . . . . . . . . . . . . . . . . . 24

3.3 Executando e Depurando Codigo em Erlang com Erlide . . . . . . . . . . . 25

3.4 Os programas de benchmark em Erlang . . . . . . . . . . . . . . . . . . . . 28

3.5 Conceitos basicos de programacao em ooErlang . . . . . . . . . . . . . . . 31

3.6 Os mesmos programas modelados em ooErlang . . . . . . . . . . . . . . . . 32

3.7 A execucao dos experimentos . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.8 As limitacoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.9 Os resultados dos experimentos . . . . . . . . . . . . . . . . . . . . . . . . 33

4 Esqueletos Algorıtmicos em ooErlang 39

4.1 Os codigos de exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.1.1 Farm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.1.2 Fork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.1.3 Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.1.4 Pipe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.1.5 Reduce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.1.6 O teste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5 Conclusoes e Trabalhos Futuros 45

5.1 Conclusoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.2 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

Referencias Bibliograficas 47

Apendices 49

ix

Apendice A Codigos de Benchmark 50

Apendice B Codigos de Biblioteca de Esqueletos 59

x

Lista de Figuras

2.1 Ilustracao de sistema SISD . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.2 Ilustracao de sistema MISD . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.3 Ilustracao de sistema SIMD . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.4 Ilustracao de sistema MIMD . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.5 Diagrama do benchmark Pingping . . . . . . . . . . . . . . . . . . . . . . . 17

2.6 Diagrama do benchmark Pingpong . . . . . . . . . . . . . . . . . . . . . . 17

2.7 Diagrama do benchmark Threadring . . . . . . . . . . . . . . . . . . . . . 18

2.8 Diagrama do esqueleto algorıtmico Pipe . . . . . . . . . . . . . . . . . . . 20

2.9 Diagrama do esqueleto algorıtmico Reduce . . . . . . . . . . . . . . . . . . 20

2.10 Diagrama do esqueleto algorıtmico generico Master and Slave . . . . . . . 21

2.11 Diagrama do esqueleto algorıtmico Fork . . . . . . . . . . . . . . . . . . . 21

2.12 Diagrama do esqueleto algorıtmico MAp . . . . . . . . . . . . . . . . . . . 22

2.13 Diagrama do esqueleto algorıtmico Farm . . . . . . . . . . . . . . . . . . . 22

3.1 Menu de configuracoes do Erlide . . . . . . . . . . . . . . . . . . . . . . . . 27

3.2 Perspectiva de depuracao do Erlide . . . . . . . . . . . . . . . . . . . . . . 27

3.3 Diagrama do codigo do PingPong . . . . . . . . . . . . . . . . . . . . . . . 28

3.4 Diagrama do codigo do PingPing . . . . . . . . . . . . . . . . . . . . . . . 29

3.5 Diagrama do codigo do Threadring . . . . . . . . . . . . . . . . . . . . . . 30

3.6 Diagrama de Classes de Benchmark em ooErlang . . . . . . . . . . . . . . 35

3.7 Medida do tempo de troca de mensagens de Pingping . . . . . . . . . . . . 36

3.8 Medida do tempo de troca de mensagens de Pingpong . . . . . . . . . . . . 36

3.9 Medida do tempo de troca de mensagens de Threadring . . . . . . . . . . . 37

3.10 Sobreposicao da medias do tempo de troca de mensagens dos benchmarks . 37

3.11 Conjunto dos graficos com as medias totais de tempo . . . . . . . . . . . . 38

4.1 Diagrama da organizacao generica da biblioteca de esqueletos . . . . . . . 41

xi

Lista de Codigos

3.2.1 Codigo Erlang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.4.1 Codigo Erlang para espera e envio de mensagem . . . . . . . . . . . . . . . 29

3.5.1 Codigo ooErlang “duck.cerl” . . . . . . . . . . . . . . . . . . . . . . . . . . 32

A.0.1Codigo Erlang - Medicoes parte 1 . . . . . . . . . . . . . . . . . . . . . . . 50

A.0.2Codigo Erlang - Medicoes parte 2 . . . . . . . . . . . . . . . . . . . . . . . 51

A.0.3Codigo Erlang - Pingpign parte 1 . . . . . . . . . . . . . . . . . . . . . . . 52

A.0.4Codigo Erlang - Pingping parte 2 . . . . . . . . . . . . . . . . . . . . . . . 53

A.0.5Codigo Erlang - Pingpong parte 1 . . . . . . . . . . . . . . . . . . . . . . . 54

A.0.6Codigo Erlang - Pingpong parte 2 . . . . . . . . . . . . . . . . . . . . . . . 55

A.0.7Codigo Erlang - Threadring parte 1 . . . . . . . . . . . . . . . . . . . . . . 56



B.0.1Codigo ooErlang - Farm Skeleton . . . . . . . . . . . . . . . . . . . . . . . 59

B.0.2Codigo ooErlang - Farm Slave . . . . . . . . . . . . . . . . . . . . . . . . . 60

B.0.3Codigo ooErlang - Fork Skeleton . . . . . . . . . . . . . . . . . . . . . . . . 61

B.0.4Codigo ooErlang - Fork Slave . . . . . . . . . . . . . . . . . . . . . . . . . 62

B.0.5Codigo ooErlang - Map Skeleton . . . . . . . . . . . . . . . . . . . . . . . . 63

B.0.6Codigo ooErlang - Map Slave . . . . . . . . . . . . . . . . . . . . . . . . . 63

B.0.7Codigo ooErlang - Pipe Skeleton . . . . . . . . . . . . . . . . . . . . . . . . 64

B.0.8Codigo ooErlang - Pipe Slave . . . . . . . . . . . . . . . . . . . . . . . . . 64

B.0.9Codigo ooErlang - Reduce Skeleton . . . . . . . . . . . . . . . . . . . . . . 65

B.0.10Codigo ooErlang - Reduce Slave . . . . . . . . . . . . . . . . . . . . . . . . 66

B.0.11Codigo ooErlang - Biblioteca . . . . . . . . . . . . . . . . . . . . . . . . . . 66

xii

B.0.12Codigo ooErlang - Teste Biblioteca . . . . . . . . . . . . . . . . . . . . . . 67

Capıtulo 1

Introducao

1.1 Introducao

Ao seguir as regras difundidas em livros tradicionais de compiladores, como o “livro do

dragao” [AVA95], novos compiladores podem ser criados para linguagens de programacao

desde que estejam definidas em uma BNF. O que pode parecer uma ideia simples, ate ser

necessario construir os seis nıveis basicos de um compilador. Mas o que deixaria algumas

pessoas desmotivadas, motiva a outras. Encontrar e solucionar um problema e o que faz a

vida de muitos ter sentido. E gracas a pessoas assim, hoje em dia existem os mais variados

compiladores para outras diversas linguagens de programacao.

Dentre estas linguagens, muitas foram promovidas a existencia por terem um pro-

blema especıfico a resolver: uma necessidade de codificar melhor para produzir programas

inovadores, por exemplo: C criada e usada para a programacao do sistema operacional

Unix [Rit93]; melhorar ou modificar a codificacao com uma linguagem, por exemplo: C++

que adicionou um pouco do paradigma orientado a objetos ao C [Str]; ou fazer um para-

digma mais acessıvel para o programador inexperiente, por exemplo: Lua criada para que

cientistas nao tao acostumados a programacao pudessem fazer seu programas em scripts de

computador [Mat03]. Seja qual for o motivo de sua criacao, estes exemplos influenciaram

a producao de tecnologia de seu tempo e seu nicho de pesquisa. E ate mesmo expandiram

os limites de suas aplicacoes, ja que hoje em dia C e C++ podem ser encontradas nas

Introdução 2

mais diferentes aplicacoes e Lua tambem foi utilizada na producao de jogos de computador

como “World of Warcraft” [wow].

Entre as linguagens de programacao mais bem estabelecidas na mercado, neste trabalho

aquela que sera abordada se chama Erlang. Criada pelos laboratorios de pesquisa da

Ericsson [Arm07]. Teve um pico de aplicacoes ao longo dos ultimos anos, pois da maneira

como foi desenvolvida, alem de resolver o problema inicial: necessidade de ferramentas para

construir sistemas de telecomunicacao confiaveis, tambem ganhou caracterısticas de uma

linguagem declarativa de proposito multiplo. E hoje em dia e utilizada em varios tipos

de aplicacoes, desde aplicativos de mensagem, chat da rede social Facebook, a servidores

de videogames (Battle Star Galactica Online e Call of Duty) e servicos de banco de dados

como SimpleDB and CouchDB [erla].

Apos o amplo reconhecimento do Erlang com uma valida solucao para problemas de

programacao concorrente. O paradigma funcional foi reconhecido como uma das suas

caracterısticas importantes [Eri80]. Este paradigma permite um alto grau de abstracao

que nao se limita a colocar o mundo real de forma compreensiva para o computador,

mas tornar a sua nao dependencia de memoria – ex.: variaveis compartilhadas, estados

ou objetos dinamicos – uma forca para a paralelizacao das solucoes. Cada processo fica

extremamente encapsulado pelo fato de que eles so podem trocar informacoes atraves de

mensagens. Entao, mesmo que “uma tempestade” esteja sendo processada do lado de fora,

dentro de cada processo esta calmo o suficiente para que ele execute sua programacao. Ao

saber tirar proveito disso, muitos dos problemas maiores podem ser divididos de forma a

torna-los mais simples e rapidos de serem resolvidos por varios processos independentes ao

mesmo tempo [Fer06].

A outra linguagem que sera abordado neste trabalho, ainda e uma novidade entre

as linguagens de programacao. ooErlang foi desenvolvida no programa de doutorado da

Universidade Federal de Pernambuco em 2013, como uma extensao do Erlang orientada

a objetos.ooErlang que roda em cima do Erlang original tenta aproximar o paradigma

funcional do orientado a objetos, para ajudar o programador acostumado a “orientacao a

objetos” passar para a utilizar “funcoes” de maneira mais natural [Jr.12]. Ja que nem todos

os programadores concordam que a programacao funcional seja um simples passo depois

de aprender a programacao orientada a objetos – OOP (Object Oriented Programming).

Justificativa 3

Deste modo, ooErlang foi desenvolvido para ser uma ferramenta que ajude a amenizar essa

estranheza ao trazer OOP para o Erlang, com a adicao de recursos como classes, heranca,

implementacao de interface e instanciacao dinamica de objetos sem perder a natureza

declarativa da linguagem original.

Quando Erlang foi feita para suportar aplicacoes soft real time, distribuıdas, toleran-

tes a falhas, non-stop e com suporte a hot-swap - para que o codigo pudesse ser alterado

sem parar o sistema, os pesquisadores desse laboratorio tinham atingido um ponto no qual

precisavam de melhores ferramentas para solucionar os problemas da pesquisa e desenvol-

vimento de sistemas de telecomunicacao para Ericson. E ao analisar o caso, adotaram o

paradigma de programacao funcional que era utilizado na linguagem base do que viria a

se tornar o Erlang, pois se adaptava melhor aos seus propositos [Arm07].

Hoje em dia, sendo a orientacao a objetos o paradigma de programacao mais difun-

dido. O programador acostumado a usa-lo percebe-se com grandes dificuldades ao passar

abruptamente para o paradigma funcional. Sendo assim, ooErlang no seu esforco de trazer

o melhor de dois mundos: toda a forca do Erlang e a praticidade da orientacao a objeto

nativa do programador, e uma ferramenta a se considerar para o aprendizado, aproxima-

cao do programador ao Erlang e solucao para utilizar o Erlang em problemas modelados

melhor com a ajuda da orientacao a objetos [Jr.12].

Ainda assim, como uma linguagem nova, ha estudos a serem feitos sobre a aplicabili-

dade do ooErlang. Este trabalho comeca com o estudo do desempenho do Erlang ao criar

programas distribuıdos. E com posse desses resultados, comeca um estudo sobre a progra-

macao distribuıda em ooErlang e seu desempenho voltado para a construcao de esqueletos

algorıtmicos, padroes de projeto do arcabouco da programacao distribuıda que podem ser

considerados um paralelo dos padroes de projeto de OOP.

1.2 Justificativa

Erlang e uma linguagem de programacao, desenvolvida para ambientes como o das

telecomunicacoes que comportam sistemas massivos de escalabilidade “soft real time” de-

pendentes de alta disponibilidade. Ela e predisposta a apresentar um bom desempenho

quando usada para aplicacoes de programacao concorrente, nao somente em tempo de res-

Trabalhos Relacionados 4

posta, mas principalmente em relacao a seguranca de que executara todos os pedidos e

permanecera estavel. Entre a literatura coletada para este trabalho ha analises de desem-

penho para programacao paralela e ate mesmo comparacoes entre Erlang e outras lingua-

gens de programacao testados com o Intel MPI Benchmark, mas este trabalho visa ser

especificamente sobre o estudo do desempenho dos programas no modelo IMB em Erlang

desenvolvidos para sistemas distribuıdo. Um ambiente diferente daquele da programacao

paralela simples, pois nele os processos estao paralelizados em maquinas diferentes, o que

amplia o problema. Por exemplo em aplicacoes bancarias, de e-commerce ou de mensagens

instantaneas a informacao nao tem um so caminho e esta constantemente mudando, indo

para lugares diferentes, sistemas diferentes e a cada diferenca dessas, mais uma complexi-

dade e adicionada ao problema. E a partir desse estudo de desempenho e possıvel ter uma

ideia de como a programacao distribuıda pode funcionar em ooErlang e comecar o estudo

sobre como esqueletos algorıtmicos poderiam ser desenvolvidos em um Erlang orientado a

objeto. [erla]

1.3 Trabalhos Relacionados

No artigo apresentado na IADIS International Conference Applied Computing 2012 foi

apresentado ooErlang como o Erlang Orientado a Objetos [Jr.12] com a intencao de trazer

um publico maior para a valiosa ferramenta que Erlang e para o desenvolvimento de sis-

termas concorrentes. No mesmo ano, no IADIS International Journal on WWW/Internet,

foi publicado o artigo “Comparing The Performance Of Java, Erlang And Scala In Web 2.0

Applications” [JJ12], onde os autores exploraram o universo dos computadores com multi-

plos processadores. Porem, nao houve espaco para abordar o caso de processos distribuıdos

entre varios computadores em rede. Neste trabalho nao e falado nada sobre a compara-

cao de performance de aplicacoes em outras linguagens de programacao, mas se explora o

desempenho da programacao distribuıda em Erlang e, ja que os codigos do Erlang podem

ser usados sem alteracao pelo ooErlang, e estudado tambem a construcao de esqueletos

algorıtmicos em ooErlang usando medidores similares aos dos artigos supracitados.

Objetivo 5

1.4 Objetivo

Obter as caracterısticas de desempenho relacionado a programacao distribuıda para

caracterizar a linguagem de programacao Erlang e ooErlang, ao criar exemplos iniciais de

esqueletos algorıtmicos nessa nesta ultima linguagem.

1.5 Objetivos Especıficos

• Desenvolver tres algoritmos em Erlang que utilizam programacao distribuıda: ping-

ping, pingpong, threadring;

• Fazer testes, medir e analisar os resultados seguindo o modelo IMB;

• Aplicar o que foi aprendido na construcao de exemplos iniciais de esqueletos algorıt-

micos em ooErlang;

• A partir dos resultados achar a resposta da hipotese inicial: ooErlang como extensao

do Erlang tambem e capaz de ter um bom desempenho em Programacao Distribuıda?

1.6 Metodologia

• Introducao a linguagem de programacao Erlang

• Leitura e estudo sobre MPI – Message Passing Interface , IMB – Intel MPI Benchmark

e a ferramenta de desenvolvimento Erlide para a analise de desempenho da linguagem

de programacao Erlang;

• Desenvolvimento de algorıtimos em Erlang e ooErlang que utilizam programacao

distribuıda com uso do modelo MPI e possam ser testados com IMB;

• Executar varias vezes cada um dos programas derivados desses algorıtimos em ambi-

entes livres da maior parte das interferencias indesejaveis e capazes de testar as suas

funcionalidades, salvar as saıdas em arquivos de texto para analise;

Metodologia 6

• A partir dos resultados verificar a validade das hipoteses iniciais e se necessario rea-

justar alguma parte do processo e ate mesmo repetir os experimentos se possıvel.

• Escrever exemplos iniciais de uma biblioteca de esqueletos algorıtmicos Pipe, Reduce,

Fork, Map e Farm em ooErlang.

Capıtulo 2

Contextualizacao

Este capıtulo visa conceder ao leitor o contexto do trabalho aqui desenvolvido e a

explicacao de como os termos que vem no tıtulo trabalham juntos.

2.1 Programacao Distribuıda

Programacao distribuıda e uma das modalidades de programacao concorrente.

Quando necessario distingui-la da programacao paralela: ela e caracterizada pela

execucao de varios processos paralelos que se comunicam entre si, atraves de uma

rede, por estarem em maquinas diferentes.

E mais comum trabalhar de forma distribuıda de dois modos: no primeiro, cada

processo pode trabalhar como uma entidade em conjunto com outras para a execucao

de uma tarefa, no exemplo de um grupo de pessoas montando um quebra cabecas:

enquanto umas cuidam dos cantos, outros montam pedacos das mesmas cores; no

segundo, ha um processo nucleo que comanda os outros, recebe resultados e delega

tarefas, como um gerente. Consequentemente, vai ser visto mais a frente como a

descricao desdes exemplos combina com aquela de alguns esqueletos algorıtmicos.

Erlang 8

2.2 Erlang

A linguagem de programacao Erlang foi desenvolvida nos laboratorios da empresa

Ericsson para suas aplicacoes de telecomunicacao e depois tornou-se “open source”,

e uma linguagem funcional, amplamente utilizada para computacao concorrente e

possui funcionalidades que permitem certa seguranca contra falhas. Por sua natureza

compacta, leve e super responsiva, com propriedades capazes de executar em soft

real time, com boa escalabilidade, robustez e integracao simples com outros sistemas

atraves de troca de mensagens, costuma agregar usuarios avidos por usar todas as

ferramentas que ela dispoem para programacao concorrente [erla].

2.2.1 Erlang e seu Sistema de Concorrencia

Uma caracterıstica nata do Erlang e a comunicacao entre processos. Ela funciona

atraves de mensagens assıncronas que nao dividem dados entre si. E como se hou-

vesse uma caixa de correio que ao mesmo tempo que isola o processo, permite a ele

receber mensagens ordenadamente e tenta combinar os cabecalhos com o que estava

esperando “pattern maching”, para entao voltar a execucao. No caso de falhas, o

metodo primario para lidar com erros e simplesmente finalizar o processo e mandar

uma mensagem para o processo no controle que entao pode tomar alguma acao em

vista do acontecido: reinicializar ou nao o processo interrompido.

Outra caracterıstica marcante e a abordagem “ferramentas, nao solucoes”. Pois pos-

sui um pequeno, mas respeitado conjunto de primitivas para criar processos e os fazer

comunicar entre si, seja apenas entre processos paralelos dentro da mesma maquina,

ate entre processos executados em diferentes nos na internet. Uma das fontes [Heb13],

dividiu duas maneiras principais de fazer sistemas distribuıdos em Erlang. Uma e

usando “Erlang nodes”, nos que podem executar qualquer comando Erlang e normal-

mente estao no mesmo cluster ou rede e a outra e baseada em sockets TCP/IP que

considera menos potente, porem mais segura. Outra informacao interessante, dada

pelo mesmo autor: como programacao distribuıda tende a ser mais complexa, uma

boa tecnica para melhorar o processo de desenvolvimento e explorar as capacidades da

ooErlang 9

linguagem e primeiramente fazer um codigo nao distribuıdo, depois faze-lo funcionar

para dois nos no mesmo computador, entao para comunicacao entre computadores

diferentes e finalmente redes diferentes.

2.3 ooErlang

Programacao Orientada a Objetos surgiu de um paradigma de modelagem orientada

a objeto. Na programacao utiliza objetos e suas relacoes para abstrair o necessario do

problema do mundo real e resolve-lo no computador. Objetos sao abstracoes de coisas

do mundo real formalizados por classes compostas de seus atributos (caracterısticas)

e metodos (acoes). Uns podem herdar caracterısticas de outros, usar polimorfismo

em alguns metodos e se associar de varias maneiras entre si. Mas o intuito principal

e facilitar a interpretacao pelos profissionais e usuarios [Jr.12].

OoErlang e uma extensao orientada a objetos da linguagem de programacao Erlang.

Os objetos sao introduzidos com uma sintaxe perto de Java, facilitando sua adocao

por programadores mais acostumados com OOP , alem de transformar os modulos

em classes, adiciona os recursos de heranca e implementacao de interface.

2.4 Desempenho das linguagens de programacao

Erlang e ooErlang

Desempenho de linguagens de programacao e um termo abrangente. Diversos bench-

marks comparam linguagens de programacao entre si, mas dificilmente algum chega

a abranger todos os requisitos. Mesmo porque, cada linguagem tem um perfil e foco

que concedem a ela peculiaridade e uso distintos. E nas vezes em que se torna neces-

sario uma avaliacao ou comparacao entre linguagens, como para a escolha da melhor

para um projeto de software, o desempenho nao e visto apenas como velocidade de

processamento, carga de memoria utilizada, writability, readability, robustez ou ou-

Programação Funcional de Erlang e Programação Orientada a Objetos de ooErlang 10

tras caracterısticas, mas tambem o processo de desenvolvimento com a linguagem e

o tempo utilizado pelos programadores para desenvolver o sistema [Fer06].

As ultimas caracterısticas citadas a cima foram por muito tempo o motivo de em-

presas desconsiderarem o uso de programacao funcional em suas aplicacoes. Alem

disso, elas as viam como trabalhos academicos sem aplicabilidade, pela falta de exem-

plos praticos. Todavia, Erlang e outras linguagens funcionais conseguiram quebrar

esse bloqueio pela aplicabilidade demonstrada com a solucao de problemas tıpicos

de um mundo de informacoes cada vez mais distribuıdas [Fer06]. E motivado por

esse contexto de rapidas mudancas, distribuicao de informacao e processamento, este

trabalho tem foco no uso da programacao distribuıda com as duas linguagens previ-

amente apresentadas.

Como, de acordo com os primeiros resultados dos trabalhos de pesquisa compara-

tivos de ooErlang com outras linguagens – realizados nesta instituicao – nao existe

overhead negativo entre implementacoes de programas paralelos feitos nele e em Er-

lang: depois de obter o benchmark da linguagem original, o estudo continuara com a

implementacao de exemplos de esqueletos algorıtmicos para uma observacao de como

eles poderiam ser feitos com a orientacao a objetos do ooErlang.

2.5 Programacao Funcional de Erlang e Progra-

macao Orientada a Objetos de ooErlang

Programacao Funcional e um paradigma de programacao que utiliza conceitos mais

diretos do calculo: variaveis expressam a dependencia que exite entre ela e o fluxo

de dados. Ou seja, sao linguagens baseadas em funcoes, o que facilita a reutilizacao

de codigo e independencia de dados. Uma funcao sempre recebe um valor para gerar

outro, independente de tudo exceto dos valores que ela recebeu, estes representados

pelas variaveis de entrada. Por causa disso, linguagens funcionais nao teriam que

se preocupar com efeitos colaterais de funcoes, pois funcoes so afetam ao que esta

dentro delas naquele momento [Fer06].

Taxonomia de Flynn 11

Pode parecer estranho, mas e muito importante: uma variavel so pode assumir um

valor. O comando “x = x + 1” nao seria aceito, pois a variavel x e associado a

um unico valor e nao a uma expressao. E completamente normal em linguagens de

programacao imperativas x receber um expressao, porque variaveis nessas linguagens

sao como caixinhas para armazenar valores, mas em linguagens funcionais elas sao

os valores.

De encontro com o paradigma ha vezes em que e preciso armazenar ou atualizar

valores e para isso ha pelo menos duas abordagens: a primeira, adicionar as ins-

trucoes de entrada e saıda necessarias, o que acaba classificando a linguagem como

impura; a segunda, deixar a linguagem puramente funcional, mas utilizar operadores

especiais de I/O: monads e sistemas de “uniqueness type”. Entao, vai depender do

objetivo da linguagem qual abordagem e escolhida: os criadores do Erlang preferiram

a “contaminacao” [Fer06], o que parece valido em relacao ao objetivo deles.

Mesmo com muita diferenca entre os dois tipos de programacao, funcional e orientada

a objetos, ha conceitos nao totalmente conflitantes, como encapsulamento e abstracao

que o ooErlang pode tirar proveito. E ate conceitos de heranca e interface puderam

ser adaptados.

2.6 Taxonomia de Flynn

Como faz parte deste trabalho estudar o desempenho de uma linguagem nativa-

mente concorrente, fazendo uso de modelos de interface ja respeitados, e interessante

tambem passar pela classificacao que e feita de acordo com caracterısticas do com-

putador paralelo. Um modelo simples para tal classificacao e dada pela Taxonomia

de Flynn [Fly72]. Esta taxonomia caracteriza computadores paralelos, de acordo

com o controle global, os dados resultantes e o controle de instrucoes e dados, sao

distinguidos em quatro casos:


Figura 2.1: Ilustracao de sistema SISD

2.6.1 Single-Instruction, Single-Data (SISD)

Instrucao Unica, Dado Unico: Existe uma unica unidade de processamento, que

tem acesso a um unico conjunto de instrucoes e outro de dados. Em cada etapa,

o elemento carrega uma instrucao, o dado correspondente e executa a instrucao. O

resultado e armazenado de volta no armazenador de dados.

2.6.2 Multiple-Instruction, Single-Data (MISD)

Multipla Instrucao, Dado Unico: Existem multiplas unidades de processamento, com

acesso a memoria global. Em cada etapa, cada unidade obtem um dado da memoria

que dividem e carrega uma instrucao. Estas instrucoes, possivelmente diferentes,

sao executadas entao em paralelo pelo processo usando o dado (identico) obtido

previamente como operador. Pouco utilizados, mas exemplos praticos seriam sistemas

de controle que executam a mesma operacao nas unidades de processamento para

mascarar falhas, se algum resultado divergir.


Figura 2.2: Ilustracao de sistema MISD

Figura 2.3: Ilustracao de sistema SIMD

2.6.3 Single-Instruction, Multiple-Data (SIMD)

Instrucao Unica, Dado Multiplo: Existem multiplas unidades de processamento, cada

uma possui um acesso privado a uma mesma memoria, da qual um processador de

controle especial busca e manda instrucoes. Em cada etapa, as unidades obtem do

processador de controle a mesma instrucao e carregam um elemento de dado separado

por seus acessos de dados privados, onde a instrucao e executada. Assim, a instrucao

e aplicada em paralelo para diferentes dados, em sincronia.


2.6.4 Multiple-Instruction, Multiple-Data (MIMD)

Figura 2.4: Ilustracao de sistema MIMD

Instrucao Multipla, Dado Multiplo: Existem multiplas unidades de processamento,

cada uma possui um acesso separado a instrucoes e dados em uma memoria. Em cada

etapa, as unidades individualmente carregam uma instrucao e um elemento de dado,

aplicam a instrucao no dado e armazena um possıvel resultado de volta a memoria.

Os processos trabalham assincronamente entre si.

2.6.5 Single Program, Multiple Data (SPMD)

Esta e um subdivisao do MIMD, para o caso de todos os processadores estarem

executando o mesmo programa em paralelo.

2.6.6 Multiple-Program, Multiple-Data (MPMD)

Esta e um subdivisao do MIMD, para o caso de todos os processadores estarem

executando programas diferentes. Normalmente esses sistemas escolhem um no para

ser o ”host”, do modelo de programacao “host/node explıcito”, ou ”manager”, da

estrategia ”manager/worker”, que executa um programa que arrenda os dados para

Lei de Anhmdal 15

todos os outros nos que executam um segundo programa. Em seguida, esses outros

nos retornam os resultados diretamente para o gerente.

2.7 Lei de Anhmdal

Tambem conhecida como argumento de Amdahl, e usada para encontrar a melhoria

maxima esperada de um sistema global em que apenas uma parte desse sistema e

melhorada. Frequentemente e usada em computacao paralela para prever o aumento

maximo teorico de velocidade utilizando multiplos processadores. A lei tem o nome

do arquiteto de computadores Gene Amdahl, por quem foi apresentada em 1967.

A aceleracao de um programa utilizando multiplos processadores em paralelo e li-

mitada pelo tempo necessario para a fracao sequencial do programa. Por exemplo,

se um programa necessita de um determinado tempo utilizando um unico nucleo do

processador e ao final ha uma porcao particular do programa para ser executado e

essas duas partes nao podem ser colocadas em paralelo, independentemente de quan-

tos processadores sao dedicados a paralelizacao da execucao deste programa, o tempo

mınimo de execucao nao pode ser menos crıtico do que o tempo da porcao final. Por

isso, o aumento de velocidade e limitada a relacao entre este tempo e a primeira parte

do programa. [Amd67] Dado:

O numero de threads de execucao:

n ∈ N

A fraccao do algoritmo, que e estritamente em serie:

B ∈ [0, 1]

O tempo T(n) um algoritmo leva para terminar quando esta sendo executado no n

thread (s) de execucao corresponde a:

T (n) = T (1)(B + 1

n(1−B)

)Portanto, o aumento de velocidade teorica que pode ser obtido por meio da execucao

de um determinado algoritmo em um sistema capaz de executar n segmentos e:

S(n) = T (1)T (n)

= T (1)

T (1)(B+ 1n(1−B))

= 1B+ 1

n(1−B)

MPI 16

2.8 MPI

Message Passing Interface (MPI) e um modelo industrial para interfaces de comunica-

cao de dados em computacao concorrente. Nesse modelo, uma aplicacao e constituıda

por um ou mais processos que se comunicam ao acionar funcoes para o envio e re-

cebimento de mensagens - similar ao que o Erlang normalmente faz. MPI e mais

utilizado na forma de sua biblioteca implementada em C.

2.8.1 MPI Benchmark – IMB

Originalmente fazer ou criar um benchmark e executar, em serie, um programa ou

operacao, a fim de avaliar a performance do sistema ou maquina em questao. Mas

o termo ”benchmark”e tambem usado para os proprios programas de benchmarking

desenvolvidos para efetuar esse processo. Apesar de mais comum como avaliacao de

performance de hardware, ainda ha circunstancias em que o benchmarking e feito

para softwares.

IMB de acordo com sua documentacao, e capaz de fazer uma serie de medidas sobre

a performance de MPI para comunicacao ponto a ponto e operacoes de comunicacao

global para finitos tamanhos de mensagem. Os dados de benchmark gerados po-

dem completamente caracterizar a performance de um sistema de clusters, incluindo

performance de nos, latencia de rede e throughput, assim como a eficiencia da imple-

mentacao de MPI usada. Dentre as implementacoes neste trabalho, constam:

2.8.2 Pingping

Consiste de um processo A que envia uma mensagem para um processo B que, por sua

vez, tambem envia uma mesma mensagem para o processo A. Assim esta montado um

cenario propıcio a obstrucoes, como se chama a situacao de um processo receber uma

mensagem ao mesmo tempo que manda outra. Por isso, Pingping e usado para medir

a eficiencia do tratamento de obstrucoes, registrar o tempo de inicio dos processos e

a vazao de mensagens oferecida pelo sistema.

MPI 17

Figura 2.5: Diagrama do benchmark Pingping

2.8.3 Pingpong

E outra forma classica de medir o processamento de uma unica mensagem enviada

entre dois processos. Pingpong funciona de maneira que um processo A envia uma

mensagem para um processo B e este ao recebe a mensagem de A, responde de volta.

Assim como no Pingping, pode ser medida a eficiencia do tratamento de obstrucoes,

registrar o tempo de inicio dos processos e a vazao de mensagens oferecida pelo

sistema

Figura 2.6: Diagrama do benchmark Pingpong

2.8.4 Threadring

Neste trabalho Threadring e o nome utilizado para o benchmark de transferencia

paralela muito parecido com o Sendrecv. Por seu nome sugestivo pode-se ter um

nocao sobre como ele se comporta, pois consiste de varios processos que formam

MPI 18

uma corrente de comunicacao, em anel. Onde cada processo envia uma mensagem

para o processo “a direita” e recebe uma mensagem de mesmo tamanho do processo

“a esquerda”, em sequencia. A contagem de acoes sao duas mensagens por amostra

(uma entra e uma sai) para cada processo. A atividade em um certo processo acontece

ao mesmo tempo que em outros processos em maquinas diferentes. E deste modo o

benchmark mede a e eficiencia do transcurso da mensagem sob a carga global.

Figura 2.7: Diagrama do benchmark Threadring

2.8.5 Medicoes

Nesses testes e comum medir os tempos para se iniciar os processos e o tempo total

desde o primeiro envio ate que todos recebam suas respectivas mensagens. E nesse

trabalho para se ter uma visao mais ampla, cada benchmark e executado com tama-

nhos de mensagens variantes de x bytes, repetidas outras y vezes e as medidas de

tempo sao uma media de amostras multiplas em cada combinacao de mensagens de

tamanho x, trocadas y vezes.

Esqueletos Algorítmicos 19

2.9 Esqueletos Algorıtmicos

Sao tambem conhecidos como “padroes de paralelismo”, modelos alto nıvel de pro-

gramacao para computacao paralela e distribuıda. Eles tiram proveito dos padroes

de programacao mais simples para esconder a complexidade de aplicacoes concorren-

tes. A partir de um conjunto basico de padroes, chamados esqueletos, padroes mais

complexos podem ser construıdos atraves de combinacao. A caracterıstica mais mar-

cante de esqueletos algorıtmicos e que a orquestracao e sincronizacao das atividades

paralelas e implicitamente definido sob os padroes dos esqueletos: os programadores

nao precisam especificar as sincronizacoes entre as partes sequenciais do aplicativo.

Isso gera duas implicacoes: primeiro, como os padroes de acesso de comunicacao sao

conhecidos com antecedencia, modelos de custos podem ser aplicados para agendar

programas esqueletos; e em segundo lugar, esse tipo de programacao reduz o numero

de erros em relacao aos modelos de programacao paralela tradicionais por exemplo

threads e, previamente mencionado, o MPI.

De acordo com as definicoes logo a cima e o que foi visto no comeco do capıtulo,

Erlang tem uma forte aptidao para a implementacao destes padroes e durante os

experimentos ooErlang tambem se apresentou responsivo. Existem varios modelos

de esqueletos algorıtmicos, mas dentre os principais esqueletos basicos, os escolhidos

para serem abordados neste trabalho sao: Pipe, Reduce, Fork, Map e Farm.

2.9.1 Pipe

Uma sequencia de nos funciona como uma linha de producao, cada no recebe uma en-

trada e manda a saıda para proximo, esses nos podem ter funcoes iguais ou diferentes

desde que suas saıdas e entradas (conexoes) combinem.

2.9.2 Reduce

Caracteriza um esqueleto com varios tipos de ligacao, normalmente com nos dina-

micamente criados para executar a mesma funcao. Muito utilizado em problemas


Figura 2.8: Diagrama do esqueleto algorıtmico Pipe

que podem ser fragmentados em partes menores recursivamente e apenas a ultima

recursao da o resultado final.

Figura 2.9: Diagrama do esqueleto algorıtmico Reduce

2.9.3 Fork, Map e Farm

Caracterizados pela mesma representacao grafica, eles sao similares e exemplos de

uma abordagem conhecida como “Master Slaves”. Pois, ha um no principal que vai

dinamicamente alocar os recursos necessarios utilizando os nos de sua responsabili-

dade. A diferenca esta nos detalhes:

Fork: Funciona como um “switch”. O no principal recebe pedidos que se en-

caixam em categorias: cada categoria dessas e tratada por um tipo diferentes de

processo para o qual o pedido e adequadamente mandado e o resultado aparece na

saıda.

Map: O no “master” faz o mapeamento da estrutura de entrada e manda as


Figura 2.10: Diagrama do esqueleto algorıtmico generico Master and Slave

Figura 2.11: Diagrama do esqueleto algorıtmico Fork

partes mapeadas para os “slaves” resolverem, um a um, entao os resultados enviados

pelos “slaves” sao agrupados na saıda.

Farm: Funciona como um arrendamento do mesmo tipo de “slaves”. Conforme

pedidos vao chegando, o “master” e responsavel por adequadamente passa-los para

os “slaves” usando praticas adequadas de alocacao e os resultados vao diretamente

para saıda.


Figura 2.12: Diagrama do esqueleto algorıtmico MAp

Figura 2.13: Diagrama do esqueleto algorıtmico Farm

Capıtulo 3

Experimentos

Ha varios fatores que influenciam o desempenho de um programa: hardware, me-

moria disponıvel, uso de memoria, algoritmo, entre outros. Apesar de por vezes um

bom desempenho depender mais do algoritmo em si, ao se utilizar algorıtimos clas-

sicos, com codigos bem conhecidos, simples e fatorados, como os do IMB, podemos

estudar o desempenho de uma linguagem de programacao pois, as caracterısticas do

codigo ja sao conhecidas. O que deixa a informacao sobre o que a linguagem e capaz

de fazer sobre este mais evidente, com o experimento executado em um ambiente,

preferencialmente, livre de interferencias e muitas variacoes.

Para se ter ideia do desempenho da programacao distribuıda ao utilizar a linguagem

Erlang, foram escolhidos tres algorıtimos IMB: pingping, pingpong e threadring, an-

teriormente citados e implementados com tecnicas de programacao distribuıda. Os

dois primeiros algoritmos sao de transferencia simples, em que uma unica mensagem

e trocada entre dois processos, um de forma sıncrona e outro assincronamente, e o

ultimo e de transferencia paralela, no qual uma unica mensagem e trocada entre dois

processos, mas ha varios processos em execucao simultaneamente. Todos os tres al-

gorıtimos, no ambito da programacao paralela distribuıda, podem ser considerados

SPMD pela taxonomia de Flynn, pois cada um manda sua propria mensagem (da-

dos multiplos) e executam o mesmo programa (mesmo programa), mudando apenas

a chamada inicial que nao acontece simultaneamente. O resultados dos testes fei-

O ambiente de execução 24

tos a seguir podem montar um benchmarking que consequentemente caracteriza o

desempenho desses programas em Erlang.

3.1 O ambiente de execucao

Cada conjunto de testes de benchmarck foi executado em maquinas de mesma con-

figuracao:

– Sistema Operacional: Ubuntu 11.04 (natty) GNU/Linux 2.6.38-8-server x86 64

– Hardware:

∗ Memoria 4 Gb – DDR2;

∗ Disco Rıgido 250 Gb - Sata 2;

∗ Processador Intel Core 2 Duo CPU E7400 - 2.8 Ghz;

– Erlang R14B03 - (64-bits)

∗ Eshell Versao – 5.8.4

3.2 Conceitos basicos de programacao em Erlang

Aqui nao seram apresentados detalhes de como utilizar a linguagem de programacao

Erlang, apenas algumas explicacoes superficiais de como sua codificacao funciona.

Programas em Erlang sao construıdos atraves de “modules” que contem funcoes invo-

cadas conforme a necessidade pelo programador usando a linha de comando do shell

que da acesso a maquina virtual do Erlang, Eshell, ou chamados por outro module.

Dentro desse “modules” o programador pode escolher quais funcoes sao compiladas e

podem ser acessadas fora do “module”.

As funcoes em si sao definidas pelo nome , sua lista de parametros e o sinal “->” que

indica o comeco dos comandos que sao separados por virgula e terminados por ponto

e vırgula, se houver outra lista de comandos para outro padrao de entrada ou ponto

final, caso nao haja outra comportamento para funcao.

Executando e Depurando Código em Erlang com Erlide 25

O que em outros paradigmas de programacao seriam chamados de variaveis, aqui

nao variam. Nesse contexto, “atoms” em letras maiusculas representam valores que

sao atribuıdos uma unica vez. Por exemplos: “A = 10”, dentro dessa funcao A vai

ser 10 de agora em diante. Com isso, em Erlang, e muito comum usar recursividade

e e justamente na chamada de funcao proxima que os valores sao atualizados. No

exemplo abaixo, a funcao tem como parametro uma lista definida dentro de colchetes

“[]” com a primeira posicao “H” separada pela barra “|” do resto da lista “T” e dentro

ela se invoca, agora adicionando ao fim da lista o valor de H mais 1. Dentro dessa

segunda funcao H vai ser outro valor e o antigo H adicionado de 1 esta no fim da

lista:

1 -module( exemplos ).2 -compile([export_all]).3

4 funcao([H|T]) ->5 funcao([T|H+1]).

Codigo 3.2.1: Codigo Erlang

Mais a frente, a programacao distribuıda em Erlang sera explicado com os codigos

usados para benchmark.

3.3 Executando e Depurando Codigo em Erlangcom Erlide

Primeiro, faz-se justo, falar sobre o Erlide [erlb], uma ferramenta que se propoem a

melhorar a eficiencia do programador a trabalhar com Erlang e foi muito utilizada

neste trabalho.

Erlang ja vem com um depurador de codigo muito completo que permite alem da

visualizacao do que esta acontecendo no programa, a troca de pedacos de codigo,

conhecido pelo termo“hot-swap”. Erlide se une ao Eclipse e tenta trazer essas mesmas

funcionalidades para uma melhor visualizacao com a IDE.

Ao se utilizar o Erlide no Eclipse, quando compilar/depurar (“run” /”debug”) apa-

recera um console de shell do Erlang, com algumas funcionalidades limitadas. Por


outro lado, de acordo com a documentacao dos desenvolvedores dessa IDE, eles ofere-

cem “todos os recursos do depurador padrao, porque o estao usando”. Os breakpoints

podem normalmente ser definidos com um duplo clique do lado esquerdo da linha no

editor de texto e ser feita a execucao passo a passo, assim como a Inspecao e modi-

ficacao de variaveis locais. Mas no caso de processamento distribuıdo a depuracao e

feita em varios nos.

A forma do Eclipse especificar como executar o codigo sendo desenvolvido e chamado

de “launch configurations”. O Erlide fornece suporte para a criacao e execucao de

“launch configurations” especıficas do Erlang. Estas configuracoes podem ser criadas

e editadas em “Run Run configurations...” ou “Debug Debug configurations..” que

oferece algumas opcoes especıficas de depuracao.

A guia principal permite selecionar os projetos cujo codigo sera carregado e execu-

tado. E possıvel tambem definir uma inicializacao propria, fornecendo uma funcao e

argumentos a serem chamados. A guia de “Runtimes” permite definir a versao que

sera usado, o nome do no e cookie (opcional). Para “debug launch configurations”,

a guia “Debug” contem as opcoes relacionadas. A que e especıfica do Erlide e a lista

de modulos interpretados. Os modulos selecionados serao interpretados em conjunto

com qualquer modulo (a partir dos projetos referenciados) que contem um break-

point habilitado. Uma lista similar esta disponıvel na view de ”Interpreted Modules”,

permitindo alterar o status dos modulos durante a depuracao. Uma observacao im-

portante e que se voce usar nomes longos e um no que e iniciado externamente.

O bastante para desenvolver e testar em um ambiente controlado e depois usar o

programa em hosts remotos.

Para finalizar sobre o Erlide: A perspectiva de depuracao normalmente ja traz o

essencial: No canto superior esquerdo a lista de processos e nıveis de execucao. Canto

direito, a lista de variaveis da funcao atual, no meio a esquerda o codigo com a linha

atual marcada em verde, a direita o Outline do modulo e embaixo o console para

I/O. Assim como normalmente no Eclipse, para passar para a proxima linha aperte

(F6), para entrar numa funcao (F5), para percorrer ate o proximo breakpoint (F8),

ou use os botoes abaixo. Ao passar pelas linhas do codigo pode ser que haja uma

parada, provavelmente ocasionada pela espera de mensagens ou input. No primeiro


Figura 3.1: Menu de configuracoes do Erlide

cenario, basta continuar a percorrer o codigo por outro processo, escolhido na lista

de processos presente na aba “Debug” – canto superior esquerdo. No segundo caso,

faca o input necessario. Para mudar o valor de uma variavel, durante a depuracao,

na aba “Variables” – canto superior direito – clique com o botao direito do mouse

sobre a variavel e clique em “Change Values” no menu que aparecera.

Figura 3.2: Perspectiva de depuracao do Erlide

Os programas de benchmark em Erlang 28

3.4 Os programas de benchmark em Erlang

Os algorıtimos escolhidos executam tarefas simples: Pingping consiste de dois pro-

cessos que mandam mensagens assincronamente entre si; Pingpong tambem sao dois

processos, mas comunicando-se sincronamente: o primeiro processo manda uma men-

sagem e aguarda uma resposta, enquanto o segundo aguarda uma mensagem e manda

outra mensagem ao recebe-la; ja o Threadring, como um Sendreceive sequencial, e

formado por um determinado numero de processos que se comunicam numa topologia

de anel ou seja, assim que uma mensagem e recebida, ela e repassada para o proximo

no do anel e isso continua entre os processos ate ser completada uma volta.

Abaixo ha uma reapresentacao grafica do ponto de vista da interacao entre as fun-

coes dos codigos utilizados. Os retangulos verdes representam funcoes que so foram

utilizados por processos, enquanto os azuis representam as que se tonaram processos

e as setas vermelhas indicam a sequencia de “spawning”.

Figura 3.3: Diagrama do codigo do PingPong

Ao comparar as duas figuras anteriores a conclusao e que elas sao iguais. No desenho

muda apenas o nome da funcao principal, mas o codigo sofre real alteracao naque-

las responsaveis pela inicializacao (“start1” e “start2”). Essas duas funcoes existem

para que as duas maquinas participando do experimento, “maquina1“ e “maquina2“,

possam ser inicializadas, se encontrem na rede, tarefa que o proprio Erlang se en-


Figura 3.4: Diagrama do codigo do PingPing

carrega ao saber dos nos presentes na rede, e entao o codigo pode ser executado

adequadamente.

Para o Erlang, criar processos e usar uma das variacoes da BIF (funcao basica in-

terna) “spawn”. Esses processos podem ser mantidos localmente ou globalmente ao

se utilizar as funcoes do module “global” para registra-los e assim poderem esperar

e receber mensagens de outros nos. A seguir esta a estrutura basica interna de um

processo que espera uma mensagem comando“receive”e ao recebe-la envia outra pelo

comando “PID ! mensagem”.

1 receive2 Message [when Guard] >3 Pid ! message;4 end

Codigo 3.4.1: Codigo Erlang para espera e envio de mensagem

No programa PinPing, a funcao “start1”: cria o arquivo que registrara o momento,

tamanho e ordem de todas mensagens trocadas pelo processo; cria um processo local

(utiliza o “spwan”) responsavel por escrever as informacoes no arquivo criado e assim

nao permitir que o tempo de escrita no arquivo influencie o andamento das trocas

de mensagens do processo principal; tambem gera a mensagem a ser passada; cria o

processo principal que entra em espera de suas mensagens, registra seu nome global-

mente, sincroniza com os erlang node que estao na rede e espera que esse processo e o


processo de log sejam terminados. Tal qual, a funcao“start1”do programa PingPong.

A funcao“start2”comeca similar: cria o arquivo de log, o processo responsavel por ele,

a mensagem a ser passada pelo processo principal e o seu proprio processo principal.

Mas entao ela comeca contagem do tempo, manda a mensagem inicial para comecar

as medicoes, espera a mensagem avisando o fim das trocas, finaliza a contagem do

tempo, espera o fim dos registros no arquivo e salva o resultado no arquivo geral. A

diferenca do “start2” do PingPing para o PingPong esta que enquanto no primeiro

ha duas mensagens inciais avisando os dois processos principais, nas duas maquinas,

que o experimento comecou. No segundo, uma mensagem e mandada para apenas

um e ele se encarrega de comecar a troca com o outro.

Diferente dos programas anteriores em que a funcao principal nao mudava de acordo

com o no, Threadring precisou se preocupar com uma certa hierarquia entre os

nos. Os nos do meio do anel nao precisam se preocupar com muito, apenas es-

perar uma mensagem, envia-la para o proximo e terminar quando acabar, porem o

primeiro/ultimo no fica responsavel por inicializar a conexao entre os nos, comecar o

envio de mensagens e tambem o terminar, e para isso precisa de funcoes especiais.

Figura 3.5: Diagrama do codigo do Threadring

A utilizacao deste Threadring e dada da seguinte forma. Os nos que formam o circulo

sao todos inicializados com a funcao“start1”, exceto pelo ultimo. Essa funcao e muito

Conceitos básicos de programação em ooErlang 31

parecida com as anteriores, a diferenca e que o processo principal, gerado dentro delas,

entra em estado de espera ate que o ultimo no seja iniciado, pois e quando ele tem

certeza que pode fazer a conexao com seu vizinho. O ultimo no faz uso da funcao

“start2” que apos preparar todo o necessario para as medicoes inicia o processo em

cadeia que e: mandar este no conectar com o seu proximo, mandar a mensagem “init”

para ele tambem e entrar em estado espera por outra mensagem “init”, o proximo no

ao receber a mensagem se conectara e mandara a mensagem para o proximo, e assim

sucessivamente ate que o primeiro no receba “init” novamente e comece a transmitir

mensagens. Quando seu vizinho receber a mensagem, ele passara para o outro e assim

por diante. Ao fim do experimento, este mesmo no principal manda a mensagem para

que o seu vizinho finalize, este por sua vez enviara a mesma mensagem para o seu

proximo, ate que o no principal receba a mensagem confirmando que todos os outros

terminaram e possa terminar tambem.

3.5 Conceitos basicos de programacao em ooEr-lang

ooErlang e uma extensao que funciona como uma camada acima do codigo em Erlang,

permitindo que os programas sejam modelados em uma abordagem mais orientada

a objetos, com uma sintaxe proxima aquela do Java, e entao o compilador trata de

passa-la para uma forma que o Erlang original possa trabalhar [ooe].

Aqui e feita uma curta introducao a programacao utilizando a esta linguagem. Para

executa-la e preciso o compilador, encontrado repositorio GitHub do projeto, e os

arquivos podem ser feitos em editores de texto simples, desde que sejam salvos com

a extensao “.cerl”. Cada arquivo “cerl” e uma classe que assim como no Erlang lista

apos seu cabecalho quais metodos serao publicos e lugares de onde funcoes podem

ser importadas. Uma classe poder ter ate quatro partes: o cabecalho que contem o

nome da classe, quais classes ela e extensao ou implementa e qual seus construtores;

a lista de atributos; os metodos da classe que sao estaticos; e os metodos normais.

O exemplo a seguir, encontrado no site do projeto [ooe], serve para ilustrar a sintaxe

da linguagem, e importante notar como os dois sımbolos de dois pontos seguidos “::”

servem para acessar atributos e metodos.

Os mesmos programas modelados em ooErlang 32

1 -class(duck).2 -export([display/0, performFly/0, performQuack/0, swim/0]).3

4 attributes.5

6 FlyBehaviour;7 QuackBehaviour.8

9 methods.10

11 display() -> null.12

13 performFly() ->14 Temp1 = self::FlyBehaviour,15 Temp1::fly().16

17 performQuack() ->18 Temp2 = self::QuackBehaviour,19 Temp2::quack().20

21 swim() ->22 io:format("All ducks float, even Decoys!~n").

Codigo 3.5.1: Codigo ooErlang “duck.cerl”

3.6 Os mesmos programas modelados em ooEr-lang

Se os programas acima descritos fossem passados para ooErlang, nao seria tao sim-

ples ou a mesma coisa do que modela-los em uma linguagem puramente orientada a

objetos: como muitas das funcoes precisam ser recursivas, muitos dados que seriam

atributos deveriam ser passados por valor normalmente e por isso seriam metodos

estaticos. A seguir estao os diagramas das principais classes desses programas na

forma descrita a cima. Onde e possıvel ver que os valores que no programa Medidor

em Erlang deveriam ser repassados em toda chamada de funcao se tornam atributos,

enquanto nos outros programas “start1” e “start2” fazem as vezes de construtores.

3.7 A execucao dos experimentos

Os tres programa foram executados em testes com dados de tamanho: dez, cinquenta

e cem kilobytes, com mil, dez mil, cinquenta mil e cem mil execucoes, para se obter

valores de testes desde condicoes leves ate cargas com estresses maiores. Cada com-

binacao de numero de troca de mensagens e tamanho da mensagem trocada foram

repetidos sobre as mesmas condicoes dez vezes. A figura a baixo demonstra a media

As limitações 33

do tempo de execucao de cada teste em relacao ao tamanho da mensagem. Os testes

se mostraram estaveis ao ponto de que a media do tempo gasto de entre cada men-

sagem se manteve fixa e variava apenas com o tamanho da mensagem trocada. Para

os tres programas.

Dessas figuras, a primeira vista identicas, tambem e possıvel inferir que apenas o

tempo da toca de mensagens se altera entre elas. Cada troca de mensagem, volta,

de Pingping, por ser assıncrono, tem praticamente metade do tempo de um volta de

Pingpong que por ser sıncrono precisa esperar que uma mensagem chegue para poder

enviar a outra. E a volta de Threadring tem, por sua vez, tambem quase o dobro

do tempo de uma volta de Pingpong, pois seus processos tambem sao sıncronos e ao

esperar um pelo outro formam dois “Pingpong” em sequencia.

Em seguida dessa figuras ha um grafico que mostra esses valores sobrepostos para

que melhor visualizacao.

3.8 As limitacoes

Nesses experimentos, cada processo esta alocado em uma maquina. No caso dos

algoritmos de transferencia simples, os testes sao relativamente mais simples de serem

feitos por dependerem apenas de duas maquinas, as limitacoes assim ficam por conta

dos sistemas e da rede. Mas, para o ultimo algorıtimo, threadring, que depende de

quantas maquinas conforme for o numero de nos, pode nao ser tao simples, porque

acrescentasse a limitacao de recursos que impede testes com mais de quatro maquinas.

3.9 Os resultados dos experimentos

Ao se repetir os testes com os algoritmos no formato da linguagem ooErlang. A

mesma proporcionalidade vista anteriormente se mantem entre os graficos. Pois o

compilador ooErlang em sua traducao do documento ooErlang para Erlang mantem

as funcoes intactas.

Por motivos de praticidade, nao serao apresentados os graficos da variacao do des-

vio padrao das trocas de mensagens a cada teste, pois, apesar de haver sim alguns

Os resultados dos experimentos 34

nuances, a maior parte do tempo eles se mantiveram no mesmo patamar medio de

0,0003 milissegundos para Pingping e Pingpong e o dobro, 0,0006 milissegundos, para

Threadring. E, sendo assim, a variancia achatou esse nuances de modo a ficar quase

fixa em 3 ∗ 107 para os dois primeiros programas e 3 ∗ 106 para o ultimo.

Mesmo em vista da troca do numero de repeticoes, os testes mantiveram-se sempre

neste formato de onda apresentado: Pingping em e o mais rapido, Pingpong dobra

esse tempo e Threadring tambem dobra o tempo do seu anterior. Podemos assim

confirmar que para Pingping fazer uso da caixa de mensagem fez diferenca, pois

simplesmente mandava sua mensagem e depois esperava receber outra, seguindo sua

caracterıstica assıncrona, enquanto Pingpong que precisava primeiro esperar, depois

enviar uma mensagem e voltar a esperar, seguindo sua caracterıstica sıncrona, dobrou

o tempo. E finalmente Threadring que estava fazendo uso de mais duas maquinas,

tambem aumentou seu tempo na mesma proporcao do aumento de maquinas, afinal,

ele funciona como um Pingpong entre um maior numero de nos. Para finalizar este

capıtulo, sao apresentados tambem os graficos com as medias de tempo totais dos

testes. Estes, idem aos anteriores, mantem as caracterısticas previamente discutidas,

apenas multiplicando o tempo pelo numero de testes.


Figura 3.6: Diagrama de Classes de Benchmark em ooErlang


Figura 3.7: Medida do tempo de troca de mensagens de Pingping

Figura 3.8: Medida do tempo de troca de mensagens de Pingpong


Figura 3.9: Medida do tempo de troca de mensagens de Threadring

Figura 3.10: Sobreposicao da medias do tempo de troca de mensagens dos benchmarks


Figura 3.11: Conjunto dos graficos com as medias totais de tempo

Capıtulo 4

Esqueletos Algorıtmicos emooErlang

A abordagem por esqueletos para programacao paralela tem estudos em varias partes

do mundo. A pesquisa deste trabalho poderia trazer artigos do Chile, Japao, Franca,

Italia e Inglaterra, entre outros. Mas como Murray Cole observa e simplifica em

sua literatura: “Muitos algorıtimos paralelos podem ser caracterizados e classificados

pela sua aderencia a uma ou mais de uma serie de padroes genericos de computacao

e interacao. Por exemplo, ha uma variedade de aplicacoes em processamento de

imagem e de sinais que sao naturalmente expressas como pipelines de processos, com

o paralelismo entre dois estagios de pipeline, dentro de cada etapa de replicacao e/ou

nos outros paralelismo de dados tradicionais.

Programacao com esqueletos propoe que tais padroes sejam abstraıdos e providos

como um kit de ferramentas para programadores, com especificacoes que transcen-

dem variacoes arquiteturais, mas sao implementacoes que reconhecidas para melhorar

a performance. Este nıvel de abstracao torna mais facil para o programador disci-

plinado experimentar com uma variedade de estruturacoes paralelas para uma dada

aplicacao, permitindo uma separacao clara entre os aspectos estruturais e os deta-

lhes de aplicacoes especıficas. Assim, a informacao estrutural explıcita proporcionada

pelo uso de esqueletos permite otimizacoes estaticas e dinamicas da implementacao

subjacente”.

Ou seja, programas paralelos estruturados devem ser concebidos separados em duas

partes: a parte que expressa o que o processo realmente deve fazer; e a que abs-

40

trai e cuida das interacoes e comunicacoes. Neste caso os esqueletos sao estruturas

basicas que podem moldar a infraestrutura necessaria para fazer esta ultima parte

independente.

Seguindo a problematica citada anteriormente. No caso dos exemplos de esqueletos

em ooErlang, aqui apresentados, sempre existe a necessidade de um processo prin-

cipal, “master”, para monitorar os processos que formam o esqueleto, “slaves”, caso

eles terminem inesperadamente ou simplesmente mandem algum mensagem de volta,

feedback. A associacao entre os slaves tambem e feita de forma puramente funcional,

eles so devem saber a identificacao dos outros para a passagem de mensagens e a sua

parte mais processual pode ficar separada dessa estrutura.

Seguindo a problematica citada anteriormente. No caso dos exemplos de esqueletos

em ooErlang, aqui apresentados, sempre existe a necessidade de um processo prin-

cipal (“master”) para monitorar os “slaves”, caso eles terminem inesperadamente ou

simplesmente mandem o resultado de volta. A associacao entre os slaves tambem e

feita de forma puramente funcional, eles so devem saber a identificacao dos outros

para a passagem de mensagens e a sua parte mais processual fica separada dessa

estrutura.

As classes slave podem possuir as funcoes slave(), para cuidar da comunicacao, e

a funcao work() para realizar suas atividades. A representacao UML, apresentada

simplificou esta parte para evitar a confusao pela repeticao dos parametros, o que

acontece e que a funcao slave normalmente repassa tudo necessario para que a funcao

work possa fazer seu trabalho, assim formando a divisao mencionada anteriormente

como pode ser observado dentro de alguns exemplos do apendice.

As classes master dos esqueletos sao diferentes para cada tipo de esqueleto ou slaves

que possuem. Elas normalmente tem mais funcoes, pois devem: gerenciar o acesso aos

recursos, representados pelos slaves; monitora-los; e tambem cuidar da organizacao

dos resultados, quando necessario. Ou seja, possuem muitas responsabilidade de

controle e por isso devem evitar obrigacoes de computacao podendo deixar isso para

outros processos que correm em paralelo.

Os códigos de exemplo 41

Figura 4.1: Diagrama da organizacao generica da biblioteca de esqueletos

4.1 Os codigos de exemplo

Os exemplos de esqueletos algorıtmicos deste trabalho foram desenvolvi-

dos com o compilador de ooErlang encontrado no repositorio GitHub:

https://github.com/jucimarjr/ooerlang e seguindo as instrucoes e informacoes locali-

zadas no site do projeto https://sites.google.com/site/ooerlang1/. Outros exemplos

e mais informacoes podem ser acessadas abertamente nestes repositorios mantidos

pelo Professor Jucimar e seus alunos


Estes exemplos sao pequenas propostas de como os esqueletos poderiam ser organiza-

dos utilizando-se dos recursos do ooErlang e podem vir a ser ampliados na ocasiao de

um problema pequeno o bastante, mas bem definido, ser encontrado para melhores

o teste.

Como as definicoes dos esqueletos ja foram definidas na introducao, a seguir sera

enfezado apenas o funcionamento dos exemplos.

4.1.1 Farm

Este exemplo tenta replicar o comportamento do esqueleto Farm: O esqueleto e

primeiramente definido com um numero de processos que farao tarefas paralelamente.

Neste codigo o master e instanciado com o numero de slaves que ele devera ter,

um metodo trata de preparar esses slaves e, quando pronto, o master pode receber

pedidos direcionados para um slave especıfico que ele vai procurar o PID, identificador

do processo, em sua lista e enviar as requisicoes por mensagem para este que deve

recebe-la e fazer seu trabalho de acordo com o programa definido: no caso, so avisar

que a recebeu e esta a esperar a proxima requisicao. Caso o master receba uma

mensagem de parada, ele cuidara para que todos os slaves recebam uma mensagem

para terminarem sua execucao e casa ele receba uma mensagem de um slave que

“morreu” ele tratara de reiniciar um com a mesma identificacao

Neste caso o master nao precisa se preocupar com os resultados do trabalho dos

slaves, concentra-se em apenas mante-los operantes.

4.1.2 Fork

Este exemplo destina-se a exemplificar o comportamento do esqueleto Fork: O es-

queleto deve tratar de diferentes tipos de slaves. Aqui comecamos com um conjunto

de mestre e escravos como no exemplo anterior. Dependendo da mensagem inicial

do master, processos diferentes sao criados, neste caso ha dois tipos de processos:

o “good guy” e o “bad guy”, mas poderia ser ate mais. Ha a mesma estrutura de

controle do exemplo anterior: existe um metodo criar slaves, outro para cuidar da


lista de identificacoes; outro para enviar a mensagem de termino a todos e os master

tambem reiniciar processos que morrem prematuramente.

Dentro do slave: cada vez que um novo personagem nasce, outro pode ser iniciado

aleatoriamente, assim como ele pode morrer aleatoriamente, para exemplificar como

esse esqueleto poder ter estados dinamicos.

4.1.3 Maps

Este codigo pretende replicar o comportamento do esqueleto Maps: Ele e mais usado

para lidar com problemas de grande porte, pois ele pode quebra-los e enviar suas pecas

para os processos encarregados de resolver cada pedaco e, em seguida, remontar estes

dados. Aqui o master tem a mesmo estrutura de gerenciamento ja discutida, mas

agora recebe uma lista, no lugar de um numero ou funcao, e envia pedacos dassa

lista para seus slaves, que processam esse pedaco e devolvem para o master que vai

reagrupa-la. Na pratico, neste exemplo a lista e multiplicada por dois.

4.1.4 Pipe

Este codigo propoem-se a replicar o comportamento do esqueleto Pipe. Ha uma

fila de processos que precisa ser percorrida em ordem. A estrutura para criacao e

monitoramento do master e similar as outras, mas os slaves sao praparados para saber

quem e o proximo na fila, para passar as mensagens de estado, e o ultimo tem mais

uma funcao para finalizar a tarefa adequadamente. Ao receber um dado numero,

pela funcao principal do esqueleto, “soma”, esse numero passa pela cadeia vinculada

de processos, onde em cada estagio ele e repassado adicionando 1, para produzir o

resultado: a soma dada pelo numero inicial mais o numero de processos.

4.1.5 Reduce

Este e o exemplo mais ludico. O codigo tentar replicar o comportamento do esqueleto

Reduce. O esqueleto e usado para repartir um problema grande, mas com etapas

de resolucao bem definidas para no final apresentar o resultado. No exemplo, em

primeiro lugar deve-se obter uma estrutura de dados, uma lista de animais e seus


nomes. O problema e cuidar de todos ao mesmo tempo. Entao, a lista e dividida

entre os processos projetados para que essa estrutura percorra, neste caso, a acao

aleatoria dos animais. Ao final, o resultado e a solucao do problema: a historia de

vida dos animais.

4.1.6 O teste

Para melhor organizar o codigo, foi criado uma classe “skeleton” generica com um

metodo sobrecarregado “create” encarregado de adequadamente iniciar o esqueleto

requerido, de acordo com a definicao de seu metodo construtor, e passar sua referencia

para uso. Depois foi feita a classe executavel “teste” que funciona como uma lista de

exemplos de utilizacao das classes referenciadas nos ultimos topicos.

Para o esqueleto farm foram criados tres slaves que recebem uma mensagem cada e

depois e enviado o pedido de termino. Ao final desse vem o teste do esquele map com

um vetor de tres posicoes para ser multiplicado por dois e impresso o resultado na tela,

ao fim. No teste do pipe, ha quatro slaves, e e pedido a soma do numero cinco, cujo

resultado deve ser nove. O reduce deve cuidar de tres animais e ao final apresentar

o log de suas vidas. Para finalizar, o esqueleto fork, inicia com um pedido da funcao

do caso “false” e apresenta qual outros pedidos foram gerados em consequencia.

Capıtulo 5

Conclusoes e Trabalhos Futuros

5.1 Conclusoes

No trabalho de tıtulo “Comparacao de desempenho da programacao concorrente en-

tre Java e Erlang utilizando Intel MPI Benchmarks” o autor foi capaz de chegar a

conclusao que o Erlang mostrou-se ser mais eficiente em 75benchmarcks, muito simi-

lares ao feitos aqui, em utilizacoes de transferencias simples e paralela de mensagens

com tamanhos variados e repeticoes sucessivas comparado ao Java, enquanto esta

segunda linguagem teve melhor desempenho em testes de broadcast. Entao, ao ob-

servar o uso dessas transferencias simples e paralelas, em que o Erlang se sobressaiu,

o trabalho aqui apresentado buscou levar essa pesquisa para a programacao distri-

buıda entre computadores. E como pode-se observar Erlang apresentou resultados

estaveis com os tres benchmarks de programacao distribuıda propostos: pingping,

pingpong, threadring, mesmo quando o codigo foi encapsulado dentro do ooErlang.

Sendo assim observa-se que ooErlang oferece os recursos do Erlang e ainda as vanta-

gens da modelagem orientada a objetos. Sendo possıvel tirar vantagem da facilidade

da ja conhecida modelagem e assim comecar prototipos de programacao distribuıda

em Erlang. O que esta muito de acordo com a filosofica de um dos inventores da lin-

guagem, Mike Williams: “Encontre os metodos certos — Design por Prototipagem”.

Apos o aprendizado das diferentes tecnicas, ferramentas e linguagens de programacao

referenciadas neste trabalho e pesquisas conduzidas para a fundamentacao do mesmo:

quanto ao estudo dos esqueletos algorıtmicos em ooErlang, foi constado que e possıvel

escreve-los usando a nova linguagem ooErlang, mas, por nao ter sido encontrado um

Trabalhos Futuros 46

problema pequeno e bem definido o bastante para testa-los mais conclusoes ainda

nao puderam ser feitas para trabalhar a comparacao entre o desempenho de varias

linguagens do programacao em programas distribuıdos. Ha sim estudos, frameworks

e linguagens voltadas exclusivamente para programacao com o uso de esqueletos al-

gorıtmicos, mas por cada uma ter sua caracterısticas e funcionalidades diversificadas,

elas ficaram fora da proposta deste trabalho que concentrou-se na producao de algo-

ritmos de programacao distribuıda em Erlang e sua extensao ooErlang.

5.2 Trabalhos Futuros

Uma extensao como o ooErlang, traz diversas possibilidades de pesquisas e trabalhos

a serem desenvolvidos. A seguir estao listados alguns trabalhos futuros que podem

vir a suceder este:

Teste de desempenho de esqueletos algorıtmicos: Este trabalho pode ser de-

senvolvido para comparacao entre esqueletos feitos de varias maneiras, em diferentes

linguagens de programacao, como por exemplo Java, C], Ruby, Ocaml, etc. Para

isto devem ser desenvolvidos exemplos para utilizar o mesmo tipo esqueleto com as

mesmas entradas e saıdas nessas diversas implementacoes.

Desenvolvimento de um sistema distribuıdo massivo utilizando ooErlang:

Este trabalho teria por objetivo verificar a utilizacao de ooErlang na criacao de

uma sistema massivo, podendo estar relacionado a um sistema de gerenciamento de

requisicoes massivas online, seja em um servidor de jogos ou sistema paralelo que

precise resolver problemas massivos de maneira paralela e distribuıda, por exemplo.

Criacao de um plugin para desenvolvimento em Eclipse, VIM e Emacs:

Esta seria uma boa ferramenta para o desenvolvimento e divulgacao do ooErlang.

Pois, atualmente, a codificacao desta linguagem de programacao e feita sem um

editor que reconheca as caracterısticas proprias de sintaxe do ooErlang, mas entao,

seria possıvel melhorar a experiencia de desenvolvimento de codigo em ooErlang, pois

erros sintaticos seriam encontrados e corrigidos durante a codificacao.

Referencias Bibliograficas

[Amd67] Gene Amdahl. Validity of the single processor approach to achieving large-

scale computing capabilities. In AFIPS Conference Proceedings(30), 1967.

[Arm07] J. Armstrong. Programming Erlang, Software for a Concurrent World.

Publisher, 2007.

[AVA95] Jeffrey D. Ullman Alfred V. Aho, Ravi Sethi. Compiladores - Princıpios,

Tecnicas e Ferramentas. Prentice Hall, 1995.

[Eri80] Ericsson. Erlang: The movie, 1980. archive.org/details/ErlangTheMovie

Acessado em 28/05/2013.

[erla] Erlang community. http://www.erlang.org/ Acessado em 28/10/2013.

[erlb] Erlide project. http://erlide.sourceforge.net Acessado em 03/11/2013.

[Fer06] P. Ferreira. Uma introducao ao erlang. DEI/ISEP, 2006.

[Fly72] Michael J. Flynn. Some computer organizations and their effectiveness. In

IEEE Trans. Comput. C–21 (9), September 1972.

[Heb13] F. Hebert. Learn You Some Erlang for Great Good! No Starch Press, Inc.,

USA, 2013.

[JJ12] L. Santos J. Jr., R. Lins. Comparing the performance of java, erlang

and scala in web 2.0 applications. In IADIS International Journal on

WWW/Internet, 2012.

[Jr.12] Lins R. Jr., J. ooerlang: another object oriented extension to erlang. In

11th ACM SIGPLAN workshop on Erlang, 2012.

[Mat03] Ash Matheson. An introduction to lua, 2003. www.gamedev.net/an-

introduction-to-lua-r1932 Acessado em 28/10/2013.

REFERÊNCIAS BIBLIOGRÁFICAS 48

[ooe] ooerlang project. https://sites.google.com/site/ooerlang1/gettingstarted

Acessado em 03/11/2013.

[Rit93] Dennis M. Ritchie. The development of the c language. In The second ACM

SIGPLAN History of Programming Languages Conference, 1993.

[Str] Bjarne Stroustrup. Evolving a language in and for the real world: C++

1991-2006. Texas AM University: www.research.att.com/ bs.

[wow] Lua. www.wowwiki.com/Lua Acessado em 28/10/2013.

Apendices

Apendice A

Codigos de Benchmark

1 -module( medicoes ).2 -compile([export_all]).3

4 %%-----------------------------------------------------------------------------5 %% printResult( Data, R, Time, OutFile )6 %% imprime o resultado7 %%8 %% Data (binary) = os dados usados no teste9 %% R = quantidade de repetic~oes

10 %% Time (s) = o tempo total do teste11 %% OutFile = o arquivo de saıda12

13 printResult(Data, R, Time_exec, OutFile) ->14 FormatH = "~-9s\t ~-13s\t ~-17s\t ~-11s~n",15 Header = ["#bytes", "#repetitions", "exec_time[sec]", "MBytes/sec"],16 io:format(OutFile, FormatH, Header),17 MBps = bandwidth_calc(Data, Time_exec),18 FormatD = "~-9w\t ~-13w\t ~-17.2f\t ~-11.6f~n",19 io:format(OutFile, FormatD, [size(Data), R, Time_exec, MBps]).20

21 %%-----------------------------------------------------------------------------22 %% printLap( Node, MSg, Now, OutFile )23 %% imprime o resultado da volta24 %%25 %%Node = no que esta fazendo o log26 %% Msg (binary) = os dados usados no teste27 %% Now (s) = a hora28 %% OutFile = processo responsavel pelo arquivo de saıda29

30 printLap(Node, Msg, Now, OutFile) ->31 FormatH = "~-20s\t ~-6s\t ~-25s ~-25s~n",32 Header = ["Node", "Msg", "Time", "{MegaSec,Sec,MicroSec}"],33 io:format(OutFile, FormatH, Header),34 FormatD = "~-20s\t ~-6w\t ~-25w ~-25w~n",35 io:format(OutFile, FormatD, [Node, Msg, calendar:now_to_datetime(Now),Now]).

Codigo A.0.1: Codigo Erlang - Medicoes parte 1

51

1 %%-----------------------------------------------------------------------------2 %% bandwidth_calc(Data, Time)3 %% calcula o trafego na rede baseado no tamanho dos dados e quanto tempo levou4 %%5 %% Data (binary) = os dados usados no teste6 %% Time (s) = o tempo total do teste7

8 bandwidth_calc(Data, Time) ->9 Megabytes = (size(Data) / math:pow(2, 20)),

10 Seconds = (Time * 1.0e-6),11 Megabytes / Seconds.12

13 %%-----------------------------------------------------------------------------14 %% generate_data(Size)15 %% gera um dado de tamanho Size bytes16 %%17 %% Size = integer18

19 generate_data(Size) -> generate_data(Size, []).20

21 generate_data(0, Bytes) ->22 list_to_binary(Bytes);23 generate_data(Size, Bytes) ->24 generate_data(Size - 1, [1 | Bytes]).25

26 %%-----------------------------------------------------------------------------27 %% time_microseg()28 %% captura o tempo atual em microsegundos29

30 time_microseg() ->31 {MS, S, US} = now(),32 (MS * 1.0e+12) + (S * 1.0e+6) + US.

Codigo A.0.2: Codigo Erlang - Medicoes parte 2

52

1 -module( pingping_medicoes ).2 -compile( [export_all] ).3 start1(Ping1, R, DataSize) ->4 OutFileLocation = "out_erl_laps_pingping1.txt",5 case file:open(OutFileLocation, [append]) of6 {error, Why} -> io:format("Falha ao criar arquivo!: ~p~n", Why);7 {ok, OutFile} ->8 Log = spawn(pingping_medicoes, log, [DataSize,OutFile,self()]),9 Data = medicoes:generate_data(DataSize),

10 global:register_name(Ping1, spawn(pingping_medicoes, pingping,11 [Log, Ping1, Data, self(), R])),12 global:sync(),13 finalize(Ping1),14 finalize(Log)15 end.16 start2(PingNode, Ping1, Ping2, R, DataSize) ->17 OutFileLocationLog = "out_erl_laps_pingping2.txt",18 case file:open(OutFileLocationLog, [append]) of19 {error, Why} -> io:format("Falha ao criar arquivo!: ~p~n", Why);20 {ok, OutFileLog} ->21 Log = spawn(pingping_medicoes, log, [DataSize,OutFileLog,self()]),22 OutFileLocation = "out_erl_pingping.txt",23 net_kernel:connect_node(PingNode),24 case file:open(OutFileLocation, [append]) of25 {error, Why} -> io:format("Falha ao criar arquivo! ~p ~n", Why);26 {ok, OutFile} ->27 Data = medicoes:generate_data(DataSize),28 global:register_name(Ping2, spawn(pingping_medicoes, pingping,29 [Log, Ping2, Data, self(), R])),30 global:sync(),31 TimeStart = medicoes:time_microseg(),32 global:send(Ping1,{init, Ping2}),33 global:send(Ping2,{init, Ping1}),34 finalize(Ping2),35 TimeEnd = medicoes:time_microseg(),36 finalize(Log),37 TotalTime = TimeEnd - TimeStart,38 medicoes:printResult(Data, R, TotalTime, OutFile)39 end40 end.

Codigo A.0.3: Codigo Erlang - Pingpign parte 1

53

1 pingping(Log, Self, Data, Parent, 1) ->2 receive3 {init, Recvr} ->4 Log ! {end_log},5 global:send(Recvr,{Self, Data}),6 Parent ! {finish, Self};7 {Recvr, Data} ->8 Log ! {end_log},9 Alive = global:whereis_name(Recvr),

10 if Alive =/= undefined -> global:send(Recvr,{Self, Data}) end,11 Parent ! {finish, Self}12 end;13 pingping(Log, Self, Data, Parent, R) ->14 receive15 {init, Recvr} ->16 Log ! {do_log},17 global:send(Recvr,{Self, Data}),18 pingping(Log,Self, Data, Parent, R-1);19 {Recvr, Data} ->20 Log ! {do_log},21 global:send(Recvr,{Self, Data}),22 pingping(Log,Self, Data, Parent, R-1)23 end.24

25 finalize(P) ->26 receive27 {finish, P} -> ok28 end.29

30 log(Size, OutFile,Parent) ->31 receive32 {do_log} ->33 medicoes:printLap(node(), Size, now(), OutFile),34 log(Size, OutFile, Parent);35 {end_log} ->36 medicoes:printLap(node(), Size, now(), OutFile),37 Parent ! {finish, self()}38 end.

Codigo A.0.4: Codigo Erlang - Pingping parte 2

54

1 -module( pingpong_medicoes ).2 -compile( [export_all] ).3 start1(Pong, R, DataSize) ->4 OutFileLocation = "out_erl_laps_pingpong1.txt",5 case file:open(OutFileLocation, [append]) of6 {error, Why} -> io:format("Falha ao criar arquivo!: ~p~n", Why);7 {ok, OutFile} ->8 Log = spawn(pingpong_medicoes, log, [DataSize,OutFile,self()]),9 Data = medicoes:generate_data(DataSize),

10 global:register_name(Pong, spawn(pingpong_medicoes, pingpong,11 [Log, Pong, Data, self(), R])),12 global:sync(),13 finalize(Pong),14 finalize(Log)15 end.16 start2(PongNode, Pong, Ping, R, DataSize) ->17 OutFileLocationLog = "out_erl_laps_pingpong2.txt",18 case file:open(OutFileLocationLog, [append]) of19 {error, Why} -> io:format("Falha ao criar arquivo!: ~p~n", Why);20 {ok, OutFileLog} ->21 Log = spawn(pingpong_medicoes, log, [DataSize,OutFileLog,self()]),22 OutFileLocation = "out_erl_pingpong.txt",23 net_kernel:connect_node(PongNode),24 case file:open(OutFileLocation, [append]) of25 {error, Why} -> io:format("Falha ao criar arquivo! ~p ~n", Why);26 {ok, OutFile} ->27 Data = medicoes:generate_data(DataSize),28 global:register_name(Ping, spawn(pingpong_medicoes, pingpong,29 [Log, Ping, Data, self(), R])),30 global:sync(),31 TimeStart = medicoes:time_microseg(),32 global:send(Ping,{init, Pong}),33 finalize(Ping),34 TimeEnd = medicoes:time_microseg(),35 finalize(Log),36 TotalTime = TimeEnd - TimeStart,37 medicoes:printResult(Data, R, TotalTime, OutFile)38 end39 end.

Codigo A.0.5: Codigo Erlang - Pingpong parte 1

55

1 pingpong(Log, Self, Data, Parent, 1) ->2 receive3 {init, Recvr} ->4 Log ! {end_log},5 global:send(Recvr,{Self, Data}),6 Parent ! {finish, Self};7 {Recvr, Data} ->8 Log ! {end_log},9 Alive = global:whereis_name(Recvr),

10 if Alive =/= undefined -> global:send(Recvr,{Self, Data}) end,11 Parent ! {finish, Self}12 end;13 pingpong(Log, Self, Data, Parent, R) ->14 receive15 {init, Recvr} ->16 Log ! {do_log},17 global:send(Recvr,{Self, Data}),18 pingpong(Log,Self, Data, Parent, R-1);19 {Recvr, Data} ->20 Log ! {do_log},21 global:send(Recvr,{Self, Data}),22 pingpong(Log,Self, Data, Parent, R-1)23 end.24


30 log(Size, OutFile,Parent) ->31 receive32 {do_log} ->33 medicoes:printLap(node(), Size, now(), OutFile),34 log(Size, OutFile, Parent);35 {end_log} ->36 medicoes:printLap(node(), Size, now(), OutFile),37 Parent ! {finish, self()}38 end.

Codigo A.0.6: Codigo Erlang - Pingpong parte 2

56

1 -module( threadring_medicoes ).2 -compile( [export_all] ).3 start1(This, NxtPr, NxtNd, R, DataSize) ->4 OutFileLocation = "out_erl_laps_threadring.txt",5 case file:open(OutFileLocation, [append]) of6 {error, Why} -> io:format("Falha ao criar arquivo!: ~p~n", Why);7 {ok, OutFile} ->8 Log = spawn(threadring_medicoes, log, [DataSize,OutFile,self()]),9 Data = medicoes:generate_data(DataSize),

10 global:register_name(This, spawn(threadring_medicoes, connection_node,11 [Log, This, NxtPr, NxtNd, Data, self(), R])),12 global:sync(),13 finalize(This),14 finalize(Log)15 end.16 start2(This, NxtPr,NxtNd, R, DataSize) ->17 OutFileLocationLog = "out_erl_laps_threadring.txt",18 case file:open(OutFileLocationLog, [append]) of19 {error, Why} -> io:format("Falha ao criar arquivo!: ~p~n", Why);20 {ok, OutFileLog} ->21 Log = spawn(threadring_medicoes, log, [DataSize,OutFileLog,self()]),22 OutFileLocation = "out_erl_threadring.txt",23 case file:open(OutFileLocation, [append]) of24 {error, Why} -> io:format("Falha ao criar arquivo! ~p ~n", Why);25 {ok, OutFile} ->26 Data = medicoes:generate_data(DataSize),27 global:register_name(This, spawn(threadring_medicoes,28 first_connection_node,[Log, This, NxtPr, NxtNd, Data,29 self(), R])),30 global:sync(),31 TimeStart = medicoes:time_microseg(),32 global:send(This,init),33 finalize(This),34 TimeEnd = medicoes:time_microseg(),35 finalize(Log),36 TotalTime = TimeEnd - TimeStart,37 medicoes:printResult(Data, R, TotalTime, OutFile)38 end39 end.

Codigo A.0.7: Codigo Erlang - Threadring parte 1

57

1 %%first node exception2

3 first_connection_node(Log, Self, NxtPr, NxtNd, Data, Parent, R) ->4 receive5 init ->6 net_kernel:connect_node(NxtNd),7 global:sync(),8 global:send(NxtPr,init),9 first_ring_node(Log, Self, NxtPr, Data, Parent, R)

10 end.11

12 first_ring_node(Log, Self, Peer, Data, Parent, 1) ->13 receive14 init ->15 Log ! end_log,16 global:send(Peer,Data),17 receive %waits last msg from last node18 Data -> Parent ! {finish, Self}19 end;20 Data ->21 Log ! end_log,22 Alive = global:whereis_name(Peer),23 if Alive =/= undefined -> global:send(Peer,Data) end,24 receive %waits last msg from last node25 Data -> Parent ! {finish, Self}26 end27 end;28 first_ring_node(Log, Self, Peer, Data, Parent, R) when R > 1 ->29 receive30 Msg when Msg == init; Msg == Data ->31 Log ! do_log,32 global:send(Peer,Data),33 first_ring_node(Log, Self, Peer, Data, Parent, R-1)34 end.


58

1 %%regular nodes2

3 connection_node(Log, Self, NxtPr, NxtNd, Data, Parent, R) ->4 receive5 init ->6 net_kernel:connect_node(NxtNd),7 global:sync(),8 global:send(NxtPr,init),9 ring_node(Log, Self, NxtPr, Data, Parent, R)

10 end.11

12 ring_node(Log, Self, Peer, Data, Parent, 1) ->13 receive14 Data ->15 Log ! end_log,16 Alive = global:whereis_name(Peer),17 if Alive =/= undefined -> global:send(Peer,Data) end,18 Parent ! {finish, Self}19 end;20 ring_node(Log, Self, Peer, Data, Parent, R) when R > 1 ->21 receive22 Data ->23 Log ! do_log,24 global:send(Peer,Data),25 ring_node(Log, Self, Peer, Data, Parent, R-1)26 end.27

28 %%generic functions29


35 log(Size, OutFile,Parent) ->36 receive37 do_log ->38 medicoes:printLap(node(), Size, now(), OutFile),39 log(Size, OutFile, Parent);40 end_log ->41 medicoes:printLap(node(), Size, now(), OutFile),42 Parent ! {finish, self()}43 end.


Apendice B

Codigos de Biblioteca deEsqueletos

1 -class(farmskeleton).2 -compile(export_all).3 -constructor([new/1]).4 %%this trys to replciate the Skeleton Farm behaviour5 %% the skeleton usually is set first with a number os processes doing different6 %% or concurrent tasks and send the received data to the one designed to receive its kind7 %% here each process receives a messages and says it does something with it8 methods. %%--------------------------------------------------------------------9 new(N) ->register(masterfarm,spawn(farmskeleton,start_slaves,[N,[]])).

10 to_slave(N, Msg) -> masterfarm ! {N, Msg}.11 stop() -> masterfarm ! stop.12 class_methods. %%--------------------------------------------------------------13 lookup_Slave([{M, Slave}|T], N) ->14 if M == N -> Slave;15 true -> lookup_Slave(T, N) end.16 stop_All(Slaves) -> lists:foreach(fun({_, Slave}) -> Slave ! die end, Slaves).17 start_slaves(0,Slaves) ->18 io:format("master:got the slaves ~n"),19 process_flag(trap_exit, true),20 master(Slaves);21 start_slaves(N,Slaves) -> %%creating the processes22 start_slaves(N-1,[{N,spawn_link(farmslave, slavemain,[N])} | Slaves]).23 %%to keep the list o slaves is matter of safety24 master(Slaves) ->25 receive26 stop -> stop_All(Slaves);27 {’EXIT’,_ , N} ->28 io:format("master:restarting dead slave ~w.~n",[N]),29 Slave = spawn_link(farmslave, slavemain,[N]),30 master(lists:keyreplace(N,1,Slaves,{N,Slave}));31 {N, Msg} ->32 Slave = lookup_Slave(Slaves,N),33 Slave ! Msg,34 master(Slaves)35 end.

Codigo B.0.1: Codigo ooErlang - Farm Skeleton

60

1 -class(farmslave).2 -compile(export_all).3

4 class_methods. %%--------------------------------------------------------------5

6 slavemain(N) ->7 receive8 die ->9 io:format("~p morreu~n",[N]),

10 exit(N); % return slave number on exit11 Msg ->12 work(N,Msg),13 slavemain(N)14 end.15

16 work(N,Msg) -> io:format("~p got the ""~p""...working now...’ll be seeing the mail17 box in a sec ~n",[N,Msg]).18

19

Codigo B.0.2: Codigo ooErlang - Farm Slave

61

1 -class(forkskeleton).2 -compile(export_all).3 -constructor([new/1]).4 %% intended to replicate the behaviour of the fork skeleton5 %% here we start a master slave set and depending on the results [messages send6 %% to the master] the new data is going through one of two processes, but could7 %% be mare this examples if the result is false, a bad guy is created, if true,8 %% a good a guy and each time a new character is born, another one migth be9 %% started [randomly] as well as it can die [randomly]

10 methods. %%--------------------------------------------------------------------11 new(BoolFun) -> register(masterfork,spawn(forkskeleton,start_slaves,[BoolFun,[]])).12 stop() -> masterfork ! stop.13 class_methods. %%--------------------------------------------------------------14 lookup_Slave([{M,_, Slave}|T], N) ->15 if M == N -> Slave; true -> lookup_Slave(T, N) end.16 stop_All(Slaves) ->17 lists:foreach(fun({_,_, Slave}) -> Slave ! die end, Slaves).18 start_slaves(BoolFun, Slaves) -> io:format("master made a decision ~n",[]),19 process_flag(trap_exit, true),20 if BoolFun == true -> master(true, [{0,true,spawn_link(fun() ->21 forkslave:slaveTrue(0) end)}]);22 BoolFun == false -> master(false, [{0,false,spawn_link(fun() ->23 forkslave:slaveFalse(0) end)}])24 end, master(BoolFun, Slaves).25 master(BoolFun, Slaves) ->26 receive27 stop -> stop_All(Slaves);28 {’EXIT’,_ , ok} -> ok;29 {’EXIT’,_ , {N,Type}} ->30 io:format("master:restarting dead slave ~w.~n",[N]),31 if Type == true -> master(BoolFun, lists:keyreplace(N,1,Slaves,32 {N,true,spawn_link(fun() -> forkslave:slaveTrue(N) end)}));33 Type == false -> master(BoolFun, lists:keyreplace(N,1,Slaves,34 {N,false,spawn_link (fun() -> forkslave:slaveFalse(N) end)}))35 end;36 true -> N = lists:flatlength(Slaves),37 master(BoolFun, [{N,true,spawn_link(fun() ->38 forkslave:slaveTrue(N) end)}|Slaves]);39 false ->N = lists:flatlength(Slaves),40 master(BoolFun, [{N,false,spawn_link(fun() ->41 forkslave:slaveFalse(N) end)}|Slaves])42 end.

Codigo B.0.3: Codigo ooErlang - Fork Skeleton

62

1 -class(forkslave).2 -compile(export_all).3 class_methods. %%--------------------------------------------------------------4 isReliable(Char) ->5 if Char=="good guy"-> true;6 true -> false7 end.8 character() ->9 random:seed(now()),

10 lists:nth(random:uniform(2), ["good guy", "bad guy"]).11 slaveTrue(N) ->12 random:seed(now()),13 A = random:uniform(2),14 if A == 1 -> masterfork ! true;%%character();15 true -> true16 end,17 receive18 die ->19 io:format("~p morreu~n",[N]),20 exit({N,true}); % return slave number on exit21 start ->22 io:format("~p Good Guy working ~n",[N]),23 A = random:uniform(2),24 if A == 1 -> slaveTrue(N);25 true -> exit(ok)26 end27 end.28 slaveFalse(N) ->29 random:seed(now()),30 A = random:uniform(2),31 if A == 1 -> masterfork ! false;%%character();32 true -> true33 end,34 receive35 die ->36 io:format("~p morreu~n",[N]),37 exit({N,true}); % return slave number on exit38 start ->39 io:format("~p Bad Guy working ~n",[N]),40 A = random:uniform(2),41 if A == 1 -> slaveFalse(N);42 true -> exit(ok)43 end44 end.

Codigo B.0.4: Codigo ooErlang - Fork Slave

63

1 -class(mapskeleton).2 -compile(export_all).3 -constructor([new/1]).4 %%this code intended to replicate the behaviour of the Skeleton Map5 %%used to deal with large codes, it breakes it, sends its parts to the designed6 %%processes and then reassembles it here we recceive a list and give back a list7 methods. %%--------------------------------------------------------------------8 new(N) ->9 Tam = lists:flatlength(N),

10 register(mastermap,spawn(mapskeleton,start_slaves,[0,N,[],Tam])).11 stop() -> mastermap ! stop.12 class_methods. %%--------------------------------------------------------------13 lookup_Slave([{M, Slave}|T], N) -> if M == N -> Slave; true -> lookup_Slave(T, N) end.14 stop_All(Slaves) ->15 lists:foreach(fun({_, Slave}) -> Slave ! die end, Slaves).16 start_slaves(X,[],Slaves,Tam) ->17 io:format("master:got ~p slaves ~n",[X]),18 process_flag(trap_exit, true),19 start_works(Slaves),20 master(Slaves,[],Tam);21 start_slaves(X,[H|T],Slaves,Tam) -> %%dividing the data22 start_slaves(X+1,T,[{X,spawn_link(mapslave, slave,[X,H])} | Slaves],Tam).23 start_works(Slaves) ->24 lists:foreach(fun({_, Slave}) -> Slave ! start end, Slaves).25 master(Slaves,Result,Tam) ->26 Temp = lists:flatlength(Result) ,27 if Tam == Temp ->28 FinalR = [B || {_,B} <- lists:keysort(1, Result)],29 io:format("~n~p~n",[FinalR]),30 stop_All(Slaves),31 exit(kill);32 true -> true33 end,34 receive35 stop -> stop_All(Slaves);36 {’EXIT’,_ , N} ->37 io:format("master:restarting dead slave ~w.~n",[N]),38 Slave = spawn_link(mapslave, slave,[N]),39 master(lists:keyreplace(N,1,Slaves,{N,Slave}),Result,Tam);40 {N, Msg} ->41 master(Slaves,[{N,Msg}|Result],Tam) %%reassembling42 end.

Codigo B.0.5: Codigo ooErlang - Map Skeleton

1 -class(mapslave).2 -compile(export_all).3 class_methods. %%--------------------------------------------------------------4

5 slave(N,Msg) ->6 receive7 die ->8 io:format("~p morreu~n",[N]),9 exit(N); % return slave number on exit

10 start ->11 work(N,Msg),12 slave(N,Msg)13 end.14 work(N,Msg) -> mastermap ! {N,Msg*2}.15

16

Codigo B.0.6: Codigo ooErlang - Map Slave

64

1 -class(pipeskeleton).2 -compile(export_all).3 -constructor([new/1]).4 %%this code intended to replicat the behaviour of the Skeleton Pipe5 %%by receiveng a data [a number X] creating linked chain of X processes and produce6 %%the result: the sum of a number + the number of processes7 methods. %%--------------------------------------------------------------------8 new(N) -> register(masterpipe,spawn(pipeskeleton,start_slaves,[0,N,[]])).9 stop() -> masterpipe ! stop.

10 soma(X) -> masterpipe ! {start,X}.11 class_methods. %%--------------------------------------------------------------12 stop_All(Slaves) -> lists:foreach(fun({Slave,_}) -> Slave ! die end, Slaves).13 start_slaves(_,0,Slaves) ->14 io:format("master:got the slaves ~n"),15 process_flag(trap_exit, true),16 master(Slaves);17 start_slaves(I,1,Slaves) ->18 Name = list_to_atom(lists:flatten(io_lib:format("slave~p", [I]))),19 register(Name,spawn_link(pipeslave, slave,[Name,last])),20 start_slaves(I+1,0,[{Name,last} | Slaves]);21 start_slaves(I,N,Slaves) ->22 Name = list_to_atom(lists:flatten(io_lib:format("slave~p", [I]))),23 Next = list_to_atom(lists:flatten(io_lib:format("slave~p", [I+1]))),24 register(Name,spawn_link(pipeslave, slave,[Name,Next])),25 start_slaves(I+1,N-1,[{Name,Next} | Slaves]).26 %%to keep the list of slaves is a matter of safety27 master(Slaves) ->28 receive29 stop -> stop_All(Slaves);30 {’EXIT’,_ , {N,Next}} ->31 io:format("master:restarting dead slave ~w.~n",[N]),32 Slave = spawn_link(pipeslave, slave,[N,Next]),33 master(lists:keyreplace(N,1,Slaves,{N,Slave}));34 {start,Msg} ->35 slave0 ! Msg,36 master(Slaves)37 end.38

39

Codigo B.0.7: Codigo ooErlang - Pipe Skeleton

1 -class(pipeslave).2 -compile(export_all).3 class_methods. %%--------------------------------------------------------------4 slave(N,Next) ->5 receive6 die ->7 io:format("~p morreu~n",[N]),8 exit({N,Next}); % return slave number on exit9 Msg ->

10 work(N,Msg,Next),11 slave(N,Next)12 end.13 work(N,Msg,last) ->14 io:format("~p got the ""~p""... ~n Result: ""~p"" ~n",[N,Msg,Msg+1]);15 work(N,Msg,Next) ->16 io:format("~p got the ""~p""...working now... ~n",[N,Msg]),17 Next ! Msg+1. %%plus 1 to the result received from the last slave

Codigo B.0.8: Codigo ooErlang - Pipe Slave

65

1 -class(reduceskeleton).2 -compile(export_all).3 -constructor([new/1]).4 %%this code try to replicate the skeleton Reduce behaviour5 %% by first getting a data structur [this example is a list of pet and its names]6 %% breaking it between the designed process they should go through [this case7 %% random action of the pets] when they finish the result is merged [here it was8 %% just collected...]9 methods. %%--------------------------------------------------------------------

10 new(Data) -> register(masterreduce,spawn(reduceskeleton,start_slaves,[Data,11 [],0])).12 stop() -> masterreduce ! stop.13 class_methods. %%--------------------------------------------------------------14 stop_All(Slaves) ->15 lists:foreach(fun({_, Slave}) -> exit(Slave,kill) end, Slaves).16 start_slaves([],Slaves,N) ->17 io:format("master:got ~p pets ~n",[N]),18 master(Slaves,N,[]);19 start_slaves([{Type,Name}|T],Slaves,N) -> %%breaking the data20 process_flag(trap_exit, true),21 case Type of22 dog -> start_slaves(T,[{N,spawn_link(reduceslave, petDog,[N,Name])}23 | Slaves],N+1);24 cat -> start_slaves(T,[{N,spawn_link(reduceslave, petCat,[N,Name])}25 | Slaves],N+1)26 end.27 %in the end, to keep a list of childs is just a matter of safety....28 master(Slaves,FinishedSlaves,Result) ->29 if FinishedSlaves < 1 -> %%check if everything is finished30 io:format("~n~p~n",[Result]),31 stop_All(Slaves),32 exit(kill);33 true -> true34 end,35 receive36 {’EXIT’,_ , {run,Type,Name}} ->37 master(Slaves,FinishedSlaves-1,[{Type,Name}|Result]); %%the merge38 {’EXIT’,_ , {N,Type,Name}} -> %%when they crash they can be restarted39 io:format("master:retriving runaway pet ~p ~p.~n",[Type,Name]),40 case Type of41 dog -> Slave = spawn_link(reduceslave, petDog,[N,Name]),42 master(lists:keyreplace(N,1,Slaves,{N, Slave}),43 FinishedSlaves,Result);44 cat -> Slave = spawn_link(reduceslave, petCat,[N,Name]),45 master(lists:keyreplace(N,1,Slaves,{N, Slave}),46 FinishedSlaves,Result)47 end;48 {’EXIT’,_ , ok} -> ok;49 stop -> stop_All(Slaves)50 end.

Codigo B.0.9: Codigo ooErlang - Reduce Skeleton

66

1 -class(reduceslave).2 -compile(export_all).3 class_methods. %%--------------------------------------------------------------4 petCat(N,Cat) ->5 random:seed(now()),6 case lists:nth(random:uniform(6), actions()) of7 die -> io:format("~p died ~n",[Cat]), exit({run,cat,Cat});8 run -> io:format("~p run away ~n",[Cat]), exit({N,cat,Cat});9 speak -> io:format("~p: meow...meow~n",[Cat]), petCat(N,Cat);

10 eat -> io:format("~p is eating ~n",[Cat]), petCat(N,Cat);11 play -> io:format("~p is playing ~n",[Cat]), petCat(N,Cat);12 sleep -> io:format("~p is sleeping ~n",[Cat]), petCat(N,Cat)13 end.14 petDog(N,Dog) ->15 random:seed(now()),16 case lists:nth(random:uniform(6), actions()) of17 die -> io:format("~p died~n",[Dog]), exit({run,dog,Dog});18 run -> io:format("~p run a way ~n",[Dog]), exit({N,dog,Dog});19 speak -> io:format("~p: wof...wof~n",[Dog]), petDog(N,Dog);20 eat -> io:format("~p is eating ~n",[Dog]), petDog(N,Dog);21 play -> io:format("~p is playing ~n",[Dog]), petDog(N,Dog);22 sleep -> io:format("~p is sleeping ~n",[Dog]), petDog(N,Dog)23 end.24 actions() -> [die,run,speak,eat,play,sleep].

Codigo B.0.10: Codigo ooErlang - Reduce Slave

1 -class(skeletons).2 -compile(export_all).3

4 methods.5

6 create(farm,N) -> farmskeleton::new(N);7 create(fork,B) -> forkskeleton::new(B);8 create(map,C) -> mapskeleton::new(C);9 create(pipe,P) -> pipeskeleton::new(P);

10 create(reduce,L) -> reduceskeleton::new(L).11

Codigo B.0.11: Codigo ooErlang - Biblioteca

67

1 -class(test).2 -export([main/0]).3 class_methods.4 main() ->5 S = skeletons::new_(),6 io:format("~n FARM SKELETON ~n",[]),7 Farm = S::create(farm,3),8 Farm::to_slave(3,"faz a func~aoX"), timer:sleep(1000),9 %%como o main e a aplicacao s~ao processos diferentes e preciso dar um tempo

10 Farm::to_slave(2,"faz a func~aoY"), timer:sleep(1000),11 Farm::to_slave(1,"faz a func~aoZ"), timer:sleep(1000),12 Farm::to_slave(2,die), timer:sleep(1000),13 Farm::to_slave(2,"faz a func~aoW"), timer:sleep(1000),14 Farm::stop(),15 %%16 timer:sleep(5000),17 io:format("~n MAP SKELETON (vetor [1,2,3] x 2) ~n",[]),18 Map = S::create(map,[1,2,3]),19 %%20 timer:sleep(5000),21 io:format("~n PIPE SKELETON ~n",[]),22 Pipe = S::create(pipe,4),23 Pipe::soma(5), timer:sleep(2000), %% here we send the main process to sleep24 Pipe::stop(), %% because otherwise the stop comand would come in the way25 %%26 timer:sleep(5000),27 io:format("~n REDUCE SKELETON ~n",[]),28 Reduce = S::create(reduce,[{dog,"Maroca"},{cat,"Berenice"},{cat,"Bernadette"},29 {dog,"Pingo"},{dog,"Gota"}]),30 %%31 timer:sleep(5000),32 io:format("~n FORK SKELETON ~n",[]),33 Fork = S::create(fork,false),34 timer:sleep(1000), %%sleep otherwise35 Fork::stop(). %%would stop too soon

Codigo B.0.12: Codigo ooErlang - Teste Biblioteca

Documents

ANALISE DE DESEMPENHO DE ALGORITMOS DE …tiagodemelo.info/monografias/2013/tcc-juliana-figueira.pdf · inovadores, por exemplo: C criada e usada para a programac~ao do sistema operacional