last font embedded pb corrected

[book_gpu.git] / BookGPU / Chapters / chapter6 / PartieORWL.tex

\clearpage
\section{Perspective: A unifying programming model}
\label{sec:ch6p3unify}

In the previous sections we have seen that controlling a distributed GPU
application when using tools that are commonly available is a quite challenging
task. To summarize, such an application has components that can be roughly
classified as:

\begin{description}
  \itemsep=0pt
\item[CPU:] CPU bound computations, realized as procedures in the chosen
  programming language
\item[CUDA$_{kern}$:] GPU bound computations, in our context realized as CUDA compute kernels
\item[CUDA$_{trans}$:] data transfer between CPU and GPU, realized with CUDA function calls
\item[MPI:] distributed data transfer routines, realized with MPI communication primitives
\item[OpenMP:] inter-thread control, realized with OpenMP synchronization tools such as mutexes
\item[CUDA$_{sync}$] synchronization of the GPU, realized with CUDA functions
\end{description}

Among these, the last (CUDA$_{sync}$) is not strictly necessary on modern
systems, but still recommended to obtain optimal performance. With or without
that last step, such an application is highly complex: it is difficult to design
or to maintain, and depends on a lot of different software components. The goal
of this section is to present a new path of development that allows to replace
the last three or four types of components that control the application (MPI,
OpenMP, CUDA$_{sync}$ and eventually CUDA$_{trans}$) by a single tool:
\textbf{O}rdered \textbf{R}ead-\textbf{W}rite \textbf{L}ocks, ORWL\index{ORWL},
see~\cite{clauss:2010:inria-00330024:1,gustedt:hal-00639289}. Besides the
simplification of the algorithmic scheme that we already have mentioned, the
ongoing implementation of ORWL allows to use a feature of modern platforms that
can improve the performance of CPU bound computations: lock-free atomic
operations to update shared data consistently. For these, ORWL relies on new
interfaces that are available with the latest revision of the ISO standard for
the C programming language, see~\cite{C11}.

\subsection{Resources}
\label{sec:ch6p3resources}

ORWL places all its concepts that concern data and control around a single
abstraction: \emph{resources}\index{ORWL!resource}. An ORWL resource may correspond to a local or
remote entity and is identified through a \emph{location}\index{ORWL!location}, that is a unique
identification through which it can be accessed from all different components of
the same application. In fact, resources and locations (entities and their names
so to speak) are mostly identified by ORWL and these words will be used
interchangeably.

Resources may be of very different kind:
\begin{description}
\item[Data] resources\index{ORWL!resource!data} are entities that represents data and not specific
  memory buffers or locations. During the execution of an application it can be
  \emph{mapped} repeatedly into the address space and in effect be represented
  at different addresses. Data resources can be made accessible uniformly in all
  parts of the application, provided that the locking protocol is observed, see
  below. Data resources can have different persistence:
  \begin{description}
  \item[RAM] data resources are typically temporary data that serve only during
    a single run of the application. They must be initialized at the beginning of
    their lifetime and the contents is lost at the end.
  \item[File] data resources are persistent and linked to a file in the file
    system of the platform.
  \item[Collective] data resources are data to which all tasks of an
    application contribute (see below). Examples for such resources are \emph{broadcast},
    \emph{gather} or
    \emph{reduce} resources, e.g to distribute initial data or to collect the
    result of a distributed computation.
  \end{description}
  Other types of data resources could be easily implemented with ORWL, e.g web
  resources (through a ftp, http or whatever server address) or fixed hardware
  addresses.
\item[Device] resources\index{ORWL!resource!device} represent hardware entities of the
  platform. ORWL can then be used to regulate the access to such device
  resources. In our context the most important such resource is the GPU, but we
  could easily use it to represent a CPU core, a camera or other peripheral
  device.
\end{description}

\Lst{algo:ch6p3ORWLresources} shows an example of a declaration of
four resources per task. Two (\texttt{curBlock} and \texttt{nextBlock}) are
intended to represent the data in a block-cyclic parallel matrix multiplication
(see p.~\pageref{ch6:p1block-cyclic}),
\texttt{GPU} represents a GPU device and \texttt{result} will represent a
collective ``gather'' resource among all the tasks.

