\documentclass{cmi}
\usepackage{upgreek}

\usepackage{subcaption}                         % для subfigure
\captionsetup[figure]{labelfont=bf}             % жирный Рис. N
\captionsetup{labelsep=period}                  % точка в конце Рис. 1>>>точка<<<
\renewcommand{\thesubfigure}{\asbuk{subfigure}} % русские буквы в подрисунках

\newcommand{\subfig}[4]{% params, label, caption
	\begin{subfigure}{#4\textwidth}%
		\centering%
		\includegraphics[#1]{#2}%
		\caption{#3}%
		\label{ris:#2}%
	\end{subfigure}%
}
\usepackage{makecell}
\newcommand*{\x}{\mathsf{x}\mskip1mu}
\newcommand*{\Received}{04.06.2018}

\begin{document}

\classify{УДК 519.687.1}

\renewcommand*{\thefootnote}{\fnsymbol{footnote}} %to make a number in end of title delete this line


\title{ОПТИМИЗАЦИЯ ФРАГМЕНТАЦИИ ПРИ ВЫДЕЛЕНИИ РЕСУРСОВ ДЛЯ ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ С СЕТЬЮ АНГАРА%
\footnote{Статья рекомендована
	к публикации программным комитетом
	Международной научной конференции
	«Параллельные вычислительные технологии
	(ПаВТ) 2018»}%
}

\author{\copyright~2018 А.В.~Мукосей, А.С.~Семенов}



\address{АО <<НИЦЭВТ>> \\
	(117587 Москва, Варшавское шоссе 125с15)}

\email{E-mail: \href{mailto:mukosey@nicevt.ru}{mukosey@nicevt.ru}, 
\href{mailto:semenov@nicevt.ru}{semenov@nicevt.ru}}

\received{Поступила в редакцию: \Received}

\maketitle{}


\renewcommand*{\thefootnote}{\arabic{footnote}}
\setcounter{footnote}{0}

% оформление аннотации
\begin{abstract}%
	В данной работе рассматривается высокоскоростная вычислительная сеть с топологией многомерный тор.
	Работа посвящена оптимизации фрагментации, возникающей в результате последовательного выделения 
	вычислительных узлов в многоузловой системе при заданном требовании о том, что сетевой трафик
	разных пользовательских заданий не должен пересекаться.
	В данной работе на основе идей из задачи о многомерной упаковке контейнера предложен метод поиска
	узлов с оценкой фрагментированности системы.
	Для такой оценки введено понятие прямоугольников максимального размера, которые возможно вписать
	в систему после размещения очередного пользовательского задания. Каждое множество узлов, подходящее
	для размещения задания, оценивается предложенной функцией, учитывающей размер и количество найденных
	прямоугольников максимального размера.
	Исследование разработанного метода проводилось с помощью симулятора работы вычислительной системы.
	Рассмотрен набор различных вычислительных систем с трехмерными и четырехмерными топологиями, размер
	минимальной системы --- $32$ вычислительных узла, максимальной --- $144$ узла.
	Для каждой системы задана синтетическая очередь заданий, параметры которой приближены к реально возможной.
	В качестве критерия качества метода выбора узлов рассматривается средняя утилизация ресурсов вычислительной
	системы и среднее время ожидания заданий в очереди.
	Исследование показало, что увеличение утилизации ресурсов для предложенного метода выбора узлов составило
	в среднем $11\%$ по сравнению с базовым методом, а среднее значение времени нахождения задания в очереди
	сокращенно на $45,3\%$.

	\keywords{Коммуникационная сеть Ангара, многомерный тор, правило порядка направлений, фрагментация вычислительной системы, выбор узлов}
\end{abstract}
\flushleft{\textbf{ОБРАЗЕЦ ЦИТИРОВАНИЯ}}
\justifying  % по всей ширене
\begin{citationplace}
	Мукосей~А.Б., Семенов~А.С. Оптимизация фрагментации при выделении ресурсов для высокопроизводительных вычислительных систем с сетью Ангара // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2018. Т.~X, №~Y. С.~Z1--Z2.
	DOI:~10.14529/cmseXXXXXX.
\end{citationplace}

\section*{Введение}
Фрагментация, возникающая в результате последовательного выделения вычислительных узлов в
многоузловой системе играет критическую роль в эффективности использования суперкомпьютера. Особенное значение эта проблема имеет для сетей с топологией типа тор.
На данный момент существует две стратегии выделения ресурсов, используемых в суперкомпьютерах
с тороидальной сетью \cite{YangXu}.
В суперкомпьютерах IBM Blue Gene/P, Blue Gene/Q предоставление ресурсов основано на разделение системы на партиции, по которым размещаются задачи пользователей \cite{reducing-fragmentation, IBM_BGQ_Redbook}. Такая стратегия может порождать фрагментацию, возникающую в результате выделения
большего числа узлов, чем требовалось или невозможности выделить доступный набор узлов из разных партиций. 

Вторая стратегия используется в серии суперкомпьютеров Cray XT/XE, где расположение
выделенных узлов \cite{CrayDoc2012} не зависит от топологии. Такой  способ выделения ресурсов может привести к деградации
производительности ввиду наличия конкурирующего трафика. В статье \cite{YangXu} алгоритм оптимизации упаковки заданий использует линейную нумерацию узлов, однако это неудобно для сети Ангара.

В АО <<НИЦЭВТ>> разработана высокоскоростная коммуникационная сеть Ангара \cite{RSD2016, Angara1}
с топологией <<многомерный тор>>. В маршрутизаторе сети реализована бездедлоковая, адаптивная
маршрутизация, основанная на правилах «пузырька» (Bubble flow control, \cite{Puente}) и
«порядка направлений» (Direction ordered routing, DOR, \cite{Adiga, Scott96-t3e}) с
использованием битов направлений \cite{Scott96-t3e}. Благодаря алгоритму First Step/Last Step
<<нестандартного первого и последнего шага>> \cite{Scott96-t3e} аппаратно поддерживается обход
отказавших узлов или линков. Эффективность этого метода по поддержанию связности в сети с
отказами была показана в статье \cite{Pozhilov}. 

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

Такая задача носит название упаковки контейнера и является $NP$-полной задачей. Существуют различные
способы решения такой задачи: авторы статьи~\cite{Knapsack-Problem} предлагают решать такую задачу
муравьиным алгоритмом --- полиномиальный алгоритмов метаэвристической оптимизации для нахождения приближённых решений, который основан на использовании модели поведения муравьёв, ищущих пути от колонии к источнику питания. Авторы статьи~\cite{container-loading-problem} разработали различные алгоритмы упаковки с использованием генетического алгоритма.

В данной статье предлагается алгоритм выбора узлов для суперкомпьютеров с топологией <<многомерный тор>>\  с учетом 
расположения заданий в топологии в коммуникационной сети. Статья организована следующим образом.
В разделе~\ref{sec:definitions} приводятся необходимые формальные определения и постановка задачи.
В разделе~\ref{sec:algorithms} описаны разработанные алгоритмы.
В разделе~\ref{sec:research} проведено исследование построенных алгоритмов.

В результате, разработанный алгоритм на рассмотренных системах и предложенных очередях в среднем увеличил утилизацию ресурсов на $11\%$, а значение времени нахождения заданий в очереди сократил на $57\%$ по сравнению с первоначальным вариантом алгоритма, использовавшемся для выбора узлов.

\section{Определения и постановка задачи}\label{sec:definitions}
В данном разделе приводятся формальные определения, которые в дальнейшем будут использоваться в статье.

Рассмотрим вычислительную систему, узлы которой объединены в тороидальную топологию. Размерности тора обозначим $(d_1, d_2, ..., d_n)$, а множество всех узлов вычислительной системы обозначим
$N = \{u|u=(u_1,...,u_n), \forall i\;u_i \in \mathbb{Z}_{d_i}\}$, а общее
число узлов --- $|N|$.
Расстояние на множестве $N$ определим следующим образом:
$L(u, v) = \sum\limits_{i=1}^{n}|u_i-v_i|, \; \forall u,v \in N$.

Состояние системы $S$ можно описать множествами узлов, доступных и недоступных для выделения, обозначим эти множества $N_{free}$ и $N_{locked}$, соответственно.

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

Будем называть \textit{заданием} $W$ --- число узлов $W_{nodes}$, запрашиваемое пользователем в момент времени $W_{start}$ на время $W_{time}$, а \textit{ресурсами для задания} --- маршрутизируемое множество узлов, размер которого не меньше, чем $W_{nodes}$. \textit{Потоком заданий} назовем множество различных заданий $W$.

Ранее в работе \cite{search-alg} авторами статьи решалась проблема поиска маршрутизируемого
множества заданного размера в коммуникационной сети Ангара с учетом топологии и маршрутизации.
Обозначим алгоритм, решающий эту проблему как $Find\_Systems(W,\; S)$. На вход этому алгоритму подается
состояние системы $S$ и задание $W$ с требуемым числом вычислительных узлов $W_{nodes}$.
Результатом работы алгоритма является набор вариантов ресурсов для задания. Необходимо заметить, что особенностью алгоритма является то, что все ресурсы для задания представляют собой многомерные прямоугольники.

Под \textit{утилизацией} ресурсов $U$ вычислительного кластера будем
понимать среднее значение утилизации по всем вычислительным узлам:
\begin{align*}
U = \frac{\sum\limits_{i=1}^{|N|}U_i}{|N|}, U_i=\frac{T_i}{T},
\end{align*}
где $U_i$ --- утилизация $i$-го вычислительного узла, $T$ --- время работы вычислительного кластера, $T_i$ -- полезное время работы
$i$-го вычислительного узла.

Обозначим \textit{значение времени нахождения задания в очереди относительно запрошенного времени} как $T^i_{delay}=\frac{Q^i}{W^i_{time}}$, где $W^i_{time}$ --- запрошенное время для задания $W^i$, $Q^i$ --- время ожидания задания $W^i$ в очереди. За \textit{среднее значение времени нахождения задания в очереди относительно запрошенного времени задания} примем $T_{mid} = \frac{\sum_{i=1}^{k}T^i_{delay}}{k}=\frac{1}{k}\sum_{i=1}^{k}\frac{Q^i}{W^i_{time}}$, где $k$ --- число различных заданий в потоке.

За оценку качества решения для потока пользовательских заданий возьмем утилизацию ресурсов вычислительного кластера и среднее значение времени нахождения задания в очереди относительно запрошенного времени. Эти характеристики используются по аналогии с работой \cite{Quasiplaner}.

Во введенных обозначениях проблема, которую решает данная статья, будет формулироваться следующим образом. 
Для заданного вычислительного кластера и последовательности заданий $Q=W^1,..., W^k$ требуется найти ресурсы для всех заданий из последовательности, которые будут максимизировать утилизацию вычислительного кластера и минимизировать среднее значение времени нахождения задания в очереди относительно запрошенного времени.

%%------ Section  -----------------------------------
\section{Алгоритм выбора узлов}\label{sec:algorithms}

Для решения поставленной проблемы в статье предложен алгоритм выбора узлов, основанный на методах, предложенных в работе \cite{container-loading-problem}, посвященной трехмерной упаковке контейнера.
Идея алгоритма выбора узлов заключается в расположении задания таким образом, чтобы максимизировать оставшееся пространство в многомерном торе. 

\subsection{Алгоритм построения прямоугольников максимального размера}\label{sec:Find_MSS}

Назовем \textit{прямоугольником максимально возможного размера $MSS\;(Max Space Size)$} многомерный прямоугольник, состоящий только из узлов $N_{free}$, который нельзя расширить ни в одну из его сторон. Расширить прямоугольник может быть невозможно по двум причинам --- либо по соответствующему измерению тора достигнуто максимальное количество узлов в кольце (расширять некуда), либо сторона прямоугольника граничит с узлом из множества $N_{locked}$.
Множество различных прямоугольников $MSS$ характеризуют меру фрагментированности системы.

Алгоритм поиска различных прямоугольников $MSS$ ($Find\_MSSs(S)$) реализован следующим образом. Из множества $N_{free}$ выбирается узел $u_1 \in N_{free}$. Выбранный узел последовательно расширяется во все стороны, пока это возможно. Полученное множество узлов обозначим $MSS_1$. На следующем этапе выбирается узел $u_2 \in N_{free} \textbackslash MSS_1$ и аналогичным образом строится множество $MSS_2$. Алгоритм продолжается до тех пор, пока множество $N_{free} \textbackslash \bigcup\limits_{iter=1}^{Iters} MSS_{iter}$ не пусто, где $Iters$ --- число итераций алгоритма. Псевдокод алгоритма представлен на \figref{Find_MSS.code}. Обозначим множество различных $MSS_{iter}$, как $MSSs$.  Важно отметить, что каждый прямоугольник строится независимо от остальных прямоугольников, в предположении доступности всех изначально свободных узлов $N_{free}$.

\begin{figure}[ht!]
	\centering
	\subfig{height=3.8cm}{rsd17-MSS-alg}{Построение прямоугольника максимально возможного размера}{0.48}
	\subfig{height=3.8cm}{rsd17-MSS-example}{Все прямоугольники максимально возможного размера, построенные алгоритмом}{0.48}
	\vspace*{1em}
	\caption{Выделение прямоугольников максимального размера}
\end{figure}

\code[15cm]{frame=single}{Find_MSS.code}{Псевдокод алгоритма Find\_MSS поиска прямоугольников максимального размера}

Иллюстрация работы алгоритма приведена на \figref{ris:rsd17-MSS-alg}~и~\figref{ris:rsd17-MSS-example}, на которых в двумерной решетке узлы множества $N_{locked}$ закрашены, а свободные узлы $N_{free}$ --- нет. Жирным контуром на \figref{ris:rsd17-MSS-alg} выделен узел, из которого поочередным расширением построен двумерный прямоугольник, который обозначен пунктирной линией. Узлы, выделенные полужирным пунктиром, соответствуют множеству узлов $N_{free}$, не входящих в построенный прямоугольник. Из этих узлов будут строиться последующие прямоугольники. Все построенные прямоугольники $MSS$ показаны на \figref{ris:rsd17-MSS-example}. 

\subsection{Оценка состояния вычислительной системы на основе прямоугольников максимального размера}\label{sec:calc_MSS}

Для оценки состояния вычислительной системы предложена функция  $\varphi$, которая тем больше, чем большее число прямоугольников максимального размера имеется в системе:
\begin{align*}
\varphi(S) = N * MSS^{nnodes}_{max} + |MSS_{max}|,
\end{align*}
где $MSS_{max}$ --- множество прямоугольников максимального размера, имеющих
наибольшее число узлов $MSS^{nnodes}_{max}$, $|MSS_{max}|$ --- число таких
прямоугольников, $S$ --- текущее состояние системы.

Эта метрика была добавлена в алгоритм $Find\_Systems(W,S)$ поиска
маршрутизируемого множества заданного размера. Для каждого найденного
маршрутизируемого множества оценивается значение функции $\varphi(S')$, где $S'$ ---
состояние вычислительной системы $S$ после выделения узлов. Для увеличения
утилизации вычислительного кластера требуется выбирать решения с наибольшим
значением функции $\varphi$. Модифицированный алгоритм $Find\_Systems(W,S)$, в котором возможные варианты систем отсортированы с учетом значения функции $\varphi$, в дальнейшем будем обозначать $Find\_Systems_{MSS}(W,S)$

\subsection{Первоначальный алгоритм выбора узлов для кластеров с сетью Ангара}
Алгоритм, который изначально работал на кластерах с сетью Ангара, устроен следующим образом. Для всего кластера строится таблица маршрутизации \cite{search-alg}. Для требуемого числа узлов $W_{nodes}$ и допустимого числа транзитных узлов $N_{transit}$ строятся всевозможные разложения чисел  $W_{nodes}, W_{nodes} + 1, ... , W_{nodes} + N_{transit}$ на $n$ множителей, таких что $1 \leqslant p_i \leqslant d_i, \forall i \in 1..n$, где $p_i$ --- множитель разложения. Все такие разложения обозначим $D$. Эти разложения описывают всевозможные размеры прямоугольников, подходящих под решение задачи $W$. Средним диаметром прямоугольника, соответствующего разложению $D_j \in D$, назовем среднее арифметическое всех расстояний между узлами прямоугольника: $\frac{\sum_{u,v \in D_j, u != v}L(u,v)}{|D_j|}$.

Следующий этап выбора узлов --- поиск множества узлов вычислительного кластера, которое можно покрыть одним из найденных прямоугольников таким образом, чтобы в покрытии присутствовали только узлы из множества $N_{free}$, то есть доступные для выделения. Поиск покрытия начинается с разложений c наименьшим средним диаметром. При первом найденном решении алгоритм заканчивает свою работу.

\section{Экспериментальное исследование}\label{sec:research}

\subsection{Симулятор вычислительного кластера}\label{sec:cluster_usage}
Для оценки утилизации ресурсов вычислительного кластера разработан симулятор очереди задач (заданий) и модель состояния кластера. Заметим, что в данной работе не рассматривалась возможность обгона заданий, то есть предоставление ресурсов заданию, имеющему более позднее время $W_{time}$, если заданию с ранним временем $W_{time}$ не были выделены ресурсы. На вход симулятору подается поток пользовательских задач $Q = {W^1,...,W^k}$. На выходе выдается полное время работы всего кластера $T$, время работы каждого узла $T_i$ и время предоставления ресурсов для каждого задания. Используя эти данные, можно вычислить утилизацию ресурсов вычислительного кластера $U$ и среднее значение времени нахождения задания в очереди $T_{mid}$.

Введем некоторые формальные определения, необходимые для описания работы симулятора. \textit{Очередью} симулятора назовем набор заданий из потока, для которых не выделялись ресурсы и время их запуска $T_{start}$ меньше текущего симулируемого времени $t$.
\textit{Временем занятости узла} $u$ системы $S$, назовем время, на которое узел $u$ был выделен для некоторого задания $W$. В начальный момент времени $t=0$ время занятости всех узлов равно $0$. Операцией \textit{выделения набора узлов} на время $T_{alloc}$ назовем увеличение времени занятости для этих узлов на время $T_{alloc}$. \textit{Временем изменения системы} $T_{S}$ назовем время, через которое освободится хотя бы один из выделенных узлов. \textit{Временем изменения очереди} $T_{queue}$ назовем время, через которое хотя бы одно задание перейдет из потока заданий в очередь симулятора. Тогда \textit{временем ожидания симулятора} $T_{sleep}$ назовем минимальное время до изменения состояния симулятора: $T_{sleep} = min(T_{S}, T_{queue})$.

Алгоритм работы симулятора устроен следующим образом. Если очередь симулятора не пуста, симулятор выполняет процедуру поиска маршрутизируемого множества для каждого задания из очереди по очереди. Если удалось найти решение, то симулятор выделяет найденные ресурсы на необходимое время, а также удаляет это задание из очереди. Если решение не было найдено, время симулятора сдвигается на время ожидания $T_{sleep}$, а время занятости каждого занятого узла $u$ системы $S$ уменьшается на $T_{sleep}$. Если очередь заданий пуста, а все узлы перешли в состояние свободных, то симулятор завершает свою работу.

\subsection{Результаты исследования}
Исследование разработанного алгоритма проводилось на симуляторе для вычислительных систем \cite{Cluster-Simulator} , представленных в таблице~\ref{systems}.

%\captionsetup[table]{labelformat=empty}
\captionsetup[table]{labelfont=bf, singlelinecheck=off, justification=raggedleft}
\tab{systems}{Моделируемые системы}{
	\begin{tabular}{|l|c|c|}
		\hline
		\multicolumn{1}{|c|}{\bf \makecell{Количество узлов \\ вычислительной системы}} &
		\multicolumn{1}{|c|}{\bf \makecell{Топология \\ 3х-мерный тор}} &
		\multicolumn{1}{|c|}{\bf \makecell{Топология \\ 4х-мерный тор}} \\
		\hline
		32  & $4\x4\x2$ & $4\x2\x2\x2$ \\ \hline
		36  & $4\x3\x3$ & $3\x3\x2\x2$ \\ \hline
		64  & $4\x4\x4$ & $4\x4\x2\x2$ \\ \hline
		96  & $6\x4\x4$ & $4\x4\x3\x2$ \\ \hline
		144 & $8\x6\x3$ & $4\x4\x3\x3$ \\ \hline
	\end{tabular}
}

Поток заданий для каждой из систем характеризуется вероятностью появления задания для каждого числа узлов от 1 до максимального. Распределение  вероятностей таких вероятностей представлено на \figref{ris:distr}. На \figref{ris:dist-32-2} представлено реальное распределение пользовательских задач (заданий) по количеству узлов, полученное с гибридного суперкомпьютера Desmos на базе сети Ангара, имеющую топологию 4х-мерный тор $4\x2\x2\x2$ \cite{Desmos}. В дальнейшем системы с данной очередью будем помечать символом $s$ --- $4\x2\x2\x2s$ и $4\x4\x2s$. Остальные распределения долей заданий по количеству узлов --- синтетические, основанные на предположении о том, что чаще всего встречаются заданий с требуемым числом узлов, равным степеням двойки.

\begin{figure}[ht!]
	\centering
	\subfig{height=3.3cm}{dist-32-1}{Для систем из 32 узлов}{0.3}
	\subfig{height=3.3cm}{dist-32-2}{Для систем из 32 узлов, кластер Desmos}{0.3}
	\subfig{height=3.3cm}{dist-36}{Для систем из 36 узлов}{0.3}
	\subfig{height=3.3cm}{dist-64}{Для систем из 64 узлов}{0.3}
	\subfig{height=3.3cm}{dist-96}{Для систем из 96 узлов}{0.3}
	\subfig{height=3.3cm}{dist-144}{Для систем из 144 узлов}{0.3}
	\vspace*{1em}
	\caption{Распределение заданий для систем с разным числом узлов}
	\label{ris:distr}
\end{figure}

Вероятности для остальных числов узлов равны 0. Задания равномерно случайно размещаются на временной шкале в диапазоне $\left[0; 40500\right]$ секунд вне зависимости от числа требуемых узлов. 
Время продолжительности заданий равномерно распределено по диапазону $\left[50; 100\right]$.

Для исследования разработанного алгоритма поиск ресурсов для заданий производился
четырьмя различными способами: методом $Find\_Systems$ без применения разработанной метрики ($Find\_Systems$);
методом $Find\_Systems_{MSS}$ с применением разработанной метрики ($Find\_Systems + MSS$); методом, который изначально функционировал на кластерах с сетью Ангара ($base$).

Диаграмма сравнения утилизации для различных методов и систем представлена на \figref{ris:util}. Сравнение средних значений времени нахождения задания в очереди относительно запрошенного времени ($T_{mid}$) для различных методов и систем представлено на \figref{ris:waiting}.

\begin{figure}[ht!]
	\centering
	\subfig{height=6.2cm}{util}{Сравнение утилизации вычислительного кластера для различных системы и методов}{0.48}
	\subfig{height=6.2cm}{waiting}{Сравнение средних значений времени нахождения задания в очереди относительно запрошенного времени ($T_{mid}$) для различных методов и систем}{0.48}
	\vspace*{1em}
	\caption{Результаты моделирования}
	\label{ris:diag}
\end{figure}

Разработанный алгоритм $Find\_Systems$ из статьи \cite{search-alg} сократил в среднем значение времени нахождения заданий в очереди на $45,3\%$, а утилизация ресурсов кластера в среднем увеличилась на $8,4\%$ относительно базового метода $base$.

Добавление в $Find\_Systems$ учета фрагментированности вычислительной системы позволило еще сократить значение времени нахождения заданий в очереди до $57\%$ относительно метода $base$, что на $11,7\%$ больше чем у метода $Find\_Systems$. Утилизация ресурсов при этом увеличивается до $11\%$ относительно метода $base$, что на $2,6\%$ больше чем у метода $Find\_Systems$.

%% -------------- Conclusion ----------------
\section*{Заключение}
В данной работе представлен метод выбора вычислительных узлов для потока пользовательских заданий, сокращающий фрагментацию вычислительной системы в сети Ангара с топологией многомерный тор. Метод основан на алгоритме выделения ресурсов для задания таким образом, чтобы максимизировать оставшееся пространство в многомерном торе. Это достигается построением прямоугольников максимального размера, которые возможно вписать в систему после размещения очередного пользовательского задания. Каждое множество узлов, подходящее для размещения задания, оценивается предложенной функцией, учитывающей размер и количество найденных прямоугольников максимального размера.

Проведено экспериментальное исследование разработанного алгоритма для различных вычислительных систем с топологией многомерный тор с общим числом узлов $32$, $36$, $64$, $96$ и $144$, при этом рассмотрены 3х-мерные и 4х-мерные конфигурации топологий. Эксперимент проводился при помощи разработанного симулятора вычислительной системы. Для каждой исследуемой вычислительной системы была создана синтетическая очередь заданий, параметры которой приближены к реальным.

Средняя утилизация ресурсов для разработанного алгоритма выбора узлов увеличилась на $11\%$, а значение времени нахождения заданий в очереди сократилось на $57\%$ по сравнению с первоначальным вариантом алгоритма. 

В дальнейшем необходимо провести исследование разработанного алгоритма для систем большого размера, а также детально исследовать и провести возможную оптимизацию времени работы алгоритма. Также возможно провести исследование о влиянии перестановки задач в очереди для улучшения характеристик использования вычислительной системы.
\begin{biblio}
\bibitem{YangXu}
Lan Z., Tang W., Wang J., Yang X., Zhou Z., Zheng X. Balancing Job Performance with System Performance via Locality-aware Scheduling on Torus-connected Systems // 2014 IEEE International Conference on Cluster Computing (CLUSTER). 2014. P. 140--148. DOI:~10.1109/CLUSTER.2014.6968751. 

\bibitem{IBM_BGQ_Redbook}
IBM Redbooks Publication: IBM System Blue Gene Solution: Blue Gene/Q System Administration. 2013. 282 p.

\bibitem{reducing-fragmentation}
Tang~W., Lan~Z., Desai~N., Buettner~D., Yu~Y.
Reducing Fragmentation on Torus-Connected Supercomputers //
In Proceedings of the 2011 IEEE International Parallel Distributed Processing Symposium (IPDPS'11).
IEEE Computer Society, Washington, DC, USA. 2011. P. 828--839 DOI:~10.1109/IPDPS.2011.82.

\bibitem{CrayDoc2012}
Cray Document: Managing System Software for Cray XE and Cray XT Systems. 2010.

\bibitem{RSD2016}
Агарков~А.А., Исмагилов~Т.Ф., Макагон~Д.В., Семенов~А.С., Симонов~А.С. Результаты оценочного тестирования отечественной высокоскоростной коммуникационной сети Ангара // Суперкомпьютерные дни в России: Труды
международной конференции (26--27 сентября 2016 г., г. Москва). М.: Изд-во МГУ, 2016. С. 626--639.

\bibitem{Angara1}
Симонов~А.С., Макагон~Д.В., Жабин~И.А., Щербак~А.Н., Сыромятников~Е.Л.,
Поляков Д.А. Первое поколение высокоскоростной коммуникационной сети «Ангара»
// Наукоемкие технологии. 2014. Т. 15. №1. С. 21--28.

\bibitem{Puente}
Puente~V., Beivide~R., Gregorio~J.A., Prellezo~J.M., Duato~J., Izu~C.
Adaptive Bubble Router: a Design to Improve Performance in Torus Networks
// Proceedings of the International Conference Parallel Processing (ICPP). 1999. P. 58--67. DOI:~10.1109/ICPP.1999.797388.

\bibitem{Adiga}
Adiga~N.R., Blumrich~M., Chen~D. Blue Gene/L Torus Interconnection Network
// IBM Journal of Research and Development. 2005. Vol. 49. No. 2. P. 265--276. DOI:~10.1147/rd.492.0265.

\bibitem{Scott96-t3e}
Scott~S.L. The Cray T3E Network: Adaptive Routing in a High Performance 3D Torus. 1996.

\bibitem{Pozhilov}
Пожилов~И.А., Семенов~А.С., Макагон~Д.В. Алгоритм определения связности сети с топологией <<многомерный тор>> с отказами для детерминированной маршрутизации // Программная инженерия. 2015. № 3. С. 13--19.

\bibitem{Knapsack-Problem}
Кагиров~Р.Р. Многомерная задача о рюкзаке: новые методы решения // Вестник Сибирского государственного аэрокосмического университета им. академика МФ Решетнева. 2007. №3.

\bibitem{container-loading-problem}
Gonçalves J.F., Resende M.G.C. A Parallel Multi-population Biased Random-key Genetic Algorithm for a Container Loading Problem // Computers \& Operations Research. February 2012. Vol. 39. No. 2. P. 179--190. DOI:~10.1016/j.cor.2011.03.009.

\bibitem{search-alg}
Мукосей~А.В., Семенов~А.С., Приближенный алгоритм выбора оптимального подмножества узлов в коммуникационной сети Ангара с отказами // Вычислительные методы и программирование. 2017. Т. 18. C. 53--64.

\bibitem{placement-alg-aladishev}
Аладышев~О.С., Киселёв~Е.А. Алгоритм эффективного размещения программ на ресурсах многопроцессорных вычислительных систем // Программные продукты и системы. 2012. №4. C. 18--25.

\bibitem{Quasiplaner}
Баранов~А.В., Киселёв~Е.А., Ляховец~Д.С. Квазипланировщик для использования простаивающих вычислительных модулей многопроцессорной вычислительной системы под управлением СУППЗ // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2014. Т. 3. №4. С. 75--84. DOI:~10.14529/cmse140405.

\bibitem{Cluster-Simulator}
Полежаев~П.Н. Симулятор вычислительного кластера и его управляющей системы, используемый для исследования алгоритмов планирования задач // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. 2010. № 6. С. 79--90.

\bibitem{alloc-in-mesh}
Sharma D.D., Pradhan D.K. A Fast and Efficient Strategy for Submesh Allocation in Mesh-connected Parallel Computers // In Procs. of the 5th IEEE Symp. on Parallel and Distributed Processing. 1993. P. 682--689. DOI:~10.1109/SPDP.1993.395466.

\bibitem{Desmos}
Dlinnova~E., Smirnov~G., Stegailov~V., Biryukov~S., Kondratyuk~N. Hybrid Supercomputer Desmos with Torus Angara Interconnect: Performance and Efficiency Optimisation // 12th International Conference, PCT 2018, Rostov-na-Donu, Russia, April 2--6, 2018.

\end{biblio}

% Сведения об авторах (Ф.И.О.(полностью), степень, звание, кафедра (отдел), вуз, e-mail)
Мукосей Анатолий Викторович, научный сотрудник, сектор управления разработки вычислительной техники, акционерное общество <<Научно исследовательский центр электронной вычислительной техники>> (Москва, Российская Федерация)

Семенов Александр Сергеевич, к.т.н, зам. начальника отдела архитектуры и программного обеспечения суперкомпьютеров, акционерное общество <<Научно исследовательский центр электронной вычислительной техники>> (Москва, Российская Федерация)
%\newpage

{\phantom{eee} \hrule \vskip 4 pt}
\classify{} % Код MSC не нужен
%\classify{MSC 00000} % Коды MSC см. http://www.ams.org/msc/

\title{ALLOCATION OPTIMIZATION FOR REDUCING RESOURCE FRAGMENTATION IN ANGARA HIGH-SPEED INTERCONNECT}

\author{\copyright~2018 A.V.~Mukosey, A.S.~Semenov}

\address{JSC <<NICEVT>>\\
	117587 Moscow, Varshavskoye shosse 125c15}

\email{E-mail: \href{mailto:mukosey@nicevt.ru}{mukosey@nicevt.ru}, 
	\href{mailto:semenov@nicevt.ru}{semenov@nicevt.ru}}

\received{Received: \Received}

\maketitle{}

\begin{abstract}%
This paper considers a high-speed interconnect with a multidimensional topology.
The paper is devoted to the optimization of fragmentation resulting from sequential allocation of compute nodes in a supercomputer provided that network traffic from different user’s tasks should not overlap.
This paper proposes a method for searching nodes with an evaluation of the fragmentation of the system based on ideas from multidimensional container packaging problem.
For such an evaluation, the concept of rectangles is introduced, which can be inscribed into the system after placing the next user task.
Each set of nodes that is suitable for placing the task is evaluated by the proposed function taking into account the size and the number of found rectangles of maximum size.
The proposed method was evaluated using computer system model.
A set of different computer systems with three-dimensional and four-dimensional topologies was considered. The minimum system size is $32$ compute nodes and the maximum is $144$.
A synthetic queue of tasks is set for each system. The parameters of the synthetic queues are close to a real ones.
The average utilization of the resources of the computer system and the average waiting time for the tasks in the queue is chosen as a method quality criterion.
The study showed that the increase of the resources utilization for the proposed method averaged $11\%$ compared to the base method, and the average time spent in queue is reduced by  $45,3\%$.

\keywordsen{ Angara interconnect,  multidimensional torus, deterministic routing, direction ordered routing, fragmentation, allocation }
\end{abstract}

\begin{flushleft}
	\textbf{FOR CITATION}
\end{flushleft}
\justifying

\begin{citationplace}
Mukosey~A.V., Semenov~A.S. Allocation Optimization for Reducing Resource Fragmentation in Angara High-speed Interconnect. \textit{Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering}. 2018. vol.~X, no.~Y. pp.~Z1--Z2. (in Russian) DOI:~10.14529/cmseXXXXXX.
\end{citationplace}

\begin{biblio_lat}
\bibitem{YangXu}
Lan~Z., Tang~W., Wang~J., Yang~X., Zhou~Z., Zheng~X. Balancing job Performance with System Performance via Locality-aware Scheduling on Torus-connected Systems. 2014 IEEE International Conference on Cluster Computing (CLUSTER). 2014. pp. 140--148. DOI:~10.1109/CLUSTER.2014.6968751. 

\bibitem{IBM_BGQ_Redbook}
IBM Redbooks Publication: IBM System Blue Gene Solution: Blue Gene/Q system administration. 2013. 282 p.

\bibitem{reducing-fragmentation}
Tang~W., Lan~Z., Desai~N., Buettner~D., Yu~Y. 
Reducing Fragmentation on Torus-Connected Supercomputers. 
In Proceedings of the 2011 IEEE International Parallel Distributed Processing Symposium (IPDPS'11).
IEEE Computer Society, Washington, DC, USA. 2011. pp. 828--839 DOI:~10.1109/IPDPS.2011.82.

\bibitem{CrayDoc2012}
Cray Document: Managing System Software for Cray XE and Cray XT Systems. 2010.

\bibitem{RSD2016}
Agarkov~A.A., Ismagilov~T.F., Makagon~D.V. Performance Evaluation of the Angara Interconnect. in Proc. Int. Conf. on Russian Supercomputing Days, Moscow, Russia, September 26--27, 2016 (Mosk. Gos. Univ., Moscow, 2016), pp. 626--639.

\bibitem{Angara1}
Simonov~A.S., Makagon~D.V., Zhabin~I.A., Shcherbak~A.N., Syromyatnikov~E.L.,
Polyakov D.A. The First Generation of Angara High-Speed Interconnect. Science Technologies. 2014. vol. 15. no. 1. pp. 21--28.

\bibitem{Puente}
Puente~V., Beivide~R., Gregorio~J.A., Prellezo~J.M., Duato~J., Izu~C.
Adaptive Bubble Router: a Design to Improve Performance in Torus Networks.
Proceedings of the International Conference Parallel Processing (ICPP). 1999. pp. 58--67. DOI:~10.1109/ICPP.1999.797388.

\bibitem{Adiga}
Adiga~N.R., Blumrich~M., Chen~D.. Blue Gene/L Torus Interconnection Network.
IBM Journal of Research and Development. 2005. vol. 49. no. 2. pp. 265--276. DOI:~10.1147/rd.492.0265.

\bibitem{Scott96-t3e}
Scott~S.L., et al. The Cray T3E Network: Adaptive Routing in a High.
Performance 3D Torus. 1996.

\bibitem{Pozhilov}
Pozhilov~I.A., Semenov~A.S., Makagon~D.V., Connectivity Problem Solution for Direction Ordered
Deterministic Routing in nD Torus. Software Engineering. 2015. no. 3. pp. 13--19.

\bibitem{Knapsack-Problem}
Kagirov~R.R. Multiple Knapsack Problem: New Solving Methods. Vestnik
of the Reshetnev Siberian State Aerospace University. 2007. iss. 3. pp. 16--20 (in Russ.). 

\bibitem{container-loading-problem}
Gonçalves J. F., Resende M. G. C. A Parallel Multi-population Based Random-key Genetic Algorithm for a Container Loading Problem. Computers \& Operations Research. February 2012. vol. 39. no. 2. pp. 179--190. DOI:~10.1016/j.cor.2011.03.009.

\bibitem{search-alg}
Mukosey~A.V., Semenov~A.S. An Approximate Algorithm for Choosing the Optimal Subset of Nodes in the Angara Interconnect with Failures. Numerical methods and Programming. 2017. vol. 18. pp. 53--64.

\bibitem{placement-alg-aladishev}
Aladyshev~O.S., Kiselov~E.A. An efficient application mapping algorithm for multiprocessor systems. Software \& Systems. 2012. no. 4. pp. 18--25.

\bibitem{Quasiplaner}
Baranov~A.V., Kiselev~E.A., Lyakhovets~D.S. The quasi scheduler for utilization of multiprocessing computing system's idle resources under control of the management system of the parallel jobs. Vestnik Yuzhno-Ural'skogo Gosudarstvennogo Universiteta. Seriya <<Vychislitelnaya Matematika i Informatika>>. 2014. vol. 3. no. 4. pp. 75--84. DOI:~10.14529/cmse140405.

\bibitem{Cluster-Simulator}
Polezhaev~P.N. Simulator of computer cluster and its management system used for research of job scheduling algorithms. Vestnik Yuzhno-Ural'skogo Gosudarstvennogo Universiteta. Seriya <<Vychislitelnaya Matematika i Informatika>>. 2010. vol. 6. pp. 79--90.

\bibitem{alloc-in-mesh}
Sharma D. D., Pradhan D. K. A fast and efficient strategy for submesh allocation in mesh-connected parallel computers. In Procs. of the 5th IEEE Symp. on Parallel and Distributed Processing. 1993. pp. 682--689. DOI:~10.1109/SPDP.1993.395466.

\bibitem{Desmos}
Dlinnova~E., Smirnov~G., Stegailov~V., Biryukov~S., Kondratyuk~N. Hybrid Supercomputer Desmos with Torus Angara Interconnect: Performance and Efficiency Optimisation.  12th International Conference, PCT 2018, Rostov-na-Donu, Russia, April 2--6, 2018.
\end{biblio_lat}

\end{document}
