Doubt about parallel programming

Question

I’m starting to learn parallel programming, and I’m looking to compare a program with a single thread with a multi thread.

What I thought was to make a very simple algorithm that, in a 1-minute interval, would calculate as many prime numbers as possible, and, show me the last calculated prime number and its position in prime numbers, for example, let’s say it was number 23, would appear number 23 and its position, in case 9, because it is the 9th prime number.

Without using parallelism, the number found was 774107, at position 62039. However, using parallelism, I obtained the number 1083757, at position 84444 (the wrong position, the right one would be 84547), I believe it was a very basic mistake, but, as I still do not understand much about parallelism, I could not solve it.

Below follows the code of the two classes I created, the first, is the Calculates class that only serves to define the instances and implement the run method. The second is Main class.

Calculates:

import java.util.Collection;

  public class Calcula extends Thread { 
      private int x;
      private int quantidade = 0;
      private int ultimo = 0;
      private long tempoInicial;

      public Calcula(int x, long tempoInicial) {
          this.x = x;
          this.tempoInicial = tempoInicial;
      }

      public int getQuantidade (){
          return quantidade;
      }

      public int getUltimo (){
          return ultimo;
      }

      @Override
      public void run() {
        long tempoMaximo=tempoInicial;
        while (tempoMaximo < tempoInicial+60000){
            tempoMaximo = System.currentTimeMillis();
            for(int z=2; z<x/2; z++){
                if (x%z==0) break;  
                else if(z==(x/2)-1){
                    quantidade++;
                    ultimo=x;
                }
            }
            x=x+8;
        }
      }
  }

Leading:

import java.util.ArrayList;
import java.util.Collection;

public class Principal{
    public static void main(String[] args){
        long tempoInicial = System.currentTimeMillis();
        Calcula t1 = new Calcula (5, tempoInicial);
        Calcula t2 = new Calcula (7, tempoInicial);
        Calcula t3 = new Calcula (9, tempoInicial);
        Calcula t4 = new Calcula (11, tempoInicial);

        t1.start();
        t2.start();
        t3.start();
        t4.start();

        try{
            t1.join();
            t2.join();
            t3.join();
            t4.join();
        } catch (InterruptedException ex){
            ex.printStackTrace();
        }

        int ultimo = t1.getUltimo();
        if (ultimo < t2.getUltimo()) ultimo = t2.getUltimo();
        if (ultimo < t3.getUltimo()) ultimo = t3.getUltimo();
        if (ultimo < t4.getUltimo()) ultimo = t4.getUltimo();

        System.out.println("Último primo encontrado: " + ultimo);
        System.out.println("Quantidade de primos encontrados: " + (t1.getQuantidade() + t2.getQuantidade() + t3.getQuantidade() + t4.getQuantidade()));
    }
}

The logic I followed was to start each thread with a different value and implement them 8 by 8, so that no repeat values are calculated. In the end, I take the getQuatity of each and each, and I see the greatest getUltimo to get the highest value. I believe the error is because some thread is calculating a little faster, then the amount goes wrong.

Answer 1

The problem is that there is no guarantee that all threads will process at exactly the same speed. Just for example, let’s assume that the prime numbers are equally distributed among the Threads; for example, if it were only 2 Threads: A and B:

Position : Thread

1A 2B 3A 4B 5A 6B 7A 8B

Then the threads will find, in order: A: 1,3,5,7 B: 2,4,6,8

However, there is no guarantee that everyone will process at the same speed, parallelism can cause something like:

Example 1:

A: 1,3
B: 2,4,6,8

Example 2:

A: 1,3,5,7
B: 2

And so on and so forth. In example 1, you would expect the return to be at position 8, but since A was slower and processed only 2 elements, 2+4 = 6. And in example B, the expected result would be 7, but it will be 4+1 = 5.

To know the position you need to ensure that all prime numbers prior to the maximum result found have been found as well: One way to do this is to ensure that the numbers are processed in the order.

For this you can share the maximum number, the counter and the next number among all Threads; You can do this by passing a control object or creating some static methods; In both cases set using Synchronized.

About Synchronized: If you have multiple threads accessing the same area of memory you can create a conflict where one thread erases the value of the other. When defining a block as Synchronized, you are telling Java that only one can access at a time, if another tries to access this same method you will have to wait.

It looks something like:

 public class Calcula extends Thread { 
      private static quantidade = 0;
      private static int ultimo = 0;
      private static int proximo = 2;
      private long tempoInicial;

      public Calcula(long tempoInicial) {
          this.tempoInicial = tempoInicial;
      }

      public int getQuantidade (){
          return quantidade;
      }

      public int getUltimo (){
          return ultimo;
      }

      private static synchronized void primoEncontrado(int n){
          quantidade += 1;
          if (n > ultimo) ultimo = n;
      }

      private static synchronized int proximo() {
         return proximo++;
      }

      @Override
      public void run() {
        long tempoMaximo=tempoInicial;
        int x;
        while (tempoMaximo < tempoInicial+60000){
            x=proximo();
            tempoMaximo = System.currentTimeMillis();
            for(int z=2; z<x/2; z++){
                if (x%z==0) break;  
                else if(z==(x/2)-1){
                    primoEncontrado(x);
                }
            }

        }
      }
  }

(May need some adjustments, wrote without testing).

That way every Thread you want to parse a new number will ask next by the next number in the "queue", and upon finding is reported to exquisite In theory this will reduce the speed slightly because the heavy processing is in making the 2 loops, but it is a consequence of the need to process in order.