Question about parallel programming

Question

Question about parallel programming

Navigation

#1 by (1 votes)

1

I'm starting to learn parallel programming, and I'm wanting to compare a single threaded program to a multithreaded one.

What I thought was to make a very simple algorithm that, within a period of 1 minute, calculate the largest number of possible prime numbers, and show me the last calculated prime number and its position in the prime numbers, for example , let's say it was number 23, would appear the number 23 and its position, in case 9, since it is the 9th prime number.

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

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

Calculate:

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;
        }
      }
  }

Main:

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 it every 8, so that neither of them computes repeated values. In the end, I get the getQuality of each and somo, and I see the largest getUltimo to get the highest value. I think the error is because some thread is calculating a bit faster, so the amount goes wrong.

java paralelismo

asked by anonymous 01.05.2017 / 16:53

1 answer

Submit to same page and return to same section Delete listview item in Xamarin [closed]

score 1 · Accepted Answer

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 prime numbers are equally distributed across 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. In example 1, you would expect the return to be 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 would be 4 + 1 = 5.

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

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

About synchronized: If you have multiple threads accessing the same area of memory you can create a conflict in which 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 that same method, you 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);
                }
            }

        }
      }
  }

(You may need some adjustments, I wrote without testing.)

In this way, each Thread that wants to analyze a new number will ask next for the next number in the "queue", and when it finds it, it is reported to the In theory this will slow down slightly because the heavy processing is in making the 2 loops, however it is a consequence of the need to process in order.