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

[__Heaven__]

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

И как сделать правильный выбор?

а вдруг сейчас ответят как мне понравится

Ну да. Я искал подтверждение моего недоверия Intel.

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

Ок. Расскажу, если удастся подключить либу.

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

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

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

Дело в том, что файлы создаются сторонней программой и их модифицировать нельзя. Чтение я выполняю в единственном потоке. Синтаксического анализа не требуется - файл бинарный. После чтения файла необходима обработка, которая приведёт данные в памяти к виду, где будут учитываться недостающие данные (такие как нормали).

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

[Igors]

.. где будут учитываться недостающие данные (такие как нормали).
..
Кстати, еще вопрос. Если в класс QMultiMap вносить новые значения, то его ведь нужно блокировать мьютексами, верно?

Верно-то верно, но боюсь это настолько увеличит накладные расходы что распараллеливание потеряет смысл. Сначала нужно навести порядок в задаче. Пока я вижу что вместо "разпоточивания" лучше заняться др делами. Не верю что полигонную нормаль нужно хранить в 3 экземплярах, не может такое решение быть удачным (какова бы ни была специфика "КЭ моделей"). Также QMultiMap точно 3D модели не подруга, от такой мапы надо избавляться. Словом "многопоточность" должна созреть

[__Heaven__]

навести порядок в задаче. Пока я вижу что вместо "разпоточивания" лучше заняться др делами. Не верю что полигонную нормаль нужно хранить в 3 экземплярах, не может такое решение быть удачным (какова бы ни была специфика "КЭ моделей"). Также QMultiMap точно 3D модели не подруга, от такой мапы надо избавляться. Словом "многопоточность" должна созреть

Нормаль необходимо хранить в 3х экземплярах. То есть, для каждой вершины, чтобы потом было удобно передавать в шейдеры при учёте освещения. Также по мере работы этот массив будет корректироваться для улучшения освещения.
QMultiMap необходим, чтобы описать узел конечно-элементной модели, то есть записать номера элементов, которые содержат данный узел. Глобальная идея: оперативно строить сечение детали.
Ну, у меня почти млн узлов и 4 млн элементов. Разве этого не достаточно для распараллеливания? На поверхности, где нужно высчитать нормали, лежит около 300000 треугольников, вроде.

[xokc]

Чтение я выполняю в единственном потоке.

Так если всё файл большой может лучше чтение "распараллелить"? Использовать асинхронное чтение и пока читается очередной кусок обрабатывать уже считанный. Правда тут Qt не помощник - QFile асинхронное чтение не поддерживает.

[__Heaven__]

Чтение я выполняю в единственном потоке.

Так если всё файл большой может лучше чтение "распараллелить"? Использовать асинхронное чтение и пока читается очередной кусок обрабатывать уже считанный. Правда тут Qt не помощник - QFile асинхронное чтение не поддерживает.

Не пойдет. Файл состоит примерно так: массив элементов, то есть 4 инта ссылающихся на номера узлов, далее массив принадлежности элементов к объемам. Далее массив узлов в виде xxxxxx…yyyyyy…zzzzzzz.
Тут только параллельно можно читать объемы, пока считаются нормали. Но это явно малоэффективно.

[Igors]

Чтобы воздух не гонять, опишите (кратко) что такое "узлы", "элементы" и "объемы", и чему они соответствуют в 3D

[m_ax]

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

Вы же понимаете, что тут всё от конкретной ситуации зависит.. Не зря же в OpenMP на этот случай есть возможность выбора стратегии для распараллеливания..  Если разброс по времени для задач не велик и сами задачи выполняются "достаточно быстро" (не буду здесь писать о том, когда наступает это "достаточно быстро") то этот вариант (когда задачи равномерно рапределяются между потоками) будет оптимален..

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

Ну и всё самое интересное, наверное, находится в промежуточном случае..

Я например, "вижу на глаз" в своей задаче этот эффект, когда приходиться ждать отстающих..
Надо допиливать parallel::transform.  

