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

Se desta vez compreendi corretamente o seu problema, você está realizando o mesmo processo de contabilizar os primos em uma única variável sincronizada tal como no último projeto, correto? Pois bem, vamos aos motivos do mais simples de resolver ao mais difícil:

1. Espera ineficiente pela finalização das threads

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

Este trecho do seu código é ineficiente, em vez de esperar você está mantendo a thread principal do processo constantemente ocupada verificando o estado das threads, monopolizando um dos núcleos do seu computador quando este poderia ser utilizado por alguma das thread ‘operárias’.

Sujestão

Utilize o método .join() para esperar pela finalização das suas threads, este método põe a thread em espera e devolve o núcleo para o sistema.

2. Sincronização da variável somaNumeroDePrimos

O seu código é menos paralelo do que poderia ser, o fato de você ter uma variável sincronizada compartilhada entre diversas threads, induz em muitos momentos uma espera desnecessária de uma ou mais threads pela liberação desta variável.

Alem disso, o simples fato de você ter um trecho sincronizado executando em cada thread, induz o sistema a realizar mais trocas de contexto do que seriam necessárias, já que algumas threads poderão concorrer para escrever na mesma variável e precisarão “esperar” o que significa devolver o núcleo para o sistema, até a variável estar disponível e o scheduler decidir devolver o núcleo para a thread, o que incorre em trocas de contexto que são pesadas (sistema copia memória da thread do registro do núcleo, escreve de outra, possivelmente limpa antes com todos estes problemas de segurança em CPUs, etc).

Sujestão

Não utilize uma variável sincronizada para este problema, deixe cada thread contabilizar o valor em sua própria variável e some os resultados ao fim, você vai precisar refatorar um pouco, existem diversas formas de se fazer isso, a mais simples provavelmente é enviar um objeto para cada thread gravar o valor, outra é usar um callbacks, outra seria usar Future, FutureTaks e callable, etc.

3. Criação de threads

criar e destruir threads é uma tarefa custosa, um pouco menos que criar processos, mas ainda assim não é desprezível, especialmente quanto maior for o número de threads que você terá de criar e destruir.

Sujestão

Utilize ExecutorService para criar um ThreadPool com um tamanho fixo, preferencialmente com a mesma quantia de threads que você tem de núcleos em sua CPU, ExecutorService vai lhe permitir submeter quantas tarefas quiser, sem escalar o número de threads, irá reutilizará as threads, o que é menos custoso. A vantagem aqui é que você já resolve o problema 2 pois ExecutorService faz uso de Future.

2 curtidas

No caso eu teria que esperar todas as Threads acabarem para que eu possa calcular o tempo de execução delas, então o código ficaria da seguinte forma ?

.
.
.
 for(int i = 0; i < numeroDeThreads; i++){
       listaDeThreads.get(i).join()
 }

        now = System.currentTimeMillis();

dessa forma eu evitaria que o núcleo responsável pela Thread principal ficasse ocioso ?

Resolvi o problema simplesmente criando uma variável local na função run() e só após cada thread acabar sua respectiva busca é que ela faz o acesso sincronizado a variável compartilhada, dessa forma eu limito o acesso a variável somaNumeroDePrimos ao número de threads criadas, em vez de ter um acesso a sessão crítica sequencial de cada posição acessada por cada thread .

Ao contrário, você garantiria que a thread principal ficasse ociosa. Pois atualmente a sua thread permanece ocupada fazendo o esforço de perguntar milhares de vezes para as threads se elas estão vivas, quando o correto seria, apenas pedir para as threads avisarem quando morrerem e devolver o núcleo para o sistema até alguma thread avisar ou o scheduler do OS decidir devolver um núcleo para a thread principal. O código é esse mesmo.

Mas simplificando, em ambos os casos, você estaria ocupando 4 núcleos de um CPU quad-core, mas no método antigo, um dos núcleos estaria ocupado fazendo uma tarefa totalmente improdutiva, ficar perguntando constantemente para as threads se já terminaram, quando poderia ser usado por alguma delas para calcular o número de primos.

É melhor, mas ainda não é o ideal. O seu problema é bastante paralelizável exatamente porque não existe a necessidade de ter uma variável compartilhada. Você ter que sincronizar ou bloquear a thread nem que seja uma vez, ainda incorre em uma troca de contexto a mais do que seria necessário.

3 curtidas