Skip to content

report.md

Latest commit

 

History

History
201 lines (150 loc) · 13.6 KB

report.md

File metadata and controls

201 lines (150 loc) · 13.6 KB
# Минимальное значение элементов матрицы

- Студент: Каур Андрей Михайлович
- Технология: SEQ | MPI
- Вариант: __

## 1. Введение

Поиск минимального элемента матрицы является одной из базовых операций линейной алгебры и важным компонентом во множестве алгоритмов обработки данных, компьютерной графики и др.
В рамках этого исследования проводится сравнительный анализ производительности последовательной и параллельной MPI-реализаций данного алгоритма.

## 2. Постановка задачи

**Цель работы:**
Реализовать последовательную и MPI-параллельную версии алгоритма поиска минимального элемента матрицы, провести их сравнение и анализ эффективности.

**Определение задачи:**
Для матрицы `A` размера `m × n` необходимо определить значение: `min(A) = min(A[i][j])`, где `0 <= i < n`, `0 <= j < m`.

**Ограничения:**
- Матрица должна быть представлена как вектор целых чисел.
- Размеры матрицы могут быть большими.
- Корректность должна сохраняться при любых значениях элементов.
- Результаты SEQ и MPI версий должны совпадать.

## 3. Алгоритм (Последовательная версия)

**Входные данные:** количество строк `rows`, количество колонок `columns`, вектор размера `rows * columns`.

**Выходные данные:** целое число - минимальный элемент матрицы.

**Алгоритм**:
1. Получить входной вектор `matrix`.
2. Присвоить переменной `min_val` значение первого элемента вектора.
3. В цикле пройтись по всем оставшимся элементам, начиная со второго:
   - Записать в `min_val` минимальное значение из текущего элемента и `min_val`.
4. Вернуть значение `min_val`.

**Сложность**: O(n), где `n` - размер вектора `matrix`.

