Russian Qt Forum

Qt => Многопоточное программирование, процессы => Тема начата: __Heaven__ от Ноябрь 29, 2014, 13:49



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

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


Название: Re: Многопоточная обработка массива
Отправлено: Old от Ноябрь 29, 2014, 13:56
Пока что гляжу в сторону QAtomicInt, но понятия не имею, как это всё реализуется.
Не представляю куда это там применить, если все координаты скорее всего представлены числами с плавающей запятой.

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


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Ноябрь 29, 2014, 14:07
Самое простое разбить весь массив на регионы и каждый регион отдать отдельной нитке.
То есть, нужно объявить класс, который принимает диапазон из вектора. Объявить таких 4 класса, передвинуть их в 4 нитки стартануть и дождаться выполнения. Верно?


Название: Re: Многопоточная обработка массива
Отправлено: Old от Ноябрь 29, 2014, 15:25
То есть, нужно объявить класс, который принимает диапазон из вектора. Объявить таких 4 класса, передвинуть их в 4 нитки стартануть и дождаться выполнения. Верно?
Не обязательно класс, это может быть функция, принимающая диапазон в качестве параметра. И эту функцию можно запустить в нескольких потоках, каждую со своим диапазоном.


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Ноябрь 29, 2014, 16:15
Вы намекаете на 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 нитки?


Название: Re: Многопоточная обработка массива
Отправлено: m_ax от Ноябрь 29, 2014, 16:18
Вы намекаете на 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, если я правильно понял..


Название: Re: Многопоточная обработка массива
Отправлено: Old от Ноябрь 29, 2014, 16:21
QtConcurrent::run один из вариантов, можно использовать std::thread. Да и класс для этого можно сделать.
Вы можете вызвать QtConcurrent::run сколько нужно раз, если на все задачи не хватит потоков, задачи станут в очередь и будут выполняться по мере освобождения рабочих нитей.


Название: Re: Многопоточная обработка массива
Отправлено: Old от Ноябрь 29, 2014, 16:24
Похоже вам нужна параллельный вариант std::transform, если я правильно понял..
Кстати да, в разделе готовых решений есть тема от m_ax про параллельный трансформ, посмотрите готовую реализацию и обсуждение.


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Ноябрь 29, 2014, 16:28
QtConcurrent::run один из вариантов, можно использовать std::thread. Да и класс для этого можно сделать.
Вы можете вызвать QtConcurrent::run сколько нужно раз, если на все задачи не хватит потоков, задачи станут в очередь и будут выполняться по мере освобождения рабочих нитей.

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


Название: Re: Многопоточная обработка массива
Отправлено: Old от Ноябрь 29, 2014, 16:37
У QtConcurrent под капотом пул поток QThreadPool. Почитайте сразу и про него. :)


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Ноябрь 29, 2014, 16:54
Не очень удачная задача - вычисление нормали слишком быстрая операция чтобы получить ощутимый эффект от распараллеливания. В любом случае нужен инструментарий, вариантов много 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);
}
}
 
Так можно обойтись без передачи индексов т.к. атомик гарантирует что каждый будет получен только один раз.


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


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Ноябрь 30, 2014, 00:11
Атомики могут использоваться для нахождения индекса, напр
а при их использовании процессы ведь начнут душить друг друга?
Соглашусь. Для таких задач проще инструмента не найти. И опять же соглашусь, что для того, чтобы ощутить эффект от распараллеливания для этого алгоритма нужно обсчитывать ну ООООЧЧЧЧЕЕЕННЬ длинные массивы. Тут скорее спасёт что-нибудь типа Intel IPP library, способное использовать SSE команды процессора.
меня интересует не только ускорение этого участка, но также и другие части функции открытия файла. Хочу, чтобы большие объёмы обрабатывались очень быстро.
Какой размер для вас оооооччччеееннь большой?
А опциями компилятора нельзя получить эффета SSE? Кстати, я слышал, что интеловские библиотеки могут подтормаживать выполнение вместо ускорения.
Вижу, что OpenMP имеет преимущества в плане простоты написания. Как насчёт скорости?
Почему OpenMP, а не OpenCL?


Название: Re: Многопоточная обработка массива
Отправлено: xokc от Ноябрь 30, 2014, 11:33
Какой размер для вас оооооччччеееннь большой?
Такой, что выгода от его многопоточной обработки превысит накладные расходы на создание/удаление/синхронизацию потоков.
Также будет зависеть от типа процессора, количества ядер и, загруженности ОС в момент обработки массива и т.п. Проще определить экспериментально. Попробуйте, например, с и без OpenMP, заодно и нам расскажите.

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

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

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

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


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

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

