Не масштабится :-(

[ssoft]

Нужно убрать цикл из цикла, а затем уже параллелить

Код

C++ (Qt)
std::vector<Vec3> CPolySDS::CalcVerNormals( const std::vector<Vec3> & pos ) const
{
	std::vector<Vec3> dst(pos.size());
	std::vector<Vec3> faces( mNorIndex.size() / mNumVerPerFace );
 
        // эффективно распараллеливаем здесь
	for (size_t i = 0; i < mNorIndex.size(); i += mNumVerPerFace) {
		faces[ i / mNumVerPerFace ] = GetFaceNormal(&mNorIndex[i], mNumVerPerFace, pos);
	}
 
        // не очень эффективно распараллеливаем здесь
	for (size_t i = 0; i < mNorIndex.size(); i += mNumVerPerFace) {
		for (size_t j = 0; j < mNumVerPerFace; ++j)
			dst[mNorIndex[i + j]] += faces[ i / mNumVerPerFace ];
	}
 
// ну и далее вектор посылается на видеокарту
 

Как вариант не очень эффективное распараллеливание попробовать реализовать без блокировок диапазонами таким способом

Номера индексов mNorIndex поделить на диапазоны. Первым потоком выполнять операции только для [0...N1), вторым - [N1...N2) и т.д. [Nx...mNorIndex.size()).
Диапазоны нужно выбирать так, чтобы кеши CPU заведомо не пересеклись.

[ssoft]

Номера индексов mNorIndex поделить на диапазоны. Первым потоком выполнять операции только для [0...N1), вторым - [N1...N2) и т.д. [Nx...mNorIndex.size()).

Правильно так:
Значения индексов mNorIndex поделить на диапазоны. Первым потоком выполнять операции только для [0...N1), вторым - [N1...N2) и т.д. [Nx...max_index)).
Где max_index, максимальное значение из mNorIndex.

[Igors]

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

Пожалуйста, прочтите стартовый пост.

Нужно убрать цикл из цикла, а затем уже параллелить

Если имеется ввиду "сделать 2 цикла и параллелить каждый" - то так теряем время на запись/чтение (вектор faces) + (еще хуже) ждем на барьере после первого цикла.

Правильно так:
Значения индексов mNorIndex поделить на диапазоны. Первым потоком выполнять операции только для [0...N1), вторым - [N1...N2) и т.д. [Nx...max_index)).
Где max_index, максимальное значение из mNorIndex.

Такое "деление на диапазоны" (иногда называют "stencil") совсем не бесплатно/безобидно. И предрассчитать его получается далеко не всегда.

Я бы делал просто "мешком локеров", напр для Qt

Код

C++ (Qt)
std::vector<int> lock(pos.size());

И перед каждым += с наглой мордой привести к QAtomicInt и лочить testAndSetAcquire

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

[ssoft]

Такое "деление на диапазоны" (иногда называют "stencil") совсем не бесплатно/безобидно. И предрассчитать его получается далеко не всегда.

Найти (или предположить) диапазон значений индексов - откуда здесь могут быть большие затраты?

Я бы делал просто "мешком локеров", напр для Qt

Любые локеры сделают только хуже. Здесь может только помочь распараллеливание безо всяких локеров. Все потоки пробегаются по всему циклу, только производят вычисления каждый в своем диапазоне. В своих задачах я формирую массивы типа faces заранее (увеличиваю только при необходимости), чтобы не иметь потерь на new|delete.
Использование заранее инициированного пула потоков и ожидание на барьере после первого цикла и далее после второго ничтожно по сравнению с затратами на вычисления.
И да, расчеты нормалей, как правило делают на GPU.

[RedDog]

Пожалуйста, прочтите стартовый пост.

Из первого поста не сильно понятно как было сделано распараллеливание.
Хотя бы псевдокод посмотреть, с теми локами и конкурентным доступом к общим объектам.
PS: OMP параллелит далеко не всегда адекватно.

[vipet]

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

Очень приятно блять.

thrust использовали на реальном проекте, работает норм, могу рекомендовать. Что быстрее - считать на цпу или передать данные (или создать) на гпу - решай сам, замерь, какие проблемы.

[Igors]

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

