Скрытие связи в матричном векторном произведении с помощью MPI

#parallel-processing #mpi

#параллельная обработка #mpi

Вопрос:

Мне нужно решить огромное линейное уравнение для нескольких правых частей (скажем, от 20 до 200). Матрица хранится в разреженном формате и распределяется по нескольким узлам MPI (скажем, от 16 до 64). Я запускаю решатель CG на узле ранга 0. Невозможно решить линейное уравнение напрямую, потому что системная матрица будет плотной (Sys = A ^ T * S * A).

Базовое матрично-векторное умножение реализуется как:

 broadcast x
y = A_part * x
reduce y
  

Хотя коллективные операции выполняются достаточно быстро (OpenMPI, похоже, использует двоичное дерево, подобное шаблону связи Infiniband), на него по-прежнему приходится довольно большая часть времени выполнения. По соображениям производительности мы уже вычисляем 8 правых сторон на итерацию (в основном SpM * DenseMatrix, просто для полноты).

Я пытаюсь придумать хорошую схему, чтобы скрыть задержку связи, но у меня пока не было хорошей идеи. Я также стараюсь воздерживаться от обмена данными 1: n, хотя я еще не определил, будет ли проблемой масштабирование.

Любые предложения приветствуются!

Комментарии:

1. Если вы не полностью привержены использованию MPI, это было бы значительно проще в Charm или какой-либо другой более динамичной среде.

Ответ №1:

Если ваша матрица уже распределена, можно ли использовать распределенный разреженный линейный решатель вместо того, чтобы запускать его только на ранге 0, а затем транслировать результат (если я правильно читаю ваше описание ..). Для этого есть множество библиотек, например, SuperLU_DIST, MUMPS, PARDISO, Aztec (OO) и т.д.

Оптимизация «множественных rhs» поддерживается, по крайней мере, SuperLU и MUMPS (не проверял другие, но я был бы ОЧЕНЬ удивлен, если бы они ее не поддержали!), Поскольку они решают AX = B, где X и B — матрицы с потенциально> 1 столбцом. То есть каждый «rhs» хранится как вектор-столбец в B.

Комментарии:

1. К сожалению, это не вариант. На самом деле умножение на системную матрицу включает в себя 2 умножения на A, поскольку мы не вычисляем системную матрицу. Для этого потребуется продукт SpM * SpM. Также большинство этих библиотек являются прямыми решателями и / или не обеспечивают оптимизацию для нескольких rhs.

2. @ebo: Я немного не уверен в вашей терминологии. Системная матрица == A? Если да, не можете ли вы предварительно вычислить его? Что касается оптимизации «множественных rhs», см. Мое редактирование.

3. Что-то вроде A ^ T * S * A. Матрица A разрежена, не помещается на одном узле, не имеет эксплуатируемой структуры, и A ^ T * S * A будет плотной.

Ответ №2:

Если вам не нужно получать результаты старой правой части перед запуском следующего запуска, вы можете попробовать использовать неблокирующую связь (ISend, IRecv) и сообщить результат уже при вычислении следующей правой части.

Но убедитесь, что вы вызываете MPI_Wait перед чтением содержимого передаваемого массива, чтобы быть уверенным, что вы не читаете «старые» данные.

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

Комментарии:

1. Это будет связь 1: n. Использование «простой» прямой связи означало бы потерю эффективной трансляции и сокращение операций.

2. В настоящее время MPI работает над развертыванием MPI-3. С этим стандартом у вас будет MPI_IBcast. Однако это пока недоступно.