[Igors]

Нормаль необходимо хранить в 3х экземплярах. То есть, для каждой вершины, чтобы потом было удобно передавать в шейдеры при учёте освещения. Также по мере работы этот массив будет корректироваться для улучшения освещения.

Кстати, а не Вы ли (не так уж давно) весьма уверенно заявляли что никакое освещение для "КЭ моделей" не требуется? Теперь опять Вы вешаете мне лапшу на уши, как будто я первый день в 3D 

Расчет освещенности требует нормалей к вертексам. Эти нормали обычно создаются моделером и хранятся в файле. Если у Вас их нет - их надо посчитать на основании нормалей к полигонам. При этом задается "smooth angle" (часто 40 градусов). Если угол между смежными полигонами меньше заданного - оба полигона используют тот же вертекс, иначе разные.

Вместо этого Вы "расшариваете" всю модель, т.е. создаете каждому полигону "свои" вертексы. Это резко увеличивает объем данных, но способно создать только примитивный "flat" shading, т.е. грани/полигоны будут заметны, плавности нет.

Ну и зачем распараллеливать затычку которую рано или поздно придется снести?

[Igors]

Я например, "вижу на глаз" в своей задаче этот эффект, когда приходиться ждать отстающих..
Надо допиливать parallel::transform.  

Ну что сказать.. Это тот самый случай когда "велосипед неуместен" т.к. он будет и хуже и сложнее в сопровождении и все др (о чем Вы так любите говорить )

Разработать свой диспетчер конечно интересно, но это ничего особенного не даст, основная работа в др местах. Во-первых создавать/удалять нитки всякий раз = несерьезно, нужна бригада/пул который можно "спустить с цепи". Это не так уж сложно, но "легкость" теряется. Во-вторых, и главное - проблема останова. Я немного изучал как это делается в omp и tbb (intel). Там целая наука. Сначала просто выполняется какое-то число nop'ов, потом вставляется pause, только потом начинает вызываться yield и в конце-концов останов на "честном" мутексе. Масса ответвлений для конкретных процессоров и для 32/64. Повторить всю эту огромную (и совершенно рутинную) работу нереально, да и зачем?

Вместо общих задач займитесь частными, вот там велосипед будет необходим 

[__Heaven__]

Нормаль необходимо хранить в 3х экземплярах. То есть, для каждой вершины, чтобы потом было удобно передавать в шейдеры при учёте освещения. Также по мере работы этот массив будет корректироваться для улучшения освещения.

Кстати, а не Вы ли (не так уж давно) весьма уверенно заявляли что никакое освещение для "КЭ моделей" не требуется? Теперь опять Вы вешаете мне лапшу на уши, как будто я первый день в 3D 

Да я и до сих пор считаю, что освещение не требуется. Что это только вносит "ошибки" в отображение результатов (см. аттач). Как видно из рисунка слева, где отключено освещение показано реальное распределение температур, а справа, где имеется освещение, деталь местами горячее (визуально).

Чтобы воздух не гонять, опишите (кратко) что такое "узлы", "элементы" и "объемы", и чему они соответствуют в 3D

Узлы - грубо говоря, точки или вершины элементов. Узлы имеют координаты в пространстве и индекс (грубо говоря порядковый номер).
Элементы (в моем случае именно тетраэдры) - набор из 4 узлов, также имеют свой индекс.
Объём - замкнутое скопление элементов, которое логически описывает какую-то часть задачи. (материал, деталь и т.д.).
Коллектор - коллекция объёмов.
В аттаче мы имеем 1 объём.

Я понял, что при выборе между атомщиками и методом, что предложил Old нужно ориентироваться следующим образом. Если у нас итерация выполняется медленно, то лучше использовать атомщиков, иначе делить задачу на равные части.

[__Heaven__]

Аттач

[Igors]

