В продолжение выпуска 2.

Чтож, попробуем ускорить нашу функцию ещё больше.
Первое, что бросается в глаза при анализе работы функции из выпуска 2 void f3(double * pdArr) так это неполная загрузка ядер в следствии не очень хорошей балансировки циклов. На этот случай у OpenMP так же есть инструменты. Для балансировки циклов используется директива schedule(type[,size]), подробнее можно почитать тут.
Не вдаваясь в подробности скажу, что наилучший результат дал вариант #pragma omp parallel for schedule(dynamic, 8192). На всякий случай, в качестве параметра, я использую величину, являющейся степенью двойки, на такое число компилятору всяко проще делить (если это ему поможет, а мне уж точно не навредит). Так какой же результат получается с такой директивой? 1.72 секунды, что 2.5 раза быстрее чем однопоточная версия функции. Использование других дериктив и других чисел в размере блока так же может давать прирост в ускорении но не такой значительный. Уменьшение размера блока увеличивает накладные расходы на обслуживание, увеличение — ухудшает балансировку. Т.е. размер блока надо подбирать индивидуально в зависимости от объёма работы, совершаемой в самом теле цикла. И на последок картина, как выглядит выполнение оптимизированной программы в Intel Thread Profiler:

На картинке представлено (как и в прошлый раз) небольшой участок выполнения программы (примерно 4 запуска параллельного цикла). Видно, что балансировка циклов стала почти идеальной (все потоки заканчивают работу практически одновременно). И даже в случае задержки запуска некоторых потоков (как в третьем цикле на картинке) все они завершают работу в один момент. Мы достигли 2.5 кратного ускорения цикла при распараллеливании его на 8 ядер. Результат достаточно посредственный, но это всё же ускорение по сравнению с однопоточной версией. В следующем выпуске исследуем причины такого не самого яркого результата.

В продолжение выпуска 1.

Так вот наблюдательный опытный разработчик конечно же догадался что причиной замедления параллельной версии стала строка #pragma omp critical. Не поставить её было нельзя, т.к. запись происходит в общую, для разных потоков, память. Будет очень показательно взглянуть на картинку, которую нам показывает Intel Thread Profiler в случае цикла с critical:

Верхняя гистограмма показывает что бОльшую часть времени наша функция задействовала всего 2 ядра на машине. По нижней части картинки видно что каждый поток работает лишь небольшую часть времени, потом натыкается на critical секцию и останавливается, передавая управление другому потоку (жёлтые линии). И такая постоянная передача управления стоит совсем не дёшево (от того и замедление в 50 раз).
Но стандарт OpenMP позволяет в данном случае использовать более «мягкую» директиву #pragma omp atomic, но при этом никто не гарантирует что компилятор не заменит её на тот же critical. Давайте проверим компилятор от Майкрософт. Проведём эксперимент с немного изменённой функций:

компилируем, запускаем и получаем ~2.6 секунд (в некоторых запусках бывает заметно больше). Much better! Ускорение в 1.7 раза (на 8 ядрах) относительно однопотоковой версии. И давайте взглянем на картину, которую нам даёт тот же Intel Thread Profiler:

Видим, что теперь функция использует почти всегда все 8 ядер системы, хотя балансировка циклов оставляет желать лучшего, и отдельные потоки заканчивают работу намного раньше других, что приводит к неполной загрузке системы. Жёлтые линии на данной картинке — это запуски цикла, который у меня в тесте запускается 100 раз подряд для получения более точного результата измерения (на картинке представлен только небольшой кусок процесса выполнения программы).

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

Исследования проводились на 8-ядерной машине (2CPU x 4core) Intel(R) Xeon(R) CPU E5530 @ 2.40GHz под управлением операционной системы Microsoft Windows XP Professional x64 Edition Service Pack 2. Все примеры компилировались на Microsoft Visual Studio 2008 Version 9.0.30729.1 SP в конфигурацией Release, OpenMP, с полной оптимизацией, без inline-ов.

для особо любопытствующих представлю «шапку» кода с вспомогательной функцией:

и перейду к делу. Предположим есть у вас большой цикл, совершающий полезное деяние (10 миллионов повторений, прошу заметить)

и хочется вам его распараллелить.

Дело благое, и пользователь должен только сказать Вам спасибо, когда программа съест всю мощь его мультиядерной машины и отработает быстрее. Вот только быстрее-ли? Давайте проверять… Для этого используется следующая функция:

И получаем результат: последовательная (однопоточная) версия отрабатывает за 4.344 секунды, а параллельная (8-поточная) за … 223 секунды! Т.е. в 50 раз медленнее.
Опытный программист конечно же уже знает в чём дело, а я расскажу почему, и продолжу изыскания, в следующем выпуске.