OpenMP ускоряет потери

Question

Я использовал OpenMP для ускорения моей программы, которая ищет шаблон в тексте.

Вопрос: Почему происходит потеря скорости в шести и десяти потоках, а затем она увеличивается на восемь и двенадцать (таблица ниже)? Я думал, что линия ускорения должна быть более прямой (больше потоков = увеличение ускорения). Я пытался использовать различный размер текста, алгоритмы и количество блоков, но диаграмма не изменилась.

Информация о программе / устройстве

• текст разделен на 10000 блоков
• omp_max_threads () возвращает 8
• размер текста 40 МБ
• процессор имеет 4 ядра

код

double start = omp_get_wtime();

#pragma omp parallel for shared(pat, blockTxt, numOfBlocks,patSize) private (i) reduction(+:result)
for (i = 0; i < numOfBlocks; i++) {
    result += Alghorithm().naive(pat, blockTxt[i], patSize, blockTxt[i].size());
}


double end = omp_get_wtime();

Диаграмма

Answer 1

Идея о том, что «больше потоков = ускорение увеличивается» в корне неверна. Вы должны стремиться к максимально полному и эффективному использованию аппаратных возможностей, чтобы уменьшить время, необходимое для решения вашей проблемы.

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

1. Разделите работу / проблему на более мелкие части, которые могут быть решены как можно более независимо друг от друга, при этом добавляя как можно меньше дополнительных работать над их рекомбинацией
2. Распределить эти небольшие задачи по различным процессорам, к которым у вас есть доступ, таким образом, чтобы:
   • Все они были заняты
   • У них всех есть работа выполнение этого будет завершено за максимально возможное время между ними
   • Издержки, связанные с распределением работы и ее объединением, настолько малы, насколько это возможно
   • И самое главное, чтобы убедиться, что часть работы, которая не была распараллелена, настолько мала, насколько это возможно

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

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

Теперь, когда у вас фактически есть два аппаратных потока на ядро, остается вероятность того, что каждый из них может позволить лучше использовать имеющееся оборудование. Обычно это не относится к задачам, требующим значительных вычислительных ресурсов, но, по-видимому, это не так, поскольку при использовании 8 потоков ускорение становится немного лучше: оно достигает 4, что, по сути, является абсолютным пределом, которого не должно быть в состоянии go выше (так как у вас есть 4 ядра).

Почему 6 замедляет вас? Что ж, если вы посмотрите на то, какими должны быть ваши цели, вы должны понимать, что с 6 потоками OpenMP, которые делятся между четырьмя ядрами, вы создаете дисбаланс нагрузки между этими ядрами и из-за синхронизации, вызванной финализацией распараллеливания, некоторые из ядрам придется подождать, пока остальные не закончат sh дополнительную работу, которую они выполняют в конце. И этого ожидания достаточно, чтобы подорвать вашу общую эффективность. Идеально для 10 потоков.

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