\documentclass{cmi}
\usepackage{upgreek}

% Данные поля заполняются редакцией журнала
%\makeatletter
%\newcommand{\@volume}{}
%\newcommand{\@issue}{}
%\newcommand{\@num}{}
%\newcommand{\@pages}{}

% Подключение bib файлов
%\addbblresources{biblio_ru.bib}{biblio_en.bib}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{enumitem}
\begin{document}

% ЗАПОЛНЯЕТСЯ АВТОРАМИ: Релевантные коды УДК статьи
% (см. http://teacode.com/online/udc/)
\classify{УДК 004.432.4}


\title{РЕСУРСОНЕЗАВИСИМОЕ ОПИСАНИЕ \\ ИНФОРМАЦИОННЫХ ГРАФОВ \\ С ДИСТРИБУТИВНЫМИ ОПЕРАЦИЯМИ \\ НА ЯЗЫКЕ ПРОГРАММИРОВАНИЯ SET@L}

\authors{И.И.~Левин$^{1}$, И.В.~Писаренко$^{2}$, Д.В.~Михайлов$^{2}$, А.К.~Мельников$^{3}$, А.И.~Дордопуло$^{2}$}

\organizations{$^{1}$Южный федеральный университет\\
	(347928 Таганрог, пер.~Некрасовский, д.~44),\\ 
	$^{2}$<<НИЦ супер-ЭВМ и нейрокомпьютеров>>\\ (347922 Таганрог, пер.~Итальянский, д.~106)\\
	$^{3}$АО <<Вычислительные решения>>\\ (117587 Москва, Варшавское ш.~, д.~125с17)}

\newcommand{\emailsinsert}{\href{mailto:iilevin@sfedu.ru}{iilevin@sfedu.ru}, \href{mailto:pisarenko@superevm.ru}{pisarenko@superevm.ru}, \href{mailto:mixailow.den@gmail.com}{mixailow.den@gmail.com}, \href{mailto:ak@comp-sol.ru}{ak@comp-sol.ru}, \href{mailto:dordopulo@superevm.ru}{dordopulo@superevm.ru} }

% ЗАПОЛНЯЕТСЯ АВТОРАМИ: Дата поступления статьи в редакцию 
\newcommand{\rdate}{05.05.2022}
\emails{\emailsinsert}
\redactiondate{\rdate}

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

% Оформление аннотации
\begin{abstract}%
В данной работе предлагается преобразовать стандартную последовательную топологию информационного графа с дистрибутивными операциями к комбинированному варианту с последовательными и параллельными фрагментами, что позволяет эффективно описать реализацию вычислений в ресурсонезависимой форме. Конечная топология зависит от доступного вычислительного ресурса реконфигурируемой системы и обеспечивает повышение удельной производительности в сравнении с исходным вариантом. Разработанный алгоритм преобразования линейной структуры в различные комбинированные топологии в зависимости от конфигурации вычислительной системы описан на языке программирования Set@l.

\keywords{дистрибутивные операции, ресурсонезависимое программирование, реконфигурируемые вычислительные системы, редукция производительности, Set@l, признаки <<разбиение пополам>> и <<голова/хвост>>.}
\end{abstract}

%Образец цитирования статьи
\forcitation{Левин~И.И., Писаренко~И.В., Михайлов~Д.В., Мельников~А.К., Дордопуло~А.И. Ресурсонезависимое описание информационных графов с дистрибутивными операциями на языке программирования Set@l}

%Верхние колонтитулы
\markboth{И.И.~Левин, И.В.~Писаренко, Д.В.~Михайлов, А.К.~Мельников, А.И.~Дордопуло}{Ресурсонезависимое описание информационных графов \ldots}

% Заголовки разделов формируются при помощи команд  \section{}, \subsection{}, \subsubsection{}
\section*{Введение}
\label{sec-intro}
Информационные графы многих прикладных задач имеют последовательную (линейную) топологию, поэтому реализация их распараллеливания (ускорения) в общем виде затруднительна. Однако, если операции графа обладают определенными свойствами, такими как дистрибутивность и ассоциативность, то целесообразно преобразовать их к виду, для которого допустимо параллельное (ускоренное) выполнение. Например, в работе~\bblcite{LevinDPMM21} показано, что за счет перестановки вершин в информационном графе с ассоциативными операциями и дальнейшей оптимизации вычислительной структуры время решения задачи может быть сокращено в число раз, соответствующее латентности операционной вершины. В данной статье представлен другой пример оптимизации последовательного информационного графа с дистрибутивными операциями для реализации на реконфигурируемых ВС с различными конфигурациями. Подобные графы широко применяются для решения многих задач цифровой обработки сигналов~\bblcite{TanJ13, WinserC17}. Для практического применения предложенных преобразований необходимы эффективные методы и средства представления параллельных программ в ресурсонезависимом виде.
В работах~\bblcite{LevinDPM19, LevinDPM19-2, LevinDPM19-3} предложен язык архитектурно-независимого параллельного программирования Set@l (Set Aspect-Oriented Language), основанный на парадигме аспектно-ориентированного программирования (АОП) и теоретико-множественном представлении исходного кода программы. Описав базовую топологию графа с дистрибутивными операциями и принципы ее преобразования в виде специальных признаков метода обработки на языке Set@l, возможно синтезировать множество вариантов топологий и переходить между ними путем изменения типов и разбиений совокупностей. Приведение графа к оптимальному виду при заданном объеме вычислительного ресурса реконфигурируемой ВС может осуществляться без изменения исходного кода программы.

\section{Преобразование информационных графов с дистрибутивными операциями}
\label{sec-feel}

Рассмотрим последовательный информационный граф, топология которого изображена на рис.~\ref{Fig1}. Представленный граф состоит из чередующихся операционных вершин $\alpha$ и $\beta$, причем обе базовые операции обладают свойством ассоциативности, а операция $\beta$ является дистрибутивной по отношению к операции $\alpha$. Граф на рис.~\ref{Fig1} позволяет вычислить последовательность коэффициентов $W_{1}, W_{2}, \ldots W_{n}$, определяемых следующей рекуррентной формулой:
\begin{figure}[h]
	\centering
	\includegraphics[scale=0.8]{Fig1}
	\caption{Последовательный информационный граф с дистрибутивными операциями $\alpha$ и $\beta$}
	\label{Fig1}
\end{figure}

Граф на рис.~\ref{Fig1} позволяет вычислить последовательность коэффициентов $W_{1}, W_{2}, \ldots W_{n}$, определяемых следующей рекуррентной формулой:
\begin{equation}
\label{eq1}
    W_{0}=x_{1};\quad W_{i}=(W_{i-1}\alpha \chi_{i+1})\beta b_{i},\quad i=1, 2, \ldots, N,
\end{equation}
где $N$~-- мощность множества, включающего все коэффициенты $\beta_{i}$. Время выполнения всех операций графа составляет

\begin{equation}
\label{eq2}
T_{G}=\tau \cdot N \cdot (l_{\alpha}+l_{\beta}),
\end{equation}
где $\tau$~-- длительность такта в секундах; $l_{\alpha, }$, $l_{\beta}$~-- латентности операционных вершин $\alpha$ и $\beta$ в тактах.

Предположим, что объем доступного вычислительного ресурса $R$ реконфигурируемой ВС не ограничен. Тогда для сокращения времени решения задачи $T_G$ возможно модифицировать последовательную топологию на рис.~\ref{Fig1}, используя свойства дистрибутивности и ассоциативности операций $\alpha$ и $\beta$. Введем элементарные преобразования пар вершин, показанные на рис.~\ref{Fig2},~а и б. Преобразование на рис.~\ref{Fig2},~а перегруппирует пару последовательно соединенных вершин $\alpha$ и $\beta$ в соответствии с законом дистрибутивности:

\begin{equation}
\label{eq3}
\left(\alpha(a, b, i), \beta(i, c, r)\right)=\left(\beta (a, c, i), \beta(b, c, ii), \alpha(i, ii, r)\right),
\end{equation}
где $a$, $b$, $c$~-- входные вершины; $r$~-- выходная вершина; $i$, $ii$~-- дуги, соответствующие промежуточным результатам вычислений. Преобразование на рис. ~\ref{Fig2},~б представляет собой слияние двух ассоциативных вершин $\beta$ в одну вершину $\beta$, на вход которой подается множество исходных операндов:

\begin{equation}
\label{eq4}
( \beta(a, b, i), \alpha(i, c, r))= \beta (a, \{b, c\}, r).
\end{equation}

\begin{figure}[h]
	\centering
	\includegraphics[scale=0.6]{Fig2}
	\caption{Преобразование пары дистрибутивных вершин $\alpha$ и $\beta$ (а) и слияние пары ассоциативных вершин (б), показанное на примере операции $\beta$}
	\label{Fig2}
\end{figure}

Последовательно применяя преобразования на рис.~\ref{Fig2},~а и б к исходному линейному графу (см. рис.~\ref{Fig1}), возможно получить модифицированную топологию с множеством подграфов-ветвей, одна из которых состоит только из вершин $\alpha$, а остальные~-- только из вершин $\beta$, как показано на рис.~\ref{Fig3},~а.

Теперь, когда граф разбит на фрагменты, содержащие ассоциативные операционные вершины только одного типа $\alpha$ или $\beta$ (см. рис.~\ref{Fig3},~а), возможно распараллелить вычисления, преобразовав каждый из последовательных подграфов к пирамидальному виду~\bblcite{Karepova16}. В результате будет получена топология, изображенная на рис.~\ref{Fig3},~б и включающая нижний пирамидальный подграф из вершин $\alpha$, входы которого соединены с выходами множества верхних пирамидальных подграфов, составленных из вершин $\beta$. Размер пирамид из вершин  $\beta$ будет меняться от $N$ вершин (для двух крайних левых подграфов на рис.~\ref{Fig3},~б) до одной вершины (крайне правая пирамида на рис.~\ref{Fig3},~б).

\begin{figure}[h]
	\centering
	\includegraphics[scale=0.35]{Fig3}
	\caption{Модифицированные топологии информационного графа с дистрибутивными операциями $\alpha$ и $\beta$ с последовательными (а) и параллельными (б) подграфами-ветвями}
	\label{Fig3}
\end{figure}


Время выполнения всех операций информационного графа на рис.~\ref{Fig3},~б является минимальным и составляет
\begin{equation}
\label{eq5}
T_{G}=(l_{\alpha}+l_{\beta}) \cdot \lceil \log_2 N \rceil \cdot \tau,
\end{equation}
где $\lceil \quad \rceil$~-- округление до целого в большую сторону. В формуле~(\ref{eq5}) округление множителя $\log_2 N$ учитывает случаи, когда размерность пирамидальных подграфов необходимо дополнить до степени 2. В отличие от исходной топологии (см. рис.~\ref{Fig1}) информационные графы на рис.~\ref{Fig3} характеризуются существенно большим объемом аппаратного ресурса, занимаемого соответствующими им вычислительными структурами: количество вершин $\beta$ возрастает до $(N^2+N)/2$, тогда как число вершин $\alpha$ остается равным $N$. Например, если в исходном графе была 1000 вершин $\beta$, то после преобразования их количество возрастет более чем в 500~раз.

На практике при решении задач даже небольшой размерности может возникнуть ситуация, когда объем аппаратного ресурса реконфигурируемой ВС недостаточен для реализации топологий, изображенных на рис.~\ref{Fig3}. Анализируя информационный граф на рис.~\ref{Fig3},~а, выделим следующие особенности:
\begin{itemize}
	\item[--]каждая ветвь из вершин $\beta$ использует только одну из переменных $x_i$;

	\item[--]на две левые ветви из вершин $\beta$ подаются все коэффициенты $\{b_1 \ldots b_N \}$, а на каждую последующую ветвь~-- на один коэффициент меньше, то есть $m$-я ветвь оперирует коэффициентами $\{b_{m-1} \ldots b_N \}$.
\end{itemize}

Поскольку операция $\beta$ ассоциативна, перегруппируем вершины в ветвях таким образом, чтобы блоки с входами $\{x_1  \ldots x_{N+1}\}$ располагались вплотную к подграфу из вершин $\alpha$ (см. рис.~\ref{Fig4},~а). В результате такого преобразования каждая ветвь, кроме крайней правой, будет содержать вершину $\beta$ с входами $b_{N-1}$ и $b_N$ (выделены на рис.~\ref{Fig4},~а). Оставим одну вершину $\beta(b_{N-1}, b_{N}, i)$ в крайней левой ветви и удалим повторяющиеся вершины, подав на входы остальных ветвей данные с выхода $i$ (см. рис.~\ref{Fig4},~б). В полученном графе возникнет новое множество идентичных вершин $\beta(i, b_{N-2}, ii)$, которое выделено на рис.~\ref{Fig4},~б и может быть заменено одной вершиной аналогичным образом. Каждый шаг преобразования уменьшает количество вершин $\beta$ и формирует промежуточную топологию, реализуемую на ВС с определенным объемом вычислительного ресурса. В предельном случае, показанном на рис.~\ref{Fig4}, в, процедура удаления одинаковых вершин повторялась до тех пор, пока во всех ветвях, кроме крайней левой, не осталось  по одной вершине $\beta$. Количество вершин $\beta$ в такой топологии равно $2 \ast N-1$ вместо $(N^2+N)/2$ в исходном графе (см. рис.~\ref{Fig4},~а). Линейку вершин $\alpha$ в графе на рис.~\ref{Fig4} в целесообразно преобразовать в пирамиду (см. рис.~\ref{Fig4},~г), обеспечив снижение времени выполнения всех операций до 
\begin{equation}
\label{eq6}
T_{G}=(l_{\alpha} \cdot \lceil \log_2 N \rceil + l_{\beta} \cdot N) \cdot \tau.
\end{equation}

Дальнейшее уменьшение аппаратных затрат возможно при разбиении исходного графа (см. рис.~\ref{Fig1}) на линейные изоморфные подграфы, содержащие максимальное реализуемое число вершин, однако при таком подходе время решения задачи $T_G$ будет не оптимальным. Более эффективный подход предполагает преобразование каждого подграфа к виду, аналогичному рис.~\ref{Fig4},~г.

\begin{figure}[h]
	\centering
	\includegraphics[scale=0.6]{Fig4}
	\caption{Модификация информационного графа с дистрибутивными операциями: перестановка вершин $\beta$ в ветвях (а), однократное удаление повторяющихся вершин $\beta$ (б), граф с одной полной ветвью (в) и перегруппировка вершин $\alpha$ в пирамидальную структуру (г)}
	\label{Fig4}
\end{figure}

Если количество операционных вершин в графе с дистрибутивными операциями после модификаций, представленных на рис.~\ref{Fig3} и~\ref{Fig5}, все еще велико для реализации соответствующей вычислительной структуры на имеющемся аппаратном ресурсе, то для формирования плотного потока данных необходимо выполнить следующие преобразования. Вернемся к последовательной топологии (см. рис.~\ref{Fig1}) и разобьем исходный граф на изоморфные подграфы, содержащие по $L$ линейно соединенных пар вершин $\alpha$ и $\beta$. Далее, используя предложенную выше методику, приведем каждый выделенный подграф к виду <<полная линейка $\beta$~-- пирамида $\alpha$>>, показанному на рис.~\ref{Fig5},~а. В соответствующей полученному графу вычислительной структуре обратная связь будет охватывать полную линейку операций $\beta$ и пирамиду операций $\alpha$, поэтому интервал обработки данных будет достаточно высоким. Для его снижения перегруппируем вершины таким образом, чтобы обратная связь охватывала только пару вершин $\alpha$ и $\beta$. Поскольку операция $\alpha$ ассоциативна, полную пирамиду размерности $N$ можно заменить на пирамиду меньшей размерности $(N-1)$ и одиночную операционную вершину $\alpha$, как показано на рис.~\ref{Fig5},~б. Вместе с вершиной $\alpha$ из линейки операций $\beta$ будет вынесена одна ближайшая к пирамиде вершина $\beta$, поэтому в конечной вычислительной структуре на рис.~\ref{Fig5},~б обратной связью будет охвачено всего две вершины, по одной каждого типа. Чтобы обеспечить минимальный интервал обработки данных, размерность выделенных подграфов должна соотноситься с латентностями операционных вершин: $L= (l_{\alpha}+l_{\beta} )$. После описанного преобразования время решения задачи составит:
\begin{equation}
\label{eq7}
T_{G}=\left(L+\left \lceil \frac{N}{l_{\alpha}+l_{\beta}} \right \rceil  \right) \cdot \tau,
\end{equation}
где $L=(l_{\alpha}+l_{\beta}) \cdot l_{\beta}+\lceil \log_2 (l_{\alpha}+l_{\beta}) \rceil \cdot l_{\alpha})$~-- длина критического пути в тактах для вычислительной структуры на рис.~\ref{Fig5}, б.