### Код последовательной версии алгоритма
```cpp
bool KaurAMinMatrixSEQ::RunImpl() {
  auto &matrix = std::get<2>(GetInput());

  int min_val = matrix[0];
  for (size_t i = 1; i < matrix.size(); i++) {
    min_val = std::min(min_val, matrix[i]);
  }

  GetOutput() = min_val ;
  return true ;
}

4. Схема распараллеливания

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

  • Инициализация: Все процессы запускаются в коммуникаторе MPI_COMM_WORLD, определяется общее количество процессов и ранг текущего процесса.
  • Распределение данных: Нулевой процесс загружает входную матрицу и вычисляет параметры для распределения данных:
    • Определяет размер каждого блока: part_size = matrix_size / world_size.
    • Распределяет остаточные элементы: первые remainder процессов получают по одному дополнительному элементу, если размер матрицы нацело не делится на количество процессов.
    • Формирует векторы sendcounts (размеры блоков) и displs (смещения в матрице).
  • Широковещательная рассылка: Вектор sendcounts рассылается всем процессам через MPI_Bcast, позволяя каждому процессу определить размер своего локального буфера.
  • Распределение данных: Матрица распределяется между процессами при помощи функции MPI_Scatterv.
  • Локальные вычисления: Каждый процесс находит минимальный элемент в своем локальном буфере.
  • Глобальная редукция: Локальные минимумы со всех процессов объединяются с помощью операции MPI_Allreduce с параметром MPI_MIN.
  • Формирование итога: Глобальный минимум становится доступным на всех процессах одновременно и сохраняется в выходные данные.

Код параллельной версии алгоритма

bool KaurAMinMatrixMPI::RunImpl() {
  int world_size = 1;
  MPI_Comm_size(MPI_COMM_WORLD, &world_size);
  int world_rank = 0;
  MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);

  std::vector<int> matrix;
  std::vector<int> sendcounts(world_size);
  std::vector<int> displs(world_size);
  std::vector<int> local_matrix;

  if (world_rank == 0) {
    auto &input = GetInput();
    matrix = std::get<2>(input);

    size_t matrix_size = matrix.size();
    size_t part_size = matrix_size / world_size;
    size_t remainder = matrix_size % world_size;

    int offset = 0;
    for (size_t i = 0; std::cmp_less(i, world_size); ++i) {
      sendcounts[i] = static_cast<int>(part_size) + (i < remainder ? 1 : 0);
      displs[i] = offset;
      offset += sendcounts[i];
    }
  }

  MPI_Bcast(sendcounts.data(), world_size, MPI_INT, 0, MPI_COMM_WORLD);
  int local_size = sendcounts[world_rank];
  local_matrix.resize(local_size);

  MPI_Scatterv(world_rank == 0 ? matrix.data() : nullptr, sendcounts.data(), displs.data(), MPI_INT,
               local_matrix.data(), local_size, MPI_INT, 0, MPI_COMM_WORLD);

  int local_min = INT_MAX;
  for (int elem : local_matrix) {
    local_min = std::min(local_min, elem);
  }

  int global_min = 0;
  MPI_Allreduce(&local_min, &global_min, 1, MPI_INT, MPI_MIN, MPI_COMM_WORLD);

  GetOutput() = global_min;

  return true;
}

5. Экспериментальные исследования

Окружение

Параметр Значение
ОС Windows 11 Pro 25H2
Процессор AMD Ryzen 5 5600X (6 ядер, 12 потоков, 3.70 ГГц)
ОЗУ 16 ГБ DDR4 3400 МГц
Компилятор MSVC 14.43.34808
Версия MPI Microsoft MPI 10.1.12498.52

Тестовые данные

  1. Функциональные тесты:

    • Используют заранее подготовленные матрицы размеров от 3×3 до 10×10 с известным минимальным элементом, размещенным в центре матрицы.
    • Значения элементов матрицы генерируются случайным образом в диапазоне от минимального элемента до 250.
    • Тесты проверяют корректность работы на различных формах матриц (квадратные, прямоугольные, единичные).

  2. Тесты производительности:

    • Используют матрицу 5000×5000 (25 миллионов элементов).
    • Элементы вычисляются по формуле i * i + j.
    • Минимальный элемент имеет фиксированное значение -1_000_000 и размещается в центре матрицы.
    • Тесты выполняются в двух режимах: pipeline и task_run.

Сравнение производительности

Для сравнения производительности использовалась матрица размером 5000×5000.

Вычисления производились по следующим формулам:

  • Ускорение = Время_последовательное / Время_параллельное
  • Эффективность = (Ускорение / Количество_процессов) × 100%
Режим выполнения Количество процессов Время выполнения (сек) Ускорение Эффективность
Последовательный
pipeline 1 0.01138 1.00x -
task_run 1 0.01138 1.00x -
MPI (2 процесса)
pipeline 2 0.03687 0.31x 15.5%
task_run 2 0.03709 0.31x 15.5%
MPI (4 процесса)
pipeline 4 0.03823 0.30x 7.5%
task_run 4 0.03550 0.32x 8.0%
MPI (6 процессов)
pipeline 6 0.03614 0.31x 5.2%
task_run 6 0.03730 0.31x 5.2%

6. Результаты

  1. Результаты функционального тестирования

    • Все функциональные тесты успешно пройдены.
    • Все реализации (SEQ и MPI) работают корректно и выдают идентичные результаты для всех тестовых наборов.

  2. Результаты сравнения производительности

    • Параллельные MPI-версии работают медленнее последовательной при всех конфигурациях процессов.
    • Максимальное ускорение достигнуто при использовании 4 процессов в режиме task_run (0.32x от последовательной версии).
    • Минимальное время выполнения среди MPI-версий: 0.03550 сек (4 процесса, режим task_run).
    • Эффективность использования процессов снижается с 15.5% при 2 процессах до 5.2% при 6 процессах.

7. Выводы

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

  2. Параллельная реализация с использованием MPI показала снижение производительности по сравнению с последовательной версией. MPI-версии работают в среднем в 3.2-3.3 раза медленнее, что связано с высокими накладными расходами на межпроцессное взаимодействие (передача данных, синхронизация, редукция) при относительно небольшой вычислительной нагрузке задачи поиска минимума.

  3. При увеличении числа процессов эффективность снижается с 15.5% (2 процесса) до 5.2% (6 процессов). Это объясняется ростом коммуникационных издержек между процессами при неизменном объеме вычислений на процесс.

  4. Для данной задачи (поиск минимума в матрице 5000×5000) оптимальным является использование 2-4 процессов, однако даже в этом случае параллельная версия уступает последовательной.

  5. Результаты демонстрируют, что не все задачи выигрывают от распараллеливания. Задачи с низкой вычислительной сложностью и интенсивным обменом данными могут показывать отрицательное ускорение из-за преобладания накладных расходов над полезными вычислениями.

8. Источники

  1. Сысоев А. В. Лекции по курсу «Параллельное программирование для кластерных систем».
  2. Официальная документация Microsoft MPI — https://learn.microsoft.com/ru-ru/message-passing-interface
  3. Документация Open MPI — https://www.open-mpi.org/doc/
  4. C++ Reference — https://en.cppreference.com