\chapter{TIME, WORK, RATE}

\label{chapter_time_work_rate}


  \begin{figure}[h]
  \begin{centering}
    \includegraphics[width=0.050\textwidth]{chap_work_time_rate/ruler.png}
    \includegraphics[width=0.18\textwidth]{chap_work_time_rate/hourglass.png}
    \includegraphics[width=0.40\textwidth]{chap_work_time_rate/speedometer.png}
    \caption{Distance / Time = Rate}
  \end{centering}
  \end{figure}

  
\section{Introduction}

We use a computer because we want an answer.  We use parallel programming
because we want that answer {\it{faster}}.  So we have to assume we already
know how to compute the answer, and we are looking for ways to speed up
the computation.  There are many things we can try, but we need to have a
reliable method of measuring whether a revised program really does run faster.
This means we need to be understand how to measure computational work, time,
and rate.

\section{Absolute Computational Work}

When Charles Babbage was designing his Analytical Engine in 1837, he used the word
``mill'' to describe the part of the machine that carried out operations on numbers.
Even today, it is sometimes useful to think of a computer as a kind of machine
that takes a bucket of raw numbers as input, carries out some kind of work on them,
and produces a bucket of output numbers.  We can actually take this simplified model
and make some rough approximations of the amount of work involved.

As long as we're ruthlessly simplifying, we'll assume that we're only dealing with
a floating point numbers, and that the task we have to carry out can always be
arranged so that it involves nothing more than the four basic arithmetic operations
of addition/subtraction, and multiplication/division.  The amount of work, called
the {\it{operation count}} can then be determined by looking at the code and counting 
the floating point operations.

To get an example of such an operation, consider the process of Gauss elimination
when applied to a matrix.  On step $k$, we determine the pivot row, move it
into the $k$-th row of the matrix, and then add a multiple of row $k$ to
each row $i$ from $k+1$ to $n$ in such a way that we zero out the entry $a(i,k)$.
This is an example of a ``saxpy'' operation, symbolized by $x \leftarrow x + s * y$,
where we multiply a vector $y$ by a scalar $s$ and add it to a vector $x$.

MATLAB allows us to write the code for such an operation in the compact form
\begin{lstlisting}
  x = x + s * y;
\end{lstlisting}
but for clarity, let's write it out:
\begin{lstlisting}
  for i = 1 : n
    x(i) = x(i) + s * y(i);
  end
\end{lstlisting}
We see that the operation count for the saxpy operation is $2n$.

Similarly, it is not difficult to see that the operation count for a dot product
of two vectors is also $2n$, while multiplying
an $m \times n$ matrix $A$ times an $n$-vector $x$ is $2mn$.  Counting the work
in Gaussian elimination is more difficult because at each step, the length and number
of the vectors involved decreases; the operation count is on the order of
$\frac{2n^3}{3} + \frac{3n^2}{2} - \frac{7n}{6}$ and the value $\frac{2n^3}{3}$ 
is generally an acceptable estimate.

\section{Wallclock and Processor Times}

We use parallel programming because it has the potential to get our
results faster.  If we're running a program interactively, then we
might be able to guess when a program runs faster; for a better measurement,
we could look at a clock.  However, since computers can do billions of
operations in one second, we'll really need a more accurate and automatic
procedure for measuring time if we want to judge performance rates.

We know that a computer has an internal clock that controls the pace of 
operations.  We'll make the assumption that each ``tick'' of the computer's 
clock measures a time period during which one operation can be carried out.
To measure the amount of (human) time that elapse during a computation, the
computer can simply count the number of ticks between the start and finish,
and multiply by a conversion value that records the length of a single
tick in seconds.  This measurement is called the {\it{wallclock time}},
because it represents a very accurate value for time elapsed from the
start to finish of our program, and it's the quantity that we hope to
reduce by converting to parallel programming.

You may have heard of another time measurement that can be used in computing,
which was once called {\it{CPU time}}, or now, {\it{processor time}}.  To explain
this, we must first mention that a computer is typically running many programs,
not just your MATLAB job.  If the computer has a single processor, then it is
responsible for executing all these programs.  It does this by a sort of
time sharing, in which each program is brought into the processor, executed
for a fixed slice of time, then temporarily frozen so that the next program
can be brought in.  Under such a system, it would be unwise to use the
wallclock time to measure performance, since the program we are interested in
would actually only have been executing for a portion of that time.  Hence,
methods were developed that allowed a program to request a separate report
that only counted the time during which the program was actually being
run by the processor.

Even in the old days, if you were running a large computation, the difference
between wallclock and CPU time was usually not outrageous; moreover, as long
as you were running on a desktop computer that you controlled, you could make
sure to turn off as many other unnecessary programs as you could, so that the
processor could focus on the program of interest.

Now, when we are trying to compare sequential and parallel programs, the CPU
time is of much less interest.  In fact, we'd expect that the parallel program
would always run up at least as much processor time as the sequential program,
since it's doing the same work.  We're far more interested in whether or not
that work was completed in a shorter time interval, because it was properly
divided up among several processors.