Если аппаратный ресурс реконфигурируемой ВС недостаточен даже для реализации вычислительной структуры на рис.~\ref{Fig5},~б, то целесообразно использовать минимальную структуру с парой вершин $\alpha$ и $\beta$. В таком случае время выполнения всех операций графа составит
\begin{equation}
\label{eq8}
T_{G}=(l_{\alpha}+l_{\beta}) \cdot \tau \cdot N.
\end{equation}

\begin{figure}[h]
	\centering
	\includegraphics[scale=0.35]{Fig5}
	\caption{Преобразованный фрагмент исходного информационного графа (а) и вычислительная структура (б), получаемая при вынесении пары вершин $\alpha$ и $\beta$}%
	\label{Fig5}
\end{figure}

Таким образом, в зависимости от соотношения объемов вычислительного ресурса $R_{\alpha}$ и $R_{\beta}$, доступных для реализации вершин соответствующих типов, их латентностей $l_{\alpha}$ и $l_{\beta}$, а также размерности обрабатываемых массивов данных $N$ возможно выделить несколько способов построения вычислительной структуры, обеспечивающих разные скорости решения задачи.  Ниже приведено составное выражение, позволяющее рассчитать время выполнения всех операций графа для каждого из этих случаев:

\begin{equation}
\label{eq9}
T_G=  
\begin{cases}
(l_\alpha+l_\beta) \cdot \lceil  \log_2 N  \rceil \cdot \tau,\;\;\text{если}\;\;R_{\alpha} \ge N, R_{\beta} \ge \frac{N^2+N}{2}; \\
(l_\alpha \cdot  \lceil  \log_2 N  \rceil +  l_\beta \cdot N) \cdot \tau,\;\;\text{если}\;\;R_{\alpha} \ge N,\;2N \le R_{\beta} < \frac{N^2+N}{2}; \\
\left\{ { (l_\alpha+l_\beta - 1) \cdot l_\beta + \lceil  \log_2 (l_\alpha+l_\beta) \rceil \cdot l_\alpha + \lceil \frac{N}{l_\alpha+l_\beta} \rceil} \right\} \cdot \tau \cdot (l_\alpha+l_\beta), \\
\text{если}\;\;l_\alpha+l_\beta \le R_{\alpha} < N,\;2 \cdot (l_\alpha+l_\beta) \le R_{\beta} < 2N; \\
\left\{ {(k-1) \cdot l_\beta + \lceil  \log_2 k  \rceil \cdot l_\alpha + \frac{N}{k}} \right\}  \cdot \tau \cdot (l_\alpha+l_\beta), \\
\text{если}\;\; R_{\alpha} < l_\alpha+l_\beta,\;R_{\beta} < 2 \cdot (l_\alpha+l_\beta),
\end{cases}
\end{equation}
где $(k-1)$~-- число автоподстановок~\bblcite{LevinD21}.