Для "приличных", нормальных задач - да. А вот для таких мелких - нет. Что вполне естественно. Напр для каждого вертекса нужно собрать индексы фейсов куда он входит. Конечно вычислений никаких, но читаются/пишутся немалые вектора, а это уже соразмеримо с временем вычисления нормалей.

И да, расчеты нормалей, как правило делают на GPU.

Разумеется гуглил (правда без особого фанатизма) но ничего не нашел. Очевидно нужно задействовать какой-то "инструментарий", но вот какой? Требования к видео: OpenGL 3.3, т.е. рассчитывать на большее я не могу. Какие варианты?

CUDA - ну это вроде NVidia SDК, вика показывает перечень поддерживаемых карт. Т.е. выходит нужно поддерживать текущий (медленный) "software вариант" ? Это заботы/груз

OpenCL - какой-то непонятный зверь. "Собирал" неск приложений где он задействован. Одно вообще висит, хотя device инициализиpуется успешно, пришлось OpenCL отключать. В др приложении вроде работает (радостно сообщает что "откомпилило" какой-то местный шейдер) но каков эффект - хз.

Из первого поста не сильно понятно как было сделано распараллеливание.
Хотя бы псевдокод посмотреть, с теми локами и конкурентным доступом к общим объектам.

Просто перед циклом вставляем

Код:

#pragma omp parallel for

Также проверялся QtConcurrent - ну там вообще мрачно. Также проверялось "ручное" разбиение (типа того что Вы предлагали). Локер не реализован вообще (пока не до него). Во всех случаях на 4 нитках тот же самый 1 fps. Профайлер показывает что да, все нитки задействованы, но в основном стоят на барьере.

PS: OMP параллелит далеко не всегда адекватно.

Интересно, можно больше подробностей?

Хотя в данном случае CPU не вызывает энтузиазма. Ну "вдвое" - это же очень мало, будет сцена/объект/итераций побольше, опять встанет тот же вопрос.

[RedDog]

Профайлер показывает что да, все нитки задействованы, но в основном стоят на барьере.

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

Интересно, можно больше подробностей?

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

[Igors]

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

Ну это фишка известная, здесь наоборот, кластер слишком велик, в рез-те все "ждут отстающего".  Бороться так

Код

C++ (Qt)
#pragma omp parallel for schedule(dynamic, 1)  // возможно др значение вместо 1

И задач "нарезать" не по числу ниток, а хотя бы вдвое больше

[m_ax]

Ну если задача не поддаётся такому явному распараллеливанию, то может имеет смысл пересмотреть стратегию..?
Как я понял, у вас каждый кадр ожидает функцию

Код

C++ (Qt)
CalcVerNormals
 

Может тогда имеет смысл распараллелить не то, что у неё под капотом находится, а просто сэт кадров?  

[Igors]

Может тогда имеет смысл распараллелить не то, что у неё под капотом находится, а просто сэт кадров?   

Разумно, примерно таким способом я часто выкручиваюсь (делать/скармливать задачи уровнем выше). К сожалению, это не всегда применимо. Напр в данном случае есть мужик (аттач) который машет руками и.т.п. Я могу его просчитать только для данного кадра (текущего времени), для следующего - все с нуля. Др словами "слишком велико чтобы выделить в задачу"

[m_ax]

Ну тогда извиняйте... Другого пути уже не найти.

[Авварон]

Что функция рассчетов то делает?
Может она весь кэш процессора вышибает? Есть тулзы (по памяти не скажу) которые профилируют промахи кэша.
Может размер итерации не подогнан под размер кэшей?
Ещё подумать в сторону векторных операций, раза в 4 могут ускорить

[ssoft]

Написал пример С++17. Ускорение есть какое-то в пару раз, но для поставленных амбициозных целей явно не подходит).
Возможно и ошибся где-то. А так-то, сразу тестовая программка сильно помогла бы вникнуть в вопрос.

[m_ax]

Что функция рассчетов то делает?
Может она весь кэш процессора вышибает? Есть тулзы (по памяти не скажу) которые профилируют промахи кэша.
Может размер итерации не подогнан под размер кэшей?
Ещё подумать в сторону векторных операций, раза в 4 могут ускорить

А можно поподробнее в сторону векторных операций? (сам просто сейчас занимаюсь вычислениями собственных значений и собственных векторов)