Thread: Single vs Multi

Boa noite, estou implementando um programa que faz a busca por números primos em uma matriz de 200 milhões de posições da seguinte forma:

1. Single-Thread:
usando uma busca sequencial onde uso 2 for () para percorrer a matriz de forma sequencial/serial e calcula o tempo que foi levado para fazer essa contagem

2. Multi-Threading:
o programa solicita ao usuário um número de threads que ele deseja subdividir a matriz (por padrão estou apenas subdividindo em potências de dois - 2, 4, 8, 16, 32…), em seguida cada thread é criada para cada sub-bloco da matriz, a thread faz acesso à variável somaNumeroDePrimos estática comum a classe, que por questões de evitar inconsistência no valor é feito uma sessão crítica usando LOCK assim apenas uma thread por vez poderá fazer o incremento da variável. No final da função de criação das threads é calculado também o tempo de execução total após as threads terminarem

Problema:
O problema é que era de se esperar que a versão Multi-Threading fosse mais rápido do que a versão Single, porém o que é observado é que a versão Multi está demorando tanto quanto a versão Single, ou para alguns casos de quantidades de Threads até pior que a forma Single.
Por isso minha intenção aqui no fórum é entender o que está acontecendo com minha implementação e de que forma eu posso resolver isso, ou até mesmo entender se estou calculando certo o tempo de execução das threads (mas acredito que sim pois eu até aguardo todas as threads terminarem, para calcular o tempo)

Segue o código:

ThreadExecute.java:

package teste;

import java.util.ArrayList;
import java.util.Random;
import java.util.Scanner;

public class ThreadExecute {

    public static int TAM = 20000;
    public static int numeroDeThreads;
    public static ArrayList<ArrayList<Integer>> matrizDeNumeros;
    public static ArrayList<Thread> listaDeThreads;

    private static final int rangeNumerosAleatorios = 11; //numeros aleatórios 0 - 10
    private static final Scanner in = new Scanner(System.in);
    private static long start, now;

    public static void preencherMatriz() {
        Random numero = new Random(2); // inicia semente para sempre gerar a mesma matriz
        ArrayList<Integer> linha;
        
            matrizDeNumeros = new ArrayList<ArrayList<Integer>>(TAM);
            for (int i = 0; i < TAM; i++) {
                linha = new ArrayList<Integer>(); 

                for (int j = 0; j < TAM; j++)
                    linha.add(numero.nextInt(rangeNumerosAleatorios));

                matrizDeNumeros.add(linha); //adiciona uma linha a cada posição, formando uma matriz
            }
    }

    public static void criarThreads() {
        float iInicial, jInicial, iFinal, jFinal, indice;
        float numerosPorThreads;
        start = 0;

            listaDeThreads = new ArrayList<Thread>();
            numerosPorThreads = (TAM * TAM) / numeroDeThreads;

            ThreadRunnable.setQuantidadeDePrimos(0);//reinicia quantidade de numeros primos

            for (int n = 0; n < numeroDeThreads; n++) {

                iInicial = (n * numerosPorThreads) / TAM;
                jInicial = (n * numerosPorThreads) % TAM;

                indice = ((n + 1) * numerosPorThreads) / TAM;
                iFinal = ((indice * 10) % 10) == 0 ? (int) indice - 1 : (int) indice;

                indice = ((n + 1) * numerosPorThreads) % TAM;
                jFinal = indice == 0 ? TAM - 1 : (int) indice - 1;

                
                ThreadRunnable runnable = new ThreadRunnable((int)iInicial, (int)jInicial, (int)iFinal, (int)jFinal);             
                Thread thread = new Thread(runnable); // mesmo que Thread t = new Thread(new ThreadRunnable ()); fora dessa classe
                thread.start();
                
                listaDeThreads.add(thread); //guarda threads em um arrayList
                
                if(start == 0)//a partir da criação da primeira Thread começa a contar o tempo
                    start = System.currentTimeMillis(); 
            }
        //aguarda TODAS as threads morrerem (serem finalizadas) para só então contar o tempo final    
        for(int i = 0; i < numeroDeThreads; i++){
            while(listaDeThreads.get(i).isAlive()){}
        }
        now = System.currentTimeMillis();
    }

    public static void modoSerial() {
        ThreadRunnable.setQuantidadeDePrimos(0); ////reinicia quantidade de numeros primos
        
        start = System.currentTimeMillis();
            ThreadRunnable serial = new ThreadRunnable(TAM, TAM);
        now = System.currentTimeMillis();
    }

    public static void main(String[] args) throws InterruptedException {

       System.out.println(Thread.currentThread().getName());
       
       System.out.println("Preenchendo matriz 20000X20000...");
       preencherMatriz();
       System.out.println("Matriz Preenchida");
       
       System.out.println("Modo Serial:");
       modoSerial();
       System.out.println("Tempo levado para o modo serial percorrer "+(now - start)+"ms");
       System.out.println("Foram encontrados "+ThreadRunnable.getQuantidadeDePrimos()+" numeros primos");
       
       //executa para diferentes numeros de threads:
       while(true){
            System.out.println("Informe o numero de threads: ");
            numeroDeThreads = in.nextInt();
            criarThreads();
            System.out.println("Tempo levado para as Threads percorrerem "+(now - start)+"ms");
            System.out.println("Foram encontrados "+ThreadRunnable.getQuantidadeDePrimos()+" numeros primos");
       }
    }
}

.
.
.
.
.
.
ThreadRunnable.java:

