Granularidade (computação paralela) - Granularity (parallel computing)

Na computação paralela , a granularidade (ou tamanho do grão ) de uma tarefa é uma medida da quantidade de trabalho (ou computação) que é executada por aquela tarefa.

Outra definição de granularidade leva em consideração a sobrecarga de comunicação entre vários processadores ou elementos de processamento. Ele define granularidade como a razão entre o tempo de computação e o tempo de comunicação, em que, o tempo de computação é o tempo necessário para realizar o cálculo de uma tarefa e o tempo de comunicação é o tempo necessário para trocar dados entre os processadores.

Se for o tempo de computação e denotar o tempo de comunicação, então a Granularidade G de uma tarefa pode ser calculada como: ${\ displaystyle T _ {\ mathrm {comp}}}$${\ displaystyle T _ {\ mathrm {comm}}}$

${\ displaystyle G = {\ frac {T _ {\ mathrm {comp}}} {T _ {\ mathrm {comm}}}}}$

A granularidade é geralmente medida em termos do número de instruções executadas em uma tarefa específica. Como alternativa, a granularidade também pode ser especificada em termos do tempo de execução de um programa, combinando o tempo de computação e o tempo de comunicação.

Tipos de paralelismo

Dependendo da quantidade de trabalho executada por uma tarefa paralela, o paralelismo pode ser classificado em três categorias: paralelismo de baixa granulação, de granulação média e de granulação grossa.

Paralelismo refinado

No paralelismo refinado, um programa é dividido em um grande número de pequenas tarefas. Essas tarefas são atribuídas individualmente a vários processadores. A quantidade de trabalho associada a uma tarefa paralela é baixa e o trabalho é distribuído uniformemente entre os processadores. Conseqüentemente, o paralelismo refinado facilita o balanceamento de carga .

Como cada tarefa processa menos dados, o número de processadores necessários para realizar o processamento completo é alto. Isso, por sua vez, aumenta a sobrecarga de comunicação e sincronização.

O paralelismo refinado é mais bem explorado em arquiteturas que suportam comunicação rápida. A arquitetura de memória compartilhada com baixo overhead de comunicação é mais adequada para paralelismo de baixa granularidade.

É difícil para os programadores detectar o paralelismo em um programa, portanto, geralmente é responsabilidade dos compiladores detectar o paralelismo refinado.

Um exemplo de sistema de baixa granularidade (de fora do domínio da computação paralela) é o sistema de neurônios em nosso cérebro .

Connection Machine (CM-2) e J-Machine são exemplos de computadores paralelos de grão fino que têm tamanho de grão na faixa de 4-5 μs.

Paralelismo de granulação grossa

No paralelismo de baixa granularidade, um programa é dividido em grandes tarefas. Devido a isso, uma grande quantidade de computação ocorre nos processadores. Isso pode resultar em desequilíbrio de carga, em que certas tarefas processam a maior parte dos dados enquanto outras podem ficar ociosas. Além disso, o paralelismo de baixa granulação falha em explorar o paralelismo no programa, pois a maior parte da computação é realizada sequencialmente em um processador. A vantagem desse tipo de paralelismo é a baixa sobrecarga de comunicação e sincronização.

A arquitetura de passagem de mensagens leva muito tempo para comunicar dados entre processos, o que a torna adequada para paralelismo de granulação grossa.

Cray Y-MP é um exemplo de computador paralelo de granulação grossa que possui um tamanho de granulação de cerca de 20s.

Paralelismo de granulação média

O paralelismo de granulação média é usado em relação ao paralelismo de granulação fina e granulação grossa. O paralelismo de granulação média é um meio-termo entre o paralelismo de granulação fina e o paralelismo de granulação grossa, em que temos o tamanho da tarefa e o tempo de comunicação maior que o paralelismo de granulação fina e menor que o paralelismo de granulação grossa. A maioria dos computadores paralelos de uso geral se enquadra nesta categoria.

