List Ranking: Um Estudo Experimental
Dissertação de Mestrado
Orientando: Guilherme Pereira Vanni
Orientador: Prof. Siang Wung Song
Departamento de Ciência da Computação
Instituto de Matemática e Estatística
Universidade de São Paulo
Introdução

Definição
Lista ligada: uma seqüência de nós tal que cada nó aponta para
outro nó, chamado seu sucessor, e não há ciclo em tal lista.
O problema de List Ranking consiste em determinar o rank para
todos os nós, isto é, a distância para o último nó da lista.
Rank:
4
2
0
5
1
6
3
6
5
4
3
2
1
0
Importância
[Reif 1993]
Síntese de algoritmos paralelos para grafos
Modelo CGM
- Arquitetura: Memória distribuída.
- Problema de tamanho n
- p processadores cada um com memória local O(n/p).
- Rodada de computação + rodada de comunicação.
- Em cada rodada cada processador envia e recebe
O(n/p) dados.
- Algoritmo eficiente
minimizar o nº rodadas de
comunicação bem como o tempo de computação local
total.
- parâmetros: n e p.
Algoritmos paralelos CGM para LR
Autor
Número de Rodadas
Algoritmo
Denhe e Song
O(log p + log log n)
probabilístico
Denhe e Song
O(ln* n log p)
probabilístico
O(p)
determinístico
O(log p)
determinístico
Sibeyn
Denhe et al.
Lista ligada armazenada em 4 proc.
P1
P2
P3
P4
1º
n
Algoritmo seqüencial O(n).
Algoritmo paralelo usando “pointer jumping” O(log n).
1
1
1
1
1
1
1
0
2
2
2
2
2
2
1
0
4
4
4
4
3
2
1
0
7
6
5
4
3
2
Cada sucessor pode estar em outro proc.
rodadas de comunicação.
1
0
O(log n)
[Dehne e Song 1997]
Amostra: cada nó é escolhido com probabilidade de 1/p.
nó da amostra = pivô
m = distância máxima entre 2 pivôs
m <= 3 p ln n com alta probabilidade
Prob. {m > c(3 p ln n)} <= 1/ n^c, c >2
Algoritmo Probabilístico - nomenclatura
nextPivot(x)
x
m
distToPivot(x)
nextPivot(x) = pivô mais próximo a direita
distToPivot(x) = distância entre x e nextPivot(x)
List ranking modificado
Determinar para cada x:
nextPivot(x) e distToPivot(x)
Algoritmo Probabilístico
n – nós, p – processadores, O(n/p) – nós por processador
1. Cada processador seleciona nós como pivô com probabilidade 1/p.
2. Todos processadores resolvem o problema do list ranking
Modificado.
3. Os valores de nextPivot(x) e distToPivot(x) de todo pivô são
enviados de cada processador a todos os outros.
4. Cada processador resolve seqüencialmente o problema do list
ranking para seus nós.
Número de rodadas do algoritmo
passo
nº rodadas
1
–
2
log 3 p + log ln n
O(log p + log log n) rodadas
3
1
de comunicação com alta prob.
4
–
total
1 + log 3 p + log ln n
Algoritmo Determinístico - definições
[Dehne et al. 2002]
r-ruling set: subconjunto de elementos selecionados de L, onde:
1. Dois vizinhos nunca são selecionados.
2. A distância de qualquer elemento ao próximo elemento
selecionado é no máximo r.
Exemplo: uma lista L e um 3-ruling set R
L
R
3
2
3
2
2
Algoritmo Determinístico
1. Computar O(p²)-ruling set R com |R| = O(n/p).
2. Fazer um broadcast de R para todos os processadores.
3
2
3
2
2
3. Calcular seq., em cada processador o List Ranking de R.
12
9
7
4
2
4. Obter para (L - R) a dist. para o próx. elemento de R (pointer jumping).
12
9
2
1
7
1
4
2
1
2
1
1
5. Calcular em cada processador os ranks dos seus elementos.
12
12
9
11
10
9
7
8
7
4
6
5
4
2
3
2
1
Número de rodadas do algoritmo
passo
nº rodadas
1
log p ?
2
log p
3
–
4
log p²
5
–
total
2 log p + log p²
O(log p) rodadas de
comunicação
O(p²)-ruling set
Quebra de simetria
Rotular cada elemento de L com o índice do processador
p rótulos
no máximo
Denote por s[i] o sucessor do elemento i
s[i] é um máximo local
L(s[i])
L(i)
L(s[s[i]])
Selecionar inicialmente todos os máximos locais
p-1
p-1
distância máxima de 2 (p - 1)
nº máx. de elementos selecionados = O(n)
Algoritmo para determinar O(p²)-ruling set
1. Marcar todos os elementos da lista como nós não selecionados.
2. Para todo i em L fazer em paralelo
Se L(i) < L(s[i]) > L(s[s[i]]) então
marcar s[i] como selecionado.
3. Seqüencialmente, em cada processador, processar as sublistas de
elementos subseqüentes que estão armazenados no mesmo processador.
Para cada sublista, marcar todo segundo elemento. Se a sublista tem
somente dois elementos, e ambos os vizinhos não possuem um rótulo
menor, marcar os elementos da sublista como não selecionado.
Algoritmo O(p²)-ruling set (continuação)
4. Para k = 1 ... log p fazer
4.1. Para todo elemento i em L fazer em paralelo
Se s[i] é não selecionado então
s[i]
s[s[i]].
4.2. Para todo elemento i em L fazer em paralelo
Se (i, s[i], s[s[i]] são selecionados) e not ( L(i) < L(s[i]) > L(s[s[i]]) )
e ( L(i) <> L(s[i]) ) e ( L(s[i]) <> L(s[s[i]]) ) então
marcar s[i] como não selecionado.
4.3. Seqüencialmente, em cada processador, processar as sublistas de
elementos selecionados subseqüentes da lista que estão armazenados
no mesmo processador. Para cada sublista marcar todo segundo
elemento como não selecionado. Se a sublista tem apenas dois
elementos e ambos os vizinhos não possuem rótulos menores, então
marcar ambos elementos da lista como não selecionado.
5. Marcar o último elemento como selecionado.
Resultados Experimentais

