Производительность OpenMP

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

Я распараллеливал массивный внешний цикл. Количество итераций цикла варьируется, как правило, между 20-150, но тело цикла выполняет огромную работу, вызывая множество локальных алгоритмов интенсивной линейной алгебры (как и в, код является частью источника, а не внешней зависимости), Внутри тела цикла есть 1000+ вызовов этих подпрограмм, но они полностью независимы друг от друга, поэтому я решил, что это будет главный кандидат на parallelism. Код цикла - С++, но он вызывает много подпрограмм, написанных на C.

Код выглядит следующим образом:

<declare and initialize shared variables here>
#ifdef _OPENMP
#pragma omp parallel for                            \
  private(....)\
  shared(....)              \
  firstprivate(....) schedule(runtime)
#endif
  for(tst = 0; tst < ntest; tst++) {

     // Lots of functionality (science!)
     // Calls to other deep functions which manipulate private variables only
     // Call to function which has 1000 loop iterations doing matrix manipulation
     // With no exaggeration, there are probably millions 
     // of for-loop iterations in this body, in the various functions called. 
     // They also do lots of mallocing and freeing
     // Finally generated some calculated_values

     shared_array1[tst] = calculated_value1;
     shared_array2[tst] = calculated_value2;
     shared_array3[tst] = calculated_value3;

 } // end of parallel and for

// final tidy up

Я полагаю, что никакой синхронизации вообще не должно быть - единственный раз, когда потоки доступа к общей переменной являются shared_arrays, и они получают доступ к уникальным точкам в тех массивах, индексированных tst.

Вещь, когда я увеличиваю количество потоков (в многоядерном кластере!). Скорости, которые мы видим (где мы вызываем этот цикл 5 раз), выглядят следующим образом:

              Elapsed time   System time
 Serial:        188.149          1.031
 2 thrds:       148.542          6.788
 4 thrds:       309.586        424.037       # SAY WHAT?
 8 thrds:       230.290        568.166  
16 thrds:       219.133        799.780

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

Я пробовал с огромным диапазоном параметров OMP_SCHEDULE, но не повезло. Связано ли это с тем, что каждый поток использует malloc/new и free/delete много? Это постоянно работает с памятью 8 ГБ, но я предполагаю, что это не проблема. Честно говоря, огромный рост системного времени делает его похожим на потоки, которые могут блокироваться, но я не знаю, почему это произойдет.

ОБНОВЛЕНИЕ 1 Я действительно думал, что ложное совместное использование будет проблемой, поэтому переписал код так, чтобы циклы сохраняли свои вычисленные значения в локальных массивах потоков, а затем копировали эти массивы в общий массив в конце. К сожалению, это не оказало никакого влияния, хотя я почти не верю в это.

Следуя совету @cmeerw, я запустил strace -f, и после инициализации есть только миллионы строк

[pid 58067] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58066] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)
[pid 58065] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)
[pid 57684] <... futex resumed> )       = 0
[pid 58067] <... futex resumed> )       = 0
[pid 58066] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58065] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58067] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58066] <... futex resumed> )       = 0
[pid 57684] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid 58065] <... futex resumed> )       = 0
[pid 58067] <... futex resumed> )       = 0
[pid 57684] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)
[pid 58066] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid 58065] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58066] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)
[pid 57684] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58065] <... futex resumed> )       = 0
[pid 58066] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 57684] <... futex resumed> )       = 0
[pid 58067] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid 58066] <... futex resumed> )       = 0
[pid 58065] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58067] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)
[pid 58066] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid 57684] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58065] <... futex resumed> )       = 0
[pid 58067] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58066] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)
[pid 57684] <... futex resumed> )       = 0
[pid 58067] <... futex resumed> )       = 0
[pid 58066] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58065] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid 58066] <... futex resumed> )       = 0
[pid 58065] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)
[pid 58066] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid 57684] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58067] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid 58066] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)
[pid 58065] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 57684] <... futex resumed> )       = 0

У кого-нибудь есть идеи, что значит? Похоже, что потоки слишком часто переключаются по контексту или просто блокируются и разблокируются? Когда я strace та же реализация с OMP_NUM_THREADS установлена в 0, я ничего не получаю. Для некоторого сравнения файл журнала, сгенерированный при использовании 1 потока, составляет 486 Кбайт, а файл журнала, созданный при использовании 4 потоков, составляет 266 МБ.

Другими словами, параллельная версия вызывает дополнительные 4170104 строки файла журнала...

ОБНОВЛЕНИЕ 2

Как предложил Том, я попытался привязать потоки к конкретным процессорам безрезультатно. Мы находимся в OpenMP 3.1, поэтому я устанавливаю переменную среды с помощью export OMP_PROC_BIND=true. Тот же самый файл журнала и тот же таймфрейм.

ОБНОВЛЕНИЕ 3

Сюжет сгущается. До сих пор я только профилировал кластер, я установил GNU GCC 4.7 через Macports и скомпилировал (с openMP) на моем Macbook в первый раз (Apple GCC-4.2.1 подбрасывает ошибку компилятора при включенном OpenMP, и именно поэтому я не компилировался и не запускал его параллельно локально до сих пор). В Macbook вы видите основную тенденцию, которую вы ожидаете

                C-code time
 Serial:         ~34 seconds
 2 thrds:        ~21 seconds
 4 thrds:        ~14 seconds
 8 thrds:        ~12 seconds
16 thrds:         ~9 seconds

Мы видим, что результаты возвратов к концам уменьшаются, хотя это вряд ли удивительно, поскольку пара наборов данных, которые мы повторяем на этих тестовых данных, имеет < 16 членов (поэтому мы генерируем 16 потоков для, например, for-loop с 7 итерациями).

