Как реализовать многопоточность в трассировке лучей Java

Question

Я пишу программу трассировки лучей на Java и реализовал многопоточность с использованием интерфейса Runnable.Каждый поток отображает часть 800 вертикальных линий.При использовании двух потоков они будут отображать 400 строк каждый.Для 8 потоков по 100 строк в каждом и т. Д.

Мое решение в настоящее время работает, но время рендеринга увеличивается при использовании большего количества потоков.Время рендеринга каждой строки увеличивается примерно в 3 раза, когда вы удваиваете количество потоков.Но большее количество строк отображается одновременно, поэтому общее время визуализации увеличивается примерно на 50%, что все еще плохо.Это должно быть быстрее.

Я знаю, что потоки отображают только правильные линии, я проверил, чтобы одни и те же пиксели не отображались несколько раз.Я попытался убедиться, что каждый поток записывает свои переменные во время цикла рендеринга, и суммировать / комбинировать их после того, как весь цикл завершен.Мой ЦП имеет 8 потоков, и загрузка процессора высока, но не 100% при рендеринге даже на 8 потоках.

class Multithread implements Runnable {
  Camera camera;
  CountDownLatch latch;
  ...

  //Constructor for thread
  Multithread(Scene s, Camera c, int thread, int threadcount, CountDownLatch cdl){
      camera = c;
      latch = cdl;
      ...
  }

  public void run(){
      try{
          ...
          //This is the render function
          camera.render(...);

          //When all threads unlatch, main class will write PNG
          latch.countDown();
      }
      catch (Exception e){System.out.println ("Exception is caught");}
  }
}

public class Camera {
    //The final pixel values are stored in the 2D-array
    ColorDbl[][] finalImage;

    Camera(int w){
        Width = w;
        finalImage = new ColorDbl[w][w]
    }

    //Start rendering
    void render(Scene S, int start, int end){

        //Create temporary, partial image
        ColorDbl[][] tempImage = new ColorDbl[Width][Width];

        Ray r;
        ColorDbl temp;
        //Render lines of pixels in the interval start-end
        for(int j = start; j < end; ++j){
            for(int i = 0; i < Width; ++i){
                r = new Ray(...);
                temp = r.CastRay(...);
                tempImage[i][j] = temp;
            }
        }

        //Copy rendered lines to final image
        for(int j=start; j<end; ++j){
            for(int i=0; i<Width; ++i){
                finalImage[i][j] = tempImage[i][j];
            }
        }
    }

    public static void main(String[] args) throws IOException{
        //Create camera and scene
        Camera camera = new Camera(800);
        Scene scene = new Scene();

        //Create threads
        int threadcount = 4;
        CountDownLatch latch = new CountDownLatch(threadcount);
        for (int thread=0; thread<threadcount; thread++){
            new Thread(new Multithread(scene, camera, thread, threadcount, latch)).start();
        }

        //Wait for threads to finish
        try{
          latch.await();
        }catch(InterruptedException e){System.out.println ("Exception");}

        //Write PNG
        c.write(...);
    }
}

При использовании 2 потоков вместо 1 я ожидаю почти удвоения рендерингаскорость, но вместо этого это займет на 50% больше.Я не ожидаю, что кто-нибудь решит мою проблему, но я был бы очень признателен за некоторые рекомендации, когда дело доходит до реализации многопоточности.Я поступаю неправильно?

Answer 1

Я нашел свою проблему и решил ее, и теперь она отлично работает, 16 потоков работают почти в 16 раз быстрее, чем 1 поток.

Думаю, проблема заключалась в том, что при создании каждого потока я передавал один и тот же объект Scene вместо нового объекта Scene. Из-за этого потоки должны были ждать друг друга в какой-то другой функции во время рендеринга.

//This is what caused the blocking
Scene s1 = new Scene(arg, arg);
Scene s2 = s1;
Scene s3 = s1;

Thread T1 = new Thread(s1);
Thread T2 = new Thread(s2);
Thread T3 = new Thread(s3);

T1.start();
T2.start();
T3.start();

Исправление:

Scene s1 = new Scene(arg, arg);
Scene s2 = new Scene(arg, arg);
Scene s3 = new Scene(arg, arg);
...

VisualVM был критически важен для нахождения блокировки, и я благодарю Philipp Claßen за совет, поскольку я бы никогда не решил это иначе.

Answer 2

В исходном коде, который вы разместили, я не вижу очевидного узкого места.Когда параллельный код выполняется медленнее, наиболее распространенными объяснениями являются либо издержки из-за синхронизации, либо выполнение дополнительной работы.

Когда речь идет о синхронизации, высокая загруженность может привести к тому, что параллельный код будет выполняться очень медленно.Это может означать, что потоки (или процессы) борются за ограниченные ресурсы (например, ожидают блокировки), но это также может быть более тонким, чем доступ к той же памяти с использованием атомарных операций, что может быть довольно дорогостоящим.В вашем примере я не видел ничего подобного.Похоже, единственной операцией синхронизации в конце являются защелки обратного отсчета, что не должно быть значительным.Неравные рабочие нагрузки также могут повредить масштабируемости, но в вашем примере это маловероятно.

Выполнение дополнительной работы может быть проблемой.Может быть, вы копируете больше данных в параллельной версии, чем в последовательной?Это может объяснить некоторые накладные расходы.Другое предположение состоит в том, что в параллельной версии локальность кэша была затронута отрицательно.Обратите внимание, что эффект кэша является значительным (как правило, доступ к памяти может стать в 50-100 раз медленнее, когда ваша рабочая нагрузка больше не помещается в кэш).

Как найти узкое место?В общем, это называется профилированием.Существуют специализированные инструменты, например, VisualVM - это бесплатный инструмент для Java, который можно использовать в качестве профилировщика.Другой, даже более простой, но часто очень эффективный первый подход - это запустить вашу программу и получить несколько случайных дампов потоков.Если у вас есть очевидное узкое место, вполне вероятно, что вы увидите его в трассировке стека.

Технику часто называют профилировщиком бедняка, но я нашел ее очень эффективной (см. этот ответ Больше подробностей).Кроме того, вы также можете безопасно применять его в производственной среде, так что это хитрый трюк, когда вам нужно оптимизировать код, который вы не можете запустить на локальном компьютере.

IDE (например, Eclipse или IntelliJ) имеют поддержкуПоток дампов, но вы также можете запустить его непосредственно из командной строки, если вы знаете идентификатор процесса:

 kill -3 JAVA_PID

Программа (или JVM, которая ее запускает) затем распечатает текущую трассировку стека всех текущих потоков,Если вы повторите это пару раз, вы должны понять, на что ваша программа тратит большую часть своего времени.

Вы также можете сравнить ее с вашей последовательной версией.Возможно, вы заметили какой-то паттерн, объясняющий издержки параллельной версии.

Надеюсь, это немного помогло начать работу.