[Beowulf] A start in Parallel Programming?

[Robert G. Brown]

On Mon, 19 Mar 2007, Joe Landman wrote:

> The higher levels you work at in abstraction, generally the slower the
> performance of the code.  But then the higher levels of abstraction
> generally map better into our own thought processes.
>
> Here is a great way to do LU decomposition of a matrix in Octave/Matlab:
>
> 	 [l , u , p ] = lu ( a );
>
> This takes matrix a and represents it as a lower triangular, an upper
> triangular, and a permutation matrix.  C.f.
> http://www.delorie.com/gnu/docs/octave/octave_145.html .
>
> While using this is a great way to write out what you want to do at a
> higher (more abstract) level, writing out an LU solver in C (a good one
> that performs well) is quite a bit harder.  And more prone to error than
> using the above.

Unless, of course, you use an excellent numerical library for C like the
GSL, in which case you have a whole range of things you can do:

   http://www.gnu.org/software/gsl/manual/html_node/LU-Decomposition.html

and where this is just the first step of many of them.  Your observation
isn't incorrect, it is just inapropos.  Indeed, if I had to choose to
trust something like incomplete gamma function evaluation in octave or
in the GSL, I'd pick the GSL.  But then, I'm on it's list...

One can abstract any set of chores in C.  Octave and matlab both are
probably written in C and in that case represent just such an
abstraction.  To write new extensions of either one would therefore
require you to program in C in order to create such an abstraction.
Good structured programming is all about creating just the precisely
correct layers of abstraction -- the right "objects", the right
"methods" -- to perfectly structure the procedural core of your code.
Indepedent of language, really -- just as true for C++ or Fortran or
Basic as it is for C.

Honestly, I suspect that there are two or three things the nay-sayers
were thinking about when they described C as "unsafe".  First and
foremost is probably the continued existence of unsafe I/O commands e.g.
gets() which enable buffer overwrite attacks in the hands of the unwary.
Second and intimately connected is likely the use of pointers and still
other commands, e.g. sprintf instead of snprintf which are both security
risks in the hands of the unwary and easy to "break".  Third is probably
C's lack of strong checking for types and sizes (impossible in a
universe where casts on pointers and overlaying memory spaces are
routinely used as forces for good, but that also make it more or less
impossible to prevent a user from overwriting the end of their own
vector.  C considers it to be your data and stack segments, and if you
want to overwrite them, that's your business and it will be presumed
that you know what it is.

The first of these (and half the second) is a valid concern -- yes, one
shouldn't use the "bad" string/char I/O commands any more and NEARLY
everyone knows it at this point but it would be even better if they just
made gets etc just go away and the heck with the fourteen remaining suid
root programs that still use gets() to accept user input.  Sorry guys,
you'll just have to close those security holes and move on.

The latter of the (and half the second) are part of C's great power.
One of my favorite examples involves ODE solvers.  Most canned ODE
solvers require that they be passed a VECTOR of ODEs and initial
conditions to return a VECTOR or new values.  Alas, I tend to solve ODEs
that are e.g. nearest-neighbor coupled on a spatial lattice in 3 (or
more!) dimensions.

There are two ways to solve this problem (for say a cube of side N
sites).  One is to allocate a single linear vector of length N^3 (to
make the ODE happy) and write your ODE derives routine with a whole lot
of Evil pointer arithmetic -- that (i*jmax + j)*kmax + k kind of stuff
so that you can do such transparent code as:

  U = - coup*vec[(i*jmax + j)*kmax + k]*vec[((i+1)*jmax + j+1)*kmax +
k+1 + ...;

which makes me hurt just to look at it but let's you evaluate the
derivatives and integrate with a straight vector solver.

The second way is to pack the offsets of the LINEAR vector vec[] into
a 3d pointer ***site -- one time, with reusable code -- and then
the code becomes

  U = - coup*site[i][j][l]*site[i+1][j+1][k+1] + ... ;

while you can STILL call the ODE solver with the *vec...

So, are pointers a force for good or evil?

Neither.  They are a programming device, a tool, a way of directly
accessing memory in a way that you can clearly visualize and over which
you have near complete control. Used carefully, used well, pointers are
so powerful that I literally cannot imagine programming without them.
They solve many problems "perfectly", and as you can see from the
example above, they can enable "magic" to be done that otherwise
requires the explicit and bug-prone programming of multidimensional
offset arithmetic and obfuscation of a simple arithmetical expression OR
the encapsulation of the linear vector ODE solver in a complex wrapper
that allocates linear scratch memory and copies over the contents of an
actual site[][][] matrix (both ways) to advance the solution each step.

This is just one thing that makes a "dangerous" feature a thing of
immense power that can be used to write surprisingly elegant code.  It's
also precisely the same kind of thing that permits crackers to overwrite
the execution stack of badly written program.

> You make your choices, and you pay the cost of the choices.

Now THIS I totally agree with.  The programmer is ultimately responsible
for the program.  I leave you with a couple of koans from the Tao of
Programming:

                              4.2

A novice asked the master: ``I have a program that sometime runs and
sometimes aborts. I have followed the rules of programming, yet I am
totally baffled. What is the reason for this?''

The master replied: ``You are confused because you do not understand
Tao. Only a fool expects rational behavior from his fellow humans. Why
do you expect it from a machine that humans have constructed? Computers
simulate determinism; only Tao is perfect.

``The rules of programming are transitory; only Tao is eternal.
Therefore you must contemplate Tao before you receive enlightenment.''

``But how will I know when I have received enlightenment?'' asked the
novice.

``Your program will then run correctly,'' replied the master.


                              4.3

A master was explaining the nature of Tao of to one of his novices.
``The Tao is embodied in all software - regardless of how
insignificant,'' said the master.

``Is the Tao in a hand-held calculator?'' asked the novice.

``It is,'' came the reply.

``Is the Tao in a video game?'' continued the novice.

``It is even in a video game,'' said the master.

``And is the Tao in the DOS for a personal computer?''

The master coughed and shifted his position slightly. ``The lesson is
over for today,'' he said.

        rgb

>
> Joe
>
>

-- 
Robert G. Brown	                       http://www.phy.duke.edu/~rgb/
Duke University Dept. of Physics, Box 90305
Durham, N.C. 27708-0305
Phone: 1-919-660-2567  Fax: 919-660-2525     email:rgb at phy.duke.edu