Параллельное матричное произведение

Question

Чтобы рассчитать произведение между двумя матрицами A и B (измерение nxm) в параллельном режиме, у меня есть следующие ограничения: сервер отправляет каждому клиенту количество строк из матрицы A и количество строк изматрица B. Это не может быть изменено.Кроме того, клиенты могут обмениваться друг с другом информацией, чтобы вычислить матричный продукт, но они не могут просить сервер отправить какие-либо другие данные.

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

Из того, что я исследовал, практически наибольшее количество сообщений, которыми обмениваются клиенты, - это n^ 2, если каждый процесс передает свои строки всем остальным.Теперь проблема в том, что если я минимизирую количество отправленных сообщений - это будет около log (n) для распределения входных данных - но тогда вычисления будут выполняться только одним процессом или более, но в любом случае это не так.больше делать параллельно, что и было главной идеей проблемы.

Какой может быть более эффективный алгоритм, который бы вычислял этот продукт?

(я использую MPI, если он делает какие-либоразница).

Answer 1

Для вычисления матричного произведения C = A x B элемент за элементом вы просто вычисляете C(i,j) = dot_product(A(i,:),B(:,j)). То есть (i, j) элемент C является точечным произведением строки i в A и столбца j в B.

Если вы настаиваете на отправке строк A и строк B вокруг, тогда вам будет непросто написать параллельную программу, производительность которой превосходит простую последовательную программу. Скорее, то, что вам следует сделать, это отправить строки A и столбцы B процессорам для вычисления элементов C. Если вы вынуждены отправлять строки A и строки B, то я предлагаю сделать это, но вычислить Продукт на сервере. То есть игнорируйте все рабочие процессоры и просто выполняйте вычисления последовательно.

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

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

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

Как уже говорилось, ваша проблема не является разумной. Либо установщик проблемы неверно определил его, либо вы неправильно указали (или неправильно поняли) правильную спецификацию.

Answer 2

Я не знаю, если это домашнее задание. Но если это не домашняя работа, то вам, вероятно, следует использовать библиотеку. Одна идея - скальпак

http://www.netlib.org/scalapack/scalapack_home.html

Scalapack написан на фортране, но вы можете вызвать его из c ++.

Answer 3

Что-то не так: если обе матрицы имеют n x m размерности, то их нельзя умножить вместе (если только n = m).В случае A * B у A должно быть столько столбцов, сколько у B строк.Вы уверены, что сервер не отправляет строки с транспонированием B?Это было бы равносильно отправке столбцов из B, и в этом случае решение тривиально.

Предполагая, что все эти данные проверены, и ваши клиенты действительно получают строки из A и B: вероятно, самое простое решение будеткаждый клиент отправляет свои строки матрицы B клиенту № 0, который повторно собирает исходную матрицу B, а затем отправляет свои столбцы обратно другим клиентам.По сути, клиент № 0 будет действовать как сервер, который действительно знает, как эффективно декомпозировать данные.Это были бы 2*(n-1) сообщения (не считая тех, которые использовались для воссоединения матрицы продукта), но, учитывая, что вам уже нужны n сообщения для распределения матриц A и B между клиентами, нет существенной потери производительности (это все еще O(n) сообщений).

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