% LaTeX document
\documentclass[a4paper,12pt]{article}
\usepackage[koi8-r]{inputenc}
\usepackage[russian]{babel}
\begin{document}
\begin{titlepage}
\begin{center}

\Huge{\textbf{
Руководство пользователя \\
библиотеки коммуникационных процедур \\
INM~ParLib (версии 1.0)}}

\vspace{0.1\textheight}
\Large{Глухов~В.~Н.} \\

\vspace{0.2\textheight}
\Large{Институт вычислительной математики~РАН \\
Москва, \today}

\end{center}
\end{titlepage}

\section{Введение}
Данное руководство содержит в себе описание библиотеки коммуникационных процедур INM ParLib, сформировавшейся в результате работ по распараллеливанию моделей погоды~\cite{T126} и климата~\cite{AGCM} на многопроцессорных вычислительных системах с распределенной памятью.

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

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

Транспонирование применяется тогда, когда существует зависимость от всех точек по одной из распределенных размерностей в то время, как вычисления по другой не распределенной размерности независимы.
В этом случае можно перераспределить данные таким образом, что первая размерность будет содержаться целиком в процессорах, а вторая станет распределенной.
После завершения вычислений можно вернуться к исходному распределению, сделав обратное транспонирование данных.
В некоторых работах~\cite{Ilghiz}, \cite{Swarztrauber} была показана эффективность такого подхода для реализации быстрого преобразования Фурье, а также возможность его применения для вычисления преобразования Лежандра~\cite{Barros}.

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

\section{Использование библиотеки}
Библиотечные процедуры доступны из программ, написанных как на Си, так и на Фортране.

\subsection{Компиляция и линковка программ}
Поскольку библиотечные процедуры обращаются к функциям MPI программа должна компилироваться и линковаться точно также как и любая другая программа, использующая библиотеку MPI.
Кроме того, при компиляции необходимо указать опцию {\tt -I{\it путь\_к\_библи\-оте\-ке}/include}, при линковке~-- {\tt -L{\it путь\_к\_библиотеке}/lib -lparlib}, a при линковки программ  на Фортране еще и опцию {\tt -lparlibf}.

\subsection{Вызов библиотечных процедур}
Вызов библиотечных процедур рекомендуется предварять опратором 
\begin{verbatim}
      INCLUDE 'parlibf.h'
\end{verbatim}
в Фортране, либо директовой 
\begin{verbatim}
#include 'parlib.h'
\end{verbatim}
в Си.

\subsubsection{Обмен граничными значениями}

Пусть массив $\cal A$ распределен между процессорами по одной или нескольким размерностям.
Тогда каждый процессор будет содержать некоторую локальную часть этого массива (подобласть).
Предположим, что подобласти не пересекаются между собой.
Тогда массив может быть описана в программ как
\begin{verbatim}
      DIMENSION A(STRIDE(1), ..., STRIDE(NDIMS))
\end{verbatim}
где {\tt NDIMS}~-- количество размерностей массива, {\tt STRIDE}~-- сами размерности.
Предположим также, что {\tt BDIM}~-- одна из размерностей, по которой массив $\cal A$ распределен и необходимо вдоль нее организовать обмен граничными значениями, при чем в общем случае не для всего массива, а лишь для некоторой его части.

Такой обмен может быть осуществлен путем вызова процедуры \\{\tt P\_BExchange} следующего вида:
\begin{verbatim}
      CALL  P_BEXCAHNGE (ARR, NDIMS, STRIDE, BLKLEN, BDIM, 
     1 OVERLAP, DATATYPE, COMM, PERIOD, IERROR)
\end{verbatim}
где {\tt ARR}~-- первый элемент локальной части массива {\tt A}; параметры {\tt BLKLEN}~-- определяют размеры той части массива {\tt A}, которая участвует в коммуникации, а именно, в коммуникацию будет вовлечена следующая его часть {\tt ARR(1:BLKLEN(1), ..., 1:BLKLEN(NDIMS))}.
Ширина коммутируемых границ определяется параметрами {\tt OVERLAP}, при чем предыдущему в группе процессору посылается блок ширины {\tt OVERLAP(1)} по размерности {\tt BDIM}, в то время как следующему~-- блок ширины {\tt OVERLAP(2)}. 
Логическая переменная {\tt PERIOD} определяет является ли обмен периодическим или нет. 
Если обмен периодический, то первый и последний процессоры в группе так же обмениваются между собой граничными значениями.
Группа процессор идентефицируется идентификатором MPI {\tt COMM}, а тип элементов массива {\tt A} определяется идентификатором MPI {\tt DATATYPE}.
Обычно, последний имеет значения {\tt MPI\_REAL} или {\tt MPI\_DOUBLE\_PRECISION}.
% здесь надо написать, что для хранения граничных значений обязательно должно быть предусмотрено специоальная память

