Programação Multiprocessador

Teste de Primalidade em Programação Multiprocessador

1. Problema: Teste de Primalidade Paralelo

• Desafio: Imprimir números primos de 1 até (10^{10}).
• Configuração:
  • Sistema multiprocessador com 10 processadores.
  • Cada processador executa uma thread.
• Objetivo:
  • Obter um ganho de velocidade aproximadamente 10 vezes maior usando os 10 processadores.

---

2. Solução com Contador Partilhado

• Estratégia:

  • Usar um objeto contador partilhado para distribuir números entre as threads.
  • Cada thread incrementa o contador e verifica a primalidade do número recebido.

• Código de Exemplo:

  Counter counter = new Counter(1);
  
  void primePrint() {
      long j = 0;
      while (j < 1010) {
          j = counter.getAndIncrement();
          if (isPrime(j))
              print(j);
      }
  }
  

• Funcionamento:

  • O contador distribui números de forma incremental.
  • Threads interrompem a execução quando todos os valores são atribuídos.

• Implementação do Contador:

  public class Counter {
      private long value;
  
      public long getAndIncrement() {
          return value++;
      }
  }
  

---

3. Desafios de Concorrência

• Problema de Consistência:

  • Em ambientes concorrentes, múltiplas threads podem ler e atualizar o mesmo valor simultaneamente, resultando em inconsistências.
  • Exemplo: Threads lendo o mesmo valor antes de o contador ser atualizado.

• Necessidade de Operações Atômicas:

  • Para evitar inconsistências, as operações de incremento e retorno precisam ser atômicas (indivisíveis).
  • Problema na Implementação:

    public long getAndIncrement() {
        temp = value;
        value = temp + 1;
        return temp;
    }
    

    • Este código não é seguro em cenários concorrentes.

---

4. Alternativa: Divisão de Trabalho por Intervalos

• Nova Estratégia:
  • Atribuir intervalos fixos de números a cada thread, reduzindo a necessidade de sincronização no contador.
• Exemplo de Código:

  void primePrint() {
      int i = ThreadID.get(); // IDs {0..9}
      for (j = i*10^9 + 1; j < (i+1)*10^9; j++) {
          if (isPrime(j))
              print(j);
      }
  }
  

• Vantagens:
  • Reduz contenção no contador.
  • Melhora a escalabilidade em sistemas multiprocessador.

---

5. Benefícios e Limitações

• Benefícios do Paralelismo:

  • Aumento significativo no desempenho em relação à execução sequencial.
  • Melhor aproveitamento dos recursos do hardware.

• Limitações:

  • Necessidade de estratégias adicionais para garantir consistência em contadores partilhados.
  • Divisão de intervalos pode causar desequilíbrio de carga entre threads dependendo da densidade de números primos.