Я пишу программу на 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 значительно хуже серийной версии, и я почти уверен, что это моя вина. Можете ли вы мне помочь?
🤔 А знаете ли вы, что...
C является основным языком для разработки ядра операционных систем.
#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);Использование шагов дает определенные преимущества в производительности. В частности, шаги дают преимущества, когда исходное количество итераций цикла велико по сравнению с шагом. Одновременная отправка меньшего количества блоков означает, что больше времени тратится на выполнение кода этих блоков, чем на их отправку. Однако, как и в случае с любым другим показателем производительности, вам, возможно, придется поиграть со значением шага, чтобы найти наиболее эффективное значение для вашего кода.
Их пример не идеален, но он иллюстрирует идею.