Эффективность параллельных вычислений

Быстрее (скорей всего) будет N потоков MPI, в который трудяться по M потоков OpenMP, Но всё это ещё очень зависит от специфики задачи. Т.е. всё равно решать нужно исходя из задачи.

Как максимизировать эффективность?

Зависит от задачи.

Чтобы по возможности все процессоры были задействованы?

Это не всегда повышает эффективность. Оверхед на обмен данными никто не отменял.

>>Представим кластер с N компьютерами. На каждом компьютере M процессоров. Как максимизировать эффективность?

Сильно от характера задачи зависит - каждый вычислительный пакет выкручивается по-своему. Но это свихнешься согласовывать. Легче MPI конечно же.

MPI всё-таки ориентирован именно на низкую пропускную способность канала

Он ориентирован на скорость сетевого обмена, которая для обычных кластеров типа Beowulf конечно же намного ниже скорости доступа к общей памяти. Но на серьезных машинах ситуация меняется (Infiniband).

>>писать на MPI и не париться и не думать ни о чём другом?

Иметь на прицеле Cluster OpenMP, но она пока сливает MPI на большом числе нод.

Представим кластер с N компьютерами. На каждом компьютере M процессоров. Как максимизировать эффективность? Чтобы по возможности все процессоры были задействованы?

Писать в чистом фукциональном стиле, не?

>>Писать в чистом фукциональном стиле, не?

Есть готовый пример какой-нибудь числодробильни, написанной по таким рекомендациям?

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

Есть готовый пример какой-нибудь числодробильни, написанной по таким рекомендациям?

Автор не про числодробильни спрашивал. Конечно, здесь можно на Фортране/Си все заоптимизировать так, что GHC будет нервно курить в сторонке. Но в общем случае, чисто функциональный подход лучше поддается распараллеливанию. И кстати, причем здесь скобочки? Чистая функциональщина - Haskell, да и стат. типизация должна давать прирост скорости.

>>Но в общем случае, чисто функциональный подход лучше поддается распараллеливанию.

Теоретически можно поверить, но на практике-то есть хоть что-нибудь рабочее?

Теоретически можно поверить, но на практике-то есть хоть что-нибудь рабочее?

кастую в тред штангистов :)

Теоретически можно поверить, но на практике-то есть хоть что-нибудь рабочее?

кастую в тред штангистов :)

У хаскеллистов как раз идёт проект по внедрению в практику своих параллельных наработок.

Ссылка на вики.

Подробнее в блоге Well-Typed (1, 2, 3).

> Вопрос вот в чём. Представим кластер с N компьютерами. На каждом компьютере M процессоров. Как максимизировать эффективность? Чтобы по возможности все процессоры были задействованы?

Есть такая штука, называется системный анализ. Вот в нём как раз и решаются такие задачи. Так что можешь к его теории обратиться, всякие задачи оптимизации есть там.

Наверное проще будет экспериментально сравнить =)

Просто-напросто использовать MPI на N*M потоков?

Будет правильней. Ибо:

• MPI давно умеет между процессами одного узла, передавать данные напрямую, не используя сетевые интерфейсы.
• Всё одно будешь затыкаться на сетевых обменах
• Скорость и сложность написания кода
• S≤1/(f+(1-f)/p)

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

вот я о чём-то похожем подумал... во-первых, это самый простой вариант, во-вторых, вроде как должно работать... надо проверить и сравнить =)

А что на них будет уже работать? :) Речь идёт о кластере... который специально для подобных штук предназначен.

man Закон Амдала тут больше

>Теоретически можно поверить, но на практике-то есть хоть что-нибудь рабочее?

http://en.wikipedia.org/wiki/Amdahl_law#Criticisms

Представим кластер с N компьютерами. На каждом компьютере M процессоров. Как максимизировать эффективность? Чтобы по возможности все процессоры были задействованы?

man транспьютеры

Как связаны критика простейших выкладок Амдала и функциональный подход к распараллеливанию?

>Есть готовый пример какой-нибудь числодробильни, написанной по таким рекомендациям?

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

ну насчёт фортрана это вряд ли, мерять надо, а вот R таким образом ускоряют

http://dan.corlan.net/R_to_common_lisp_translator/#rationale : http://dan.corlan.net/bench.html

Хотя этот тест однопроцессорный, не интересно.

Так, что выкладки Амдала — про макс % нераспаралелливающегося (последовательного) кода. Процентов последовательного кода меньше (например, в функциональном подходе) — выкладки неприменимы. Хотя тут другой вопрос, про накладные расходы рантайма самого языка возникает (то есть, где этот непараллельный код сидит, в программе, или в рантайме).

