LINUX.ORG.RU

OpenMP ускоряет но маловато

 ,


0

4

Привет! Я обрабатываю матрицу MxN данных (выделена одним блоком данных через просто malloc), скажем объёмом 5 Гб. Каждая строка может обрабатываться независимо от других, и это похоже отличный кандидат на использование OpenMP:

const int M = ...;
const int N = ...;

int *data = malloc(M * N * 4);

#pragma omp parallel for
for (m = 0; m < M; m++) {
    const int *line = data + N * m * 4;
    consume_line(line, N);
}

С использованием OpenMP вижу ускорение в три раза на 8-ми ядерном CPU. Как-то маловато. От системы не зависит, даже на MSVC результат схож с GCC на Ubuntu.

Вопрос - а что ж 3x так мало? Можно ли ускорить ещё?

Каждая строка

Мало, надо дробить на крупные блоки из строк. А на видеокартах операции тайлами обычно делают.

ЗЫ пока из профайлера запуск потоков не станет мизерным, можно увеличивать размер блоков.

ac130kz ★★
()
Последнее исправление: ac130kz (всего исправлений: 1)

Диванная аналитика.

Попробуй вместо блоба data нааллоцировать отдельных line. Тут линейная локальность данных ненужна и даже вредна, так как она полезна когда ты текущей итерацией кешируешь часть будующих данных на следующую итерацию в однопоточке, а когда операции явно раскидываются по ядрам, выборка из общего data будет такова что будет захватываться части общих данных просто из за зармера кеш линии и один будет ждать второго и так далее так как должна быть сохранена консистентность памяти ведь ты туда пишешь, а не просто читаешь, вот если бы просто читал то да всё был бы ок. Или выравнивай line по размеру кеш линии проца. Так что-бы размер line был ему кратен если это возможно в твоём алгоритме. Да ты потеряешь время на аллокациях. ИМХО

LINUX-ORG-RU ★★★★★
()
Последнее исправление: LINUX-ORG-RU (всего исправлений: 6)
Ответ на: комментарий от ac130kz

На карточках аппаратно работают с Z-curve (кривая Мортона/Гильберта) данными, где курва йя пердоле :D и формируется и читается аппаратно как независимый блок данных и пуляется в шейдерное ядрышко. Ключевое слово аппаратно ЕМНИП вроде Так что не возникает конфликта записи когда куски считываемых/записанных данных перекрывают друг друга. А тайлы это уже чуть про другое.

LINUX-ORG-RU ★★★★★
()

Вопрос - а что ж 3x так мало?

Не видя consume_line, сложно сказать, но вангую, что все упирается в контролер памяти.

Можно ли ускорить ещё?

Если дело действительно в памяти, то скорее всего нельзя, разве что выравнивание строк проверить.

arax ★★
()
Ответ на: комментарий от sshestov

В consume_line сильно сложная логика?

достаточно сложная, можно что-то с ней сделать теоретически? У меня же и так параллельно всё. Не думаю что распараллеливание внутри consume_line что-то даст, хотя может ошибаюсь?

former_anonymous ★★★
() автор топика

Можно ли ускорить ещё?

А ты выясни, во что оно упирается? Судя по «в три раза на 8-ми ядерном CPU», возможно, что и в ПСП.
Если есть возможность, проще всего потестить на чем-нибудь многоканальном типа эпика, где прибить потоки к ядрам на разных чиплетах, и соответственно разложить данные.

GAMer ★★★★★
()
Последнее исправление: GAMer (всего исправлений: 1)
Ответ на: комментарий от former_anonymous

Действительно. Я почему-то думал, что по-умолчанию используется schedule(static,1).

private() и firstprivate() создают отдельные инстансы переменных для каждого треда - так можно избавиться от ненужной конкуренции за переменную. Может быть актуально, если переменная меняется в цикле или не объявлена как const.

У тебя, вот, кстати, m определена не в самом цикле, судя по коду, а где-то ранее. Попробуй её тоже в private() присунуть.

А вообще, если у тебя в consume_line() всё обмазано симдами, то, возможно, что просто проц троттлит на таких вычислениях. Либо ты действительно упёрся в память и/или часто промахиваешься по кешам.

man perf

anonymous
()

Вообще, такие вопросы надо профилировщику задавать, а не нам. Это во-первых.

Во-вторых, задача перемножения матриц чуть ли не каконiчная при изучении параллельных алгоритмов. Вот примеры на OpenMP.

DarkAmateur ★★★★
()
Ответ на: комментарий от former_anonymous

Спрошу на всякий случай: а у нас же m и line - они private? (в первом примере написано наоборот, но я полагаю лень было ctrl-C - ctrl-V полностью).

Как еще один вариант могу предложить потреблять не строку, а что-нибудь меньшим объемом. Если, конечно, задача это позволяет. Хорошо бы примерно хоть представлять что внутри consume_line происходит (но это, очевидно, коммерческая тайна).

sshestov ★★
()
Ответ на: комментарий от sshestov

Спрошу на всякий случай: а у нас же m и line - они private?

Ну по логике да, line ведь внутри цикла объявляется. m - объявлен снаружи цикла, но это же итератор в терминах openmp, он имеет уникальное значение для каждого потока.

former_anonymous ★★★
() автор топика

Вопрос - а что ж 3x так мало?

Я бы попробовал выяснить источник проблемы по двум вариантам - либо это сам алгоритм consume_line(), либо это немного не правильное использование omp (синтаксис или логика или еще что-то).

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

  • Если время будет примерно одинаково - значит либо функция consume_line() слишком быстра (больше времени уходит на синхронизацию при создании/удалении потоков, чем на полезную работу каждого потока), либо экземпляры функции consume_line() дерутся за другой ресурс (например нехватка ОЗУ, нехватка кэша процессора и т.п.). Тут поможет только пересмотр алгоритма в consume_line().

  • Если время на обычных потоках будет близко к ожидаемому (ускорению в 7-8 раз на 8 потоках) - значит что-то не так с использованием omp и нужно разбираться с применением omp.

И еще. Одно дело, если у вас без потоков время работы занимало 10 сек., а с omp потоками 3 сек. И совсем другое дело, если у вас без потоков 10 часов, а с omp потоками 3 часа. И там и там ускорение примрерно в 3 раза, но возиться и ускорять условные 3 сек. уже врятли имеет смысл, а вот ускорять 3 часа вполне разумное желание.

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

Vic
()
Последнее исправление: Vic (всего исправлений: 4)