Parallel and distributed computing · Computação paralela e distribuída
Doing work in order
- Most simple programs are sequential: they do one step, then the next, then the next.
- The computer finishes step 1 before it starts step 2.
- This is easy to understand, but it can be slow for big jobs.
Trabalhando em sequência
- A maioria dos programas simples é sequencial: executa um passo, depois o próximo, depois o próximo.
- O computador termina o passo 1 antes de começar o passo 2.
- Isso é fácil de entender, mas pode ser lento para grandes tarefas.
Sequential (one worker):
task A -> task B -> task C -> task D
|-------|--------|--------|--------|
total time = A + B + C + D
Parallel computing
- Parallel computing splits work so several parts run at the same time.
- A modern computer has several processors (also called cores) that can each do work.
- If four workers each take one task, four tasks can finish in about the time of one.
Computação paralela
- A computação paralela divide o trabalho para que várias partes sejam executadas ao mesmo tempo.
- Um computador moderno possui vários processadores (também chamados núcleos) que podem realizar trabalho individualmente.
- Se quatro trabalhadores cada um assumir uma tarefa, quatro tarefas podem ser concluídas em aproximadamente o tempo de uma.
Parallel (four workers at once):
worker 1: task A
worker 2: task B
worker 3: task C
worker 4: task D
|--------|
total time ≈ the longest single task
Speedup
- Speedup asks: how many times faster is the parallel version?
- speedup = (sequential time) / (parallel time).
- Example: a job takes 8 seconds in order, but 2 seconds split up. Speedup = 8 / 2 = 4 times.
Ganho de velocidade
- O ganho de velocidade pergunta: quantas vezes mais rápido é a versão paralela?
- ganho de velocidade = (tempo sequencial) / (tempo paralelo).
- Exemplo: uma tarefa leva 8 segundos em sequência, mas 2 segundos dividida. Ganho de velocidade = 8 / 2 = 4 vezes.
Not always N times faster
- More processors does not always mean N times faster.
- Some parts of a job cannot be split — they must happen in order.
- Also, splitting work and joining results back together takes some extra time.
Nem sempre N vezes mais rápido
- Mais processadores não significam necessariamente N vezes mais rápido.
- Algumas partes de uma tarefa não podem ser divididas — elas devem acontecer em sequência.
- Além disso, dividir o trabalho e unir os resultados novamente consome algum tempo extra.
Job = setup (must be in order) + main work (can split)
setup main work (split over 4)
|-----| |--------------------------------|
|--------| <- this part gets 4x
The setup part stays the same length.
Distributed computing
- Distributed computing uses many separate computers that cooperate over a network.
- They may sit in different rooms, cities, or countries.
- Examples: the web (many servers), big data jobs split over thousands of machines, and large science projects.
Computação distribuída
- A computação distribuída utiliza muitos computadores separados que cooperam através de uma rede.
- Eles podem estar em salas diferentes, cidades ou países distintos.
- Exemplos: a Web (muitos servidores), trabalhos de big data divididos entre milhares de máquinas e grandes projetos científicos.
Distributed (computers cooperate over a network):
[computer 1] [computer 2] [computer 3]
\ | /
\ | /
shared network / job
Each computer does part of the work.
Trade-offs
- Good: parallel and distributed systems can be much faster, and can handle huge jobs.
- Harder: the code is more complex; parts must be coordinated; results must be combined.
- Limits: speedup is capped by the parts that cannot be split, and by network delays between computers.
Compromissos
- Vantagem: sistemas paralelos e distribuídos podem ser muito mais rápidos e lidar com tarefas enormes.
- Dificuldade: o código é mais complexo; as partes devem ser coordenadas; os resultados devem ser combinados.
- Limites: o ganho de velocidade é limitado pelas partes que não podem ser divididas e pelos atrasos de rede entre computadores.
Key words
- Sequential: steps run one after another, in order.
- Parallel: parts run at the same time on several processors.
- Speedup: sequential time divided by parallel time.
- Distributed: many separate computers cooperate over a network.
Palavras-chave
- Sequencial: passos executados um após o outro, em ordem.
- Paralelo: partes executadas ao mesmo tempo em vários processadores.
- Ganho de velocidade: tempo sequencial dividido pelo tempo paralelo.
- Distribuído: muitos computadores separados cooperam através de uma rede.
Common mistakes
- Parallel speed-up only helps work that can be split into independent parts.
- Each extra processor adds less and less speed.
Erros comuns
- O ganho de velocidade paralelo só ajuda no trabalho que pode ser dividido em partes independentes.
- Cada processador adicional adiciona menos e menos velocidade.
Now you try
- Put the speedup formulas to work as small functions.
- Model a job that is part fixed setup and part splittable work. Press Check answer.
Agora você tenta
- Aplique as fórmulas de ganho de velocidade como pequenas funções.
- Modelar uma tarefa que tem parte de configuração fixa e parte de trabalho divisível. Pressione Verificar resposta.
A job has a setup part that must run in order, and a splittable part that workers can share at the same time. Write parallel_time(setup, splittable, workers) that returns the total time: the setup, plus the splittable part divided among the workers. Example: parallel_time(2, 8, 4) → 4.0 (2 + 8/4). · Um trabalho possui uma parte setup que deve ser executada em sequência, e uma parte splittable que workers pode ser compartilhada simultaneamente. Escreva parallel_time(setup, splittable, workers) que retorne o tempo total: a configuração mais a parte divisível dividida entre os trabalhadores. Exemplo: parallel_time(2, 8, 4) → 4.0 (2 + 8/4).
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Write speedup(sequential, parallel) that returns how many times faster the parallel version is: the sequential time divided by the parallel time. Example: speedup(8, 2) → 4.0. · Escreva speedup(sequential, parallel) que retorne quantas vezes mais rápido é a versão paralela: o tempo sequencial dividido pelo tempo paralelo. Exemplo: speedup(8, 2) → 4.0.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Even with unlimited workers, the setup part still cannot be split. Write max_speedup(setup, splittable) for the best possible speedup: the whole job time divided by the setup time (endless workers shrink the splittable part to almost nothing, leaving only the setup). Example: max_speedup(2, 6) → 4.0 ((2+6)/2). · Mesmo com trabalhadores ilimitados, a parte setup ainda não pode ser dividida. Escreva max_speedup(setup, splittable) para o ganho de velocidade melhor possível: o tempo total do trabalho dividido pelo tempo de configuração (trabalhadores infinitos reduzem a parte divisível a quase nada, restando apenas a configuração). Exemplo: max_speedup(2, 6) → 4.0 ((2+6)/2).
Click Run to see the output here. · Clique em Executar para ver a saída aqui.