Descrição do Funcionamento do Algoritmo Hiperquicksort

Joacir Bezerra de Siqueira, Marcos Tadeu A. de Souza

Professor Jones Oliveira de Albuquerque

Universidade Federal Rural de Pernambuco (UFRPE)

Departamento de Matemática e Física

Curso de Licenciatura em Computação

joacirsiqueira@terra.com.br, mtasufrpe@yahoo.com.br

Resumo. Este paper tem como finalidade principal, descrever o funcionamento do ALGORITMO HYPERQUICKSORT (HYPERCUBE MULTICOMPUTER) descrito no Capítulo 10, página 279 do livro Parallel Programming in C with MPI and OpenMP de Michael J. Quinn. Apresenta um exemplo prático onde é demonstrado passo-a-passo todo o desenvolvimento do algoritmo. No exemplo, para melhor compreensão, utiliza-se uma lista com 32 números para ser ordenado por 8 processadores de um Hypercubo.

Abstract. This paper has as main purpose, to describe the operation of HYPERQUICKSORT ALGORITHM (HYPERCUBE MULTICOMPUTER) described in the Chapter 10, page 279 of the book Parallel Programming in C with MPI and OpenMP of Michael J. Quinn. It presents a practical example where step-to-step is demonstrated the whole development of the algorithm. In the example, for better understanding, a list is used with 32 numbers to be ordered by 8 processors of a Hypercube.

Palavra-chave. Hypercubo, processadores, programação paralela.

Introdução. O estudo do algoritmo Hyperquicksort é bastante interessante, pois, assim pode-se ter uma idéia inteiramente precisa da Programação Paralela e Distribuída. O algoritmo Hyperquicksort que será analisado, inicia recebendo os valores aleatórios contidos em uma lista de valores. Estes valores são distribuídos uniformemente entre os processadores do hypercubo. É necessário deter o conhecimento do quicksort , pois cada processador fará inicialmente o quicksort em na relação de valores que recebeu da lista inicial. A seguir é apresentado o algoritmo e será analisado um exemplo.

ALGORITMO HIPERQUICKSORT PARALELO.

Global n (Nº inicial de elementos por processador)

d (Dimensão do hipercubo)

i (Nº da dimensão do hipercubo em uso)

Local logical.num (Numeração única do processador)

partner (Processador sócio na troca)

root (Processador raiz no hipercubo em uso)

splitter (Valor médio do processador raiz)

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)

if logical.num > partner then (10)

Envia elementos menores para o processador partner

Recebe elementos maiores do processador partner

else (logical.num < partner)

Envia elementos maiores para o processador partner

Recebe elementos menores do processador partner

endif

Junte as 02 listas numa lista única ordenada (11)

endfor

endif

endfor

end

