/usr/share/doc/coop-computing-tools/manual/allpairs.html

<html>
<head>
<title>Allpairs User's Manual</title>
</head>
<body>

<style type="text/css">
pre {
background: #ffffcc;
font-family: monospace;
font-size: 75%
font-align: left;
white-space: pre;
border: solid 1px black;
padding: 5px;
margin: 20px;
}
</style>
<h1>Allpairs User's Manual</h1>
<b>Last Updated October 2010</b>
<p>
Allpairs is Copyright (C) 2009 The University of Notre Dame.
This software is distributed under the GNU General Public License.
See the file COPYING for details.
<p>
<h2>Overview</h2>

<table>
<tr>
	<td valign=middle>
			<a href=http://www.nd.edu/~ccl/software/allpairs/large.gif><img src=http://www.nd.edu/~ccl/software/allpairs/small.gif align=right border=0></a>
	</td>
	<td valign=middle>
		<div id=abstraction>
All-Pairs( array A[i], array B[j], function F(x,y) )<br>
returns matrix M where<br>
M[i,j] = F( A[i], B[j] )<br>
		</div>
	</td>
</tr>
</table>
<p>
The All-Pairs abstraction computes the Cartesian product of two sets,
generating a matrix where each cell M[i,j] contains the output of the function
F on objects A[i] and B[j]. You provide two sets of data files (as in the above
figure, one set is setA = {A0, A1, A2, A3} and the other set is setB = {B0, B1,
B2, B3}) and a function F that computes on them (later in the text we refer to this fuction F as either <b>compare program</b> or <b>compare function</b>. You may optionally provide
additional parameters to control the actual computation, such as computing only
part of the matrix, using a specified number of CPU cores. The abstraction then
runs each of the functions in parallel, automatically handling load balancing,
data movement, fault tolerance and so on for you.

<h2 id="preparation">All-Pairs on a Single Machine</h2>

Let's suppose you have a whole lot of files that you want to compare all to each other, named <tt>a</tt>, <tt>b</tt>, <tt>c</tt>, and so on.  Suppose that you also have a program named <tt>compareit</tt> that when invoked as <tt>compareit a b</tt> will compare files <tt>a</tt> and <tt>b</tt> and produce some output summarizing the difference between the two, like this:
<pre>
a b are 45 percent similar
</pre>
<p>
To use the allpairs framework, create a file called <tt>set.list</tt> that lists each of your files, one per line:
<pre>
a
b
c
...
</pre>
Then, invoke <tt>allpairs_multicore</tt> like this:
<pre>
allpairs_multicore set.list set.list compareit
</pre>
The framework will carry out all possible comparisons of the objects, and print the results one by one:
<pre>
a a are 100 percent similar
a b are 45 percent similar
a c are 37 percent similar
...
</pre>
For large sets of objects, allpairs_multicore will use as many cores as you have available, and will carefully manage virtual memory to exploit locality and avoid thrashing.  Because of this, you should be prepared for the results to come back in any order.

<h2>All-Pairs on a Distributed System</h2>

So far, we have introduced how to use All-Pairs abstraction on a single
machine.  But sometimes the All-Pairs problem is too big to allow a single
machine to finish it in a reasonable amount of time, even if the single machine
is multicore. So, we have built a <a
		href=http://www.cse.nd.edu/~ccl/software/workqueue>Work Queue</a>
version of the All-Pairs abstraction which allows the users to easily apply the
All-Pairs abstraction on clusters, grids or clouds.
<p>
To use the All-Pairs Work Queue version, you will need to start a All-Pairs
master program called <tt>allpairs_master</tt> and a number of workers.
The workers will perform the tasks distributed by the master and return the
results to the master. The individual tasks that the master program distributes
are sub-matrix computation tasks and all the tasks would be performed by the
<tt>allpairs_multicore</tt> program on the workers. For end users, the only
extra step involved here is starting the workers. Starting the All-Pairs master
program is almost identical to starting the All-Pairs multicore program.
<p>
For example, to run the same example as above on a distributed system:
<pre>
allpairs_master set.list set.list compareit
</pre> 

This will start the master process, which will wait for workers to connect.
Let's suppose the master is running on a machine named <tt>barney.nd.edu</tt>.
If you have access to login to other machines, you could simply start
worker processes by hand on each one, like this:
<pre>
% work_queue_worker barney.nd.edu 9123
</pre>
If you have access to a batch system like <a href=http://www.cs.wisc.edu/condor>Condor</a>, you can submit multiple workers at once:
<pre>
% condor_submit_workers barney.nd.edu 9123 10
Submitting job(s)..........
Logging submit event(s)..........
10 job(s) submitted to cluster 298.
</pre>

A similar script is available for Sun Grid Engine:
<pre>
% sge_submit_workers barney.nd.edu 9123 10
</pre>

In the above two examples, the first argument is the port number that the
master process will be or is listening on and the second the argument is the
number of workers to start. Note that <tt>9123</tt> is the default port
number that the master process uses. If you use the '-p' option in the
<tt>allpairs_master</tt> to change the listening port, you will need to
modify the port argument in the starting worker command accordingly.

<p>Once the workers are running, the <tt>allpairs_master</tt> can dispatch tasks
to each one very quickly.  If a worker should fail, Work Queue will retry the
work elsewhere, so it is safe to submit many workers to an unreliable
system.</p>

<p>When the All-Pairs master process completes, your workers will
still be available, so you can either run another master with the same workers,
remove them from the batch system, or wait for them to expire.  If you do
nothing for 15 minutes, they will automatically exit by default.  You
can change this worker expiration time by setting the '<tt>-t</tt>' option.</p>
<p>Note that <tt>condor_submit_workers</tt> and <tt>sge_submit_workers</tt> are
simple shell scripts, so you can edit them directly if you would like to
change batch options or other details.</p>

<h2>Using an Internal Function</h2>

If you have a very fast comparison program (less than a tenth of a second),
the allpairs framework may be spending more time starting your program
than actually accomplishing real work.  If you can express your comparison
as a simple function in C, you can embed that into the allpairs framework
to achieve significant speedups.
<p>
To accomplish this, <a href=http://www.cse.nd.edu/~ccl/software/download.shtml>download</a>
the CCTools source code, and build it.  Then, look for the file <tt>allpairs/src/allpairs_compare.c</tt>.
At the top, you will see a function named <tt>allpairs_compare_CUSTOM</tt>, which accepts
two memory objects as arguments.  Implement your comparison function, and then rebuild
the code.  Test you code by running <tt>allpairs_multicore</tt> on a small set of data,
but specify <tt>CUSTOM</tt> as the name of the comparison program.  If your tests succeeed
on a small set of data, then proceed to using <tt>allpairs_master</tt>.
<p>
We have implemented several internal comparison functions as examples, including:
<dir>
<li> BITWISE - Counts the number of bytes different in each object.
<li> SWALIGN - Performs a Smith-Waterman alignment on two genomic sequences.
<li> IRIS - Performs a similarity comparison between two iris templates.
</dir>

<h2>Tuning Performance</h2>

By default, both <tt>allpairs_master</tt> and <tt>allpairs_multicore</tt> will adjust to
the proprties of your workload to run it efficiently.  <tt>allpairs_master</tt> will run
a few sample executions of your comparison program to measure how long it takes, and
then break up the work units into tasks that take abuot one minute each.  Likewise,
<tt>allpairs_multicore</tt> will measure the number of cores and amount of memory
available on your system, and then arrange the computation to maximize performance.
<p>
If you like, you can use the options to further tune how the problem is decomposed:
<dir>
<li> <tt>-t</tt> can be used to inform <tt>allpairs_master</tt> how long (in seconds)
it takes to perform each comparison.  If given, <tt>allpairs_master</tt> will not
sample the execution, and will start the computation immediately.
<li> <tt>-x</tt> and <tt>-y</tt> can be used to set the size of the sub-problem
dispatched from <tt>allpairs_master</tt> to <tt>allpairs_multicore</tt>
<li> <tt>-c</tt> controls the number of cores used by <tt>allpairs_multicore</tt>,
which is all available cores by default.
<li> <tt>-b</tt> controls the block size of elements maintained in memory by <tt>allpairs_multicore</tt>,
which is 3/4 of memory by default.
</dir>


<h2>For More Information</h2>

For the latest information about Allpairs, please visit our <a href=http://www.cse.nd.edu/~ccl/software/allpairs>web site</a> and subscribe to our <a href=http://www.cse.nd.edu/~ccl/software/help.shtml>mailing list</a>.

</body>
</html>
coop-computing-tools-doc 4.0-1.1 / usr / share / doc / coop-computing-tools / manual / allpairs.html
