Почему не работает OpenMP?

Сделал 2 функции без использования и с ипользованием OpenMP

#include <string>
#include <iostream>
#include <fstream>
#include <Windows.h>
#include <omp.h>
 
using namespace std;
 
struct Result
{
  LARGE_INTEGER StopTime, StopTimeNthread, Freq, StartTime, StartTimeNthread;
  long nRes, nResNthread;
  int nthread;
};
 
Result res;
 
ofstream fTest;
 
void sum_arr(const long n) // обычная функция
{
  long sum = 0;
  long* a = (long*)malloc(sizeof(long)*n);
  for(long i = 0; i < n; ++i)
  {
    a[i] = 1;
  }
  QueryPerformanceCounter(&res.StartTime);
  for(long i = 0; i < n; ++i)
  {
    sum += a[i];
  }
  QueryPerformanceCounter(&res.StopTime);
  res.nRes = sum;
  free(a);
}
 
void sum_arr_omp(const long n) // обычная функция
{
  long sum = 0;
  long* a = (long*)malloc(sizeof(long)*n);
  for(long i = 0; i < n; ++i)
  {
    a[i] = 1;
  }
  res.nthread = omp_get_max_threads();
  QueryPerformanceCounter(&res.StartTimeNthread);
  #pragma omp parallel shared(a) reduction (+: sum) num_threads(res.nthread)
  {
   #pragma omp for    
   for(long i = 0; i < n; ++i)
   {
     sum += a[i];
   }
  } // #pragma omp parallel
  QueryPerformanceCounter(&res.StopTimeNthread);
  res.nResNthread = sum;
  free(a);
}
 
int main()
{
  setlocale(LC_ALL, "");
  double nMax;
  QueryPerformanceFrequency(&res.Freq);
  fTest.open("Test.txt", ios::app | ios::out | ios::binary);
  sum_arr(1000000);
  sum_arr_omp(1000000);
  nMax = ((double)res.StopTime.QuadPart - (double)res.StartTime.QuadPart)/((double)res.StopTimeNthread.QuadPart
        - (double)res.StartTimeNthread.QuadPart);
  cout  << nMax << "\t\tefficiency of use " <<  res.nthread << " threads"  << endl;
  fTest << nMax << "\t\tefficiency of use " <<  res.nthread << " threads"  << endl;
  if(res.nRes != res.nResNthread)
    cout << "!!! Error" << endl;
  system("\npause");
  return 0;
}

Однако использование OpenMP не дает выигрыша по времени, а даже замедляет выполнение программы. Помогите, пожалуйста, разобраться. Проект прикрепил
Прикреплённый файлCpuGpu.zip (2,42 Кбайт, скачиваний: 91)

Цитата tuchin @ 16.05.17, 13:46

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

Скорее всего просто погрешность, на таких операциях. Отключи оптимизацию в компиляторе. Ну и сделай там какие-нибудь операции потяжелее.

Оптимизации в проекте нет. Сделал умножение векторов - тот же результат. Отношение времени без OpenMP и с OpenMP изменяется в пределах от 0.5 до 1.5 при запусках программы

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

Проверь, кстати, что твой код работает в разных потоках. А то эти прагмы ни4ого ни к чему необязывают, могут тупо игнорироваться.

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

Цитата Олег М @ 16.05.17, 19:58

Проверь, кстати, что твой код работает в разных потоках. А то эти прагмы ни4ого ни к чему необязывают, могут тупо игнорироваться.

А как это проверить?

tuchin
Вы не учли что на синхронизацию потоков нужно время.
Время переключения между потоками порядка 10 мкс. А время реакции OpenMP может быть гораздо выше в плоть до хх мс. За это время основной поток у вас успевает всё просчитать самостоятельно. Увеличьте расчёт в 100 раз по времени.
А ещё лучше до 10 секунд. Тогда побочные эффекты с временем на ваш тест не будут влиять.

Сообщение отредактировано: Pavia - 17.05.17, 03:15

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

И на сумме получилось. При nMax = 100000000 выигрыш составил в среднем 2.5 раза

Цитата Pavia @ 17.05.17, 03:11

Вы не учли что на синхронизацию потоков нужно время.
Время переключения между потоками порядка 10 мкс. А время реакции OpenMP может быть гораздо выше в плоть до хх мс. За это время основной поток у вас успевает всё просчитать самостоятельно. Увеличьте расчёт в 100 раз по времени.
А ещё лучше до 10 секунд. Тогда побочные эффекты с временем на ваш тест не будут влиять.

