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

[__Heaven__]

Этот же нетбук но уже win

Normals calculated with 1 thread in  31  ms
Normals calculated with multithreading in  25  ms
Normals calculated with 1 thread in  32  ms
Normals calculated with multithreading in  22  ms
Normals calculated with 1 thread in  28  ms
Normals calculated with multithreading in  22  ms
Normals calculated with 1 thread in  28  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  28  ms
Normals calculated with multithreading in  21  ms
Normals calculated with 1 thread in  28  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  28  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  28  ms
Normals calculated with multithreading in  21  ms
Normals calculated with 1 thread in  28  ms
Normals calculated with multithreading in  21  ms
Normals calculated with 1 thread in  29  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  28  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  29  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  29  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  27  ms
Normals calculated with multithreading in  21  ms
Normals calculated with 1 thread in  28  ms
Normals calculated with multithreading in  22  ms
Normals calculated with 1 thread in  28  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  29  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  28  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  28  ms
Normals calculated with multithreading in  21  ms
Normals calculated with 1 thread in  28  ms
Normals calculated with multithreading in  21  ms
Normals calculated with 1 thread in  27  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  28  ms
Normals calculated with multithreading in  21  ms
Normals calculated with 1 thread in  28  ms
Normals calculated with multithreading in  21  ms
Normals calculated with 1 thread in  28  ms
Normals calculated with multithreading in  21  ms
Normals calculated with 1 thread in  28  ms
Normals calculated with multithreading in  22  ms

[Igors]

Ну для начала - очень неплохо. КПД конечно "оставляет желать лучшего", но на такой задаче трудно что-то выжать. Можно поиграться с диспетчером, напр

Код

C++ (Qt)
// размер "порции" 10К 
#pragma omp parallel for schedule(dynamic, 10000) 

[__Heaven__]

Всё это очень круто. Спасибо, что научили.
Но ещё осталось пару вопросов.
Где можно найти описание этой игрушки да такое, чтобы было простым и быстро учило? Пока что нашёл только официальную версию.
По какому принципу идёт распараллеливание?

[Old]

Где можно найти описание этой игрушки да такое, чтобы было простым и быстро учило? Пока что нашёл только официальную версию.

Например здесь:
https://parallel.ru/tech/tech_dev/openmp.html
https://software.intel.com/ru-ru/articles/getting-started-with-openmp

В сети много информации.

[__Heaven__]

Где можно найти описание этой игрушки да такое, чтобы было простым и быстро учило? Пока что нашёл только официальную версию.

Например здесь:
https://parallel.ru/tech/tech_dev/openmp.html
https://software.intel.com/ru-ru/articles/getting-started-with-openmp

В сети много информации.

Спасибо.

Чуть не оставил без внимания MSVC 2013 x64. Те же 4 ядра:

Normals calculated with 1 thread in  17  ms
Normals calculated with multithreading in  38  ms
Normals calculated with 1 thread in  21  ms
Normals calculated with multithreading in  80  ms
Normals calculated with 1 thread in  20  ms
Normals calculated with multithreading in  16  ms
Normals calculated with 1 thread in  21  ms
Normals calculated with multithreading in  16  ms
Normals calculated with 1 thread in  15  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  21  ms
Normals calculated with multithreading in  62  ms
Normals calculated with 1 thread in  16  ms
Normals calculated with multithreading in  13  ms
Normals calculated with 1 thread in  15  ms
Normals calculated with multithreading in  30  ms
Normals calculated with 1 thread in  15  ms
Normals calculated with multithreading in  41  ms
Normals calculated with 1 thread in  17  ms
Normals calculated with multithreading in  32  ms
Normals calculated with 1 thread in  15  ms
Normals calculated with multithreading in  19  ms
Normals calculated with 1 thread in  23  ms
Normals calculated with multithreading in  67  ms
Normals calculated with 1 thread in  24  ms
Normals calculated with multithreading in  72  ms
Normals calculated with 1 thread in  15  ms
Normals calculated with multithreading in  16  ms
Normals calculated with 1 thread in  21  ms
Normals calculated with multithreading in  14  ms
Normals calculated with 1 thread in  21  ms
Normals calculated with multithreading in  19  ms
Normals calculated with 1 thread in  15  ms
Normals calculated with multithreading in  21  ms
Normals calculated with 1 thread in  15  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  15  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  15  ms
Normals calculated with multithreading in  16  ms
Normals calculated with 1 thread in  16  ms
Normals calculated with multithreading in  17  ms
Normals calculated with 1 thread in  15  ms
Normals calculated with multithreading in  17  ms
Normals calculated with 1 thread in  15  ms
Normals calculated with multithreading in  36  ms
Normals calculated with 1 thread in  15  ms
Normals calculated with multithreading in  16  ms
Normals calculated with 1 thread in  17  ms
Normals calculated with multithreading in  16  ms