А опциями компилятора нельзя получить эффета SSE?
Типа "спрошу-ка еще раз то же самое - а вдруг сейчас ответят как мне понравится". Ничего не напоминает?  :)


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Ноябрь 30, 2014, 13:09
В какой-то мере да, но накладные расходы есть всегда, и часто они значительны. .... Придется "ждать отстающих"
И как сделать правильный выбор?
а вдруг сейчас ответят как мне понравится
Ну да. Я искал подтверждение моего недоверия Intel.
Такой, что выгода от его многопоточной обработки превысит накладные расходы на создание/удаление/синхронизацию потоков.
Также будет зависеть от типа процессора, количества ядер и, загруженности ОС в момент обработки массива и т.п. Проще определить экспериментально. Попробуйте, например, с и без OpenMP, заодно и нам расскажите.
Ок. Расскажу, если удастся подключить либу.
Похоже вам нужна параллельный вариант std::transform, если я правильно понял..
Боюсь, что мне пока что не хватает опыта задействовать этот вариант. Ваш код понял только через строчку. Но, наверное, спустя какое-то время, вернусь к нему.
Чтение/загрузка - не те места где распараллеливание эффективно, т.к. все упирается в I/O. Здесь обычно ускоряются на синтаксическом разборе
Дело в том, что файлы создаются сторонней программой и их модифицировать нельзя. Чтение я выполняю в единственном потоке. Синтаксического анализа не требуется - файл бинарный. После чтения файла необходима обработка, которая приведёт данные в памяти к виду, где будут учитываться недостающие данные (такие как нормали).

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


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Ноябрь 30, 2014, 14:03
.. где будут учитываться недостающие данные (такие как нормали).
..
Кстати, еще вопрос. Если в класс QMultiMap вносить новые значения, то его ведь нужно блокировать мьютексами, верно?
Верно-то верно, но боюсь это настолько увеличит накладные расходы что распараллеливание потеряет смысл. Сначала нужно навести порядок в задаче. Пока я вижу что вместо "разпоточивания" лучше заняться др делами. Не верю что полигонную нормаль нужно хранить в 3 экземплярах, не может такое решение быть удачным (какова бы ни была специфика "КЭ моделей"). Также QMultiMap точно 3D модели не подруга, от такой мапы надо избавляться. Словом "многопоточность" должна созреть


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Ноябрь 30, 2014, 16:13
навести порядок в задаче. Пока я вижу что вместо "разпоточивания" лучше заняться др делами. Не верю что полигонную нормаль нужно хранить в 3 экземплярах, не может такое решение быть удачным (какова бы ни была специфика "КЭ моделей"). Также QMultiMap точно 3D модели не подруга, от такой мапы надо избавляться. Словом "многопоточность" должна созреть
Нормаль необходимо хранить в 3х экземплярах. То есть, для каждой вершины, чтобы потом было удобно передавать в шейдеры при учёте освещения. Также по мере работы этот массив будет корректироваться для улучшения освещения.
QMultiMap необходим, чтобы описать узел конечно-элементной модели, то есть записать номера элементов, которые содержат данный узел. Глобальная идея: оперативно строить сечение детали.
Ну, у меня почти млн узлов и 4 млн элементов. Разве этого не достаточно для распараллеливания? На поверхности, где нужно высчитать нормали, лежит около 300000 треугольников, вроде.


Название: Re: Многопоточная обработка массива
Отправлено: xokc от Ноябрь 30, 2014, 16:48
Чтение я выполняю в единственном потоке.
Так если всё файл большой может лучше чтение "распараллелить"? Использовать асинхронное чтение и пока читается очередной кусок обрабатывать уже считанный. Правда тут Qt не помощник - QFile асинхронное чтение не поддерживает.


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Ноябрь 30, 2014, 17:25
Чтение я выполняю в единственном потоке.
Так если всё файл большой может лучше чтение "распараллелить"? Использовать асинхронное чтение и пока читается очередной кусок обрабатывать уже считанный. Правда тут Qt не помощник - QFile асинхронное чтение не поддерживает.
Не пойдет. Файл состоит примерно так: массив элементов, то есть 4 инта ссылающихся на номера узлов, далее массив принадлежности элементов к объемам. Далее массив узлов в виде xxxxxx…yyyyyy…zzzzzzz.
Тут только параллельно можно читать объемы, пока считаются нормали. Но это явно малоэффективно.


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Ноябрь 30, 2014, 17:35
Чтобы воздух не гонять, опишите (кратко) что такое "узлы", "элементы" и "объемы", и чему они соответствуют в 3D