Первый вариант описывает предельный случай, когда аппаратного ресурса достаточно для реализации вычислительной структуры, соответствующей полному графу с пирамидальными подграфами на рис.~\ref{Fig3},~б, что позволяет выполнить все операции за наименьшее время. Второй вариант описывает ситуацию, когда аппаратного ресурса $R_{\beta}$ не хватает на построение множества пирамидальных структур, но хватает на построение линейки, использование которой позволяет удалить повторяющиеся вершины (см. топологию на рис.~\ref{Fig4},~г). Третий вариант описывает ситуацию, когда доступного ресурса не хватает на реализацию всего графа целиком, но достаточно для реализации подсистемы, охваченной обратной связью, включающей в себя $l_{\alpha}+l_{\beta}$ блоков $\alpha$ и $2 \cdot (l_{\alpha}+l_{\beta})$ блоков $\beta$ (см. вычислительную структуру на рис.~\ref{Fig5},~б). Наконец, последний вариант описывает случай, когда оборудования не хватает для того, чтобы реализовать даже описанную выше подсистему. В таком случае автоподстановка реализуется столько раз, сколько позволяет объем свободного аппаратного ресурса. В предельном случае $k=l_{\alpha}+l_{\beta}$ рассматриваемое выражение переходит в третье, а при $k=1$~-- в формулу~(\ref{eq8}) для минимальной вычислительной структуры с парой вершин $\alpha$ и $\beta$, охваченных обратной связью.

