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 = # 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 nodeprog.o CFLAGS = -g user : $(USER) $(MAIN) $(DOMINO) $(COMLOC) cc $(USER) $(MAIN) $(DOMINO) $(COMLOC) \ -lF77 -lI77 -lU77 -o user < This correctly links the Fortran libraries > two.o: .f f77 -c .f main.o: main.f f77 -c main.f # 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)