Спасибо большое за подробный ответ! А как Вы определили, что переключение между потоками занимает около 10 мкс?

Цитата Pavia @ 17.05.17, 03:11

между потоками порядка 10 мкс

скорее порядка 1-10мс

tuchin
Мне была очень интересна эта тема времени. И я её досконально изучал. Жалко с OpenMP я мало работал.
Сейчас запустил ваш тест получил не внятные результаты. Основываясь на опыте увеличил время замера. Гипотетические высказывания совпали с практическими.

По поводу цифр это примерные значения, так как с OpenMP я мало работал. Не надо их воспринимать буквально и делать поспешных выводов.
Откуда известно, что время переключения задач занимает 10 мкс? Intel приводит информацию для своих процессоров. А также есть презентация от Макрософта с информация о том как работает планировщик в виндоусе.

10 мс это короткий цикл, когда переключение известно кого на кого.
1-10 мс это время выгрузки регистров ядра в КЭШ в зависимости от модели процессора. А переключение это выгрузка плюс загрузка умножаем на 2. И плюс энергосберегающий режим, так как Интела приводит для максимальной частоты. А это ещё умножь на 3 раза.

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

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

Резюме: Более и или менее стабильный выигрыш от многопоточности можно получить только на интервалах времени, значительно превышающих квант переключения потоков в ОС (т.е. >> 10-15 мс). Если все же хочется "поиграться" с OpenMP на интервалах, сравнимых с квантом, то лучше не "жадничать" и задавать кол-во потоков меньше max_threads в расчете на то, что один или несколько логических процессоров м.б. заняты другими потоками\задачами.

Сообщение отредактировано: leo - 18.05.17, 05:17

Цитата leo @ 18.05.17, 05:06

В данном случае дело не просто в переключении контекста, а в создании и инициализации новых потоков (как объектов ядра ОС) и, главное, в возможной задержке их запуска, т.к. созданные потоки запускаются не сразу, а просто ставятся в очередь планировщика потоков (соответствующего приоритета).

Результат слабо зависит от того создаёшь потоки или запускаешь уже существующие. Лично я не смог добиться, чтоб на 8 процессорах отрабатывало быстрее в 8 раз, как хотелось бы. В среднем - выигрыш получался немного больше 4-х. Что с omp, что без.

Цитата leo @ 18.05.17, 05:06

Более и или менее стабильный выигрыш от многопоточности можно получить только на интервалах времени, значительно превышающих квант переключения потоков в ОС (т.е. >> 10-15 мс).

Выигрыш будет, когда поток успевает выполнить работу за квант времени. Иначе будет сбрасываться кэш процессора.

Цитата Олег М @ 18.05.17, 05:26

Результат слабо зависит от того создаёшь потоки или запускаешь уже существующие

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

Цитата Олег М @ 18.05.17, 05:26

Выигрыш будет, когда поток успевает выполнить работу за квант времени

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

Цитата Олег М @ 18.05.17, 05:26

Иначе будет сбрасываться кэш процессора.

В данной задаче сброс кэша особой роли не играет, т.к. ни 4Мб в первом варианте, ни тем более 400 Мб во-втором, по любому в L1\L2 не умещаются.

Цитата Олег М @ 18.05.17, 05:26

Лично я не смог добиться, чтоб на 8 процессорах отрабатывало быстрее в 8 раз, как хотелось бы. В среднем - выигрыш получался немного больше 4-х

Небось 8 логических при 4 физических ядрах. А при использовании HT\SMP рассчитывать на выигрыш более чем на десяток-другой процентов не приходится, особенно на простых задачах (типа подсчета суммы целочисленного массива).

Сообщение отредактировано: leo - 18.05.17, 08:12

Цитата leo @ 18.05.17, 08:08

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

Что значит запуск потока? Они уже все запущены, речь идёт только о переключении контекста.

Цитата leo @ 18.05.17, 08:08

Небось 8 логических при 4 физических ядрах.

Я тоже так подумал. Хотя omp_get_num_procs() возвращает 8

Цитата Олег М @ 18.05.17, 08:45

Что значит запуск потока? Они уже все запущены, речь идёт только о переключении контекста.

