Java Thread: Single vs Multi

Gabriel Barbosa Brandao · 12 de maio de 2022

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 não é primo
        return true;
    }

    public static long getQuantidadeDePrimos() {
        return somaNumeroDePrimos;
    }

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