Russian Qt Forum

Qt => Многопоточное программирование, процессы => Тема начата: Daniel от Ноябрь 22, 2012, 12:38



Название: Параллельное выполнение цикла расчета
Отправлено: Daniel от Ноябрь 22, 2012, 12:38
Добрый день. Помогите, кто может :)

Происходит огромное количество расчетов вот такого вида:
Код:
for ( int j = 2; j <= MJ - 1; j++)
     for ( k = 2; k <= NK - 1; k++)
          for ( i = 2; i <= *(Radiuses + k) - 1; i++)
          {
                //вычисление нескольких локальных переменных и проверок
                ...
                *(*(*(p1 + i) + j) + k) =  *(*(*(p + i) + j) + k) + /* огромная формула, независящая от p1 */
          }
Хочу сделать, чтобы считало, используя все CPU, т.к. расчеты иногда сутками идут.
Пробую через
Код:
#pragma omp parallel for
, предварительно включив в .pro-файл строку:
Код:
QMAKE_CXXFLAGS += -fopenmp
, а в файл, где происходит расчет, подключил:
Код:
#include <omp.h>

Уже обнаружил такой аспект, что цикл после #pragma omp parallel for не может быть по unsigned int, что исправил объявляя в цикле локальную переменную int j. Также пробовал заменить MJ (который беззнаковый) на int - та же проблема, поэтому вернул его обратно. И как вы уже наверное поняли, помышляю я распараллелить внешний цикл по j.
А проблема такая:
 error: undefined reference to `omp_get_num_threads'
 error: undefined reference to `omp_get_thread_num'
 error: undefined reference to `GOMP_parallel_start'
 error: undefined reference to `GOMP_parallel_end'

ну и как результат:
 error: collect2: ld returned 1 exit status

В гугле не нашел похожих проблем. Скорее всего чего-то где-то я недоподключил. Подскажите, кто может.

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


Название: Re: Параллельное выполнение цикла расчета
Отправлено: Igors от Ноябрь 22, 2012, 12:59
Нет самой либы, напр libgomp.a (или др имя на Вашей платформе). Флаг только говорит генерировать код omp
А вообще omp - верный, правильный путь


Название: Re: Параллельное выполнение цикла расчета
Отправлено: Daniel от Ноябрь 22, 2012, 13:08
Нет самой либы, напр libgomp.a (или др имя на Вашей платформе). Флаг только говорит генерировать код omp
А вообще omp - верный, правильный путь
А где ее взять и куда положить?

У меня Win8 Pro x64, использую Qt 4.7.2 for Desktop - MinGW 4.4 (Qt SDK)


Название: Re: Параллельное выполнение цикла расчета
Отправлено: Igors от Ноябрь 22, 2012, 13:22
А где ее взять и куда положить?

У меня Win8 Pro x64, использую Qt 4.7.2 for Desktop - MinGW 4.4 (Qt SDK)
Я использую др IDE поэтому могу только отослать в гуглу  :)


Название: Re: Параллельное выполнение цикла расчета
Отправлено: Fat-Zer от Ноябрь 22, 2012, 14:20
А где ее взять и куда положить?

У меня Win8 Pro x64, использую Qt 4.7.2 for Desktop - MinGW 4.4 (Qt SDK)
скорей всего она есть, должна идти в комплекте с gcc. только назавается она libgomp.
не знаю, правда, положили ли её вам в комплект под виндой...
скорей всего она просто не указана для линковки... линкеру соответственно надо просто передать -lgomp. как в qmake это правильно сделать, да ещё и под виндой, я уже и не помню...


Название: Re: Параллельное выполнение цикла расчета
Отправлено: xokc от Ноябрь 22, 2012, 15:59
как в qmake это правильно сделать, да ещё и под виндой, я уже и не помню...
Если libgomp лежит в стандартной lib папке, то
.pro: -lgomp

Если libgomp лежит не в стандартной lib папке, то
.pro: -L"Путь к папке с библиотекой" -lgomp


Название: Re: Параллельное выполнение цикла расчета
Отправлено: Daniel от Ноябрь 22, 2012, 16:24
Добавил в QtSDK\mingw\lib\
  libgomp.a
а в QtSDK\mingw\bin\
  pthreadGC2.dll

затем в .pro:
  LIBS += -lgomp
  QMAKE_CXXFLAGS += -fopenmp

Теперь компилируется. Но при выполнении #pragma omp parallel for вылетает с ошибкой -1073741819 :(




