\documentclass{sig-alternate-05-2015}
\begin{document}

% ACM templates include ISBN and DOI...
\isbn{N.A.}
\doi{N.A.}

\title{GPUMC Assignment 2: Kentucky's Line Extrusion Orderer}
\subtitle{Implementor's Notes}

\numberofauthors{1}
\author{
Hank Dietz\\
       \affaddr{Department of Electrical and Computer Engineering}\\
       \affaddr{University of Kentucky, Lexington, KY USA}\\
       \email{\texttt{hankd@engr.uky.edu}}
}

\maketitle
\begin{abstract}

This project involved modifying a serial C program that uses a
genetic algorithm to reorder extrusion of line segments to
minimize print time (total travel time between line segments).
The idea is to speed-up the program by using OpenMP.

\end{abstract}


\section{General Approach}

The key to getting speedup is to parallelize things at the
highest level possible. Here, there were two convenient spots:

\begin{itemize}
\item

The population initialization loop. It turns out that
\texttt{greedy()} is one of the most expensive operations, so
parallelizing execution across multiple copies of it yields good
speedup.

\item

The loop over all ``generations" in the genetic algorithm. This
offers a huge amount of parallelism if the population is large,
but fundamentally hits two problems. First, the serial
steady-state GA only replaces one population member at a time,
but this will replace multiple ones simultaneously, so we'll
need to ensure the population members being worked on are
disjoint.  Second, there is a subtle change in the search
statistics because disjoint sets of members being operated upon
means that a newly-created population member can be directly
involved in no more than one of the \texttt{nproc} simultaneous
creations of new members... this will slow convergence.

\end{itemize}

Both of those parts of the code simply turn into OpenMP
\texttt{parallel for} constructs, however, there are a few
things that need to be dealt with for shared access:

\begin{itemize}
\item

A lot depends on being able to \texttt{mkorder()} in parallel,
so we need to ensure threads use a private (local) order buffer.

\item

The standard \texttt{rand()} isn't thread safe, so we need to
use something else... here, \texttt{rand\_r()} with
\texttt{rseed[iproc]} for its state and inital values generated
sequentially calling \texttt{rand()}. It turns out that
\texttt{rand\_r()} is not very random in the low bits, so for
\texttt{RANDPLACE}, I divide the value by 13 to help randomize
the low bits. Using a prime population size would also help
randomize.

\item

The update of the best value found so far is protected by an
OpenMP lock: \texttt{bester}.

\item

To avoid deadlock, each thread needs to pick (and claim) all the
population members for making a new member in one shot. This is
done by \texttt{claim3()} and they are released by
\texttt{unclaim3()}. The array \texttt{claimed[]} tracks which
population members have been claimed, and the OpenMP lock
\texttt{claimer} ensures one one claim is processed at a time.

\end{itemize}

Note that both updating the best and claiming members to work on
are done in ways that try to minimize the work done while locked.

% insert a break to roughly level columns...
%\vfill\pagebreak

\section{Performance}

Running on 4 procesors, typical speedup is between 2X and 3X.

The final schedule is now sent to \texttt{stderr}.

\section{Issues}

The modified code will not work without \texttt{-fopenmp}.

Parallel results obtained were often slightly inferior to the
sequential version because of the aversion to reuse of the best.
Perhaps \texttt{claim3()} should prefer picking \texttt{abest}?
To better understand how the search worked, I replaced the
\texttt{VERBOSE} tracking with logic that tracks the history
of each population member in the array \texttt{by[][]}. This
revealed that new best are rarely derived from Random starts,
and almost never combined Original, Greedy, and Random.

There was a bug in \texttt{rotate()} in the distributed version
of \texttt{kleo.c} that made \texttt{a} a rotation of
\texttt{a}, not of \texttt{b}. It was fixed and a comment
inserted.



\end{document}