Итак, теперь остается вопрос - ПОЧЕМУ производительность кластера ухудшается настолько плохо. Сегодня вечером я собираюсь попробовать другой четырехъядерный linuxbox. Кластер компилируется с GNU-GCC 4.6.3, но я не могу поверить, что само по себе это будет иметь такое значение?

В кластере не установлены ltrace и GDB (и я не могу получить их по разным причинам). Если мой linuxbox дает производительность, похожую на кластер, я проведу соответствующий анализ ltrace.

ОБНОВЛЕНИЕ 4

О, мой. Я поединок загрузил свой Macbook Pro в Ubuntu (12.04) и перезапустил код. Все это работает (что несколько успокаивает), но я вижу то же самое, странное плохое поведение, которое я вижу на кластерах, и тот же запуск миллионов вызовов futex. Учитывая единственную разницу между моей локальной машиной в Ubuntu и OSX - это программное обеспечение (и я использую один и тот же компилятор и библиотеки - по-видимому, не существует различных реализаций glibc для OSX и Ubuntu!) Теперь мне интересно, как-то связано с тем, как Linux планирует/распределяет потоки. В любом случае, находясь на моей локальной машине, вы делаете все в миллион раз легче, поэтому я собираюсь идти вперед и ltrace -f и посмотреть, что я могу найти. Я написал работу для кластеров, которая forks() отключена от отдельного процесса и дает идеальную 1/2 во время выполнения, поэтому определенно можно получить parallelism...

Ответ 1

Итак, после некоторого довольно обширного профилирования (благодаря этому отличному сообщению для информации о gprof и выборке времени с помощью gdb), в котором было написано большую функцию обертки для создания уровня производительности код для профилирования, стало очевидно, что в течение большей части времени, когда я прерывал текущий код с помощью gdb и запускал backtrace, стек находился в вызове STL <vector>, каким-то образом манипулируя вектором.

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

Кажется, что по какой-либо причине (возможно, некоторые статические или глобальные переменные в глубине реализации STL<vector>?), когда есть циклы, проходящие через сотни тысяч итераций параллельно, происходит некоторая глубокая блокировка уровня, которая происходит в Linux ( Ubuntu 12.01 и CentOS 6.2), но не в OSX.

Я действительно заинтригован, почему я вижу эту разницу. Может ли быть разница в том, как реализован STL (версия OSX была скомпилирована в GNU GCC 4.7, так же как и Linux), или это связано с переключением контекста (как предлагает Арне Бабенхауэрхайде).

В заключение, мой процесс отладки был следующим:

Исходное профилирование из R для идентификации проблемы
Убедитесь, что переменные static не действуют как общие переменные
Профилировано с помощью strace -f и ltrace -f, что было действительно полезно при идентификации блокировки как виновника
Профилировано с помощью valgrind для поиска ошибок
Пробовал различные комбинации для типа расписания (автоматический, управляемый, статический, динамический) и размер блока.
Пробовал привязывать потоки к конкретным процессорам
Избегайте ложного обмена, создавая потоки-локальные буферы для значений, а затем реализуйте одно событие синхронизации в конце for-loop
Удалены все mallocing и freeing из параллельного региона - не помогли с проблемой, но обеспечили небольшое общее ускорение
Пробовал различные архитектуры и ОС - на самом деле не помог, но показал, что это проблема Linux и OSX, а не суперкомпьютер и рабочий стол
Построение версии, которая реализует concurrency с помощью вызова fork() - наличие рабочей нагрузки между двумя процессами. Это уменьшило время как на OSX, так и на Linux, что было хорошо
Построен симулятор данных для репликации нагрузки на производственные данные
профилирование gprof
gdb профилирование выборки времени (прерывание и обратная трассировка)
Вычислите векторные операции
Если бы это не сработало, ссылка Арне Бабенхаузерхейд выглядит так, что у него могут быть некоторые важные вещи по проблемам фрагментации памяти с помощью OpenMP

Ответ 2

Трудно точно знать, что происходит без значительного профилирования, но кривая производительности кажется показателем False Sharing...

потоки используют разные объекты, но те объекты оказываются близкими достаточно в памяти, что они попадают в одну и ту же строку кэша, а кеш система рассматривает их как единый кусок, который эффективно защищен аппаратная блокировка записи, которую может удерживать только одно ядро за раз

Отличная статья по теме в Dr Dobbs

http://www.drdobbs.com/go-parallel/article/217500206?pgno=1

В частности, это может привести к тому, что подпрограммы выполняют много malloc/free.

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

Ответ 3

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

Heres python3.2-code, который в основном делает это (вы, скорее всего, не захотите сделать это в python по соображениям производительности), или добавьте for-loop в C-функцию и свяжите это с помощью cython. Я пока показываю его на Python):

from concurrent import futures
from my_cython_module import huge_function
parameters = range(ntest)
with futures.ProcessPoolExecutor(4) as e:
    results = e.map(huge_function, parameters)
    shared_array = list(results)

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

Огромные функции без взаимодействия и небольшие входные значения почти вызывают многопроцессорность. И как только у вас это получится, переключение на MPI (с почти неограниченным масштабированием) не слишком сложно.

С технической стороны переключение контекста AFAIK в Linux довольно дорогое (монолитное ядро с большим объемом памяти ядра), в то время как они намного дешевле на OSX или в микросхеме Hurd (Mach). Это может объяснить огромное количество системного времени, которое вы видите в Linux, но не на OSX.