%\begin{algorithm}[H]
%  \caption{Declaration of ORWL resources for a block-cyclic matrix
%    multiplication.}
%  \label{algo:ch6p3ORWLresources}
\begin{Listing}{algo:ch6p3ORWLresources}{Declaration of ORWL resources for a block-cyclic matrix multiplication}
#include "orwl.h"
...
ORWL_LOCATIONS_PER_TASK(curBlock, nextBlock, GPU, result);
ORWL_DATA_LOCATION(curBlock);
ORWL_DATA_LOCATION(nexBlock);
ORWL_DEVICE_LOCATION(GPU);
ORWL_GATHER_LOCATION(result);
\end{Listing}
%\end{algorithm}


\subsection{Control}
\label{sec:ch6p3ORWLcontrol}


ORWL regulates access to all its resources, no ``random access'' to a resource
is possible. It doesn't even have a user-visible data type for resources.
\begin{itemize}
\item All access is provided through \emph{handle}s\index{ORWL!handle}. Similar to pointers or
  links, these only refer to a resource and help to manipulate it. Usually
  several handles to the same resource exist, even inside the same OS process
  or thread, or in the same application task.
\item The access is locked with RW semantics, where \emph{R} stands for
  concurrent \textbf{R}ead~access, and \emph{W} for exclusive
  \textbf{W}rite~access. This feature replaces the control aspect of MPI
  communications, OpenMP inter-thread control and CUDA$_{sync}$.
\item This access is \textbf{O}rdered (or serialized)\index{ordered access} through a FIFO, \emph{one
    FIFO per resource}. This helps to run the different tasks of an application
  in a controlled order and to always have all resources in a known state. This
  aspect largely replaces and extends the ordering of tasks that MPI typically
  achieves through the passing of messages.
\item The access is transparently managed for remote or local resources.
  Communication, if necessary, is done asynchronously behind the scenes. This
  replaces the explicit handling of buffers and messages with MPI.
\end{itemize}

\subsection{Example: block-cyclic matrix multiplication (MM)}
\label{sec:ch6p3ORWLMM}

Let us now have a look how a block-cyclic matrix multiplication\index{matrix
  multiplication!block cyclic} algorithm can be
implemented with these concepts (\Lst{algo:ch6p3ORWLBCCMM}). Inside the loop it mainly consists of three
different operations, of which the first two can be run concurrently, and the
third must be done after the other two.
%\begin{algorithm}[H]
%  \caption{Block-cyclic matrix multiplication, high level per task view.}
%  \label{algo:ch6p3ORWLBCCMM}
\begin{Listing}{algo:ch6p3ORWLBCCMM}{Block-cyclic matrix multiplication, high level per task view}
typedef double MBlock[N][N];
MBlock A;
MBlock B[k];
MBlock C[k];

<do some initialization>

for (size_t i = 0; i < k; ++i) {
  MBlock next;
  parallel-do {
    operation 1: <copy the matrix A of the left neighbor into next>;
    operation 2: {
      <copy the local matrix A to the GPU >;
      <on GPU perform C[i] = A * B[0] + ... + A * B[k-1]; >;
    }
  }
  operation 3: {
    <wait until the right neighbor has read our block A>;
    A = next;
  }
}

<collect the result matrix C consisting of all C blocks>
\end{Listing}
%\end{algorithm}


\Lst{algo:ch6p3ORWLlcopy} shows the local copy operation~3 as it could
be realized with ORWL.
It uses two resource handles
\texttt{nextRead} and \texttt{curWrite} and marks nested \emph{critical
  sections} for these handles. Inside the nested sections it obtains pointers to
the resource data; the resource is \emph{mapped} into the address space of the
program, and then a standard call to \texttt{memcpy} achieves the operation
itself. The operation is integrated in its own \textbf{for}-loop, such that it
could run independently in an OS thread by its own.
%\begin{algorithm}[H]
%  \caption{An iterative local copy operation.}
%  \label{algo:ch6p3ORWLlcopy}
\begin{Listing}{algo:ch6p3ORWLlcopy}{An iterative local copy operation}
for (size_t i = 0; i < k; ++i) {
  ORWL_SECTION(nextRead) {
    MBlock const* sBlock = orwl_read_map(nextRead);
    ORWL_SECTION(curWrite) {
      MBlock * tBlock = orwl_write_map(curWrite);
      memcpy(tBlock, sBlock, sizeof *tBlock);
    }
  }
}
\end{Listing}
%\end{algorithm}