Существует так же асинхронный вариант применения операции обмена граничными значениями. 
Он реализован в библиотеке в виде четырех процедур:
\begin{verbatim}
      CALL P_BEXCAHNGE_INIT (NDIMS, STRIDE, BLKLEN, BDIM, 
     1 OVERLAP, DATATYPE, COMM, PERIO, BEXCHANGE, IERROR)
      CALL P_BEXCAHNGE_START (ARR, BEXCHANGE, IERROR)
      CALL P_BEXCAHNGE_END (BEXCHANGE, IERROR)
      CALL P_BEXCAHNGE_FREE (BEXCHANGE, IERROR)
\end{verbatim}
Первая процедура создает и инициализирует некоторую структуру, содержащую в себе всю информацию, необходимую для начала обмена, и возвращает дескриптор {\tt BEXCHANGE}, идентифицирующий эту структуру, вторая начинает обмен, третья ожидает окончания обмена, и, наконец, последняя удаляет созданную структуру из памяти. 
Таким образом, между процедурами {\tt P\_BExcahnge\_start} и {\tt P\_BExchange\_end} могут производиться полезные вычисления в фоновом режиме, одновременно с пересылкой данных.

\subsubsection{Транспонирование}
Допустим, массив $\cal A$ распределен между процессорами некоторой группы вдоль размерности {\tt DIM\_SOURCE} блоками ширины {\tt LBLKS\_SOURCE(IPROC)}, где {\tt IPROC}~-- номер процессора, а размерность {\tt DIM\_DEST} содержится в процессорах целиком.
Будем называть транспонированием массива $\cal A$ такое его перераспреденеие, в результате которого каждый порцессор будет обладать блоком ширины {\tt LBLKS\_DEST(IPROC)} вдоль размерности {\tt DIM\_DEST} и всеми точкамии вдоль размерности {\tt DIM\_SOURCE}.
Если {\tt ARR\_SOURCE}~-- первый элемент локальной подобласти массива $\cal A$ до транспониравания, а {\tt ARR\_DEST}~-- после транспонирования, вызов соответствующей библиотечной процедуры будет иметь следующий вид:
\begin{verbatim}
      CALL P_TRANSPOSE (NDIMS, ARR_SOURCE, DIM_SOURCE, 
     1 LBLKS_SOURCE, ARR_DEST, DIM_DEST, LBLKS_DEST, 
     2 STRIDE, BLKLEN, OVERLAP, DATATYPE, COMM, PERIOD, 
     3 DIAG, IERROR)
\end{verbatim}
где {\tt NDIMS}~-- количество размерностей массива $\cal A$, {\tt DATATYPE}~-- дескриптор MPI, соответствующий типу элементов массива, {\tt COMM}~-- коммуникатор MPI, определяющий группу процессорв.
Заметим, что если массив $\cal A$ хранится в памяти каждого процессора целиком, нет необходимости процессорам пересылать его диагональный блок самим себе. 
Для того, чтобы пересылки диагонального блока не происходило, переменная {\tt DIAG} должна иметь значение {\tt .FALSE.} на входе процедуры.

Пусть локальная подобласть массива $\cal A$ представлен на входе процедуры массивом {\tt A\_SOURCE}, а на выходе~-- массивом {\tt A\_DEST}.
Они могут быть описаны в программе как
\begin{verbatim}
      DIMENSION A_SOURCE(DIM_SOURCE(1), ..., DIM_SOURCE(NDIMS))
      DIMENSION A_DEST(DIM_DEST(1), ..., DIM_DEST(NDIMS))