Это вы тут с подачи Pavia увлеклись простыми "переключениями контекста". А я толкую о том, что сначала должен быть создан и проинициализирован соответствующий объект ядра и все его окружение (стек, TEB, контекст процессора и т.п.), затем поток должен быть поставлен в очередь потоков своего приоритета и дождаться, пока планировщик решит "запустить" его в первый раз на исполнение, после чего наконец-то и произойдет долгожданное "переключение контекста" процессора с одного потока на другой. Соотв-но с момента вызова CreateThread до реального запуска потока (первого переключения контекста) может пройти несколько единиц или десятков миллисекунд в зависимости от загрузки системы и воли случая. Их можно не учитывать, когда общее время работы достаточно велико. Но если задача м.б. выполнена одним потоком примерно за то же время, то это приводит к чистому проигрышу в "ожидании у моря погоды". И результаты ТС это подтверждают - при n = 1 млн получается фифти-фифти от 0.3 до 1.5, а при n = 100 млн - выигрыш "в среднем 2.5 раза"

Сообщение отредактировано: leo - 18.05.17, 09:41

Цитата leo @ 18.05.17, 09:40

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

Во-первых - я сначала создавал потоки, потом запускал таймер, потом запускал обработку данных.
Во-вторых - создание потоков никак не повлияло на время обработки.
В-третьих - и какой процент времени от 30-секундной обработки приходится на создание потока, чтоб его учитывать?

Олег М
Вообще-то мы тут обсуждаем не твои эксперименты с предварительным созданием потоков и 30-секундной обработкой, а конкретный вопрос г-на tuchin-а "Почему не работает OpenMP?" при сложении (всего лишь) 1 миллиона int, которое на современных процах м.б. выполнено одним потоком за несколько миллисекунд. Отсюда и чехарда выигрышей\проигрышей OpenMP, т.к. время обработки одним потоком сравнимо со временем создания\запуска доп.потоков. А когда ТС увеличил время обработки в 100 раз, то и результаты у него стали более стабильные и предсказуемые - ну прям как у тя

Сообщение отредактировано: leo - 18.05.17, 13:10

Цитата leo @ 18.05.17, 12:55

Вообще-то мы тут обсуждаем не твои эксперименты с предварительным созданием потоков и 30-секундной обработкой,

Проблема в том, что там результаты слабо зависят от длительности. Те микросекунды, за которые создаётся/запускается поток слабо влияют на работу, длительностью в миллисекунды.
Его код я тоже исполнял, получил то же самое, разница - в 4 раза.

Цитата Олег М @ 18.05.17, 13:18

Те микросекунды, за которые создаётся/запускается поток слабо влияют на работу, длительностью в миллисекунды.
Его код я тоже исполнял, получил то же самое, разница - в 4 раза

Я уже устал повторять, что поток только создается за микросекунды, а запускаться может как через микросекунды, так и через единицы-десятки миллисекунд. Все зависит от текущей загрузки процессоров левыми потоками. У тебя 8-процессорная система, поэтому, грубо говоря, при 1 своем и 3-х левых потоках остается еще 4 свободных процессора, которые теоретически могут дать выигрыш до 4 и более раз. А на 4-процессорной системе в тех же условиях свободных процессоров нет, и соотв-но все зависит от воли случая - через какое время левые потоки освободят занимаемые процессоры (либо принудительно по истечении кванта, либо добровольно уснув на wait-функциях). Pavia тоже исполнял этот тест и

Цитата Pavia @ 17.05.17, 18:30

получил не внятные результаты. Основываясь на опыте увеличил время замера. Гипотетические высказывания совпали с практическими.

PS: На разброс результатов также может влиять текущая величина кванта времени, которая может изменяться от стандартных 15 мс до 1 мс при вызове timeBeginPeriod различными мультимедиа-примочками - например, рекламными анимашками в браузере. Чем больше величина кванта, тем больше м.б. разброс выигрышей\проигрышей на малых интервалах при наличии левых потоков.

leo
Загляни внутрь кода OpenMP. Потоки он создаёт заранее и входит при обращении к циклу входи в них быстро. Основной тормоз по выход из потока.

Добавлено 19.05.17, 08:23

Цитата leo @ 19.05.17, 08:00

