André Luis Faria de Oliveira Uéverton dos Santos Souza ... · André Luis Faria de Oliveira Uéverton dos Santos Souza ... 12 Modelo de troca de mensagens.....24 13 Modelo UMA

André Luis Faria de OliveiraUéverton dos Santos Souza

Algoritmos ParalelosDe Ordenação

Trabalho de Conclusão de Curso submetido

ao Curso de Tecnologia em Sistemas de

Computação da Universidade Federal

Fluminense como requisito parcial para

obtenção do grau de Tecnólogo em

Sistemas de Computação.

Orientador:Maise Dantas da Silva

NITERÓI2008

André Luis Faria de OliveiraUéverton dos Santos Souza

ALGORITMOS PARALELOSDE ORDENAÇÃO

Trabalho de Conclusão de Curso submetido

ao Curso de Tecnologia em Sistemas de

Computação da Universidade Federal

Fluminense como requisito parcial para

obtenção do grau de Tecnólogo em

Sistemas de Computação.

Niterói, 28 de Junho de 2008.

Banca Examinadora:

_________________________________________

Profª. Maise Dantas da Silva, M.Sc. – Tutor Orientador

UFRJ – Universidade Federal do Rio de Janeiro

_________________________________________

Prof. Fábio Protti, D.Sc. – Avaliador


_________________________________________

Prof. Danilo Artigas da Rocha, M.Sc. – Avaliador


AGRADECIMENTOS

A Deus, que sempre iluminou a nossa

caminhada.

A toda diretoria do Curso de Tecnologia em

Sistemas de Computação, por nos proporcionar

um excelente curso e um aprendizado

imensurável.

A nossa Orientadora Maise Dantas da Silva,

pelo estímulo e atenção que nos concedeu

durante o curso.

Aos Colegas de curso pela força, motivação e

apoio que sempre nos deram.

RESUMO

Algoritmo nada mais é do que um conjunto de regras e operações bem

definidas e ordenadas, destinadas à solução de um problema ou classe de

problemas em um número finito de etapas, muito utilizado em praticamente todas as

áreas da computação.

Existem algoritmos que são executados paralelamente, levando em conta

arquiteturas de computadores com mais de um processador para executar mais de

uma instrução ao mesmo tempo; tais algoritmos são conhecidos como algoritmos

paralelos.

Um algoritmo paralelo possui diversas características e diversas formas de ser

desenvolvido, mas independente da forma de desenvolvimento, o objetivo principal é

sempre otimizar o tempo de trabalho para o qual ele foi desenvolvido. Entre os

diversos tipos de algoritmos que utilizam a técnica de programação paralela,

podemos citar os de ordenação, que se adaptaram muito bem a esse recurso e que

são muito utilizados.

Este trabalho tem como objetivo estudar algoritmos paralelos de ordenação,

bem como estruturas de dados utilizadas por eles. Por isso, inicialmente, são

estudadas as arquiteturas paralelas e os conceitos relevantes à avaliação do

desempenho de algoritmos paralelos.

Palavras-chaves: algoritmo, paralelismo e ordenação.

LISTA DE ILUSTRAÇÕES

1 Processamento de Dados usando Paralelismo.....................................................15

2 Modelo SISD..........................................................................................................17

3 Computador SISD: PC - Computador....................................................................17

4 Modelo SIMD.........................................................................................................18

5 Computador SIMD: Supercomputador paralelo....................................................18

6 Modelo MISD.........................................................................................................19

7 Modelo MIMD.........................................................................................................20

8 Supercomputador Intel...........................................................................................20

9 Modelo simplificado das relações entre os tipos de arquiteturas..........................21

10 Modelo de memória compartilhada.....................................................................22

11 Modelo de memória distribuída............................................................................23

12 Modelo de troca de mensagens...........................................................................24

13 Modelo UMA........................................................................................................25

14 Modelo NUMA......................................................................................................26

15 Modelo Mestre/Escravo.......................................................................................30

16 Funcionamento do pipeline de cinco estágios.....................................................31

17 Modelo de threads do usuário.............................................................................35

18 Modelo de threads do núcleo...............................................................................35

19 Modelo de threads híbridas.................................................................................35

20 Bubble sort com pipeline .....................................................................................40

21 Odd-Even transposition sort em paralelo............................................................41

22 Funcionamento do Merge Sort seqüencial..........................................................43

23 Funcionamento do Odd-Even Merge Sort...........................................................45

24 Operação de particionar sobre um exemplo de lista ..........................................47

25 Iteração do procedimento particionar..................................................................47

26 Exemplo da aplicação paralela do algoritmo Quick sort......................................49

27 Pares de processos adjacentes do Hyperquicksort............................................51

28 Roteamento para processos adjacentes do Bitonic Sort.....................................53

29 Funcionamento do Rank Sort paralelo................................................................56

30 Ordenação do Counting Sort sobre um vetor de entrada A[1 .. 8]......................58

31 Funcionamento do algoritmo Radix Sort.............................................................61

LISTA DE ALGORITMOS

1 Versão seqüencial do algoritmo Buble Sort...........................................................39

2 Versão seqüencial do algoritmo Odd even transposition......................................41

3 Versão paralela do algoritmo Odd even transposition...........................................41

4 Versão seqüencial do algoritmo Merge Sort..........................................................43

5 Versão paralela do algoritmo Merge Sort..............................................................45

6 Versão seqüencial do algoritmo Quick Sort...........................................................46

7 Versão paralela do algoritmo Quicksort em hipercubo..........................................51

8 Versão paralela do algoritmo Bitonic Sort em hipercubo......................................54

9 Versão seqüencial do algoritmo Rank Sort...........................................................55

10 Versão paralela do algoritmo Rank Sort..............................................................56

11 Versão seqüencial do algoritmo Counting Sort...................................................58

12 Versão paralela do algoritmo Counting Sort........................................................59

13 Versão seqüencial do algoritmo Radix Sort.........................................................61

14 Versão paralela do algoritmo Radix Sort.............................................................62

LISTA DE ABREVIATURAS E SIGLAS

SISD – Instrução Única, Dado Único (Single Instruction, Single Data)

SIMD – Instrução Única, Dados Múltiplos (Single Instruction Multiple Data)

MISD – Múltiplas Instruções, Dado Único (Multipe Instruction, Single Data)

MIMD – Múltiplas Instruções, Dados Múltiplos (Multiple Instruction, Multiple Data)

UMA – Acesso Uniforme à Memória (Uniform Memory Access)

NUMA – Acesso Não Uniforme à Memória (Non-Uniform Memory Access)

NORMA – Acesso Não Remoto à Memória (Non-Remote Memory Access)

API – Interface de Programa de Aplicação (Aplication Program Interface)

MPI – Interface de Passagem de Mensagem (Message Passing Interface)

PVM – Máquina Virtual Paralela (Parallel Virtual Machine)

OPENMP – Multi-Processamento Aberto(Open Multi-Processing)

SUMÁRIO

RESUMO...................................................................................................................04

LISTA DE ILUSTRAÇÕES........................................................................................05

LISTA DE ALGORITMOS.........................................................................................06

LISTA DE ABREVIATURAS E SIGLAS ...................................................................07

CAPÍTULO 1 - INTRODUÇÃO.................................................................................10

1.1 DEFINIÇÕES ...................................................................................................11

1.2 FORMA DE IMPLEMENTAÇÃO PARALELA X SEQÜENCIAL.......................12

CAPÍTULO 2 - ALGORITMOS PARALELOS...........................................................13

2.1 FORMAS DE DECOMPOSIÇÃO......................................................................15

2.2 ARQUITETURAS PARALELAS........................................................................15

2.2.1 CLASSIFICAÇÃO DE FLYNN.....................................................................16

2.2.2 CLASSIFICAÇÃO SEGUNDO O COMPARTILHAMENTO DE MEMÓRIA 21

2.2.3 MULTIPROCESSADORES E MULTICOMPUTADORES...........................24

2.3 BALANCEAMENTO DE CARGA......................................................................27

2.3.1 EFICIÊNCIA.................................................................................................27

2.3.2 ACELERAÇÃO (SPEEDUP)........................................................................27

2.4 TÉCNICAS DE ALGORITMOS PARALELOS..................................................28

2.4.1 DIVISÃO E CONQUISTA.............................................................................28

2.4.2 RANDOMIZAÇÃO........................................................................................29

2.4.3 MESTRE E ESCRAVO................................................................................30

2.4.4 PIPELINE.....................................................................................................30

2.4.5 POOL DE TRABALHO.................................................................................32

CAPÍTULO 3 - LINGUAGENS DE PROGRAMAÇÃO PARALELA..........................33

3.1 PROCESSOS E THREADS..............................................................................33

3.2 PVM (MEMÓRIA DISTRIBUÍDA – TROCA DE MENSAGENS).......................36

3.3 MPI (MEMÓRIA DISTRIBUÍDA – TROCA DE MENSAGENS)........................37

3.4 OPENMP (MEMÓRIA COMPARTILHADA)......................................................37

CAPÍTULO 4 - ALGORITIMOS DE ORDENAÇÃO PARALELOS...........................38

4.1 BUBBLE SORT.................................................................................................39

4.1.1 FUNCIONAMENTO DO ALGORITMO NA FORMA SEQÜENCIAL...........39

4.1.2 FUNCIONAMENTO DO ALGORITMO NA FORMA PARALELA................40

4.1.3 ANÁLISE DAS VERSÕES...........................................................................42

4.2 MERGE SORT..................................................................................................42


4.2.2 FUNCIONAMENTO DO ALGORITMO NA FORMA PARALELA ...............44


4.3 QUICK SORT....................................................................................................46


4.3.2 FUNCIONAMENTO DO ALGORITMO NA FORMA PARALELA ...............48

4.3.3 HYPERQUICKSORT (UMA VARIAÇÃO DO QUICK SORT) .....................50


4.4 BITONIC SORT.................................................................................................52


4.5 RANK SORT.....................................................................................................54




4.6 COUNTING SORT............................................................................................57




4.7 RADIX SORT....................................................................................................60




CONCLUSÃO...........................................................................................................64

REFERÊNCIAS BIBLIOGRÁFICAS........................................................................66

10

1. INTRODUÇÃO

Estruturas de dados e seus algoritmos são temas fundamentais em

computação, utilizados em praticamente todas as suas áreas [Szwarcfiter,1994].

O desenvolvimento de aplicações computacionais tem passado por ligeiras

evoluções, e em algumas se faz necessário um alto poder de processamento para

que se obtenham resultados rápidos e satisfatórios. Para que tais resultados sejam

obtidos, é necessária a utilização de programação paralela e de computadores com

arquiteturas de processamento mais poderosas. A utilização de programação

paralela faz com que se tenha um maior desempenho no desenvolvimento de

sistemas.

Grande parte dos algoritmos utilizados hoje em dia utiliza a ordenação para

que os dados sejam acessados eficientemente, e para tal ordenação existem

diversas formas de implementação.

As operações de ordenação de dados podem ser usadas, por exemplo, para

resolver problemas de teoria dos grafos, computação geométrica e processamento

de imagem. Por essa razão, a ordenação tem uma importância adicional para os

desenvolvedores de algoritmos paralelos, pois diversas versões para funcionamento

em paralelo destes algoritmos são desenvolvidas, com o objetivo de diminuir

consideravelmente o tempo de execução dos mesmos.

Este trabalho tem como objetivo estudar algoritmos paralelos de ordenação,

bem como as estruturas de dados utilizadas por eles.

Primeiramente, vamos definir o que é um algoritmo, para então abordarmos

técnicas de implementação paralela. Como tema central desse trabalho, serão

estudadas as formas paralelas de alguns algoritmos tradicionais de ordenação.

11

1.1 Definições

Um algoritmo é uma seqüência não ambígua de instruções que é executada

até que determinada condição se torne verdadeira [Aurélio,2002]. Mais

especificamente, em matemática, constitui o conjunto de processos para efetuar um

cálculo, como, por exemplo, o cálculo de uma área.

O conceito de algoritmo é freqüentemente ilustrado pelo exemplo de uma

receita, embora muitos algoritmos sejam muito mais complexos. Eles podem repetir

passos (fazer iterações) ou necessitar de decisões (tais como comparações ou

lógica) até que a tarefa seja completada.

Um algoritmo não representa, necessariamente, um programa de computador,

mas apenas os passos necessários para realizar uma dada tarefa e que somente irá

resolver um problema se estiver implementado corretamente e for apropriado ao

problema.

A implementação de um algoritmo pode ser feita por um computador, ou

mesmo por um ser humano. Existem diferentes algoritmos que podem realizar a