Узлы - грубо говоря, точки или вершины элементов. Узлы имеют координаты в пространстве и индекс (грубо говоря порядковый номер).
Элементы (в моем случае именно тетраэдры) - набор из 4 узлов, также имеют свой индекс.
Объём - замкнутое скопление элементов, которое логически описывает какую-то часть задачи. (материал, деталь и т.д.).
Коллектор - коллекция объёмов.
В аттаче мы имеем 1 объём.

В стандартных терминах

Узлы - вертексы
Элемент - полигон
Элемент из 4 узлов - квадрангл (quadrangle/quad)
Объем - объект
замкнутое скопление - солид (solid object)

А как у Вас задается полигон? Обычно он хранит не сами вертексы, а их индексы, напр (0, 1, 2, 3). Один и тот же вертекс может входить в разные полигоны, напр др полигон (5, 6, 3, 2).

[__Heaven__]

А как у Вас задается полигон? Обычно он хранит не сами вертексы, а их индексы, напр (0, 1, 2, 3). Один и тот же вертекс может входить в разные полигоны, напр др полигон (5, 6, 3, 2).

Из-за специфики файла я задаю полигоны в виде вектора вершин и индексы не использую. То есть получается float [] = xyzxyzxyzxyzxyzxyzxyzxyzxyzxyzxyzxyz...

[__Heaven__]

Столкнулся с трудностями:

Код

C++ (Qt)
    const int nVolumes = volumeShells.size();
    const int nThreads = QThread::idealThreadCount() - 1;
 
    QThread** threads = new QThread* [nThreads];
    NormalSolver** solvers = new NormalSolver* [nThreads + 1];
 
    for (int i = 0; i < nThreads; ++i)
    {
        (solvers[i] = new NormalSolver)->moveToThread(threads[i] = new QThread(this));
        qDebug() << connect(threads[i], SIGNAL(started()), solvers[i], SLOT(run()));
    }
    solvers[nThreads] = new NormalSolver;
 
    volumeShellNormals.resize(nVolumes);
 
    for (int i = 0; i < nVolumes; ++i) // для каждого объёма
    {
        int nVertices = volumeShells.at(i).size();
        int nTriangles = nVertices / 3;
        int trianglesPerThread = nTriangles / (nThreads + 1);
 
        volumeShellNormals[i].resize(nVertices);
 
        const float* data = volumeShells.at(i).constData();
        float* dest = volumeShellNormals[i].data();
 
        for (int j = 0; j < nThreads; ++j)
        {
            const float* begin = data + j * trianglesPerThread,
                       * end = begin + trianglesPerThread;
            solvers[i]->setSrc(begin, end);
            solvers[i]->setDst(dest + j * trianglesPerThread);
            threads[i]->start();
        }
 
        solvers[nThreads]->setSrc(data + nThreads * trianglesPerThread, data + nVertices);
        solvers[nThreads]->setDst(dest + nThreads * trianglesPerThread);
        solvers[nThreads]->run();
 
        for (int j = 0; j < nThreads; ++j)
            threads[j]->wait();
    }
 
    for (int i = 0; i < nThreads; ++i)
    {
        delete solvers[i];
        delete threads[i];
    }
    delete solvers[nThreads];
    delete[] solvers;
    delete[] threads;
 

1) не понимаю, почему я не могу использовать QVector классов унаследованных от QObject и обращаться к ним по []
2) Нитки не стартуют

[Igors]

1) не понимаю, почему я не могу использовать QVector классов унаследованных от QObject и обращаться к ним по []

Потому что вектор (или др контейнер) требует конструктор копирования.

Из-за специфики файла я задаю полигоны в виде вектора вершин и индексы не использую. То есть получается float [] = xyzxyzxyzxyzxyzxyzxyzxyzxyzxyzxyzxyz...

Вы совершенно напрасно "велосипедите", так Вы раздуваете данные и создаете себе ненужные проблемы. Ладно, дело Ваше, больше вопросами мучить не буду