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