mesma tarefa usando um conjunto diferenciado de instruções em mais ou menos

tempo, espaço ou esforço do que outros. Essa diferença pode ser reflexo da

complexidade aplicada, que depende também de estruturas de dados adequadas

para o algoritmo. Por exemplo, um algoritmo para se vestir pode especificar várias

formas de você se vestir; em um você pode calçar as meias antes de vestir as

calças, já em outro a ordem das execuções das tarefas pode ser diferente, mas o

objetivo do algoritmo é o mesmo. Fica bem claro o seguinte: um algoritmo pode ser

mais custoso de executar do que o outro, mesmo que suas funções sejam as

mesmas.

Então, de forma bem resumida, um algoritmo nada mais é do que conjunto de

operações bem definidas e ordenadas, destinadas à solução de um problema ou

classe de problemas em um número finito de etapas.

12

1.2 Forma de implementação paralela X seqüencial

Um algoritmo pode ser classificado de diversas formas, inclusive pela maneira

que ele foi implementado. Quanto à forma de implementação, o algoritmo pode ser

classificado como seqüencial ou paralelo.

Atualmente, a maioria dos algoritmos utilizados se baseia em seqüências de

passos, de forma que cada passo consiste de operações que são executadas de

uma única vez. Estes algoritmos, denominados algoritmos seqüenciais, são bem

ajustados aos computadores de hoje, que basicamente processam operações de

maneira igualmente seqüencial.

O aumento da velocidade com que computadores seqüenciais operam tem um

custo muito alto. A busca por um custo menor proporcionou a construção de

computadores paralelos (computadores que processam operações múltiplas em um

passo único). No entanto, para se resolver um problema eficientemente em um

computador paralelo, aproveitando todos os seus recursos, é usualmente necessário

projetar algoritmos que especifiquem múltiplas operações a cada passo, isto é, um

algoritmo paralelo.

13

2. ALGORITMOS PARALELOS

Os algoritmos seqüenciais são executados instrução a instrução, como se

fosse uma lista de instruções a ser percorrida, onde cada instrução é executada de

uma única vez [Cormen,2002].

Por outro lado, existem algoritmos que são executados paralelamente, levando

em conta arquiteturas de computadores com mais de um processador para executar

mais de uma instrução ao mesmo tempo. Tais algoritmos dividem os problemas em

subproblemas e os repassam a quantos processadores estiverem disponíveis,

juntando no final os resultados do processamento desses subproblemas em um

resultado final. Tal conceito é base para a programação paralela. Entretanto,

igualmente em um computador com um único processador, o paralelismo pode ser

explorado utilizando-se recursos que aproveitam o tempo ocioso do processador.

Por exemplo, quando temos um determinado processo que está sendo executado

pelo processador e este, por algum motivo, interrompe sua execução, aguardando

uma resposta externa, podemos iniciar a execução de outro processo, explorando

assim o intervalo que o processo inicial teve no aguardo de uma resposta, simulando

assim certo grau de paralelismo, onde reduzimos o tempo que teríamos que

aguardar para termos os dois processos finalizados, se tivéssemos que esperar o

processo inicial terminar para podermos executar o segundo. Então, é importante

diferenciar paralelismo em um algoritmo e a capacidade de cada computador de

simular um certo nível de paralelismo. O algoritmo paralelo deve ser executado

eficientemente em qualquer computador e ter, ao menos, o mesmo nível de

paralelismo que o computador, para que recursos não sejam deixados inativos.

A computação paralela engloba uma grande variedade de aplicações, tanto no

campo científico (Física, Química, Matemática, Engenharia, Medicina), como na área

comercial (Computação Gráfica, Sistemas de Banco de Dados) ou mesmo gerencial.

O grande desafio para os matemáticos interessados na programação paralela é,

além de gerar algoritmos paralelos, programá-los de forma eficiente.

De uma forma geral, algoritmos seqüenciais são paralelizáveis. Alguns

algoritmos são fáceis de dividir em partes. Por exemplo, suponha que desejamos

dividir o trabalho de verificar todos os números de um a cem para ver quais são

14

múltiplos de dois. Usando o contexto de algoritmos paralelos, isso poderia ser feito

atribuindo um subconjunto dos números a cada processador disponível, diminuindo

assim a complexidade computacional. Por outro lado, existem problemas que não

são paralelizáveis, chamados então problemas inerentemente seqüenciais

[Bertsekas,1989], como, por exemplo, algoritmos que são executados em passo

único, ou algoritmos em que cada passo após o primeiro dependa de uma resposta

de seu passo anterior para ser executado .

Dentro do contexto computacional, um algoritmo paralelo, ao contrário de um

algoritmo seqüencial tradicional, é um que pode executar, em um mesmo instante,

partes independentes de um mesmo problema, onde cada parte é processada em

dispositivos processadores diferentes, para assim se chegar ao resultado correto.

Os algoritmos paralelos são valiosos, porque são a maneira mais rápida de se

executar tarefas, computando grandes quantidades de informação. Através do uso

de um algoritmo paralelo, podemos usar de uma maneira bem proveitosa todos os

recursos que os processadores modernos possuem.

Os algoritmos paralelos nos fornecem várias vantagens em relação aos

algoritmos seqüenciais, dentre as quais podemos citar:

• A redução do tempo de execução, pois se um programa seqüencial precisa de

t unidades de tempo para executar em um único processador então, idealmente, um

programa paralelo equivalente completaria a tarefa em t/p unidades de tempo

quando executado em p processadores;

• O aumento da quantidade de memória, já que, se um programa precisa de w

palavras de memória e cada processador tem w/p palavras disponíveis, então p

processadores ofereceriam conjuntamente a capacidade necessária.

O paralelismo em um algoritmo pode aumentar o desempenho de vários tipos

de arquiteturas de computador, mas antes de analisarmos os algoritmos produzidos

de forma paralela, alguns conceitos de extrema importância devem ser analisados.

15

2.1 Formas de Decomposição

O paralelismo pode ser definido como uma técnica utilizada em tarefas grandes

e complexas para se obter resultados da forma mais rápida, dividindo a tarefa

principal em subtarefas menores, que serão distribuídas em vários processadores

para serem executadas simultaneamente. Abaixo podemos ter uma idéia de como

funciona:

Quando desejamos desenvolver programas em ambientes paralelos, o primeiro

passo a ser estudado é a forma como o algoritmo pode ser paralelizado.

Para se decompor um algoritmo em pequenas tarefas que serão executadas em

paralelo, é necessário determinar a decomposição funcional e a decomposição de

domínio. Quando um problema é decomposto em diferentes tarefas, gerando assim,

diversos programas que serão distribuídos entre múltiplos processadores para

execução simultânea, surge a decomposição funcional. Quando ocorre a

decomposição dos dados em grupos, que serão distribuídos entre múltiplos

processadores que executarão, simultaneamente, um mesmo programa, tem-se a

decomposição de domínio.

2.2 Arquiteturas Paralelas

O processamento paralelo vem sendo usado há algum tempo; o seu início é

considerado junto ao surgimento do computador ILLIAC IV, construído na

Universidade de Illinois em 1971, com 64 processadores [Amorim,1988]

Problema a ser resolvido (Tarefa Principal)

complexaTarefa 1 Tarefa 2 Tarefa 3

Processador 1 Processador 2 Processador 3

Figura 1: Processamento de Dados usando Paralelismo.

16

[Navaux,1989], porém nunca foi de domínio público e sempre permaneceu na

obscuridade dos laboratórios acadêmicos, inatingível ao grande público. No entanto,

isto vem se modificando, tendo como principal alavancador de sua popularização o

software livre.

Para entendermos melhor o desempenho dos algoritmos paralelos e a forma

que os mesmos são desenvolvidos, devemos conhecer algumas classificações de

arquiteturas existentes.

2.2.1 Classificação de Flynn

A Classificação de Flynn tem como princípio que a execução de um conjunto

de instruções sobre um conjunto de dados é o tópico mais importante de processo

de um computador, ou, em outras palavras, ela se baseia no fato de um computador

executar uma seqüência de instruções sobre uma seqüência de dados,

diferenciando-se o fluxo de instruções (instruction stream) e o fluxo de dados (data

stream). Por fluxo compreende-se uma seqüência de instruções ou dados

executados em um único processador, onde:

• fluxo de instruções é uma seqüência de instruções executados por uma máquina;

• fluxo de dados é uma seqüência de dados, inclusive de entrada, resultados parciais

e intermediários, utilizados pelo fluxo de instruções;

Baseado nestes conceitos, Michael Flynn classificou, em 1972, os diversos

modelos de arquiteturas de computadores. Essa classificação baseou-se no número

de fluxos de dados e de instruções existentes em cada instante, produzindo

principalmente quatro classes de computadores:

2.2.1.1 SISD (Single Instruction, Single Data – Instrução Única, Dado Único)

É a classe mais simples, onde o equipamento é considerado seqüencial, pois

só é executada uma instrução por vez para cada dado enviado. As instruções são

executadas seqüencialmente, mas podem ser sobrepostas nos seus estágios de

17

execução (pipeline). São as máquinas Von Neumann tradicionais, sem qualquer tipo

de paralelismo.

Figura 2: Modelo SISD.

Como exemplo, temos os microcomputadores pessoais e as estações de trabalho.

2.2.1.2 SIMD (Single Instruction, Multiple Data – Instrução Única, Dados Múltiplos)

É o equivalente ao paralelismo de dados, onde uma simples instrução é

executada paralelamente utilizando vários dados. Nesta arquitetura paralela, uma

única instrução, através de uma unidade de controle, é executada de forma síncrona

sobre um conjunto de dados diferentes, distribuídos ao longo de processadores

elementares. Neste contexto, podemos citar a tecnologia MMX – Extensão

Figura 3: Computador SISD: PC – Computador.

18

multimídia (MultiMedia eXtension), utilizada pelos processadores atuais para

processamento de recursos multimídia (imagem, som, etc) e processamento vetorial.

Figura 4: Modelo SIMD.

Como exemplo, podemos citar o CM-2, que é um supercomputador massivamente

paralelo com 65.536 processadores.

2.2.1.3 MISD (Multipe Instruction, Single Data – Instruções Múltiplas, Dado Único)

Teoricamente, são máquinas que executam várias instruções ao mesmo tempo

para um único dado; diferentes instruções operam a mesma posição de memória ao

mesmo tempo, executando instruções diferentes. Imaginar uma máquina como essa

não faz sentido. Além de ser impraticável tecnicamente, não existe nenhuma

Figura 5: Computador SIMD: Supercomputador paralelo.

19

representação real dela, tendo inclusive o próprio Flynn duvidado que algum dia isso

pudesse acontecer.

Essa arquitetura seria muito útil, caso sua representação fosse real, em

problemas como os de quebra de criptografia, onde sua utilização seria mais

eficiente do que uma máquina com vários processadores tentando quebrar esse

código, resolvendo assim este problema mais facilmente e com menor custo.

Figura 6: Modelo MISD.

2.2.1.4 MIMD (Multiple Instruction, Multiple Data – Instruções Múltiplas, Dados Múltiplos)

É o modelo de processamento paralelo no qual cada processador age

independentemente, ocasionando, portanto, múltiplos fluxos de instruções e

múltiplos dados. Neste modelo, temos vários contadores de programa e diferentes

dados (são os vários computadores paralelos e distribuídos atuais).

20

Figura 7: Modelo MIMD.

Como exemplo, podemos citar o supercomputador Paragon, produzido pela

Intel.

Na Figura 9, temos um pequeno esquema das relações entre as arquiteturas

classificadas por Flynn, onde podemos ver que a arquitetura MIMD, que executa

várias instruções ao mesmo tempo para vários dados, engloba as demais

classificações, que são a arquitetura SIMD, que executa somente uma instrução

utilizando vários dados em um determinado instante, e a arquitetura MISD que

executa várias instruções para um dado único. A arquitetura SISD, que executa uma

única instrução por vez para cada dado enviado, é a intersecção da arquitetura

Figura 8: Supercomputador Intel.

..Intel

21

SIMD (executa uma instrução por vez para vários dados) com a arquitetura MISD

(executa várias instruções para um único dado).

Figura 9: Modelo simplificado das relações entre os tipos de arquiteturas.

Dentre todas as classificações de arquiteturas existentes, a Classificação de

Flynn é a mais utilizada e tem como base a quantidade de instruções e dados

processados em um determinado momento, embora não seja abrangente o

suficiente para incluir alguns computadores modernos (como por exemplo,

processadores vetoriais e máquinas de fluxo de dados). Outro inconveniente dessa

classificação é a falta de hierarquia. A classificação MIMD, por exemplo, engloba

