Разбиение программы на 4 потока происходит медленнее, чем на один поток.

Question

На прошлой неделе я писал трассировщик лучей и подошел к моменту, когда он делает достаточно, чтобы многопоточность имела смысл.Я пробовал использовать OpenMP для его распараллеливания, но запуск с большим количеством потоков на самом деле медленнее, чем запуск с одним.

Прочитав другие подобные вопросы, особенно об OpenMP, я предположил, что gcc лучше оптимизирует последовательный код.Однако запуск скомпилированного кода ниже с помощью export OMP_NUM_THREADS=1 в два раза быстрее, чем с export OMP_NUM_THREADS=4.Т.е.Это один и тот же скомпилированный код в обоих запусках.

Запускаем программу с time:

> export OMP_NUM_THREADS=1; time ./raytracer
real    0m34.344s
user    0m34.310s
sys     0m0.008s


> export OMP_NUM_THREADS=4; time ./raytracer
real    0m53.189s
user    0m20.677s
sys     0m0.096s

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

Код, который я распараллелил с помощью OpenMP

void Raytracer::render( Camera& cam ) {

    // let the camera know to use this raytracer for probing the scene
    cam.setSamplingFunc(getSamplingFunction());

    int i, j;

    #pragma omp parallel private(i, j)
    {

        // Construct a ray for each pixel.
        #pragma omp for schedule(dynamic, 4)
        for (i = 0; i < cam.height(); ++i) {
            for (j = 0; j < cam.width(); ++j) {
                cam.computePixel(i, j);
            }
        }
    }
}

При чтении этот вопрос Я думал, что нашел ответ.В нем говорится о реализации gclib rand(), синхронизирующей вызовы самого себя для сохранения состояния для генерации случайных чисел между потоками.Я довольно часто использую rand() для выборки Монте-Карло, поэтому подумал, что проблема в этом.Я избавился от вызовов rand, заменив их одним значением, но использование нескольких потоков все равно медленнее. РЕДАКТИРОВАТЬ:упс оказывается, я неправильно это проверял, это были случайные значения!

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

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

Может ли кто-нибудь подсказать места, где могут быть какие-то раздоры?Что попробовать?

Заранее спасибо.

РЕДАКТИРОВАТЬ:Извините, было глупо не предоставить дополнительную информацию о моей системе.

• Компилятор gcc 4.6 (с оптимизацией -O2)
• Убунту Линукс 11.10
• ОпенМП 3
• Intel i3-2310M Quad core 2,1 ГГц (на данный момент на моем ноутбуке)

Код для вычисления пикселя:

class Camera {

    // constructors destructors
    private:
        // this is the array that is being written to, but not read from.
        Colour* _sensor; // allocated using new at construction.
}

void Camera::computePixel(int i, int j) const {

    Colour col;

    // simple code to construct appropriate ray for the pixel
    Ray3D ray(/* params */);
    col += _sceneSamplingFunc(ray); // calls a const method that traverses scene. 

    _sensor[i*_scrWidth+j] += col;
}

Судя по предположениям, причиной замедления может быть обход дерева.Некоторые другие аспекты:при вызове функции выборки происходит довольно много рекурсии (рекурсивное отскакивание лучей) - может ли это вызвать эти проблемы?

Answer 1

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

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

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

Я протестировал код, и он работает — никаких блокировок и заметного замедления работы в результате вызовов threadrand.Не стесняйтесь указывать на грубые ошибки.

потокранд.h

#ifndef _THREAD_RAND_H_
#define _THREAD_RAND_H_

// max number of thread states to store
const int maxThreadNum = 100;

void init_threadrand();

// requires openmp, for thread number
int threadrand();

#endif // _THREAD_RAND_H_

потокrand.cpp

#include "threadrand.h"
#include <cstdlib>
#include <boost/scoped_ptr.hpp>
#include <omp.h>

// can be replaced with array of ordinary pointers, but need to
// explicitly delete previous pointer allocations, and do null checks.
//
// Importantly, the double indirection tries to avoid putting all the
// thread states on the same cache line, which would cause cache invalidations
// to occur on other cores every time rand_r would modify the state.
// (i.e. false sharing)
// A better implementation would be to store each state in a structure
// that is the size of a cache line
static boost::scoped_ptr<unsigned int> randThreadStates[maxThreadNum];

// reinitialize the array of thread state pointers, with random
// seed values.
void init_threadrand() {
    for (int i = 0; i < maxThreadNum; ++i) {
        randThreadStates[i].reset(new unsigned int(std::rand()));
    }
}

// requires openmp, for thread number, to index into array of states.
int threadrand() {
    int i = omp_get_thread_num();
    return rand_r(randThreadStates[i].get());
}

Теперь вы можете инициализировать случайные состояния потоков из main с использованием init_threadrand(), а затем получить случайное число, используя threadrand() при использовании нескольких потоков в OpenMP.

Answer 2

Ответ: не зная, на какой машине вы это запускаете, и не видя по-настоящему кода вашего computePixel функция, от этого зависит.

Существует довольно много факторов, которые могут повлиять на производительность вашего кода, один из которых приходит на ум — это выравнивание кэша.Возможно, ваши структуры данных, а вы упомянули дерево, не совсем идеальны для кэширования, и ЦП в конечном итоге ждет поступления данных из ОЗУ, поскольку он не может поместить данные в кеш.Неправильное выравнивание строк кэша может привести к чему-то подобному.Если процессору приходится ждать поступления данных из ОЗУ, вполне вероятно, что поток будет отключен от контекста и будет запущен другой.

Планировщик потоков вашей ОС недетерминирован, поэтому когда запуск потока — вещь непредсказуемая, поэтому, если случится так, что ваши потоки будут работать мало или будут конкурировать за ядра ЦП, это также может замедлить работу.

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

Есть и другие факторы, о которых я не сразу вспомнил, однако я предлагаю немного почитать о многопоточности.Это сложная и обширная тема.Там много материала.

Записываются ли данные в конце, данные, которые должны быть доступны другим потокам? computePixel ?

Answer 3

Одна из сильных возможностей заключается в том, ложный обмен.Похоже, что вы вычисляете пиксели последовательно, поэтому каждый поток может работать с чередующимися пикселями.Обычно это очень плохой поступок.

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

Чтобы это исправить, вам необходимо убедиться, что каждый поток действительно работает в независимом регионе.Сейчас кажется, что вы делите по строкам (я не уверен, так как не знаю OMP).Работает ли это, зависит от того, насколько велики ваши строки, но конец каждой строки все равно будет перекрываться с началом следующей (с точки зрения строк кэша).Возможно, вы захотите разбить изображение на четыре блока и заставить каждый поток работать с серией последовательных строк (например, 1..10 11..20 21..30 31..40).Это значительно сократит обмен.

Не беспокойтесь о чтении постоянных данных.Пока блок данных не изменяется, каждый поток может эффективно читать эту информацию.Однако будьте осторожны с любыми изменяемыми данными, которые есть в ваших постоянных данных.

Answer 4

Я только что посмотрел и Интел i3-2310M на самом деле у него не 4 ядра, у него 2 ядра и гиперпоточность.Попробуйте запустить свой код всего в двух потоках и убедитесь, что это поможет.Я считаю, что в целом гиперпоточность совершенно бесполезна, когда у вас много вычислений, и на своем ноутбуке я отключил ее и добился гораздо лучшего времени компиляции своих проектов.

На самом деле, просто зайдите в BIOS и отключите HT — это бесполезно для компьютеров разработки и вычислений.