\documentclass[a4paper, final]{article}
%\usepackage{literat} % Нормальные шрифты
\usepackage[14pt]{extsizes} % для того чтобы задать нестандартный 14-ый размер шрифта
\usepackage{tabularx}
\usepackage{booktabs}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[left=25mm, top=20mm, right=20mm, bottom=20mm, footskip=10mm]{geometry}
\usepackage{ragged2e} %для растягивания по ширине
\usepackage{setspace} %для межстрочного интервала
\usepackage{moreverb} %для работы с листингами
\usepackage{indentfirst} % для абзацного отступа
\usepackage{moreverb} %для печати в листинге исходного кода программ
\usepackage{pdfpages} %для вставки других pdf файлов
\usepackage{tikz}
\usepackage{graphicx}
\usepackage{afterpage}
\usepackage{longtable}
\usepackage{float}

% Рекомендуется для biblatex (кавычки/локализация цитат и т.п.)
\usepackage{csquotes}

% ГОСТ-стили для biblatex
\usepackage[
  backend=biber,
  bibstyle=gost-numeric, % ссылки вида: [1]
  citestyle=gost-numeric,
  sorting=none % порядок в списке = по первому цитированию
]{biblatex}

% Все источники хранятся в отдельном файле
\addbibresource{refs.bib}

\renewcommand*{\bibfont}{\small}

% \usepackage[paper=A4,DIV=12]{typearea}
\usepackage{pdflscape}
% \usepackage{lscape}

\usepackage{array}
\usepackage{multirow}

\renewcommand\verbatimtabsize{4\relax}
\renewcommand\listingoffset{0.2em} %отступ от номеров строк в листинге
\renewcommand{\arraystretch}{1.4} % изменяю высоту строки в таблице
\usepackage[font=small, singlelinecheck=false, justification=centering, format=plain, labelsep=period]{caption} %для настройки заголовка таблицы
\usepackage{listings} %листинги
\usepackage{xcolor} % цвета
% \usepackage{hyperref}% для гиперссылок
\usepackage{enumitem} %для перечислений

