Многопоточная обработка массива

[__Heaven__]

Привет, друзья!
Ни разу не занимался мультипоточным программированием кроме случая, когда нужно интерфейс отделить от вычислений.
Суть задачи:
Имеется вектор вершин в виде xyzxyzxyz.... Необходимо брать по 3 вершины и вычислять нормаль. Нормаль записывать в соседний вектор для каждой из вершин (то есть трижды подряд).

Пока что гляжу в сторону QAtomicInt, но понятия не имею, как это всё реализуется.
Нужно ли выделять отдельный класс для решения задачи? Нужно ли создавать отдельные QThread?
Прошу помочь разобраться и найти оптимальный вариант решения задачи.

[Old]

Пока что гляжу в сторону QAtomicInt, но понятия не имею, как это всё реализуется.

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

Нужно ли выделять отдельный класс для решения задачи? Нужно ли создавать отдельные QThread?
Прошу помочь разобраться и найти оптимальный вариант решения задачи.

Самое простое разбить весь массив на регионы и каждый регион отдать отдельной нитке.

[__Heaven__]

Самое простое разбить весь массив на регионы и каждый регион отдать отдельной нитке.

То есть, нужно объявить класс, который принимает диапазон из вектора. Объявить таких 4 класса, передвинуть их в 4 нитки стартануть и дождаться выполнения. Верно?

[Old]

То есть, нужно объявить класс, который принимает диапазон из вектора. Объявить таких 4 класса, передвинуть их в 4 нитки стартануть и дождаться выполнения. Верно?

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

[__Heaven__]

Вы намекаете на QtConcurrent::run?
Меня смущает

The thread is taken from the global QThreadPool. Note that the function may not run immediately; the function will only be run when a thread is available.

Если я возьму и запущу QtConcurrent::run столько раз, сколько выдаст QThread::idealThreadCount(), то у меня не будет ли застоя какой-либо из веток?

Как выполнить запуск функции в 4 нитки?

[m_ax]

Вы намекаете на QtConcurrent::run?
Меня смущает

The thread is taken from the global QThreadPool. Note that the function may not run immediately; the function will only be run when a thread is available.

Если я возьму и запущу QtConcurrent::run столько раз, сколько выдаст QThread::idealThreadCount(), то у меня не будет ли застоя какой-либо из веток?

Как выполнить запуск функции в 4 нитки?

Похоже вам нужна параллельный вариант std::transform, если я правильно понял..

[Old]

QtConcurrent::run один из вариантов, можно использовать std::thread. Да и класс для этого можно сделать.
Вы можете вызвать QtConcurrent::run сколько нужно раз, если на все задачи не хватит потоков, задачи станут в очередь и будут выполняться по мере освобождения рабочих нитей.

[Old]

Похоже вам нужна параллельный вариант std::transform, если я правильно понял..

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

[__Heaven__]

QtConcurrent::run один из вариантов, можно использовать std::thread. Да и класс для этого можно сделать.
Вы можете вызвать QtConcurrent::run сколько нужно раз, если на все задачи не хватит потоков, задачи станут в очередь и будут выполняться по мере освобождения рабочих нитей.

Что имеется в виду под рабочими потоками? Я не хочу получить ситуацию, когда у меня 4 физ ядра и на них выполняется 3 нитки расчетов.
Про методы std почитаю, как буду у компа, спасибо

[Old]

У QtConcurrent под капотом пул поток QThreadPool. Почитайте сразу и про него.

[Igors]

Не очень удачная задача - вычисление нормали слишком быстрая операция чтобы получить ощутимый эффект от распараллеливания. В любом случае нужен инструментарий, вариантов много concurrent, tbb, std::thread> QThread. Лично я использую OpenMP и очень доволен, выглядит так

Код

C++ (Qt)
#pragma omp parallel for
for (int i = 0; i < N; ++i)
 DoCalcNormal(i);

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

