\chapter{THE COMBINATION LOCK}

\label{chapter_combination_lock}

%
%  This images from Wikipedia "Combination Lock" web page.
%
  \begin{figure}[h]
    \includegraphics[width=0.49\textwidth]{chap_combination_lock/combination_discs.png}
    \includegraphics[width=0.49\textwidth]{chap_combination_lock/combination_unlocked.png}
    \caption{The locking rings (left) and the combination lock (right)}
  \end{figure}
  
\section{Introduction}

A determined, methodical, and careful person can open a combination lock,
given enough time, simply by trying every possible combination in order.
If someone offers to help, and there's a copy of the lock with the
same unknown combination, then we can expect the task to be accomplished
in half the time, and if more helpers are available, the better.

We can formulate the combination lock problem on the computer, and
simulate the procedure of a person trying to determine the combination.
What may be surprising is that, if more than one processor is available
to the computer, it is again possible to accomplish the task more quickly,
by sharing the work among the available ``helpers''.

\section{The Combination Lock Problem}

A common class of combination locks involves a set of identical numbered
dials, each of which can be turned independently to display one of the
numbers.  The lock is manufactured in such a way that it will only open
if each dial has been set to the correct numeric setting, called the
``combination''.  A typical lock used for a bicycle or suitcase might 
have three dials, each labeled with the digits 0 through 9.  Such a lock
obviously has exactly $10 \times 10 \times 10 = 1,000$ possible combinations.

Since we will be interested in variations of this problem, let's reserve
$m$ to represent the number of dials, and $n$ be the number of digits
or symbols or settings to choose from on each dial.  Using this notation,
we may conveniently refer to a combination lock by specifying the two
values $(m,n)$, in that order.  The bicycle lock is thus a $(3,10)$ lock.

The number of combinations in an $(m,n)$ lock is $n^m$, which means that,
simply by adding a few more dials or symbols, we can quickly be looking
at millions or billions of combinations.  The combination lock thus has
a feature common to many computational problems that can be described by a
few parameters: for small parameter values, the problem is easily solved,
but with a modest increase, the problem quickly becomes extremely 
difficult.

If we wish to pose an example of the combination lock problem, we must
include a choice for the combination.  We can designate this by $c$.
The quantity $c$ must be a vector of length $m$, containing the correct
settings for the dials.  Once we have selected the lock parameters $(m,n)$ 
and the combination $c$, we have described a problem.  

A locksmith could build this lock, and allow contestants to try to open it.
We, instead, will ``build'' a simulation of the lock on the computer,
and follow that up by simulating the procedure by which someone might try
to determine the combination.
  
\section{Opening the Bicycle Lock Sequentially}

We'll start by determining the combination of a (3,10) bicycle lock.
Since there are just 10 symbols on the dials, we can think of represent
them as the digits 0 through 9.  By concatenating the three symbols of
the combination, we can think of it as simply a number between 0 and 999.
This point of view makes it easy to come up with a solution procedure,
(just start counting!).  It also makes it possible to pause at any time,
and restart later, as long as we know the last combination we tried.  We will
use that fact shortly.

A simple MATLAB procedure for the bicycle lock problem might be:
\begin{lstlisting}
%% combination_lock.m
%
%  Set the combination C.
%
  rng ( 'shuffle' );
  c = randi ( [ 0, 999 ], 1, 1 );
%
%  Generate every number A between 0 and 999,
%  and then see if it is the combination C.
%
  for a = 0 : 999

    if ( a == c )
      fprintf ( 1, '\n' );
      fprintf ( 1, '  The combination is %d!\n', a );
      break
    end
  
  end
\end{lstlisting}

Given how simple the solution is, it might hardly seem that this problem 
was worth coding up.  But before we go on, let us note that the reason we were
able to solve the problem was that we came up with a representation for 
the combinations, and a procedure for generating each combination exactly once.

\section{Opening the Bicycle Lock in Parallel}