\newcommand{\specialcell}[2][l]{\begin{tabular}[#1]{@{}l@{}}#2\end{tabular}}
\newcommand{\imgplaceholder}[2][0.9\textwidth]{%
    \includegraphics[width=#1]{#2}%
}


\setlist[enumerate,itemize]{leftmargin=1.2cm} %отступ в перечислениях

% \hypersetup{colorlinks,
    % allcolors=[RGB]{010 090 200}} %красивые гиперссылки (не красные)

% подгружаемые языки — подробнее в документации listings (это всё для листингов)
\lstloadlanguages{ SQL}
% включаем кириллицу и добавляем кое−какие опции
\lstset{tabsize=2,
    breaklines,
    basicstyle=\footnotesize,
    columns=fullflexible,
    flexiblecolumns,
    numbers=left,
    numberstyle={\footnotesize},
    keywordstyle=\color{blue},
    inputencoding=cp1251,
    extendedchars=true
}
\lstdefinelanguage{MyC}{
    language=SQL,
%    ndkeywordstyle=\color{darkgray}\bfseries,
%    identifierstyle=\color{black},
%    morecomment=[n]{/**}{*/},
%    commentstyle=\color{blue}\ttfamily,
%    stringstyle=\color{red}\ttfamily,
%    morestring=[b]",
%    showstringspaces=false,
%    morecomment=[l][\color{gray}]{//},
    keepspaces=true,
    escapechar=\%,
    texcl=true
}

\textheight=24cm % высота текста
\textwidth=16cm % ширина текста
\oddsidemargin=0pt % отступ от левого края
\topmargin=-1.5cm % отступ от верхнего края
\parindent=24pt % абзацный отступ
\parskip=5pt % интервал между абзацами
\tolerance=2000 % терпимость к "жидким" строкам
\flushbottom % выравнивание высоты страниц


% Настройка листингов
\lstset{
    language=python,
    extendedchars=\true,
    inputencoding=utf8,
    keepspaces=true,
    % captionpos=b, % подписи листингов снизу
}

% Настройка содержания
\usepackage{tocloft}
\usepackage[hidelinks]{hyperref}

% section в содержании НЕ жирным
\renewcommand{\cftsecfont}{\normalfont}
\renewcommand{\cftsecpagefont}{\normalfont}

% убрать отступ у subsection
\setlength{\cftsubsecindent}{0pt}

% subsubsection курсивом
\usepackage{titlesec}

\titleformat{\subsubsection}
  {\normalfont\large\itshape} % стиль: обычный + курсив
  {\thesubsubsection}   % номер (убери если не нужен)
  {1em}
  {}


\begin{document}
% ТИТУЛЬНЫЙ ЛИСТ
\begin{center}
    \hfill \break
    \hfill \break
    \normalsize{МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ\\
        федеральное государственное автономное образовательное учреждение высшего образования «Санкт-Петербургский политехнический университет Петра Великого»\\[10pt]}
    \normalsize{Институт компьютерных наук и кибербезопасности}\\[10pt] 
    \normalsize{Высшая школа технологий искусственного интеллекта}\\[10pt] 
    \normalsize{Направление: 02.03.01 <<Математика и компьютерные науки>>}\\
    
    \hfill \break
    \hfill \break
    \hfill \break
    \large{Отчёт по практическим заданиям по дисциплине}\\
    \large{<<Высокоскоростные сетевые технологии суперкомпьютеров>>}\\
    
    \hfill \break
    \hfill \break
    \hfill \break
\end{center}

\small{ 
    \begin{tabular}{lrrl}
        \!\!\!Студент, & \hspace{2cm} & & \\
        \!\!\!группы 5130201/20101 & \hspace{2cm} & \underline{\hspace{3cm}} & Тищенко А. А. \\\\
        \!\!\!Руководитель, & \hspace{2cm} & & \\
        \!\!\!профессор, д.т.н. & \hspace{2cm} & \underline{\hspace{3cm}} & Курочкин М. А. \\\\
        &&\hspace{4cm}
    \end{tabular}
    \begin{flushright}
        <<\underline{\hspace{1cm}}>>\underline{\hspace{2.5cm}} 2026г.
    \end{flushright}
}

\hfill \break
\begin{center} \small{Санкт-Петербург, 2026} \end{center}
\thispagestyle{empty} % выключаем отображение номера для этой страницы

\newpage
\tableofcontents

\newpage
\section*{Введение}
\addcontentsline{toc}{section}{Введение}

Современные вычислительные задачи во многих областях науки и техники требуют обработки больших объёмов данных и выполнения ресурсоёмких численных расчётов. В связи с этим особую роль играют высокопроизводительные вычислительные системы (High Performance Computing, HPC), позволяющие значительно ускорить решение сложных задач за счёт параллельной обработки данных и использования специализированных архитектур.

Одной из ключевых задач при работе с вычислительными системами является исследование их производительности. Для этого применяются специальные тесты и бенчмарки, позволяющие оценить эффективность вычислений при различных алгоритмах и конфигурациях оборудования. Одним из наиболее известных тестов является LINPACK, который используется для измерения производительности вычислительных систем при решении систем линейных алгебраических уравнений \cite{dongarra2003linpack}. Данный тест лежит в основе рейтинга суперкомпьютеров TOP500 и широко применяется для оценки производительности высокопроизводительных вычислительных систем.

Первая лабораторная работа посвящена исследованию производительности вычислительных систем на основе решения систем линейных алгебраических уравнений. В рамках работы изучаются численные методы решения СЛАУ, включая прямые и итерационные методы, а также реализуется собственная версия теста LINPACK с использованием параллельных вычислений. Особое внимание уделяется сравнению производительности стандартной реализации Intel High Performance Linpack и собственной реализации алгоритма.

Вторая лабораторная работа направлена на изучение технологий параллельного программирования и межпроцессного взаимодействия. В рамках данной работы рассматривается технология MPI (Message Passing Interface), широко используемая для разработки масштабируемых параллельных приложений \cite{gropp2014mpi}. Разработанный алгоритм реализуется с использованием MPI и исследуется его производительность при запуске на различном количестве вычислительных узлов. Полученные результаты сравниваются с реализацией вычислений с использованием технологии CUDA, предназначенной для выполнения параллельных вычислений на графических процессорах \cite{kirk2016cuda}.

Все вычислительные эксперименты проводились на вычислительном кластере Суперкомпьютерного центра Политехнического университета (СКЦ Политехнический). Доступ к вычислительным ресурсам осуществлялся через удалённое подключение по протоколу SSH. Для выполнения экспериментов использовалась учётная запись \texttt{tm3u21}, вход на кластер производился через узел доступа \texttt{login1.hpc.spbstu.ru}.  


\newpage
\section{Задача 1}

\subsection{Постановка задачи}

В рамках первого задания требовалось исследовать производительность вычислительной системы при решении плотной системы линейных алгебраических уравнений и сопоставить результаты собственной реализации с эталонным тестом LINPACK. Для достижения этой цели были поставлены следующие задачи:
\begin{enumerate}
    \item изучить подходы к оценке производительности вычислительных систем;
    \item разработать собственную CUDA-реализацию LINPACK-подобного теста;
    \item выполнить экспериментальные запуски на вычислительном узле СКЦ Политехнический;
    \item сравнить результаты собственной программы и стандартного Intel LINPACK.
\end{enumerate}

\begin{lstlisting}[caption={Фрагмент файла \texttt{\~{}/.ssh/config}}, label={lst:ssh-config}]
Host polytech
    HostName login1.hpc.spbstu.ru
    User tm3u21
    IdentityFile ~/.ssh/09
    ForwardAgent yes
\end{lstlisting}

Для подключения к СКЦ Политехнический в файл \texttt{\~{}/.ssh/config} была добавлена запись, приведённая в листинге~\ref{lst:ssh-config}. После этого вход на кластер выполнялся командой \texttt{ssh polytech}. Подтверждение входа под учётной записью \texttt{tm3u21} приведено на рис.~\ref{fig:task1-login}.

\subsection{Математическое описание}

Тест LINPACK применяется для оценки производительности вычислительных систем при решении плотной системы линейных уравнений \cite{dongarra2003linpack}. Рассматривается задача
\begin{equation}
    A x = b,
\end{equation}
где $A \in \mathbb{R}^{n \times n}$ --- плотная квадратная матрица, $x \in \mathbb{R}^{n}$ --- искомый вектор решения, $b \in \mathbb{R}^{n}$ --- вектор правой части.

В классическом варианте LINPACK обычно применяются прямые методы, основанные на LU-разложении \cite{golub2013matrix}. В собственной реализации для первого задания использован итерационный метод Якоби, так как он хорошо распараллеливается на GPU: каждая строка матрицы может обрабатываться независимо \cite{saad2003iterative}.

Для метода Якоби очередное приближение вычисляется по формуле
\begin{equation}
    x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum\limits_{j \ne i} a_{ij} x_j^{(k)} \right), \quad i = 1, 2, \dots, n.
\end{equation}

Критерий остановки выбран в виде
\begin{equation}
    \max_i \left| x_i^{(k+1)} - x_i^{(k)} \right| \le \varepsilon.
\end{equation}

Чтобы обеспечить сходимость метода, в программе формируется строго диагонально доминирующая матрица. Для контроля качества решения дополнительно вычисляются:
\begin{equation}
    \| A x - b \|_{\infty},
\end{equation}
\begin{equation}
    \| x - x_{true} \|_{\infty},
\end{equation}
где $x_{true}$ --- заранее известное опорное решение, использованное при построении тестовой системы.

Для приближённой оценки производительности используется LINPACK-подобная метрика
\begin{equation}
    R = \frac{\frac{2}{3} n^3}{t},
\end{equation}
где $t$ --- время решения, измеренное в секундах. В отчёте далее используется величина $R$ в GFLOPS.

\subsection{Особенности реализации}

Собственная программа реализована на CUDA C++ и находится в файле \texttt{task1/src/main.cu}. В реализации приняты следующие решения:
\begin{itemize}
    \item для каждой строки матрицы запускается отдельный поток CUDA, который вычисляет новое значение одной компоненты вектора решения;
    \item матрица $A$ и вектор $b$ один раз копируются на устройство, а далее итерационный процесс выполняется на GPU;
    \item завершение итераций контролируется через флаг \texttt{converged}, который может быть сброшен любым потоком, если изменение соответствующей компоненты превысило $\varepsilon$;
    \item после завершения расчёта на стороне CPU вычисляются невязка и ошибка относительно заранее известного решения;
    \item для удобства дальнейшего анализа программа может сохранять результаты в CSV-файл.
\end{itemize}

Такой вариант не является буквальной реализацией классического LU-LINPACK, однако решает ту же прикладную задачу --- измерение производительности при решении плотной СЛАУ --- и позволяет исследовать эффективность распараллеливания на GPU.
Полный текст исходного кода CUDA-реализации приведён в приложении А.

\subsection{Сборка и запуск}

Подготовленные файлы для выполнения задания были размещены в каталоге \texttt{/home/ipmmstudy1/tm3u21/supercomputers/task1}. Запуск собственной CUDA-реализации выполнялся пакетным файлом \texttt{task1/scripts/run\_cuda.slurm}, который загружал модули \texttt{compiler/gcc/11} и \texttt{nvidia/cuda/11.6u2}, собирал программу через \texttt{nvcc} и запускал серию вычислительных экспериментов. Полный текст данного файла приведён в приложении Б.

Эталонный CPU-вариант Intel LINPACK запускался из архива Intel oneMKL Benchmarks Suite for Linux, предварительно распакованного в каталог \\ \texttt{/home/ipmmstudy1/tm3u21/LINPACK}. В результате файл \texttt{xlinpack\_xeon64} был получен по пути \texttt{LINPACK/benchmarks\_2025.3/linux/share/mkl/benchmarks/linpack}. Для запуска использовался пакетный файл \texttt{task1/scripts/run\_intel\_linpack.slurm}, полный текст которого приведён в приложении В.

Для Intel LINPACK был подготовлен отдельный входной файл \texttt{lininput\_report\_xeon64}, в котором зафиксированы те же размеры задач, что и для CUDA-реализации: $1000$, $1500$, $2000$, $2500$, $3000$, $3500$. Полный текст этого файла приведён в приложении Г.

\subsection{Результаты эксперимента}

\begin{figure}[H]
    \centering
    \imgplaceholder{img/task1-login.png}
    \caption{Подключение к СКЦ Политехнический под учётной записью \texttt{tm3u21}}
    \label{fig:task1-login}
\end{figure}

\begin{figure}[H]
    \centering
    \imgplaceholder{img/task1-cuda-node.png}
    \caption{Конфигурация узла и графического ускорителя, использованных для CUDA-эксперимента}
    \label{fig:task1-cuda-node}
\end{figure}

\begin{figure}[H]
    \centering
    \imgplaceholder{img/task1-cuda-run.png}
    \caption{Терминальный вывод собственной CUDA-реализации теста}
    \label{fig:task1-cuda-run}
\end{figure}

\begin{figure}[H]
    \centering
    \imgplaceholder{img/task1-cuda-sacct.png}
    \caption{Сведения Slurm о выполнении собственной CUDA-реализации}
    \label{fig:task1-cuda-sacct}
\end{figure}

\begin{figure}[H]
    \centering
    \imgplaceholder{img/task1-intel-run.png}
    \caption{Терминальный вывод стандартного Intel LINPACK}
    \label{fig:task1-intel-run}
\end{figure}

\begin{figure}[H]
    \centering
    \imgplaceholder{img/task1-intel-sacct.png}
    \caption{Сведения Slurm о выполнении Intel LINPACK}
    \label{fig:task1-intel-sacct}
\end{figure}

Для сравнения были использованы два фактических запуска на СКЦ Политехнический: собственная CUDA-реализация (задание \texttt{6616336}, узел \texttt{n02p009}, раздел \texttt{tornado-k40}) и стандартный Intel LINPACK (задание \texttt{6616818}, узел \texttt{n01p090}, раздел \texttt{tornado}). Для Intel LINPACK использовался отдельный входной файл, содержащий те же размеры задач, что и в CUDA-реализации.

Подключение к кластеру под учётной записью \texttt{tm3u21} показано на рис.~\ref{fig:task1-login}. Конфигурация вычислительного узла и графических ускорителей, задействованных при CUDA-эксперименте, приведена на рис.~\ref{fig:task1-cuda-node}. Терминальный вывод собственной CUDA-реализации и сведения Slurm о её выполнении приведены на рис.~\ref{fig:task1-cuda-run} и рис.~\ref{fig:task1-cuda-sacct}. Аналогичные материалы для эталонного CPU-запуска Intel LINPACK приведены на рис.~\ref{fig:task1-intel-run} и рис.~\ref{fig:task1-intel-sacct}.

Численные результаты сведены в таблицу \ref{tab:task1-results}. Для столбцов CUDA использованы значения из файла \texttt{results/task1-cuda-6616336.csv}. Для Intel LINPACK в таблицу внесены минимальное время из серии прогонов и максимальная производительность из секции \texttt{Performance Summary}.

\begin{table}[H]
    \centering
    \small
    \caption{Сравнение собственной CUDA-реализации и Intel LINPACK}
    \label{tab:task1-results}
    \begin{tabular}{cccccccc}
        \toprule
        $N$ & $t_{CUDA}$, мс & Iter & $\|Ax-b\|_{\infty}$ & $R_{CUDA}$, GFLOPS & $t_{Intel}$, c & $R_{Intel}$, GFLOPS & $S_t$ \\
        \midrule
        1000 & 5.0083 & 6 & $2.242 \cdot 10^{-6}$ & 133.114 & 0.010 & 67.331 & 2.00 \\
        1500 & 7.4931 & 6 & $1.107 \cdot 10^{-6}$ & 300.277 & 0.020 & 114.360 & 2.67 \\
        2000 & 8.3563 & 5 & $2.443 \cdot 10^{-5}$ & 638.244 & 0.028 & 193.276 & 3.35 \\
        2500 & 10.4837 & 5 & $1.593 \cdot 10^{-5}$ & 993.608 & 0.042 & 250.731 & 4.01 \\
        3000 & 12.6709 & 5 & $1.288 \cdot 10^{-5}$ & 1420.573 & 0.069 & 260.451 & 5.45 \\
        3500 & 14.8861 & 5 & $9.516 \cdot 10^{-6}$ & 1920.138 & 0.100 & 286.264 & 6.72 \\
        \bottomrule
    \end{tabular}
\end{table}

\begin{figure}[H]
    \centering
    \imgplaceholder{img/task1-time-comparison.png}
    \caption{Сравнение времени решения эталонной и собственной реализаций}
    \label{fig:task1-time-comparison}
\end{figure}

Графическое сравнение времени решения приведено на рис.~\ref{fig:task1-time-comparison}. Скрипт, использованный для построения данного графика, приведён в приложении Д.

По полученным результатам можно сделать следующие наблюдения:
\begin{itemize}
    \item все тестовые случаи для размеров от $1000$ до $3500$ успешно сошлись за $5$--$6$ итераций;
    \item время решения возрастает плавно: от $5.0083$ мс при $N = 1000$ до $14.8861$ мс при $N = 3500$;
    \item ошибка по известному решению остаётся на уровне порядка $10^{-9}$--$10^{-8}$, а невязка --- на уровне $10^{-6}$--$10^{-5}$, что подтверждает корректность полученного решения;
    \item на всех рассмотренных размерах задач собственная реализация работает быстрее Intel LINPACK, а выигрыш по времени возрастает от $2.00$ до $6.72$ раза.
\end{itemize}

\subsection{Выводы}

В рамках первого задания была подготовлена собственная CUDA-реализация LINPACK-подобного теста для решения плотной СЛАУ методом Якоби. Программа поддерживает запуск серии экспериментов, измерение времени выполнения, а также вычисление невязки и ошибки относительно известного точного решения.

Дополнительно были подготовлены пакетные файлы запуска для собственной CUDA-реализации и для стандартного Intel LINPACK. Полные тексты этих файлов приведены в приложениях Б и В.

На текущем этапе можно зафиксировать, что собственная CUDA-реализация корректно работает на узле \texttt{tornado-k40} и обеспечивает сходимость на всём исследованном диапазоне размеров. В сопоставлении со стандартным Intel LINPACK на CPU она показывает меньшее время решения на всех исследованных размерах: собственная реализация оказывается более производительной, а выигрыш по времени возрастает от $2.00$ раза при $N = 1000$ до $6.72$ раза при $N = 3500$.


\newpage
\section{Задача 2}

\subsection{Постановка задачи}

В рамках второго задания требовалось решить следующие задачи:
\begin{enumerate}
    \item изучить технологию межпроцессного взаимодействия MPI;
    \item разработать параллельный масштабируемый алгоритм для решения вычислительной задачи;
    \item реализовать разработанный алгоритм с использованием технологии MPI;
    \item исследовать производительность реализации на 1, 2 и 4-х узлах СКЦ <<Политехнический>>;
    \item сравнить время решения вычислительной задачи с использованием MPI и CUDA.
\end{enumerate}

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

\subsection{Математическое описание}


Дано:
\begin{itemize}
    \item массив $P$ --- полигон размера $n \times n$ целых чисел;
    \item точки $P_1(x_1, y_1)$ и $P_2(x_2, y_2)$ на полигоне;
    \item контуры $V$, запрещённые для движения (ячейки со значением $-1$).
\end{itemize}
Требуется построить $L$ --- кратчайшую траекторию, соединяющую $P_1$ и $P_2$, либо сообщить, что такой траектории не существует. Траектория не может проходить через ячейки со значением $-1$.


Для решения задачи используется волновой алгоритм \cite{lee1961algorithm}. Алгоритм состоит из двух фаз.

\textbf{Фаза 1 --- распространение волны.} От начальной точки к конечной распространяется волна. На каждом шаге волна пополняется свободными ячейками, которые ещё не принадлежат волне и являются соседями ячеек, попавших в волну на предыдущем шаге. Для определения соседей используется окрестность фон Неймана (рис.~\ref{fig:task2-fon}): четыре ячейки сверху, снизу, слева и справа. Каждая новая ячейка заполняется значением
\begin{equation}
    d_{i,j} = \min\bigl(d_{i,j},\; d_{i-1,j}+1,\; d_{i+1,j}+1,\; d_{i,j-1}+1,\; d_{i,j+1}+1\bigr),
\end{equation}
где $d_{i,j}$ --- текущее расстояние от стартовой точки до ячейки $(i,j)$. Ячейки с препятствиями ($P_{i,j} = -1$) игнорируются.

\begin{figure}[H]
    \centering
    \includegraphics[width=0.15\textwidth]{img/task2-wave-fon.png}
    \caption{Окрестность фон Неймана}
    \label{fig:task2-fon}
\end{figure}

Начальная ячейка $P_1$ заполняется нулём. Остальные свободные ячейки инициализируются значением $\infty$. Итерации продолжаются до тех пор, пока хотя бы одна ячейка обновляется.

Иллюстрации первого, третьего и последнего шагов распространения волны приведены на рис.~\ref{fig:task2-first}--\ref{fig:task2-last}.

\begin{figure}[H]
    \centering
    \includegraphics[width=0.4\textwidth]{img/task2-wave-first-step.png}
    \caption{Первый шаг распространения волны}
    \label{fig:task2-first}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.4\textwidth]{img/task2-wave-third-step.png}
    \caption{Третий шаг распространения волны}
    \label{fig:task2-third}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.4\textwidth]{img/task2-wave-last-step.png}
    \caption{Последний шаг распространения волны}
    \label{fig:task2-last}
\end{figure}

\textbf{Фаза 2 --- восстановление пути.} Из конечной ячейки $P_2$ к начальной $P_1$ выполняется обратный ход: на каждом шаге выбирается соседняя ячейка со значением на единицу меньше текущего (рис.~\ref{fig:task2-reverse}).

\begin{figure}[H]
    \centering
    \includegraphics[width=0.4\textwidth]{img/task2-wave-reverse.png}
    \caption{Восстановление пути}
    \label{fig:task2-reverse}
\end{figure}

\subsection{Особенности реализации MPI}

Для распараллеливания волнового алгоритма с использованием MPI \cite{gropp2014mpi} применена декомпозиция полигона по строкам. Полигон размера $n \times n$ разбивается на горизонтальные полосы, каждая из которых обрабатывается отдельным MPI-процессом. При использовании $P$ процессов каждый из них получает примерно $n / P$ строк.

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

Алгоритм работы программы:
\begin{enumerate}
    \item Процесс с рангом 0 генерирует полигон $P$.
    \item Полигон рассылается всем процессам через \texttt{MPI\_Bcast}.
    \item Массив расстояний $dist$ распределяется по процессам через \texttt{MPI\_Scatterv}.
    \item Итеративно выполняется:
    \begin{enumerate}
        \item обмен теневыми строками с соседними процессами через \texttt{MPI\_Sendrecv};
        \item волновой шаг на локальных строках;
        \item проверка глобальной сходимости через \texttt{MPI\_Allreduce} с операцией \texttt{MPI\_LOR}.
    \end{enumerate}
    \item Результат собирается на процессе 0 через \texttt{MPI\_Gatherv}.
    \item Процесс 0 выводит длину пути и время выполнения (замер через \texttt{MPI\_Wtime}).
\end{enumerate}

Полный текст MPI-реализации приведён в приложении Е.

\subsection{CUDA-реализация для сравнения}

Для сопоставления с MPI-реализацией подготовлена CUDA-версия того же волнового алгоритма, основанная на программе прошлого семестра. В отличие от исходной версии, размер полигона задаётся через аргумент командной строки (вместо \texttt{\#define}). Используется ядро с глобальной памятью: каждый поток обрабатывает несколько ячеек с шагом, равным общему числу потоков. Полный текст CUDA-реализации приведён в приложении Ж.

\subsection{Сборка и запуск}

Файлы для второго задания были размещены в каталоге \texttt{/home/ipmmstudy1/tm3u21/supercomputers/task2}.

MPI-версия запускалась пакетным файлом \texttt{task2/scripts/run\_mpi.slurm} в разделе \texttt{tornado} на 1, 2 и 4 узлах. Для каждого запуска число узлов задавалось при отправке задачи:
\begin{verbatim}
sbatch --nodes=1 scripts/run_mpi.slurm
sbatch --nodes=2 scripts/run_mpi.slurm
sbatch --nodes=4 scripts/run_mpi.slurm
\end{verbatim}
Полный текст данного файла приведён в приложении З.

CUDA-версия запускалась пакетным файлом \texttt{task2/scripts/run\_cuda.slurm} в разделе \texttt{tornado-k40} на одном узле. Полный текст приведён в приложении И.

Обе программы последовательно запускались на полигонах размером $500$, $1000$, $2000$, $3000$, $5000$.

\subsection{Результаты эксперимента}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.8\textwidth]{img/task2-mpi-run.png}
    \caption{Терминальный вывод MPI-реализации волнового алгоритма}
    \label{fig:task2-mpi-run}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.8\textwidth]{img/task2-cuda-run.png}
    \caption{Терминальный вывод CUDA-реализации волнового алгоритма}
    \label{fig:task2-cuda-run}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.8\textwidth]{img/task2-sacct.png}
    \caption{Сведения Slurm о выполнении задач второго задания}
    \label{fig:task2-sacct}
