Разреженное матрично-векторное умножение на разбиение строк - PullRequest
Новая
       53

Разреженное матрично-векторное умножение на разбиение строк

0 голосов
/ 10 мая 2019

Я новичок в средах MPI и параллельных вычислений.У меня есть разные разреженные матрицы из https://sparse.tamu.edu/, и я пытаюсь умножить разреженную матрицу с плотным вектором на разделение строк с размерами N x N и N x 1 соответственно.Я протестирую свою параллельную программу MPI с количеством процессов 1,2,4,8,16.

Я провел некоторое исследование об этом алгоритме и нашел лучшее решение и дорожную карту из этой презентации.https://www.sandia.gov/~mmwolf/presentations/CS591MH/CS591MH_20070913.pdf

Алгоритм такой:

  1. Сначала разбейте всю разреженную матрицу по строкам для каждого процесса, а также разбейте плотный вектор.Для повышения эффективности памяти также храните ненулевые элементы разреженной матрицы.
  2. Перед выполнением любых вычислений отправьте векторный элемент, необходимый для отправки x [j], удаленным процессам с ненулевыми значениями в столбце j.
  3. Выполните вычисления и сохраните результаты каждой строки в выходном векторе.

Я не понял, как указать удаленные процессы для отправки x [j].Если я укажу, как я могу общаться между этими процессами с помощью неблокирующих операций отправки и получения?Должен ли я использовать цикл for для каждой операции отправки?

Заранее спасибо.

1 Ответ

0 голосов
/ 12 мая 2019

Примечание: я решил, как умножить разреженную матрицу - умножение плотных векторов на разбиение по строкам.

В 1D - Разделение разреженных матриц по порядку, сначала я прочитал различные разреженные матрицы из SuiteSparse Matrix Collection (https://sparse.tamu.edu/), используя «mmio.c» из https://math.nist.gov/MatrixMarket/mmio-c.html и разделив эту разреженную матрицу через RowWise на N x (N / p) -матрицы и назначить эти матрицы различным процессам (p = число процессов). После разбиения всей матрицы на разные части я просто создаю (N / p) x 1 плотный вектор для каждого процесса ,

После завершения раздела мне нужно было определить, какие процессы взаимодействуют друг с другом, чтобы неблокирующая связь точка-точка (MPI_Isend и MPI_IRecv) была небольшой. По этой причине мне нужно было создать график взаимодействия задач, который показывает, какие процессы взаимодействуют друг с другом. Процесс может отправить свою плотную векторную часть другим процессам, которые используют этот плотный вектор для локального умножения. Кроме того, процесс может получать различные плотные векторные части от других процессов. Например, после определения этих процессов я получил эти два зависимых процесса.

Пример

Процесс 0

Отправить иждивенцев

Процесс 1 Процесс 5 Процесс 6

Получите иждивенцев

Процесс 10 Процесс 13

Просматривая эти зависимые процессы, я использовал два цикла for в каждом процессе для отправки своей плотной векторной части и получения другой плотной векторной части от других процессов, используя неблокирующую двухточечную связь (MPI_Isend и MPI_Irecv). Для ожидания всех запросов на отправку и получение я использовал функцию MPI_Waitall.

В качестве заключительной части я реализовал разреженную матрицу - плотное векторное умножение.

...