quase todas as arquiteturas paralelas sem apresentar subníveis. No entanto, apesar

de antiga (proposta em 1972) a classificação de Flynn é bastante concisa.

2.2.2 Classificação segundo o compartilhamento de memória – (Categorias MIMD)

O custo (ou a complexidade) dos algoritmos é estimado nos termos do espaço

(memória) e do tempo (ciclos do processador) consumidos. Com isso, os algoritmos

paralelos necessitam aperfeiçoar mais um recurso, que é a comunicação entre

processadores diferentes. Esse aperfeiçoamento pode ser obtido, por exemplo, pelo

uso de memória compartilhada ou de memória distribuída.

22

2.2.2.1 Memória Compartilhada

Em uma memória compartilhada (shared memory), existe um único espaço de

endereçamento, que será usado de forma implícita para comunicação entre

processadores. Em outras palavras, diferentes processadores acessam uma mesma

memória compartilhando os dados entre si.

Figura 10: Modelo de memória compartilhada.

2.2.2.2 Memória Distribuída

Quando a memória não é compartilhada, existem múltiplos espaços de

endereçamento privados (multiple private address spaces), um para cada

processador. Esse modelo de memória é chamado de memória distribuída.

A memória distribuída (distributed memory) refere-se à localização física da

memória. Se a memória é implementada com vários módulos, e cada módulo foi

colocado próximo de um processador, então a memória é considerada distribuída.

Em outras palavras, uma memória é distribuída quando cada processador possui

sua própria memória, de forma que os dados devem ser trocados entre os

processadores por mecanismos específicos de troca.

23

Figura 11: Modelo de memória distribuída.

No modelo de memória distribuída, um dos mecanismos de comunicação mais

comuns é o de troca de mensagens, que consiste em processos seqüenciais

trocando informações entre si.

Em um sistema de troca de mensagens, os processadores devem ser

sincronizados para receberem e/ou enviarem mensagens. Essas mensagens podem

ser síncronas ou assíncronas:

Síncrona: comunicação na qual o processador que envia a mensagem aguarda, do

destinatário, o recebimento de um sinal confirmando o recebimento da mensagem.

Assíncrona: comunicação na qual o processador que envia a mensagem não

espera que haja um sinal de recebimento dessa mensagem pelo destinatário.

Tais mensagens podem ainda ser de um dos três tipos:

Um - para - Um: um processador enviando mensagem para outro.

Um - para - Muitos: um processador enviando mensagem para outros, não todos.

Um - para - Todos: um processador enviando mensagem para todos os outros.

24

Figura 12: Modelo de troca de mensagens.

2.2.3 Multiprocessadores e Multicomputadores

Outra alternativa à troca de mensagem é o uso de uma memória centralizada

(centralized memory). Neste caso, a memória encontra-se à mesma distância de

todos os processadores, independentemente de ter sido implementada com um ou

vários módulos. Independentemente do uso de uma memória compartilhada, uma

máquina paralela pode utilizar multiprocessadores, ou ser formada por

multicomputadores:

Multiprocessadores: Todos os processadores acessam, através de uma rede

de interconexão, uma memória compartilhada. Esse tipo de máquina possui apenas

um espaço de endereçamento, de forma que todos os processadores são capazes

de endereçar todas as memórias. A comunicação entre processos é feita através da

memória compartilhada de forma bastante eficiente com operações do tipo load e

stored. Essas características resultam do fato desse tipo de máquina paralela ser

construída a partir da replicação apenas do componente processador de uma

arquitetura convencional. Daí o nome múltiplos processadores.

O acesso às memórias do sistema por multiprocessadores pode ser

classificado como:

25

• Acesso uniforme à memória – UMA (Uniform Memory Access)

Neste tipo de acesso, a memória M utilizada é centralizada e encontra-se à

mesma distância de todos os processadores P, fazendo com que a latência de

acesso à memória seja igual para todos os processadores do sistema.

Muitas das máquinas com esse tipo de acesso utilizam uma memória cache

para amenizar a diferença de velocidade entre processador e memória principal.

Para cada consulta feita à memória principal, é mantida uma cópia na memória

cache, com o objetivo de acelerar um novo acesso ao mesmo endereço. Como

todos os processadores podem endereçar toda a memória do sistema, em um

determinado momento, várias cópias da mesma posição de memória principal

podem existir em caches diferentes. Isso caracteriza um problema, pois um

processador pode trabalhar com sua cópia local e esta não refletir mais o estado

atual do mesmo endereço na memória principal. Este problema é chamado de

coerência de cache (cache coherence). A maioria dos multiprocessadores UMA trata

esse problema através do hardware.

Figura 13: Modelo UMA.

• Acesso não uniforme à memória – NUMA (Non-Uniform Memory Access)

Neste caso, a memória é distribuída e implementada com múltiplos módulos,

de forma que cada módulo é associado a um processador. O espaço de

endereçamento é único, e cada processador pode endereçar toda a memória do

sistema. Se o endereço gerado pelo processador encontrar-se no módulo de

memória diretamente ligado a ele, dito local, o tempo de acesso será menor que a

um módulo que está diretamente ligado a um outro processador, dito remoto, que só

26

pode ser acessado através da rede de interconexão. Por esse motivo, essas

máquinas possuem um acesso não uniforme à memória.

Figura 14: Modelo NUMA.

Multicomputadores: Cada processador P possui uma memória local M, à qual

só ele tem acesso. As memórias dos outros processadores são consideradas

memórias remotas e possuem espaços de endereçamento distintos (um endereço

gerado pelo processador P1 só é capaz de endereçar a memória M1). Como não é

possível o uso de variáveis compartilhadas nesse ambiente, a troca de informações

com outros processos é feita por envio de mensagens pela rede de interconexão.

Por essa razão, essas máquinas também são chamadas de sistemas de troca de

mensagens (message passing systems). Essas características resultam do fato

desse tipo de máquina paralela ser construído a partir da replicação de toda a

arquitetura convencional, e não apenas do componente processador como nos

multiprocessadores. Daí o nome múltiplos computadores.

Multicomputadores podem ainda ser classificados de acordo com seu acesso à

memória:

• Acesso à memória não remota - NORMA (Non-Remote Memory Access). Como

uma arquitetura tradicional inteira foi replicada na construção dessas máquinas, os

registradores de endereçamento de cada máquina só conseguem endereçar a sua

memória local.

27

2.3 Balanceamento de Carga

Outro conceito importante é o balanceamento de carga (Load Balancing). A

distribuição das tarefas entre os processadores deve ser realizada de forma que o

tempo da execução paralela seja eficiente. Se as tarefas não forem bem

distribuídas, pode ocorrer a espera pelo término do processamento de uma única

tarefa por todo o sistema.

As medidas mais aceitas para se avaliar o desempenho de programas

paralelos são a eficiência e a aceleração.

2.3.1 Eficiência

É a medida da eficácia de um algoritmo paralelo quanto à utilização do tempo

nos vários processadores, e é dada pela seguinte expressão:

E(P,N) = Ts / P * Tp,

onde:

P é o número de processadores envolvidos na aplicação;

N é a dimensão do problema considerado;

Ts é o tempo de execução do algoritmo s seqüencial, onde s é o algoritmo

seqüencial correspondente ao paralelo;

Tp é o tempo de execução do algoritmo paralelo, considerando-se p processadores.

Quanto mais próximo de 1 for E(P,N), melhor é a eficiência do algoritmo.

2.3.2 Aceleração (Speedup)

É a razão entre o tempo de execução necessário para o algoritmo seqüencial

mais eficiente e o tempo necessário para se realizar a mesma computação em uma

máquina paralela. Existem diversas variações do conceito de speedup:

Speedup absoluto(n) = (tempo de execução do melhor algoritmo seqüencial) /

(tempo de execução do programa paralelo com n processadores).

28

Speedup aproximado(n) = (tempo de execução do programa paralelo com 1

processador) / (tempo de execução do programa paralelo com n processadores).

Speedup relativo (n) = (tempo de execução do programa paralelo com (n-1)

processadores) / (tempo de execução do programa paralelo com n processadores).

2.4 Técnicas de Algoritmos Paralelos

Assim como nos algoritmos seqüenciais, existem muitas técnicas para o

desenvolvimento de algoritmos paralelos. Algumas destas técnicas são variações

das técnicas seqüenciais, enquanto outras são específicas para algoritmos

paralelos. A seguir essas técnicas serão abordadas.

2.4.1 Divisão e Conquista

Um algoritmo de divisão e conquista tem como característica dividir um

problema maior em partes menores, formando assim pequenos problemas que são

simples de serem resolvidos. Dessa forma, com a solução dessas pequenas partes,

podemos obter a solução do problema maior através da junção da solução das

pequenas partes.

O paradigma da Divisão e Conquista aumenta a modularidade e geralmente

guia a algoritmos simples e eficientes. Esta técnica é considerada uma ferramenta

poderosa para solução de problemas seqüenciais, e tem um papel tão importante

quanto este na programação paralela. A grande vantagem desta técnica é que,

geralmente, um problema é dividido em subproblemas que são resolvidos de forma

totalmente independente, o que permite a paralelização de maneira trivial, no

instante da divisão. Esta técnica mostrou-se bastante poderosa para a programação

paralela, apesar de desvantagens que podem ser minimizadas, o que a torna muito

usada no desenvolvimento de algoritmos paralelos.

2.4.2 Randomização

29

Números aleatórios são usados em algoritmos paralelos para garantir que

certas decisões locais possam, com grande probabilidade, fornecer boas decisões

globais, além de quebrar a previsibilidade do algoritmo.

2.4.2.1 Amostragem (Sampling)

Uma utilização da aleatoriedade é escolher uma amostra que represente bem

um determinado conjunto. Em alguns casos, um problema pode ser solucionado

através da seleção de uma amostra. Resolve-se o problema na amostra e, então, a

solução da amostra guiará a solução para o conjunto original. A amostragem com

randomização é usada em muitas áreas, como geometria computacional, grafos, e

algoritmos de comparação de cadeias de caracteres.

2.4.2.2 Quebra de Simetria (Symmetry Breaking)

Uma outra utilização da randomização é a quebra de simetria, como, por

exemplo, a seleção de um conjunto de vértices independentes de um grafo (neste

conjunto os vértices não são vizinhos dois a dois). Na resolução em paralelo, cada

vértice deve decidir, em paralelo com os outros, se ele entra ou não no conjunto, e

se ele entrar, seus vizinhos não devem entrar. A dificuldade acontece quanto existe

certa simetria no grafo, e esta simetria é quebrada através da randomização.

2.4.2.3 Balanceamento de Carga

É uma outra utilização da randomização. Uma vez que há um conjunto de

dados a ser processado, estes dados podem ser divididos entre os processadores

de maneira aleatória, o que garante, com certa probabilidade, um balanceamento,

sem o processamento em excesso (overhead) causado pelo cálculo da carga de

dados. Existem também aplicações de escalonamento usando a randomização.

2.4.3 Mestre/Escravo (process farm)

30

Neste paradigma, um ou mais processos mestres executam as tarefas

essenciais do programa paralelo e dividem o restante das tarefas para os processos

escravos.

Mestre

EscravoEscravoEscravo

Figura 15: Modelo Mestre/Escravo.

Quando um processo escravo termina sua tarefa, ele informa ao mestre, que

atribui uma nova tarefa para o escravo. Este paradigma é bastante simples, visto

que o controle está centralizado em um ou mais processos mestre. Sua

desvantagem é que o mestre pode se tornar um gargalo na comunicação. Isso

acontece quando as tarefas são muito pequenas (ou os escravos são relativamente

rápidos).

2.4.4 Pipeline

O Pipeline é uma técnica de implementação de processadores que permite a

sobreposição temporal das diversas fases de execução das instruções, aumenta o

número de instruções executadas simultaneamente e a taxa de instruções iniciadas

e terminadas por unidade de tempo. No entanto, o pipeline não reduz o tempo gasto

para completar cada instrução individualmente.

No paradigma pipeline um número de processos forma um pipeline virtual. Os

processos podem formar esses pipelines de uma maneira linear, multidimensional,

cíclica ou acíclica.

O modelo pipeline envolve mapeamento estático de tarefas em processos. O

princípio desta técnica é poder iniciar uma nova tarefa antes que o resultado para a

tarefa anterior na seqüência de tarefas tenha sido gerado. O uso do pipeline então

tem como meta aumentar a produtividade do processo (throughput) como um todo.

31

Um algoritmo pipeline baseia-se no relacionamento que se dá entre um

processo e o processo seguinte, em que a saída de um é a entrada do seu