Название: Re: Многопоточная обработка массива
Отправлено: m_ax от Ноябрь 30, 2014, 17:47
В какой-то мере да, но накладные расходы есть всегда, и часто они значительны. Пример: дали каждой нитке свою часть индексов. Напр 1-я получает [0..100], вторая [100..200] и.т.д. Казалось бы, это идеальный вариант, никто никого не душит. Но тут др беда - загруженность у ниток разная, напр 1-я уже посчитала все 100, а 2-я только 10. Придется "ждать отстающих"
Вы же понимаете, что тут всё от конкретной ситуации зависит.. Не зря же в OpenMP на этот случай есть возможность выбора стратегии для распараллеливания..  Если разброс по времени для задач не велик и сами задачи выполняются "достаточно быстро" (не буду здесь писать о том, когда наступает это "достаточно быстро") то этот вариант (когда задачи равномерно рапределяются между потоками) будет оптимален..

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

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

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


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Декабрь 01, 2014, 08:28
Нормаль необходимо хранить в 3х экземплярах. То есть, для каждой вершины, чтобы потом было удобно передавать в шейдеры при учёте освещения. Также по мере работы этот массив будет корректироваться для улучшения освещения.
Кстати, а не Вы ли (не так уж давно) весьма уверенно заявляли что никакое освещение для "КЭ моделей" не требуется? :) Теперь опять Вы вешаете мне лапшу на уши, как будто я первый день в 3D  :)

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

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

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


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Декабрь 01, 2014, 08:57
Я например, "вижу на глаз" в своей задаче этот эффект, когда приходиться ждать отстающих..
Надо допиливать parallel::transform.  
Ну что сказать.. Это тот самый случай когда "велосипед неуместен" т.к. он будет и хуже и сложнее в сопровождении и все др (о чем Вы так любите говорить :))

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

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


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 01, 2014, 11:22
Нормаль необходимо хранить в 3х экземплярах. То есть, для каждой вершины, чтобы потом было удобно передавать в шейдеры при учёте освещения. Также по мере работы этот массив будет корректироваться для улучшения освещения.
Кстати, а не Вы ли (не так уж давно) весьма уверенно заявляли что никакое освещение для "КЭ моделей" не требуется? :) Теперь опять Вы вешаете мне лапшу на уши, как будто я первый день в 3D  :)
Да я и до сих пор считаю, что освещение не требуется. Что это только вносит "ошибки" в отображение результатов (см. аттач). Как видно из рисунка слева, где отключено освещение показано реальное распределение температур, а справа, где имеется освещение, деталь местами горячее (визуально).
Чтобы воздух не гонять, опишите (кратко) что такое "узлы", "элементы" и "объемы", и чему они соответствуют в 3D
Узлы - грубо говоря, точки или вершины элементов. Узлы имеют координаты в пространстве и индекс (грубо говоря порядковый номер).
Элементы (в моем случае именно тетраэдры) - набор из 4 узлов, также имеют свой индекс.
Объём - замкнутое скопление элементов, которое логически описывает какую-то часть задачи. (материал, деталь и т.д.).
Коллектор - коллекция объёмов.
В аттаче мы имеем 1 объём.

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


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 01, 2014, 11:25
Аттач
(http://i9.pixs.ru/storage/8/8/6/Untitledpn_6520536_14963886.png)


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Декабрь 01, 2014, 12:54
Узлы - грубо говоря, точки или вершины элементов. Узлы имеют координаты в пространстве и индекс (грубо говоря порядковый номер).
Элементы (в моем случае именно тетраэдры) - набор из 4 узлов, также имеют свой индекс.
Объём - замкнутое скопление элементов, которое логически описывает какую-то часть задачи. (материал, деталь и т.д.).
Коллектор - коллекция объёмов.
В аттаче мы имеем 1 объём.
В стандартных терминах

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

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


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 01, 2014, 13:25
А как у Вас задается полигон? Обычно он хранит не сами вертексы, а их индексы, напр (0, 1, 2, 3). Один и тот же вертекс может входить в разные полигоны, напр др полигон (5, 6, 3, 2).
Из-за специфики файла я задаю полигоны в виде вектора вершин и индексы не использую. То есть получается float [] = xyzxyzxyzxyzxyzxyzxyzxyzxyzxyzxyzxyz...


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 01, 2014, 13:34
Столкнулся с трудностями:
Код
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) Нитки не стартуют


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Декабрь 01, 2014, 14:35
1) не понимаю, почему я не могу использовать QVector классов унаследованных от QObject и обращаться к ним по []
Потому что вектор (или др контейнер) требует конструктор копирования.

Из-за специфики файла я задаю полигоны в виде вектора вершин и индексы не использую. То есть получается float [] = xyzxyzxyzxyzxyzxyzxyzxyzxyzxyzxyzxyz...
Вы совершенно напрасно "велосипедите", так Вы раздуваете данные и создаете себе ненужные проблемы. Ладно, дело Ваше, больше вопросами мучить не буду  :)


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 01, 2014, 15:03
Элемент из 4 узлов - квадрангл (quadrangle/quad)
Нет. Тетраэдр. Вы же пишете о двумерном четырёхугольнике.
Потому что вектор (или др контейнер) требует конструктор копирования.
Спасибо. Ни разу не сталкивался до сих пор.


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 01, 2014, 16:53
Мда... Замерил скорость поиска нормалей с использованием одной нитки - получил 21. Причём на нетбуке
И опять же соглашусь, что для того, чтобы ощутить эффект от распараллеливания для этого алгоритма нужно обсчитывать ну ООООЧЧЧЧЕЕЕННЬ длинные массивы.
Я думал, что у меня такой массив.


Название: Re: Многопоточная обработка массива
Отправлено: xokc от Декабрь 01, 2014, 18:59
Добавьте OpenMP макрос перед циклом из примера от Igors, запустите на чем-нибудь многоядерном и сравните результаты. Интересно же!


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 02, 2014, 10:16
Добавьте OpenMP макрос перед циклом из примера от Igors, запустите на чем-нибудь многоядерном и сравните результаты. Интересно же!
Хорошо. Только для этого мне потребуется помощь.
Я так понял, что у меня на машине установлен уже omp, подключение сделал подобно этому
В свойствах проекта нужно дописать (там, где QMake build arguments)

"QMAKE_LIBS+=-static -lgomp -lpthread" "QMAKE_CXXFLAGS+=-msse3 -fopenmp" QMAKE_CXXFLAGS+=-U_WIN32

Только почему-то у меня при вызове omp_get_num_threads() и вообще любых OpenMP функций не из main, а из потока QThread программа выпадает с ошибкой Segmentation Fault.