Если исходный последовательный граф состоит из чередующихся вершин, содержащих ассоциативные операции двух типов, одна из которых является дистрибутивной по отношению к другой, мы можем значительно ускорить выполнение всех операций графа. Степень этого ускорения зависит от того, сколько вычислительных блоков возможно реализовать на доступном нам оборудовании и как именно будет преобразован исходный граф. При этом в случае, если мы реализуем вычислительную систему с обратной связью, глубина которой и размер системы определяется суммарной латентностью блоков $\alpha$ и $\beta$, то мы получим лучший результат, чем при реализации всего графа целиком, при условии, что у нас не хватает ресурса для представления всех блоков $\beta$ в виде пирамидальной структуры.

\section{Ресурсонезависимая программа на языке Set@l}
\label{sec-Set}

Традиционные методы параллельного программирования, как правило, оперируют информационным графом с фиксированной структурой, поэтому их использование для описания преобразований топологии графа с дистрибутивными операциями (см. рис.~\ref{Fig1}--\ref{Fig5}) достаточно трудоемко и малоэффективно. Код ресурсонезависимой программы, которая реализует рассмотренные преобразования, будет состоять из множества подпрограмм, связанных условными операторами и задающих отдельные варианты топологий. В отличие от классических языков параллельного программирования, возможности языка архитектурно-независимого программирования Set@l позволяют описать принципы построения и модификации графов с дистрибутивными операциями в виде множеств типов <<голова/хвост>> и <<разбиение пополам>> и правил их декомпозиции. В таком случае исходный код программы описывает не отдельные реализации, а множество возможных топологий графа для заданной размерности задачи. Аспекты выбирают определенный вариант топологии, исходя из конкретных значений параметров конфигурации. Для изменения структуры информационного графа достаточно изменить тип и разбиение множеств, тогда как исходный код программы, описывающий математическую сущность алгоритма, остается неизменным.

