[9fans] parallel/distributed computation

[9fans] parallel/distributed computation

[lejatorn]

Hi all,

As I'm working in a geophysics lab, one of my point of interests
regarding plan9 would be heavy scientific computation, especially
parallel computing. 

So, first is there any fortran compiler on plan9? Second, is there any
support for parallel computing, like mpi (even libs for that in C would
be something)?

Regards,
Mathieu.

-- 
GPG key on subkeys.pgp.net:

KeyID:	| Fingerprint:
683DE5F3 | 4324 5818 39AA 9545 95C6 09AF B0A4 DFEA 683D E5F3
--

Re: [9fans] parallel/distributed computation

[ron minnich]

On 10/17/07, lejatorn@gmail.com <lejatorn@gmail.com> wrote:
> Hi all,
>
> As I'm working in a geophysics lab, one of my point of interests
> regarding plan9 would be heavy scientific computation, especially
> parallel computing.
>
> So, first is there any fortran compiler on plan9? Second, is there any
> support for parallel computing, like mpi (even libs for that in C would
> be something)?

You have two choices.

1) write it from scratch
2) port gcc and then all of gnubin -- and then all of the various
parallel computing software

if you want industrial strength versions of this type of thing, you
won't do (1) better than the  scads of people doing it now (well, your
code will sure look better than openmpi.org, but it won't do mpi
better).

So you might want to start with the gcc port. Not because we want gcc,
mind, but because we need gcc -- because there are way too many bits
that have to be done, and not enough people to do them.

ron

Re: [9fans] parallel/distributed computation

[Eric Van Hensbergen]

On 10/17/07, ron minnich <rminnich@gmail.com> wrote:
>
> You have two choices.
>
> 1) write it from scratch
> 2) port gcc and then all of gnubin -- and then all of the various
> parallel computing software
>

Ron fails to mention that we are also looking at flushing out support
for large-scale HPC applications under Plan 9 -- but that work is just
getting underway and Fortran isn't one of our initial targets
(although some level of MPI API support most likely is).

            -eric

Re: [9fans] parallel/distributed computation

[David Leimbach]

[-- Attachment #1: Type: text/plain, Size: 1204 bytes --]

On 10/17/07, Eric Van Hensbergen <ericvh@gmail.com> wrote:
>
> On 10/17/07, ron minnich <rminnich@gmail.com> wrote:
> >
> > You have two choices.
> >
> > 1) write it from scratch
> > 2) port gcc and then all of gnubin -- and then all of the various
> > parallel computing software
> >
>
> Ron fails to mention that we are also looking at flushing out support
> for large-scale HPC applications under Plan 9 -- but that work is just
> getting underway and Fortran isn't one of our initial targets
> (although some level of MPI API support most likely is).
>
>             -eric
>

Who's "we"?  I've experience implementing MPI against Portals, TCP and funky
shared memory issues on Mac OS X.

Of course for me to do so for Plan 9 would probably violate several
employment non-competes and other IP contracts I have.

Doesn't mean I'm not interested in seeing it happen though.  Plan 9 might be
really ideal for HPC, especially with myrinet drivers available and it's
absolutely no-nonsense VM subsystem.  (yeah you can exhaust RAM, but all
that paging/swapping was never good for HPC anyway now was it?  I'm thinking
CPlant...  Ron (Minnich) might laugh at me... :-)

Dave

[-- Attachment #2: Type: text/html, Size: 1824 bytes --]

Re: [9fans] parallel/distributed computation

[ron minnich]

On 10/17/07, David Leimbach <leimy2k@gmail.com> wrote:
>
> Who's "we"?  I've experience implementing MPI against Portals, TCP and funky
> shared memory issues on Mac OS X.

"we" is jim, charles, eric, and me. I'm porting some of the HPCS apps
to Plan 9. After thinking hard about an "MPI lite" approach, I'm
taking the "write these apps as though it were NOT 1970" approach.

In particular, if you have
1) threads
2) sizeof
3) function pointers (and prototypes, now, there's a concept)
4) a functioning type system

There's a lot of MPI you (well, I) don't need. Seen in retrospective,
MPI is really a bandaid for the failings of the CM-5 and T3D runtime
systems. The application to clusters was actually an afterthought.