sucessor. A entrada do primeiro processo é a entrada do algoritmo e a saída do

último processo é a saída do algoritmo. Temos então que cada processo consiste

numa parte do pipeline e numa pequena parte do algoritmo.

Com pipeline, o processamento de uma instrução é composto por pelo menos

cinco fases, como ilustrado abaixo.

Figura 16: Funcionamento do pipeline de cinco estágios.

O estágio 1 busca a instrução na memória e armazena em um buffer até

chegar a hora de executá–la. No estágio 2, ocorre a decodificação da instrução,

determinando tipo e operandos. No estágio 3, ocorre a busca dos operandos na

memória ou nos registradores. No estágio 4, temos a execução - passagem pelo

caminho de dados. Finalmente, no estágio 5, o resultado do processamento é escrito

em um registrador.

32

2.4.5 Pool de Trabalho

Neste modelo, um conjunto (pool) de tarefas é disponibilizado por uma

estrutura de dados global e um determinado número de processos é criado para

executar esse conjunto de tarefas. No início, só existe uma única tarefa,

gradativamente os processos buscam novas tarefas e imediatamente passam a

executá-las, espalhando o processamento. O programa paralelo termina quando o

pool de trabalho fica vazio. Este tipo de modelo facilita o balanceamento da carga;

por outro lado é difícil obter um acesso eficiente e homogêneo aos múltiplos

processos.

33

3. LINGUAGENS DE PROGRAMAÇÃO PARALELA

O paralelismo surgiu como uma ferramenta para otimizar o desempenho dos

programas, aproveitando os recursos das máquinas ao máximo. Porém, colocar em

prática o que o paralelismo propõe exige um conhecimento muito aprofundado dos

meios possíveis de se paralelizar os problemas em questão. Com isso, surgiram as

linguagens de programação paralela, como um novo recurso para facilitar a tarefa de

construir programas que utilizem os recursos de paralelismo de equipamentos com

arquitetura de computação paralela. Para utilizar plenamente os recursos de um

equipamento multiprocessado, existem basicamente duas opções: construir

programas explicitando e controlando manualmente os trechos de paralelismo,

utilizando recursos de uma linguagem de programação como C ou Java para a

criação das threads e processos necessários, ou utilizar-se de uma linguagem de

programação paralela, que normalmente são diretivas de compilador para uma

linguagem de programação pré-existente como, por exemplo, C ou Java, que

possuem recursos que facilitam o tratamento de trechos paralelos e seqüenciais dos

programas, atuando como um pré-compilador e criando a versão final em uma

linguagem de programação, poupando ao programador a tarefa de se preocupar

com o gerenciamento de threads e processos. Desde o surgimento dessas

arquiteturas, diversas interfaces de programação paralela foram criadas, entre elas a

PVM, a MPI e a OpenMP, que serão vistas a seguir. Esta última foi desenvolvida por

um grupo composto pelos maiores fabricantes de software e hardware do mundo. O

desenvolvimento foi realizado através de um trabalho colaborativo entre os diversos

parceiros interessados no projeto, entre eles: Compaq/Digital, Hewlett-Packard, Intel,

IBM, KAI, Silicon Graphics, Sun e outros.

3.1 Processos e Threads

Para colocar em prática o paralelismo, os programadores podem tanto utilizar

os recursos das linguagens paralelas, quanto fazer manipulação em linguagens

34

tradicionais como C e Java. Porém, em ambos os meios, o que está sendo

explorado é o gerenciamento de processos e threads.

• Processos

Dividir um programa em diversos processos e gerenciar a execução dos

mesmos entre os processadores é teoricamente uma das formas mais simples de

implementar o paralelismo. Porém, a programação da comunicação é explícita e o

programador é responsável por toda a comunicação entre os processos. O

gerenciamento de processos é muito utilizado em técnicas de algoritmos paralelos

como o Pipeline e o Mestre e Escravo.

• Threads

Em sistemas operacionais que dão suporte a multithread, a thread passou ser

utilizada em detrimento ao processo, pois essas são linhas de execução diferentes e

independentes dentro de um mesmo processo, apresentando várias vantagens e

desvantagens em relação ao processo.

Dentre as vantagens no uso de threads, podemos destacar:

• é mais fácil criar uma thread do que um processo;

• é mais rápido terminar uma thread do que um processo;

• é mais rápido chavear (retirar uma thread ou processo executando para a inserção

de outro) entre threads de um mesmo processo;

• threads podem se comunicar sem invocar nenhuma primitiva ou dispositivo do

sistema operacional, já que compartilham memória e arquivos de um mesmo

processo;

• o término de um processo implica no término de todas as threads deste processo.

Para o desenvolvimento de aplicações multithread, o sistema operacional, onde

o programa vai ser implementado e executado, deverá oferecer algum tipo de

suporte para threads. Há basicamente 3 formas para isto:

35

Threads do usuário: Esse tipo de implementação impossibilita

o sistema operacional de distribuir as

threads entre vários processadores em

caso de sistemas multiprocessados.

A thread possui chaveamento rápido por

não envolver o sistema operacional.

Figura 17: Modelo de threads do usuário.

Threads do núcleo:

O sistema operacional pode distribuir as

threads entre todos os processadores

disponíveis na máquina.

A thread do núcleo possui chaveamento

cerca de 10 vezes mais lento do que a

thread em modo usuário.

Threads híbridas:Um processo pode ter várias

threads em modo usuário, que por

sua vez são combinadas em

conjunto e delegadas a threads

em modo núcleo.

O programador desenvolve em

modo usuário e depois específica

quantas threads em modo núcleo

estão associadas ao processo.

Figura 19: Modelo de threads híbridas.

Figura 18: Modelo de threads do núcleo.

36

Os sistemas operacionais que oferecem suporte à programação multithread

colocam à disposição do programador uma API (conjunto de rotinas e padrões

estabelecidos por um software para utilização de suas funcionalidades por

programas aplicativos) de funções, através das quais threads de núcleo poderão ser

implementadas.

Sistemas operacionais que não oferecem suporte à programação multithread

poderão implementar bibliotecas para que o programador possa implementar

sistemas concorrentes. Como exemplo de uma boa alternativa, podemos citar a

linguagem Java.

3.2 PVM (Memória Distribuída – Troca de Mensagens)

PVM é a abreviação de Máquina Virtual Paralela (Parallel Virtual Machine).

Este é um pacote de software que permite que uma rede heterogênea de

computadores de todos os tipos seja programada como se fosse apenas uma única

"Máquina Virtual Paralela". A programação é baseada no paradigma de troca de

mensagens.

JPVM: JPVM é uma API implementada totalmente em Java que permite a troca

de mensagens explícita, combinando as vantagens da linguagem Java, como

portabilidade e interoperabilidade, com as técnicas de troca de mensagens entre

processos paralelos em ambientes distribuídos, sendo uma implementação em Java

da biblioteca Parallel Virtual Machine. A interface semelhante do JPVM em relação

ao PVM permite aos programadores acostumados ao PVM padrão a migração de

um ambiente para o outro com uma maior facilidade.

A JPVM é composta por duas partes [Ferrari, 1998]: JpvmDaemon - processo

que é executado em todos os nós de uma rede a fim de formar uma máquina

paralela virtual, realizar a comunicação entre os processos criados e coordenar as

tarefas em execução; e o JpvmEnvironment - biblioteca que trata das funções

básicas para a geração do paralelismo, como troca de mensagens, criação e

eliminação de processos, sincronização de tarefas, modificação da máquina virtual,

envio e recebimento de mensagens.

37

3.3 MPI (Memória Distribuída – Troca de Mensagens)

MPI (Massage Passing Interface) é um padrão de interface de troca de

mensagens para aplicações que utilizam computadores MIMD com memória

distribuída.

MPIJAVA: O MPIJava é uma interface que permite fazer uso da orientação a

objetos em Java juntamente com a biblioteca MPI, amplamente usada na

computação paralela e distribuída [Baker, 1998]. Para tanto, as chamadas dos

métodos do código em java obedecem à estrutura das funções definidas em MPI, o

que torna a programação menos flexível. A portabilidade também é atingida, uma

vez que a chamada das funções MPI não é específica para uma determinada

arquitetura. Em um nível de abstração mais baixo, MPIJava executa as funções

nativas de uma implementação MPI, conforme a definição feita no momento da

instalação. Dentro das formas de comunicação possíveis em Java, a biblioteca

apresenta bons resultados [Baker, 1999]. O uso de MPIJava já foi validado em

diversas implementações e avaliações de desempenho [Taboada, 2003].

3.4 OpenMP (Memória Compartilhada)

O OpenMP (Open Multi-Processing) é uma especificação para implementação

portável, que oferece um conjunto de diretivas para a programação paralela em

sistemas multiprocessados com memória compartilhada, realizando para tal a

criação e o controle de threads. As diretivas do OpenMP podem ser incluídas em

programas escritos nas linguagens C e FORTRAN para especificar trechos ou

blocos de programas que devem ser executados em paralelo. Para a implementação

dos laços paralelos, o OpenMP utiliza a biblioteca "Pthreads", o que lhe proporciona

um bom desempenho e um alto grau de portabilidade, uma vez que "Pthreads"

possui desempenho otimizado e já foi implementada em inúmeras plataformas.

Internamente, o OPENMP trabalha com um modelo “FORK-Join” onde, a partir de

uma “thread master” (aquela que iniciou o programa), cria-se um conjunto de threads

para a realização de tarefas em paralelo, e depois é realizada uma junção, onde

todas as threads são sincronizadas e destruídas, sobrando somente a principal.

38

4. ALGORITMOS DE ORDENAÇÃO PARALELOS

A ordenação é um dos aspectos fundamentais em ciência computacional,

muitos cientistas de computação consideram a ordenação o problema mais

fundamental no estudo de algoritmos [Cormen, 2002]. O objetivo da ordenação é

facilitar a localização dos membros de um conjunto de dados. Assim sendo, é uma

atividade fundamental e universalmente utilizada para a elaboração de algoritmos

mais complexos. Exemplos de casos em que os objetos são ordenados podem ser

encontrados em listas telefônicas, impostos de renda, índices, bibliotecas,

dicionários, etc.

A ordenação é uma das atividades mais comuns realizadas nos computadores

seriais. Muitos algoritmos incorporam a ordenação para que a informação possa ser

acessada eficientemente. As várias técnicas de ordenação ilustram claramente

como um dado problema pode ser resolvido por meio de diferentes algoritmos.

Diversas literaturas facilmente encontradas nas livrarias apresentam as vantagens e

desvantagens de cada técnica e quais técnicas devem ser consideradas em cada

aplicação.

A ordenação tem uma importância adicional para os desenvolvedores de

algoritmos paralelos. Ela é freqüentemente utilizada para realizar permutações de

dados em computadores de memória distribuída. Estas operações de movimentos

de dados podem ser usadas, por exemplo, para resolver problemas de teoria dos

grafos, geometria computacional e processamento de imagem. Por isso, é

importante reduzir ao máximo a complexidade dos algoritmos que lidam com o

problema da ordenação. As melhores ordenações em série possuem complexidade

de pior caso O(n log n). Deste modo, versões para funcionamento em paralelo

destes algoritmos foram desenvolvidas, com o objetivo de diminuir

consideravelmente o tempo de execução dos mesmos.

Neste trabalho, serão abordados vários algoritmos de ordenação, tais como quick

sort, merge sort, bitonic sort, rank sort, entre outros. Para cada algoritmo

abordado, serão feitas comparações sobre suas implementações paralela e

seqüencial. Além disso, pela análise de suas complexidades, será mostrado que

39

estes algoritmos, quando paralelizados, podem obter uma performance muito

superior em relação aos seqüenciais.

4.1 BUBBLE SORT

A forma seqüencial do algoritmo de ordenação bubble sort usa uma estratégia

de “comparação e troca”, que é aplicada em várias iterações sobre os dados a

serem ordenados.

4.1.1 Funcionamento do algoritmo na forma seqüencial.

Consideremos um vetor X de n posições, variando de 1 até n, que desejamos

ordenar de forma não decrescente. O algoritmo começa comparando o valor que se

encontra na sua primeira posição com o da posição seguinte, ou seja, o elemento da

posição 1 com o da posição 2, e troca os valores de posição, caso o valor que se

encontra na posição 2 seja menor que o da posição 1. Em seguida, repete o mesmo

passo, só que agora para os valores que atualmente se encontram nas posições 2 e

3. Este processo é repetido de forma análoga até que o algoritmo compare os

valores que se encontram na penúltima e última posições. Este processo de

comparações e trocas é considerado uma fase do algoritmo, sendo o algoritmo

