Skip to content

report.md

Latest commit

 

History

History
81 lines (64 loc) · 6.52 KB

report.md

File metadata and controls

81 lines (64 loc) · 6.52 KB

Умножение разреженных матриц. Элементы типа double. Формат хранения матрицы – столбцовый (CCS).

  • Student: Агафонов Илья Дмитриевич, group 3823Б1ФИ1
  • Technology: SEQ | MPI
  • Variant: 5

1. Introduction

Задача умножения разреженных матриц является критически важной в научных вычислениях и машинном обучении. Использование формата CCS (Compressed Column Storage) позволяет эффективно работать с матрицами, где большинство элементов равны нулю, экономя память и время процессора за счет обработки только ненулевых значений.

2. Problem Statement

Необходимо реализовать умножение двух разреженных матриц $A$ и $B$ в формате CCS для получения результирующей матрицы $C = A \times B$.

Входные данные:

  • Матрицы $A (m \times k)$ и $B (k \times n)$ в формате CCS.
  • Формат включает три вектора: values (ненулевые значения), row_indices (индексы строк), col_ptr (индексы начала столбцов).

Выходные данные:

  • Результирующая матрица $C (m \times n)$ в формате CCS.

Ограничения:

  • Тип данных — double.
  • Число столбцов $A$ равно числу строк $B$ ($A.n == B.m$).

3. Baseline Algorithm (Sequential)

Последовательный алгоритм использует "столбцовую" логику:

  1. Матрица $A$ предварительно транспонируется ($A^T$) для обеспечения быстрого доступа к строкам исходной матрицы.
  2. Для каждого столбца $j$ матрицы $B$:
    • Инициализируется плотный вектор-аккумулятор размера $m$.
    • Проход по ненулевым элементам $B_{kj}$.
    • Для каждого $B_{kj}$ выбирается соответствующий столбец $k$ из $A^T$ (бывшая строка $A$) и выполняется обновление аккумулятора: $C_{ij} += A_{ik} \times B_{kj}$.
    • Ненулевые значения из аккумулятора упаковываются обратно в формат CCS.

4. Parallelization Scheme

Для распараллеливания используется распределение столбцов выходной матрицы между MPI-процессами:

  • Data Distribution:
    • Процесс 0 транспонирует матрицу $A$ и рассылает её всем узлам через MPI_Bcast.
    • Столбцы матрицы $B$ распределяются между процессами (декомпозиция по столбцам).
  • Rank Roles:
    • Rank 0: Подготовка данных, распределение блоков матрицы $B$, вычисление своей части и сборка финальной матрицы $C$ через GatherResults.
    • Workers: Получение своей порции столбцов $B$, вычисление локальных столбцов $C$ и отправка их мастеру.
  • Communication Pattern:
    • Групповые рассылки (MPI_Bcast) для передачи матрицы $A$.
    • Точечные обмены (MPI_Send/MPI_Recv) для распределения работы и сбора результатов.

5. Implementation Details

  • Код разбит на функциональные блоки:
    • SparseMatrixCCS: Основная структура данных.
    • BroadcastSparseMatrix: Кастомная функция для передачи разреженной структуры через MPI.
    • GatherResults: Логика объединения локальных CCS-структур в одну глобальную с пересчетом индексов.

6. Experimental Setup

Hardware/OS:

  • Процессор: Процессор AMD Ryzen 5 5500U, ядер: 6, логических процессоров: 12
  • Оперативная память: 16 ГБ DDR4
  • Операционная система: Windows 10 Pro 22H2
  • Toolchain:
    • Компилятор: g++ 13.3.0
    • Тип сборки: Release (-O3 )
    • MPI: Open MPI 4.1.6

7. Results and Discussion

7.1 Correctness

Корректность подтверждена успешным прохождением тестов agafonov_i_sparse_matrix_ccs_func, где результаты параллельной версии сравнивались с последовательным эталоном. Все тесты PASSED.

7.2 Performance

На основе замеров в режиме Release на 4 процессах:

Mode Count Time, s Speedup Efficiency
seq 1 0.0195 1.00 100
mpi 4 0.2072 0.52 11.2%

* Примечание: На матрицах время пересылки данных (коммуникационная составляющая) превышает время вычислений. Для получения ускорения требуются матрицы размерностью от 3000x3000 и выше.

8. Conclusions

Алгоритм успешно реализован и проходит все тесты на корректность. Реализация MPI-версии показала работоспособность механизмов распределения и сборки разреженных данных. Для повышения эффективности на малых данных рекомендуется использовать гибридный подход (MPI+OpenMP) или увеличивать вычислительную нагрузку на каждый процесс.

9. References

  1. Материлы и документация по курсу
  2. MPI Standard Specification: [https://www.mpi-forum.org/].