> Of course for me to do so for Plan 9 would probably violate several
> employment non-competes and other IP contracts I have.

Ah, c'mon David, it's just a few years in a pound-me-in-the-ass
federal prison. They might even allow conjugal visits.

ron

Re: [9fans] parallel/distributed computation

[Randolph Fritz]

On 2007-10-17, Eric Van Hensbergen <ericvh@gmail.com> wrote:
> On 10/17/07, ron minnich <rminnich@gmail.com> wrote:
>>
>> You have two choices.
>>
>> 1) write it from scratch
>> 2) port gcc and then all of gnubin -- and then all of the various
>> parallel computing software
>>
>
> Ron fails to mention that we are also looking at flushing out support
> for large-scale HPC applications under Plan 9 -- but that work is just
> getting underway and Fortran isn't one of our initial targets
> (although some level of MPI API support most likely is).
>

And you fail to mention...unless you've moved...that you're at IBM
Austin, working with Blue Gene.

Randolph

Re: [9fans] parallel/distributed computation

[Richard Miller]

[-- Attachment #1: Type: text/plain, Size: 606 bytes --]

Ron says:

> There's a lot of MPI you (well, I) don't need.

I would say you need almost none of it.  Around 1993 as part of my PhD
project I designed a parallel computing library based on the BSP model
with exactly six primitives (of which two are housekeeping and one
more is arguably redundant) - see attached man page.  The simplicity
meant that it could be implemented quickly and efficiently on a range
of platforms from workstation clusters to the Cray T3D, and users
found it easy to use and understand.

Sadly BSP was too unconventional (too simple?) to become popular.

-- Richard

[-- Attachment #2.1: Type: text/plain, Size: 311 bytes --]

from postmaster@vt310:
The following attachment had content that we can't
prove to be harmless.  To avoid possible automatic
execution, we changed the content headers.
The original header was:

	Content-Type: text/troff
	Content-Disposition: attachment; filename=bsp.3
	Content-Transfer-Encoding: base64

[-- Attachment #2.2: bsp.3.suspect --]
[-- Type: application/octet-stream, Size: 8535 bytes --]

.TH bsp 3BSP "Version 1.1" "Oxford BSP Library"
.SH NAME
bsp_start, bsp_finish, bsp_sstep, bsp_sstep_end, bsp_fetch, bsp_store \(em
Oxford BSP library primitives
.SH FORTRAN SYNOPSIS
.nf
.B subroutine bsp_start (maxprocs, nprocs, mypid)
.B integer maxprocs, nprocs, mypid
.LP
.B subroutine bsp_finish
.LP
.nf
.B subroutine bsp_sstep (stepid)
.B integer stepid
.LP
.nf
.B subroutine bsp_sstep_end (stepid)
.B integer stepid
.LP
.nf
.B subroutine bsp_fetch (pid, src, dst, nbytes)
.B integer pid, nbytes
.IB anytype " src, dst"
.LP
.nf
.B subroutine bsp_store (pid, src, dst, nbytes)
.B integer pid, nbytes
.IB anytype " src, dst"
.SH C SYNOPSIS
.nf
.B bspstart (argc, argv, maxprocs, nprocs, mypid)
.B char **argv;
.B int *nprocs, *mypid;
.LP
.B bspfinish (\|)
.LP
.nf
.B bspsstep (stepid)
.B int stepid;
.LP
.nf
.B bspsstep_end (stepid)
.B int stepid;
.LP
.nf
.B bspfetch (pid, src, dst, nbytes)
.B int pid, nbytes;
.B void *src, *dst;
.LP
.nf
.B bspstore (pid, src, dst, nbytes)
.B int pid, nbytes;
.B void *src, *dst;
.SH DESCRIPTION
The Oxford BSP library provides a
concise set of basic operations
for architecture-independent parallel programming
according to the
.B bulk-synchronous parallel
model of computation.
There are implementations of the library for
distributed-memory multicomputers,
shared-memory multiprocessors,
and networked workstation clusters,
using
a variety of parallel software platforms
to provide the underlying communication and
synchronisation.
All versions present the
same set of primitives to the application program,
with identical syntax and semantics.
.SS Process management
.TP 10
.BI "bsp_start (" "maxprocs, nprocs, mypid" )
initiates the parallel execution of multiple copies
of the calling program, on separate processors if possible.
The call to
.B bsp_start
must be the first executable statement of the program.
.TP
.B bsp_finish (\|)
must be called at the end of the program.
When every process has called
.BR bsp_finish ,
parallel resources are released and the entire program exits.
.TP 10
.I maxprocs
the maximum number of parallel processes to run.
.I maxprocs = 0
requests all available processors.
.TP
.I nprocs
returns the number of parallel processes actually started,
including the original caller.
The degree of parallelism may be specified by the user when
starting the program, or in a prior `configuration' step;
see
.BR bsp (1)
for details on each parallel architecture.
Programs should be designed to work correctly for any value of
.IR "nprocs " "between " "1 " "and " maxprocs .
.TP
.I mypid
returns in each process the
.B process identifier
of that process, which
is an integer between
.IR "0 " "and " "nprocs\-1" .
Process
.I 0
is the only
process which can read from standard input,
and may be the only one which has
access to program arguments and environment variables.
.TP
.I argc
(C interface only) the number of arguments passed to
.B main(\|)
.TP
.I argv
(C interface only) the list of arguments passed to
.B main(\|)
.LP
An Oxford BSP program is in SPMD (single program, multiple data)
form:
all processes execute the same program text,
but each has its own independent copy of all variables.
The master-slave programming style can also be accommodated, by
performing `master' operations only in process \fI0\fP;
generally process \fI0\fP can act as a slave as well,
unless it has useful work to do while the slave computation is proceeding.

The memory model is `direct' BSP, requiring the data to be explicitly
partitioned and distributed.
There is no global shared data,
but a process can make explicit requests to read and write
the local data of another process.
.SS Bulk synchronisation
.TP 10
.BI "bsp_sstep (" stepid )
marks the beginning of a
.B superstep
\(em a phase of the parallel program during which
each process can perform a series of computation steps on
local data, and request the asynchronous reading or writing of
non-local data to be used in a later superstep.
.TP
.BI "bsp_sstep_end (" stepid )
marks the end of a superstep.
There is an implicit global barrier synchronisation,
in which processes are delayed until every process has
reached the end of the superstep and all asynchronous data accesses
have completed.
.TP 10
.I stepid
an integer label which
serves to identify supersteps
in the program for profiling, consistency checking and error reporting.
The
.BR bsp_sstep " and " bsp_sstep_end"
delimiting one
superstep must have the same
label,
which should be different from any other superstep
in the program text,
but the choice of step numbering is otherwise arbitrary.
.LP
Execution on all processors must proceed through all the
supersteps in the same order.
This implies that if a superstep is written inside a loop or
.B if
statement, the loop control variable or conditional
expression must have the same value in all processors.
Within a superstep, each processor may perform different computations,
follow different control paths, and even call different subroutines,
but every processor must have reached the end of the current superstep
before any one can proceed to the next.
.LP
The present version of the library does not allow supersteps to be nested,
or to synchronise only a subset of processes.
.SS Remote data access
.TP 10
.BI "bsp_fetch (" "pid, src, dst, nbytes" )
requests an asynchronous transfer of data from another process.
The caller may not examine the
data until after the next
.BR bsp_sstep_end ,
because it is not certain to arrive before the barrier synchronisation.
.TP 10
.BI "bsp_store (" "pid, src, dst, nbytes" )
requests an asynchronous transfer of data to another process.
The remote process may not examine the
data until after the next
.BR bsp_sstep_end .
But the calling process is permitted to modify its local
copy as soon as the
.B bsp_store
returns,
so that it is possible to reuse one buffer variable as the source
for multiple stores in the same superstep.
.TP 10
.I pid
process identifier of the remote process
.TP
.I src
data source location in the remote process (fetch)
or the calling process (store)
.TP
.I dst
data destination location in the calling process (fetch)
or the remote process (store)
.TP
.I nbytes
length in bytes of the data to be transferred
.LP
In \s-1FORTRAN\s+1,
.IR "src " "and " dst
may be variables, array names, or indexed array expressions;
and
.I src
may also be an expression yielding a value of size
.IR nbytes .
In C,
.IR "src " "and " dst
are pointers to any type.
.LP
Note that
.BR bsp_fetch " and " bsp_store
are not message-passing primitives, although on
some machines they will be implemented by
means of messages.
Semantically they are remote assignment operations,
which may be performed on some shared-memory machines
as a direct transfer of data from address space to another,
with no need for extra buffering or per-message synchronisation.
.LP
The present version of the library permits non-local data access
only to objects which are statically allocated.
That is, the source of a fetch or the destination of a store must be a
.BR "static " "or " "extern "
variable in C,
a local or
.B common
variable in \s-1FORTRAN\s+1.
.SS Consistency rules
To avoid the nondeterminism caused by concurrent access to shared data,
there are logical restrictions on the use of the
remote assignment primitives.
.IP \(bu 3
The destination data object of a
.BR bsp_fetch " or " bsp_store
may not be examined or modified by any process during the
same superstep \(em that is, it may not be the
source or destination of any other
.BR bsp_fetch " or " bsp_store
or appear in a local expression or assignment.
.IP \(bu
A data object which is modified locally by a process
(by an assignment or input statement)
may not be fetched by any other process in the same superstep.
.LP
.SH FILES
.IR $BSP /lib/ $ARCH /libbsp_ $MEDIUM .a
.br
where
.RS 3
.TP 10
$BSP
directory where the Oxford BSP library is installed
(possibly
.BR /usr/local/bsp \)
.TP
$ARCH
architecture of parallel machine
.TP
$MEDIUM
underlying communications medium
.RE
.SH AUTHOR
Richard Miller <miller@comlab.ox.ac.uk>
.br
Oxford University Computing Laboratory
.SH SEE ALSO
.na
.BR bsp "(1), " bspf77 "(1), " bspcc "(1), " bspprof "(1), "
.BR bsp_time "(3), " bsp_broadcast "(3), " bsp_reduce (3)
.br
.LP
.I "A bridging model for parallel computation,"
L.G. Valiant, CACM 33(8): 103\-111, 1990.
.br
.I "The Oxford BSP Library Users' Guide,"
R. Miller and J. Reed,
Oxford University Computing Laboratory
.SH COPYRIGHT
The Oxford BSP library Version 1.1 is Copyright \(co 1994 by Richard Miller

Re: [9fans] parallel/distributed computation

[roger peppe]

>          src       data source location in the remote process (fetch)
>                   or the calling process (store)

it looks to me like it wouldn't work across different architectures.
is that a correct reading? maybe this is a usual restriction in
this kind of library?

Re: [9fans] parallel/distributed computation

[Richard Miller]

> it looks to me like it wouldn't work across different architectures.
> is that a correct reading? maybe this is a usual restriction in
> this kind of library?

Quite right - homogeneous architectures only.  Attempting to cope
with heterogeneity accounts for some of the complexity (and inefficiency)
of some other libraries.  I would guess that any decently scalable
parallel machine will be single-architecture (but I haven't surveyed
the field lately).

Re: [9fans] parallel/distributed computation

[anyrhine]

Richard Miller wrote:
>> it looks to me like it wouldn't work across different architectures.
>> is that a correct reading? maybe this is a usual restriction in
>> this kind of library?
> 
> Quite right - homogeneous architectures only.  Attempting to cope
> with heterogeneity accounts for some of the complexity (and inefficiency)
> of some other libraries.  I would guess that any decently scalable
> parallel machine will be single-architecture (but I haven't surveyed
> the field lately).

the roadrunner.

i don't know if it's decently scalable though :)

Re: [9fans] parallel/distributed computation

[ron minnich]

BSP is not really sufficient for scaling or building all applications.
It's a great hammer, but not all the apps are nails.

ron

Re: [9fans] parallel/distributed computation

[erik quanstrom]

> BSP is not really sufficient for scaling or building all applications.
> It's a great hammer, but not all the apps are nails.
> 
> ron

could you elaborate or give a pointer explaining why
bsp is insufficient?

- erik

Re: [9fans] parallel/distributed computation

[ron minnich]

On 10/26/07, erik quanstrom <quanstro@quanstro.net> wrote:

> could you elaborate or give a pointer explaining why
> bsp is insufficient?

BSP is essentially all about "the inner loop". In this loop, you do
the work, and, at the bottom of the loop, you tell everyone what you
have done.

So you are either computing or communicating. Which means, on your
$100M computer, that you are using about $50M of it over time. Which
is undesirable.

Nowadays, people work fairly hard to ensure that while computation is
happening, the network is busy moving data.

This problem with BSP is well known, which is why some folks have
tried to time-share the nodes in the following
way(www.ccs3.lanl.gov/pal/publications/papers/petrini01:feng.pdf):
have N jobs (N usually 2). While N-1 jobs are using the network, and
hence not computing, have 1 job computing. Of course, matching this
all up is hard, and most compute  jobs typically are sized to use all
of memory, so this approach has not been used much. The nodes on the
big machines are typically not shared between jobs.

BSP was an interesting idea but is not commonly used any more, at
least on the systems I know about. Rather, people work hard to overlap
communication and computation.

ron
p.s. for more recent work see: www.cs.unm.edu/~fastos/06meeting/sft.pdf

Re: [9fans] parallel/distributed computation

[erik quanstrom]

thanks.

- erik

> BSP is essentially all about "the inner loop". In this loop, you do
> the work, and, at the bottom of the loop, you tell everyone what you
> have done.
> 
> So you are either computing or communicating. Which means, on your
> $100M computer, that you are using about $50M of it over time. Which
> is undesirable.
> 
> Nowadays, people work fairly hard to ensure that while computation is
> happening, the network is busy moving data.
> 
> This problem with BSP is well known, which is why some folks have
> tried to time-share the nodes in the following
> way(www.ccs3.lanl.gov/pal/publications/papers/petrini01:feng.pdf):
> have N jobs (N usually 2). While N-1 jobs are using the network, and
> hence not computing, have 1 job computing. Of course, matching this
> all up is hard, and most compute  jobs typically are sized to use all
> of memory, so this approach has not been used much. The nodes on the
> big machines are typically not shared between jobs.
> 
> BSP was an interesting idea but is not commonly used any more, at
> least on the systems I know about. Rather, people work hard to overlap
> communication and computation.
> 
> ron
> p.s. for more recent work see: www.cs.unm.edu/~fastos/06meeting/sft.pdf

Re: [9fans] parallel/distributed computation

[Richard Miller]

> BSP is essentially all about "the inner loop". In this loop, you do
> the work, and, at the bottom of the loop, you tell everyone what you
> have done.
> 
> So you are either computing or communicating.

Not quite accurate.  In BSP, communication is separated from
synchronisation.  During the loop (BSP calls it a "superstep"), each
process does a mixture of computation and asynchronous communication,
in any order.  The computation is only allowed to use data which was
local to that process at the beginning of the superstep.  At the end
of the superstep, there's a global barrier synchronisation.  After the
synchronisation, processes can use the new values which which were
communicated during the previous superstep.  During a superstep,
therefore, computation and communication can and should be overlapped
as much as the algorithm and platform allow.  It's only the barrier
synch at the end which needs to be atomic.

> ... Which means, on your
> $100M computer, that you are using about $50M of it over time. Which
> is undesirable.

In the worst case of exactly equal amounts of computation and
communication, the cost of having no overlap at all would be a
constant factor of 2, but this does not limit scalability.  (Academic
computer scientists don't care about constant factors, except perhaps
in their research grants ...)

> This problem with BSP is well known, which is why some folks have
> tried to time-share the nodes

Mapping multiple virtual processors onto each physical processor to
increase overlap and hide latency was always part of the BSP model.
Valiant's original CACM paper called it "parallel slackness".

Ron is right to say BSP doesn't fit all problems.  I think it's worst
with loosely structured or adaptive algorithms where it's hard to
predict in advance how much work each process will do in a superstep;
then the global synch can be too restrictive.

But where it does fit, the simplicity of the approach gives the usual
benefits of minimalism.  Hence not completely off topic for this list,
I hope.

-- Richard