Эффективная параллельная первичная факторизация

Question

Я пытаюсь сделать параллельную версию простой факторизации в Java, и у меня есть рабочая программа. Тем не менее, программа работает очень медленно - намного медленнее, чем моя последовательная версия. Я понимаю, что это может быть связано с оптимизацией потоков и большим количеством потоков (я пытался использовать ExecutorService, но я не думаю, что я действительно освоился с этим). Кто-нибудь, кто может указать способ оптимизировать этот кусок кода?

class HovedFaktorArbeider implements Runnable //Class for first step factorization
  {
    int fra;
    int til;
    int id;
    List<Long> tempFaktorer; //Must be long since we'll stumble upon primes larger than int.MAX_VALUE accidentally
    long[] lokaleFaktorer;
    CyclicBarrier faktorBarrier = new CyclicBarrier(k+1);
    ExecutorService executorService = Executors.newFixedThreadPool(2);
    long g;

    public HovedFaktorArbeider(int fra, int til, int id)
    {
      this.fra = fra;
      this.til = til;
      this.id = id;
    }

    public void run()
    {
      try
      {
        //int tempK = 2; //Erstatter bare k for aa sjekke
        long tempN = (long) n;
        g = (tempN*tempN)-100;
        long tall = g + (long) fra; //The long numbers to be factorized
        for(int i = fra; i <= til; i++) //For the number split
        {
          int tempFra = 0;
          int tempTil = 0;
          int rest = 0;
          int faktor = 0;
          if(primes.size() % k > 0)  //If not perfect division
          {
            rest = (primes.size() % k);  //Saving remainder
            faktor = (primes.size()/k);  //Saving divisor, spreading remainder
            rest--; //Decrement remainder
          }
          else  //If perfect divison
            faktor = primes.size()/k;

          tempTil = faktor; //Setting end value

          tempFaktorer = new ArrayList<Long>();
          for(int ii = 0; ii < k; ii++) //For the prime number split
          {
            //executorService.submit(new HjelpeFaktorArbeider(tempFra, tempTil, tall, ii));
            new Thread(new HjelpeFaktorArbeider(tempFra, tempTil, tall, ii)).start();
            tempFra = tempTil + 1; //Set new value for start
            if(rest > 0)
            {
              tempTil += faktor + 1; //Spreading remainder
              rest--;
            }
            else
              tempTil += faktor; //New end value
          }
          faktorBarrier.await();
          lokaleFaktorer = new long[tempFaktorer.size()];
          for(int j = 0; j < tempFaktorer.size(); j++)
          {
            lokaleFaktorer[j] = tempFaktorer.get(j);
          }
          faktorer[i] = lokaleFaktorer; //TNB: i does not start at 0, so placement should be correct
          tall++;
        }
        mainBarrier.await();
        executorService.shutdown();
      }
      catch(Exception e){e.printStackTrace();}
    }

    public synchronized void oppdaterTempFaktorer(long tall)
    {
      tempFaktorer.add(tall);
    }

    class HjelpeFaktorArbeider implements Runnable //Class for second step factorization
    {
      int fra;
      int til;
      int id;
      long tall;


      public HjelpeFaktorArbeider(int fra, int til, long tall, int id)
      {
        this.fra = fra;
        this.til = til;
        this.id = id;
        this.tall = tall;
      }

      public void run()
      {
        try
        {
          long t = tall;
          for(int i = fra; i < til; i++)
          {
            int primtall = primes.get(i);

            while(t % primtall == 0)
            {
              try
              {
                oppdaterTempFaktorer((long) primtall);
              }
              catch(Exception e){e.printStackTrace();}

              t = t/primtall;
            }
          }
          runBarrier.await();
          if(t > 1 && id == 0 && !tempFaktorer.contains(t))
          {
            try
            {
              oppdaterTempFaktorer(t);
            }
            catch(Exception e){e.printStackTrace();}
          }
          faktorBarrier.await();
        }
        catch(Exception e){e.printStackTrace();}
      }
    }
  }

На данный момент у меня есть список простых чисел, найденных через сито Эрастотена, ограничение n и число ядер k (8 на моей машине).

P.S .: причина, по которой существует два класса Runnable, заключается в том, что мне нужно, чтобы каждая факторизация выполнялась несколькими потоками.

Answer 1

Если вас интересует параллелизм, я предлагаю вам взглянуть на другие модели параллелизма, такие как Futures или Actors. Темы и блокировки SOooo0o 2007.

Что касается вопроса о том, как сделать параллельный код быстрее, это вопрос на миллиард долларов, который имеет много подходов. Это полностью зависит от вашей проблемы и вашей архитектуры.

Так что начинать со своей проблемы - это не фантастическая проблема - использовать параллельные архитектуры, как вы можете видеть, потому что, например, скажем, у вас 9 потоков, и вы проверяете числа 2,3,4,5,6,7 , 8,9,10, это уже довольно плохо, потому что вам не нужно проверять 4,6,8,9,10, так как 2 и 3 показали бы, что они довольно плохие (хорошо, вы, вероятно, не будете проверять четные числа, но только чтобы доказать свою точку зрения). Поэтому некоторые проблемы не могут очень хорошо использовать параллельный код, как вы можете видеть здесь.

Что касается вашего вопроса о том, как эффективно распараллелить Java-код, то наиболее приемлемый ответ - нет. Программисты в наши дни больше заботятся о том, чтобы не блокировать потоки, которые обычно вращаются вокруг принципала don't call me we'll call you. Но как написать эффективный параллельный код для математической задачи - это слишком широкий вопрос информатики.

Но в целом ваш вопрос слишком широкий.