\section{Measuring Time}

MATLAB includes the {\bf{tic}} and {\bf{toc}} functions which set a starting
time and then return the time elapsed since that point:
\begin{lstlisting}
  tic;
  
  combination_lock
  
  elapsed_time = toc;
\end{lstlisting}
The same command can be used in parallel.  The {\bf{matlabpool}} command itself 
can take some time.  Typically, we want to ignore that, and focus on the 
parallel computation, so the timing calls should go {\it{inside}} the calls
to {\bf{matlabpool}}:
\begin{lstlisting}
  matlabpool open local 4
 
  tic;
  
  combination_lock_parallel
  
  elapsed_time = toc;
 
  matlabpool close
\end{lstlisting}
The value returned by {\bf{toc}} is measured in seconds, and has an accuracy that can
be as good as one-millionth of a second; this varies from one computer system to another,
and you can find out your computer's resolution using the following simple program: 
\begin{lstlisting}
  tic;
  elapsed_time = toc;
  fprintf ( 1, 'The tic/toc resolution on this computer is %g\n', elapsed_time );
  fprintf ( 1, 'The number of tic/toc ticks is about %d\n', 1 / elapsed_time );
\end{lstlisting}

\section{A Test Drive on Your Computer}

If I look up the specifications for my computer, I find out that I have a
2.8GHz Quad-Core processor.  This means I have four processors (that's good,
I can do parallel processing), and that each processor runs with a clock speed
of $R$ = 2.8 GigaHertz, that is, it ``ticks'' 2.8 billion times a second.
 
When I run the {\tt{tick\_tock\_resolution.m}} code on this computer, I get
a tic/toc resolution of about 1.4 millionths of a second, and about 680,000
tic/toc ticks per second; in other words, tic/toc is pretty good, but the shortest
event it can measure lasts 4 ticks on my computer's clock.  Since we will usually
be interested in measure large computations with thousands or millions of operations,
tic and toc will be accurate enough for us.

Now let's assume that I am running a sequential MATLAB program, and that
the amount of work involved is $w$ floating point operations.  If the processor
could really do exactly one operation per clock tick, and it had nothing to 
do but my explicit instructions, then it will be interesting to compute the
computational rate $r = \frac{w\hbox{ (floating point operations)}}{s\hbox{ (seconds)}}$
and compare it to $R$.

\begin{lstlisting}
%% dot_product_timing
  x = rand ( n, 1 );
  y = rand ( n, 1 );

  tic;
  z = 0.0;
  for i = 1 : n
    z = z + x(i) * y(i);
  end
  t = toc;

  r = ( 2 * n ) / t;
  R = 2800000000;
  fprintf ( 1, '%d  %g  %g\n', n, r, R );
\end{lstlisting}

Our script leaves the value $n$ as a variable.  We will run the script for
values of $n$ that are powers of 2, from $2^0$ to $2^{25}$, and keep track of
the results.  Once the problem size $n$ gets big enough, the plot for the
computational time seems to follow a reasonable linear pattern, which suggests
that the time measurements made by {\bf{tic}} and {\bf{toc}} are properly
related to the work being carried out.

  \begin{figure}[h]
  \begin{centering}
    \includegraphics[width=0.80\textwidth]{chap_work_time_rate/dot_product_timing_time.png}
    \caption{Computational Time for the Dot Product}
  \end{centering}
  \end{figure}

When we plot the computational rate, we see a ``ramping up'' effect; that is,
over a significant initial range of values of $n$, the rate rises somewhat
steeply, and then levels off to a plateau, at which we might assume the
computation is proceeding at its maximum possible rate.

  \begin{figure}[h]
  \begin{centering}
    \includegraphics[width=0.80\textwidth]{chap_work_time_rate/dot_product_timing_rate.png}
    \caption{Computational Rate for the Dot Product}
  \end{centering}
  \end{figure}

  \begin{figure}[h]
  \begin{centering}
    \includegraphics[width=0.80\textwidth]{chap_work_time_rate/dot_product_timing_rates.png}
    \caption{Comparison of Dot Product Rate to Maximum}
  \end{centering}
  \end{figure}

\section{Relative Computational Work}

Unlike the dot product, most computations are not simple enough that we can
essentially estimate the number of floating point operations.  This could be
because the computation is complicated, involves many conditional statements,
or invokes special functions whose evaluation requires an iteration of an
unspecified number of steps.  Estimating the number of floating point operations
allows us to measure whether we are using the computer efficiently; but even
if we can't do that, we can still using the idea of timing our code to be able
to judge whether one algorithm is faster than another, or how rapidly the 
work must be growing as the problem size increases.  In this case, we are using
the idea of relative comparison.  We don't know how long it takes to evaluate
the sine function once, but we can expect that it takes ten times longer to
evaluate 10 sine functions.  And we might compare the speed of evaluation of the sine
function using MATLAB's built-in {\it{sin()}} function to the speed where
we used a Taylor series.  