Reid-Miller algoritmos PRAM com resultados satisfatórios
para o Cray C-90, mas específicos para a máquina.

Gustedt apresenta dois algoritmos CGM (PC-cluster):
probabilístico e um determinístico.

Sibeyn algoritmo CGM com O(p) rodadas de comunicação.
Para p = 36 e n = 600 mil aceleração de aproximadamente 5.

Chan e Dehne algoritmo com O(log p) rodadas de
comunicação. Resultados conhecidos mais eficientes.
Gustedt - desempenho do programa determinístico
Tempo de execução por elemento para o programa determinístico
Gustedt - desempenho do programa probabilístico
Tempo de execução por elemento para o programa probabilístico
Chan e Dehne - desempenho do programa determinístico
Curva dos tempos observados na plataforma ultra (switch de 100Mb)
Chan e Dehne - desempenho do programa determinístico
Curva dos tempos observados na plataforma thoga (switch de 1Gb)
Resultados obtidos neste trabalho
Programa Probabilístico com n = 1M
6
Total
Comp
Comum
Segundos
4
2
0
0
2
4
6
8
No. Processadores
Curva dos tempos observados para o algoritmo probabilístico com entrada n = 1M.
Resultados obtidos neste trabalho
Programa Probabilístico com n = 32M
100
Total
Comp
80
Segundos
Comum
60
40
20
0
0
2
4
6
8
No. Processadores
Curva dos tempos observados para o algoritmo probabilístico com entrada n = 32M.
Resultados obtidos neste trabalho
Programa Probabilístico com n = 32M
4
Acelerações
3
2
1
0
2
4
6
8
No. Processadores
Acelerações (speedups) obtidas para o algoritmo probabilístico para n = 32M.
Resultados obtidos neste trabalho
Programa Determinístico com n = 32M
120
Total
100
Comp
Comum
Segundos
80
60
40
20
0
0
2
4
6
8
No. Processadores
Curva dos tempos observados para o algoritmo determinístico com entrada n = 32M.
Resultados obtidos neste trabalho
Programa Determinístico Modificado com n = 32M
120
Total
100
Comp
Comum
Segundos
80
60
40
20
0
0
2
4
6
8
No. Processadores
Curva dos tempos observados para o algoritmo probabilístico com entrada n = 32M.
Conclusão
•
Os dados experimentais obtidos mostram um desempenho
satisfatório dos programas.
•
Os programas são mais eficientes para maiores valores da entrada
(n).
•
O tempo de execução diminui com o aumento do número de
processadores, exceto para n = 1M, onde o tempo de comunicação
não é compensado pela quantidade de dados. Para p = 8 e n = 16M
todos os programas paralelos são mais rápidos que o programa
seqüencial.
•
Programa determinístico modificado é um pouco mais rápido que o
programa determinístico.
•
A implementação do algoritmo probabilístico (que possui na teoria
maior número de rodadas de comunicação) obteve melhor
desempenho que a do algoritmo determinístico.