[Igors]

Можете попробовать intel реализацию - для мелких задач она дает гораздо больший КПД

[__Heaven__]

Да, и кстати не надо полагать что memcpy - самое быстрое (напр в данном случае это не так).

Расходуем ресурсы на вызов вместо быстрого прямого копирования?

[Igors]

Расходуем ресурсы на вызов вместо быстрого прямого копирования?

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

[__Heaven__]

Расходуем ресурсы на вызов вместо быстрого прямого копирования?

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

Пока психологически не перебороть. Причём никогда не программировал на си. Начал с c++ в msvs2008.
Когда я так записываю, мне кажется, что у меня всё будет летать, в отличии если я запишу понятным для себя языком.

[xokc]

Осталось ipp попробовать, подозреваю сильно будете удивлены. Особенно если и память для этих векторов выделить с помощью ippMalloc и, главное, найти подходящую по смыслу функцию, например ippmNormalize_v3_32f (не уверен, что это именно она!). Оно будет для каждого из используемых типов CPU использовать свой набор векторных команд. Впрочем, оптимизировать функцию, "из коробки" выполняющуюся за 20 ms на мой взгляд не очень правильно.

[__Heaven__]

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

Моей ошибкой было то, что это изначально была не оптимизация. То есть я изначально не замерил скорость выполнения при использовании скалярного решения.
Мне казалось, что на слабом оборудовании (как мой нетбук) это действие займет до 2-3 сек.

[Igors]

Моей ошибкой было то, что это изначально была не оптимизация. То есть я изначально не замерил скорость выполнения при использовании скалярного решения.
Мне казалось, что на слабом оборудовании (как мой нетбук) это действие займет до 2-3 сек.

Под "скалярным" подразумевается "без использования векторных команд" (SSE и др), multi-threading здесь ни при чем.

[__Heaven__]

Вот ещё задача.
Глобальная цель - взять большую кучу тетраэдров (описывает деталь) и оперативно построить сечение по ним. Строить планирую по такому принципу: У меня имеется оболочка из треугольников, которая описывает видимые грани тетраэдров, которые лежат на поверхности кучи (то есть грани, которые не соприкасаются с другими элементами). Путём перебора я найду треугольник, вершины которого лежат по разные стороны сечения. Мне известна связь оболочковых треугольников с тетраэдрами - получается я найду элемент (тетраэдр), который рассекает сечение. После этого я хочу взять каждый узел этого элемента и посмотреть, какие ещё элементы принадлежат этим узлам. Если найденные элементы будут в плоскости сечения, то их записываем. И так до тех пор, пока не найдём все элементы, проходящие через сечение.
Для достижения этой цели необходимо решить задачу:
Дано:
Массив элементов (тетраэдров). Записан в виде n1, n2, n3, n4, n1, n2, n3, n5, n2, n3, n4, n6... То есть, 1 элемент это 4 идущих подряд значения. n1, n2 - номера узлов.
Также есть массив принадлежности элементов к объёмам. Записан в виде v1, v1, v1,...., v2, v2... То есть на каждые 4 n приходится 1 v.
Необходимо для каждого номера узла записать номера элементов, в которых тот участвует. Помимо этого разнести результаты по объемам.

Вот код, который я написал:

Код

C++ (Qt)
    int nVolumes = volumeShells.size(); // количество объёмов
    nodeElemsMap.clear();
    nodeElemsMap.resize(nVolumes);
 
    QMultiMap<int, int>* maps = nodeElemsMap.data();
    const int* pVolumeDepend = volumeDepend.constData(),
             * pElems = elems.constData();
 
    for (int i = 0; i < volumeDepend.size(); ++i)
        for (int j = i * 4; j < (i + 1) * 4; ++j)
            maps[pVolumeDepend[i]].insert(pElems[j], i);
 

Но он работает очень медленно. Я загрузил геометрию на 915316 узлов и 4611335 элементов. Словарь обсчитывался 10 секунд. Можно ли что-то придумать, чтобы сократить время хотя-бы до секунды?

[Igors]

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

1) Пробегаетесь по всем вертексам, для каждого вычисляете лежит он слева или справа от плоскости. Записываете это в vector<char>. Время этой пробежки даже меньше чем вычисления нормалей

2) По каждому тетраэдру - если его вертексы лежат по разные стороны (vector<char>), то он пересекается секущей плоскостью. Время еще меньше чем "1"

[__Heaven__]

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

1) Пробегаетесь по всем вертексам, для каждого вычисляете лежит он слева или справа от плоскости. Записываете это в vector<char>. Время этой пробежки даже меньше чем вычисления нормалей

2) По каждому тетраэдру - если его вертексы лежат по разные стороны (vector<char>), то он пересекается секущей плоскостью. Время еще меньше чем "1"

Да. я уже тоже подумал об этом. сейчас кодирую - измерять буду