bubble sort constituído por n-1 fases semelhantes.

Procedimento BUBBLE_SORT(n)

inícioPara i := n-1 até 1 faça Para j := 1 até i faça compara_e_troca(aj, aj+1)fim

Algoritmo 1 – Versão seqüencial do algoritmo Buble Sort.

Obs.: compara_e_troca(aj, aj+1) compara aj com aj+1 e troca seus valores de

posição caso o valor de aj seja maior que o valor de aj+1.

4.1.2 Funcionamento do algoritmo na forma paralela

40

Após esta breve descrição do algoritmo seqüencial, analisemos a seguinte

questão: é possível criar uma versão paralela eficiente deste algoritmo? A resposta a

esta pergunta é positiva. Através da técnica de pipeline, é possível melhorar o

desempenho do algoritmo, em comparação com a versão seqüencial. Isto se deve

ao fato de ser possível serem executadas várias fases em simultâneo na versão com

pipeline.

Tal método é possível porque cada fase só faz uma comparação com um par

de posições; quando a primeira fase se encontra na comparação entre as posições

x3 e x4, a segunda fase já pode, sem problema algum, fazer a comparação entre as

posições x1 e x2. A terceira fase terá início quando a segunda fase estiver

comparando as posições x3 e x4, e a primeira fase, por sua vez, se encontrar na

comparação das posições x5 e x6. (Ver Figura 20.)

Figura 20: Bubble sort com pipeline.

Existe ainda uma variação do algoritmo bubble sort, cujo nome é odd-even

(transposition) sort, que consiste em duas fases: a fase even (par) e a fase odd

(ímpar). Na fase even, comparam-se, e se necessário trocam-se, as posições pares

com a posição seguinte a cada uma delas. Na fase odd, a idéia é análoga à anterior,

mas para as posições ímpares.

41

Procedimento Odd-even(n)início Para i := 1 até n faça Se i é ímpar então

Para j := 0 até n / 2 – 1 faça compara_e_troca(a2j+1, a2j+2)

Se i é par então Para j := 1 até n / 2 – 1 faça

compara_e_troca(a2j, a2j+1)fim

Algoritmo 2 – Versão seqüencial do algoritmo Odd even transposition.

Procedimento Odd-even-paralelo(n)início Para i := 1 até n faça

Se i é ímpar então Se id é ímpar então

Compara_e_troca_min(id+1) Senão

Compara_e_troca_max(id-1)Se i é par então Se id é par então

Compara_e_troca_min(id+1) Senão

Compara_e_troca_max(id-1)fim

Algoritmo 3 – Versão paralela do algoritmo Odd even transposition.

Obs.: id é o índice do processo. Considerando a Figura 21, id variaria de 1 a 6.

Neste algoritmo, consideramos um elemento por processo, onde n é o

número de processos (também número de elementos a se ordenar).

Figura 21: Odd-Even transposition sort em paralelo.

42

Assumimos que os processos são organizados em um vetor

unidimensional, onde inicialmente o elemento ai reside no processo pi.

compara_e_troca_min(id+1) compara o elemento que reside no

processo id+1 com o elemento que reside no processo id+2 e troca seus

valores de posição mantendo o elemento de menor valor no processo

id+1 [Grama, 1994].

compara_e_troca_max(id-1) compara o elemento que reside no

processo id-1 com o elemento que reside no processo mais próximo e

retém o maior [Grama, 1994].

4.1.3 Análise das versões

A versão paralela do bubble sort é bem mais eficiente que a versão seqüencial,

já que a solução paralela tem complexidade O(n) [Grama,1994], enquanto que o

algoritmo bubble sort na sua versão seqüencial apresenta uma complexidade de

O(n2) [Grama,1994].

4.2 MERGE SORT

O algoritmo merge sort consiste de duas etapas. Na primeira etapa, uma lista

de elementos é recursivamente separada em metades, até que todos os elementos

estejam separados. A segunda etapa do algoritmo consiste em fazer a junção

(merge) dos elementos separados, retornando no final uma única lista com todos os

elementos ordenados.

4.2.1 Funcionamento do algoritmo na forma seqüencial

Consideremos, a título de exemplo, uma lista de oito elementos desordenados

que se quer ordenar de forma não decrescente (ver Figura 22). Durante todo o

processo da divisão da lista, não é feita qualquer computação sobre os elementos e

suas posições. Nesta primeira etapa, a lista original é separada em duas listas com

quatro elementos cada, que são separadas recursivamente até que cada elemento

forme uma lista unitária. É na fase da junção (merge) que o algoritmo ordena todos

43

os elementos da forma pretendida. Neste caso, em que queremos ordenar de forma

não decrescente, esta etapa do algoritmo inicialmente junta cada duas listas

unitárias em uma única lista, ficando o menor valor na primeira posição e o maior na

segunda posição. Este processo é repetido para as quatro listas criadas

anteriormente, juntando-as duas a duas em uma única lista até que reste apenas

uma lista ordenada de forma não decrescente. A Figura 22 ilustra as duas etapas do

algoritmo para uma lista com oito elementos.

Figura 22: Funcionamento do Merge Sort seqüencial.

Procedimento MergeSort(A,p,r)

início

Se p < r então q := (p+r)/2 MergeSort(A,p,q) MergeSort(A,q+1,r) Junção(A,p,q,r)fim

Obs.: MergeSort(A,p,r),ordena o vetor A de p até r.Algoritmo 4 – Versão seqüencial do algoritmo Merge Sort.

Procedimento Junção(A,p,q,r)início i := p k := p j := q-1 enquanto (i <= q) e (j<=r) faça se A[i] <= A[j] então B[k] := A[i] i:= i+1 senão B[k] := A[j] j := j+1 enquanto i <= q faça B[k] := A[i]

i := i+1 k := k+1

enquanto j <= r faça B[k] := A[j]

j := j+1 k := k+1

para i de p até r faça A[i] := B[i]fim

Copia os elementos da parte esquerda

Copia os elementos da parte direita

Copia os elementos do vetor auxiliar

44

Junção(A,p,q,r), faz a junção de A[p..q] e A[q+1..r] de forma que os

elementos fiquem ordenados conforme mostrado na Figura 22.

O procedimento Junção utiliza um vetor auxiliar B[p..r].


A versão simples paralela baseia-se em atribuir a cada processador uma lista

de elementos, na parte inicial da divisão da lista a ser ordenada. Esta versão tem o

problema de, em algumas fases do algoritmo, ser necessária bastante comunicação

entre processadores. Mas, por outro lado, esta versão torna-se bastante leve

computacionalmente para cada um dos processadores envolvidos, pois cada

processador é responsável por uma lista pequena.

4.2.2.1 Odd-Even merge sort (uma variação do merge sort)

Este algoritmo tem como objetivo unir duas listas ordenadas, em uma só lista

ordenada.

Considerando as listas A = a1, a2, ..., an e B = b1, b2, ..., bn, o algoritmo começa

criando uma lista ordenada C, constituída pelos elementos das posições (índices)

ímpares de ambas as listas. Existe o processo análogo para as posições (índices)

pares, sendo criada a lista D com os elementos de a2, a4, ..., an, b2, b4, ..., bn. Para

maior facilidade de percepção futura, os elementos da lista C estarão referenciados

e ordenados da seguinte forma: c1, c2, ..., cn; analogamente, os da lista D serão

d1,...,dn. A lista final ordenada, E, constituída pelos elementos: e1, e2, ..., e2n, como

podemos observar na Figura 23, é dada da seguinte forma: O seu primeiro

elemento, e1, corresponde a c1 (primeiro elemento da lista C), e o último elemento,

e2n, é obtido de dn (ultimo elemento da lista D). Isto ocorre porque o vetor C contém

os elementos a1 e b1 (os menores elementos da lista A e B), já que C é formado por

todos os elementos das posições ímpares das listas A e B, e como o vetor C é

ordenado, logo c1 conterá o menor elemento das duas listas. De forma análoga,

considerando n um número par, D conterá os elementos an e bn (os maiores

elementos da lista A e B), já que D é formado por todos os elementos das posições

pares das listas A e B, e como o vetor D é ordenado, logo dn conterá o maior

A B

C D

E

1 5 9 13 2 3 6 15

1 2 6 9 3 5 13 15

1 2 3 5 6 9 13 15

A1 A2 A3 A4 B1 B2 B3 B4

C1 C2 C3 C4 D1 D2 D3 D4

E1 E2 E3 E4 E5 E6 E7 E8

E4= min{c3, d2 } E5 = max{c3, d2 }

I = 2

45

elemento das duas listas. Os demais elementos de E, que variam de 2 a 2n-1, serão

obtidos da seguinte forma:

e2i = min(ci+1, di), e2i+1 = Max(ci+1, di), onde (1 ≤ i ≤ n-1).

Figura 23: Funcionamento do Odd-Even Merge Sort.

Procedimento Odd-even-merge(n)

Para i := 1 até (n/2) faça

compara_e_troca(P2i, P2i+1)

Para i := (log n-1) até 1 faça

Para j := 1 até (n-2i)/2 faça

compara_e_troca(P2j-1, P2j+2i-2)

Algoritmo 5 – Versão paralela do algoritmo Merge Sort.

Obs.: Assumimos que temos n processadores disponíveis, sendo n um número

par, onde cada comparação entre pares de processos é distribuída entre

os n processadores disponíveis.

No laço (para i de (log n-1) até 1 faça), i é decrementado, até que i=1.

compara_e_troca(x,y) compara x com y e troca seus valores de posição,

caso o valor de x seja maior que o valor de y.

Consideramos que a lista A(a1,a2,a3,...) está armazenada em processos

(P0,P2,P4,...) e a lista B(b1,b2,b3,....) em processos (P1,P3,P5,...). No final da

46

execução deste algoritmo a lista E(e1,e2,e3,e4,...) é formada pelos

processos (P0,P1,P2,P3,P4,...) [Mayr,1995].

Maiores detalhes sobre o funcionamento deste algoritmo podem ser

encontrados em [Mayr, 1995].


O merge sort seqüencial tem complexidade O(n.log n) [Mayr,1995], o que é

ótimo para um algoritmo de ordenação seqüencial. O odd-even merge sort em

comparação com a versão seqüencial é bastante superior, pois apresenta uma

complexidade de tempo de O(log2n) [Mayr,1995] com n processadores.

4.3 QUICK SORT

O algoritmo Quicksort, inventado por C.A.R. Hoare [Hoare, 2008], é um

algoritmo recursivo que tem como base a comparação de valores para ordenar uma

lista desordenada.


Quando é passada uma lista de números, o algoritmo seleciona um número

dessa lista, tornando-o pivô. Então, a lista é partida em duas sublistas: uma

contendo os números menores que o pivô, e outra com os números maiores. Em

seguida, o algoritmo chama a si mesmo recursivamente para ordenar as duas

sublistas. A função retorna a concatenação da primeira lista, pivô e segunda lista.

Obs.: A chave do algoritmo é o procedimento particionar, que organiza a sublista

Procedimento Quicksort(A,p,r)início Se p<r então

q := particionar(A,p,r)Quicksort(A,p,q-1)Quicksort(A,q+1,r)

fim

Procedimento particionar(A,p,r)início

x := A[r]i := p-1Para j := p até r-1 faça

se A[j] <= x entãoi := i+1trocar(A[i],A[j])

trocar(A[i+1],A[r]) retornar i+1fim

Algoritmo 6 – Versão seqüencial do algoritmo Quick Sort.

47

A[p..r] localmente.

A seguir, as Figuras 24 e 25 ilustram o funcionamento do procedimento

particionar. Os elementos da lista ligeiramente sombreados estão na primeira

partição, com valores não maiores que x. Elementos fortemente sombreados estão na

segunda partição, com valores maiores que x. Os elementos não sombreados ainda

não foram inseridos em nenhuma partição, e o elemento final branco é o pivô.

A Figura 25 ilustra as seguintes situações:

Figura 25: Iteração do procedimento particionar.

(a) Arranjo inicial. Nenhum dos elementos foi

inserido em qualquer das duas primeiras

partições.

(b) O valor 2 é inserido na partição de valores

menores.

(c)-(d) Os valores 8 e 7 foram acrescentados à

partição de valores maiores.

(e) Os valores 1 e 8 são permutados, e a

partição menor cresce.

(f) Os valores 3 e 8 são permutados, e a

partição menor cresce.

(g)-(h) Os valores 5 e 6 são incluídos na

partição maior e o loop termina.

(i) O elemento pivô é permutado com o primeiro

elemento da segunda partição, de forma a

residir entre as duas partições.

Figura 24: Operação de particionar sobre um exemplo de lista.

48