Исходный код программы на языке Set@l, приведенный на рис.~\ref{Fig6}, описывает базовую последовательную топологию графа с дистрибутивными операциями (см. рис.~\ref{Fig1}). Отметим, что вершины $\alpha$ (\texttt{alpha}) и $\beta$ (\texttt{beta}) могут соответствовать как простым операциям над числами с фиксированной запятой, так и более сложным операциям сложения и умножения комплексных чисел, векторов и матриц.

\begin{figure}[h]
	\centering
	\includegraphics[scale=0.35]{Fig6}
	\caption{Исходный код программы на языке Set@l, описывающий последовательную топологию информационного графа с дистрибутивными операциями (см. рис.~\ref{Fig1})}
	\label{Fig6}
\end{figure}

Полный граф описывается рекурсивно (\texttt{Rec}, см. строку (1) на рис.~\ref{Fig6}) как отношение~\texttt{F} между множествами переменных \texttt{X} и коэффициентов \texttt{B} и результирующим элементом~\texttt{r}. Поскольку граф строится по последовательному принципу <<голова/хвост>>, в условии завершения рекурсии (\texttt{break}, строки (2)--(4)) и правиле раскрытия итераций (\texttt{main}, строки (5), (6)) используются соответствующие признаки \texttt{Head} (<<голова>>: выделение первого элемента множества) и \texttt{Tail} (<<хвост>>: выделение подмножества, содержащего все элементы исходного множества, кроме первого). Альтернативный принцип построения графов, рассматриваемый в данной работе, -- <<разбиение пополам>> -- предполагает формирование параллельной пирамидальной структуры.

На каждой итерации (см. строки (5), (6) на рис.~\ref{Fig6}) линейку дистрибутивных операций~\texttt{F} над множествами \texttt{X} и \texttt{B} можно представить как аналогичную линейку операций над <<хвостами>> этих множеств и пару связанных через элемент \texttt{i} вершин $\alpha$ и $\beta$, на входы которых подаются <<головы>> множеств \texttt{X} и \texttt{B} и промежуточный результат \texttt{e} последовательного выполнения ассоциативных операций \texttt{F} над \texttt{Tail(X)}, \texttt{Tail(B)}, а выход \texttt{r} является конечным или промежуточным результатом вычислений. Так как исходный последовательный граф не привязан к какой-либо вычислительной архитектуре, все его элементы связаны между собой по параллельно-зависимому принципу \texttt{conc}~\bblcite{LevinDPM19(3)}. При выполнении условия завершения рекурсии (строки (2)--(4)) последняя линейка операций \texttt{F} преобразуется в особую пару вершин, на входы которой подаются оставшиеся элементы множеств~\texttt{X}~и~\texttt{B}.

На рис.~\ref{Fig7} представлен код на языке программирования Set@l, который описывает базовое преобразование пары дистрибутивных вершин $\alpha$ и $\beta$ (признак \texttt{distr}, строки (1)--(4), см. рис.~\ref{Fig2},~а) и слияние пары ассоциативных вершин любого типа (признак \texttt{mrg}, строки (5)--(8), см. рис.~\ref{Fig2},~б), на основе которых осуществляется дальнейшая модификация последовательного информационного графа. Преобразование \texttt{mrg} позволяет передать тип \texttt{H/T} (<<голова/хвост>>) или \texttt{DIV2} (<<разбиение пополам>>) формируемому множеству \texttt{k}, подаваемому на вход блока \texttt{f}.

\begin{figure}[h]
	\centering
	\includegraphics[scale=0.4]{Fig7}
	\caption{Код базовых признаков, описывающих преобразование пары дистрибутивных вершин (\texttt{distr}) и слияние пары ассоциативных вершин (\texttt{mrg}), на языке программирования Set@l}
	\label{Fig7}
