Параллельный матричный продукт

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

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

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

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

(Я использую MPI, если это имеет значение).


parallel-processing algorithm matrix mpi
person Clara    schedule 08.12.2010    source источник
comment
Знает ли каждый клиент, какие другие клиенты получили какие строки, или им тоже нужно запрашивать это, чтобы выяснить это?   -  person Anon.    schedule 09.12.2010
comment
Да, каждый клиент может узнать это самостоятельно, рассчитав его.   -  person Clara    schedule 09.12.2010
comment
Вы уверены, что клиенты получают строки матрицы B вместо столбцов? Если это действительно так, то это несколько усложнит задачу.   -  person Martin v. Löwis    schedule 09.12.2010
comment
Действительно, проблема в том, что клиенты получают строки из матрицы B и не имеют достаточно информации для вычисления элемента из результирующей матрицы. Из строк, полученных из матрицы А, остаются неиспользованные элементы, поэтому им необходимо обмениваться информацией с другими клиентами.   -  person Clara    schedule 09.12.2010
comment
Уверен, что это хорошая задача для распараллеливания? Для n узлов потребуется n*n трафика, и в то же время каждый узел будет производить меньше полезной информации на свой трафик.   -  person ruslik    schedule 09.12.2010
comment
Правда, это худший случай, я бы сказал. Однако я подумал о том, что на первом этапе, например, половина клиентов отправляет свою информацию (имеется в виду строки из B и, возможно, также неиспользуемые элементы из A), а другая половина получает. На следующем шаге клиенты, получившие информацию, могли бы фактически отправить дальше то, что они собрали (имеется в виду полученная информация и своя собственная), и это могло бы немного уменьшить трафик...   -  person Clara    schedule 09.12.2010

Ответы (3)


arrow_upward
5
arrow_downward

Чтобы вычислить произведение матрицы 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, то я предлагаю вам сделать это, но вычислить продукт на сервере. То есть игнорировать все рабочие процессоры и просто выполнять вычисления последовательно.

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

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

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

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

person High Performance Mark    schedule 08.12.2010

arrow_upward
0
arrow_downward

Что-то не так: если обе матрицы имеют размерность 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, которая ужасно масштабируется, поэтому, если у вас достаточно маленькие матрицы и много процессов, возможно, вам лучше просто последовательно вычислять продукт на сервере.

person suszterpatt    schedule 09.12.2010
comment
Хорошо, матрицы имеют размеры nxm и mxn, извините, что опускаю эту информацию. Проблема связана с огромными матрицами, с которыми трудно работать, если вы собираетесь брать элементы из B, чтобы отправить столбец. Однако требование заключалось в том, чтобы данные (как матрицы A, так и матрицы B) отправлялись блоками строк — так как они фактически сохраняются в памяти. - person Clara; 10.12.2010

arrow_upward
0
arrow_downward

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

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

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

person nielsle    schedule 09.12.2010