(a) Se A[j] > x, j é incrementado, e o loop se mantém sem mudanças.

(b) Quando A[j]<=x, i é incrementado, A[i] e A[J] são permutados, e então j é

incrementado. Por causa da troca, agora temos que A[i] <= x; de modo semelhante,

também temos que A[j-1] > x, pois o item que foi trocado em A[j - 1] é sempre maior

que x.


Existem algumas vantagens na utilização deste algoritmo, no que toca a

paralelização de algoritmos. Uma, porque é considerado um dos algoritmos mais

rápidos. E outra, por ser um algoritmo que chama a si próprio recursivamente, sendo

que essas chamadas podem ser executadas independentemente.

Em relação ao desenvolvimento deste algoritmo, inicialmente os valores

encontram-se distribuídos ao longo dos processos. Escolhemos então um pivô de

cada um dos processos. Após isso, cada processo divide os seus números em duas

listas: aqueles que são menores ou iguais ao pivô, e aqueles que são maiores do

que o pivô (que chamaremos aqui de “lista menor” e “lista maior”, respectivamente) –

procedimento que denominamos de rearranjo local. Cada processo na parte de cima

da lista de processos (parte da lista em que se encontram os elementos maiores que

o último pivô) envia a sua “lista menor” para um processo concorrente na parte

inferior da lista de processos (parte da lista em que se encontram os elementos

menores que o último pivô; em princípio a parte inferior se encontra no início da lista)

e recebe uma “lista maior” em retorno. Neste momento, os processos na parte

superior da lista de processos têm valores maiores do que o pivô, e os processos na

parte inferior da lista de processos têm valores menores ou iguais ao pivô,

procedimento este denominado rearranjo global. A partir deste ponto, os processos

dividem-se em dois grupos e o algoritmo é chamado novamente. Em cada grupo de

processos, é distribuído um pivô. Os processos dividem a sua lista e trocam valores

com processos concorrentes. Após log p recursões, cada processo tem uma lista

desordenada de valores, que são diferentes dos valores possuídos pelos outros

processos. Cada processo pode agora ordenar a lista que controla usando quicksort

seqüencial.

49

Figura 26: Exemplo da aplicação paralela do algoritmo Quick sort.

Em relação à complexidade, se tivermos p processadores, podemos dividir a

lista de n elementos em p sublistas em O(n). Após isso, a sua ordenação será em

O((n/p)log(n/p)) [Grama, 1994].

Uma das vantagens deste algoritmo em relação a outros algoritmos de

ordenação em paralelo é o fato de não ser necessária a sua sincronização. Um

processo é criado por cada sublista gerada, sendo que esse processo só trabalha

com essa lista, não se comunicando com os outros processos.

O tempo de execução do algoritmo começa a ser contabilizado quando o

primeiro processo começa a sua execução, e termina quando o último processo

termina a sua execução. É por isto que é importante assegurar que todos os

processos tenham a mesma carga de trabalho, para que terminem todos por volta

do mesmo tempo. Neste algoritmo, a carga de trabalho é relacionada com o número

de elementos controlados pelos processos. Um ponto negativo deste algoritmo é a

necessidade de se conseguir um pivô perto da mediana dos valores, para garantir

50

maior divisão de trabalho pelos processos. Por exemplo, em uma lista com os

valores 1, 2, 4, 7, 9, 10, o pivô deve ter valor próximo a 5,5 (pois a mediana é

(4+7)/2, que é 5.5).

No entanto, poderia ser feito um melhor balanceamento do tamanho da lista

pelos processos se, em vez de escolher um número arbitrário da lista para ser pivô,

escolhêssemos um valor mais perto do valor mediano da lista ordenada. Este ponto

é a motivação por trás do próximo algoritmo em paralelo: hyperquicksort.

4.3.3 Hyperquicksort (uma variação do quick sort)

Este algoritmo, desenvolvido por Wagar [Wagner, 1987], em vez de escolher

um número arbitrário da lista para ser pivô, escolhe um valor mais perto do valor

mediano da lista ordenada. Considerando que os valores continuam a mover-se

entre processos, teremos então um pivô para dividir os números em dois grupos: a

parte superior e a parte inferior. O hyperquicksort possui o seguinte princípio: cada

processador resolve um subproblema usando o algoritmo seqüencial quicksort e

utiliza um mecanismo de comunicação paralela eficiente para gerar a solução final

partindo das soluções parciais dos processadores. No primeiro passo do

hyperquicksort, cada processador usa o quicksort para ordenar sua lista local.

Durante cada passo da segunda fase do algoritmo, um hipercubo [Hipercubo, 2008]

é dividido em dois subcubos. Cada processador envia valores ao seu vizinho no

outro subcubo, com isso cada processador recebe valores e os acrescenta a sua

lista remanescente.

Os passos finais do hyperquicksort são os mesmos do quicksort paralelo. Após

a execução desses passos, cada processo tem uma sublista ordenada própria e

uma sublista ordenada que recebe de um outro processo. Esse processo vai então

juntar as duas listas, para que todos os elementos que controla estejam ordenados.

É importante que os processos terminem esta fase com listas ordenadas, porque

quando o algoritmo se chamar novamente, dois processos precisarão escolher o

elemento mediano das suas listas como pivô.

O hyperquicksort assume que o número de processos é um expoente de 2. Se

imaginarmos a lista de processos como um hipercubo, poderemos modelar as

51

comunicações, de modo que estas sejam sempre feitas entre pares de processos

adjacentes (Ver Figura 27).

Figura 27: Pares de processos adjacentes do Hyperquicksort.

No início do algoritmo, cada processo tem no máximo n/p valores, onde n é o

número de elementos a serem ordenados, p é o número de processadores e n é

maior que p. A complexidade de tempo esperada do passo inicial do quicksort é

Θ[(n/p)log(n/p)] [Grama, 1994]. Assumindo que cada processo guarda n/2p valores e

transmite n/2p valores em cada passo de separar-e-juntar, o número esperado de

comparações necessárias para juntar as duas listas numa única lista ordenada é

n/p. O número de comparações feitas durante o algoritmo todo é Θ[(n/p)(logn+logp)],

para log p iterações.

Assumindo que cada processo passa metade dos seus valores em cada

iteração, o tempo necessário para enviar e receber n/2p valores ordenados para

outro processo, é Θ(n/p).

Procedimento hipercubo_quicksort(B,n)início Para i := 1 até d faça

x := pivô

Particionar B em B1 e B2 tal que B1 <= x < B2

Se (n-ésimo_bit(i)=0) então

Enviar B2 para um processo através da i-ésima dimensão

C recebe uma sublista ordenada dessa mesma dimensão

B recebe B1 U C

Senão Enviar B1 para um processo através da i-ésima dimensão

C recebe uma sublista ordenada dessa mesma dimensão

B recebe B2 U C

Ordenar B usando quicksort seqüencialfimAlgoritmo 7 – Versão paralela do algoritmo Quicksort em hipercubo.

52

Obs.: p é o número de processadores.B é o vetor a ser ordenado.n é o número de elementos, onde n é bem maior que p. d é o número de dimensões.


A complexidade de tempo seqüencial do quicksort é O(n.log n) [Cormen, 2002].

O overhead (processamento ou armazenamento utilizado ou gasto em excesso para

executar uma determinada tarefa) da comunicação do hyperquicksort é p vezes a

complexidade da comunicação, ou Θ(n.log p) [Grama, 1994].

O hyperquicksort tem duas desvantagens que limitam as suas vantagens.

Primeiro, o número esperado de vezes que um valor é passado de um processo

para outro é (log p)/2. Este overhead da comunicação limita a escalabilidade (característica desejável em todo o sistema, ou em um processo, que indica sua

habilidade de manipular uma porção crescente de trabalho de forma uniforme) do

algoritmo em paralelo. Poderíamos reduzir este overhead se conseguíssemos

encontrar uma maneira de enviar as chaves diretamente para os seus destinos

finais. Além disso, a maneira como os pivôs são escolhidos pode levar a certos

problemas no balanceamento da carga de trabalho entre processos. Se

conseguíssemos ter exemplares de todos os processos, poderíamos ter uma melhor

divisão das listas de elementos pelos processos.

4.4 BITONIC SORT

O Bitonic Sort é um algoritmo de ordenação desenvolvido especialmente para

máquinas paralelas [Bitonic, 2008].


O algoritmo Bitonic Sort é a base para algoritmos de ordenação

polilogarítmicos de complexidade de tempo O (log2 n) [Batcher, 1968]. O seu

princípio funcional baseia-se no compara-e-troca, onde dois elementos são

comparados e, se estiverem fora de ordem, são trocados.

53

Para se aplicar este algoritmo, é necessário ter uma seqüência bitônica, ou

seja, uma seqüência de números (a1, a2, ..., an) tal que existe um inteiro aj (1 < j < n),

tal que a1 < a2 < ... < aj > aj+1 > ... > an. Por exemplo, a seqüência (1, 3, 5, 6, 7, 4, 2) é

bitônica, com j=5, e a seqüência (9, 6, 3, 2, 5, 7, 10) também é bitônica, pois

podemos deslocá-la ciclicamente obtendo a seqüência bitônica (2, 5, 7, 10, 9, 6, 3),

com j=4. Se a lista de elementos a ser ordenada não forma inicialmente uma

seqüência bitônica, então ela deverá ser transformada em uma e, em seguida, esta

seqüência poderá ser classificada. Um único passo compara-troca pode dividir a

seqüência bitônica em duas seqüências bitônicas, confome o Lema:

Lema 1 [Quinn, 1994]: Se n é par então n/2 comparadores (circuito combinatório

que permite comparar o valor de dois elementos) são suficientes para transformar

uma seqüência bitônica de n valores a1, a2, ..., an em duas seqüências bitônicas com

n/2 valores.

O Bitonic Sort sempre compara elementos cujos índices diferem em

exatamente um bit. Uma vez que os processadores estão conectados usando o

modelo de vetor de processadores no hipercubo, se seus índices diferem em

exatamente um bit, então fica fácil implementar o algoritmo Bitonic Sort neste

modelo. Neste caso, os processadores substituem os comparadores. Em vez de

rotear pares de elementos por comparadores, os processadores roteam os dados

para os processadores adjacentes, onde os elementos são comparados e trocados,

se necessário.

A Figura 28 mostra a comunicação do Bitonic sort em hipercubo para n = 16.

Durante cada passo do algoritmo, setas indicam os pares de processos que

executam operações de comparar-trocar.

Figura 28: Roteamento para processos adjacentes do Bitonic Sort.

54

Procedimento Bitonic_sort(label,d)

início Para i := 0 até d-1 faça Para j := i até 0 faça

Se (i+1)-ésimo bit do label <> j-ésimo bit do label então Compara_e_troca_max(j)Senão Compara_e_troca_min(j)

Obs.: n = 2d processos.label é o índice do processo.

d é a dimensão do hypercubo.

O algoritmo utiliza as funções Compara_e_troca_max(i) e

Compara_e_troca_min(i). Estas funções comparam o elemento local com

o elemento no mais próximo processo junto a i-ésima dimensão e retém o

mínimo ou o máximo dos dois elementos.

Durante cada passo do algoritmo, é efetuada uma operação de

comparação e troca para todo processo. O algoritmo executa um total de

(1+ log n)(log n)/2 passos [Grama, 1994], assim o tempo de

processamento paralelo é: Tp = Θ (log² n).

4.5 RANK SORT

O rank sort, também conhecido como enumeration sort, é um exemplo de

algoritmo de ordenação estável, ou seja, as posições relativas de dois elementos

com mesmo valor se mantêm, como podemos verificar no exemplo abaixo:

Lista original:

444 555 555 666 777 333 999 222 111 222 888

Lista ordenada, após ordenação estável:

111 222 222 333 444 555 555 666 777 888 999

Este algoritmo consiste em determinar a quantidade de números menores que

um determinado número x, calculando assim a posição (rank) de x na lista ordenada.


fim

Algoritmo 8 - Versão paralela do algoritmo Bitonic Sort em hipercubo.

55

Consideremos como exemplo um vetor com n números (a[0] … a[n-1]).

Inicialmente, a[0] é comparado com todos os outros elementos. O total de elementos

menores que a[0] determina seu rank. Este valor é o seu índice no vetor ordenado b,

onde ele será colocado. A mesma operação é repetida para todos os elementos do

vetor a.

Para i := 0 até n faça Para cada númeroinício rank := 0; Para i := 0 até n faça Conta os números menores que a[i] Se (a[i] > a[j]) ou (a[i] = a[j] e i<j) então

rank :=rank+1; b[rank] := a[i]; Copia a[i] na sua posição correta em bfim