\end{figure}


Фрагмент программы на языке Set@l изображенный на рис.~\ref{Fig8}, определяет процедуру преобразования \texttt{Tr} линейного информационного графа с дистрибутивными операциями (см. топологию на рис.~\ref{Fig1} и код на рис.~\ref{Fig6}) к топологии с подграфами-ветвями (см. рис.~\ref{Fig3},~а). Движение по итерациям начинается от пары вершин $\alpha$ и $\beta$, соединенной с выходом \texttt{r}.

На каждой итерации (\texttt{main}, см. строки (6)--(8) на рис.~\ref{Fig8}) последовательно (\texttt{seq}) реализуются одно преобразование пары дистрибутивных вершин (\texttt{distr}, строка (6)) и два отдельных слияния (\texttt{mrg}, строки (6)--(8)) групп ассоциативных вершин $\alpha$ и $\beta$. В итоге граф представляется как объединение этих операций с аналогичным подграфом, вершины которого входят в множество $\texttt{Tail}^2\texttt{(G)=Tail(Tail(G))}$. Преобразования \texttt{mrg} осуществляются над группами вершин, связанных общими элементами \texttt{c}, а характер параллелизма объединяемых вершин определяется передаваемыми типами \texttt{talpha} и \texttt{tbeta} (\texttt{H/T} или \texttt{DIV2}). Строки (10)--(14) описывают параллелизм ветвей из вершин $\beta$, свойственный для графа с топологией на рис.~\ref{Fig3},~а.

Переход от топологии с последовательными подграфами-ветвями (см. рис.~\ref{Fig3},~а) к его параллельной реализации (см. рис.~\ref{Fig3},~б) может осуществляться за счет передачи типов \texttt{talpha=‘DIV2’} и \texttt{tbeta=‘DIV2’} при вызове процедуры \texttt{Tr}.

\begin{figure}[h]
	\centering
	\includegraphics[scale=0.4]{Fig8}
	\caption{Код преобразования исходного информационного графа (см. рис.~\ref{Fig1}) в структуру с последовательными подграфами-ветвями (см. рис.~\ref{Fig3},~а) на языке Set@l}
	\label{Fig8}
\end{figure}

На следующем этапе топология с подграфами-ветвями (см. рис.~\ref{Fig3},~а) оптимизируется путем удаления повторяющихся вершин $\beta$ (см. рис.~\ref{Fig8}). Соответствующая процедура \texttt{Gcut} задается фрагментом кода на языке программирования Set@l, представленном на рис.~\ref{Fig9}. Признак \texttt{vcut} (см. строки (1)--(3)) выделяет пару вершин $\beta$ с одинаковыми входами \texttt{c}, \texttt{f} и разными выходами \texttt{e}, \texttt{ee} и заменяет их на одну вершину с объединенным выходом \texttt{k}, в котором обе связи реализуются параллельно (\texttt{par}). Процедура \texttt{scut} (см. строки (4)--(7)) последовательно выделяет все повторяющиеся вершины в текущем графе \texttt{B} и применяет к ним преобразование \texttt{vcut}. Процесс продолжается до тех пор, пока из исходной группы не останется одна уникальная вершина (см. рис.~\ref{Fig4},~б). Процедура \texttt{Gcut} многократно повторяет преобразование \texttt{scut} и приводит граф к виду, показанному на рис.~\ref{Fig4}, в: все ветви из вершин $\beta$, кроме первой, содержат по одной вершине, а повторяющиеся вершины полностью удалены.

\begin{figure}[h]
	\centering
	\includegraphics[scale=0.4]{Fig9}
	\caption{Фрагмента кода программы на языке Set@l, реализующий удаление повторяющихся вершин $\beta$ (см. рис.~\ref{Fig4})}
	\label{Fig9}
\end{figure}

После оптимизации топологии графа (см. код на рис.~\ref{Fig9}) необходимо синтезировать вычислительную структуру \texttt{CS}, показанную на рис.~\ref{Fig5},~б. Для этого множества входных данных \texttt{XD} и \texttt{BD} типа \texttt{pipe} (конвейерная обработка) разбиваются на подмножества типа \texttt{conc} (параллельно-зависимая обработка), размерность которых определяется латентностями операционных вершин $l_\alpha$ (\texttt{la}) и $l_\beta$ (\texttt{lb}), а затем преобразование \texttt{FG}, описанное на рис.~\ref{Fig6}--\ref{Fig9}, выполняется над каждым подмножеством (\texttt{sub}):\\
\texttt{XD=pipe(\textbf{union}[conc(x(a) \ldots x(b))|(x(a),x(b)) \textbf{in} X \&\& \\  
\indent\qquad\qquad\qquad\qquad\qquad\qquad	\qquad a \textbf{in} set(1,la+lb+1, \ldots) \&\&  \\  
\indent\qquad\qquad\qquad\qquad\qquad\qquad	\qquad b \textbf{in set}(la+lb,2*(la+lb), \ldots)]); \\  
BD=pipe(\textbf{union}[conc(b(c) \ldots b(d))|(b(c),b(d)) \textbf{in} B \&\& \\ 
\indent\qquad\qquad\qquad\qquad\qquad\qquad	\qquad	c \textbf{in set}(1,la+lb+1, \ldots) \&\&  \\
\indent\qquad\qquad\qquad\qquad\qquad\qquad	\qquad	d \textbf{in set}(la+lb,2*(la+lb), \ldots)]]); \\ 
CS=FG(x,b,r| \textbf{forall} sub(x) \textbf{in} XD \&\& \textbf{forall sub}(b) \textbf{in} BD); }

