Какие намеки на то, что алгоритм должен распараллеливаться?

Question

Мой опыт показывает, что даже при использовании многоядерных процессоров распараллеливание алгоритма не всегда заметно ускоряет его. На самом деле, иногда это может замедлить ход событий. Каковы хорошие намеки на то, что алгоритм может быть значительно ускорен при распараллеливании?

(Конечно, учитывая предостережения с преждевременной оптимизацией и их соотношение со злом)

Answer 1

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

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

[Предостережение к этому, это те архитектуры, которые имеют очень большое нет. из «ядер» (таких как машины подключения 64 000 ядер). Они хорошо подходят для вычислений, которые можно разбить на относительно простые действия, назначенные конкретной топологии (например, прямоугольная сетка).]

Answer 2

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

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

Answer 3

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

Хорошая аналогия - над чем вы могли бы поработать, чтобы у вас была группа друзей, которые могли бы одновременно выполнять разные роли? Например, сборка мебели ikea могла бы хорошо распараллеливаться, если разные люди могут работать на разных участках, но раскатывание обоев может и не происходить, потому что вам нужно делать стены последовательно.

Answer 4

Во-первых, посмотрите эту статью покойного Джима Грея:

Экономика распределенных вычислений

На самом деле, это прояснит некоторые недоразумения на основании того, что вы написали в вопросе. Очевидно, что если менее проблематичным будет решение вашей задачи, то тем сложнее это будет.

Answer 5

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

Answer 6

Что ж, если вам нужно много блокировок, чтобы работать, то это, вероятно, один из тех сложных алгоритмов, которые плохо распараллеливаются. Есть ли какая-либо часть алгоритма, которая может быть разбита на отдельные части, которые не должны касаться друг друга?