Sec. 14-6 Communications between Nodes and Control Process 

251 

broadcasting blocks of data from every node to each of the other nodes. 
We should note that for reasons of history and simplicity we have presented definitions of broadcast, combine, and concat that apply to a full hypercube. Each of these utilities has a natural implementation on a subcube of the full computer and this useful extension will be given in the Software Supplement -Vol. 2 of this book. 

14-5.6 cparam 
Another new routine we introduce in this section is cparam, which returns various constants and parameters of the hypercube to the application program. Although cparam is not a collective communication routine, it is introduced in this section because it sup- plies important information about the node environment, some of which is specific to the hypercube topology. These constants and parameters are actually declared in the file cros.h, which must be included at the start of each application program. Although these quantities could be made available to the application program as initialized external vari- abies, such a method is undesirable in a real operating system, since it makes the system too vulnerable to errors in the application program. In crOS III, we do not allow the application program to have direct access to the system's copy of the parameters, so that an error in the application program cannot easily corrupt the system's parameters. Instead, the routine cparam takes a pointer to the structure cubenv as an argument, and copies the parameters defining the current node environment into the structure. Code 14-11 defines the contents of this structure. 

Code 14-11 The Structure cubenv as Used by the Routine cparam 
KCPARA, the FORTRAN equivalent of cparam, supplies the values of doc, proc- num, nproc, cpmask, and cubemask to the application program in an integer array. 

14-6 Communications between Nodes and Control Process 
In this section we shall examine implementations of the collective communication routines that provide communication between the nodes and the control process. As we mentioned in Sec. 14-4, we shall assume that the control process resides in a special pro- cessing element, the control processor, which is connected only to node O by a communi- cation channel. We further assume that the control processor can use cwrite and cread in 

252 

crOS ill: A S~ific Implementation of d1e Progranuning Environment Chap. 14 

the same way as the nodes to access its communication channel. The channel mask cubemask contains the channel mask of its communication channel, which connects it to node 0. In node ° cpmask is the mask of the channel that connects it to the control pro- cessor. In nodes other than node 0, cpmask is set equal to 0. 
As in Sec. 4-5, we continue to require that all the nodes communicate with the con- trol process collectively. A pair of complementary routines implements each mode of communication between the control process and the ensemble. Each of the nodes in the hypercube calls one of the routines while the control process calls the other. Although all of the nodes do not have to call their respective routines strictly simultaneously, they must issue the calls before calling any other communication routine. This is the loose synchronization condition discussed in earlier chapters. By requiring all the nodes to call the routines in loose synchronization, the details of how messages are routed between the control processor and the nodes are hidden from the application programmer. 

14-6.1 fcread, fcwrite 
Two of the routines that we discuss in this section require access to a file system so that they can transfer more data than will fit in the memory of the control processor. Since we do not have a full operating system in the conventional sense for the ensemble nodes, we have not assumed that the nodes have direct access to any kind of file system. Thus, we win provide the nodes with access to an operating system with a file system only through the control process. 
We introduce two routines that provide an interface between the file system of the control processor and its communication channel to node 0. The routines, fcread and fcwrite, are analogous to cread and cwrite, except that they use the file system of the con- trol processor instead of application memory .That is, fcread reads data from the com- munication channel and writes them to the file system, while fcwrite performs the inverse operation. The routines are defined in Code 14-12. 

Code 14-12 The Routinesfcread andfcwrite 
For convenience, we assume that open files in the control processor's file system can be identified by an integer "file descriptor". In a UNIX system, for example, a file descriptor is returned by a successful call to open, creat, dup, or pipe. 

Sec. 14-6 Communications between Nodes and Control Process 

14-6.2 setup 

253 

Both of the modes of communication between the control process and the ensemble that were introduced in Sec. 4-5 will be implemented using the same type of broadcast tree as described in the previous section. The only difference is that node O communi- cates with the control process, rather than acting as the source. Since the broadcast tree depends only on the hypercube dimension, the quantities corresponding to rchan and wchan can be calculated as part of the initialization of each node and stored in external variables. The routine setup (Code 14-13) illustrates the initialization of the node vari- ables needed to implement communications between the control process and the hyper- cube. 

In setup, the variable tocp is defined as the channel mask of the channel which gets messages closer to the control process in the broadcast tree. The variable brchan is the channel mask specifying those channels on which messages from the control process are to be forwarded. The dimension of the subcube to which each node must forward mes- sages from the control process is stored in subdoc. The algorithm for determining the variables is essentially the same as that used in broadcast to determine rchan and wchan. As before, node O is treated as a special case. 

Code 14-13 The Routine setup 

254 

crOS ill: A Specific Implementation of the Programming Environment Chap. 14 

14-6.3 bcastcp, bcastelt 
Having initialized variables containing the channel numbers and masks that will be needed for the routines implementing communications between the control process and the nodes, we can proceed to describe the routines that implement the four modes of communication. The first such routines we will examine are bcastelt and bcastcp (Code 14-14). 
As we clearly see, the implementations of bcastelt and bcastcp are very simple once we have initialized the necessary channel masks. Essentially all that is involved is calling cwrite and cread with the correct arguments. Since we are using the same broad- cast algorithm as presented in the previous section, the same comments about the optimality of the algorithm apply. 

extern int tocp, brchan; int bcastelt(buf, nbytes) char *buf; int nbytes; 

I* called by nodes *1 
I* pointer to buffer for incoming data *1 I* maximum amount of data to read *1 

int status; 

status = cread(buf. tocp, brchan, nbytes}; return(status}; 

int bcastcp(buf, nbytes) char *bur; int nbytes; 

int status; 

status = cwrite(buf. cubemask, nbytes ); retum(status ); 

1* called by control process *1 1* pointer to data to broadcast *1 1* amount of data to broadcast *1 

Code 14-14 The Routines bcaslell and bcaslcp 

14-6.4 floadcp, mloadcp, loadelt 
The second mode of communication from the control process to the nodes is imple- mented by the routines loadelt and loadcp. A broadcast algorithm similar to the one described in Sec. 14-5.3 is used, except that it is modified slightly so that separate mes- sages arrive at each node. A problem that arises when using the load routines is that they are designed so that they may be used to reload large ensembles of data from suspended computations. Since the nodes and the control processor presumably have comparable amounts of memory, the control processor cannot in general accommodate, in memory, 

Sec. 14-6 Communications between Nodes and Conlro1 Process 

255 

the large "checkpoint" buffers for all of the nodes in a large ensemble. However, the problem is rather artificial since the control processor would normally load such buffers directly from its file system. Thus, we avoid the problem by defining two load routines that can be run in the control processor, one that reads the buffers from memory, mloadcp, and one that reads the buffers directly from the control processor's file system, fioadcp. The three loading routines are given in Codes 14-15, 14-16, and 14-17. 

Code 14-15 The Routine loadelt 

Code 14.16 The Routine mloadcp 

256 

crOS m: A Specific Implementation of the Programming Environment Chap. 14 

Code 14-17 The Routinefloadcp The modification incorporated in dle broadcast algoridlm in loadelt is designed to send as many separate messages on each channel as dlere are nodes connected through dlat channel. Referring back to Fig. 14-2, which illustrates dle broadcast tree, we see dlat dle number is 2cha", where chan is dle channel number. Interestingly, 2cha" is also dle mask for channel chan .The value of nbytes in dle second call to cread is irrelevant since dle whole message will always be forwarded. 
The routine mloadcp uses dle information contained in dle array bufmap to direct separate blocks of data from dle array buffer to each of dle nodes. First, mloadcp checks that dle number of nodes indicated by dle first element of bufmap agrees widl nproc, dle total number of active nodes. If dle number of nodes indicated in bufmap is correct, mloadcp obtains dle length of dle first block of data from bulmap. It transmits dle block of data using cwrite and increments dle pointer to buffer appropriately. The process dlen repeats until mloadcp has sent a block of data to each of dle nodes. If any type of error occurred while transmitting the blocks, mloadcp returns -I to indicate dle error. Odler- wise, it returns the number of data blocks dlat it sent. 
The routine ftoadcp is nearly identical to mloadcp except dlat dle data blocks are taken from dle file specified by dle file descriptor Id using the routine Icwrite. However, bufmap resides in memory as in dle case of mloadcp. Thus, in order to use ftoadcp to restore a "dump" of dle ensemble from dle file system dle contents of bulmap must be read from dle file system separately. 

14-6.5 fdumpcp, mdumpcp, dumpelt 
The same problem with buffering occurs in the dump routines, which allow each of the nodes to send a separate message to the control process. One possible use of the dump routines is, as alluded to above, to "checkpoint" a long-running program. If all of the nodes tried to send the control process a long message, the control process might not be able to buffer all of the messages at once. Thus, we also need two versions of the con- trol process routine, mdumpcp andfdumpcp, which store the messages in memory and in 

Sec. 14-6 Communications between Nodes and Control Process 

257 

the file system, respectively. The implementations of the dump routines is almost the same as for the load routines, except that the direction of data flow is reversed. Codes 14-18, 14-19, and 14-20 contain implementations of these routines. 

Code 14.18 The Routine dumpell 

Code 14-19 The Routinefdumpcp 
We see here that dumpelt is identical to loadelt, except that one of the calls to cread has been changed to a call to cwrite, and the direction of data flow through the other cread has been reversed. Both mdumpcp and fdumpcp are similar to the corresponding load routines, except that the direction of data flow is reversed. The error response could 

258 

crOS m: A Specific Implementation of the Programming Environment Chap. 14 

int mdumpcp(buffer, nbytes, bufmap) 1* called by control process *1 
char *buffer; 1* pointer to buffer for incoming data*1 
int nbytes; 1* maximum amount of data to read per node *1 int *bufmap; 1* actual number of bytes read from each node *1 

:mt 1, error; char *ptr; 

bufmap [0] = nproc; plr = buffer; error = 0; 
for(i = 0; i < nproc; ++i) { 
bufmap [i+1] = cread (plr, cubemask, 0, nbytes); if (bufmap [i+1] = -1) { 
error= -1; 
plr += nbytes; 

else ptr += bufmap [i+l]; 

if(error = -1) retum(error); else retum(nproc); 

Code 14.20 The Routine mdumpcp 
be made somewhat more sophisticated in a real implementation of the dump routines, as it should be with all the implementations in this chapter. When creating a checkpoint for the ensemble with fdumpcp, the contents of bufmap must be written to a file, since jloadcp requires both the data blocks and the format information in bufmap. 

14-6.6 combcp, combelt The last of the collective communication routines we will discuss in this section are combelt and combcp. Since the control process will receive only one block of data from the ensemble as a whole, the ability to write the data directly to the control processor's file system is not needed. The control process does not contribute a block of data to the combining routine, so it only has to read the result from node 0. Thus, we can easily implement combelt using combine. We note that cwrite is called by every node in com- belt, but node 0 is the only node that actually writes the block of data items, since only node 0 has a nonzero value of cpmask. The routines combelt and combcp are given in Codes 14-21 and 14-22 respectively. 

Sec. 14-6 Comm1D1ications between Nodes and Control Process 

259 

Code 14-21 The Routine combelt 

Code 14-22 The Routine combcp 

14-6.7 cubeld 
So far we have not described how a program is loaded into the nodes and executed. We now introduce an additional family of routines that are called in the control processor to load a program into each node of the ensemble. The difference between the various possible cube/d routines involves the issue of how the argument list is passed to the node programs. We describe only one of the routines, cube/d/, in this section, and defer a dis- cussion of the remaining variations until Appendix E. The routine cube/d/ is defined in Code 14-23. 

260 

CtOS ill: A Specific Implementation of the Programming Environment Chap. 14 

Code 14-23 The Routine cubeldl 
The specified value of doc must be less than or equal to the maximum hypercube dimension as fixed by the actual machine. The second argument to cubeldl, name, gives the name of the file containing the program to be run in each node. We note that the cubeld routines load the same program into every node, although more general versions could allow different programs to be loaded into the argument list for main in each of the nodes. The list of arguments passed to each node is terminated by the final argument to cubeldl, which must be NULLPTR. 

14- 7 Mapping of Nodes onto Decomposition Topology 
In Sec. 4-6, we introduced a specific instance of a class of functions that map the nodes of the concurrent processor onto the decomposition topology of an application. The particular mapping we introduced, gridmap, is limited to decomposition topologies that are Cartesian grids. As we anticipated in Sec. 4-6, not all possible mappings of nodes onto the decomposition topology of an application are equally efficient In fact, since the hypercube interconnection does not allow direct communication between all pairs of nodes, the mapping of nodes onto the decomposition topology must be done carefully, so that a communication channel connects (as well as possible) adjacent regions of the decomposition topology. 
In Sec. 14-4, we mentioned that the hypercube topology also contains grids of lower dimensionality than that of the hypercube. Thus, we restrict our implementation of gridmap to mapping grids onto the nodes of the hypercube. In the interest of simplicity , we imposed an additional condition on gridmap: that the number of nodes in any dimen- sion of the mapping be a power of two. This additional condition is not strictly neces- sary, but it simplifies the algorithm and ensures that periodic boundaries can always be provided by a communication channel connecting nodes on opposite edges of the grid. 
Grids cannot be mapped onto the hypercube by means of a decimal ordering of the nodes, since in that case, consecutively numbered nodes would not, in general, be linked by a communication channel. In discussing the mapping algorithm, we return to a pro- perty of the numbering scheme we used for labeling the nodes of the hypercube, and examine it in more depth. The important property to which we refer is that the processor numbers of adjacent nodes, those directly linked by a communication channel, differ in their binary representation by a single bit. A numbering scheme in which only a single bit differs between successive numbers is known as a binary Gray Code [Gilbert 58]. While many Gray Codes are possible for a given number of bits, one particular Gray Code is generally regarded as the Gray Code because of its ease of computation. 

Sec. 14-7 Mapping of Nodes onto Decomposition Topology 

261 

The d -bit Gray Code can be generated recursively by first prepending a 0 bit to the (d-l)-bit Gray Code and then prepending a I to the same (d -l)-bit Gray Code written in reverse order. Let us start with the triviall-bit Gray Code: 0, I. We can easily gen- erate the 2-bit Gray Code, which is written in binary: 00, 01, II, 10. Applying the gen- erating rule again, we obtain the 3-bit Gray Code: 000, 001, 011, 010, 110, III, 101, loo. Notice that the first and last numbers in the Gray Code always differ in their highest bits. The availability of periodic boundaries is due to the first and last number always differing by a single bit Algorithms exist that rapidly convert between a Gray Code and its corresponding binary value, and these will be utilized in the actual implementation. 
By now the direction in which we are proceeding should be clear. The processor numbers of the nodes form a Gray Code, and the mapping procedure requires a conver- sion of the Gray Codes into coordinates on a grid of some specified dimensionality .To illusb"ate, we examine the case of the mapping of all the nodes in a 3-cube onto a ring. The 3-bit Gray Code gives the processor number of the node at each position in the ring. Starting with the coordinate 0 we have the following sequence of nodes: 0, 1,3, 2, 6, 7 , 5, 4, which map onto the coordinates 0 through 7 of the ring. Since the nodes whose coordinates are 0 and 7 differ by a single bit, a ring is formed. 
For grids of higher dimensionality than a ring, the same procedure is applied, but first the bits of the nodes' processor numbers are divided between the dimensions of the desired grid. The processor numbers of a d -dimensional hypercube contain d bits. Thus, a two-dimensional grid can be formed by assigning m bits to the x -dimension and n bits to the y -dimension in such a manner that m + n = d. Dividing the bits of the pro- cessor numbers into groups for each dimension of the grid guarantees that the number of nodes in each dimension is a power of two. Once the bits of a node's processor number are so divided, the groups are independently mapped to a coordinate, yielding a coordi- nate for each dimension of the grid. The mapping uniquely assigns each node to a posi- tion in the grid. Fig. 14-4 illustrates the assignment of nodes in a 3-cube to a two- dimensional grid with 4 nodes in the x -dimension and 2 nodes in the y -dimension. 
By grouping the bits comprising each node's processor number according to the number of nodes in each dimension of the grid and converting the groups of bits into coordinates, a map is created which assigns each node to a position in the grid. Adjacent nodes in the grid are guaranteed to be connected by a communication channel due to the properties of the Gray Code. The only remaining problem is that of determining the numbers of the channels connecting a particular node to its neighbors in the grid. Find- ing these channel numbers is an easy task once the grid assignment of nodes is known. By performing an exclusive-OR operation of the bits of the node's processor number with those of a neighbor's processor number, the channel mask of the connecting channel is obtained. The numbers of the channels connecting adjacent regions of the two- dimensional grid in Fig. 14-4 are indicated. 
We present the implementation of gridmap beginning with a pair of routines that convert between Gray Codes and binary procnum representation. Both routines will be used to implement the functionality of gridmap. 

262 

ClOS m: A Specific Implementation of the Progranuning Environment Chap. 14 

Mapping of a 3-cube onto a 20 grid 

100 (0. I ) 

1( 

(1,0) YL 001 x 
FIgure 14-4 Mapping of a three-dimensional hypercube alto a two-dimensional grid. 

0 

101 (1.1) 

l' 

(0,0) 000 

0 

III (2,1) 

0 

110 (3,!) 

(2,0) 011 

)1 

0 

(3,0) 010 

), 

Code 14.24 The Routine graytobin 
We begin by initializing a static integer array with a mask for each of the bitS in a 16-bit integer. The values of the masks are given as hexadecimal numbers so that the bit position of each mask is easily seen. The routine graytobin (Code 14-24} takes a Gray Code as itS argument and converts it to a cardinal number. The Gray Code is restricted to a 15-bit value since 16-bit integers are used in the conversion and one extra bit is required. The routine bintogray (Code 14-25} takes a cardinal number as itS argument and converts it to a Gray Code. The correctness of the algorithms for performing the conversions is easily verified by applying them to test cases. 

Sec.14-7 Mapping of Nodes onto Decomposition Topology 

263 

unsigned int bintogray(n) unsigned int n; { 

int temp; 

temp=n« I; retum«temp A n) » I); 

Code 14.25 The Routine bintogray 
Another utility that we will use in the routines that implement gridmap is log2 (Code 14-26), which returns the logarithm to the base 2 of its argument If its argument is not a power of 2, a value of -I is returned to indicate the error. 

int log2(n) WlSigned int n; 

int i=O; 
unsigned int nl=n; 

while(nl »= 1) i++; 

if(I«i 1= n) return -1; 

else 

return i; 

Code 14-26 The Routine 10g2 
The first of the gridmap routines is gridinit (Code 14-27), which is simply an ini- tialization routine for the other three routines comprising gridmap. The routine gridinit takes as input the dimension of the decomposition topology and an array of integers con- taining the number of nodes in each dimension. If the requested mapping is not possible, gridinit returns -I; otherwise, O is returned. 
In addition to saving a copy of dim and the array nwn, two data arrays and a mask that are used by the other gridmap routines are initialized by gridinit. Several checks are also made to determine whether the requested mapping is possible. First. the dimen- sionality of the requested topology must not be larger than the maximum specified by the macro MAXDIM, since that is the size of the various static arrays used by the gridmap routines. As mentioned previously, the number of nodes in each dimension is required to 

264 

CIOS m: A Specific Implementation of the Programming Environment Chap. 14 

be a power of two in our implementation of gridmap, although a more sophisticated implementation might have no such restriction. The special case, in which there is only one node in a dimension of the decomposition topology, is handled correctly by the grid- map routines. Finally, the total number of nodes required by the requested topology must not exceed the number of nodes in the ensemble. 
The arrays goffset and gmask contain information that allows the bits of a processor number to be easily grouped according to the number of bits assigned to each dimension of the topology. The groups can then be converted into coordinates using graytobin. The array goffset contains the position of the first bit assigned to the ith dimension of the topology , and gmask contains a bit mask whose width is the number of bits assigned to the ith dimension. The procedure for obtaining the subset of bits of a processor number corresponding to a dimension of the topology consists of shifting the processor number by goffset bits to the right, and performing the bitwise AND of the resulting number and gmask. 
The mask grem is a mask of any bits of a processor number that are not needed in the requested topology. It allows the other gridmap routines to ensure that only one node is assigned to a set of grid coordinates. Since having any unused bits in the processor number means that at least half the nodes are not being used, the situation should not arise often, but the gridmap routines will still work correctly. 
The gridmap routine gridcoord (Code 14-28) uses the algorithm for breaking a pro- cessor number into groups of bits, in order to convert the processor number into the coor- dinates of the node in the requested topology. It takes two arguments, a processor number and a pointer to an integer array in which the coordinates of the node will be stored. If the indicated node is not part of the topology, or gridinit has not been called, -I is returned. Otherwise, O is returned. 

Code 14.28 The Routine gridcoord 

Sec. 14-7 Mapping of Nodes onto Decomposition Topology 

265 

static int ginit = 0; static int gdim; 
static int gnum[MAXDIM]; 
static \mSigned int goffset[MAXDIM]; static \mSigned int gmask[MAXDIM]; static \mSigned int grem; 

int gridinit(dim, Dum) int dim; 
int*Dum; 

int i, Do offset; 

ginit = 1; n= 1; 
offset = 0; 
if(dim > MAXDIM) return(-l); gdim = dim; 
for(i = 0; i < dim; ++i) { if(log2(num[i]) = -1) 
return(-l); 
goffset[i] = offset; 
offset += log2(num[i]); gmask[i] = num[i] -1; gnum[i] = num[i]; n *= num[i]; 

/* indicates whether gridinit called */ /* keep a copy of dim */ 
/* keep a copy of array num */ 
/* offset of first bit in procnum */ 
/* mask ofbits for each dimension */ /* mask ofbits not used in topology */ 

/* dimension of decomposition topology */ /* number of nodes in each dimension */ 

/* indicate that gridinit called */ 
/* keep count of total nodes used */ 

1* check if dim is too large *1 1* save dim *1 

1* is number of nodes a power of 2 ? *1 

1* save current offset *1 
1* increment offset by # bits in dim i *1 
1* mask ofbits needed by dimension i *1 1* save number of nodes in dimension i *1 1* update total number of node used *1 

if(n > nproc) return( -1); 1+ check that enough nodes are available +1 grem = «1 « (doc -offset» -1) « offset; 1+ mask of bits not used +1 return(O); 1+ no error -return O +1 

Code 14-27 The Routine gridinit 
The gridmap routine gridproc (Code 14-29) perfOfDlS the inverse of the mapping perfofDled by gridcoord. Given an integer an'ay containing the grid coordinates of the desired node, gridproc returns the node's processor number, unless the specified coordi- nates are outside the range of the grid or gridinit has not been called, in which case a value of -I is returned. After checking the bounds on each of the coordinates, gridproc calls bintogray to convert the coordinate into its Gray Code. The resulting Gray Code is then shifted to the left by goffset bits to its correct position in the processor number. The processor number is then assembled by using a bitwise OR operation to combine the pieces obtained from the individual coordinates. 

266 

crOS m: A Specific Implementation of the Programming Environment Chap. 14 

Code 14-29 The Routine gridproc 
We now introduce one additional gridmap routine that was not discussed in Sec. 4-6. The routine gridchan (Code 14-30) takes a processor number, a grid dimension and a direction, and returns the channel mask of the channel connecting the specified node to its neighbor in the indicated direction. Thus, an application can use gridchan to deter- mine the mask of the channel on which to send a message, so that it arrives at the neigh- boring node in any of the particular decomposition grid directions. 

Code 14.30 The Routine gridchan 
Checks on the arguments are performed to ensure that the channel requested actu- ally exists. The argument dir must be either + 1 or -1 to indicate that the dim coordinate increases or decreases by 1. If dim is not one of the dimensions of the grid, gridchan 

Sec. 14-8 A More General Communication System 

267 

returns -I to indicate the error. The algorithm begins by obtaining the coordinates of proc by using gridcoord and adding dir to the coordinate in the dim dimension of the grid. Periodic boundaries are handled by testing to determine whether the resulting coor- dinate is out of range and, if so, making the necessary adjustment. The routine gridproc is then used to convert the modified coordinates into a processor number. The mask of the connecting channel is obtained by performing an exclusive-OR of the two processor numbers. 
It should be emphasized that gridchan always assumes periodic boundaries when it calculates the channel mask specified by its arguments, even though some applications do not involve periodic boundaries. In those applications, the coordinate in the appropriate dimension should be tested to determine whether it is at one of the edges before calling gridchan. If the node is at the edge of one of its nonperiodic boundaries, it can simply use a channel mask of 0 for any communications that would go across the edge. We also note that if gridchan is called along a dimension containing only one node, the periodic boundaries apply and it correctly returns a channel mask of 0. 
The implementations of all the gridmap routines given here are not necessarily as fast as they could be. In a real system, several additional data arrays could be initialized by gridinit so that the other gridmap routines could obtain their results by reading the appropriate data array instead of calculating the result each time. However, the imple- mentations were meant to clearly illustrate the underlying methods, and a more sophisti- cated implementation would not have served our present purposes. 

14-8 A More General Communication System 
The only type of internode communications that has been discussed in any detail so far in this book is crystalline communications. In Chap. 4 we defined the features that characterize a crystalline communication system. Its essential feature is that its routines poll the communication channels indefinitely while waiting for them to become ready for transmitting or receiving. As a result of polling the channels indefinitely, the crystalline communication routines impose a synchronizing condition that forces the nodes to exe- cute their programs in a loose lockstep as discussed in Sec. 4-3. Due to the synchroniza- tion imposed by the crystalline communications, they are most useful in applications whose communications can be expected by the participating nodes, and whose computa- tionalloads are well balanced. In addition, any message-forwarding must be done expli- citly, as in the routines that implement communication between the nodes and the control process, requiring that intermediate nodes also "know" in advance about the intended communication. In Sec. 22-2 the crystal-router algorithm will be described. This algo- rithm provides for automatic forwarding of messages within a crystalline communica- tions system, and shows that loose synchronization, and not forwarding, is the essential restriction of this environment. 
Clearly, crystalline communication systems such as CrOS III are not suitable for all applications, although we have shown their usefulness in a rich variety of problems. We shall now briefly examine a more general method of providing internode communication. However, a detailed discussion of the method is outside the scope of this volume. 

268 

crOS ill: A Specific Implementation of the Progranuning Envirorunent Chap. 14 

The essential defining feature of crystalline communications, polling the channels to determine whether they are ready for transmitting or receiving, is also its fundamental limitation. Another method for a processor to obtain the status information from its channels is to allow the channel interrupt lines to interrupt its main process. Thus, instead of polling the receive interrupt line of a channel to determine whether a packet can be read from the channel buffer, the processor is interrupted when a packet arrives in the buffer. When the interrupt occurs, the processor stops its current task and executes an inte"upt handler. The interrupt handler then reads the packet and stores it in some special location. When the interrupt handler is finished, the processor resumes execution of the task that was interrupted. 
In the same way, the processor can be interrupted when a channel is ready for a packet to be written. The interrupt handler for a transmit operation then writes the next packet in the message currently being sent However, if no messages are ready to be sent, the processor should disable the channel's transmit interrupt to prevent continual interruption by the channel. When a transmit interrupt line is disabled, it does not inter- rupt the processor even though the channel is ready to send a packet Thus, a channel's transmit interrupt must be enabled when the next message is ready to be sent 
A communication system that allows the processor to be interrupted, rather than polling the interrupt lines, is known as an interrupt-driven communication system. Since packets are read from the channels when they arrive instead of when cread is called, the messages do not need to be anticipated by the application program of the destination node, as in the case of crystalline communications. If the message header contains the processor number of its destination in addition to the message's length, the message can be forwarded toward its destination by an intermediate node. Since the interrupt handlers that actually read and write packets can also forward the messages, message forwarding can be done in a manner transparent to the application programmer. 
The synchronization imposed on an application by a crystalline communication system is not present when an interrupt-driven communication scheme is used. Thus, applications are freed to an extent from the constraint that the loads be well balanced between every communication step. However, the requirement that the computational loads be balanced in a good concurrent algorithm is not removed, but only somewhat relaxed. The total computational load should be balanced even when an interrupt-driven communication system is used, but it does not need to be balanced between every com- munication step in the algorithm. 
Another seeming advantage of an interrupt-driven communication system is that its user interface can be made more independent of the concurrent processor on which it is running. The interconnection topology of the ensemble is less important than with the crOS III communication system, since the interrupt-driven system can automatically route messages between any nodes in the ensemble transparently to the application pro- gram. Further, messages will be sent more quickly to nodes that are closer together, so the interconnection topology still has an important effect on the performance of the com- munication system. In Sec. 22-5, we will define the virtual machine loosely synchronous communication system and show it can be implemented either in terms of a crystalline or 

Sec. 14-9 Comments on Shared-Memory Machines 

269 

an asynchronous communication system. In the case of the hypercube, we use the crystal-router built on top of CrOS III. This illustrates that the essential advantage of an asynchronous system lies in its application to problems that are outside the loosely syn- chronous class, and not for its utility in irregular loosely synchronous problems. In other words, asynchronous communication systems are needed for temporally irregular prob- lems; they are applicable to but not needed for spatial irregularity. Note that temporal irregularity occurs not only in problems such as event-driven simulations, but also in sys- tem functions like debuggers which require the computer to interact with a highly unpredictable user. 
Unfortunately, the many advantages of an interrupt-driven communication do not come without a cost While an interrupt-driven system has more capabilities than a cry- stalline system, it is correspondingly more complicated. One effect of its additional com- plexity is that an interrupt-driven system is generally slower than a crystalline system. If the crystalline system is incapable of providing the communication facilities required by an application, an interrupt-driven system may be the only choice. However, problems that can be programmed with crystalline communications normally should be, since they will almost certainly run faster. In addition to providing slower communication, an interrupt-driven communication system is substantially more difficult to design than a crystalline system. Fortunately, the substantial body of literature on computer network- ing provides a useful starting point for the design of an interrupt-driven communication system. 

14-9 Comments on Shared-Memory Machines 
Throughout this chapter we have considered communication channels that are implemented separately in each node's hardware. However, some concurrent processors are designed as shared-memory machines, either by actually connecting several process- ing elements to a common block of memory , or by building a switch in hardware that allows each of the nodes to access any of several blocks of common memory. Throughout this book we have described domain decomposition as the essential idea behind concurrent computation. Although this probably underlies most effective uses of all concurrent processors, it is necessary to explicitly partition the data domain only for distributed memory machines, such as the hypercube. Shared-memory concurrent pro- cessors allow more general, and possibly more convenient, programming techniques where the data domain is shared in a single large memory and never needs to be expli- citly decomposed. However, one can use domain decomposition and the associated message-passing communication environment on such machines, and this may well lead to their best performance. In particular shared-memory concurrent processors with large local caches are naturally programmed by domain decomposition [Fox 87]. Indeed, the use of caches on sequential machines is optimized by domain decomposition. So although we realize that this is not the only method of using shared memory , we describe below how to implement a crystalline environment on such machines. 
A communication channel that can easily be implemented using shared-memory consists of a channel buffer and a pair of indices keyed to this channel buffer. One of the 

270 

crOS m: A Specific Implementation of fue Programming Environment Chap. 14 

indices specifies ilie next location in ilie buffer to be written by ilie transmitting node, and ilie oilier indicates ilie next location to be read by ilie receiving node. In such an imple- mentation, no memory conflicts occur since only ilie transmitting node modifies ilie chan- nel buffer and ilie transmit index, while only ilie receiving node modifies ilie receiving index. Of course, ilie transmitting node must be able to read ilie receiving index, and the receiving node must be able to read the channel buffer and the transmitting index. The two indices provide the same type of information as the interrupt lines of the communica- tion channels implemented in hardware, but they are more flexible. In particular, a mes- sage does not need to be transmitted as a string of packets in ilie shared-memory imple- mentation of the channels. 
We can implement cwrite and cread easily using the shared-memory communica- tion channels, so that they impose ilie same synchronizing conditions as discussed in Sec. 4-3 and 14-3. The channel buffer is a data structure known as a circular buffer which is empty when the transmit and receive indices are identical, and full when the transmit index is one less ilian the receive index. In order to transmit a message, cwrite first writes a block of data whose size is one less than the size of the channel buffer into the channel buffer, and makes ilie transmit index one less than the receive index. It cannot write any more data into ilie buffer until cread has been called in the receiving node. To determine whether cread has read any of the data in the buffer, cwrite compares the two indices. If any data have been read by cread, cwrite can write additional data into the buffer and adjust the transmit index accordingly. After writing the whole message, cwrite continues to compare the two indices until they are identical, indicating that cread has finished in the receiving node, and then cwrite returns. 
The routine cread is implemented in a similar way. It first compares the two chan- nel indices to determine if the transmitting node has written any data. When the channel buffer contains data, cread reads ilie amount indicated by the difference of the indices and adjusts the receive index accordingly. As in the version of cread implemented on the hardware communication channels, cread obtains the length of the message from the header that cwrite has prepended to the contents of the message. It then continues to compare the channel indices, read data from the channel, and adjust the receive index until it has read the "whole message. After reading the last of ilie message and adjusting the receive index, the two channel indices are again identical, indicating that the channel buffer is empty . 
The other basic communication routines, such as vwrite and vread, can be imple- mented in a similar way. Since the collective communication routines in crOS III can be implemented using the basic communication routines, the example implementations in Sec. 14-5 and 14-6 can be applied to the shared-memory version of CrOS m. However, restricting the shared-memory implementation to reflect a hypercube interconnection topology would be a serious waste of the shared-memory resources. Since a full-duplex channel connecting two nodes requires only two channel buffers and two pairs of channel indices, a channel can easily be established between every pair of nodes unless the amount of shared-memory is severely limited. Thus, the shared-memory implementation of crystalline communications could closely resemble ilie virtual concurrent processor 

14-9 Comments on Shared-Memory Machines 

"71 

described in Chap. 4. Still, an implementation of the message-passing environment we have described falls far short of the possibilities allowed by a shared-memory machine. In particular, broadcasts could be implemented directly by some scheme that reserves a block of memory for global messages, rather than by writing the same message into several chan- nel buffers. In addition, by transferring pointers to blocks of memory, rather than the blocks themselves, the crystalline communication routines could be made faster. Simply transferring pointers would not always be desirable, but it could greatly reduce the amount of time spent communicating when it was appropriate, especially when large messages were involved. However, when making comparisons between shared-memory architectures and message-passing architectures, we must remember that using shared- memory facilities to implement a message-passing system imposes restrictions on the access of the shared-memory and, therefore, is not necessarily the best way to program such machines. 

15 

15-1 Introduction 
In Chap. 6 we introduced the CUBIX system for concealing the details of the con- trol processor from programs running in the parallel processor. In the intervening chapters, and in the corresponding sections of the Software Supplement, we have made extensive use of CUBIX's 1/0 facilities. In this chapter we give a more detailed specification of CUBIX than the overview in Chap. 6, and we describe an implementa- tion of CUBIX using the crOS III library of Chap. 14. 

15-2 Specification of CUBIX 
CUBIX is a software system designed to simplify the programming of distributed computers. It consists of two parts: a universal program which runs in the control pro- cessor and remains unchanged from one application to the next, and a library of subrou- tines which may be linked with the node program. These subroutines interact with the universal control processor program to provide operating system services to programs running in the nodes of the concurrent processor. As discussed in Chap. 6, use of CUBIX results in programs which are easier to debug and maintain, and are more port- able. Parallel CUBIX programs may often be ported to sequential machines with little or no effort. CUBIX incurs little or no speed performance penalty, but does require memory for additional code which must be present in every processor of the distributed machine. 

15-2.1 System Calls 
If CUBIX is to make the control processor's operating system available to the con- current processor, its specification must depend on the control processor and its operating system. The basic ideas remain unchanged under different operating systems, but in order to avoid vague generalities, we specialize in this chapter to a discussion of control processors running the UNIX operating system. UNIX is attractive because of its popu- larity as well as the economy of its design. For example, the UNIX System V Program- mer Reference Manual [AT&T 84] lists 58 system calls which comprise the totality of an services a node process may request from the operating system. 
The UNIX system calls are defined in terms of their interface to C programs, so by specializing to UNIX, we are automatically biased toward the C programming language. Other languages may be accommodated by defining an appropriate set of bridges to the C system calls. 

273 

274 

CUBIX-Implementation Issues Chap. 15 

A CUBIX program running in the concurrent processor interacts with the control processor's operating system by using the same system calls and calling sequences that would appear in a sequential program running on the control processor. The system calls available on a host running UNIX System V are listed in Table 15-1. 

Table 15-1 List of UNIX System V Calls Those marked with an asterisk are not available in CUBIX. 
The system calls in Table 15-1 behave in the node processors exactly as if they were executed directly on the conttol processor. Their exact specifications may be found in the UNIX System V Programmer Reference Manual, or the equivalent manual if the conttol processor has a different operating system. Erroneous calls are tteated in the usual way by returning an impossible value and setting the value of errno to indicate the type of error. There are two important restrictions: 
1- System calls must be made loosely synchronously in all processors. 2- All processors must provide the same arguments to the system call. In the case of arguments which are pointers, the pointers may be different, but they must point to identical data. 
Since all nodes request the same thing, only one call is made on the conttol proces- sor, and only one value is returned to all the nodes. It is important to realize that the nodes do not attempt to internally emulate the control processor's operating system. In all cases, the arguments passed to the system call in the nodes are transmitted to the con- trol processor, where the system call is executed. Result codes and returned data are col- lected by the universal program in the control processor and sent back to the nodes. 
The system calls marked with an asterisk in Table 15-1 may not be invoked via CUBIX because they don't make sense within the CUBIX model. The disallowed sys- tem calls would change the run-time environment of the control process in a way that is not useful when the control process is a universal application-independent program. For example, sbrk would allocate system memory to the control process. This memory would not be accessible to the nodes of the parallel machine, as might be expected. Furthermore, once allocated, the conttol process would not make use of the new memory . 
In addition to the system calls defined by the conttol processor's operating system, CUBIX provides two more, mread and mwrite, which facilitate I/O operations when dif- ferent nodes read or write distinct data. They are called like read and write as shown in Code 15-1. 

Sec. 15-2 Specification of CUBIX 

275 

Code 15-1 Specification of mread and mwrite 
The system call mread causes cnt o bytes to be read from the file identified by the file descriptor, Id, into the memory of processor O starting at ptr 0. The next cnt 1 bytes are read from the file into the memory of processor 1 starting at Ptrl' etc. Subscripts refer to the value of the argument in the corresponding processor. The call mwrite behaves like mread. except that data is copied from the memory of the various proces- sors to the file. Both mread and mwrite must be called loosely synchronously, and the file descriptor argument must be the same in all processors, but the number of bytes read or written and the actual data sent may be different in each. 
These calls allow for distinct data to be read or written by each node, and they return different values to each node, corresponding to the number of bytes actually read or written. For example, if the file descriptor, Id, refers to a file with 17 remaining bytes, and the following statement is executed loosely synchronously in all processors: 
howmany = mread(fd, ptr, 7) 
the variable howmany will take on the value 7 in nodes 0 and 1, the value 3 in node 2, and the value 0 in nodes 3 and higher. 

15-2.2 The Standard 110 Library in CUBIX 
In the previous section we described the low level interface between node pro- grams and the control processor's operating system. Usually, however, programmers do not use these primitive system calls directly. High-Ievel languages provide standard ways of performing the most common 1/0 tasks, allowing the programmer the option of remaining ignorant about the underlying operating system. Different languages treat 1/0 in very different ways, with important implications about how effectively they can incor- porate CUBIX. 
In C, 1/0 capabilities are not defined as part of the language. Instead, a standard library of subroutines is provided which performs common tasks reasonably uniformly and efficiently. Any programmer or installation is free to rewrite or modify the library to change the behavior of the various routines. Thus, we can easily extend the Standard 1/0 Library , which is often written in C, to include routines appropriate for concurrent pro- gramming. 

276 

CUBIX-Implementation Issues Chap. 15 

Conversely, in FOR1RAN, 1/0 is explicitly part of the language. FOR1RAN CUBIX, as specified in Appendix C, requires the extension of the 1/0 system familiar to FORTRAN programmers and compiler-dependent modifications to the FOR1RAN run- time libraries. This is difficult to implement, and because of the compiler dependence, is less portable than the C version of CUBIX. Thus, we again specialize to C, at the expense of language independence, and discuss only the C implementation of CUBIX. 
There are two principal forms of Standard 1/0 allowed in CUBIX, which we denote as singular and multiple. Singular Standard 1/0 is similar to system calls described in the previous section. It requires loose synchronization and identical arguments, and its usage is identical to that in a sequential implementation. It is useful for obtaining or reporting global data. Multiple Standard 1/0 resembles the use of mread and mwrite. In multiple 1/0, distinct data is read or written by each node. Multiple 1/0 is not bound by the rule of identical arguments, and in the case of output, loose synchronization is not necessary either. 

In the CUBIX version of the Standard 110 Library, the attribute of multiplicity, i.e., either singular or multiple, is associated with each open stream (FILE pointer). AIl streams, including stdin. stdout. and stderr are initially opened in the singular state. The new functions fmulti and fsingl change their argument's multiplicity. The function ismulti returns a nonzero value if its argument is in multiple mode, and zero otherwise. These three functions are defined in Code (15-2). 

fmulti(stream) FILE *stream; 

fsingl(stream) Fll..E *stream; 

int ismulti(sb'eam) Fll.E *sb'eam; 

Code 15-2 Specification offmulti,fsingl and ismulti 
In conb"ast to the situation with system calls. the nodes execute the code for the Standard 1/0 Library routines. The control processor only plays a part if a system routine from Table 15-1 is called by the library routine. 

Code 15.3 Example of Multi Mode Input 
Use of multiple streams does require some explanation beyond a reference to sequential usage. Input streams in multiple mode behave in a reasonable fashion. Data is read by processors in order of increasing procnum; each processor begins immediately