Название: Re: Параллельное выполнение цикла расчета
Отправлено: Daniel от Ноябрь 22, 2012, 16:37
Вроде как проблема в том, что это распараллеливание происходит внутри QThread, но вот решения я так и не нашел :(


Название: Re: Параллельное выполнение цикла расчета
Отправлено: ssoft от Ноябрь 22, 2012, 16:54
Небольшой комментарий к коду

Код:
*(*(*(p1 + i) + j) + k) =  *(*(*(p + i) + j) + k)

Вроде как, быстрее быдет работать, к тому же и запись понятнее, если написать (при условии что ***p1 простой тип)

Код:
p1[ i ][ j ][ k ] = p[ i ][ j ][ k ] +


Название: Re: Параллельное выполнение цикла расчета
Отправлено: Daniel от Ноябрь 22, 2012, 17:10
Вроде как, быстрее быдет работать, к тому же и запись понятнее, если написать (при условии что ***p1 простой тип)
Код:
p1[ i ][ j ][ k ] = p[ i ][ j ][ k ] +
Тип простой - float. А почему? Я всегда думал, что при использовании оператора [] происходит проверка на выход за границы массива. А по поводу понятности, то я обычно макросы использую. Но если [] быстрее, то надо будет поправить.


Название: Re: Параллельное выполнение цикла расчета
Отправлено: Igors от Ноябрь 22, 2012, 17:31
Тип простой - float. А почему? Я всегда думал, что при использовании оператора [] происходит проверка на выход за границы массива. А по поводу понятности, то я обычно макросы использую. Но если [] быстрее, то надо будет поправить.
Это не Паскаль, никаких проверок на границы не производится. Скорость выполнения одна и та же, но [] намного легче для восприятия. Использование ** (двух звездочек в объявлении) нежелательно, трех - тем более. 


Название: Re: Параллельное выполнение цикла расчета
Отправлено: Daniel от Ноябрь 22, 2012, 17:54
Это не Паскаль, никаких проверок на границы не производится. Скорость выполнения одна и та же, но [] намного легче для восприятия. Использование ** (двух звездочек в объявлении) нежелательно, трех - тем более. 

Понятно... Значит поправлю как-нибудь, ведь действительно лучше выглядит.

По поводу основной проблемы:
Таки да, это из-за того, что #pragma omp parallel for вызывается из QThread (точнее унаследованного от него класса). Потому что я попробовал в void main() вызвать методы omp - работают.
И как это решить - без понятия, единственное, что нашел, так это обсуждение этой проблемы на каком-то французском форуме (на фр. языке). А решением оказалось вызов где-то метода
Код:
pthread_win32_thread_detach_np (); 
Но я не понял где, да и не работает он у меня (<pthread.h> подключаю).
Может у кого-то какие идеи?
А и еще: то же самое, скомпиленное под линуксом или VS, пашет, в то время как под Mac или на Qt - нет (сам не проверял, но просто с такой проблемой сталкивались люди в темах, что я нагуглил).


Название: Re: Параллельное выполнение цикла расчета
Отправлено: Igors от Ноябрь 22, 2012, 18:07
Используйте omp прямо из главной нитки, ни к чему искать приключений. По умолчанию все ядра будут задействованы. Можно создавать др нитки (через pthread или QThread) но они не будут входить в "бригаду omp". А вот главная нитка входит. Если нужно обновить UI можно напр так

Код
C++ (Qt)
#pragma omp parallel for
for (int i = 0; i < limit; ++i) {
// расчеты
 
#pragma omp master   // код ниже будет выполняться только главной
{
// рисуем в UI
 }
}
 


Название: Re: Параллельное выполнение цикла расчета
Отправлено: Daniel от Ноябрь 22, 2012, 18:27
Если честно - не представляю, как это организовать.
Алгоритм приблизительно такой:

Код:
MainWindow::StartCalculation() {
  // считывание параметров и т.д.
  thread->start(); //thread типа MyThread унаследованного от QThread
}
MyThread::run()
{
  do
  {
       ladle->Iterate(); // итерации последовательны, т.е. нельзя их параллельно
       // запись результатов в файл, возбуждение сигнала об обновлении прогрессбара...
  }
  while (условие выхода);
}

Ladle::Iterate()
{
   считать_то(); // каждое считать() - это пробег по 3-д массиву
   считать_сё();
   for ( m = 0; m < iterations; m++) // iterations обычно = 500-5000
      считать_еще(); // именно тут я хотел распараллелить, а если получится, то потом в каждом "считать()"
}
Схематически оно выглядит так. Вот куда тогда всовывать это #pragma omp parallel for ? Перед ladle->Iterate(); или thread->start(); ? Так вроде нельзя, там же не циклы...
Извиняюсь, что торможу и нагружаю, просто уже устал :)


