Computer Science › Sistemas
Arquitetura de Computadores explicou por que os fabricantes de chips pararam de deixar núcleos individuais mais rápidos e passaram a entregar mais deles; esta disciplina retoma exatamente dali, fazendo uma pergunta diferente: dados muitos núcleos (ou muitas máquinas), como um programador de fato faz um programa usá-los?
A memória compartilhada (UMA ou NUMA) dá a todo processador um único espaço de endereçamento que todos podem ler e escrever diretamente; a memória distribuída dá a cada processador a sua própria memória privada e força a comunicação por meio de mensagens explícitas, a única distinção de hardware que determina qual modelo de programação um programa paralelo pode sequer usar.
Dois eixos diferentes ao longo dos quais um programa pode ser dividido: o paralelismo de tarefas roda operações diferentes concorrentemente (cada thread faz algo diferente), enquanto o paralelismo de dados roda a mesma operação concorrentemente sobre pedaços diferentes de dados, os eixos que o CS2013 nomeia explicitamente como as duas estratégias centrais de decomposição.
A decomposição de domínio divide os dados em pedaços e dá a cada processador o mesmo código para rodar no seu próprio pedaço (uma realização direta do paralelismo de dados); a decomposição funcional divide o problema em estágios ou papéis distintos, cada um rodando código diferente. É a mesma pergunta de particionamento que o dividir-para-conquistar já fazia, agora aplicada entre processadores em vez de chamadas recursivas.
Dividir o trabalho é a parte fácil; um programa paralelo real também precisa mover dados entre os pedaços (comunicação), manter na ordem certa as operações que dependem dos resultados umas das outras (sincronização) e identificar exatamente quais operações têm essas dependências, para começo de conversa. São três custos separados e inevitáveis que toda decomposição tem que pagar.
Granularidade é a razão entre computação e comunicação em cada pedaço paralelo: fina demais e o overhead de comunicação domina, grossa demais e os processadores ficam ociosos esperando alguns poucos pedaços lentos. O balanceamento de carga é o problema companheiro de garantir que todo processador de fato receba uma fatia justa e de tamanho parecido do trabalho.
Speedup = T(1) / T(p), a razão entre o tempo de execução sequencial e o paralelo em p processadores; eficiência = Speedup / p, a fração do tempo de cada processador de fato gasta em trabalho útil. São os dois números contra os quais toda afirmação de desempenho paralelo, no fim das contas, tem que ser medida.
Se uma fração f de um programa é inerentemente sequencial, nenhum número de processadores pode empurrar o speedup além de 1/f, um teto rígido que transforma o “basta adicionar mais núcleos” numa pergunta que sempre tem que começar com “quanto disto consegue sequer rodar em paralelo?”.
A Lei de Amdahl assume que o tamanho do problema é fixo enquanto os processadores crescem; o reenquadramento de Gustafson assume o oposto: na prática, mais processadores são usados para resolver um problema maior no mesmo tempo, e não o mesmo problema mais rápido. Sob essa suposição, o speedup escala quase linearmente em vez de bater num teto rígido.
A escalabilidade forte mantém o tamanho do problema fixo e adiciona processadores, exatamente o regime que a Lei de Amdahl limita; a escalabilidade fraca aumenta o tamanho do problema em proporção aos processadores, exatamente o regime que a Lei de Gustafson descreve. Relatórios reais de desempenho em HPC dizem qual das duas querem dizer, porque as duas perguntas têm respostas honestas muito diferentes.
Uma única thread mestre roda sequencialmente até encontrar uma região `#pragma omp parallel`; nesse ponto ela faz fork de um time de threads trabalhadoras que executam aquela região juntas, e depois faz join de volta numa única thread ao fim da região. Este é o modelo fork-join a partir do qual todo programa OpenMP é construído.
`#pragma omp for` divide as iterações de um loop entre as threads já criadas pelo fork de uma região paralela envolvente, e uma cláusula `reduction` dá a cada thread o seu próprio acumulador privado, que o OpenMP combina com segurança no final. É a forma padrão, só com diretivas, de paralelizar por dados um loop comum sem mexer na lógica do seu corpo.
Quando uma cláusula de redução não é expressiva o suficiente, `critical` e `atomic` dão às threads acesso mutuamente exclusivo a uma atualização compartilhada: `atomic` compila para uma única instrução de hardware rápida quando possível, e `critical` cobre blocos arbitrários de código a um custo maior. São as duas ferramentas no nível de diretiva que mantêm um programa de memória compartilhada correto sem escrever um lock à mão.
O MPI não tem um espaço de endereçamento compartilhado no qual fazer fork de threads. Em vez disso, um número fixo de processos independentes é lançado junto (SPMD: o mesmo programa, rodando em todo processo), cada um identificado por um rank inteiro único dentro de um comunicador, e cada pedacinho de coordenação entre eles tem que acontecer por meio de mensagens explícitas.
`MPI_Send`/`MPI_Recv` bloqueiam o processo chamador até que a transferência da mensagem possa ser considerada completa com segurança: simples, mas um par correspondente na ordem errada pode causar deadlock no programa inteiro. `MPI_Isend`/`MPI_Irecv` retornam imediatamente e deixam o processo fazer outro trabalho enquanto a mensagem ainda está em trânsito, ao custo de precisar de um `MPI_Wait` explícito antes de tocar o buffer de novo.
A maioria dos programas MPI reais mal usa pares brutos de send/recv diretamente: `MPI_Bcast` envia os dados de um processo a todos os processos, `MPI_Reduce` combina os dados de todos os processos de volta num só com um operador como soma ou máximo, e `MPI_Scatter`/`MPI_Gather` dividem e remontam um array por todos os ranks, cada um deles um padrão de comunicação geral o bastante para ser implementado de forma muito mais eficiente do que um laço escrito à mão de chamadas ponto a ponto.
Uma máquina com vários núcleos e um gargalo de memória real geralmente pede OpenMP; um cluster de muitas máquinas sem memória compartilhada pede MPI; um problema com milhares de operações independentes, simples e idênticas pede o modelo SIMT da GPU já coberto em Arquitetura de Computadores, um guia de decisão que amarra arquitetura de memória, decomposição, Amdahl/Gustafson e os dois modelos de programação cobertos aqui numa única escolha real, feita honestamente (muitos códigos de HPC reais usam mais de um deles juntos).
Part of the Computer Science curriculum.
Arquitetura de Computadores explicou por que os fabricantes de chips pararam de deixar núcleos individuais mais rápidos e passaram a entregar mais deles; esta disciplina retoma exatamente dali, fazendo uma pergunta diferente: dados muitos núcleos (ou muitas máquinas), como um programador de fato faz um programa usá-los?
A memória compartilhada (UMA ou NUMA) dá a todo processador um único espaço de endereçamento que todos podem ler e escrever diretamente; a memória distribuída dá a cada processador a sua própria memória privada e força a comunicação por meio de mensagens explícitas, a única distinção de hardware que determina qual modelo de programação um programa paralelo pode sequer usar.
Dois eixos diferentes ao longo dos quais um programa pode ser dividido: o paralelismo de tarefas roda operações diferentes concorrentemente (cada thread faz algo diferente), enquanto o paralelismo de dados roda a mesma operação concorrentemente sobre pedaços diferentes de dados, os eixos que o CS2013 nomeia explicitamente como as duas estratégias centrais de decomposição.
A decomposição de domínio divide os dados em pedaços e dá a cada processador o mesmo código para rodar no seu próprio pedaço (uma realização direta do paralelismo de dados); a decomposição funcional divide o problema em estágios ou papéis distintos, cada um rodando código diferente. É a mesma pergunta de particionamento que o dividir-para-conquistar já fazia, agora aplicada entre processadores em vez de chamadas recursivas.
Dividir o trabalho é a parte fácil; um programa paralelo real também precisa mover dados entre os pedaços (comunicação), manter na ordem certa as operações que dependem dos resultados umas das outras (sincronização) e identificar exatamente quais operações têm essas dependências, para começo de conversa. São três custos separados e inevitáveis que toda decomposição tem que pagar.
Granularidade é a razão entre computação e comunicação em cada pedaço paralelo: fina demais e o overhead de comunicação domina, grossa demais e os processadores ficam ociosos esperando alguns poucos pedaços lentos. O balanceamento de carga é o problema companheiro de garantir que todo processador de fato receba uma fatia justa e de tamanho parecido do trabalho.
Speedup = T(1) / T(p), a razão entre o tempo de execução sequencial e o paralelo em p processadores; eficiência = Speedup / p, a fração do tempo de cada processador de fato gasta em trabalho útil. São os dois números contra os quais toda afirmação de desempenho paralelo, no fim das contas, tem que ser medida.
Se uma fração f de um programa é inerentemente sequencial, nenhum número de processadores pode empurrar o speedup além de 1/f, um teto rígido que transforma o “basta adicionar mais núcleos” numa pergunta que sempre tem que começar com “quanto disto consegue sequer rodar em paralelo?”.
A Lei de Amdahl assume que o tamanho do problema é fixo enquanto os processadores crescem; o reenquadramento de Gustafson assume o oposto: na prática, mais processadores são usados para resolver um problema maior no mesmo tempo, e não o mesmo problema mais rápido. Sob essa suposição, o speedup escala quase linearmente em vez de bater num teto rígido.
A escalabilidade forte mantém o tamanho do problema fixo e adiciona processadores, exatamente o regime que a Lei de Amdahl limita; a escalabilidade fraca aumenta o tamanho do problema em proporção aos processadores, exatamente o regime que a Lei de Gustafson descreve. Relatórios reais de desempenho em HPC dizem qual das duas querem dizer, porque as duas perguntas têm respostas honestas muito diferentes.
Uma única thread mestre roda sequencialmente até encontrar uma região `#pragma omp parallel`; nesse ponto ela faz fork de um time de threads trabalhadoras que executam aquela região juntas, e depois faz join de volta numa única thread ao fim da região. Este é o modelo fork-join a partir do qual todo programa OpenMP é construído.
`#pragma omp for` divide as iterações de um loop entre as threads já criadas pelo fork de uma região paralela envolvente, e uma cláusula `reduction` dá a cada thread o seu próprio acumulador privado, que o OpenMP combina com segurança no final. É a forma padrão, só com diretivas, de paralelizar por dados um loop comum sem mexer na lógica do seu corpo.
Quando uma cláusula de redução não é expressiva o suficiente, `critical` e `atomic` dão às threads acesso mutuamente exclusivo a uma atualização compartilhada: `atomic` compila para uma única instrução de hardware rápida quando possível, e `critical` cobre blocos arbitrários de código a um custo maior. São as duas ferramentas no nível de diretiva que mantêm um programa de memória compartilhada correto sem escrever um lock à mão.
O MPI não tem um espaço de endereçamento compartilhado no qual fazer fork de threads. Em vez disso, um número fixo de processos independentes é lançado junto (SPMD: o mesmo programa, rodando em todo processo), cada um identificado por um rank inteiro único dentro de um comunicador, e cada pedacinho de coordenação entre eles tem que acontecer por meio de mensagens explícitas.
`MPI_Send`/`MPI_Recv` bloqueiam o processo chamador até que a transferência da mensagem possa ser considerada completa com segurança: simples, mas um par correspondente na ordem errada pode causar deadlock no programa inteiro. `MPI_Isend`/`MPI_Irecv` retornam imediatamente e deixam o processo fazer outro trabalho enquanto a mensagem ainda está em trânsito, ao custo de precisar de um `MPI_Wait` explícito antes de tocar o buffer de novo.
A maioria dos programas MPI reais mal usa pares brutos de send/recv diretamente: `MPI_Bcast` envia os dados de um processo a todos os processos, `MPI_Reduce` combina os dados de todos os processos de volta num só com um operador como soma ou máximo, e `MPI_Scatter`/`MPI_Gather` dividem e remontam um array por todos os ranks, cada um deles um padrão de comunicação geral o bastante para ser implementado de forma muito mais eficiente do que um laço escrito à mão de chamadas ponto a ponto.
Uma máquina com vários núcleos e um gargalo de memória real geralmente pede OpenMP; um cluster de muitas máquinas sem memória compartilhada pede MPI; um problema com milhares de operações independentes, simples e idênticas pede o modelo SIMT da GPU já coberto em Arquitetura de Computadores, um guia de decisão que amarra arquitetura de memória, decomposição, Amdahl/Gustafson e os dois modelos de programação cobertos aqui numa única escolha real, feita honestamente (muitos códigos de HPC reais usam mais de um deles juntos).