На разброс результатов также может влиять текущая величина кванта времени, которая может изменяться от стандартных 15 мс до 1 мс при вызове timeBeginPeriod различными мультимедиа-примочками

Ещё не забываем что СУБД любят её включать. Но по моим замером на потоки эта функция не оказывает заметного влияния, скорее она больше влияет на очередь сообщений.

Добавлено 19.05.17, 08:57
leo
Такое чувство что Вы не учитываете что у потоков есть приоритеты. Либо не до конца понимаете как они работают.
Как только вы запустили задачу и сделали её активной у неё становиться наивысший приоритет. Это значит что она будет получать управление пока не появиться поток с высшим приоритетом. А откуда он возьмётся пока вы не ткнёте мышкой в другое окно? ответ не возьмётся.

Но ОС иногда всё же переключает потоки. Делает она это редко и не надолго.
Вот цифры с моих замеров. Округлил для расчётов.
400 раз на процессор. 50 на ядро. Из них 10 имеют длительность по 16.6 мс. И 40 скажем по 20 мкс.

Откуда вопрос: какова вероятность того что все 8 потоков трудятся над вашей программой?
Задача у нас занимает 10 мкс. Таких участков в 1 секунде 100 000.
(10*16,6мс/10мкс+40*20 мкс/10 мкс)/100000=16680/100000=1/6
Это значит что ошибка измерения за счёт вытесняющей многозадачности составляет всего 1 раз на 6 запусков.

И стоит учесть что эта вероятность что 1 поток, а не все 8 окажутся заняты над чужими программами.
Это значит что если ошибка произойдет, то она составит не более 1/8=12,5%

Если вы запустите проигрывать видео, то тогда да вероятность "простоя" снизится. Но майкрософт её держат на уровне не более чем 2 к 1.

Это расчёт для задачи длиной в 10 мкс. На других задачах погрешность может возрасти.

Сообщение отредактировано: Pavia - 19.05.17, 09:15

Алгоритм шедулера вообще-то документирован.

Qraizer
Если вы про Ритхера, то он описывает устройство планировщика NT4 максимум Win2k с тех пор стратегия работы поменялась несколько раз.
Если вы про мою ссылку, то она от 2003 года и там нет описание нововведений сделанных в Viste и Win7 и я мочу про Win10. В принципе есть публикации некоторых исследователей.
Но даже с учётом этого это неполный материалы. И они не дают полной картины происходящего.
Хочется её описать и понять. Но вот нужных слов пока не нахожу. А обучение на примерах слишком долго народу будет не интересно.

Она менялась в каждом релизе, но только количественно. Качественно шедулеры ОС всех версий работают по одинаковым алгоритмам.

Добавлено 19.05.17, 13:18

Цитата Pavia @ 19.05.17, 10:42

Но даже с учётом этого это неполный материалы. И они не дают полной картины происходящего.

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

Добавлено 19.05.17, 13:27

Цитата Qraizer @ 19.05.17, 13:17

Качественно шедулеры ОС всех версий работают по одинаковым алгоритмам.

Точнее, алгоритмы менялись в сторону расширения функциональности, например, для лучшей поддержки мультимедиа или там репланировки исполнительных очередей ядерных потоков. Но в той своей части, которая берёт истоки от самых первых реализаций вытесняющей многозадачности, алгоритмы прежние, менялись только значения их параметров. Например, конкретные цифры приоритетов, сопоставляемые тем или иным PRIORITY_CLASS в сочетании с THREAD_PRIORITY или значения уровней DIRQL.

Цитата Pavia @ 19.05.17, 08:20

Такое чувство что Вы не учитываете что у потоков есть приоритеты. Либо не до конца понимаете как они работают.

Я то понимаю и учитываю. А ты ?
Во-первых, "наивысший" приоритет активной задачи означает не самый высокий среди прочих потоков, а условно наивысший (THREAD_PRIORITY_HIGHEST=+2) относительно собственного базового приоритета, который всего на пару единиц превышает базовый. Поэтому активный поток имеет преимущество перед потоками "обычных" приложений с нормальным базовым и текущим приоритетом. Но в системе могут крутиться потоки и с более высоким приоритетом - системные, мультимедийные или просто сами себе задающие более высокий приоритет (например, менеджер задач или ProcessExplorer Руссиновича).
Но главное, второе - повышенный приоритет имеет только поток, владеющий активным окном, а все доп.потоки, которые он создает получают базовый приоритет процесса, т.е. по умолчанию нормальный, а не повышенный (и уж никак не "наивысший"). Соотв-но у этих потоков нет никаких особых преимуществ перед другими нормальными потоками в системе.