Нынешняя функция выглядит таким образом:
Код
C++ (Qt)
   while (src != srcEnd)
   {
       // присваиваем временные имена
       const float& x0 = *(src++);
       const float& y0 = *(src++);
       const float& z0 = *(src++);
 
       const float& x1 = *(src++);
       const float& y1 = *(src++);
       const float& z1 = *(src++);
 
       const float& x2 = *(src++);
       const float& y2 = *(src++);
       const float& z2 = *(src++);
 
       // вычисляем векторы
       float a[3] = {x1 - x0, y1 - y0, z1 - z0},
             b[3] = {x2 - x0, y2 - y0, z2 - z0};
 
       const int x = 0,
                 y = 1,
                 z = 2;
       // вычисление и запись перпендикуляра
       *dest = a[y] * b[z] - a[z] * b[y];
       dest[1] = a[z] * b[x] - a[x] * b[z];
       dest[2] = a[x] * b[y] - a[y] * b[x];
 
       // вычисление длины и нормализация
       float inv_length = 1.0 / sqrt(*dest * *dest +
                                     dest[y] * dest[y] +
                                     dest[z] * dest[z]);
       *dest *= inv_length;
       dest[y] *= inv_length;
       dest[z] *= inv_length;
 
       // копирование во все вершины
       memcpy(dest + 3, dest, 3 * sizeof(float));
       memcpy(dest + 6, dest, 3 * sizeof(float));
 
       dest += 9;
   }
 
Что и куда добавлять?


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Декабрь 02, 2014, 11:42
Что и куда добавлять?
Пока ничего, сначала поработать с исходным кодом. Если нет желания сделать свой класс (напр Vec3f), то использовать хотя бы QVector3D. Он конечно сделан хреновенько, но все ж лучше чем всякий раз так пыль глотать. Напр

Код
C++ (Qt)
void CalcNormals( const float * srcF, int numF, float * dstF )
{
const QVector3D * src = (QVector3D *) srcF;
QVector3D * dst = (QVector3D *) dstF;
int N = numF / 3 / 3;
 
// #pragma omp parallel for
for (int i = 0; i < N; ++i) {
  int j = i * 3;
  dst[j] = dst[j + 1] = dst[j + 2] = QVector3D::crossProduct(src[j + 1] - src[j], src[j + 2] - src[j]).normalize();
}
}


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 02, 2014, 12:27
Всё равно сделал по-своему (лень).
Параллельная задача
Код
C++ (Qt)
   int times = (srcEnd - src) / sizeof(float) / 9;
   #pragma omp parallel for
   for(int i = 0; i < times; i++)
   {
       // присваиваем временные имена
       int j = i * 9;
       const float& x0 = src[j];
       const float& y0 = src[j + 1];
       const float& z0 = src[j + 2];
 
       const float& x1 = src[j + 3];
       const float& y1 = src[j + 4];
       const float& z1 = src[j + 5];
 
       const float& x2 = src[j + 6];
       const float& y2 = src[j + 7];
       const float& z2 = src[j + 8];
 
       // вычисляем векторы
       float a[3] = {x1 - x0, y1 - y0, z1 - z0},
             b[3] = {x2 - x0, y2 - y0, z2 - z0};
 
       const int x = 0,
                 y = 1,
                 z = 2;
       // вычисление и запись перпендикуляра
       float& xNorm = dest[j] = a[y] * b[z] - a[z] * b[y];
       float& yNorm = dest[j + 1] = a[z] * b[x] - a[x] * b[z];
       float& zNorm = dest[j + 2] = a[x] * b[y] - a[y] * b[x];
 
       // вычисление длины и нормализация
       float inv_length = 1.0 / sqrt(xNorm * xNorm +
                                     yNorm * yNorm +
                                     zNorm * zNorm);
       xNorm *= inv_length;
       yNorm *= inv_length;
       zNorm *= inv_length;
 
       // копирование во все вершины
       memcpy(&xNorm + 3, &xNorm, 3 * sizeof(float));
       memcpy(&xNorm + 6, &xNorm, 3 * sizeof(float));
 
   }
 
Против однопоточной
Код
C++ (Qt)
   while (src != srcEnd)
   {
       // присваиваем временные имена
       const float& x0 = *(src++);
       const float& y0 = *(src++);
       const float& z0 = *(src++);
 
       const float& x1 = *(src++);
       const float& y1 = *(src++);
       const float& z1 = *(src++);
 
       const float& x2 = *(src++);
       const float& y2 = *(src++);
       const float& z2 = *(src++);
 
       // вычисляем векторы
       float a[3] = {x1 - x0, y1 - y0, z1 - z0},
             b[3] = {x2 - x0, y2 - y0, z2 - z0};
 
       const int x = 0,
                 y = 1,
                 z = 2;
       // вычисление и запись перпендикуляра
       *dest = a[y] * b[z] - a[z] * b[y];
       dest[1] = a[z] * b[x] - a[x] * b[z];
       dest[2] = a[x] * b[y] - a[y] * b[x];
 
       // вычисление длины и нормализация
       float inv_length = 1.0 / sqrt(*dest * *dest +
                                     dest[y] * dest[y] +
                                     dest[z] * dest[z]);
       *dest *= inv_length;
       dest[y] *= inv_length;
       dest[z] *= inv_length;
 
       // копирование во все вершины
       memcpy(dest + 3, dest, 3 * sizeof(float));
       memcpy(dest + 6, dest, 3 * sizeof(float));
 
       dest += 9;
   }
 
