Skip to content

report.md

Latest commit

 

History

History
269 lines (197 loc) · 14.8 KB

report.md

File metadata and controls

269 lines (197 loc) · 14.8 KB

Сумма элементов вектора

  • Студент: Батьков Филипп Владиславович, группа 3823Б1ПР3
  • Технология: SEQ | MPI
  • Вариант: 1

1. Введение

Цель задачи - разработка и реализация последовательной и параллельной версий алгоритма для суммирования элементов массива. Дополнительно необходимо реализовать тесты для проверки их корректности и провести сравнительный анализ эффективности обоих подходов с использованием реальных данных.

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

На вход подается вектор из челых чисел. Требуется определить сумму элементов этого вектора.

Тип входных данных:

using InType = std::vector<int>;

Тип выходных данных:

using OutType = int;

3. Базовый алгоритм (Sequential)

Основной принцип работы заключается в последовательном обходе всех элементов вектора и суммировании их значений в общую переменую:

int sum = 0;
for (int val : GetInput()) {
  sum += val;
}

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

Краткое описание

Алгоритм распараллеливается по схеме распараллеливания по данным. Исходный вектор делится на равные сегменты между всеми процессами. Каждый процесс выполняет суммирование своей части. Затем эти локальные суммы объединяются в общую.

4.1. Предварителльные действия

int rank = 0;
int mpi_size = 0;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &mpi_size);

m_rank_ = static_cast<size_t>(rank);
m_mpi_size_ = static_cast<size_t>(mpi_size);

if (m_rank_ == 0) {
  GetInput() = in;
} else {
  GetInput() = std::vector<int>();
}

Описание: В конструкторе задачи указывается количество доступных процессов и текущий ранг каждого из них. Данные копируются только на корневом процессе, чтобы избежать дублирования на всех остальных, так как каждый процесс будет работать только с собственной частью данных в дальнейшем.

4.2. Рассылка размера входных данных

size_t input_size = 0;
if (m_rank_ == 0) {
    input_size = GetInput().size();
}

MPI_Bcast(&input_size, 1, MPI_UNSIGNED_LONG_LONG, 0, MPI_COMM_WORLD);

Описание: Данные хранятся только в корневом процессе. Чтобы каждый процесс получил их размер, нужно разослать его с помощью функции MPI_Bcast().

4.3. Алгоритм базового распределения

const size_t base_chunk = input_size / m_mpi_size_;
const size_t remaining_elements = input_size % m_mpi_size_;

size_t chunk_size = base_chunk;
if (m_rank_ < remaining_elements) {
  chunk_size = base_chunk + 1;
}

Описание: Начальный размер блока данных для каждого процесса определяется путём разделения входного вектора на равные части. Однако в некоторых случаях равномерное распределение невозможно. Тогда каждый процесс получает дополнительный элемент, пока не будет исчерпан остаток.

4.4. Подготовка параметров перед отправкой данных

std::vector<int> send_counts(m_mpi_size_);
std::vector<int> displs(m_mpi_size_);
size_t disp = 0;

for (size_t i = 0; i < m_mpi_size_; ++i) {
  size_t chunk = base_chunk;
  if (i < remaining_elements) {
    chunk = base_chunk + 1;
  }

  int int_chunk = static_cast<int>(chunk);
  int int_disp = static_cast<int>(disp);

  if (int_chunk > std::numeric_limits<int>::max() || int_disp > std::numeric_limits<int>::max()) {
      return false;
  }

  send_counts[i] = int_chunk;
  displs[i] = int_disp;
  disp += chunk;
}

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

4.5. Распределение данных между процессами

MPI_Scatterv(GetInput().data(), send_counts.data(), displs.data(), MPI_INT, local_data.data(),
            static_cast<int>(chunk_size), MPI_INT, 0, MPI_COMM_WORLD);

Описание: Исходный вектор распределяется между всеми процессами. Функция MPI_Scatterv() отправляет каждому процессу свой блок данных с определённым размером и смещением.

4.6. Вычисление локальной суммы

int local_sum = 0;
for (int val : local_data) {
  local_sum += val;
}

4.7. Объединение в конечный результат

int global_sum = 0;
MPI_Allreduce(&local_sum, &global_sum, 1, MPI_INT, MPI_SUM, MPI_COMM_WORLD);

Описание: Функция MPI_Allreduce() выполняет коллективную операцию редукции, то есть собирает локальные суммы со всех процессов, складывает их и отправляет результат обратно всем процессам.

