3 базовых вещи относительно параллельных вычислений
От: remark Россия http://www.1024cores.net/
Дата: 19.11.08 20:34
Оценка: 316 (26)
Краткое введение на тему "Почему моя программа на многоядерном процессоре работает медленнее?"


3 базовых вещи относительно параллельных вычислений, и они же — 3 основные ошибки, которые часто допускают программисты при реализации параллельных алгоритмов. Ошибки в том плане, что они могут серьёзно снижать производительность и приводить не к ожидаемой линейной масштабируемости, а к супер-линейной деградации производительности при увеличении количества процессоров/ядер.

Они абсолютно иррелевантны используемой технологии, будь то Threading Building Blocks, Task Parallel Library, Java Fork/Join, OpenMP, Cilk/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) сложнее понять, например, будет ли у нас последовательный доступ к данным или нет. И опять же, более высокоуровневые модели менее подвержены этой проблеме.


Как вывод можно сказать, что по-возможности следует предпочитать как можно более высокоуровневые средства (если таковые имеются для конкретной задачи, и если нет задачи выжать все 100% из железа), т.к. они могут помочь решить часть проблем. В пределе можно использовать вообще готовые библиотечные функции для выполнения типовых задач (операции с векторами и матрицами, обработка аудио/видео, сбор статистики и т.д.). Например, Intel поставляет для этих целей библиотеки IPP (Integrated Performance Primitives) и MKL (Math-Kernel Library), а AMD — Framewave, они не только внутренне распараллелены, но и используют последние наборы команд (SSE4). Если такие библиотеки не предоставляют необходимой функциональности, то придётся делать самому, и тут важно понимать, что никакой магии не произойдёт — необходимо не только правильно записать синтаксис, но и провести хотя бы ограниченный анализ алгоритма и структур данных, что бы удовлетворить вышеуказанные пункты, и не пополнить ряды мистеров-а-почему-моя-программа-стала-работать-медленнее

1024cores — all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re: 3 базовых вещи относительно параллельных вычислений
От: Mamut Швеция http://dmitriid.com
Дата: 14.12.08 20:53
Оценка:
Здравствуйте, remark, Вы писали:

R>Краткое введение на тему "Почему моя программа на многоядерном процессоре работает медленнее?"


Если будет желание дополнить или расширить идею, то это можно будет сделать здесь (логин/пароль — как на RSDN)


dmitriid.comGitHubLinkedIn
Re[2]: 3 базовых вещи относительно параллельных вычислений
От: remark Россия http://www.1024cores.net/
Дата: 14.12.08 21:26
Оценка:
Здравствуйте, Mamut, Вы писали:

M>Здравствуйте, remark, Вы писали:


R>>Краткое введение на тему "Почему моя программа на многоядерном процессоре работает медленнее?"


M>Если будет желание дополнить или расширить идею, то это можно будет сделать здесь (логин/пароль — как на RSDN)


Ок.
А про статус/идею/цель этой штуки где можно почитать?

M>


1024cores — all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[3]: 3 базовых вещи относительно параллельных вычислений
От: neFormal Россия  
Дата: 14.12.08 23:35
Оценка:
Здравствуйте, remark, Вы писали:

R>А про статус/идею/цель этой штуки где можно почитать?


http://wk.rsdn.ru/MainPage.ashx
вика носит экспериментальный характер и, в идеале, должна служить структурированным хранилищем полезной информации из статей и постов на форуме.. чтобы инфа не терялась в куче сообщений..

в разделе "о сайте" несколько топиков на тему вики: http://gzip.rsdn.ru/forum/group/rsdn.aspx

M>>

R>

ммм
...coding for chaos...
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.