Algoritmo 9 - Versão seqüencial do algoritmo Rank Sort.

Analisando a complexidade, podemos observar que este algoritmo é pouco

eficiente quando executado em modo seqüencial, uma vez que faz n-1 comparações

n vezes, o que resulta em uma complexidade de tempo de O(n2).


Como é necessário existir um acesso partilhado ao vetor, este algoritmo é mais

indicado para sistemas de memória compartilhada. O cálculo da posição final de

cada número no vetor ordenado é dividido por n processadores, que a determinam

em paralelo, ficando assim o algoritmo com uma complexidade de tempo de O(n).

No entanto, é possível implementá-lo em sistemas de memória distribuída. Neste

caso, um processo central (mestre) distribui pelos outros processadores (escravos)

n/p elementos do vetor, sendo p o número total de processadores. Cada

processador fica responsável por calcular o rank de cada um dos seus n/p

elementos. No final, os cálculos são reportados ao processo central, que constrói o

vetor ordenado. Esta distribuição só compensa quando n é suficientemente grande,

devido ao custo das operações de comunicação. Uma outra limitação do uso deste

56

algoritmo neste tipo de sistema é a utilização de uma grande quantidade de

memória, uma vez que cada processador precisa de uma cópia do vetor

desordenado e de um vetor do tamanho deste último para poder posicionar os

elementos repetidos ordenados na posição correspondente. Utilizando n2

processadores e uma estrutura em árvore, a complexidade de tempo diminui para

O(log n) [Mayr,1995]. Cada processador executa a comparação de um elemento

com outro, somando-se os resultados de cada comparação cada vez que se muda

de nível na árvore, como ilustrado na Figura 29.

Como a utilização de n2 processadores (e até mesmo de n processadores,

quando n é muito grande) se torna proibitiva, é comum agrupar números e

distribuí-los pelos processadores disponíveis. Partindo do princípio que temos m

grupos, seriam necessários apenas n/m processadores para calcular a posição no

vetor ordenado em cada grupo de números (sem que este cálculo seja paralelizado).

No entanto, o número de operações em cada processador aumentaria m vezes.

Para i := 0 até n faça em paralelo Para cada númeroinício rank := 0; Para i := 0 até n faça Conta os números menores que a[i] Se (a[i] > a[j]) ou (a[i] =a[j] e i<j) então

rank :=rank+1; b[rank] := a[i]; Copia a[i] na sua posição correta em bfim


Figura 29: Funcionamento do Rank Sort paralelo.

Algoritmo 10 - Versão paralela do algoritmo Rank Sort.

57

A versão paralela do Rank sort é bem mais eficiente que a versão seqüencial,

pois tem complexidade O(log n) [Mayr,1995], enquanto que a versão seqüencial,

apresenta uma complexidade de O(n²) [Amato, 1998].

4.6 COUNTING SORT

Outro exemplo de um algoritmo estável é o counting sort. Este é uma

otimização do rank sort para o caso em que todos os números da lista a ser

ordenada são inteiros não negativos. Neste caso, a complexidade de tempo da

execução é reduzida de O(n2) para O(n). Tal como no rank sort, a idéia fundamental

é determinar, para cada número i, a quantidade de elementos menores que ele.


A idéia básica do counting sort é determinar, para cada elemento de entrada x,

o número de elementos menores que ele. Essa informação pode ser usada para

inserir o elemento x diretamente na sua posição no vetor de saída. Por exemplo, se

há 17 elementos menores que x, então x é colocado na posição de saída 18. Esse

esquema deve ser ligeiramente modificado para manipular a situação na qual vários

elementos têm o mesmo valor, pois não queremos inserir todos os elementos na

mesma posição.

No algoritmo counting sort, partimos da suposição de que a entrada é um vetor

A[1 .. n]. Utilizaremos dois outros vetores: o vetor B[1 .. n], que conterá a saída

ordenada, e o vetor C[0 .. k], um vetor auxiliar, onde k é o maior valor de A.

Segue-se uma possível versão para este algoritmo, tendo em conta a

existência de valores duplicados.

Procedimento Counting-Sort (A, B, K)

58

início1 Para i := 0 até k faça2 C[i] := 0;3 Para j := 1 até n faça4 C[A[j]] := C[A[j]]+1; 5 Agora C[i] contém o número de elementos iguais a i.6 Para i := 2 até k faça7 C[i] := C[i] + C[i-1];8 Agora C[i] contém o número de elementos menores ou iguais a i.9 Para i := n até 1 faça10 B[C[A[j]]] := A[j];11 C[A[j]] := C[A[j]] -1;fim

Um exemplo de execução do Counting sort é ilustrado na Figura 30. Após a

inicialização do laço “para” das linhas 1 e 2, inspecionamos cada elemento de

entrada no laço “para” das linhas 3 e 4. Se o valor de um elemento de entrada é i,

incrementamos C[i]. Desse modo, depois da linha 4, C[i] contém o total de

elementos de entrada iguais a i, para cada i inteiro de 0 a k. Nas linha 6 e 7

determinamos para cada valor i de 0 a k, quantos elementos de entrada são

menores ou iguais a i; mantendo uma soma atualizada do vetor C (operação

denominada prefix sum). Finalmente no laço “para” das linhas 9 a 11, cada elemento

A[j] é colocado em sua posição ordenada correta no vetor de saída B.

Figura 30: Ordenação do Counting Sort sobre um vetor de entrada A[1 .. 8].

Algoritmo 11 - Versão seqüencial do algoritmo Counting Sort.

59

As seguintes etapas do Algoritmo 11 são ilustradas na Figura 30:

(a) O vetor A e o vetor auxiliar C após a linha 4 do algoritmo 11.

(b) O vetor C após a linha 7.

(c) – (e) O vetor de saída B e vetor auxiliar C após três iterações no laço nas linhas

9 a 11, respectivamente. Apenas os elementos levemente sombreados foram

preenchidos.

(f) O vetor de saída final ordenado B.


Na paralelização do counting sort, usa-se a versão paralela do prefix sum, que

requer um tempo de O(log n) com n processadores [Algos, 2008]. Para atingir este

tempo, partimos recursivamente o vetor C ao meio e somamos as duas metades

também recursivamente, estando associada a esta computação uma árvore binária

completa, em que cada nó interno contém a soma das suas folhas descendentes. A

ordenação final pode ser feita em O(n/p), caso tenhamos n < p processadores,

dividindo-se o vetor em p sub-vetores, cada um com n/p elementos; ou então O(1),

caso tenhamos n processadores.

InícioPara i := 0 até r faça

C[i] := 0

Para i := 0 até n-1 faça

C[A[i]+1] := C[A[i]+1] + 1

PPC := ParallelPrefixSum( c )

Para i := 0 até n-1 faça

