3 базовых вещи относительно параллельных вычислений, и они же - 3 основные ошибки, которые часто допускают программисты при реализации параллельных алгоритмов. Ошибки в том плане, что они могут серьёзно снижать производительность и приводить не к ожидаемой линейной масштабируемости, а к супер-линейной деградации производительности при увеличении количества процессоров/ядер.
Они абсолютно иррелевантны используемой технологии, будь то Threading Building Blocks, Task Parallel Library, Java Fork/Join, OpenMP, Cilk, Parallel Pattern Library или же что-то кустарного производства. Даже Intel Concurrent Collections, которая позиционируется как "No knowledge of parallel technologies required to write correct programs that execute in parallel", на самом деле подвержена в той или иной степени этим моментам.
Итак, первый момент - гранулярность элементов работы. Что бы достичь хорошей производительности, гранулярность элементов работы должна быть тщательно выбрана. Слишком мелкие элементы работы будут вносить колоссальные накладные расходы. Слишком большие - не будут давать достаточного параллелизма.
Рассмотрим более детально. Когда я тестировал на разных компьютерах издержки TBB на синтетическом бенчмарке, то у меня получались издержки примерно в 500-600 тактов на 1 задачу (task). Т.е. если мы вложим в каждую задачу полезной работы на 10 тактов, то получим издержки примерно в 5 000%. Очень ориентировочно минимальный объём полезной работы на задачу должен быть порядка 10 000 тактов (тогда издержки будут примерно 5%). По поводу максимального размера задачи сказать сложнее, но, по крайней мере, общее количество задач должно быть не меньше чем, ну скажем, 16*количество_ядер (для обеспечения балансировки нагрузки), и так же абсолютный размер задачи должен быть в разумных пределах, скажем, не больше 100 мс, если речь идёт о клиентском приложении. Т.к. последняя оставшаяся задача, по несчастливому стечению обстоятельств, может начать выполняться как раз в тот момент, когда все остальные задачи уже как раз выполнены, т.о. время её выполнения будет прибавлено к общему времени выполнения алгоритма (последняя задача как бы не будет распараллелена).
Чрезмерное разделение данных. Для того, что бы достичь хорошей масштабируемости, каждый поток должен работать преимущественно со своими индивидуальными данными. Такой "невинный" факт, что каждый поток, на каждой итерации изменяет какую-то глобальную переменную (или ограниченный набор переменных) может (и будет) приводить не к ожидаемой линейной масштабируемости, а к супер-линейной деградации производительности. Тут так же надо учитывать тот факт, что аппаратное обеспечение считает "индивидуальными данными" не различные переменные на уровне исходного кода, а различные кэш-линии (т.н. false-sharing).
К этой проблеме более склонны низкоуровневые модели программирования (OpenMP, TBB tasks), в то время как более высокоуровневые модели (алгоритмы TBB - parallel_reduce, parallel_scan; Intel Concurrent Collections) способы содержать в себе больше "интеллекта" для предотвращения проблемы.
Локальность. Не смотря на то, что подсистема памяти современного компьютера всё ещё называется RAM (random-access memory, память с произвольным доступом), сейчас она является чем-то типа сложной распределенной гетерогенной иерархической системы. К счастью, есть очень простые правила как использовать её эффективно:
Предпочитайте последовательный доступ к памяти (иронично по отношению к названию памяти - "память с произвольным доступом").
Используйте все, загруженные в кэш, данные.
Повторно используйте данные, пока они ещё в кэше.
Более коротко: локальность и предсказуемость. Причём локальность как в пространстве, так и во времени. Т.е. RAM лучше не использовать как RAM
Хотя рекомендация локальности обращений к памяти сейчас одинаково применима и к однопоточному программированию, в многопоточном программировании (например, в модели, основанной на задачах - tasks) сложнее понять, например, будет ли у нас последовательный доступ к данным или нет. И опять же, более высокоуровневые модели менее подвержены этой проблеме.