Going Nowhere Fast
Alunos:

Huander Leão da Silva
 Ricardo Belloti dos Santos
Conjectura de Waring
A conjectura de Waring diz que todo o
inteiro pode ser escrito como soma de
potencias.
 Esta conjetura diz que qualquer inteiro
pode ser expressado como uma soma de
de pelo menos quatro quadrados inteiros.

Mistério das Pirâmides

Encontrar os número piramidais no
intervalo de 0 a 1 bilhão.

de 0 a 100.000 tempo O(n2)
Problema da Mochila
 Tempo de execução está relacionado ao
algoritmo

Números Piramidais

São números da forma:
(m3

– m) / 6
(para m >= 2)
Exemplo:
 1,
4, 10, 20, 35, 56, 84, 120, 165…
O problema

Resolver rapidamente, através de um programa, a
Conjectura de Waring para os números piramidais.

Esta conjectura (1928) diz que todo inteiro pode ser
representado como uma soma de no máximo 5 numeros
piramidais.

Objetivo:
“Usar um supercomputador para provar esta cojectura
para todos os números de 1 até 1.000.000.000”
Dificuldades



Fazer um bilhão de qualquer coisa custaria
muito tempo
Encontrar um algoritmo mais eficiente para o
problema
O algoritmo:

Crescimento assintónito, O(n2)


Rápido para números pequenos
Cada vez mais lento a medida que os números cresciam
Idéias

Melhorar o algoritmo (30.000 vezes mais rápido)
 Crescimento

assintónito: O(n lgn)
Paralelismo

dividir a carga de processamento entre vários
processadores: 16 nós




P1 = 1 até 62.500.000
P2 = 62.500.001 até 125.000.000
...
P16 = 937.500.000 até 1.000.000.000
A Máquina

Intel IPSC-860 hypercube

computação paralela de alta performance
 arquitetura de hipercubo com 32 nós
 memória distribuída: 16 Mb cada processador
 sistema multi-programado e multi-usuário

O usuário pode determinar o tamanho do
hipercubo de 0 até o tamanho máximo disponível.
Cada programa de usuário “roda” em todos os nós
do hipercubo de uma dimensão determinada.
Algoritmos Paralelos

Duas cabeças pensa melhor do que uma!
2
computadores processam mais do que 1
 n computadores processam mais do que n-1

Como ter performance com computadores
em paralelo?
 Algoritmos
Paralelos
 Atribuir atividades para cada processador
Algoritmos Paralelos

Nem sempre é melhor solução,
processamento paralelo tem problemas
 Ganhos
potenciais pode ser encontrado em
algoritmo seqüencial
 Erros
 “Tente o processamento paralelo apenas
após o processamento seqüencial se mostra
muito lento”.
Execução esperada do Algoritmo
Resultado = ???
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Execução Real do Algoritmo
= Resultado!!!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Problemas
Problemas com a máquina
 A metade da máquina e a maioria de seus
usuários ficam refém de um único
processo de um usuário.
 Custo para elaboração do algoritmo
paralelo

Resultado
Solução mais rápida
 Após o termino da execução os números
foram entregues ao requerente.

 Ganhador
no Prêmio Nobel
 Seu pai teria feito a conjectura em 1928.
Conclusões
Antes de resolver um problema
eficientemente deve-se verificar a real
necessidade dele ser resolvido, e
resolvido rapidamente.
 Se for colocar em paralelo deve-se ter
certeza de balancear a carga de cada
processador.

Referência




http://csep1.phy.ornl.gov/ipsc860_guide/node2.html#SE
CTION00020000000000000000
http://www2.toki.or.id/book/AlgDesignManual/BOOK/BO
OK3/NODE101.HTM
http://www.ppgia.pucpr.br/~laplima/aulas/materia/arvgen
_m.html
Organização Estrutura de Computadores, 4 Edição –
Andrew S. Tanenbaum. LTC Editora