UFRPE-Licenciatura em Computação
Disciplina:Computação Paralela e Distribuída
Equipe: Marcos Tadeu A de Souza
Joacir Siqueira
Algoritmo Hiperquicksort
Índice
•Comentário do algoritmo......de 3 a 8
Transcrição do algoritmo, com comentários para os
procedimentos principais, conforme marcador numérico,
inserido no lado direito.
•Demonstração prática.........de 9 a 13
Aplicação
do
algoritmo
comentado, com um exemplo concreto.
anteriormente
2
Algoritmo Hiperquicksort
(Comentário do algoritmo)
ALGORITMO HIPERQUICKSORT PARALELO
Global n
d
i
Local logical.num
partner
root
splitter
(Nº inicial de elementos por processador)
(Dimensão do hipercubo)
(Nº da dimensão do hipercubo em uso)
(Numeração única do processador)
(Processador sócio na troca)
(Processador raiz no hipercubo em uso)
(Valor médio do processador raiz)
3
Algoritmo Hiperquicksort
(Comentário do algoritmo)
begin
for all Pj , where 0  j < 2d do (1)
Ordene os n elementos usando o quicksort seqüencial (2)
if d  0 then (3)
for i  d downto 1 do (4)
root  root of the binary i-cube containing processor
logical.num (5)
if logical.num = root then (6)
splitter  valor médio do processador logical.num (7)
endif
Processador raiz envia valor médio para demais
processadores do i-cubo (8)
Use splitter para partição dos valores ordenados em uma
lista dos maiores e dos menores
partner  logical.num  2 (i-1) (9)
4
Algoritmo Hiperquicksort
(Comentário do algoritmo)
partner
partner
partner
partner
if logical.num > partner then (10)
Envia elementos menores para o processador
Recebe
elementos
maiores
do
processador
else (logical.num < partner)
Envia elementos maiores para o processador
Recebe
elementos
menores
do
processador
endif
Junte as 02 listas numa lista única ordenada (11)
endfor
endif
endfor
end
5
Algoritmo Hiperquicksort
(Comentário do algoritmo)
(1) Para todo processador índice j, onde j seja maior ou
igual a zero e menor que a dimensão do hipercubo
(2) Cada processador executa seqüencialmente o algoritmo
quicksort, com sua lista
(3) Enquanto d for maior que zero, executar as instruções
do laço
(4) A variável i recebe o valor de d, decrementado até 1. A
cada ciclo i será decrementado até o valor limite 1.
Quando i for igual a 1, o algoritmo se encerra.
(5) A variável root recebe o menor número de identificação
(em binário) do processador, do hipercubo que está
sendo processado.
(6) Se a numeração binária única do processador for a
mesma da variável root, executar os procedimentos
indicados no sublaço.
6
Algoritmo Hiperquicksort
(Comentário do algoritmo)
(7) A variável splitter recebe o valor médio do processador cuja
numeração binária única é igual a da variável root
(8) A variável splitter é divulgada para os demais processadores
do hipercubo
(9) Efetua o cálculo do processador parceiro, para todos os
processadores do hipercubo. O cálculo é realizado através da
operação lógica OU EXCLUSIVO, entre a numeração binária do
processador e o número binário calculado pela expressão 2 (i-1)
Assim, para o processador 1 ( 01 em binário ), quando i=2, tem
como parceiro ( partner ):
01
10
11 (processador 3)
7
Algoritmo Hiperquicksort
(Comentário do algoritmo)
(10) Para cada processador, executa um dos procedimentos
condicionais, conforme sua numeração seja menor ou maior que
a do seu parceiro. Cada processador que possui numeração
maior que seu parceiro, envia para ele os elementos de sua lista
menores que o splitter (valor médio) do processador root do
hipercubo corrente e recebe deste os valores maiores que o
splitter.
(11) Após as permutações, entre processadores e seus parceiros,
junte/ordene suas listas numa lista única de elementos.
8
Algoritmo
Hiperquicksort
Algoritmo
Hiperquicksort
(Demonstração Prática)
P2 11 36 44 50 53 67 86 95
P3 1
P0 8 16 17 48 49 66 96 97
P1 39 47 51 54 58 65 76 82
5 15 16 23 35 44 81
Aqui verificamos inicialmente os passos (1) e (2), ou seja distribuição dos
elementos entre os processadores e a ordenação de suas listas. A seguir como
d = 2 - passo (3), entra-se no laço seguinte – passo (4), com i recebendo
inicialmente o valor de d, ou seja i=2. Como estamos inicialmente trabalhando
com todo o hipercubo, o processador de menor numeração P0, é selecionado
como raiz – root recebe a numeração de P0 - passo (5). O valor médio de P0
(48, splitter) é divulgado para todos os demais processadores – passo (8). A
seguir cada processador calcula seu processador parceiro – passo (9). Assim
formam-se os pares P0/P2 e P1/P3.
9
Algoritmo
Hiperquicksort
Algoritmo
Hiperquicksort
(Demonstração Prática)
P2 49 66 96 97 50 53 67 86 95
P3 51 54 58 65 76 82 81
P0 8 16 17 48 11 36 44
P1 39 47 1
5 15 16 23 35 44
Após o cálculo dos parceiros ( partners), efetuam-se as permutações
indicadas no passo (10). O processador P0 envia a P2, os elementos de sua
lista maiores que o splitter (valor médio do processador raiz P0) e este envia
para P0 os elementos de sua lista menores que o splitter. Os mesmo processo
ocorre com a dupla P1/P3. Cada processador junta/ordena em uma lista
única, os elementos recebidos de seus parceiros e os elementos
remanescentes de sua lista original.
10
Algoritmo
Hiperquicksort
Algoritmo
Hiperquicksort
(Demonstração Prática)
P2 49 50 53 66 67 86 95 96 97
P3 51 54 58 65 76 81 82
P0 8 11 16 17 36 44 48
P1 1
5 15 16 23 35 39 44 47
Reiniciando o processo, entra-se no passo (4), decrementando-se i mais uma
vez, fazendo i=1 (2-1). Como i agora é igual a 1, ocorrerá o processamento
em paralelo, nas 02 metades do hipercubo original. Numa das metades temos
um hipercubo formado por P0/P1 e noutra P2/P3. Em cada uma das metades,
será escolhido um root (P0 e P2) – passo (5). Dentro de cada uma das
metades, a variável splitter receberá o valor médio do root (indicados em azul
na demonstração acima) – passo (7) e esta será informada aos demais
processadores pertencentes ao hipercubo em curso, ou seja, P0 informa P1 e
P2 informa P3 – passo (8)
11
Algoritmo
Hiperquicksort
Algoritmo
Hiperquicksort
(Demonstração Prática)
P2 49 50 53 66 67 51 54 58 65
P3 86 95 96 97 76 81 82
P0 8 11 16 17 1
P1 36 44 48 23 35 39 44 47
5 15 16
A seguir, dentro de cada uma das metades, cada processador calcula seu
partner – passo (9). Ocorrem as permutações indicadas no passo (10),
dentro da dimensão de cada uma das dimensões do hipercubo (cada uma
das metades). O processador P0 envia a P1, os elementos de sua lista
maiores que o splitter (valor médio do processador raiz P0) e este envia
para P0 os elementos de sua lista menores que o splitter. Os mesmo
processo ocorre com a dupla P2/P3. Cada processador junta/ordena em uma
lista única, os elementos recebidos de seus parceiro e os elementos
remanescentes de sua lista original.
12
Algoritmo
Hiperquicksort
Algoritmo
Hiperquicksort
(Demonstração Prática)
P2 49 50 51 53 54 58 65 66 67
P3 76 81 82 86 95 96 97
P0 1
P1 23 35 36 39 44 44 47 48
5
8 11 15 16 16 17
Reiniciando o processo, entra-se no passo (4), decrementando-se i mais uma
vez, fazendo i=0 (1-1). Como i agora é igual a 0, nenhum dos procedimentos
seguintes do laço é executado, finalizando-se o algoritmo. Como podemos
perceber, os elementos encontram-se devidamente ordenados, localizando-se
os de menor valor nos processadores de menor numeração e os de maior
valor nos processadores de maior numeração.
13