coop-computing-tools-doc 4.0-1.1 / usr / share / doc / coop-computing-tools / manual / wavefront.html

This file is indexed.

/usr/share/doc/coop-computing-tools/manual/wavefront.html is in coop-computing-tools-doc 4.0-1.1.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below. 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
<html>
<head>
<title>Wavefront 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>Wavefront User's Manual</h1>
<b>Last Updated June 2013</b>
<p>
Wavefront is Copyright (C) 2010 The University of Notre Dame.
This software is distributed under the GNU General Public License.
See the file COPYING for details.
<p>

<table>
<tr>
	<td valign=middle>
		<a href=wavefront_large.gif><img src=images/wavefront_small.gif align=right border=0></a>
	</td>
	<td valign=middle>
		<div id=abstraction>
Wavefront( array R[x,0], array R[0,y], function F(x,y,d) )<br>
returns matrix R where<br>
R[i,j] = F( R[i-1,j], R[i,j-1], R[i-1,j-1] )<br>
		</div>
	</td>
</tr>
</table>

The Wavefront abstraction computes a two dimensional recurrence relation.
You provide a function F that accepts the left (x), right (y), and diagonal (d).
The abstraction then runs each of the functions in the order of dependency,
handling load balancing, data movement, fault tolerance, and so on.
<p> To use Wavefront, install the <a
    href=/~ccl/software/downloadfiles.shtml>Cooperative Computing Tools</a> and
run the program named <tt><b>wavefront_master</b></tt>. You need to set up an
input file with initial boundary values of R, and provide a function that
computes a new cell from adjacent cells. Each line of the input file has the format:

<pre>
row column arg1,arg2,...
</pre>

In which row and column describe the position of a cell, with zero-based
indices, and arg1,arg2,... is the list of arguments fed to F (that is, each
R[i,j] is actually a tuple). 


To run wavefront, specifying the program that computes each cell, and the
number of cells in each dimension, for example:

<pre>
wavefront_master ./func.exe 10 10 input.data output.data
</pre>

in which input.data is the file with the initial boundary conditions,
and output.data are the results computed for a 10x10 matrix.

The program <tt>func.exe</tt> may be written in any language that you like.
For each cell of the result, the program will be invoked like this:

<pre>
./func.exe x y x-file y-file d-file
</pre>

in which each of <tt>x-file</tt>, <tt>y-file</tt> and <tt>d-file</tt> are files
that contain the data from
the x, y, and diagonal neighbors, in the format:

<pre>
arg1,arg2,...
</pre>

These files are generated automatically by <tt>wavefront_master</tt>. Your
function is required to parse them, and to print the result of the current cell
to <tt>stdout</tt>, in the format:

<pre>
arg1,arg2,...
</pre>

<tt>wavefront_master</tt> is a Work Queue application, thus it does not perform
any work by itself, but it relies on workers connecting to it. To launch a
single worker:

<pre>
work_queue_worker mymachine.somewhere.edu 9123
</pre>

in which 9123 is the default port for Work Queue applications. Work Queue
provides convenient alternatives to launch many workers simultaneously for
different batch systems (e.g. condor), which are explained in the section <b>
    Project names </b> in the <a href=workqueue.html> Work Queue manual </a>. 

Wavefront will check for a few error conditions, and then start to run,
showing progress on the console like this:

<pre>
# elapsed time : waiting jobs / running jobs / complete jobs (percent complete)
0 : 0 / 1 / 0 (%0.00)
5 : 0 / 2 / 1 (%1.23)
10 : 0 / 3 / 3 (%3.70)
16 : 0 / 4 / 6 (%7.41)
21 : 0 / 4 / 8 (%9.88)
...
</pre>

When complete, your outputs will be stored in the output file specified, with the same format as for the input data.

Here is a graph of a 100 by 100 problem run on a 64-core machine, where each F takes about five seconds to execute:
<p>
<img src=images/wavefront_progress.gif>
<p>
The <b>-B</b> option will write a bitmap progress image every second.
Each pixel represents the state of one cell in the matrix: green indicates complete, blue currently running, yellow ready to run, and red not ready.  Here is an example of the progress of a small ten by ten job using five CPUs:
<p>

<table>
<tr>
<td><img src=images/wavefront_progress1.gif>
<td><img src=images/wavefront_progress2.gif>
<td><img src=images/wavefront_progress4.gif>
<td><img src=images/wavefront_progress5.gif>
</table>

Note that at the broadest part of the workload, there are not enough CPUs to run all cells at once, so some must wait.  Also note that the wave does not need to run synchronously: cells may begin to compute as soon as their dependencies are satisfied.

<h2>For More Information</h2>

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

APT Browse - Built by Thomas Orozco.