(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.

(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 ):

0001+0010 = 0011 (processador 3)

(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.

Exemplo de execução do Algoritmo.

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 = 3 - passo (3), entra-se no laço seguinte – passo (4), com i recebendo inicialmente o valor de d, ou seja i=3. 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 (44, 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/P4, P1/P5, P2/P6 e P3/P7.

Inicialmente temos a seguinte lista de valores aleatórios:

60	2	44	32	21	18	3	90	20	22	10	14	38	28	30	6	4	70	65	35
25	8	15	55

P6 P7

P4 P5

P2 P3

P0 P1

Os números da lista são distribuídos uniformemente entre os processadores do hypercubo, ficando do seguinte modo:

P2 3 90 20 P3 22 10 14 P6 65 35 25 P7 8 15 55

P0 60 2 44 P1 32 21 18 P4 38 28 30 P5 6 4 70

Neste momento cada processador realiza o seqüencial quicksort em sua lista de valores. Então fica:

P2 3 20 90 P3 10 14 22 P6 25 35 65 P7 8 15 55

P0 2 44 60 P1 18 21 32 P4 28 30 38 P5 4 6 70

Como temos um único Hypercubo, então o variável root= 0000_b. Neste momento temos a logical.num = root. Daí o processador P0 informa a todos processadores que fazem parte do hypercubo, seu número médio. No exemplo é o numero (44). Portanto a variável splitter = 44. Será utilizado por todos processadores.

A Dimensão do Hypercubo é 2^d. Como d=3 temos 2³ = 8 processadores

Determinação do partner:

partner ← logical.num. 2^{i – 1} { Na 1ª passagem temos 2^3-1 = 2² = 4 = 0100_b }.

partner: P0 = 0100 P1 = 0100 P2 = 0100 P3 = 0100

0000 0001 0010 0011

0100_b 0101_b 0110_b 0111_b

P4 = 0100 P5 = 0100 P6 = 0100 P7 = 0100

0100 0101 0110 0111

0000_b 0001_b 0010_b 0011_b

Portanto os processadores P0 com P4, P1 com P5, P2 com P6 e P3 com P7, farão a troca entre si da seguinte maneira: O processado de menor índice envia seus valores maiores do que seu valor médio (44) para seu parceiro e recebe do seu parceiro os valores menores do que o valor médio (44). Daí fica:

P4 60 P5 70 P6 90 65 P7 55

P0 2 44 28 30 38 P1 18 21 32 4 6 P2 3 20 25 35 P3 10 14 22 8 15

De acordo com o algoritmo, faz-se um seqüencial quicksort em cada processador ficando do seguinte modo:

P4 60 P5 70 P6 65 90 P7 55

P0 2 28 30 38 44 P1 4 6 18 21 32 P2 3 20 25 35 P3 8 10 14 15 22

Neste passo d é decrementado de 1. Fica então i = 2. Portanto demos dois cubos:

P2 P3 P6 P7

P0 P1 P4 P5

O processador P0 envia seu valor médio (30) para os processadores P1, P2 e P3. O processador P4 envia seu valor médio (60) para os processadores P5, P6 e P7.

Determinação do partner:

partner ← logical.num. 2^{i – 1} { Na 2ª passagem temos 2^2-1 = 2¹ = 2 = 0010_b }.

partner: P0 = 0010 P2 = 0010 P4 = 0010 P6 = 0010

0000 0010 0100 0110

0010_b 0000_b 0110_b 0100_b

P1 = 0010 P3 = 0010 P5 = 0010 P7 = 0010

0001 0011 0101 0111

0011_b 0001_b 0111_b 0101_b

Portanto os processadores P0 com P2, P1 com P3, P4 com P6 e P5 com P7, farão a troca entre si da seguinte maneira: O processado de menor índice envia seus valores maiores do que seu valor médio para seu parceiro e recebe do seu parceiro os valores menores do que o valor médio. Daí fica:

P2 38 44 35 P3 32 P6 65 90 P7 70

P0 2 28 30 3 20 25 P1 4 6 18 21 8 10 14 15 22 P4 60 P5 55

Cada processador realiza o seqüencial quicksort. Fica ordenado da seguinte maneira:

P2 35 38 44 P3 32 P6 65 90 P7 70

P0 2 3 20 25 28 30 P1 4 6 8 10 14 15 18 21 22 P4 60 P5 55

Neste passo d é decrementado de 1. Fica então i = 1. Portanto temos:

P2 P3 P6 P7

P0 P1 P4 P5

Determinação do partner:

partner ← logical.num. 2^{i – 1} { Na 2ª passagem temos 2^2-1 = 2¹ = 2 = 0010_b }.

partner: P0 = 0001 P2 = 0001 P4 = 0001 P6 = 0001

0000 0010 0100 0110

0001_b 0011_b 0101_b 0111_b

P1 = 0010 P3 = 0010 P5 = 0010 P7 = 0010

0001 0011 0101 0111

0000_b 0010_b 0100_b 0110_b

Portanto os processadores P0 com P1, P2 com P3, P4 com P5 e P6 com P7, farão a troca entre si da seguinte maneira: O processado de menor índice envia seus valores maiores do que seu valor médio para seu parceiro e recebe do seu parceiro os valores menores do que o valor médio. Valor médio: P0 = 20; P2 = 38; P4 = 60; P6 = 65. Daí fica:

P1 25 28 30 21 22 P3 44 P5 P7 90 70

P0 2 3 20 4 6 8 10 14 15 18 P2 35 38 32 P4 60 55 P6 65

Cada processador realiza o seqüencial quicksort. Fica ordenado da seguinte maneira:

P1 21 22 25 28 30 P3 44 P5 P7 70 90

P0 2 3 4 6 8 10 14 15 18 20 P2 32 35 38 P4 55 60 P6 65

Finalmente, os processadores devolvem para Lista os valores contidos em cada processador.

2	3	4	6	8	10	14	15	18	20	21	22
25	28	30	32	35	38	44	55	60	65	70	90

Conclusão.

Verifica-se que se trata de um algoritmo eficaz, podendo efetuar implementação. Na realidade é um ótimo estudo para o entendimento da Programação Paralela e Distribuída.

Referência Bibliográfica.

Michael J. Quinn. Parallel Programming in C with MPI and OpenMP. McGRAW-HILL, 2003.