Результат достаточно интересный. Ответ на вопрос примерно могу сформулировать, но спрошу знающих. Что у нас происходит на первом цикле, что параллельное вычисление слабее скалярного?
Цитировать
Normals calculated with 1 thread in  14  ms
Normals calculated with multithreading in  27  ms
Normals calculated with 1 thread in  13  ms
Normals calculated with multithreading in  8  ms
Normals calculated with 1 thread in  14  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  13  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  13  ms
Normals calculated with multithreading in  6  ms
Normals calculated with 1 thread in  13  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  13  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  13  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  14  ms
Normals calculated with multithreading in  6  ms
Normals calculated with 1 thread in  13  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  13  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  14  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  13  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  13  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  13  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  14  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  13  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  14  ms
Normals calculated with multithreading Qin  7  ms
Normals calculated with 1 thread in  15  ms
Normals calculated with multithreading in  6  ms
Normals calculated with 1 thread in  14  ms
Normals calculated with multithreading in  8  ms
Normals calculated with 1 thread in  14  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  13  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  13  ms
Normals calculated with multithreading in  8  ms
Normals calculated with 1 thread in  14  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  14  ms
Normals calculated with multithreading in  7  ms


Название: Re: Многопоточная обработка массива
Отправлено: Old от Декабрь 02, 2014, 12:31
Запускает рабочие потоки.


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 02, 2014, 12:46
На линуксе пишет
cannot find -lQt5OpenGL
                -lQt5Widgets
и т.д.
В чём дело?
При выключении omp всё работает и результаты работы второго алгоритма оказались  быстрее первого. Нужно перезамерить.


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 02, 2014, 12:48
результаты работы второго алгоритма оказались  быстрее первого. Нужно перезамерить.
Код:
Normals calculated with 1 thread in  7  ms
Normals calculated with multithreading in  28  ms
Normals calculated with 1 thread in  7  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  6  ms
Normals calculated with multithreading in  6  ms
Normals calculated with 1 thread in  7  ms
Normals calculated with multithreading in  6  ms
Normals calculated with 1 thread in  7  ms
Normals calculated with multithreading in  6  ms
Normals calculated with 1 thread in  7  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  7  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  6  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  6  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  7  ms
Normals calculated with multithreading in  6  ms
Normals calculated with 1 thread in  7  ms
Normals calculated with multithreading in  6  ms
Normals calculated with 1 thread in  6  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  7  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  7  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  7  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  7  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  7  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  7  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  6  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  7  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  6  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  7  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  6  ms
Normals calculated with multithreading in  7  ms
Normals calculated with 1 thread in  6  ms
Normals calculated with multithreading in  6  ms
Normals calculated with 1 thread in  7  ms
Normals calculated with multithreading in  6  ms


Название: Re: Многопоточная обработка массива
Отправлено: Old от Декабрь 02, 2014, 12:49
На линуксе пишет
cannot find -lQt5OpenGL
                -lQt5Widgets
и т.д.
В чём дело?
Вы бы показали строку запуска линкера перед этим сообщением.


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 02, 2014, 12:53
Цитировать
12:51:51: Настройки не изменились, этап qmake пропускается.
12:51:51: Запускается: «/usr/bin/make»
g++ -Wl,-rpath,/opt/Qt/5.3/gcc_64 -Wl,-rpath,/opt/Qt/5.3/gcc_64/lib -o ProCASTil main.o mainwindow.o solver.o positioner.o geometry.o axis.o progressdialog.o complexexportdialog.o fractionsolidcurve.o normalsolver.o qrc_icons.o qrc_shaders.o qrc_templates.o moc_mainwindow.o moc_solver.o moc_positioner.o moc_axis.o moc_progressdialog.o moc_complexexportdialog.o moc_fractionsolidcurve.o moc_normalsolver.o   -static -lgomp -L/opt/Qt/5.3/gcc_64/lib -lQt5OpenGL -lQt5Widgets -lQt5Gui -lQt5Core -lGL -lpthread
/usr/bin/ld: cannot find -lQt5OpenGL
/usr/bin/ld: cannot find -lQt5Widgets
/usr/bin/ld: cannot find -lQt5Gui
/usr/bin/ld: cannot find -lQt5Core
/usr/bin/ld: cannot find -lGL
collect2: error: ld returned 1 exit status
make: *** [ProCASTil] Error 1
12:51:52: Процесс «/usr/bin/make» завершился с кодом 2.
Ошибка при сборке/установке проекта ProCASTil (комплект: Desktop Qt 5.3 GCC 64bit)
When executing step "Сборка"


Название: Re: Многопоточная обработка массива
Отправлено: Old от Декабрь 02, 2014, 12:56
Скажите, а -static это вы добавляете? Попробуйте без него.


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Декабрь 02, 2014, 12:58
Код
C++ (Qt)
int times = (srcEnd - src) / sizeof(float) / 9;
А у Вас с адресной арифметикой все норм? Разница указателей возвращает число float (а не число байт). Да, и кстати не надо полагать что memcpy - самое быстрое (напр в данном случае это не так).