Атомики могут использоваться для нахождения индекса, напр

Код

C++ (Qt)
void threadFunc( void )
{
  while (true) {
   int index = theAtomicCount++;
   if (index >= maxTask) return;
   CalcNormal(index);
 }
}
 

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

[xokc]

Лично я использую OpenMP

Соглашусь. Для таких задач проще инструмента не найти. И опять же соглашусь, что для того, чтобы ощутить эффект от распараллеливания для этого алгоритма нужно обсчитывать ну ООООЧЧЧЧЕЕЕННЬ длинные массивы. Тут скорее спасёт что-нибудь типа Intel IPP library, способное использовать SSE команды процессора.

[__Heaven__]

Атомики могут использоваться для нахождения индекса, напр

а при их использовании процессы ведь начнут душить друг друга?

Соглашусь. Для таких задач проще инструмента не найти. И опять же соглашусь, что для того, чтобы ощутить эффект от распараллеливания для этого алгоритма нужно обсчитывать ну ООООЧЧЧЧЕЕЕННЬ длинные массивы. Тут скорее спасёт что-нибудь типа Intel IPP library, способное использовать SSE команды процессора.

меня интересует не только ускорение этого участка, но также и другие части функции открытия файла. Хочу, чтобы большие объёмы обрабатывались очень быстро.
Какой размер для вас оооооччччеееннь большой?
А опциями компилятора нельзя получить эффета SSE? Кстати, я слышал, что интеловские библиотеки могут подтормаживать выполнение вместо ускорения.
Вижу, что OpenMP имеет преимущества в плане простоты написания. Как насчёт скорости?
Почему OpenMP, а не OpenCL?

[xokc]

Какой размер для вас оооооччччеееннь большой?

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

А опциями компилятора нельзя получить эффета SSE?

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

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

Безусловно, могут - если у вас код написан лучше, чем его могут написать в Intel. Но мой опыт говорит говорит об обратном.

Вижу, что OpenMP имеет преимущества в плане простоты написания. Как насчёт скорости?

Скорости по сравнению с чем? Если с ручным управлением пулами потоков и распределением обрабатываемого массива между ними или QtConcurrent/TBB, то все они делают примерно одно и тоже. Погрешность будет на уровне точности измерения.

Почему OpenMP, а не OpenCL?

У них несколько разные задачи и подход к их решению. OpenMP предназначен, прежде всего, для простого автоматического распараллеливания кода в тех случаях, когда разработчик не желает вдаваться в подробности того, как это реализуется компилятором. Здесь, как и показывал Igors, достаточно написать простой макрос перед телом распараллеливаемого цикла и забыть обо всём.
OpenCL же - это вполне себе навороченный фреймворк со своим ЯП, который позволяет выполнять код в том числе на GPU. В вашем случае это из пушки по воробьям будет. Там уж накладные расходы на передачу данных из ОЗУ в память видеокарты и обратно точно уничтожат всю выгоду от их обработки на GPU.

[Igors]

а при их использовании процессы ведь начнут душить друг друга?

В какой-то мере да, но накладные расходы есть всегда, и часто они значительны. Пример: дали каждой нитке свою часть индексов. Напр 1-я получает [0..100], вторая [100..200] и.т.д. Казалось бы, это идеальный вариант, никто никого не душит. Но тут др беда - загруженность у ниток разная, напр 1-я уже посчитала все 100, а 2-я только 10. Придется "ждать отстающих"

меня интересует не только ускорение этого участка, но также и другие части функции открытия файла. Хочу, чтобы большие объёмы обрабатывались очень быстро.

Чтение/загрузка - не те места где распараллеливание эффективно, т.к. все упирается в I/O. Здесь обычно ускоряются на синтаксическом разборе

А опциями компилятора нельзя получить эффета SSE?

Типа "спрошу-ка еще раз то же самое - а вдруг сейчас ответят как мне понравится". Ничего не напоминает?