\end{figure}

Для сравнения были использованы четыре фактических запуска на СКЦ <<Политехнический>>: CUDA-реализация (задание \texttt{6619329}, узел \texttt{n02p001}, раздел \texttt{tornado-k40}) и три запуска MPI-реализации на 1, 2 и 4 узлах (задания \texttt{6619332}, \texttt{6619333}, \texttt{6619334}, раздел \texttt{tornado}).

Терминальный вывод MPI- и CUDA-реализаций приведён на рис.~\ref{fig:task2-mpi-run} и рис.~\ref{fig:task2-cuda-run}. Сведения Slurm о выполнении задач показаны на рис.~\ref{fig:task2-sacct}.

Численные результаты сведены в таблицу~\ref{tab:task2-results}.

\begin{table}[H]
    \centering
    \small
    \caption{Сравнение времени выполнения MPI (1, 2, 4 узла) и CUDA}
    \label{tab:task2-results}
    \begin{tabular}{ccccccc}
        \toprule
        $n$ & $t_{\text{MPI-1}}$, мс & $t_{\text{MPI-2}}$, мс & $t_{\text{MPI-4}}$, мс & $t_{\text{CUDA}}$, мс & $S_2$ & $S_4$ \\
        \midrule
        500  & 30.60  & 14.94  & 17.85  & 48.89   & 2.05 & 1.71 \\
        1000 & 191.56 & 97.56  & 55.69  & 283.94  & 1.96 & 3.44 \\
        2000 & 1304.08 & 654.28 & 343.95 & 1949.41 & 1.99 & 3.79 \\
        3000 & 4616.74 & 2363.96 & 1200.42 & 6372.31 & 1.95 & 3.85 \\
        5000 & 19897.95 & 9960.07 & 5349.19 & 27251.48 & 2.00 & 3.72 \\
        \bottomrule
    \end{tabular}