\end{verbatim}
где размерность {\tt DIM\_SOURCE}  имеет следующие значения:
$$
   \texttt{DIM\_SOURSE(IDIM)}=\left\{
   \begin{array}{l}
      \texttt{BLKLEN(DIM\_SOURCE)} \textrm{, если } \texttt{IDIM=DIM\_SOURCE}\\
      \texttt{STRIDE(IDIM)} \textrm{, в противном случае}
   \end{array}\right.
$$
а размерность {\tt DIM\_DEST}:
$$
   \texttt{DIM\_DEST(IDIM)}=\left\{
   \begin{array}{l}
      \texttt{BLKLEN(DIM\_DEST)} \textrm{, если } \texttt{IDIM=DIM\_DEST}\\
      \texttt{STRIDE(IDIM)} \textrm{, в противном случае}
   \end{array}\right.
$$

В общем счучае массивы {\tt A\_SOURCE} и {\tt A\_DEST} могут быть задействованы в транспонировании не целиком, а лишь частично:
\begin{verbatim}
      ARR_SOURCE(1:BLK_SOURCE(1), ..., 1:BLK_SOURCE(NDIMS)
      ARR_DEST(1:BLK_DEST(1), ..., 1:BLK_DEST(NDIMS)
\end{verbatim}
где блоки имеют следующие размеры:
$$
   \texttt{BLK\_SOURCE(IDIM)}=\left\{
   \begin{array}{l}
      \texttt{LBLKS\_SOURCE(IPROC)} \textrm{, если } \texttt{IDIM=DIM\_SOURCE} \\
      \sum\texttt{LBLKS\_DEST} \textrm{, если } \texttt{IDIM=DIM\_DEST} \\
      \texttt{BLKLEN(IDIM)} \textrm{, в противном случае}
   \end{array}\right.
$$
$$
   \texttt{BLK\_DEST(IDIM)}=\left\{
   \begin{array}{l}
      \texttt{LBLKS\_DEST(IPROC)} \textrm{, если } \texttt{IDIM=DIM\_DEST} \\
      \sum\texttt{LBLKS\_SOURE} \textrm{, если } \texttt{IDIM=DIM\_SOURCE} \\
      \texttt{BLKLEN(IDIM)} \textrm{, в противном случае}
   \end{array}\right.
$$

Асинхронный вариант транспонирования реализован в виде четырех процедур:
\begin{verbatim}
      CALL P_TRANSPOSE_INIT (NDIMS, DIM_SOURCE, LBLKS_SOURCE, 
     1 DIM_DEST, LBLKS_DEST, STRIDE, BLKLEN, OVERLAP, DATATYPE, 
     2 COMM, PERIOD, DIAG, TRANSP, IERROR)
      CALL P_TRANSPOSE_START (ARR_SOURCE, ARR_DEST, TRANSP, 
     1 IERROR)
      CALL P_TRANSPOSE_END (TRANSP, IERROR)
      CALL P_TRANSPOSE_FREE (TRANSP, IERROR)
\end{verbatim}
где {\tt TRANSP}~-- дескриптор транспонирования.

\begin{thebibliography}{}
\bibitem{T126} Глухов~В.~Н. Распараллеливание глобальной спектральной модели среднесрочного прогноза погоды T126 на многопроцессорной вычислительной системе с распределенной памятью. Optimization of Finite Element Approximations, Splines and Wavelets (OFEA'2001). Abstracts of International conference (June~25--29, 2001, St.-Petersburg, Russia), 2001, 184~p.

\bibitem{AGCM} М.~A.~Tolstykh, V.~N.~Gloukhov. Implementation of global atmospheric models on parallel computers. {\it Вычислительные технологии.} Институт вычислительных технологий СО~РАН, Новосибирск.

\bibitem{Ilghiz} Ибрагимов~И.~В. Параллельные алгоритмы БПФ и скалярного произведения векторов. Матричные методы и алгоритмы. ИВМ РАН, Москва, 1999.

\bibitem{Swarztrauber} P.~N.~Swarztrauber, S.~W.~Hammond. A comparison of optimal FFTs on torus and hypercube multicomputers. {\it Parallel computing},~27 (2001), pp.~847--859.

\bibitem{Barros} Barros,~S.~R.~M., Kauranne,~T. On the parallelization of global spectral weather models. {\it Parallel Computing},~20 (1994), pp.~1335--1356.

\bibitem{Rodriguez} B.~Rodriguez, L.~Hart, T.~Henderson. Performance and portability in parallel computing: a weather forecasr view. {\it High Performance Computing in the Geosciences}, 1995, Kluwer Academic Publishers, Netherlands, pp.~1--23.

\bibitem{Henderson} T.~Henderson, D.~Shaffer, M.~Govett, L.~Hart. SMS User's Guide. Advanced Computing Branch, Aviation Division, NOAA Forecast system laboratory, Boulder, 2001.

\end{thebibliography}

\end{document}
