[gambit-list] Cosmic convergence
Bradley Lucier
lucier at math.purdue.edu
Sat Jan 14 16:24:01 EST 2006
With the purchase of my 8-core, shared-memory, SMP Opteron machine
and Marc's possible interest (see http://mailman.iro.umontreal.ca/
pipermail/gambit-list/2006-January/000560.html) in extending Gambit's
runtime to support SMP, three threads of thought (obsessions?) have
converged. It would seem to be difficult to develop any one of them
without the other two, and one of them involves Gambit development
directly, so please forgive the limited relevance of this message to
this list.
1. My current image processing research.
I'm not going to explain the details here, except to say that the
problems are highly parallelizable, involves minimizing functions
over high-dimensional spaces (say, 40 dimensions), and evaluating
the function to be minimized can take a few minutes on a single
Opteron core. We don't yet know a provably correct algorithm for the
solution of the problem, so we're doing exploratory calculations, and
we're still at the "get the right answer, see if that answer's
interesting, and if so, see if we can speed up the algorithm to make
it practical" stage. Each test calculation takes hours to days to
complete. SMP would speed up the process tremendously.
2. SMP in Gambit.
'Nuff said.
3. A new framework for array processing, with applications to image
processing.
People who develop new algorithms for image processing often start in
Matlab because it can be interactive, it operates on entire matrices
at a time, and it has a lot of built-in functions. The latter part
is the killer app aspect of Matlab---if Matlab has the functions you
want built in, then you're golden, the code runs fast, it's easy to
program, etc.
If, however, you're developing new algorithms, rather than just
trying to use a known algorithm, it's possible, or even likely, that
Matlab won't have the built-in functions you need. Then you're
reduced to "writing Fortran/C code in Matlab", writing loops that
operate on one number/pixel/voxel/... at a time. Then you find out
that, not only is it difficult to write code in this style, Matlab is
incredibly slow executing code like that. So then the graduate
student rewrites the code in C, which is even more difficult, but now
it runs quickly, but it's nearly impossible to debug or change. (And
it's usually the graduate student going this route, because they
won't believe from the beginning that Matlab won't cut it, and then
they think that the only way to get the code to run in 20 seconds
instead of two hours is to write it in C.)
So, I want to fix this problem. My goal is a framework in Scheme for
developing new algorithms in array/image processing that has the
following properties:
A. The speed of programs developed with this framework are
within an order of magnitude of the speed of similar programs written
in C.
B. It's at least as easy to develop new algorithms in this
framework as it is to work in Matlab when Matlab's built-in functions
suffice.
I've been writing all my image processing algorithms in this evolving
framework for at least five years now. In functional programming
terms, the basic operations are various flavors of map, reduce,
curry, and, when you're really in a pickle, for-each, on multi-
dimensional arrays containing heterogeneous or homogeneous data
types. (You use curry when you want to slice and dice multi-
dimensional images in various ways, e.g., to view a three-dimensional
image of a body in a different image plane than the one in which the
body was scanned originally.) I'm working on an SRFI submission.
Now here's the convergence. Some people at Google just made a big
deal about their map-reduce algorithms that they use to process
multiple gigabytes of data over thousands of processors. To have
this work, they need two things, which can be explained in SRFI-1
terms: first, in
(map f l1 l2 ...)
then it can't matter in what order f is applied to the elements of
the lists, and, in fact, f has to be "thread safe", any parallel
executions of f applied to the elements of the list must give the
same answer, and second, in
(reduce op id l)
the same must be true of op, and op must be associative. (The
property needed for "map" is more restrictive than the R5RS property
for argument evaluation, which is that R5RS is allowed to assume that
the arguments to a function end up with the same value no matter in
what order they are computed, but they must be computed sequentially
in some order, no parallelism, no threads, etc.) So you realize that
if you want to parallelize multi-dimensional array versions of these
functions, you need the same properties.
On the other hand, an array for-each, say,
(array-for-each f a1 a2 a3 ...)
must apply f in some fixed order, and sequentially. And you realize
that either you supply versions of array-map and array-reduce that
have the same property, or you expect that the times that array-map
and array-reduce need these properties are so few and far between
that you leave it to the users to cobble together what they need from
array-for-each. (The only time I've needed this property so far is
to read and write image files.)
So, there we go.
Without an SMP version of Gambit, I couldn't develop and test our new
parallel image processing framework and speed up executing our new
algorithms by a factor of 8 or so.
Without our image processing research applications, I wouldn't have
anything with which to test SMP Gambit or my new array-processing
framework.
And without the new image-processing framework, I doubt that I could
easily develop fast, SMP-capable, image-processing algorithms for my
research.
So, yes, "We want our SMP!"
Brad
More information about the Gambit-list
mailing list