Всё равно сделал по-своему (лень).
Типа "не могу разлюбить copy-paste" :)  


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 02, 2014, 13:09
Код
C++ (Qt)
int times = (srcEnd - src) / sizeof(float) / 9;
А у Вас с адресной арифметикой все норм? Разница указателей возвращает число float (а не число байт). Да, и кстати не надо полагать что memcpy - самое быстрое (напр в данном случае это не так).
спасибо. глаза уже замылились - пока искал один баг на калькуляторе считал адреса, вот и автоматом выдал...
Скажите, а -static это вы добавляете? Попробуйте без него.
Спасибо. Помогло

Win 4 ядра
Цитировать
Normals calculated with 1 thread in  14  ms
Normals calculated with multithreading in  30  ms
Normals calculated with 1 thread in  15  ms
Normals calculated with multithreading in  10  ms
Normals calculated with 1 thread in  14  ms
Normals calculated with multithreading in  11  ms
Normals calculated with 1 thread in  13  ms
Normals calculated with multithreading in  10  ms


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 02, 2014, 13:18
Linux 2 ядра нетбук
Цитировать
Normals calculated with 1 thread in  21  ms
Normals calculated with multithreading in  53  ms
Normals calculated with 1 thread in  20  ms
Normals calculated with multithreading in  16  ms
Normals calculated with 1 thread in  20  ms
Normals calculated with multithreading in  17  ms
Normals calculated with 1 thread in  19  ms
Normals calculated with multithreading in  17  ms
Normals calculated with 1 thread in  20  ms
Normals calculated with multithreading in  16  ms
Normals calculated with 1 thread in  19  ms
Normals calculated with multithreading in  17  ms
Normals calculated with 1 thread in  19  ms
Normals calculated with multithreading in  15  ms
Normals calculated with 1 thread in  19  ms
Normals calculated with multithreading in  24  ms
Normals calculated with 1 thread in  20  ms
Normals calculated with multithreading in  23  ms
Normals calculated with 1 thread in  20  ms
Normals calculated with multithreading in  23  ms
Normals calculated with 1 thread in  23  ms
Normals calculated with multithreading in  21  ms
Normals calculated with 1 thread in  20  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  21  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  20  ms
Normals calculated with multithreading in  16  ms
Normals calculated with 1 thread in  19  ms
Normals calculated with multithreading in  23  ms
Normals calculated with 1 thread in  19  ms
Normals calculated with multithreading in  21  ms
Normals calculated with 1 thread in  20  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  19  ms
Normals calculated with multithreading in  23  ms
Normals calculated with 1 thread in  20  ms
Normals calculated with multithreading in  21  ms
Normals calculated with 1 thread in  19  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  19  ms
Normals calculated with multithreading in  20  ms
Normals calculated with 1 thread in  19  ms
Normals calculated with multithreading in  21  ms
Normals calculated with 1 thread in  19  ms
Normals calculated with multithreading in  16  ms
Normals calculated with 1 thread in  22  ms
Normals calculated with multithreading in  26  ms
Normals calculated with 1 thread in  19  ms
Normals calculated with multithreading in  20  ms


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 02, 2014, 13:29
Этот же нетбук но уже 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


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Декабрь 02, 2014, 13:31
Ну для начала - очень неплохо. КПД конечно "оставляет желать лучшего", но на такой задаче трудно что-то выжать. Можно поиграться с диспетчером, напр

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


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 02, 2014, 13:58
Всё это очень круто. Спасибо, что научили.
Но ещё осталось пару вопросов.
Где можно найти описание этой игрушки да такое, чтобы было простым и быстро учило? Пока что нашёл только официальную версию.
По какому принципу идёт распараллеливание?


Название: Re: Многопоточная обработка массива
Отправлено: Old от Декабрь 02, 2014, 14:00
Где можно найти описание этой игрушки да такое, чтобы было простым и быстро учило? Пока что нашёл только официальную версию.
Например здесь:
https://parallel.ru/tech/tech_dev/openmp.html
https://software.intel.com/ru-ru/articles/getting-started-with-openmp

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


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 02, 2014, 14:13
Где можно найти описание этой игрушки да такое, чтобы было простым и быстро учило? Пока что нашёл только официальную версию.
Например здесь:
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


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Декабрь 02, 2014, 14:23
Можете попробовать intel реализацию - для мелких задач она дает гораздо больший КПД


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 02, 2014, 16:05
Да, и кстати не надо полагать что memcpy - самое быстрое (напр в данном случае это не так).
Расходуем ресурсы на вызов вместо быстрого прямого копирования?


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Декабрь 02, 2014, 16:32
Расходуем ресурсы на вызов вместо быстрого прямого копирования?
Да, "сбиваем конвейер". Вообще от многих сишных вещей (что у Вас в коде) лучше потихоньку избавиться, не те времена


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 02, 2014, 20:18
Расходуем ресурсы на вызов вместо быстрого прямого копирования?
Да, "сбиваем конвейер". Вообще от многих сишных вещей (что у Вас в коде) лучше потихоньку избавиться, не те времена
Пока психологически не перебороть. Причём никогда не программировал на си. Начал с c++ в msvs2008.
Когда я так записываю, мне кажется, что у меня всё будет летать, в отличии если я запишу понятным для себя языком.


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


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 03, 2014, 09:35
оптимизировать функцию, "из коробки" выполняющуюся за 20 ms на мой взгляд не очень правильно.
Моей ошибкой было то, что это изначально была не оптимизация. То есть я изначально не замерил скорость выполнения при использовании скалярного решения.
Мне казалось, что на слабом оборудовании (как мой нетбук) это действие займет до 2-3 сек.


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Декабрь 03, 2014, 09:53
Моей ошибкой было то, что это изначально была не оптимизация. То есть я изначально не замерил скорость выполнения при использовании скалярного решения.
Мне казалось, что на слабом оборудовании (как мой нетбук) это действие займет до 2-3 сек.
Под "скалярным" подразумевается "без использования векторных команд" (SSE и др), multi-threading здесь ни при чем.


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 03, 2014, 11:35
Вот ещё задача.
Глобальная цель - взять большую кучу тетраэдров (описывает деталь) и оперативно построить сечение по ним. Строить планирую по такому принципу: У меня имеется оболочка из треугольников, которая описывает видимые грани тетраэдров, которые лежат на поверхности кучи (то есть грани, которые не соприкасаются с другими элементами). Путём перебора я найду треугольник, вершины которого лежат по разные стороны сечения. Мне известна связь оболочковых треугольников с тетраэдрами - получается я найду элемент (тетраэдр), который рассекает сечение. После этого я хочу взять каждый узел этого элемента и посмотреть, какие ещё элементы принадлежат этим узлам. Если найденные элементы будут в плоскости сечения, то их записываем. И так до тех пор, пока не найдём все элементы, проходящие через сечение.
Для достижения этой цели необходимо решить задачу:
Дано:
Массив элементов (тетраэдров). Записан в виде 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 секунд. Можно ли что-то придумать, чтобы сократить время хотя-бы до секунды?


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Декабрь 03, 2014, 12:33
Накрутили хз что :) Если надо найти какие тетраэдры пересекаются секущей плоскостью, то все куда проще

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

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



Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Декабрь 03, 2014, 12:36
Накрутили хз что :) Если надо найти какие тетраэдры пересекаются секущей плоскостью, то все куда проще

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

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


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Февраль 20, 2015, 17:17
Что у нас происходит на первом цикле, что параллельное вычисление слабее скалярного?
Запускает рабочие потоки.
Как запустить потоки на этапе запуска приложения, а не открытия файла?

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


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Февраль 20, 2015, 18:19
Как запустить потоки на этапе запуска приложения, а не открытия файла?
Они и запускаются при вызове omp_init, обычно на старте приложения. Если истекло "время прокрутки" они усыпляются на "честном" мутексе, новая задача потребует их пробуждения. Хотя время прокрутки устанавливать можно, в этом обычно нет смысла, оно по умолчанию велико (доли секунды). 

Это бесплатно? Ссылочкой поделитесь?
Да. бесплатно. Ссылку не помню - но из исходников я ее не собирал, гуглите intel openmp.


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Февраль 20, 2015, 22:04
Я не хочу, чтобы они усыплялись. Пользователь может открыть приложение и не предпринимать действий с участием openmp. Если я установлю это время прокрутки на бесконечность, что я потеряю?


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Февраль 21, 2015, 10:59
Я не хочу, чтобы они усыплялись. Пользователь может открыть приложение и не предпринимать действий с участием openmp. Если я установлю это время прокрутки на бесконечность, что я потеряю?
Не знаю можно ли "бесконечность", но в этом ничего хорошего нет, будет жраться процессорное время впустую. Т.е. получите капитальный тормоз, даже для др приложений.

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


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Февраль 21, 2015, 11:37
Спасибо. Предмет я уже выбрал.
Я думал, что инициализация потоков это нечто болтающееся в памяти и ожидающее своего выхода, но не жрущее процессор.


Название: Re: Многопоточная обработка массива
Отправлено: Old от Февраль 21, 2015, 11:39
Спасибо. Предмет я уже выбрал.
Я думал, что инициализация потоков это нечто болтающееся в памяти и ожидающее своего выхода, но не жрущее процессор.
Так и есть, рабочие нитки при отсутствии работы уснут и не будут есть процессор. Но вы не хотите что бы они засыпали. Почему то. :)


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Февраль 21, 2015, 15:20
Запутался...
В какой момент нитки создаются, а в какой пробуждаются?
у меня есть в коде только #pragma omp parallel for. Я так понял, что потоки создаются при первом проходе по этому участку. При последующих проходах потоки уже просто просыпаются. Так вот я не хочу тратить время на первом проходе на их создание. Хочу создавать при запуске приложения, а пробуждать по запросу пользователя.
Или я чего-то не понимаю?


Название: Re: Многопоточная обработка массива
Отправлено: Old от Февраль 21, 2015, 15:38
Попробуйте использовать omp_init в начале программы, или запустить фейковый параллельный цикл, просто для запуска потоков.


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Февраль 21, 2015, 16:03
не понимаю, что за omp_init, как его прописывать.
В документации нет такого сочетания. Подскажите кодом, пожалуйста


Название: Re: Многопоточная обработка массива
Отправлено: Old от Февраль 21, 2015, 17:40
не понимаю, что за omp_init, как его прописывать.
В документации нет такого сочетания. Подскажите кодом, пожалуйста
Как я понял, такая функция есть в реализации стандарта от intel.
Если в вашей реализации нет такой функции (в моей например нет), то я бы предложил создать простой цикл в начале программы, который и распараллелить с помощью openmp, тогда для него будут созданы рабочие потоки.


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Февраль 21, 2015, 18:10
Код:
#pragma omp parallel for
for (;false;);