S[PPC[A[i]+1] := A[i]

fim

Algoritmo 12 - Versão paralela do algoritmo Counting Sort.

Obs.: O comando PPC := ParallelPrefixSum(c), efetua paralelamente a

operação do laço “Para”, das linhas 6 e 7 do Algoritmo 11, atribuindo ao

vetor auxiliar PPC os valores dos números de elementos menores ou

60

iguais aos elementos correspondentes no vetor C, ou seja, o valor de

PPC[i] é o número de elementos do vetor C, menores ou iguais que C[i].


O algoritmo Counting sort seqüencial pressupõe que cada um dos n elementos

de entrada é um inteiro no intervalo de 0 a k, para algum inteiro k. Quando k = O(n),

a ordenação é executada no tempo Θ(n), pois o laço “para” das linhas 1 e 2 demora

o tempo Θ(k), o laço “para” das linhas 3 e 4 demora o tempo Θ(n), o laço “para” das

linhas 6 e 7 demora o tempo Θ(k) e o laço “para” das linhas 9 a 11 demora o tempo

Θ(n). Com isso, o tempo total é Θ(k+n). E como, na prática, a ordenação por

contagem é usada quando temos k = O(n), o tempo de execução resulta em Θ(n)

[Cormen, 2002].

Em contrapartida, sua versão paralela é bastante superior, pois apresenta uma

complexidade de tempo de O(log n) [Mayr,1995].

4.7 RADIX SORT

O radix sort é um dos algoritmos de ordenação mais utilizados, devido à sua

rapidez e simplicidade de implementação. Ele parte do pressuposto que os dígitos

representam valores e que a sua posição, que está ordenada do menos significativo

para o mais significativo, indica o seu peso relativo.


Imaginando que um número tem b bits (ou dígitos, caso a notação utilizada

seja decimal), na sua versão mais simples, o algoritmo ordena os números em b

passagens, sendo que, em cada i-ésima passagem, os números são ordenados

pelo i-ésimo bit menos significativo. Este número de passagens pode ser reduzido

de b para b/r se considerarmos blocos de r dígitos em vez de um único bit. A

complexidade de tempo vai depender do algoritmo de ordenação usado, que tem de

ser estável, de modo a preservar a ordem relativa dos elementos.

61

A Figura 31 mostra a operação de radix sort sobre uma lista de sete números

de 3 dígitos. A primeira coluna é a entrada. As colunas restantes mostram a lista

após ordenações sucessivas sobre posições de dígitos cada vez mais significativas.

As colunas destacadas indicam a posição do dígito sobre o qual é feita a ordenação

para produzir cada lista a partir da anterior. O algoritmo radix sort era o algoritmo

utilizado pelas máquinas de ordenação de cartões, que agora são encontradas

apenas nos museus de informática.

O counting sort é um algoritmo de ordenação muito usado pelo radix sort, cuja

complexidade de tempo em modo seqüencial é O(n).

Radix Sort(A,d)

Para i:= 1 até d faça USAR UMA ORDENAÇÃO ESTÁVEL PARA ORDENAR A LISTA A SOBRE O DÍGITO i

Algoritmo 13 – Versão seqüencial do algoritmo Radix Sort.

O código acima para o Radix Sort é direto. O procedimento supõe que cada

elemento da lista A de n elementos tem d dígitos, onde o dígito 1 é o dígito menos

significativo e o dígito d é o dígito mais significativo.


Podemos paralelizar o radix sort usando um algoritmo de ordenação paralelo,

como o counting sort, descrito na seção anterior, atingindo-se assim um tempo de

execução de O(log n), com n processadores e b e r constantes. No entanto, em

sistemas de memória distribuída, para grandes quantidades de dados, o tempo

gasto em comunicação é muito elevado e o balanceamento da carga é muito

irregular, pois não se sabe de início o formato de todos os elementos a serem

Figura 31: Funcionamento do algoritmo Radix Sort.

62

ordenados. Por esta razão, foram propostas várias formas de dividir a carga de

trabalho entre os vários processadores, com o objetivo de diminuir estes problemas.

Uma dessas propostas é denominada de “Load Balanced Parallel Radix Sort”

[Journal, 2002], e consiste em atribuir a cada processador exatamente o mesmo

número de elementos, eliminando assim o problema da distribuição de carga, mas

gastando ainda muito tempo para redistribuir os elementos pelos processadores.

Uma outra proposta, denominada “Partitioned Parallel Radix Sort”, veio solucionar o

problema de comunicação da anterior, uma vez que elimina a redistribuição global

de elementos ao ordená-los, inicialmente, pelos seus bits mais significativos e,

depois, distribuir grupos destes elementos pelos processadores disponíveis, onde

são ordenados pelos seus r bits menos significativos, reduzindo assim a troca de

mensagens entre processadores.

1 Procedimento radix sort(A,r)

2 início

3 Para i := 0 até b/r – 1 faça

4 offset := 0

5 Para j := 0 até 2r -1 faça

6 flag := 0

7 se o i-ésimo bloco de r bits menos significativo de A[Pk] = j então

8 flag := 0

9 index := prefix_sum(flag)

10 se flag = 1 então

11 rank := offset + índex

12 offset := ParallelPrefixSum (flag)

13 cada processo Pk envia o elemento A[Pk] para o processo Prank

14 fim

Algoritmo 14 – Versão paralela do algoritmo Radix Sort

Obs.: O algoritmo acima utiliza uma representação binária dos elementos a

serem ordenados.

b é o número de bits na representação binária de um elemento.

63

r é o número de bits menos significativos, que serão usados como base

para a ordenação.

Das linhas 3 a 13 são feitas b/r iterações, onde os elementos são

ordenados de acordo com os r bits menos significativos.

O algoritmo examina os elementos a serem ordenados r bits de cada vez,

onde r < b. Durante cada iteração do laço entre as linhas 5 e 12, o

algoritmo determina a posição dos elementos com r-bits igual a j. Na linha

13, cada processo envia o seu elemento para o processo apropriado

[Grama, 1994].

ParallelPrefixSum é o mesmo utilizado na versão paralela do algoritmo

counting sort (Algoritmo 12), enquanto prefix_sum efetua a mesma

operação do ParallelPrefixSum, porém de forma sequencial.


O Radix sort seqüencial tem complexidade O(n) [Cormen, 2002]. Sua versão

paralela, quando comparada à seqüencial, é bastante superior, pois apresenta,

assim como o counting sort, uma complexidade de tempo de O(log n) [Grama,

1994].

64

CONCLUSÃO

Durante a elaboração deste trabalho, observamos que a execução em paralelo

dos algoritmos estudados aumenta consideravelmente a eficiência de tempo da

ordenação de elementos. Além disso, existe uma grande preocupação em otimizar

certos aspectos dos algoritmos de modo a reduzir o processamento em excesso

gasto para executar uma determinada tarefa.

Normalmente, se obtêm um maior poder computacional pelo uso de

paralelismo, mas, no entanto, o desempenho de algoritmos em paralelo é bastante

afetado pela topologia e pelas características da conexão entre os processadores.

Por isso, é de extrema importância ser feita uma pré-análise do algoritmo que vai ser

implementado e do nível de processamento que vai ser necessário, pois alguns

algoritmos têm um melhor custo-benefício quando desenvolvidos de modo

seqüencial (não-paralelo).

O conceito de programação paralela está diretamente relacionado ao uso de

computadores paralelos, ou seja, computadores dotados de várias unidades de

processamento, com capacidade de executar programas paralelos.

Alguns conceitos são extremamente importantes quando se deseja

desenvolver programas em ambientes paralelos, e o primeiro passo a ser estudado

é a forma como o algoritmo pode ser paralelizado. Para resolver um problema

eficientemente em um computador paralelo, é usualmente necessário projetar

algoritmos que especifiquem múltiplas operações a cada passo.

O paralelismo em um algoritmo pode aumentar a performance de vários tipos

de arquiteturas de computador. De um modo geral, a execução dos algoritmos de

ordenação em modo paralelo é mais eficiente em relação ao tempo consumido

quando comparada com a execução em modo seqüencial, mas, no entanto,

processamentos em excesso são introduzidos pela comunicação e, em certos

casos, a distribuição pouco equilibrada limita o seu bom funcionamento.

Construir algoritmos paralelos é muito mais difícil e trabalhoso do que

algoritmos seqüenciais. Porém, para resolver problemas complexos, apenas uma

máquina (mesmo a mais rápida do mundo) nem sempre é suficiente. Logo, a

utilização dos algoritmos paralelos neste caso é imprescindível.

65

Vários problemas podem ocorrer quando se desenvolvem algoritmos

paralelos, mas recentes pesquisas mostram avanços no desenvolvimento de

ambientes para execução de tais algoritmos. Espera-se que, em poucos anos,

construir e executar um algoritmo paralelo seja uma tarefa tão comum quanto

executar um programa seqüencial hoje.

A computação paralela é a forma mais acessível de se resolver problemas que

exigem muita computação e está se difundindo cada vez mais pela queda no custo

dos componentes eletrônicos.

66

REFERÊNCIAS BIBLIOGRÁFICAS

[Aurélio, 2002] Aurélio, B.H.F; “Mini Aurélio século XXI – minidicionário da língua

portuguesa”, Nova Fronteira, 2002.

[Cormen, 2002] Cormen, T.H.; Leiserson, C. E.; Rivest, R. L.; Sten, C.;

“Algoritmos - tradução da 2ª edição americana – Teoria e Prática”,

Campus, 2002.

[Grama, 1994] Grama, A.; Karypis,G.; Kumary,V., “Introduction to Parallel

Compunting”, Pearson Addison Wesley,1994.

[Szwarcfiter,1994] Szwarcfiter, J.L.; Markenzon, L., “Estruturas de Dados e seus

Algoritmos” 2ª edição revista, LTC, 1994.

[Mayr,1995] Mayr, E.W.; Puech, C., “Lecture Notes in Computer Science”,

Springer, 1995.

[Bertsekas, 1989] D. P. Bertsekas, J. N. Tsitsiklis, “Parallel and Distributed

Computation”, Prentice-Hall International Editions, 1989.

[Navaux, 1989] NAVAUX, P. O. A. “Introdução ao processamento paralelo. RBC -

REVISTA BRASI-LEIRA DE COMPUTAÇÃO”, Rio de Janeiro, v.5,

n.2, p. 31-43, 1989.

[Amorim, 1988] Amorim, Cláudio L., Barbosa, Valmir C., Fernandes, Edil S. T.

“Uma Introdução à Computação Paralela e Distribuída”, Campinas,

SP, UNICAMP, IMECC, 1988.

[Ferrari, 1998] Ferrari, A. J.; “JPVM: Network parallel computing in Java”, ACM,

1998. Ferrari, A. J.; “Workshop on Java for High-Performance

Network Computing”, Palo Alto, 1998.

67

[Baker, 1998] Baker, M. et al. “mpiJava: A Java Interface to MPI. Submitted to

First UKWorkshop on Java for High Performance Network

Computing”, Europar, 1998.

[Baker, 1999] Baker, M. et al. “mpiJava: An Object-Oriented Java Interface to

MPI”, Europar, 1999.

[Taboada, 2003] Taboada, G. L.; Tourino, J.; Doallo, R. “Performance Modeling

and Evaluation of Java Message-Passing Primitives on a Cluster”.

Lecture Notes in Computer Science, v.2840, p.29-36, 2003.

[Batcher, 1968] Batcher, K. E. “Sorting Networks and their applications”.

proceedings of the AFIPS Spring Joint,1968

[Andrews, 2000] G. Andrews. “Multithreaded, Parallel and Distributed

Programming”, Addison-Wesley, 2000

[Quinn, 1994] Quinn, Michael J. – “Parallel Computing: Theory and Practice”.

Mc-GRAW-HILL, 1994.

[Wagner, 1987] K.Wagner. “More complicated questions about maxima and minima,

and some closures of NP”. Theoretical Computer Science, 1987.

[Amato, 1998] N. M. Amato, R. Iyer, S. Sundaresan, Y. Wu, “A Comparison of

Parallel Sorting Algorithms on Different Architectures”, 1998

[Sedgewick, 1988] Sedgewick, R., “Algorithms , 2a. edição”. Pearson Addison

Wesley,1988.

[Journal, 2002] Lee, S. J.; Dongseung, K.; Sohn, A.; “Journal of Parallel and

Distributed Computing”. Academic Press, 2002.

68

[Hoare, 2008] http://en.wikipedia.org/wiki/C._A._Hoare

acessado em 26 - 06 - 2008.

[Bitonic, 2008] http://en.wikipedia.org/wiki/Bitonic_sorter

acessado em 26 - 06 - 2008.

[Algos, 2008] http://algos.inesc-id.pt/~scm

acessado em 25 - 06 - 2008.

[Wotug, 2008] http://www.wotug.org/parallel/

acessado em 12 - 03 -2008.

[DCS, 2008] http://www.dcs.ed.ac.uk/home/stg/pub/P/par_alg.html

acessado em 12 - 03 -2008.

[Parallel, 2008] http://en.wikipedia.org/wiki/Parallel_algorithm

acessado em 15 - 03 -2008.

[Pipeline, 2008] http://en.wikipedia.org/wiki/Pipeline_%28computing%29

acessado em 15 - 03 -2008.

[PComp, 2008] http://en.wikipedia.org/wiki/Parallel_computing

acessado em 15 - 03 -2008.

[Wikiac, 2008] https://wikiac.dei.uc.pt/index.php/Pipeline

acessado em 03 - 05 -2008.

[Algorithms, 2008] http://www.cs.cmu.edu/~scandal/nesl/algorithms.html

acessado em 12 - 03 -2008

[MPI, 2008] http://www.lam-mpi.org/

acessado em 20 - 04 - 2008.

http://www.lam-mpi.org/

http://www.cs.cmu.edu/~scandal/nesl/algorithms.html

https://wikiac.dei.uc.pt/index.php/Pipeline

http://en.wikipedia.org/wiki/Parallel_computing

http://en.wikipedia.org/wiki/Pipeline_(computing)

http://en.wikipedia.org/wiki/Parallel_algorithm

http://www.dcs.ed.ac.uk/home/stg/pub/P/par_alg.html

http://www.wotug.org/parallel/

http://algos.inesc-id.pt/~scm

http://en.wikipedia.org/wiki/Bitonic_sorter

http://en.wikipedia.org/wiki/C._A._Hoare

69

[PVM, 2008] http://www.epm.ornl.gov/pvm/pvm_home.html

acessado em 20 - 04 - 2008.

[PSC, 2008] http://www.psc.edu/machines/cray/t3d/t3d.html

acessado em 03 - 05 - 2008.

[Bublesort, 2008] http://pt.wikipedia.org/wiki/Bubble_sort

acessado em 10 - 04 - 2008.

[Quicksort, 2008] http://pt.wikipedia.org/wiki/Quick_sort

acessado em 10 - 04 - 2008.

[Mergesort, 2008] http://pt.wikipedia.org/wiki/Merge_sort

acessado em 10 - 04 - 2008.

[Radixsort, 2008] http://pt.wikipedia.org/wiki/Radix_sort

acessado em 10 - 04 -2008.

[Countsort, 2008] http://pt.wikipedia.org/wiki/Count_sort

acessado em 10 - 04 - 2008.

[OrdEstavel, 2008] http://pt.wikipedia.org/wiki/Ordenação_estável

acessado em 25 - 06 - 2008.

[DCA, 2008] http://www.dca.fee.unicamp.br/~jro/ea960/pipeline/

Pipeline.htm

acessado em 12 - 06 - 2008.

[Orbita1, 2008] h ttp://orbita.starmedia.com/~computacaounifenas/

paralela/introducao.htm

acessado em 06 - 06 - 2008.

http://orbita.starmedia.com/~computacaounifenas/

http://www.dca.fee.unicamp.br/~jro/ea960/pipeline/

http://pt.wikipedia.org/wiki/Ordena%C3%A7%C3%A3o_est%C3%A1vel

http://pt.wikipedia.org/wiki/Count_sort

http://pt.wikipedia.org/wiki/Radix_sort

http://pt.wikipedia.org/wiki/Merge_sort

http://pt.wikipedia.org/wiki/Quick_sort

http://pt.wikipedia.org/wiki/Bubble_sort

http://www.psc.edu/machines/cray/t3d/t3d.html

http://www.epm.ornl.gov/pvm/pvm_home.html

70

[Orbita2, 2008] http://orbita.starmedia.com/~computacaounifenas/

paralela/arquiteturas.htm

acessado em 06 - 06 - 2008.

[NUMA, 2008] http://en.wikipedia.org/wiki/ Ccnuma#Cache_

coherent_NUMA_.28ccNUMA.29

acessado em 10 - 06 -2008.

http://www.dei.isep.ipp.pt/~nsilva/ensino/ArqC/arqc2004-

2005/risc.htm#Pipeline

acessado em 02 - 06 – 2008.

[Teknoel, 2008] http://www.teknoel.com/show/?file=/theory/ connectionGrid/

cm- 2.htm

acessado em 03 - 05 - 2008.

[Angelfire, 2008] http://www.angelfire.com/pro/ pipeline/um_algoritmo_de_

pipeline_baseia.htm

acessado em 12 - 06 - 2008.

[W.alg.ord, 2008] http://pt.wikipedia.org/wiki/Algoritmo_de_ordenação

acessado em 10 - 04 - 2008.

[Hipercubo, 2008] http://pt.wikipedia.org/wiki/Hipercubo

acessado em 13 - 07 - 2008.

[Dei, 2008]

http://pt.wikipedia.org/wiki/Hipercubo

http://pt.wikipedia.org/wiki/Algoritmo_de_ordena%C3%A7%C3%A3o

http://www.angelfire.com/pro/

http://www.teknoel.com/show/?file=/theory/

http://www.dei.isep.ipp.pt/~nsilva/ensino/ArqC/arqc2004-%20%20%20%20%20%20%20%202005/risc.htm#Pipeline

http://www.dei.isep.ipp.pt/~nsilva/ensino/ArqC/arqc2004-%20%20%20%20%20%20%20%202005/risc.htm#Pipeline

http://en.wikipedia.org/wiki/

http://orbita.starmedia.com/~computacaounifenas/

Documents

André Luis Faria de Oliveira Uéverton dos Santos Souza ... · André Luis Faria de Oliveira Uéverton dos Santos Souza ... 12 Modelo de troca de mensagens.....24 13 Modelo UMA