Название: Re: Параллельное выполнение цикла расчета
Отправлено: Igors от Ноябрь 22, 2012, 19:10
Код:
   for ( m = 0; m < iterations; m++) // iterations обычно = 500-5000
      считать_еще(); // именно тут я хотел распараллелить, а если получится, то потом в каждом "считать()"
}
Этот цикл должен быть достаточно трудоемким, если же на его выполнение затрачиваются доли секунды - нет смысла городить огород. Точнее считать_еще() должно быть достаточно трудоемким, просто число итераций ни о чем не говорит, бывает и 10-20 параллелятся прекрасно.

Лучше всего просто перенести все в главную нитку и забыть о MyThread. Если же не хочется "так много ломать", то можно сделать сигнал с BlockingQueuedConnection который остановит MyThread а слот в главной нитке запустит бригаду ниток omp. В любом случае оmp parallel вставлять в главной нитке перед циклом который нужно распараллелить


Название: Re: Параллельное выполнение цикла расчета
Отправлено: Daniel от Ноябрь 22, 2012, 19:59
А после отправки сигнала и исполнения слота, возобновить тред thread->start()? И она продолжит с того же места или начнет run() сначала?


Название: Re: Параллельное выполнение цикла расчета
Отправлено: ssoft от Ноябрь 23, 2012, 07:08
Скорость выполнения одна и та же, но [] намного легче для восприятия. Использование ** (двух звездочек в объявлении) нежелательно, трех - тем более.  

Написал грубый тест производительности.

Код:
		QVector< float > data( 1024, 0.0f );
float * values = data.data();
int int_count = data.count();

for ( int i = 0; i < 40; ++i )
{

quint64 count = quint64( 1 ) << i;
qDebug()
<< "Start tests:" << i
<< "-" << count << "iterations";

QTime timing;
timing.start();

for ( quint64 iter = 0; iter < count; ++iter )
{
for ( int i = 0; i < int_count; ++i )
{
values[ i ] = static_cast< float >( iter + i );
}
}
qDebug()
<< timing.elapsed()
<< "for container[ i ]";

timing.restart();

for ( quint64 iter = 0; iter < count; ++iter )
{
for ( int i = 0; i < int_count; ++i )
{
*( values + i ) = static_cast< float >( iter + i );
}
}
qDebug()
<< timing.elapsed()
<< "for *( array + i )";
}
}

return 0;

Для компилятора gcc (mingw) разницы нет, а вот для MSVC2010 разница почти в 10%!
Впервые столкнулся с этим при реализации численных методов лет 8 назад.
10% при длительности расчетов дни или недели - это очень существенно.
Поправьте, если я не прав.


Название: Re: Параллельное выполнение цикла расчета
Отправлено: xokc от Ноябрь 23, 2012, 08:38
Замеряли, надеюсь, в release с включёнными оптимизациями? Компиляторы сейчас достаточно умны, чтобы слажать на таком примитивном случае.


Название: Re: Параллельное выполнение цикла расчета
Отправлено: Igors от Ноябрь 23, 2012, 09:48
А после отправки сигнала и исполнения слота, возобновить тред thread->start()? И она продолжит с того же места или начнет run() сначала?
Продолжит (см описание BlockingQueuedConnection). Вообще распараллеливание - довольно серьезная штука, часто требуется переделать задачу в корне. Конечно получится сходу - слава богу, но рассчитывать на это не стоит. Возможно есть смысл сначала попробовать на небольшом тестовом проекте.

Для компилятора gcc (mingw) разницы нет, а вот для MSVC2010 разница почти в 10%!
Впервые столкнулся с этим при реализации численных методов лет 8 назад.
10% при длительности расчетов дни или недели - это очень существенно.
Поправьте, если я не прав.
В MSVC есть много такого что совершенно недоступно моему пониманию :) А вообще это классический пример из библии Страутструпа где говорится типа "современный компилятор должен сделать примерно одинаковый код".

