View
218
Download
0
Category
Preview:
Citation preview
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
UFRJ – Universidade Federal do Rio de Janeiro
_________________________________________
Prof. Danilo Artigas da Rocha, M.Sc. – Avaliador
UFRJ – Universidade Federal do Rio de Janeiro
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.1 FUNCIONAMENTO DO ALGORITMO NA FORMA SEQÜENCIAL...........42
4.2.2 FUNCIONAMENTO DO ALGORITMO NA FORMA PARALELA ...............44
4.2.3 ANÁLISE DAS VERSÕES...........................................................................46
4.3 QUICK SORT....................................................................................................46
4.3.1 FUNCIONAMENTO DO ALGORITMO NA FORMA SEQÜENCIAL...........46
4.3.2 FUNCIONAMENTO DO ALGORITMO NA FORMA PARALELA ...............48
4.3.3 HYPERQUICKSORT (UMA VARIAÇÃO DO QUICK SORT) .....................50
4.3.4 ANÁLISE DAS VERSÕES...........................................................................52
4.4 BITONIC SORT.................................................................................................52
4.4.1 FUNCIONAMENTO DO ALGORITMO NA FORMA PARALELA................52
4.5 RANK SORT.....................................................................................................54
4.5.1 FUNCIONAMENTO DO ALGORITMO NA FORMA SEQÜENCIAL...........55
4.5.2 FUNCIONAMENTO DO ALGORITMO NA FORMA PARALELA................55
4.5.3 ANÁLISE DAS VERSÕES...........................................................................57
4.6 COUNTING SORT............................................................................................57
4.6.1 FUNCIONAMENTO DO ALGORITMO NA FORMA SEQÜENCIAL...........57
4.6.2 FUNCIONAMENTO DO ALGORITMO NA FORMA PARALELA................59
4.6.3 ANÁLISE DAS VERSÕES...........................................................................60
4.7 RADIX SORT....................................................................................................60
4.7.1 FUNCIONAMENTO DO ALGORITMO NA FORMA SEQÜENCIAL...........60
4.7.2 FUNCIONAMENTO DO ALGORITMO NA FORMA PARALELA................61
4.7.3 ANÁLISE DAS VERSÕES...........................................................................63
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].
4.2.2 Funcionamento do algoritmo na forma paralela
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].
4.2.3 Análise das versões
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.
4.3.1 Funcionamento do algoritmo na forma seqüencial
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.
4.3.2 Funcionamento do algoritmo na forma paralela
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.
4.3.4 Análise das versõ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].
4.4.1 Funcionamento do algoritmo na forma paralela
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.
4.5.1 Funcionamento do algoritmo na forma seqüencial
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).
4.5.2 Funcionamento do algoritmo na forma paralela
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
4.5.3 Análise das versões
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.
4.6.1 Funcionamento do algoritmo na forma seqüencial
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.
4.6.2 Funcionamento do algoritmo na forma paralela
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].
4.6.3 Análise das versões
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.
4.7.1 Funcionamento do algoritmo na forma seqüencial
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.
4.7.2 Funcionamento do algoritmo na forma paralela
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.
4.7.3 Análise das versões
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.
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.
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]
Recommended