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

[Олег М]

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

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

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

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

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

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

[leo]

Цитата Олег М @ 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

[leo]

Цитата Олег М @ 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-секундной обработки приходится на создание потока, чтоб его учитывать?

[leo]

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

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

[Олег М]

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

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

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

[leo]

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

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

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

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

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

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

[Pavia]

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]

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

[Pavia]

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

[Qraizer]

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

Добавлено 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.

[leo]

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

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

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

[tuchin]

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

#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)

[tuchin]

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