01 - Introdução a SuperComputação

Como vimos na expositiva, uma solução de alto desempenho depende de três partes:

1. algoritmos eficientes
2. implementações eficientes
3. paralelismo

Na atividade de hoje vamos estudar o primeiro ponto e quantificar o efeito de algoritmos eficientes na resolução de um problema complexo.

Problemas estudados em SuperComputação

Em Desafios de Programação conhecemos a classe dos problemas NP-completo, que são aqueles que acreditamos não existir nenhum algoritmo determinístico que os resolvem em tempo polinomial. Ou seja, são problemas importantes cuja solução é difícil. Em geral temos classes de algoritmos para resolvê-los:

1. ótimos globais: algoritmo que encontra a solução "correta" do problema.
2. ótimos locais: algoritmo que encontra uma solução "boa" e que não pode ser melhorada por pequenas modificações.
3. aproximação: algoritmos que garantem estar "perto o suficiente" da solução ótima. Este tipo de algoritmo não nos interessa em SuperComputação.

Iremos analisar hoje 4 executáveis que resolvem o problema do Caixeiro Viajante.

1. busca-local-1 - implementação de um método de busca rápida, porém não ótima.
2. busca-local-1-par - implementação paralela do programa acima.
3. busca-local-2 - implementação alternativa do mesmo método acima. Os resultados de ambos são idênticos.
4. busca-local-2-par - implementação paralela do programa acima.

Important

Não estamos interessados no Caixeiro Viajante em si hoje. Queremos é comparar diferentes maneiras de resolvê-lo para entendermos o papel de técnicas de SuperComputação na velocidade de processamento e nos resultados obtidos.

Ferramental

Realizar testes de maneira automatizada é muito importante para quantificar os efeitos de diferentes algoritmos e técnicas de paralelismo. O snippet abaixo executa

import subprocess
import time

with open('entradas-busca-local/in-0.txt') as f:
    start = time.perf_counter()
    proc = subprocess.run(['./busca-local-1'], input=f.read(), text=True, capture_output=True)
    end = time.perf_counter()

    print('Saída:', proc.stdout)
    print('Stderr:', proc.stderr)
    print('Tempo total(s):', end - start)

Vamos agora praticar usar este snippet para executar nossos testes automaticamente.

Example

Crie uma função roda_com_entrada(executavel, arquivo_in) que roda o primeiro argumento usando como entrada o conteúdo do segundo argumento. Teste seu código com o executável busca-local-1 e com o arquivo de entrada in-0.txt usado no exemplo acima.

Sua função deverá devolver uma tupla (stdout,time) com stdout sendo a saída do programa e time seu tempo de execução em segundos.

# TODO: exercício aqui

Algoritmos sequenciais

Com esse código, vamos criar um relatório interativo que roda nossos testes automaticamente e já plota informações prontas para nossas análises. Vamos começar examinando o desempenho do executável busca-local-1.

Example

Rode o busca-local com os arquivos de entrada na pasta entradas-busca-local. Guarde os tempos em uma lista.

Example

Leia o tamanho das entradas dos arquivos na pasta entradas-busca-local e guarde em uma segunda lista.

Example

Plote o tempo de execução pelo tamanho da entrada usando matplotlib

# TODO: exercício aqui

Example

Repita os três passos acima para o executável busca-local-2. Finalize plotando os tempos de execução de ambos os executáveis no mesmo gráfico.

#TODO: seu código aqui

Example

Segundo uma coleta de dados informal e altamente confiável, 93,17% dos alunos não colocam legendas nem títulos nos gráficos gerados. Faça isso agora.

Question

Interprete o gráfico que você gerou na linha de cima.

Question

Compare manualmente a saída dos programas. Existe diferença em seus resultados?

Question

Resgate seus conhecimentos de Desafios de Programação e explique a diferença entre os algoritmos.

Algoritmos paralelos

Na discussão inicial da expositiva chegamos à conclusão de que se conseguimos realizar N operações em paralelo teremos um ganho de no máximo N vezes no desempenho de nosso programa. Nesta parte iremos estudar esta afirmação usando implementações paralelas dos algoritmos da seção anterior.

Example

Execute os algoritmos paralelos com as mesmas entradas e compare com suas versões paralelas. Use um gráfico para facilitar as comparações

Question

Compare os tempos obtidos. Qual foi o ganho médio? Quantos núcleos a máquina que você está usando possui? Responda comparando cada algoritmo sequencial com sua versão paralela.

Já estabelecemos que busca-local-2 é melhor que busca-local-1 por ser utilizar um algoritmo mais eficiente e vimos na prática a diferença entre um algoritmo $O(n^3)$ e um algoritmo $O(n^2)$. Vamos agora examinar a seguinte questão.

É possível usar paralelismo para tornar busca-local-1-par melhor que busca-local-2?

Example

Compare o desempenho de busca-local-1-par com busca-local-2. Faça um gráfico

Question

Com base em seu gráfico acima, responda a pergunta: "É possível usar paralelismo para tornar busca-local-1-par melhor que busca-local-2?"

Vamos agora generalizar a pergunta:

Question

Dados dois algoritmos com complexidades computacionais diferentes, sendo que o primeiro é inferior ao segundo. É possível usar paralelismo para tornar o primeiro mais rápido que o segundo para todos tamanhos de entrada? Assuma que você possui um número fixo de núcleos.