5. Детали реализации

Структура кода:

tasks/batkov_f_vector_sum/
├── common
│ └── include
│     └── common.hpp
├── info.json
├── mpi
│   ├── include
│   │   └── ops_mpi.hpp
│   └── src
│       └── ops_mpi.cpp
├── report.md
├── seq
│   ├── include
│   │   └── ops_seq.hpp
│   └── src
│       └── ops_seq.cpp
├── settings.json
└── tests
    ├── functional
    │   └── functional.cpp
    └── performance
        └── performance.cpp

Ключевые классы:

  • BatkovFVectorSumMPI — описание параллельного алгоритма
  • BatkovFVectorSumSEQ — описание последовательного алгоритма
  • BatkovFRunFuncTestsProcesses — функциональные тесты
  • BatkovFRunPerfTestProcesses — тест производительности

6. Экспериментальная среда

Компонент Значение
CPU Apple M2 (8 cores)
RAM 16 GB
ОС MacOS 15.3.1
Компилятор GCC 17.0.0 (g++), C++20, CMake, Release
MPI mpirun (Open MPI) 5.0.8

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

  1. Функциональные тесты:
    • тестовые данные извлекаются из файлов
    • файлы имеют различные данные, чтобы покрыть все случаи
  2. Тест производительности:
    • данные извлекаются из файла
    • файл содержит 1'000'000 чисел
    • в функции SetUp данные дублируются несколько раз, чтобы увеличить их размер до 128'000'000

7. Результаты и обсуждение

7.1 Корректность

Для проверки корректности используются функциональныt тесты, данные для которых извлекаются из четырех .txt файлов, содержащих различные данные для покрытия следюущих случаев:

  • Проверка коррекности при четном количетве элементов - два файла
  • Проверка коррекности при нечетном количетве элементов - один файл
  • Проверка при пустом векторе - один файл

Тесты были подобраны для проверок всех уникальных случаев работы алгоритма. Все тесты прошли проверку на SEQ и MPI реализации.

7.2 Производительность

Для теста производительности используется файл, содержащий один миллион чисел, в функции SetUp данные дублируются несколько раз, чтобы увеличить общий размер.

task_run:

Mode Count Time, s Speedup Efficiency
seq 1 0.5122482750 1.00 N/A
seq 2 0.5329974582 0.96 48.0%
seq 4 0.5806474584 0.88 22.0%
seq 8 1.7569079582 0.29 3.6%
mpi 1 1.9576604000 0.26 26.2%
mpi 2 0.9991464000 0.51 25.6%
mpi 4 0.5317128000 0.96 24.1%
mpi 8 0.3706790000 1.38 17.3%

pipeline:

Mode Count Time, s Speedup Efficiency
seq 1 0.5169585082 1.00 N/A
seq 2 0.5485557418 0.94 47.1%
seq 4 0.5662108332 0.91 22.8%
seq 8 0.9808735166 0.53 6.6%
mpi 1 1.8863512000 0.27 27.4%
mpi 2 1.0292510000 0.50 25.1%
mpi 4 0.5325800000 0.97 24.3%
mpi 8 0.4775352000 1.08 13.5%

8. Заключение

Разработаны реализации алгоритма суммирования элементов вектора для последовательного выполнения (SEQ) и с применением интерфейса передачи сообщений (MPI). На основании проведенных экспериментальных исследований и их анализа можно сделать следующие выводы:

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

  2. Производительность MPI-версии: при увеличении количества процессов наблюдается ускорение выполнения относительно MPI-версии с одним процессом. Например, в режиме task_run speedup увеличивается с 0.26 (1 процесс) до 1.38 (8 процессов), а время выполнения снижается с 1.96 до 0.37 секунд. Это ускорение достигается за счет распараллеливания вычислений: каждый процесс обрабатывает свою часть данных параллельно, что уменьшает общее время вычислений.

  3. Эффективность MPI-версии: несмотря на ускорение, эффективность снижается с увеличением числа процессов: с ~26-27% (1 процесс) до ~13-17% (8 процессов). Это обусловлено тем, что накладные расходы на организацию передачи сообщений между процессами (MPI_Bcast, MPI_Scatterv, MPI_Allreduce) растут быстрее, чем выигрыш от распараллеливания. Низкая вычислительная сложность операции суммирования не позволяет полностью компенсировать коммуникационные издержки.

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

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

9. Источники

  1. Материалы курса
  2. Документация Open MPI
  3. MPI стандарт