\end{table}

В таблице $S_2 = t_{\text{MPI-1}} / t_{\text{MPI-2}}$ и $S_4 = t_{\text{MPI-1}} / t_{\text{MPI-4}}$ --- ускорение при увеличении числа узлов.

\begin{figure}[H]
    \centering
    \imgplaceholder{img/task2-time-comparison.png}
    \caption{Зависимость времени вычисления от размера полигона}
    \label{fig:task2-time-comparison}
\end{figure}

Графическое сравнение времени решения приведено на рис.~\ref{fig:task2-time-comparison}. Скрипт, использованный для построения данного графика, приведён в приложении К.

По полученным результатам можно сделать следующие наблюдения:
\begin{itemize}
    \item при увеличении числа узлов с 1 до 2 наблюдается практически линейное ускорение: $S_2$ составляет от $1{,}95$ до $2{,}05$ на всех размерах задач;
    \item при увеличении числа узлов до 4 ускорение $S_4$ зависит от размера задачи: для $n = 500$ оно составляет лишь $1{,}71$ из-за доминирования накладных расходов на обмен, а для $n \ge 1000$ достигает $3{,}44$--$3{,}85$;
    \item MPI-реализация на одном узле оказывается быстрее CUDA-реализации на всех размерах задач: например, при $n = 5000$ MPI выполняется за $19{,}9$ с, а CUDA --- за $27{,}3$ с;
    \item различие в производительности объясняется тем, что при последовательном обходе строк в MPI-версии волна может распространяться на несколько ячеек за одну итерацию, тогда как в CUDA все ячейки обрабатываются параллельно и за одну итерацию волна продвигается не более чем на одну ячейку (для $n = 5000$: 166 итераций MPI против 7541 итерации CUDA);
    \item на 4 узлах MPI-реализация работает в $3{,}7$--$5{,}1$ раза быстрее CUDA.