package teste;

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class ThreadRunnable implements Runnable {

    public static long somaNumeroDePrimos = 0;
    private int iInicial, jInicial, iFinal, jFinal;

    private static Lock lock = new ReentrantLock();

    //contrutor para o modo do Threads
    public ThreadRunnable(int iInicial, int jInicial, int iFinal, int jFinal) {
        this.iInicial = iInicial;
        this.jInicial = jInicial;
        this.iFinal = iFinal;
        this.jFinal = jFinal;
    }
    
    //construtor para o modo serial
    public ThreadRunnable(int iFinal, int jFinal) { 
        this.iInicial = 0;
        this.jInicial = 0;
        this.iFinal = iFinal;
        this.jFinal = jFinal;

        modoSerial();
    }

    @Override
    //execução no modo Thread
    public void run() {
        
        int i = iInicial, j = jInicial;
        while (i != iFinal || j != jFinal + 1) {

            if (j == ThreadExecute.TAM) {
                j = 0;
                i++;
            }
                if (isPrimo(ThreadExecute.matrizDeNumeros.get(i).get(j))){
                    lock.lock();
                        somaNumeroDePrimos++;
                    lock.unlock();
                }       
            j++;
        }
    }
    
    //execução no modo serial
    public void modoSerial() {
        for (int i = iInicial; i < iFinal; i++)
            for (int j = jInicial; j < jFinal; j++)
                if (isPrimo(ThreadExecute.matrizDeNumeros.get(i).get(j)))
                    somaNumeroDePrimos++;
    }
    
    public boolean isPrimo(int numero) {

        if (numero <= 1)
            return false;

        for (int divisor = 2; Math.pow(divisor, 2) <= numero; divisor++)
            if (numero % divisor == 0)
                return false; // se achar algum divisor menor ou igual do que a raiz quadrada do proprio
                              // número, entao nao é primo
        return true;
    }

    public static long getQuantidadeDePrimos() {
        return somaNumeroDePrimos;
    }

    public static void setQuantidadeDePrimos(long somaNumeroDePrimos) {
        ThreadRunnable.somaNumeroDePrimos = somaNumeroDePrimos;
    }
}

.
.
.
.
.
Obs: Como a matriz é muito grande é preciso evitar o erro Exception in thread “main” java.lang.OutOfMemoryError: Java heap space

No NetBeans:
botão direito no nome do projeto > properties >

                                                          **OU**

Por Linha de comando:
//na pasta dist/
java -jar -Xms0m -Xmx3072m Teste.jar

Oi @Gabriel_Brandao

Eu rodei seu código e dei uma analisada por cima. Algumas considerações:

  • Para esse tipo de código (onde o programa está só calculando coisas) não adiantar criar mais threads que o número de CPUs disponíveis na sua máquina. Por isso aumentar muito não ajuda.

  • O processor de criar threads tem um overhead, um custo adicional, então em vários casos você só verá diferença para valores grandes de matrizes.

  • Para um programa com múltiplas threads rodar com eficiência, você deve evitar gargalos. Ou seja, um recurso compartilhado por várias threads, onde elas precisam ficar esperando as outras pra continuar trabalhando. No seu caso é a variável somaNumeroDePrimos que está protegida pelo lock. Se você remover o lock verá que a versão multithread fica bem mais rápida (e com valores errados!!!).
    O que você quer fazer é diminuir ao máximo o tempo que você precisa interagir com essas variáveis compartilhadas entre todas as threads.
    No caso do seu programa uma maneira seria modificar o método run assim:

  public void run() {

    int i = iInicial, j = jInicial;
    int somaNumeroDePrimosLocal = 0;
    while (i != iFinal || j != jFinal + 1) {

      if (j == ThreadExecute.TAM) {
        j = 0;
        i++;
      }
      if (isPrimo(ThreadExecute.matrizDeNumeros.get(i).get(j))){
        //lock.lock();
        somaNumeroDePrimosLocal++;
        //lock.unlock();
      }
      j++;
    }

    lock.lock();
    somaNumeroDePrimos+= somaNumeroDePrimosLocal;
    lock.unlock();

  }

Ao invés de somar +1 na variável global a cada primo encontrado, eu calculo todos os primos naquela thread específica numa variável local e só no final eu atualizo uma vez a variável global com a soma parcial.

1 curtida

Não necessariamente. Adicionar mais threads nem sempre deixa as coisas mais rápidas.

Aqui tem uma explicação bem didática e detalhada sobre isso.

1 curtida

De fato isso faz mais sentido agora, já que apenas um número igual ao de threads fará o acesso a variável global, de fato o tempo agora está otimizado.

Uma dúvida:
É correto eu esperar as threads acabarem para eu poder fazer o calculo do tempo, dessa forma?

        for(int i = 0; i < numeroDeThreads; i++){
            while(listaDeThreads.get(i).isAlive()){}
        }
        now = System.currentTimeMillis();

Li em outro lugar que o uso da função join() seria mais adequada já que ele põe a Thread principal em espera libera o uso do core para o uso do sistema o que pode fazer ele ser utilizado por outra thread. Ou teria uma forma mais elegante de se calcular o tempo de execução das threads ?

Com certeza, eu fiz o uso de uma extrapolação pra ficar mais claro o meu objetivo, e por se tratar de um problema que é paralelizável, é de se esperar que a maneira paralela seja mais rápida que a serial (se feito da forma correta) .

Inclusive o ponto de saturação (momento em que o aumento do número de threads piora o resultado final) foi alcançado para acima de 32 Threads para 200 milhões de posições com range de números primos de 0 a 10, quem sabe se eu triplicar essa quantidade de posições (ou apenas aumentar o range de números aleatórios por posição) o ponto de saturação seja alcançado com menos threads.