В итоге будет получена вычислительная структура, изображенная на рис.~\ref{Fig5}, а. Чтобы перейти к конечной вычислительной структуре, изображенной на рис.~\ref{Fig5},~б, необходимо выделить множество входов \texttt{A} пирамиды из вершин $\alpha$ и модифицировать его следующим образом:\\
\texttt{A=(a|beta(c,d,a) \&\& alpha(a,b,e));\\
A*=(H/T(DIV2(a1\ldots ak-1), ak)|k=cap(A));}

Представленный в данном разделе код на языке программирования Set@l учитывает все случаи, выделенные в формуле~(\ref{eq9}), и позволяет описать реализацию информационных графов с дистрибутивными операциями на реконфигурируемых ВС в компактной ресурсонезависимой форме.

\section*{Заключение}
\label{sec-conclusion}

Таким образом, в данной статье показан метод, который за счет перестановки вершин в информационном графе с дистрибутивными операциями и дальнейшей оптимизации вычислительной структуры позволяет ускорить выполнение всех операций графа, причем степень этого ускорения зависит от того, сколько вычислительных блоков возможно реализовать на имеющемся аппаратном ресурсе. Язык архитектурно-независимого программирования Set@l обеспечивает описание преобразований в компактной ресурсонезависимой форме. В отличие от традиционных языков параллельного программирования, в которых изменение топологии информационного графа требует модификации исходного кода программы, Set@l задает множество вариантов реализации в одной программе, а синтез конкретной вычислительной структуры осуществляется автоматически в соответствии с заданными пользователем параметрами конфигурации -- объемом доступного вычислительного ресурса и латентностью базовых операций.

\vspace{1em}
{\it Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта \textnumero 20-07-00545.}

\begin{thebibliography} {8}
\bibitem{LevinDPMM21} 
Levin~I.I., Dordopulo~A.I., Pisarenko~I., Mikhailov~D., Melnikov~A.: Resource-Independent Description of Information Graphs with Associative Operations in Set@l Programming Language // Parallel Computing Technologies, 16th International Conference, PaCT 2021, Kaliningrad, Russia, September 13–18, 2021. Proceedings.  Vol. 12942 / ed. by V. Malyshkin. Springer, 2021. Lecture Notes in Computer Science. P. 74--87. DOI: 10.1007/978-3-030-86359-3\_6.
\bibitem{TanJ13} 
Tan~L., Jiang~J.: Digital Signal Processing: Fundamentals and Applications. 2nd ed. Oxford: Elsevier Science, 2013. 896 p.
\bibitem{WinserC17} 
Winser~A., Cranos~M.W.: Digital Signal Processing: Principles, Algorithms and System Design. London: Elsevier, 2017. 634 p.
\bibitem{LevinDPM19} 
Levin~I.I., Dordopulo~A.I., Pisarenko~I.V., Melnikov~A.K.: Aspect-Oriented Set@l Language for Architecture-Independent Programming of High-Performance Computer Systems // Supercomputing. RuSCDays 2019. Vol. 1129 / ed. by L. Sokolinsky, M. Zymbler. Cham: Springer,2019. P. 517--528. Communications in Computer and Information Science. DOI:10.1007/978-3-030-36592-9\_42.
\bibitem{LevinDPM19-2} 
Levin~I.I., Dordopulo~A.I., Pisarenko~I.V., Melnikov~A.K.: Objects of Alternative Set Theory in Set@l Programming Language // Parallel Computing Technologies, 15th International Conference, PaCT 2019, Almaty, Kazakhstan, August 19–23, 2019. Proceedings. Vol. 11657 / ed. by V. Malyshkin. Springer, 2019. P. 18--31. Lecture Notes in Computer Science. DOI:10.1007/978-3-030-25636-4\_3.
\bibitem{LevinDPM19-3} 
Левин~И.И., Дордопуло~А.И., Писаренко~И.В., Мельников~А.К. Язык архитектурно-независимого программирования вычислительных систем Set@l // Вестник компьютерных и информационных технологий. 2019. № 3. С. 48--56. DOI:10.14489/vkit.2019.03.pp.048-056.
\bibitem{Karepova16} 
Карепова~Е.Д. Основы многопоточного и параллельного программирования. Красноярск: Сиб. федер. ун-т, 2016. 356 с.
\bibitem{LevinD21} 
Levin~I.I., Dudko~S.A.: Equivalent Transformations of Some Kinds of Computing Structures of Non-linear Recurrent Expressions for Reconfigurable Computing Systems // Parallel Computational Technologies. Vol. 1437 / ed. by L. Sokolinsky, M. Zymbler. Cham: Springer, 2021. P. 3--17. Communications in Computer and Information Science. DOI:10.1007/978-3-030-81691-9\_1.
\end{thebibliography}

% Сведения об авторах (Ф.И.О.(полностью), степень, звание, кафедра (отдел), вуз, e-mail)
Левин Илья Израилевич, д.т.н., профессор, кафедра интеллектуальных и многопроцессорных систем, Южный федеральный университет (Таганрог, Российская Федерация)

Писаренко Иван Вадимивич, <<НИЦ супер-ЭВМ и нейрокомпьютеров>> (Таганрог, Российская Федерация)

