<commit_before>\chapter{OpenCAL OpenMP version}

With the name OpenCAL-OMP, we identify the OpenMP implementation of
the software library, which can run on all the cores for your CPU. If
you are luky and have a shared memory multiptocessor system,
OpenCAL-OMP can also exploit all the cores of all your CPUs.

Similarly to the serial version, OpenCAL-OMP allows for some
\emph{unsafe operations}, which can significantly speed up your
application. Howevewr, it must be given the utmost attention due to
possible problems related to race condions. In particular, when many
theads perform concurrent operations on the same memory locations, if
such operation are made by more than one basic machine instructions,
it can appen they can interleave, giving rice to wrong
results. Furthermore, even in the case of atomic operations, race
conditions can occur if the logic order of execution is not
respected. For instance, in a sequence of write-read atomic
operations, it can occur that the read is performed before the write
due to the fact that the thread performing the write is executed
first.

In the following sections, we will introduce OpenCAL-OMP by comparing
examples source code differences with respect to the serial
implemebntations. In the first part of the Chapter, we will deal with
the OpenCAL's safe mode, while in the last one, we will discuss unsafe
operations.

\section{Conway's Game of Life in OpenCAL-OMP}

In Section \ref{sec:cal_life}, we described Conway's Game of Life and
shown a possible implementation using the \verb'OpenCAL' serial
library. Here, we present a \verb'OpenCAL-OMP' implementation of the
same cellular automaton in listing \ref{lst:calomp_life}, by
discussing the differences with respect the serial implementation.

\lstinputlisting[float,floatplacement=H, label=lst:calomp_life, caption=An OpenCAL-OMP implementation of the Conway's game of Life.]{../opencal/OpenCAL-OMP/examples/calomp_life/source/life.c}

As you can see, the OpenMP-based implementation of Life, which uses
only safe operations, is alsmost identical to the serial one (listing
\ref{lst:cal_life}). The only differences can be found at lines 3-5
where, instead of including the OpenCAL header files, you can find the
OpenCAL-OMP headers. All the remaining source code is unchanged. Note
that also the OpenCAL-OMP statements' prefix does not change with
respect to the OpenCAL's one (i.e. \verb'cal' for the functions,
\verb'CAL' for the data types, and \verb'CAL_' for the constants). In
conclusion, if you only use OpenCAL-OMP in safe mode, besides
including the proper OpenCAL-OMP header files instead of the OpenCAL
ones, you don't need to change the serial code at all.

\section{SciddicaT}

As for the case of Conway's Game of Life, even the OpenCAL-OMP
implementation of SciddicaT cellular automaton, shown in Lsting
\ref{lst:calomp_sciddicaT}, does not significantly differ from the
serial implementation that you can find in the previous Chapter. As
before, the only differences regard the included headers (lines
3-5). In conclusion, as for the Life cellular automaton, due to the
fact we used only OpenCAL-OMP safe operations, besides including the
proper OpenCAL-OMP header files instead of the OpenCAL ones, you don't
need to change the serial code at all.

\lstinputlisting[label=lst:calomp_sciddicaT, caption=An OpenCAL-OMP implementation of the SciddicaT debris flows simulation model.]{../opencal/OpenCAL-OMP/examples/calomp_sciddicaT/source/sciddicaT.c}

\section{SciddicaT with active cells optimization}
Here we present an OpenCAL-OMP implemenation of SciddicaT, which takes
advantage of the built-in OpenCAL active cells optimization. You can
find the complete source code in Listing
\ref{lst:calomp_Sciddicat-activecells}, while the corresponding serial
implementation can be found in previous Chapter.

\lstinputlisting[label=lst:calomp_Sciddicat-activecells, caption=An OpenCAL-OMP implementation of the SciddicaT debris flows simulation model with the active cells optimization.]{../opencal/OpenCAL-OMP/examples/calomp_sciddicaT-activecells/source/sciddicaT.c}

With respect to the Sciddica implementation in Listing
\ref{lst:calomp_sciddicaT}, which is exclusively based on safe
OpenCAL-OMP operations, the active cells management, as implemented
here, requires an unsafe operation. Such an unsafe operation is
performed by means of the \verb'calAddActiveCellX2D()' function (line
87), which adds a cell belonging to the neighbourhood to the set $A$
of active cells. Such an operation both breasks the formal definition
of Omogeneous Cellular Automanta, and also can give rise to race
condition. In fact, if more threads try to add the same cell to the
set $A$ at the same time, being this a non-atomic operation, the
result can be wrong. In order to avoid this possible error,
OpenCAL-OMP is able to \emph{lock} the memory locations involved in
the operations so that each thread can entirely perform its own task,
without the risk other threads interfere. In order to do that, it is
sufficient to put OpenCAL-OMP in \emph{unsafe} state by calling the
\verb'calSetUnsafe2D()', as done al line 163. No other modifications
to the serial source code are required.

\section{SciddicaT as eXtended CA}


\section{SciddicaT with explicit simulation loop}


\begin{table}
  \centering
  \begin{tabular}{l|c|c|c|c|c|c}
    \hline
    T version & Serial [s] & 1thr & 2thr & 4thr & 6thr & 8thr\\
    \hline
    \hline
    naive         & 240s & 0.82 (293s) & 1.22 (196s) & 1.53 (157s) & 1.64 (146s) & 1.6 (150s)\\
    active cells  & 23s  & 0.77 (30s)  & 1.36 (17s)  & 1.77 (13s)  & 2.09 (11s)  & 2.3 (10s)\\
    eXtended CA   & 13s  & 0.77 (17s)  & 1.86 (7s)   & 2.6  (5s)   & 2.17  (6s)  & 2.6 (5s)\\
    explicit loop & 12s  & 0.75 (16s)  & 1.2  (10s)  & 2.4  (5s)   & 2.4  (5s)   & 3.0 (4s)\\
    \hline
  \end{tabular}
  \caption{Speedup of the four different
    implementations of the SciddicaS3hex debris flows model accelerated by OpenMP.}
  \label{tab:speedup}
\end{table} 

\begin{table}
  \centering
  \begin{tabular}{l|c|c|c|c|c|c}
    \hline
    S3-hex version & Serial [s] & 1thr & 2thr & 4thr & 6thr & 8thr\\
    \hline
    \hline
    naive         & 1030s & 0.52 (1982s) & 0.9 (1142s) & 1.03 (998s) & 1.13 (913s) & 1.3  (781s)\\
    active cells  & 55s   & 0.86 (64s)   & 1.57 (35s)  & 2.75 (20s)  & 2.5  (22s)  & 3.06 (18s)\\
    eXtended      & 27s   & 0.87 (31s)   & 1.42 (19s)  & 2.7  (10s)  & 2.46 (11s)  & 3.38 (8s)\\<commit_msg>Added SciddicaT omp explicit, still incomplete<commit_after>\chapter{OpenCAL OpenMP version}

With the name OpenCAL-OMP, we identify the OpenMP implementation of
the software library, which can run on all the cores for your CPU. If
you are luky and have a shared memory multiptocessor system,
OpenCAL-OMP can also exploit all the cores of all your CPUs.

Similarly to the serial version, OpenCAL-OMP allows for some
\emph{unsafe operations}, which can significantly speed up your
application. Howevewr, it must be given the utmost attention due to
possible problems related to race condions. In particular, when many
theads perform concurrent operations on the same memory locations, if
such operation are made by more than one basic machine instructions,
it can appen they can interleave, giving rice to wrong
results. Furthermore, even in the case of atomic operations, race
conditions can occur if the logic order of execution is not
respected. For instance, in a sequence of write-read atomic
operations, it can occur that the read is performed before the write
due to the fact that the thread performing the write is executed
first.

In the following sections, we will introduce OpenCAL-OMP by comparing
examples source code differences with respect to the serial
implemebntations. In the first part of the Chapter, we will deal with
the OpenCAL's safe mode, while in the last one, we will discuss unsafe
operations.

\section{Conway's Game of Life in OpenCAL-OMP}

In Section \ref{sec:cal_life}, we described Conway's Game of Life and
shown a possible implementation using the \verb'OpenCAL' serial
library. Here, we present a \verb'OpenCAL-OMP' implementation of the
same cellular automaton in listing \ref{lst:calomp_life}, by
discussing the differences with respect the serial implementation.

\lstinputlisting[float,floatplacement=H, label=lst:calomp_life, caption=An OpenCAL-OMP implementation of the Conway's game of Life.]{../opencal/OpenCAL-OMP/examples/calomp_life/source/life.c}

As you can see, the OpenMP-based implementation of Life, which uses
only safe operations, is alsmost identical to the serial one (listing
\ref{lst:cal_life}). The only differences can be found at lines 3-5
where, instead of including the OpenCAL header files, you can find the
OpenCAL-OMP headers. All the remaining source code is unchanged. Note
that also the OpenCAL-OMP statements' prefix does not change with
respect to the OpenCAL's one (i.e. \verb'cal' for the functions,
\verb'CAL' for the data types, and \verb'CAL_' for the constants). In
conclusion, if you only use OpenCAL-OMP in safe mode, besides
including the proper OpenCAL-OMP header files instead of the OpenCAL
ones, you don't need to change the serial code at all.

\section{SciddicaT}

As for the case of Conway's Game of Life, even the OpenCAL-OMP
implementation of SciddicaT cellular automaton, shown in Lsting
\ref{lst:calomp_sciddicaT}, does not significantly differ from the
serial implementation that you can find in the previous Chapter. As
before, the only differences regard the included headers (lines
3-5). In conclusion, as for the Life cellular automaton, due to the
fact we used only OpenCAL-OMP safe operations, besides including the
proper OpenCAL-OMP header files instead of the OpenCAL ones, you don't
need to change the serial code at all.

\lstinputlisting[label=lst:calomp_sciddicaT, caption=An OpenCAL-OMP implementation of the SciddicaT debris flows simulation model.]{../opencal/OpenCAL-OMP/examples/calomp_sciddicaT/source/sciddicaT.c}

\section{SciddicaT with active cells optimization}
Here we present an OpenCAL-OMP implemenation of SciddicaT, which takes
advantage of the built-in OpenCAL active cells optimization. You can
find the complete source code in Listing
\ref{lst:calomp_Sciddicat-activecells}, while the corresponding serial
implementation can be found in previous Chapter.

\lstinputlisting[label=lst:calomp_Sciddicat-activecells, caption=An OpenCAL-OMP implementation of the SciddicaT debris flows simulation model with the active cells optimization.]{../opencal/OpenCAL-OMP/examples/calomp_sciddicaT-activecells/source/sciddicaT.c}

With respect to the Sciddica implementation in Listing
\ref{lst:calomp_sciddicaT}, which is exclusively based on safe
OpenCAL-OMP operations, the active cells management, as implemented
here, requires an unsafe operation. Such an unsafe operation is
performed by means of the \verb'calAddActiveCellX2D()' function (line
87), which adds a cell belonging to the neighbourhood to the set $A$
of active cells. Such an operation both breasks the formal definition
of Omogeneous Cellular Automanta, and also can give rise to race
condition. In fact, if more threads try to add the same cell to the
set $A$ at the same time, being this a non-atomic operation, the
result can be wrong. In order to avoid this possible error,
OpenCAL-OMP is able to \emph{lock} the memory locations involved in
the operations so that each thread can entirely perform its own task,
without the risk other threads interfere. In order to do that, it is
sufficient to put OpenCAL-OMP in \emph{unsafe} state by calling the
\verb'calSetUnsafe2D()', as done al line 163. No other modifications
to the serial source code are required.

\section{SciddicaT as eXtended CA}
Here we present an OpenCAL-OMP implemenation of SciddicaT, which takes
advantage of the built-in OpenCAL unsafe operations. They represents
an extension of the Omogeneous Cellular Automata definition, allowing
for further computational optimizations. Using unsafe operation, give
rise to an eXtended CA, as described in the previous chapter. You can
find the complete source code of SciddicaT implemented as an eXtended
CA in Listing \ref{lst:calomp_SciddicaT-unsafe}, while the
corresponding serial implementation can be found in Listing
\ref{lst:cal_sciddicaT-unsafe}, in previous Chapter.

\lstinputlisting[label=lst:calomp_SciddicaT-unsafe, caption=An OpenCAL-OMP implementation of the SciddicaT debris flows eXtended CA simulation model with unsafe optimization.]{../opencal/OpenCAL-OMP/examples/calomp_sciddicaT-unsafe/source/sciddicaT.c}

Note that, only the topographic altitude and the debris thicness are
now considered as model's substates (lines 25-28, 147-148), as the
four outflows substates are no longer needed. Moreover, the number of
elementary process now considered is two (lines 143-144), instead of
three for the previous versions of SciddicaT.

The call to the \verb'calSetUnsafe2D()' function (line 139) puts
OpenCAL-OMP in unsafe state, allowing to lock memory locations
(i.e. cells) that can be simultaneously accessed by more threads. In
order to lock a cell, you have to use spacific functions, which are
provided by the \verb'OpenCAL-OMP/cal2DUnsafe.h' header file (line
6). In the specific case, besides \verb'calAddActiveCellX2D()', the
\verb'calAddNext2Dr()' and \verb'calAddNextX2Dr()' functions are
employed (lines 88-89). In fact, a combination of get-set operations,
as done in the corresponding serial implementation (Listing
\ref{lst:cal_sciddicaT-unsafe}, can not be considerd. In fact, let
considered the snippet of code in Listing \ref{lst:get-set}. As you
can see, for each not-eliminated cell, the algorithm computes a flow,
$f$ (line 5), and then subtract it from the central cell (line 6) and
add it to the corresponding neigbour (line 7), in order to perform the
mass balance. In both cases (flow subtraction and adding), a flawor of
\verb'calGet' function is called to read the current value of the
$Q_h$ substate at the next working plane. Subsequently, a flawor of
\verb'calSet' function is used to update the previously read
value. When a single thread is used to perform such operations, no
race conditions can occur. At the contrary, even in the case of two
concurrent threads, different undesirable situations can take place,
which give rise to wrong resutls. For instance, let suppose both the
threads read the value first, and then they write their updated values;
in this case, the resulting value will correspond to the one written
by the thread that write the value for last, and the contribution of
the other thread will be lost.

\begin{lstlisting}[float,floatplacement=H, label=lst:get-set, caption=Example of non atomic operation made of a combination of get-set calls.]
  // <snip>
  for (n=1; n<sciddicaT->sizeof_X; n++)
  if (!eliminated_cells[n])
  {
    f = (average-u[n])*P.r;
    calSet2Dr (sciddicaT,Q.h,i,j,  calGetNext2Dr (sciddicaT,Q.h,i,j)  -f);
    calSetX2Dr(sciddicaT,Q.h,i,j,n,calGetNextX2Dr(sciddicaT,Q.h,i,j,n)+f);
    // <snip>
  }
  // <snip>
\end{lstlisting}  

In order to avoid such kind of problems whed dealing with more
threads, the above mentioned \verb'calAddNext2Dr()' and
\verb'calAddNextX2Dr()' functions lock the cell under condideration
and then perform the get-set oprations. In this way, is ensured that
only a thread can work at the same time and no race conditions can
occur. Obviously, this can give rise to a lack of performance.


\section{SciddicaT with explicit simulation loop}

As for the serial version, aslo for the OpenMP based realease of OpenCAL is
further possibile to improve computational performance of SciddicaT by
avoiding unnecessary substates updating.

As we already stated, the \verb'calRun2D()' function used so far to
run the simulation loop updates all the defined substates at the end
of each elementary process. However, in the specific case of the
SciddicaT XCA model, no substates updating should be executed after
the application of the second elementaty process, as it just remove
inactive cells from the set $A$.

A new OpenCAL implementation of SciddicaT is presented in Listing
\ref{lst:calomp_sciddicaT-explicit}. It is based on an explicit global
transition function, defined by means of \verb'calRunAddGlobalTransitionFunc2D()'. registers a callback functions within which you can both reorder the sequence of elementary processes to be applyed in the generic computational step, and also chouse which substates have to be updated. It also explicitates the simulation loop and also
defines a stopping criterion for the simulation termination. The
complete implementation is shown for the sake of completeness.


\lstinputlisting[label=lst:calomp_sciddicaT-explicit, caption=An OpenCAL-OMP implementation of the SciddicaT XCA debris flows simulation model with explicit simulation loop.]{../opencal/OpenCAL-OMP/examples/calomp_sciddicaT-unsafe-explicit/source/sciddicaT.c}



\begin{table}
  \centering
  \begin{tabular}{l|c|c|c|c|c|c}
    \hline
    T version & Serial [s] & 1thr & 2thr & 4thr & 6thr & 8thr\\
    \hline
    \hline
    naive         & 240s & 0.82 (293s) & 1.22 (196s) & 1.53 (157s) & 1.64 (146s) & 1.6 (150s)\\
    active cells  & 23s  & 0.77 (30s)  & 1.36 (17s)  & 1.77 (13s)  & 2.09 (11s)  & 2.3 (10s)\\
    eXtended CA   & 13s  & 0.77 (17s)  & 1.86 (7s)   & 2.6  (5s)   & 2.17  (6s)  & 2.6 (5s)\\
    explicit loop & 12s  & 0.75 (16s)  & 1.2  (10s)  & 2.4  (5s)   & 2.4  (5s)   & 3.0 (4s)\\
    \hline
  \end{tabular}
  \caption{Speedup of the four different
    implementations of the SciddicaS3hex debris flows model accelerated by OpenMP.}
  \label{tab:speedup}
\end{table} 

\begin{table}
  \centering
  \begin{tabular}{l|c|c|c|c|c|c}
    \hline
    S3-hex version & Serial [s] & 1thr & 2thr & 4thr & 6thr & 8thr\\
    \hline
    \hline
    naive         & 1030s & 0.52 (1982s) & 0.9 (1142s) & 1.03 (998s) & 1.13 (913s) & 1.3  (781s)\\
    active cells  & 55s   & 0.86 (64s)   & 1.57 (35s)  & 2.75 (20s)  & 2.5  (22s)  & 3.06 (18s)\\
    eXtended      & 27s   & 0.87 (31s)   & 1.42 (19s)  & 2.7  (10s)  & 2.46 (11s)  & 3.38 (8s)\\
{'fraction_non_alphanumeric': 0.07411284990081551, 'fraction_numerical': 0.025071633237822348, 'mean_word_length': 4.300525700934579, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6367372', 'n_tokens_mistral': 5836, 'n_tokens_neox': 5408, 'n_words': 2439}