637 lines
46 KiB
TeX
Executable File
637 lines
46 KiB
TeX
Executable File
\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}
|