Next, in \Lst{algo:ch6p3ORWLrcopy} we copy data from a remote task to
a local task. Substantially the operation is the same, only that in the example
different handles (\texttt{remRead} and \texttt{nextWrite}) are used to
represent the respective resources.
%\begin{algorithm}[H]
%  \caption{An iterative remote copy operation as part of a block cyclic matrix
%    multiplication task.}
%\label{algo:ch6p3ORWLrcopy}
\begin{Listing}{algo:ch6p3ORWLrcopy}{An iterative remote copy operation as part of a block cyclic matrix multiplication task}
for (size_t i = 0; i < k; ++i) {
  ORWL_SECTION(remRead) {
    MBlock const* sBlock = orwl_read_map(remRead);
    ORWL_SECTION(nextWrite) {
      MBlock * tBlock = orwl_write_map(nextWrite);
      memcpy(tBlock, sBlock, sizeof *tBlock);
    }
  }
}
\end{Listing}
%\end{algorithm}

Now let us have a look into the operation that probably interests us the most,
the interaction with the GPU in \Lst{algo:ch6p3ORWLtrans}. Again there
is much structural resemblance to the copy operations from above, only that  we
transfer the data to the GPU in the innermost block and then run the GPU MM
kernel while we still are inside the critical section for the GPU.
%\begin{algorithm}[H]
%  \caption{An iterative GPU transfer and compute operation as part of a block cyclic matrix
%    multiplication task.}
%  \label{algo:ch6p3ORWLtrans}
\begin{Listing}{algo:ch6p3ORWLtrans}{An iterative GPU transfer and compute operation as part of a block cyclic matrix multiplication task}
for (size_t i = 0; i < k; ++i) {
  ORWL_SECTION(GPUhandle) {
    ORWL_SECTION(curRead) {
      MBlock const* sBlock = orwl_read_map(curRead);
      transferToGPU(sBlock, i);
    }
    runMMonGPU(i);
  }
}
\end{Listing}
%\end{algorithm}

Now that we have seen how the actual procedural access to the resources is
regulated we will show how the association between handles and resources is
specified. E.g in our application of block-cyclic MM the \texttt{curRead} handle
should correspond to current matrix block of the corresponding task, whereas
\texttt{remRead} should point to the current block of the neighboring task.
Both read operations on these matrix blocks can be effected without creating
conflicts, so we would like to express that fact in our resource specification.
From a point of view of the resource ``current block'' of a particular task,
this means that it can have two simultaneous readers, the task itself performing
the transfer to the GPU, and the neighboring task transferring the data to its
``next block''.

\Lst{algo:ch6p3ORWLdecl} first shows the local dynamic declarations of
our application; it declares a \texttt{block} type for the matrix blocks, a
\texttt{result} data for the collective resource, and the six handles that we
have seen so far.
%\begin{algorithm}[H]
%  \caption{Dynamic declaration of handles to represent the resources.}
%  \label{algo:ch6p3ORWLdecl}
\begin{Listing}{algo:ch6p3ORWLdecl}{Dynamic declaration of handles to represent the resources}
/* A type for the matrix blocks */
typedef double MBlock[N][N];
/* Declaration to handle the collective resource */
ORWL_GATHER_DECLARE(MBlock, result);

/* Variables to handle data resources */
orwl_handle2 remRead   = ORWL_HANDLE2_INITIALIZER;
orwl_handle2 nextWrite = ORWL_HANDLE2_INITIALIZER;
orwl_handle2 nextRead  = ORWL_HANDLE2_INITIALIZER;
orwl_handle2 curWrite  = ORWL_HANDLE2_INITIALIZER;
orwl_handle2 curRead   = ORWL_HANDLE2_INITIALIZER;

/* Variable to handle the device resources */
orwl_handle2 GPUhandle = ORWL_HANDLE2_INITIALIZER;
\end{Listing}
%\end{algorithm}