Intel iPSC é um exemplo de computador paralelo de granulação média com tamanho de granulação de cerca de 10 ms.

Exemplo

Considere uma imagem 10 * 10 que precisa ser processada, visto que o processamento dos 100 pixels é independente um do outro.

Paralelismo refinado: suponha que haja 100 processadores responsáveis ​​pelo processamento da imagem 10 * 10. Ignorando o overhead de comunicação, os 100 processadores podem processar a imagem 10 * 10 em 1 ciclo de clock. Cada processador está trabalhando em 1 pixel da imagem e então comunica a saída para outros processadores. Este é um exemplo de paralelismo refinado.

Paralelismo de granulação média: considere que há 25 processadores processando a imagem 10 * 10. O processamento da imagem agora levará 4 ciclos de clock. Este é um exemplo de paralelismo de granulação média.

Paralelismo de granulação grossa: Além disso, se reduzirmos os processadores para 2, o processamento levará 50 ciclos de clock. Cada processador precisa processar 50 elementos, o que aumenta o tempo de computação, mas a sobrecarga de comunicação diminui à medida que o número de processadores que compartilham dados diminui. Este caso ilustra o paralelismo de granulação grossa.

void main()
{
  switch (Processor_ID)
  {
    case 1: Compute element 1; break;
    case 2: Compute element 2; break;
    case 3: Compute element 3; break;
    .
    .
    .
    .
    case 100: Compute element 100; 
              break;
  }
}

void main()
{
  switch (Processor_ID)
  {
    case 1: Compute elements 1-4; break;
    case 2: Compute elements 5-8; break;
    case 3: Compute elements 9-12; break;
    .
    .
    case 25: Compute elements 97-100; 
             break;
  }
}

void main()
{
  switch (Processor_ID)
  {
    case 1: Compute elements 1-50; 
            break;
    case 2: Compute elements 51-100; 
            break;
  }
}

Níveis de paralelismo

A granularidade está intimamente ligada ao nível de processamento. Um programa pode ser dividido em 4 níveis de paralelismo -

1. Nível de instrução.
2. Nível de loop
3. Nível de sub-rotina e
4. Nível de programa

A maior quantidade de paralelismo é alcançada no nível de instrução , seguido pelo paralelismo em nível de loop . No nível de instrução e loop, o paralelismo refinado é alcançado. O tamanho de grão típico no nível de instrução é de 20 instruções, enquanto o tamanho de grão no nível de loop é de 500 instruções.

No nível da sub-rotina (ou procedimento), o tamanho do grão é normalmente de alguns milhares de instruções. O paralelismo de granulação média é alcançado no nível de sub-rotina.

No nível do programa , a execução paralela de programas ocorre. A granularidade pode estar na faixa de dezenas de milhares de instruções. O paralelismo de granulação grossa é usado neste nível.

A tabela abaixo mostra a relação entre os níveis de paralelismo, tamanho do grão e grau de paralelismo

Impacto da granularidade no desempenho

A granularidade afeta o desempenho de computadores paralelos. Usar grãos finos ou pequenas tarefas resulta em mais paralelismo e, portanto, aumenta a velocidade . No entanto, sobrecarga de sincronização, estratégias de agendamento , etc., podem impactar negativamente o desempenho de tarefas de baixa granularidade. Aumentar o paralelismo sozinho não pode fornecer o melhor desempenho.

Para reduzir a sobrecarga de comunicação, a granularidade pode ser aumentada. Tarefas de granulação grossa têm menos sobrecarga de comunicação, mas costumam causar desequilíbrio de carga. Conseqüentemente, o desempenho ideal é alcançado entre os dois extremos de paralelismo de granulação fina e de granulação grossa.

Vários estudos propuseram sua solução para ajudar a determinar a melhor granularidade para auxiliar o processamento paralelo. Encontrar o melhor tamanho de grão depende de vários fatores e varia muito de problema para problema.

Veja também

• Paralelismo de nível de instrução
• Paralelismo de dados

Citações