\end{itemize}

\subsection{Выводы}

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

Экспериментальные запуски показали, что MPI-реализация хорошо масштабируется: при переходе с 1 на 2 узла достигается практически линейное ускорение ($S_2 \approx 2{,}0$), а на 4 узлах --- ускорение до $3{,}85$ раза при достаточном размере задачи ($n \ge 1000$). MPI-реализация даже на одном узле оказалась быстрее CUDA благодаря меньшему числу итераций алгоритма.


\newpage
\section*{Заключение}
\addcontentsline{toc}{section}{Заключение}

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

В первом задании была разработана собственная CUDA-реализация LINPACK-подобного теста и проведено сравнение с эталонным Intel LINPACK. Собственная реализация показала меньшее время решения на всех исследованных размерах задач с ускорением от $2{,}00$ до $6{,}72$ раза.

Во втором задании волновой алгоритм поиска пути был реализован с использованием MPI и исследована его масштабируемость при запуске на 1, 2 и 4 узлах СКЦ <<Политехнический>>. MPI-реализация продемонстрировала хорошую масштабируемость: ускорение при переходе с 1 на 2 узла составило около $2{,}0$, а на 4 узлах --- до $3{,}85$ раза. При сравнении с CUDA MPI-версия оказалась быстрее на всех размерах задач благодаря меньшему числу итераций при последовательном обходе строк.

\newpage
\printbibliography[heading=bibintoc]

\newpage
\section*{Приложение А}
\addcontentsline{toc}{section}{Приложение А}
\label{app:task1-cuda-source}
\lstinputlisting[caption={Файл \texttt{task1/src/main.cu}}, label={lst:task1-main}]{../task1/src/main.cu}

\newpage
\section*{Приложение Б}
\addcontentsline{toc}{section}{Приложение Б}
\label{app:task1-cuda-slurm}
\lstinputlisting[caption={Файл \texttt{task1/scripts/run\_cuda.slurm}}, label={lst:task1-cuda-slurm}]{../task1/scripts/run_cuda.slurm}

\newpage
\section*{Приложение В}
\addcontentsline{toc}{section}{Приложение В}
\label{app:task1-intel-slurm}
\lstinputlisting[caption={Файл \texttt{task1/scripts/run\_intel\_linpack.slurm}}, label={lst:task1-intel-slurm}]{../task1/scripts/run_intel_linpack.slurm}

\newpage
\section*{Приложение Г}
\addcontentsline{toc}{section}{Приложение Г}
\label{app:task1-intel-input}
\lstinputlisting[caption={Файл \texttt{task1/intel/lininput\_report\_xeon64}}, label={lst:task1-intel-input}]{../task1/intel/lininput_report_xeon64}

\newpage
\section*{Приложение Д}
\addcontentsline{toc}{section}{Приложение Д}
\label{app:task1-plot-script}
\lstinputlisting[caption={Файл \texttt{task1/scripts/plot\_task1\_results.py}}, label={lst:task1-plot-script}]{../task1/scripts/plot_task1_results.py}

\newpage
\section*{Приложение Е}
\addcontentsline{toc}{section}{Приложение Е}
\label{app:task2-mpi-source}
\lstinputlisting[language=C, caption={Файл \texttt{task2/src/wave\_mpi.c}}, label={lst:task2-mpi}]{../task2/src/wave_mpi.c}

\newpage
\section*{Приложение Ж}
\addcontentsline{toc}{section}{Приложение Ж}
\label{app:task2-cuda-source}
\lstinputlisting[language=C, caption={Файл \texttt{task2/src/wave\_cuda.cu}}, label={lst:task2-cuda}]{../task2/src/wave_cuda.cu}

\newpage
\section*{Приложение З}
\addcontentsline{toc}{section}{Приложение З}
\label{app:task2-mpi-slurm}
\lstinputlisting[language=bash, caption={Файл \texttt{task2/scripts/run\_mpi.slurm}}, label={lst:task2-mpi-slurm}]{../task2/scripts/run_mpi.slurm}

\newpage
\section*{Приложение И}
\addcontentsline{toc}{section}{Приложение И}
\label{app:task2-cuda-slurm}
\lstinputlisting[language=bash, caption={Файл \texttt{task2/scripts/run\_cuda.slurm}}, label={lst:task2-cuda-slurm}]{../task2/scripts/run_cuda.slurm}

\newpage
\section*{Приложение К}
\addcontentsline{toc}{section}{Приложение К}
\label{app:task2-plot-script}
\lstinputlisting[language=python, caption={Файл \texttt{task2/scripts/plot\_task2\_results.py}}, label={lst:task2-plot}]{../task2/scripts/plot_task2_results.py}


\end{document}