>>Так, что выкладки Амдала — про макс % нераспаралелливающегося (последовательного) кода.

Ну вот брехать-то не надо, а? Выкладки Амдала только про максимальный выигрыш во времени, а процент непараллелящегося кода там идет как _внешний_ параметр.

Процентов последовательного кода меньше (например, в функциональном подходе) — выкладки неприменимы.

Бред собачий, выкладки применимы всегда.

>>про накладные расходы рантайма самого языка возникает (то есть, где этот непараллельный код сидит, в программе, или в рантайме).

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

А что на них будет уже работать?

Обычно кластер покупается для совместного использования и там одновременно могут работать задачи и от нескольких пользователей. Исключение составляют только мини-кластера и кластера купленные специально для поддержки одного большого проекта с офигенным финансированием.

то есть, рантайм MPICH добавляет условно X1% накладных расходов языка C runtime в смысле макс. количества последовательного кода. (malloc/free можно пренебречь или сразу выделить статически весь объём). Рантайм какой-нибудь параллельной штанги - X2%. Сама задача вносит Y1% последовательного кода (при императивном C-MPICH подходе) и Y2% последовательного кода в случае параллельной штанги. Плюс Z1%/Z2% затраты на коммуникацию. Получается в случае C/MPICH работа из N частей, в случае пара-штанги из M частей. Подставляем в формулу с английской википедии про закон Амдала, «разбиение работы на N (M) частей, и ускорение общей работы». Выводы — 1. такое-то разбиение удачнее, а такое-то неудачнее. 2. в таких-то задачах накладные расходы параллельной штанги примерно можно оценить так-то. (Y2-Y1) относительно (X2-X1)

чисто функциональный подход лучше поддается распараллеливанию

в контексте задачи разницы никакой, разве что рантайм того же GHC выполнит за тебя часть работы (раскидает зелёные потоки по ядрам, например)

> MPI давно умеет между процессами одного узла, передавать данные напрямую, не используя сетевые интерфейсы.

Это точно. К тому же использование OpenMP вместе с MPI добавит времени на синхронизацию потоков и усложнит отладку гибридного кода.

Как максимизировать эффективность? Чтобы по возможности все процессоры были задействованы?

Странно, вот мне всегда интересно что ждут когда на форуме, не важно ЛОР или ixbt или rsdn задают вопрос, ответ на который не на докторскую диссертацию даже тянет а на целую монографию а-ля «Структуры данных и алгоритмы» в 3 томах

http://developers.slashdot.org/story/11/05/27/1831251/What-Makes-Parallel-Pro...

по-моему, вы преувеличиваете... какая тут монография.

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

вопрос по правде говоря предполагает всего-ничего два варианта ответа...

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

вы только заголовок прочитали или пост целиком?

По традиции Ъ по ссылкам не ходят и посты целиком не читают

Ну тогда всё понятно =)

> Вопрос вот в чём. Представим кластер с N компьютерами. На каждом компьютере M процессоров. Как максимизировать эффективность? Чтобы по возможности все процессоры были задействованы?

Зависит от задачи - размера данных, числа операций на ед данных, интенсивности обменов и тд.

Если говорить за числодробилки, то эффективность использования ими совр кластеров составляет проценты в лучшем случае, а чаще доли процента, причем чем кластер монструознее тем эффективность меньше. Если говорить об актуальных задачах (всякие волновые уравнения, газогидродинамика и тд), то в наст момент не существует тулз для создания эффективных кодов, получите в лучшем случае те самые доли процента загрузки проца. Щас вон екзофлопных систем понастроют - то то будет смеху...

Ой, вот это такая же байка для нубов, как и чудо-неоптимальный qsort. Чисто функциональный стиль вообще неэффективен на вычислительных задачах на современных архитектурах эвм. Распараллеливать проще, но за счет, эм, потери в производительности.

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

Чтобы посчитать задачу параллельно тебе нужно разбить ее на куски и отдать разным процам/ядрам, при этом тебе хочется раздать задачу поровну, чтобы система была нагружена равномерно. Нити начинают рулить тогда, когда ты заранее не можешь очень точно оценить это «поровну».

Например тебе нужно сравнить 2 массива строк. Ты пилишь массив на 2 части и сравниваешь. Вдруг выясняется, что в первой половине строки начинают различаться в среднем раньше => дисбаланс => потеря масшабируемости. Если ты распилишь массив на 20 частей и динамически раскидаешь по тем же 2-м нитям, скорее всего они сбалансируют вычисления.

>> Как максимизировать эффективность?

Зависит от задачи.

Ну-ну. Идеальная эффективность достигается при использовании одного процессора. Независимо от задачи.