Re: [9fans] parallel/distributed computation

[Richard Miller <9fans@hamnavoe.com>]

[-- 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