\title{cs378: Concurrency: Lab 1 Writeup Template}
\author{
        You \\
        Department of Computer Science\\
        UT Austin
}
\date{\today}

\documentclass[9pt]{article}
\usepackage{graphicx}
\usepackage[margin=1.2in]{geometry}

\begin{document}
\maketitle

\section{Step 1: Unsynchronized Workers}\label{step1}

\begin{figure}[t]
  \centering
  \includegraphics[width=.9\textwidth]{random-scalability.png}
  \caption{Step 1 scalability sample graph.
  \emph{NOTE: the data in these graphs are random. If your data show different 
  trends that's GOOD.}}
\end{figure}
\label{fig:step-1-scalability}

\begin{figure}[t]
  \centering
  \includegraphics[width=.9\textwidth]{random-lost-updates.png}
  \caption{Step 1 lost-updates sample graph.
  \emph{NOTE: the data in these graphs are random. If your data show different 
  trends that's GOOD.}}
  \label{fig:step-1-lost-updates}
\end{figure}

\begin{figure}[t!!!]
  \centering
  \includegraphics[width=.9\textwidth]{random-load-imbalance.png}
  \caption{Step 1 load-imbalance sample graph.
  \emph{NOTE: the data in these graphs are random. If your data show different 
  trends that's GOOD.}}
  \label{fig:step-1-load-imbalance}
\end{figure}


\subsection{Scalability of an Unsynchronized Counter}
\emph{Using the Unix time utility, time and graph the
  runtime of your program with a maxcounter of 1000000 as a function of the number of workers
  from 1 (sequential) to twice the number of processor cores on
  your machine....}


\begin{itemize}
\item Provide a graph of scalability similar to Figure~\ref{fig:step-1-scalability}.
\item List at least two reasons you can think of why performance gets worse as parallelism
  increases.
\item If performance does not get monotonically worse
  list at least one reason why this might be the case.
\end{itemize}

\subsection{Counting lost updates}
\emph{Now change your program so that each worker counts the number of times
      it actually increments the shared counter variable. You can do this
      with a global array of per-worker counters indexed by say, worker id.
      This will allow you to measure lost updates as well as
      load imbalance. The ratio of lost updates to correct
      updates should simply be the total number of updates summed across
      all workers, divided by the maxcounter value. Without synchronization,
      this should be greater than 1. Create a graph of the lost update
      ratio as a function of worker thread count...}

%% \begin{figure}[t]
%%   \centering
%%   \includegraphics[width=.6\textwidth]{step1-lost-updates.pdf}
%%   \caption{Step 1 lost updates sample graph}
%% \end{figure}

\begin{itemize}
\item Provide a graph of lost updates similar to Figure~\ref{fig:step-1-lost-updates}.
\item Does the number of lost
  updates surprise you or match your expectations?
\item Does the trend match
  the scalability you observe, or differ?
\item Why or why not?
\end{itemize}



\subsection{Load Imbalance}

\emph{...Each thread will differ from expectation differently so 
      graph the average difference from the expected value for each
      worker...}

%% \begin{figure}[t]
%%   \centering
%%   \includegraphics[width=.6\textwidth]{step1-load-imbalance.pdf}
%%   \caption{Step 1 load imbalance sample graph}
%% \end{figure}

\begin{itemize}
  \item Provide a graph of load imbalance similar to Figure~\ref{fig:step-1-load-imbalance}.
  \item Does load imbalance follow a similar pattern to your
      scalability?         
\end{itemize}

\vfill
\eject

\section{Step 1a: Understanding Scalability Loss}\label{step1}

Repeat step 1 with a privatized counter, and answer the questions about what you think the scalability bottleneck is. 

\section{Step 2: Synchronization}\label{step2}

In this sample, the graphs for mutex, spinlocks, and atomics are combined.
You can follow this pattern, or provide separate graphs for each. 

\begin{figure}[t]
  \centering
  \includegraphics[width=.9\textwidth]{random-scalability-atomic-mutex-spinlock.png}
  \caption{Step 2 scaling sample graph. NOTE: DATA IN SAMPLES IS RANDOM.}
\label{fig:step-2-scalability}
\end{figure}


\begin{figure}[t]
  \centering
  \includegraphics[width=.9\textwidth]{random-load-imbalance-atomic-mutex-spinlock.png}
  \caption{Step 2 imbalance sample graph. NOTE: RANDOM DATA!}
\label{fig:step-2-load-imbalance}
\end{figure}

\begin{itemize}
\item Provide a graph of scalability similar to Figure~\ref{fig:step-2-scalability}.
\item Provide a graph of load imbalance similar to Figure~\ref{fig:step-1-load-imbalance}.
\item Do the run-time and load balance as a function of the
      number of threads change significantly for mutexes from the unsynchronized case?
      How about absolute performance? Does the lock make things slower or faster
      or is it a wash?
\item Do the run-time and load balance as a function of the
      number of threads change significantly from the unsynchronized case?
      How about absolute performance? Does the spinlock make things slower or faster
      or is it "a wash"? How does it affect load imbalance, and why?
\item Do scalability, absolute performance, or load imbalance change? Why/why not?
\end{itemize}
  

\eject


\section{Step 3: Load balancing with core affinity}\label{step3}

\begin{figure}[t]
  \centering
  \includegraphics[width=.9\textwidth]{random-step3-scaling.png}
  \caption{Step 3 scaling sample graph. NOTE: data in samples are random.}
  \label{fig:step-3-scaling}
\end{figure}

\begin{figure}[t]
  \centering
  \includegraphics[width=.9\textwidth]{random-step3-load-imbalance.png}
  \caption{Step 3 load imbalance sample graph. NOTE: data in samples are random.}
  \label{fig:step-3-load-imbalance}
\end{figure}

In this sample, the graphs for affinity, load-balanced and single-core pinned
with mutex, spinlocks, and atomics are combined.
You can follow this pattern, or provide separate graphs for each.



\begin{itemize}
\item Provide a graph of scalability similar to Figure~\ref{fig:step-3-scaling}.
\emph{Recall that you are not required to do every locking primitive. It is fine to measure just one,
although we hope you find it interesting to investigate them all.}
\item Provide a graph of load imbalance similar to Figure~\ref{fig:step-3-load-imbalance}.
\emph{Recall that you are not required to do every locking primitive. It is fine to measure just one,
although we hope you find it interesting to investigate them all.}
\item  What changes when you evenly distribute workers to cores and why?
\item What changes when you put all workers on one core and why?
\end{itemize}

\vfill\eject

\section{Step 4}\label{step4}

\begin{figure}[t!!!!]
  \centering
  \includegraphics[width=.9\textwidth]{random-step4-scaling.png}
  \includegraphics[width=.9\textwidth]{random-step4-load-imbalance.png}
  \caption{Step 4 scaling and load imbalance sample graphs for spinlocks. \emph{NOTE: SAMPLES USE RANDOM DATA}}
  \label{fig:step-4-spinlocks}
\end{figure}

\begin{figure}[t!!!!]
  \centering
  \includegraphics[width=.9\textwidth]{random-step4-scaling.png}
  \includegraphics[width=.9\textwidth]{random-step4-load-imbalance.png}
  \caption{Step 4 scaling and load imbalance sample graphs for atomics. \emph{NOTE: SAMPLES USE RANDOM DATA}}
  \label{fig:step-4-atomics}
\end{figure}


\begin{itemize}
\item Provide graphs of scaling and load imbalance for spinlocks as a function of thread count and write probability 
similar to Figure~\ref{fig:step-4-spinlocks}.
\item Provide graphs of scaling and load imbalance for atomics as a function of thread count and write probability 
similar to Figure~\ref{fig:step-4-atomics}.
\item  How do scalability and load imbalance change with read-write ratio
  using spinlocks? Do the data
  match your expectations? Please speculate on any reasons for divergence;
  you are not required to investigate them (yet), but you should feel
  free to do so if you're curious.
\item  How do scalability and load imbalance change with read-write ratio
  using atomics? Do the data
  match your expectations? Please speculate on any reasons for divergence;
  you are not required to investigate them (yet), but you should feel
  free to do so if you're curious.
\end{itemize}

\bibliographystyle{abbrv}
%\bibliography{main}

\end{document}
This is never printed