Длительность расчетов дни/недели часто свидетельствует просто о том что никаких попыток оптимизировать вычисления не предпринималось :) У меня нет оснований не верить Вашим тестам, но это проверка "холостого хода". То есть изменив все [] на * в рабочем проекте мы получим совсем не -10%, а возможно -2%. а может даже и +5% (бывает и так). В другом кусочке кода компилятор может разбираться с [] уже совсем по-другому.


Название: Re: Параллельное выполнение цикла расчета
Отправлено: ssoft от Ноябрь 23, 2012, 10:08
MSVC2010
Release
Проверил всё, что предлагает студия
  Disabled (/Od) здесь всегда все одинаково.

А вот для

  Minimize Size /01
  Maximize Speed /02
  Full Optimization /0x

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

Код:
Start tests: 16 - 65536 iterations 
612 for container[ i ]
610 for *( array + i )
Start tests: 17 - 131072 iterations
1235 for container[ i ]
1230 for *( array + i )
Start tests: 18 - 262144 iterations
2473 for container[ i ]
2452 for *( array + i )
Start tests: 19 - 524288 iterations
4920 for container[ i ]
4903 for *( array + i )
Start tests: 20 - 1048576 iterations
9810 for container[ i ]
9820 for *( array + i )

так и к разному

Код:
Start tests: 16 - 65536 iterations 
613 for container[ i ]
690 for *( array + i )
Start tests: 17 - 131072 iterations
1232 for container[ i ]
1390 for *( array + i )
Start tests: 18 - 262144 iterations
2455 for container[ i ]
2775 for *( array + i )
Start tests: 19 - 524288 iterations
4908 for container[ i ]
5612 for *( array + i )
Start tests: 20 - 1048576 iterations
9818 for container[ i ]
11183 for *( array + i )

не удивлюсь, если у кого-нибудь будет наоборот.

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

Цитировать
Длительность расчетов дни/недели часто свидетельствует просто о том что никаких попыток оптимизировать вычисления не предпринималось

часто да, но здесь нет  ;D. Ряд задач, например, нестационарные задачи газовой динамики с подвижной геометрией считают неделями, а иногда и месяцами.


Название: Re: Параллельное выполнение цикла расчета
Отправлено: Igors от Ноябрь 23, 2012, 10:33
Склоняюсь к мнению, что предложенный мной тест не корректен, и разницы между записями нет.
Вообще нужно сравнить ассемблерный код, он должен быть идентичен.
В gcc все стабильно - результат одинаковый.
Я бы подытожил так: ковыряться в этом нет никакого смысла, здесь ничего не извлечь  :)

часто да, но здесь нет  ;D. Ряд задач, например, нестационарные задачи газовой динамики с подвижной геометрией считают неделями, а иногда и месяцами.
Ну спорить о незнакомой мне предметной области я не могу, поэтому др пример. Вы давеча спрашивали "что ето за рендер" - там тоже если увеличить разрешение, то счет быстро пойдет на часы и дни. Однако никаким "волшебным кодом" (т.е. чисто технически) это не решить - нужно менять/усиливать алгоритм.


Название: Re: Параллельное выполнение цикла расчета
Отправлено: Fregloin от Ноябрь 23, 2012, 11:26
 может немного не в тему, но если такие вычисления длятся сутками, то может посмотреть в сторону OpenCL? и перенсти нагрузку на видеокарту?


Название: Re: Параллельное выполнение цикла расчета
Отправлено: ssoft от Ноябрь 23, 2012, 14:20
может немного не в тему, но если такие вычисления длятся сутками, то может посмотреть в сторону OpenCL? и перенсти нагрузку на видеокарту?

Так и делают уже достаточно давно (несколько лет), но пока на уровне научно-исследовательских работ.


Название: Re: Параллельное выполнение цикла расчета
Отправлено: xokc от Ноябрь 23, 2012, 14:35
Так и делают уже достаточно давно (несколько лет), но пока на уровне научно-исследовательских работ.
Очень плотно уже несколько лет работаем с вычислениями на видеокартах NVidia, но не через OpenCL, а через CUDA Toolkit. Очень нравится. И инструментарий разработчика, и комъюнити, и результаты. Раньше эти же задачи решали на ПЛИС - сроки вывода решений на рынок стали в разы короче.


Название: Re: Параллельное выполнение цикла расчета
Отправлено: Daniel от Ноябрь 23, 2012, 17:42
Спасибо всем, особенно Igors.
Попробую как-нибудь на простом проекте, а вчера вечером меня осенило и я смог ускорить расчет в разы с математической точки зрения.
Но распараллеливанием все равно надо будет заняться.