Алгоритм изображения в градациях серого медленнее, чем многопоточный, чем последовательный

Question

Для школьного проекта нам нужно многопоточность алгоритма обработки изображений. Я решил разделить высоту изображения на количество нитей. Каждая нить проходит по высоте и ширине и меняет цвета пикселей. Как ни странно, последовательная версия всегда намного быстрее. Что я делаю не так?

Метод, выполняемый потоками:

public synchronized void applyGrayScale(int numberOfThreads) {
    int heightPerThread = imageHeight / numberOfThreads;
    //Set the thread counter
    int threadCounter = this.getCount();
    this.setCount(count + 1);

    /*The height per thread is calculated by the number of threads. We first start at 0. For the next thread we start at heightPerThread * [current thread number]
    So for example; first thread runs from 0 to 80 pixels. The second thread runs from 81 to 160 pixels.
     */
    for (int j = ((heightPerThread - 2) * threadCounter); j < (heightPerThread * (threadCounter + 1) - 1); j++) {
        for (int i = 0; i < imageInput.getWidth() - 1; i++) {
            //Get the RGB value and set it to grayscale
            int rgb;
            int p = RGB.getRGBW(imageInput, i, j);
            rgb = (int) ((((p >> 16) & 0xFF) * 0.2125) + (((p >> 8) & 0xFF) * 0.7154) + ((p & 0xFF) * 0.0721));
            rgb = (rgb << 16) | (rgb << 8) | (rgb);
            //Set the new RGB value per pixel
            imageOutput.setRGB(i, j, rgb);
        }
    }
}

Код для запуска программы:

   int threadsAmount = 5;
   final Thread[] threads = new Thread[threadsAmount];

   BufferedImage image = null;
    try {
        image = ImageIO.read(new File("C:/Cat03.jpg"));
    } catch (IOException e) {
        e.printStackTrace();
    }

    //Define the starting time
    long start = System.currentTimeMillis();

    //Create a new grayscale object and set the image
    final GrayscaleParallel grayscaleParallel = new GrayscaleParallel(image);

    //Thread to apply the grayscale with the number of threads
    class grayScaleThread extends Thread {
        @Override
        public void run() {
            grayscaleParallel.applyGrayScale(threadsAmount);
        }
    }

    //Start all threads
    for (int i = 0; i < threadsAmount; i++) {
        threads[i] = new grayScaleThread();
        threads[i].start();
    }

    //Wait for all threads to finish
    for (int i = 0; i < threadsAmount; i++) {
        try {
            threads[i].join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    //save result to file
    grayscaleParallel.createImage();

    //Define how long it took
    long end = System.currentTimeMillis();
    float sec = (end - start) / 1000F;
    System.out.println(sec + " seconds parallel");

Вывод: 0,897 секунды параллельно 0,798 секунд, серийный номер

Последовательный алгоритм:

 for (int j = 0; j < _image.getHeight(); j++) {
        for (int i = 0; i < _image.getWidth(); i++) {
            int rgb;
            int p = RGB.getRGBW(_image, i, j);

            rgb = (int) ((((p >> 16) & 0xFF) * 0.2125) + (((p >> 8) & 0xFF) * 0.7154) + ((p & 0xFF) * 0.0721));
            rgb = (rgb << 16) | (rgb << 8) | (rgb);

            imageOutput.setRGB(i, j, rgb);
        }
    }
    return imageOutput;

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

Answer 1

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

Вместо этого вы должны разделить изображение перед рукой - при создании потока «скажите» им, какую часть он должен изменить. Затем измените метод с synchronized на обычный и позвольте им выполнять свою работу параллельно.

Answer 2

Вы не делаете ничего плохого!

Узким местом в преобразовании изображения является не расчет, а доступ к памяти.

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

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

(Могут также быть некоторые накладные расходы для одновременного чтения / записи различных потоков в многопоточной версии, что может еще больше снизить производительность)

---

Как уже упоминалось в комментариях:

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

applyGrayScale() равен synchronized и поэтому не может быть вызван параллельно в одном экземпляре класса. Так что, если все ваши потоки используют один и тот же экземпляр, они вызывают applyGrayScale(), все остальные потоки плачут, пока один выполняет метод.

Но я уверен, что даже после исправления этого многопоточная версия будет по-прежнему работать медленнее, чем последовательная, из-за причин, упомянутых выше в моем ответе.