Suppose we need to fill an array {\it{a(,)}} with products of sines and
exponentials, according to the following scheme:
\begin{lstlisting}
function a = sin_exp1 ( m, n )
%% sin_exp1.m
  a = zeros ( m, n );
  for i = 1 : m
    for j = 1 : n
      a(i,j) = sin ( i * pi / m ) * exp ( j * pi / n );
    end
  end
\end{lstlisting}

We don't know how long this process will take, and it will certainly depend on
the values $m$ and $n$.  However, we may realize that the evaluation of {\it{sin()}}
and {\it{exp()}} are expensive operations, and we notice that we're calling these
expensive functions a lot, $mn$ times in fact.  Since we really only need to know the
values of $m$ sines and $n$ exponentials, we could precompute them in vectors $u$ 
and $v$, and then hope to save time, at least if the problem size is large.

\begin{lstlisting}
function a = sin_exp2 ( m, n )
%% sin_exp2.m
  u = zeros ( m, 1 );
  for i = 1 : m
    u(i) = sin ( i * pi / m );
  end
  v = zeros ( n, 1 );
  for j = 1 : n
    v(j) = exp ( j * pi / n );
  end
  for i = 1 : m
    for j = 1 : n
      a(i,j) = u(i) * v(j);
    end
  end
\end{lstlisting}

Looking more carefully at the calculation of the result {\it{a(,)}}, we might
notice that it has the form of a vector ``outer product'', that is, the product
of two vectors that creates an array as the result.  MATLAB knows about outer
products just like it knows about inner products, and can evaluate them rapidly.
So we might try to speed up our calculation by writing it in the language of vectors:
\begin{lstlisting}
function a = sin_exp3 ( m, n )
%% sin_exp3.m
  u = sin ( ( 1 : m ) * pi / m );
  v = exp ( ( 1 : n ) * pi / n );
  a = u' * v;
\end{lstlisting}

We know how to time these calculations:
\begin{lstlisting}
  nv = zeros ( 12, 1 );
  t1 = zeros ( 12, 1 );
  t2 = zeros ( 12, 1 );
  t3 = zeros ( 12, 1 );
  m = 1000;
  n = 1;
  for j = 1 : 12
    nv(j) = n;
    tic
    a = sin_exp1 ( m, n );
    t1(j) = toc;
    tic
    b = sin_exp2 ( m, n );
    t2(j) = toc;
    tic
    c = sin_exp3 ( m, n );
    t3(j) = toc;
    n = n * 2;
  end
\end{lstlisting}

For this study, the value of $n$ doubles at each successive measurement point.
That suggests that if we plot the data, we should use a logarithmic scale for $n$;
otherwise, much of the data will be bunched up on the left hand side and less
visible.

  \begin{figure}[h]
  \begin{centering}
    \includegraphics[width=0.80\textwidth]{chap_work_time_rate/sin_exp_time_absolute.png}
    \caption{Absolute Time Comparison for Three Equivalent Algorithms}
  \end{centering}
  \end{figure}

Now the actual times are not of interest to us.  It means much more to be able to
say that algorithm 3 took twice or a tenth as much time as algorithm 1.  Assuming
that algorithm 1 is our base for comparison, we can make a plot of the ratio between
the time a given algorithm took and the time algorithm 1 required, which is a 
relative time comparison.

  \begin{figure}[h]
  \begin{centering}
    \includegraphics[width=0.80\textwidth]{chap_work_time_rate/sin_exp_time_relative.png}
    \caption{Relative Time Comparison for Three Equivalent Algorithms}
  \end{centering}
  \end{figure}

Although the relative time plot is easier to understand, it's hard to avoid the
psychological reaction that the graph rising the highest represents the best result.
But we can avoid that misinterpretation by plotting the relative {\it{rate}} or 
{\it{speed}} rather than time; that is, we plot the time algorithm 1 required divided
by the time the given algorithm required.  Notice that, at least for this example,
our decision to display relative speeds means that the results for algorithm 3
(the winner in this particular competition) are shown with greater detail,
whereas the slower algorithm is much less prominent.

  \begin{figure}[h]
  \begin{centering}
    \includegraphics[width=0.80\textwidth]{chap_work_time_rate/sin_exp_speed_relative.png}
    \caption{Relative Speed Comparison for Three Equivalent Algorithms}
  \end{centering}
  \end{figure}

Recall that the computation rate was defined by $r = w / t$, where $w$ was the work,
and $t$ the time.  We ran algorithms 1, 2, and 3 and got timings $t1$, $t2$ and $t3$,
but we weren't able to estimate $w$, so we can't compute a true (absolute) rate.
However, the relative speed is the {\it{ratio}} of the rates, and in that case,
$w$ is a common factor, and drops out, so it doesn't matter if we don't actually know
its value:
\begin{displaymath}
  \frac{r3}{r1} = \frac{w/t3}{w/t1} = \frac{t1}{t3}
\end{displaymath}
which justifies our natural assumption that, when judging speeds, even if we can't say whether 
either of two programs is actually fast, we should always prefer the one
that is faster than the other!