На одном и том же ПК и в одной и той же программе:

#include <string>
#include <iostream>
#include <Windows.h>
#include <omp.h>
 
using namespace std;
 
struct Result
{
  LARGE_INTEGER StopTime, StopTimeNthread, Freq, StartTime, StartTimeNthread;
  double ElapsedTime, ElapsedTimeNthread;
  double nRes, nResNthread;
  int nthread;
};
 
Result res;
 
void sum_arr(int* a, long long int n) // обычная функция
{
  QueryPerformanceCounter(&res.StartTime);
  for(long long int i = 0; i < n; ++i)
  {
    res.nRes += a[i];
  }
  QueryPerformanceCounter(&res.StopTime);
}
 
void sum_arr_omp(int* a, long long n) // обычная функция
{
  res.nthread = omp_get_max_threads();
  long long int sum = 0;
  QueryPerformanceCounter(&res.StartTimeNthread);
  #pragma omp parallel shared(a) reduction (+: sum) num_threads(res.nthread)
  {
   #pragma omp for
   for(long long i = 0; i < n; ++i)
   {
     sum += a[i];
     //cout << omp_get_thread_num() << endl;
   }
  } // #pragma omp parallel
  QueryPerformanceCounter(&res.StopTimeNthread);
  res.nResNthread = (double)sum;
}
 
int main()
{
  setlocale(LC_ALL, "");
  double nTime;
  long long int nMax = 100000000; // nMax = 100000000 - работает на планшете
  //long long int nMax = 20;
  QueryPerformanceFrequency(&res.Freq);
    int* a = (int*)malloc(sizeof(int)*nMax);
    if(a == NULL)
    {
      cout << "Can`t get memory for array a" << endl;
      system("\npause");
      exit(1);
    }
    for(long long int i = 0; i < nMax; ++i)
    {
      a[i] = 1;
    }
    sum_arr(a, nMax);
    sum_arr_omp(a, nMax);
    free(a);
  nTime = ((double)res.StopTime.QuadPart - (double)res.StartTime.QuadPart)/((double)res.StopTimeNthread.QuadPart
        - (double)res.StartTimeNthread.QuadPart);
  cout  << nTime << "\t\tefficiency of use " <<  res.nthread << " threads"  << endl;
  if(res.nRes != res.nResNthread)
    cout << "!!! Error" << endl;
  system("\npause");
  return 0;
}

в режиме отладки VS2010 дает выигрыш 2.5, а CodeBlocks с MinGW - 4.5. Почему так сильно отличаются результаты? Проект прикрепил.
Прикреплённый файлCpuGpuForum.zip (3,08 Кбайт, скачиваний: 73)

Я получил результаты, указанные в приложении. У меня возникло предположение, что библиотека POSIX threads, которую, по всей видимости, использует CodeBlocks в OpenMP, более эффективна, чем библиотеки Visual Studio. Правильно ли мое предположение или есть этому другие объяснения?
Прикреплённый файлOpenMP.zip (19,77 Кбайт, скачиваний: 111)

библиотека Visual Studio
мда без меня тут опять туфту будут нести

Сообщение отредактировано: Cfon - 23.05.17, 13:15

Ну не так выразился, но смысл то понятен. Ведь работа с потоками в Visual C++ реализована, наверное, а виде какого-то класса и может быть реализована в dll (библиотеке).

Вообще говоря, для процессора "2 ядра, 4 потока" выигрыш в 2.5-3 раза является более ожидаемым\правдоподобным, чем в 4 и тем более в 4.9 раза. Скорее всего тут не обошлось без доп.оптимизаций не на уровне потоков, а в реализации цикла (например с использованием SIMD для сложения нескольких int за одну команду).

К тому же не совсем понятно, запускаешь ли ты прогу из IDE, или же кликом на exe из эксплорера. Если из IDE, то тут могут замешиваться доп.факторы, которые не имеют отношения к делу (например, тот же базовый приоритет процесса и соотв-но его потоков по умолчанию наследуются от родительского процесса). И почему сравниваешь дебажные версии, а не релизные?

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