Because we were able to represent the possible combinations as the integers between
0 and 999, it should be clear how the solution procedure could be speeded up if
we had one or more workers to help us: simply divide up the range [0,999] among 
the available workers so that each combination is checked by somebody.
Perhaps the worker who finds the answer should also announce this fact so that
the others can stop looking.

Since this problem will run very quickly on a single processor, it
might not seem worth using parallel computing.  Nonetheless, it's so
easy to request parallel processing that we might as well introduce it
for this example.  We have to replace the keyword {\bf{for}} by
{\bf{parfor}}, if a MATLAB loop is appropriate for parallel processing.
The {\bf{parfor}} statement indicates that the work of the loop, (the
individual iterations) can be divided up among the set of available
processors.

Our sequential code includes a {\bf{break}} statement.  The rules for
using the {\bf{parfor}} statement require that the loop not involve
any {\bf{break}} statements.  Fortunately, we can easily modify our
program to omit the {\bf{break}}; as long as we print the combination
when we find it, we will get the information we need.

Thus, the text of a parallel version of our algorithm might be:

\begin{lstlisting}
%% combination_lock_parfor.m
%
%  Set the combination C.
%
  rng ( 'shuffle' );
  c = randi ( [ 0, 999 ], 1, 1 );
%
%  Generate every number A between 0 and 999,
%  and then see if it is the combination C.
%
  parfor a = 0 : 999

    if ( a == c )
      fprintf ( 1, '\n' );
      fprintf ( 1, '  The combination is %d!\n', a );
    end
  
  end
\end{lstlisting}

The revised program can still be executed by MATLAB, in the usual
way; however, the ``usual way'' involves running sequentially.
So once we've created a parallel program, we have to issue some
commands to MATLAB to request that the program actually be run using
multiple processors.  Assuming our desktop machine has 
the Parallel Computing Toolbox installed, let's run the algorithm
with 4 processors:

\begin{lstlisting}
%% Run the parfor script on 4 local workers

  matlabpool open local 4

  combination_lock_parallel
  
  matlabpool close
\end{lstlisting}

The {\bf{matlabpool}} command directs MATLAB to set up a pool of
4 workers; the script begins executing with the client copy of
MATLAB, but when the {\bf{parfor}} statement is reached, these workers
are called, and each is assigned a segment of the loop iteration range.
One of the workers finds the combination and prints it; but each
worker continues until it has checked every value in its range.
Once all the loop iterations are completed, the workers ``retire'', and
the client resumes control of the calculation.

\section{Discussion}

Our simple example asks us to find the combination, and we simply pick
a number at random as our goal, which might make the whole search seem somewhat
contrived.  But in fact, many real problems share this structure, with
the exception that now the answer isn't known in advance.  For example,
instead of searching for a 3 digit integer $a$ that equals $c$, we might be 
searching for a number $a$ such that the function 
$f(x) = x^5-123x^4+2x^3-246x^2+3x-369$ is equal to zero.  There is just
one value $a$ between 0 and 999 for which this is true, and we can search
for it in the same way, but now the answer is no longer obvious.

In this example, it's easy to believe that we can replace a sequential
calculation by one in which multiple workers divide up the job and
complete it correctly, because the task was so simple.  There are no
complicated arrays to be read or written, no worker has to consider
what any other worker has done.  But surely most problems are much
more complicated than this one; it's natural to worry about a complicated
numerical calculation can similarly be divided up among cooperating
workers.  We will address such issues shortly.

Another issue is that while we have been successful in running the program
in parallel, our real goal is to get answers faster.  For this tiny
example, it's not really clear that we have achieved any such benefit.
In fact, if you actually run the parallel code, you will notice that 
the {\bf{matlabpool}} command takes a perceptible time to complete, 
perhaps longer than the calculation itself.  Our main purpose in this 
example was simply to get {\it{something}} running in parallel, the 
simpler the better - however, it is important
not to imagine that a parallel program is better, or guaranteed to be
faster, than a sequential version.  In fact, we will see that it is
always important, when using parallel programming, to check that
parallelism is helpful for the number of processors and problem sizes
that we are likely to consider.