Это запустит 4 потока, если у меня 4 ядра?


Название: Re: Многопоточная обработка массива
Отправлено: Old от Февраль 21, 2015, 18:17
Код:
#pragma omp parallel for
for (;false;);

Это запустит 4 потока, если у меня 4 ядра?
Ну если это оптимизатор совсем не выкинет... :)
Посчитайте несколько синусов в зависимости от времени и инициализируйте этим значением генератор случайных чисел, например. :)


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Февраль 21, 2015, 18:42
Код:
#pragma omp parallel for
for (;false;);

Это запустит 4 потока, если у меня 4 ядра?
Это не откомпилируется т.к. счетчик цикла должен быть известен OpenMP. По умолчанию задействуются все ядра. Главная нитка тоже "в бригаде" (что имеет свои минусы и плюсы). Число ниток можно установить с помощью omp_set_num_threads (хедер-то откройте)


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Февраль 21, 2015, 19:46
Да, действительно, не компилируется.
Написал:
Код:
    #pragma omp parallel for
    for (int i = 0; i < 1; ++i);
В хэдере я видел что имеется. Интересовало значение по умолчанию.

Спасибо.


Название: Re: Многопоточная обработка массива
Отправлено: m_ax от Февраль 21, 2015, 21:28
Кстатии, читал недавно, что OpenMP и с итераторами в циклах может работать.. Круто.. 


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Февраль 21, 2015, 23:16
Интересно. Кутёвый форич в том ли числе


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Февраль 25, 2015, 19:16
Ещё интересуют пару моментов.
При использовании распараллеливания операция new или QVector::resize(n) может привести к нахлёсту памяти?
Ещё интересует понятие reentrant - мне его никак не осознать. Означает ли оно, что я могу спокойно запараллелить QVector::append в 4 потока?


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Февраль 25, 2015, 19:48
Насчёт QVector::append  сам провел тест.
Код
C++ (Qt)
#pragma omp parallel for
   for (int i = 0; i < 100000000; ++i)
   {
       vec.append(i);
   }
 
Сначала получил ошибку в работе с памятью, а когда предварительно зарезервировал место, то получил размер массива 34171332


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Февраль 26, 2015, 10:41
Ещё интересуют пару моментов.
При использовании распараллеливания операция new или QVector::resize(n) может привести к нахлёсту памяти?
Ещё интересует понятие reentrant - мне его никак не осознать. Означает ли оно, что я могу спокойно запараллелить QVector::append в 4 потока?
Любые не-константные операции с любым контейнером НЕ "потокобезопасны" (NOT thread-safe) и ведут к крашу. Reentrant к этому отношения не имеет, это просто утверждение что ф-ция/метод отработает корректно если будет вызвана из самой себя, непосредственно или через цепочку др вызовов.

Если в параллельных вычислениях формируются результаты требующие сохранения в контейнере, то стандартная техника - каждая нитка пишет в свой контейнер, потом все сливается. Есть и менее хлопотный (но и менее эффективный) способ
Код
C++ (Qt)
#pragma omp parallel for
for (int i = 0; i < 100000000; ++i)
{
#pragma omp critical
    vec.append(i);
}
 
Правда в данном случае это будет работать медленнее чем без OpenMP :)  Однако если основные вычисления будут вне critical - то вполне.

Ещё интересуют пару моментов.
Так, "пара моментов" (типа "детали") :)  Да там еще ничего и не начиналось. Настоящее распараллеливание очень далеко от резвого создания потоков в Qt. Мало не покажется.



Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Февраль 26, 2015, 10:53
О, спасибо. Мне это пригодится.

У меня имеется обработка с помощью #pragma omp parallel for.
Как будет правильнее отображать прогресс (со значением -1)?
Я имею в виду, как обойти блокировку интерфейса. Нужно вынести вычисления в QThread? OpenMP не сунется в главный поток?


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Февраль 26, 2015, 10:56
О, спасибо. Мне это пригодится.

У меня имеется обработка с помощью #pragma omp parallel for.
Как будет правильнее отображать прогресс (со значением -1)?
Я имею в виду, как обойти блокировку интерфейса. Нужно вынести вычисления в QThread? OpenMP не сунется в главный поток?
Используйте

#pragma omp master


Название: Re: Многопоточная обработка массива
Отправлено: __Heaven__ от Февраль 26, 2015, 14:03
Можно подробнее?
Есть 2 класса MainWindow и Solver. Первый вызывает метод второго и показывает прогресс. В методе Solver прописан #pragma omp parallel for.
Куда вписывается #pragma omp master?


Название: Re: Многопоточная обработка массива
Отправлено: Igors от Февраль 26, 2015, 15:18
Можно подробнее?
Есть 2 класса MainWindow и Solver. Первый вызывает метод второго и показывает прогресс. В методе Solver прописан #pragma omp parallel for.
Куда вписывается #pragma omp master?
Псевдокод
Код
C++ (Qt)
void Solver::CalcParallel( void )
{
 QAtomicInt numDone = 0;
 
#pragma omp parallel for
 for (int i = 0; i < data.size; ++i) {
  DoCalc(data[i]);
  ++numDone;
 
#pragma omp master
  mainWindow->UpdateNumDone(numDone);
 }
}