This file is a concatenation (for Netlib purposes) of three
"documentation" files:
README
interface.doc
makefile
They should be split up after receipt at the places marked by lines
of the form
# SPLIT HERE FILENAME = <filename> #
The Netlib version of DOMINO contains this documentation file, a
source code file (in the language C), and files containing various
versions of conoface, an assembly language interface.
# SPLIT HERE FILENAME = README #
This directory contains the routines of the DOMINO system
as described in:
TR-1648 April, 1986
DOMINO
A Message Passing Environment
for
Parallel Computation
by
D. P. O'Leary
G. W. Stewart
R. A. van de Geijn
University of Maryland
Department of Computer Science
College Park, MD 20742
DOMINO is a set of C-language routines with a short assembly language
interface that allows multiple tasks to communicate and schedules
local tasks for execution. These tasks may be on a single processor
or spread among multiple processors connected by a message-passing
network.
Although the authors and others at the University of Maryland
have used DOMINO in a variety of applications, this release is
preliminary. We would appreciate hearing about any bugs in the
system, as well as your comments and suggestions. We can be
reached through ARPANET or NANET at the following addresses.
oleary@mimsy.umd.edu
na.oleary@su-score.arpa
stewart@mimsy.umd.edu
na.pstewart@su-score.arpa
rvdg@mimsy.umd.edu
Once you get things sorted out, you will find that DOMINO is a
rather simple system that can be easily modified for special
purposes. We encourage such tinkering (remember to let us know
about your good ideas), but to prevent the proliferation of
incompatible DOMINO's, please document and date your changes in
the preamble of each program.
The files in this directory can be split into several groups:
GROUP A: (portable)
accept.c killnodes.c ready.c
addq.c listp.c removeq.c
cleanup.c main.c request.c
cmcheck.c makeid.c schedule.c
conmes.c makenode.c sendn.c
control.c makeutnd.c sendp.c
data.c match.c sendrn.c
domdefs.c passn.c startup.c
freelist.c queuep.c sweep.c
(These files have been collapsed into dominoport.c)
domdec.h domparam.h domstruct.h
GROUP B: (machine dependent)
boot.c error.c nextproc.c
(The last two have been collapsed into domdefault.c)
GROUP C: (documentation)
INDEX README domino.doc
GROUP D:
conofacepc.s conofacevcc.s conofacevv.s
conofaces.s conofacevu.s spproface.c
GROUP E:
brig.boot.c brig.go.c brig.node.c
(These files have been collapsed into brigade.c
GROUP F:
makefile
Group A consists of the routines which are fully portable and
which should be part of any DOMINO version. The only changes
that might need to be made is in the values of certain contants
in domparam.h (e.g. NTSIZE, STORSIZE, MAXNAME.)
Group B consists of machine dependent routines. nextproc
depends on the physical connections between the processors of
a parallel machine. error depends on how errors can be handled
by the machine and/or processor. boot may depend on machine
and/or user application.
Group C consists of documentation on the system dependent
interfaces: CONOFACE and PROFACE as well as some pointers on
how to alter DOMINO so that nodeprograms can be written in
FORTRAN.
Group D consists of a file that contains the PROFACE routines
for the case when DOMINO is implemented on a single processor
as well as several versions of CONOFACE:
conofacepc.s: 8086/8088 series Lattice C compiler
conofaces.s: Sun-2 UNIX cc compiler
conofacevcc.s: Z80 processor Vandata vcc C cross
compiler
conofacevu.s: VAX UNIX cc compiler
conofacevv.s: VAX VMS cc compiler
Group E consists of files that contain the brigade example
from the DOMINO manual.
GROUP F consists of a sample makefile for unix users.
INSTALLING DOMINO:
1. If necessary, write proface, conoface as well as boot, error
and nextproc. Otherwise pick the appropriate files from
GROUP B and D.
2. Compile (and create a library from) the object files of GROUP A
and step 1.
Note 1: ON A SINGLE PROCESSOR proface is given by spproface.c,
and group B should not have to be rewritten.
Note 2: The user might want to separate dominoport.c into
separate files. The comments indicate the suggested
name of the file. The routines are separated by
/* %$%$ etc %$%$ */
and /* ... */ has to be edited out from around
"#include" statements.
RUNNING AN APPLICATION
1. Write user application.
2. Link user application with library.
3. Run
MAKEFILE
If the hostmachine runs the UNIX operating system,
it is strongly recommended that the user use a makefile.
The file "makefile" is a sample makefile for the bucket
brigade example.
A QUICK TEST
1. UNIX users: rename the proper conoface file conoface.s
type: make brigade
This should link brigade.c with the DOMINO routines and create
an executable file "brigade".
2. non-UNIX users: compile and link brigade.c with dominoport.c,
domdefault.c, spproface.c and the proper conoface
file and run the result.
Note: Depending on how the user programs are written, it is quite
possible for DOMINO to finish in an infinite loop. (The system
does not itself check if all nodes are detached.) This happens
in the case of the brigade example.
# SPLIT HERE FILENAME = interface.doc #
This file contains notes on how to create one's own conoface
and/or proface. It also includes notes on using fortran
subroutines as node programs in the Unix Vax version of
Domino.
1. CONOFACE
CONOFACE (for COntrol NOde interFACE) consists of the routines
awaken, pause, finis and invoke. These routines allow processor
control to be transferred freely from the control routine to a
node program and back, even if many nodes share the same copy of
a nodeprogram. All C compilers we know of use a program stack to
pass parameters to subroutines and to create space for local
variables. DOMINO allocates a stack to each node on a processor,
and the main task performed by conoface is to manipulate stack
pointers. The following descriptions are rough outlines of how
the routines might be programmed.
awaken(ndp)
struct node *ndp;
awaken is the routine called by control which awakens the node
pointed to by ndp. It makes the Stack Pointer (SP) point to
the proper place in the Node Stack, allowing the environment
(local variables, regs etc.) to be saved while the node is not
awake. Depending on the status of the node, different action
needs to be taken:
status==READY : nodeprogram is to be entered from top.
set status = ACTIVE
set initial = TRUE
save Stack Pointer (SP)
set SP = ndp->stackbot
call (*ndp->program)(ndp, &initial)
status==ACTIVE : nodeprogram last exited using pause.
set initial = FALSE
restore SP, regs etc. to exactly as it was when pause was
called by the node program.
return as if from pause
if a return from (*ndp->program)() occurs (meaning it exited
using return instead of pause or finis), the following action
is to be taken:
set status = READY
set ndp->stacktop = ndp->stackbot
return from awaken, making sure the stack is restored
properly.
pause()
pause is the function which returns control to the operating
system. Upon return from pause any pending requests have been
fulfilled. The pause routine saves the current environment on
the node stack, sets stacktop of node equal to the top of this
stack and returns control to the operating system as if awaken
returned.
finis()
finis is the function which indicates the node is finished
will all computation. It sets stacktop of the node equal to
stackbot, sets status equal to DETACHED and returns control to
the operating system as if last awaken returned.
invoke(funct, arg1, ..., argn)
invoke has the same effect as
funct( arg1, ..., argn),
except that the system stack is used for local storage instead
of the node stack. This is an optional routine, not implemented
in all versions of CONOFACE.
2. PROFACE
This section contains brief descriptions of the subroutines that
make up PROFACE, the PROcessor interFACE.
FLAGS USED:
int accreq; This flag signals that the accept routine
is needed for an internal communication.
int retwbd; This flag signals that inbound messages
should be blocked as soon as possible.
inb_handler()
This routine should be called whenever items arrive from other
processors. When called, it acts as follows:
1. inb_handler feeds messages to accept one (integer size)
item at a time by calling accept(item).
2. once accept has been called with the first item of a
message, it can only be called with items from the same
message, until it returns DONE.
3. whenever accept returns DONE, two flags, accreq (for accept
requested) and retwbd (for return with buffer disabled)
become important:
if accreq==TRUE: the accept routine is needed for an
internal communication. Do not call accept with any
incoming items until inon(TRUE) (see description below)
is called (by sendn.) The easiest way of accomplishing
this is by blocking all items from other processors from
arriving, which in turn should prevent inb_handler from
being called, and hence no calls to accept with items
from other processors will occur. Once inon is called,
accept can be called with any incoming item.
if retwbd==TRUE: the sendp routine is trying to send in
"burst mode". Ideally all calls to inb_handler and
accept should be suspended until the message has been
completely sent. This can be accomplished by blocking
all incoming items from arriving. To avoid dead-lock,
incoming items should only be blocked if no message item
generated by a sendp on another processor has already
arrived. Once sendp has completed the burst of
communication, incoming items should be allowed to
arrive, and accept can be called with any such item.
if both retwbd and accreq are FALSE, accept can be called with
items from a new message.
accburst(mes, n, item)
int **mes, *n, item;
accburst is called by accept whenever the current message
accept is processing was generated by a sendp on another
processor. Its purpose is to bring in the message data as
quickly as possible (in "burst mode"). *n items (of which
item is the first) are expected to arrive, and are to be put
in memory pointed to by *mes. It should perform the following
functions:
1. put item in memory pointed to by *mes.
2. increase *mes and decrease *n.
3. if the processor is not currently sending to another
processor (as indicated by the sending flag) and *n>0
suspend all other processes on the processor and poll for
the reset of the items of the message data.
upon return *mes and *n have been updated to reflect how many
items of the message data still need to be brought in.
transmit(proc, n, mes)
int proc, n, *mes;
transmit sends n items starting at memory address mes to
processor proc. To avoid dead-lock the convention is adopted
that when transmit returns, the items it sent must arrived at
the destination processor. (Dead-lock may occur if transmit
returns from sending the first item of a message generated by
sendp without it actually arriving at its destination. If the
receiving processor is also attempting a sendp, both processor
may switch to burst mode at the same time.)
int inoff()
inoff blocks incoming items from arriving and hence keeps
inb_handler from being called. It is used to create critical
sections. It returns FALSE or TRUE, depending on whether or
not incoming items were already blocked.
inon(flag)
int flag;
if flag==TRUE, inon unblocks incoming items from arriving, and
allows inb_handler to be called, which in turn can call
accept. If flag==FALSE, no action is taken.
infree()
infree is called by sendn whenever it needs to use accept for
an internal communication. If accept is not currently being
used for an incoming message (indicated by itemno==0) it
blocks incoming items and returns. Otherwise it sets accreq,
and waits until the incoming message has been consumed, after
which it resets accreq and returns.
reqinblock()
reqinblock is called by sendp in order to signal that it would
like to send in "burst mode" as soon as convenient (see also
inb_handler.) It sets the retwbd flag. If burst mode can be
started immediately (see inb_handler for specification of this
condition), it will block all incoming items and return.
Otherwise eventually the inb_handler may block incoming items
if a burst mode can be started later.
freeinblock()
freeinblock is the opposite of reqinblock. It is called by
sendp to indicate burst mode is nolonger needed. It resets
retwbd and unblocks incoming items.
prostart()
prostart is called by the startup routine and allows PROFACE
to initialize itself. It also needs to set the global
variable selfaddr to the processor address (either the
physical address, or a relative address which is an index into
a table which contains the physical addresses.) prostart
returns with incoming items blocked.
Below we give a sample PROFACE for an imaginary parallel proces-
sor with the following specifications. Those familiar with ZMOB,
an experimental parallel processor at the University of Maryland,
will recognize it as a simplified version of that machine.
Each processor has a mailbox into which other processors
can deposit messages one item at a time. The mailbox will
be blocked automatically the moment an item arrives from
another processor (we will assume no conflict can occur).
Variables inb_item and source will contain the contents of
the item and its source processor address respectively.
procaddr contains the physical address of the processor
itself. The following primitives are used for handling the
mailboxes:
block():
block mailbox from accepting any incoming items.
unblock():
allow incoming items to arrive in mailbox.
set_excl(proc):
allow only items from processor proc to arrive once
the mailbox is unblocked.
reset_excl():
allow items from any processor to arrive once the
mailbox is unblocked.
einbint():
enable inbound interrupt once mailbox is unblocked.
The moment an item arrives in the mailbox control is
transferred to the inb_handler routine.
dinbint():
disable inbound interrupt once mailbox is unblocked.
No action is taken when an item arrives in the mail-
box.
wait_for_item():
unblock mailbox and wait until next item arrives.
send(proc, item):
put item in mailbox of processor proc as soon as it
is ready for it.
extern int itemno; /* Number of current item in an */
/* incoming message */
extern int sending; /* A flag indicating whether */
/* PROFACE is currently trans- */
/* mitting a message */
int ibef; /* indicates if mailbox is blocked*/
int accreq; /* indicates if accept is needed */
/* for internal communication */
int retwbd; /* indicates if inbuffer is to */
/* left blocked at end of current */
/* inbound communication */
/*
accburst allows for faster communication during an
inbound communication started by a sendp on another
processor. Attempts to accept *n items (of which
item is the first) and puts them in memory starting
at *mes. Upon return mes *mes and *n have been
updated appropriately.
*/
accburst(mes, n, item)
int **mes, *n, item;
{
/* put first item in memory /*
*(*mes)++ = item;
(*n)--;
if (*n>0 && !sending) {
/* accept the next *n items in burst mode */
dinbint();
while ((*n)-->0) {
unblock();
wait_for_item();
*(*mes)++ = inb_item;
};
einbint();
};
return;
};
/*
inb_handler is the routine called whenever an item
arrives in the mailbox.
*/
inb_handler()
{
/* if first item, set exclusive source */
if (itemno == 0) set_excl(source);
more = accept(inb_item);
if (more == MORE)
/* not end of current inbound message */
unblock();
else {
/* allow items from any processor to arrive */
reset_excl();
/* unblock unless appropriate flags are set */
if (!accreq && !retwbd) unblock();
}
return;
}
/*
inoff blocks inbound items from arriving. It
also returns whether mailbox was alreay blocked.
*/
int inoff()
{
int temp;
block();
temp = ibef;
ibef = FALSE;
return(temp);
}
/*
inon unblocks mailbox if oldibef is TRUE.
*/
inon(oldibef)
int oldibef;
{
if (ibef = oldibef) unblock();
return;
}
/*
infree waits until accept is free, blocks mailbox
*/
infree()
{
inoff();
if (itemno) {
accreq = TRUE;
inon(TRUE);
while (itemno);
accreq = FALSE;
};
return;
}
/*
reqinblock sets retwbd, indicating processor would
like to send in burst mode. If no inbound communication
is currently happening, mailbox remains blocked until
freeinblock is called. Otherwise the mailbox is blocked
as soon as current inbound communication is finished.
*/
reqinblock()
{
inoff();
retwbd = TRUE;
if (!itemno) inon(TRUE);
return;
}
/*
freeinblock resets retwbd and unblocks the mailbox
if necessary.
*/
freeinblock()
{
inoff();
retwbd = FALSE;
inon(TRUE);
return;
}
/*
prostart initializes PROFACE (and the processor).
It returns with mailbox blocked, and inbound interrupts
enabled.
*/
prostart()
{
/* initialize system */
/* block mailbox */
inoff();
/* allow items from any processor to arrive */
reset_excl();
for (selfaddr=0;proctabl(selfaddr)==procaddr;selfaddr++);
/* selfaddr is an index into the table proctabl, which
holds the physical addresses of the processors */
retwbd = FALSE;
accreq = FALSE;
/* enable inbound interrupts */
einbint();
return;
}
/*
transmit sends the contents of the integer array mes
of length n to processor with index proc.
*/
transmit(proc, n, mes)
int proc, n, *mes;
{
for (;n>0;n--) send(proctabl(proc), *mes++);
return;
}
3. NODE PROGRAMS IN FORTRAN
Fortran subroutines can be used as node programs in the Unix Vax
version of DOMINO if the following conventions are observed:
1. The main program for DOMINO should be rewritten in
Fortran, so that Fortran i/o is handled correctly:
call control ()
stop
end
2. The internal name for a C subroutine named "x" is
"_x", while the internal name for a Fortran subroutine
named "x" is "_x_". Therefore, to call the DOMINO
routines from Fortran, interface routines (in C) are
needed. For example:
control_ ()
{
control();
awaken_ ()
{
awaken();
}
pause_ ()
{
pause();
}
finis_ ()
{
finis();
}
3. A function in C should be written to take nodep and
initialp and return auxp and initial .
(This has not been done yet.)
Then the node program can call a subroutine using these
as arguments, and treat aux as an array.
4. The routines should be linked as follows (assuming they
have been separated properly, see README):
DOMINO = accept.o \
< etc., omitting main.o >
COMLOC = fconoface.c \
fcontrol.o \
< These are assumed to contain the four
routines in note 2.>
go.o < user go node program >
USER = main.o <fortran> nodeprog.o
CFLAGS = -g
user : $(USER) $(MAIN) $(DOMINO) $(COMLOC)
<tab> cc $(USER) $(MAIN) $(DOMINO) $(COMLOC) \
-lF77 -lI77 -lU77 -o user
< This correctly links the Fortran libraries >
two.o: <nodeprog>.f
<tab> f77 -c <nodeprog>.f
main.o: main.f
<tab> f77 -c main.f
<etc.>
# SPLIT HERE FILENAME = makefile #
DOMINO = dominoport.o domdefault.o conoface.o spproface.o
USER = brigade.o
CFLAGS = -g
brigade : $(DOMINO) $(USER)
cc -o brigade $(DOMINO) $(USER)