Отправка Apple против OpenMP для распараллеливания цикла for на Apple MacBook Pro с помощью M3Pro
Я пишу программу на C, которая принимает массив размером 2N и меняет местами записи, индексы которых отличаются на один бит в указанной позиции в двоичных представлениях индексов.
Профилируя код, я заметил, что по умолчанию он разворачивает только один поток, что делает его очень медленным. Я попробовал OpenMP, а также Apple Dispatch (ранее Grand Central Dispatch), чтобы распараллелить свой код, но результаты меня немного разочаровали.
Есть ли кто-нибудь более опытный в этих фреймворках и может мне помочь?
Стоит ли мне обратить внимание на Металл?
Моя идея распараллеленной версии моего кода состоит в том, чтобы перебрать все целые числа до 2N-1-1, вставить ноль в указанную позицию справа и поменять местами запись, индекс которой находится на расстоянии 2pos. Версия, которую я реализовал с помощью OpenMP, выглядит так:
void swapEntries(double complex* array, uint64_t N, uint64_t pos) {
uint64_t swapDistance = 1 << pos // 2^pos is the distance between entries to swap
uint64_t indices = 1 << (N - 1) // 2^(N-1) is the max integer missing a zero at pos
#pragma omp parallel for default(none) shared(array, indices, pos, swapDistance)
{
for (uint64_t i = 0; i < indices; ++i) {
uint64_t left = (i & (~0U << pos)) << 1; // Copy the bits left to pos and shift
// them one position to the left
uint64_t right = (i & ~(~0U << pos)); // Copy the bits right of pos
i = (left | right); // Merge the two integers (now with a
// zero at pos)
double complex tmp = *(array + i); // Swap the entry with the one
*(array + i) = *(array + (i + swapDistance)); // swapDistance away
*(array + (i + swapDistance)) = tmp;
}
};
}
На экземпляре с N=30 при использовании clang от Apple с флагом -O2 он работает почти в два раза быстрее, чем его серийная версия. Я нахожу это весьма отрезвляющим, учитывая тот факт, что мой MacBook M3 с M3Pro имеет 11 ядер (даже если 7 из них являются ядрами эффективности).
На следующем этапе я попробовал библиотеку Apple Dispatch, используя простое преобразование цикла, приведенное в википедии и также упомянутое в документации.
void swapEntries(double complex* array, uint64_t N, uint64_t pos) {
uint64_t swapDistance = 1 << pos // 2^pos is the distance between entries to swap
uint64_t indices = 1 << (N - 1) // 2^(N-1) is the max integer missing a zero at pos
/* Get a concurrent dispatch queue */
dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0)
dispatch_apply(indices, queue, ^(size_t) {
uint64_t left = (i & (~0U << pos)) << 1; // Copy the bits left to pos and shift them
// one position to the left
uint64_t right = (i & ~(~0U << pos)); // Copy the bits right of pos
i = (left | right); // Merge the two integers (now with a
// zero at pos)
double complex tmp = *(array + i); // Swap the entry with the one
*(array + i) = *(array + (i + swapDistance)); // swapDistance away
*(array + (i + swapDistance)) = tmp;
});
}
Обе эти функции делают именно то, что должны; У меня есть модульные тесты, чтобы проверить это. Однако реализация Dispatch значительно хуже серийной версии, и я почти уверен, что это моя вина. Можете ли вы мне помочь?
Что касается сравнения эффективности OpenMP и Apple Dispatch, я не могу комментировать, так как у меня вообще нет опыта работы с последним. Просто я бы на 100% выбрал OpenMP, поскольку он широко реализован на каждой платформе и является переносимым (ваша версия Dispatch не может быть скомпилирована/связана с использованием компилятора стороннего производителя, в то время как код OpenMP всегда можно скомпилировать, даже если OpenMP не поддерживается). доступный)
@PierU большое спасибо за ваш комментарий. Мне пришлось искать, что означает код, привязанный к памяти. Если я должен исправить, вы имеете в виду, что время доступа к массиву составляет большую часть времени в моем коде, а не элементарные вычисления над записями. Как вы думаете, смогу ли я в этой конкретной задаче обменять вычисления на границы памяти? Или лучше распараллелить программы, вызывающие эту программу, и оставить это как последовательное вычисление?
Что касается упомянутого вами состояния гонки, можете ли вы предоставить ссылку, в которой вы видите потенциальную угрозу? Я написал несколько модульных тестов, и все они сработали довольно хорошо. Однако я думаю, что максимальное использованное N было 4.
У меня нет четкого представления о том, как работает ваш код, так что, возможно, все в порядке. Но является ли переопределение i внутри цикла (вместо использования временной переменной) преднамеренным? Если да, то я действительно сомневаюсь, что это безопасно с несколькими потоками...
Что касается производительности, вы склонны писать в массиве совершенно случайно, что потенциально может создать так называемое «ложное совместное использование».
Ваш код не компилируется из-за отсутствия ; после строк 2 и 3. Кроме того, наличие блока кода ({) между omp parallel for и фактическим for-циклом является незаконным. Можно разделить прагму на omp parallel перед { и omp for между { и циклом. Хотя вместо этого я бы просто избавился от блока кода.
Изменение i внутри цикла также незаконно для OpenMP. См. Форма канонического цикла: «[Индекс цикла] не должен изменяться во время выполнения цикла for, кроме incr-expr.», где incr-expr — это ++i в вашем случае.
Кстати, вы описываете Apple Dispatch как «ранее Grand Central Dispatch»… AFAIK, Apple не отказалась от термина GCD. В документации Dispatch написано «Dispatch, также известный как Grand Central Dispatch (GCD)». «НОД» по-прежнему является общепринятым термином.
В ответ на общую проблему производительности мы обычно решаем ее «шагом», выполняя больше работы за итерацию. Прямо сейчас каждая итерация выполняет незначительный объем работы. И особенно в GCD, если у вас очень мало работы на каждой итерации, скромные накладные расходы на многопоточность могут перевесить любой выигрыш в производительности от многопоточности. Как только вы начнете двигаться вперед, (а) производительность каждого из них значительно улучшится; и (б) разница между ними значительно уменьшится.
@Rob По крайней мере, для OpenMP я бы сказал, что важна не рабочая нагрузка на итерацию, а рабочая нагрузка на часть итераций. Здесь размер чанка составляет $2^(N-1)/nthreads", что неплохо при N=30.
@rob, странная часть вычислений слева и справа фактически обеспечивает гарантию того, что у меня есть 0 в бите, представленном swapDistance, и i+swapDistance фактически устанавливает этот бит. Для i=0b1111 и pos=2 у нас будет left=0b11000 и right=0b11, а затем объединим их в i=0b11011. Как отмечали другие, это явно должна быть новая переменная для OpenMP. Мне интересно, откуда я взялся за НОД и каковы там рамки.
@Йоахим – Согласен. Я был преждевременным заявлять, что это не является потокобезопасным (и я удалил этот комментарий), потому что похоже, что индексы i и i+swapDistance никогда не повторяются.
@Joachim - Да, в примере GCD ОП неясно, откуда берется i и какова его сфера применения. Я ожидал увидеть что-то вроде dispatch_apply(indices, queue, ^(size_t i) {…}) с i в качестве параметра блока. Сравнивая его с кодом OpenMP, становится ясно, что i задумывался как индекс цикла. Код ОП у меня даже не компилируется…
@paleonix: Конечно, вы правы относительно пропущенного ; после строк 2 и 3. Я просто пропустил их, редактируя код для вопроса. Под «блоком кода между omp parallel for и фактическим for-циклом...» вы имеете в виду default(none) shared(array, indices, pos, swapDistance)? Если да, то это связано с тем, что моя IDE жалуется на то, что не установлен default(none). @paleonix и @PierU: Спасибо за подсказку, вместо этого я ввел в цикл локальную переменную, содержащую (left | right).
Нет, я имею в виду, что вы не можете использовать этот { (начало нового блока кода) после omp for. Цикл for должен идти сразу после этой прагмы. GCC даже выдает ошибки при компиляции с -fopenmp. Вы можете использовать блок кода {} для определения параллельной области, но когда он объединяет omp parallel с omp for в omp parallel for, это будет применяться только к одному циклу.
Ответы 1
#pragma omp parallel for OpenMP будет выполнять итерации цикла for, и они будут «разделены на смежные непустые подмножества, называемые частями». (См. раздел 11.5.3 Интерфейс прикладного программирования OpenMP . Это также обсуждается в девятом видео серии обучающих материалов Введение в OpenMP.) Разбиение на части максимизирует объем работы в каждом потоке и минимизирует скромные накладные расходы. вводится параллелизмом.
GCD не делает этого за вас, и каждая итерация dispatch_apply будет отправляться отдельно. Если вы хотите разбить работу на части в GCD, вам придется сделать это самостоятельно, проходя по индексам цикла for, а затем внутри блока dispatch_apply вы сами перебираете подмножество индексов.
Конечным результатом является то, что OpenMP сгруппирует работу в минимальное количество фрагментов для желаемого количества потоков, тогда как в вашем примере GCD при отсутствии шагового перемещения существует необычайное количество отдельных диспетчеризаций, при этом накладные расходы на диспетчеризацию быстро компенсируют любые преимущества, предлагаемые параллелизмом.
В GCD мы исправляем это, «шагая», увеличивая объем работы, выполняемой в каждом потоке. Прямо сейчас каждая итерация dispatch_apply (известная как concurrentPerform в Swift) выполняет незначительный объём работы. И особенно в GCD, если у вас очень мало работы на каждой итерации, скромные накладные расходы на многопоточность могут перевесить любой выигрыш в производительности от многопоточности.
Например, возьмем N, равное 30. В примере dispatch_apply это приведет к 536 миллионам (2N-1) отправок. Да, dispatch_apply снизит риск взрыва потока (ограничив количество активных потоков количеством ядер на устройстве), но он не будет «разбивать» работу за вас. Вы должны сделать это сами.
Для получения дополнительной информации о шаге см. раздел «Улучшение кода цикла» устаревшего Apple Concurrency Programming Guide, в котором говорится:
В листинге 5-3 показано, как заменить цикл
forего эквивалентом на основе диспетчеризации. Блок или функция, которую вы передаетеdispatch_applyилиdispatch_apply_f, должна принимать целочисленное значение, указывающее текущую итерацию цикла. В этом примере код просто выводит на консоль номер текущего цикла.Листинг 5-3. Замена цикла for без перехода
queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0); dispatch_apply(count, queue, ^(size_t i) { printf("%u\n", i); });Хотя предыдущий пример является упрощенным, он демонстрирует основные методы замены цикла с помощью очередей отправки. И хотя это может быть хорошим способом повысить производительность кода, основанного на циклах, вы все равно должны использовать этот метод с умом. Хотя очереди отправки имеют очень низкие накладные расходы, планирование каждой итерации цикла в потоке все равно требует затрат. Поэтому вам следует убедиться, что ваш код цикла выполняет достаточно работы, чтобы оправдать затраты. Точное количество работы, которую вам нужно выполнить, — это то, что вам нужно измерить с помощью инструментов производительности.
Простой способ увеличить объем работы на каждой итерации цикла — использовать пошаговое выполнение. При использовании страйдинга вы переписываете свой блочный код, чтобы выполнить более одной итерации исходного цикла. Затем вы уменьшаете указанное вами значение счетчика для функции
dispatch_applyна пропорциональную величину. В листинге 5-4 показано, как можно реализовать пошаговое выполнение кода цикла, показанного в листинге 5-3. В листинге 5-4 блок вызывает операторprintfстолько же раз, сколько значение шага, которое в данном случае равно 137. (Фактическое значение шага — это то, что вам следует настроить на основе работы, выполняемой вашим кодом.) Поскольку при делении общего количества итераций на значение шага остается остаток, все оставшиеся итерации выполняются в реальном времени.Листинг 5-4. Добавление шага в отправленный цикл for
int stride = 137; dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0); dispatch_apply(count / stride, queue, ^(size_t idx){ size_t j = idx * stride; size_t j_stop = j + stride; do { printf("%u\n", (unsigned int)j++); } while (j < j_stop); }); size_t i; for (i = count - (count % stride); i < count; i++) printf("%u\n", (unsigned int)i);Использование шагов дает определенные преимущества в производительности. В частности, шаги дают преимущества, когда исходное количество итераций цикла велико по сравнению с шагом. Одновременная отправка меньшего количества блоков означает, что больше времени тратится на выполнение кода этих блоков, чем на их отправку. Однако, как и в случае с любым другим показателем производительности, вам, возможно, придется поиграть со значением шага, чтобы найти наиболее эффективное значение для вашего кода.
Их пример не идеален, но он иллюстрирует идею.
Большое спасибо за подсказку. Мне удалось изменить свой код, и теперь его производительность соответствует производительности OpenMP.
Какая бы ни была используемая библиотека потоков, не все коды/алгоритмы можно эффективно распараллелить. Обычно коды, привязанные к памяти (т. е. узким местом является пропускная способность шины памяти), не работают быстрее, даже если используется больше ядер, и это, вероятно, имеет место в данном случае. Более того, я подозреваю, что в этом коде есть условия гонки, что делает его некорректным (проверяли ли вы результаты, когда он выполняется более чем в одном потоке?).