Михайлов Денис Васильевич, <<НИЦ супер-ЭВМ и нейрокомпьютеров>> (Таганрог, Российская Федерация)

Мельников Андрей Кимович, к.т.н., доцент, АО <<Вычислительные решения>> (Москва, Российская Федерация)

Дордопуло Алексей Игоревич, к.т.н., <<НИЦ супер-ЭВМ и нейрокомпьютеров>> (Таганрог, Российская Федерация)

%\newpage

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

\title{RESOURCE-INDEPENDENT DESCRIPTION OF INFORMATION GRAPHS~WITH DISTRIBUTIVE OPERATIONS IN THE SET@L PROGRAMMING LANGUAGE}

\authorsen{I.I.~Levin$^{1}$, I.V.~Pisarenko$^{2}$, D.V.~Mikhailov$^{2}$, A.K.~Melnikov$^{3}$, A.I.~Dordopulo$^{2}$}

\organizations{$^{1}$Southern Federal University (Nekrasovsky lane 44, Taganrog, 347928 Russia),\\
$^{2}$Supercomputers and Neurocomputers Research Center (Italyansky lane 106, Taganrog, 347922 Russia),\\
$^{3}$``Computational Solutions'' JSC (Varshavskoe highway 125с17, Moscow, 119991 Russia)}

\emails{\emailsinsert}
\redactiondateen{\rdate}

\begin{abstract}%
In the paper we suggest to transform a standard sequential topology of an information graph with distributive operations into its hybrid version with sequential and parallel fragments. Such transformation allows efficient description of calculations in the resource-independent form. The result topology depends on available hardware resource of a reconfigurable system and provides increasing of the special performance in comparison to the initial topology. We developed an algorithm of a linear structure transformation into various hybrid topologies according to the configuration of the computer system. The algorithm is described in the Set@l programming language.

\keywordsen{distributive operations, resource-independent programming, reconfigurable computer systems, performance reduction, Set@l, <<half-splitting>> and <<head/tail>> attributes.}
\end{abstract}

\forcitationen{Levin~I.I.,  Pisarenko~I.V., Mikhailov~D.V., Melnikov~A.K., Dordopulo~A.I. Resource-independent description of information graphs with distributive operations in the Set@l programming language}

\openaccess

\insertbiblioen


\begin{thebibliography}{8}

\bibitem{LevinDPMM21} 
Levin~I.I., Dordopulo~A.I., Pisarenko~I., Mikhailov~D., Melnikov~A.: Resource-Independent Description of Information Graphs with Associative Operations in Set@l Programming Language // Parallel Computing Technologies, 16th International Conference, PaCT 2021, Kaliningrad, Russia, September 13–18, 2021. Proceedings.  Vol. 12942 / ed. by V. Malyshkin. Springer, 2021. Lecture Notes in Computer Science. P. 74--87. DOI:10.1007/978-3-030-86359-3\_6.
\bibitem{TanJ13} 
Tan~L., Jiang~J.: Digital Signal Processing: Fundamentals and Applications. 2nd ed. Oxford: Elsevier Science, 2013. 896 p.
\bibitem{WinserC17} 
Winser~A., Cranos~M.W.: Digital Signal Processing: Principles, Algorithms and System Design. London: Elsevier, 2017. 634 p.
\bibitem{LevinDPM19} 
Levin~I.I., Dordopulo~A.I., Pisarenko~I.V., Melnikov~A.K.: Aspect-Oriented Set@l Language for Architecture-Independent Programming of High-Performance Computer Systems // Supercomputing. RuSCDays 2019. Vol. 1129 / ed. by L. Sokolinsky, M. Zymbler. Cham: Springer,2019. P. 517--528. Communications in Computer and Information Science. DOI:10.1007/978-3-030-36592-9\_42.
\bibitem{LevinDPM19-2} 
Levin~I.I., Dordopulo~A.I., Pisarenko~I.V., Melnikov~A.K.: Objects of Alternative Set Theory in Set@l Programming Language // Parallel Computing Technologies, 15th International Conference, PaCT 2019, Almaty, Kazakhstan, August 19–23, 2019. Proceedings. Vol. 11657 / ed. by V. Malyshkin. Springer, 2019. P. 18--31. Lecture Notes in Computer Science. DOI:10.1007/978-3-030-25636-4\_3.
\bibitem{LevinDPM19-3} 
Levin~I.I., Dordopulo~A.I., Pisarenko~I.V., Melnikov~A.K. Architecture-independent Set@l programming language for computer systems // Vestnik komp'iuternykh i informatsionnykh tekhnologii. 2019. No. 3. P. 48--56. DOI:10.14489/vkit.2019.03.pp.048-056. (in Russian).
\bibitem{Karepova16} 
Karepova~E.D. Fundamentals of Multithreaded and Parallel Programming. Krasnoyarsk: Publishing of the Siberian Federal University, 2016. 356 p. (in Russian).
\bibitem{LevinD21} 
Levin~I.I., Dudko~S.A.: Equivalent Transformations of Some Kinds of Computing Structures of Non-linear Recurrent Expressions for Reconfigurable Computing Systems // Parallel Computational Technologies. Vol. 1437 / ed. by L. Sokolinsky, M. Zymbler. Cham: Springer, 2021. P. 3--17. Communications in Computer and Information Science. DOI:10.1007/978-3-030-81691-9\_1.
	
\end{thebibliography}

\end{document}