With these declarations, we didn't yet tell ORWL much about the resources to
which these handles refer, nor the type (read or write) or the priority (FIFO
position) of the access. This is done in code
\Lst{algo:ch6p3ORWLinit}. The handles for
\Lst{algo:ch6p3ORWLtrans} are given first, \texttt{GPUhandle} will be
accessed exclusively (therefore the \texttt{write}) and, as said,
\texttt{curRead} is used shared (so a \texttt{read}). Both are inserted in the
FIFO of there respective resources with highest priority, specified by the
\texttt{0}s in the third function parameter. The resources to which they
correspond are specified through calls to the macro \texttt{ORWL\_LOCATION},
indicating the task (\texttt{orwl\_mytid} is the ID of the current task) and the
specific resource of that task, here \texttt{GPU} and \texttt{curBlock}.

Likewise, a second block of insertions concerns the handles for
\Lst{algo:ch6p3ORWLrcopy}: \texttt{newWrite} reclaims an exclusive
access and \texttt{remRead} a shared. \texttt{remRead} corresponds to a
resource of another task; \texttt{previous(orwl\_mytid)} is supposed to return
the ID of the previous task in the cycle. Both accesses can be effected
concurrently with the previous operation, so we insert with the same priority
\texttt{0} as before.

Then, for the specification of the third operation
(\Lst{algo:ch6p3ORWLlcopy}) we need to use a different priority: the
copy operation from \texttt{nextBlock} to \texttt{curBlock} has to be performed
after the other operations have terminated.

As a final step, we then tell ORWL that the specification of all accesses is
complete and that it may schedule\index{ORWL!schedule} all these accesses in the respective FIFOs of
the resources.
%\begin{algorithm}[H]
%  \caption{Dynamic initialization of access mode and priorities.}
%  \label{algo:ch6p3ORWLinit}
\begin{Listing}{algo:ch6p3ORWLinit}{Dynamic initialization of access mode and priorities}
/* One operation with priority 0 (highest) consists      */
/* in copying from current to the GPU and run MM, there. */
orwl_write_insert(&GPUhandle, ORWL_LOCATION(orwl_mytid, GPU), 0);
orwl_read_insert(&curRead, ORWL_LOCATION(orwl_mytid, curBlock), 0);

/* Another operation with priority 0 consists             */
/* in copying from remote to next                         */
orwl_read_insert(&remRead, ORWL_LOCATION(previous(orwl_mytid), curBlock), 0);
orwl_write_insert(&nextWrite, ORWL_LOCATION(orwl_mytid, nextBlock), 0);

/* One operation with priority 1 consists       */
/* in copying from next to current              */
orwl_read_insert(&nextRead, ORWL_LOCATION(orwl_mytid, nextBlock), 1);
orwl_write_insert(&curWrite, ORWL_LOCATION(orwl_mytid, curBlock), 1);

orwl_schedule();
\end{Listing}
%\end{algorithm}

\subsection{Tasks and operations}
\label{sec:ch6p3tasks}
With that example we have now seen that ORWL distinguishes
\emph{tasks}\index{ORWL!task} and
\emph{operations}\index{ORWL!operation}. An ORWL program is divided into tasks that can be seen as the
algorithmic units that will concurrently access the resources that the program
uses. A task for ORWL is characterized by
\begin{itemize}
\item a fixed set of resources that it manages, ``\emph{owns}'', in our example
  the four resources that are declared in \Lst{algo:ch6p3ORWLresources}.
\item a larger set of resources that it accesses, in our example all resources
  that are used in \Lst{algo:ch6p3ORWLinit}.
\item a set of operations that act on these resources, in our example the three
  operations that are used in \Lst{algo:ch6p3ORWLBCCMM}, and that are
  elaborated in Listings~\ref{algo:ch6p3ORWLlcopy},~\ref{algo:ch6p3ORWLrcopy}
  and~\ref{algo:ch6p3ORWLtrans}.
\end{itemize}

\noindent
Each ORWL operation is characterized by
\begin{itemize}
\item one resource, usually one that is owned by the enclosing task, that it
  accesses exclusively. In our example, operation~1 has exclusive access to the
  \texttt{next} block, operation~2 has exclusive access the \texttt{GPU}
  resource, and operation~3 to the \texttt{A} block.
\item several resources that are accessed concurrently with others.
\end{itemize}
In fact each ORWL~operation can be viewed as a compute-and-update procedure of a
particular resource with knowledge of another set of resources.


%%% Local Variables:
%%% mode: latex
%%% fill-column: 80
%%% ispell-dictionary: "american"
%%% mode: flyspell
%%% TeX-master: "../../BookGPU.tex"
%%% End: