Sec. 22-2 crystal-router and General Message Traffic in the Crystalline Environment 

427 

routing table correspond to individual messages, and the rows to channel numbers. Each entry in the table is assigned one of the three values SEND, KEEP, or BOTH (for mes- sages with multiple destination processors). For each channel the corresponding row of the routing table is scanned, and each message is either sent on that channel (SEND), written to a local buffer (KEEP), or both of these (BOTH), depending on the table entry. 
We begin by specifying the structure of messages employed by crystal Jouter . Associated with each message is a set of tickets -one for each destination node. Code 22-1 outlines the dynamic crystal-router algorithm. 

proc-begin crystal-router ( general routing algorithm ) 
declare-struct mail ( deciare-int ndest; ( number of destination processors ) declare-buf dest-list; (integer array of destinations) declare-int nbytes; ( number of bytes in message ) declare-buf message; ( the message) ) ; declare-buf output-mail; ( buffer of mail items to send ) 
declare-buf input-mail; ( buffer to store mail items received ) 
declare-buf com-buf; ( communications buffer to store mail items exchanged on specific channel ) 
[copy any items in output-mail addressed to this processor to input-mail ] for-begin ( each channel, c, of the hypercube, c = 0,..., (d -I) ) for begin ( each mail item in output mail buffer ) 
-if-begin ( the Clb bit of any of ilie destination processors * the Clb bit ofprocnum ) then 
[add mail item to com-bufbuffer] if end for end 
[exchange com-bufbuffer on channel c, storing received data in com-bufbuffer] for -begin ( each mail item in com-buf) 
if-begin ( this processor is one of the destination processors ) then [ copy mail item to input-mail buffer] if end 
if-begin ( mail item must be forwarded ) then [ copy mail item to output-mail buffer] if end for end for end proc-end 

Code 22.1 The crystal-router Algorithm 

We see that the crystal-router algorithm cycles over each channel and is essen- tially the ordered cube geodesic algorithm. At the end of log~ steps, all messages are guaranteed to have been delivered to their correct addresses. In the case that each mes- sage has a ticket to reach every other node, crystal-router becomes the expand algorithm of Sec. 21-3.3. Furthermore, it reverts to index if each message is given the appropriate 

428 

General Message Passing in a Loosely Synchronous Environment Chap. 22 

single destination ticket. Thus, crystal-router is optimal for regular hypercube commun- ication in both the distributed broadcast (expand) and single destination (index. tran- spose. etc.) limits. However, it is not necessarily optimal in intermediate cases, but its obvious usefulness in irregular simulations makes it a strong contender as the method of choice for communication routing. We have found it to be of use in such diverse applica- tions as non-binary FFf's [A1oisio 87], Ka1man filters in a multi-track environment [Gottschalk 87] , and circuit simulation. From the point of view of the present section, the routines in Sec. 21-3 may be regarded as simply special cases of crystal-router, in which an explicit ticket is unnecessary because it is implied by the positions of the data. In Sec. 22-4 we introduce the crystal-accumulator that generalizes fold in the same way that the crystal-router generalizes index. 

22-3 Examples of the Use of the Crystal-Router Algorithm 
This section presents two examples of the use of the crystal-router algorithm. In the first the crystal-router is used to communicate circuit information in a spatially decomposed circuit simulation. In the second example, the crystal-router is used in per- forming non-binary FFfs. 

22-3.1 Circuit Simulation 
The previous section showed how the crystal-router provides a general, efficient communication system for the hypercube. Here we sketch out its use in circuit simula- tions. Although circuit simulations are geometrically quite irregular, the router allows arbitrary nodes of the hypercube to communicate in an efficient, synchronous manner. In addition to the irregularity of communication the balancing of the computational work- load among nodes of the hypercube is of equal importance in this example. A simple recursive bisection technique [Baden 87, Dippe 84, Dippe 85, Karp 77, Whelan 85] is used to achieve load-balance. Figure 22-l(a) shows the model CAD problem: a VLSI circuit which we wish to simulate (e.g., by using a system similar to SPICE). 
The load-balancing problem is illustrated in Fig. 22-1(b). Some types of circuit simulations are dominated by evolution of the transistors, so this is all that is shown in the figure. The challenge is to find a decomposition which puts equal numbers of transis- tors into each processor (balancing the load), yet groups them into regions of simple, convex shapes (keeping communication overhead reasonable). This is accomplished nicely by the recursive bisection technique. Figure 22-2 shows the decomposition of our model problem onto a 25 (32 node) hypercube. The first bisection is given in Fig. 22-2(a), where the data set has been split into two halves, containing an equal number of transistors. The left half of the problem will be simulated via the low half of the hypercube (nodes O through 15) while the right half will be handled by the high half of the hypercube (nodes 16 through 31). 
The bisection process continues in a recursive manner. Figure 22-2(b) shows the next stage, where each half has been further split into two parts. The process continues through five stages, finally giving the result of Fig. 22-2(c). At this point, each processor 

.: . 

.. .. 

.,.. . 
, .. 

~ 

... 

.. : : 

0 . 0 00 0 00 

0. :.. .. : :1 

0000 0 0 0 00000, 0 

.. 

.. .. 

.. 
..~. : : : 

0 0 
.00 0 00 

"" :"" " :: 

: :1 

00 - 

. ~ 

l'lgure 22-2(a) The first step of bisection. The circuit to the left of the division will be handled by the low half of the hypercube, the circuit to the right by the high half, (b) The next step of the recursive procedure. Each region is again bisected, (c) The final (fifth) step of bisection. At this point, we have a one-t0-0ne mapping between the 25 processors of the hypercube and the 32 regions of the figure. 

Sec. 22-3 Examples of the Use of the Crystal-Router Algorithm 

431 

The major steps of a simple parallel circuit simulator are outlined in Code 22-2. The data, which consists of circuit elements and netlist information, is loaded into the machine and then decomposed by a call to bisect. Interprocessor communication is done by means of a static crystal-router. Before entering the time evolution loop, initialization is achieved by a call to dry -run which takes the netlist as input and sets up routing tables that decide which circuit elements talk to one another when crystal Jouter is called. The main loop consists of a loop over circuit elements. First, the inputs to the element in question from the previous time step are combined. The element is then updated (evolved) and its output placed in the outgoing communications buffer. After looping through all the elements in this processor, a call to crystal-router is made which per- forms all necessary communications in an efficient manner. 

Code 22-2 A circuit simulation algoritJun using crystal-router 

22-3.2 Non-binary FFI's 
In their original formulation of the FFf , Cooley and Tukey [Cooley 65] described the algorithm for any "highly composite" number of points, N% .In general, the time to compute the Fourier Transform of a vector of length N% is proportional to N% times the sum of the prime factors of N% .In the well known special case in which N% = 2' , the sum of the prime factors is simply 21, or 2Iog~% .The time to transform the vector is propor- tional to N%logzN% .Subsequently, [Rader 68], [Good 58], [Winogmd 75, 76], and others introduced improvements to the original algorithm which significantly reduce the number of time consuming complex multiplications. In any event, the overall time to evaluate the transform remains proportional to N% times the sum of the factors of N% . 
In any of the algorithms, the number of points in the transform is factored into say, 
N%=N1xN2xN3x ...Nm (22-1) 

432 

General Message Passing in a Loosely Synchronous Environment Chap. 22 

A sequence of transfonnations is applied to the data, first in groups of N l' then in groups of N 2, and so on. After the last set of transfonnations is applied, the Fourier Transfonn has been computed. Non-binary FFTs may be computed efficiently on distri- buted computers using the static crystal router of Sec. 22-2. The static crystal router is used to move data between processors,-so that at the i th stage of the calculation, all the data points in a group of N i are together in one processor. In general, each time the crystal-router is called, all the data in the distributed processor is completely shuffled, requiring approximately: 

Nx 
tshuffle = tcomm NlogzN 
The overhead associated with the m calls to the crystal-router is approximately: 
mtcomm logzN f -L..U- :: 

(22-3 
)J .nUJJ~ t ~ factors of N 
)calc \~ x 
The functional form of this overhead is identical to the overheads encountered in Chap. 11, where we studied binary FFfs, and fQund that a hypercube is ideal for evaluating them. It is interesting that the performance of non-binary FFfs scales in a similar way, although the constant of proportionality is likely to be greater due to use of the very gen- era! crystal-router rather than explicit calls to crOS III routines. The importance of communication with respect to calculation is further increased because the non-binary FFfs perform fewer calculations in both the sequential and parallel cases. 
An additional consideration when computing non-binary FFfs is the possibility of load imbalance. This is probably best illustrated by an example. Consider a 1680 point Fourier transform on a 16 processor system. The number of points is factored as follows: 
1680= 7 x 5 x 3 x 16=7x 5 x 3 x 24 (22-4) The distributed algorithm proceeds as follows: 
7 x 5 x 3 = 105 16-point transforms 
crystal-router 
5 x 3 x 16 = 240 7-point transforms crystal-router 
3 x 16 x 7 = 336 5-point transforms crystal-router 
16 x 7 x 5 = 560 3-point transforms 
The most imbalanced phase of the calculation is the first, in which 105 transforms are computed on 16 processors. Clearly, 9 processors compute 7 transforms while 7 of the processors compute only 6 transforms. The load imbalance overhead in such a situation is: 

tslowes,-tallg 
f imbalance = t = avg 

16 105 

= 15% 

f??-~'\ 

Sec. 22-3 Examples of the Use of the Crystal-Router Algorithm 

433 

It is important to note that the significance of load imbalance decreases rapidly as the number of points in the transform increases. In fact, for a 11760 = 72 x 5 x 32 x 24 point transform, evaluated on a 128-node system, the load imbalance is only about 2%. Aloisio, Fox, Kim, and Veneziani [Aloisio 87] have compared the performance of the Cooley- Tukey algorithm and the Prime Factor Algorithm on several hypercubes, and concluded that although the Prime Factor Algorithm requires the crystal-router, its overall performance is often significantly better than the Cooley- Tukey algorithm. 

22-4 The crystal-accumuJator Routine 
The cryslal-accumulalor is another utility which makes use of the method of ordered cube geodesics. Suppose we have a vector V(i) in each of the nodes, i = 0, I, ..., N -I, whose elements we wish to combine to form a vector, S, the decomposition of which is arbitrary . 

SqU)=Vj(O)EBVj(I)EB ...EBVj(N-I) (22-6) 
where j=O,I,...,(M -I), labels the vector elements, and q U) maps the ordering of the ele- ments of S to that of V. Furthermore, let p (I) be the number of the unique processor in which S, resides. As in the routine combine described in Sec. 14-5.4, the combining function EB is specified by the user, and must be associative and commutative. An addi- tional feature of the cryslal-accwnulalor is that the elements of V (i) which equal the identity element of the combining function do not contribute to S, and so are not com- municated between processors. 
The pseudocode describing the cryslal-accwnulalor algorithm is given in Code 22-5. The algorithm begins by discarding those elements of V(i) equal to the identity element of the combining function. For each of the remaining elements, the channel mask, c U ), required to send V j to processor p (q U» is evaluated. The V j are then arranged in order of increasing c U) in a data structure called dala-buf, which also con- tains the values of c U) and q U). Within each group of elements having the same value of c U), the elements of dala-bufare stored in order of final storage location, qU). The algorithm then loops over each channel of the hypercube, starting with the highest, and sends those elements of dala-buffor which the corresponding bit of cU) is set At the same time, elements received on the same channel are stored in a scratch buffer, and each has the bit of c (j) appropriate to that channel setto zero. These elements are then com- pared with the remaining elements in dala-buf so that the ordering by channel mask and final storage location is maintained, and elements having the same value of q U) are com- bined. After this procedure has been repeated for each channel, the elements remaining in dala-buf are just the elements of S belonging to each processor, in the order specified by q U). Figure 22-3 shows how cryslal-accumulalor works for an example on a 2- dimensional hypercube, in which the vector length, M, is 8. 
The cryslal-accwnulalor provides a useful (although not always optimal) general purpose communication scheme in various complex summation algorithms, where the optimal, custom-designed solution is difficult to find. Modeling complicated, multi- component circuits or neurobiological networks provides various examples of this kind 
~ 

434 

General Message Passing in a Loosely Synchronous Environment Chap. 22 

Sort/Compress Stage 
Initial Sorted & Compressed 
-12 456 545106 PO I 2 5 7 5 2 I 7 PI 
0123 567 ' ~ 7106235p2 23567 67523 P3 

Exchange on Channell Followed by Merge/Combine (StepO) 
~45 0135 ~~43 5 PO 
5 2 ° 5 2 3 ~ 5 2 3 PI 7106 ° 106 ~ 7106 P2 67 017 ~ 167 P3 

Exchange on Channel O Followed by Merge/Combine (Stepl) Resident Received Merged & Combined 
r43 E>t3 ~ 
[43 PO , E> , ~ , PI , E>' ~, P2 t 6 E> t 06 ~ 106 P3 
Final result, S 
Flgure 22.3 An example of dIe crystal-accumulator for dIe case M=8 on a 2-D hyper- cuOO. The ordering of S is determined by q(j), and its decomposition over dIe hypercube by P(j). Here it is assumed dlat q = (2, 4,5,3, 1, 7, 0, 6), and p = (0, 0, 1, 0, 3,2,3,3). 
[Furmanski 87a, 87b]. Consider, for example, a neural network with short or medium-range connectivity, and with patchy activity patterns such that a domain decomposition would result in poor efficiency in the concurrent algorithm. Patches (i.e., small compact cortical regions with temporal activity excess) might be due to the multi-Iayer structure arising from the over- lapping in space and time of neuronal sub-populations, or to rhythmic activity in which the enhanced workload area propagates in an oscillatory fashion through a given cortical structure. This type of situation is found, for example, in the hippocampus, cerebellum, and piriform cortex. 
Scattered decomposition is the simple, general-purpose solution of the load-balance problem due to patches. If the number of model neurons per patch exceeds the number of nodes on the hypercube, the scattered decomposition results in satisfactory load- balance since each patch is distributed over the whole hypercube. The price to be paid is that the network neighbors are not neighbors in the hypercube topology, and we are faced with the problem of sparse vector summation with non-zero components distributed over a hypercube in a complicated, problem-dependent and time-dependent manner. 
This is precisely the problem addressed by the crystal-accumulator. Intuitively we can illustrate the action of the algorithm in this case by saying that the dendritic tree of each neuron is distributed over the whole hypercube. In the case of sparse connectivity 

Sec. 22-4 The cryslal-accumulalor Routine 

435 

some, or even many, of the branches may be absent. The crystal-accumulator moves signals along the dendrites (represented by hypercube geodesics), concurrently perform- ing partial summations in the nodes in a manner which is statistically homogeneous for all trees. For this example we have M neurons and V j (i) is the contribution to the input signal of neuron number j coming from all neurons in node i. The calculation of the individual V j (i) would proceed concurrently, and typically involve a substantial amount of computation. 

proc-begin crystal-accumulator (combine vectors V(i) to give S) 
declare-struct mstruct ( declare-int dest-mask, dest-index; declare-buf but; } ; declare-buf data-but; (array of data type mstruct) 
declare-buf scratch-but; (array of data type mstruct) 
declare-buf p; (integer array, maps decomposition of S to processors) declare-buf q; (integer array, maps ordering of S to that of V(i» 
[copy elements of V not equal to identify element to data-buf] 
[sort elements of data-butin order of the channel mask needed to get to p(q(/) ] 
[for each channel mask sort elements of data-but in order of final decomposition of S] for -begin (channel, c, from (d-l) to O ) 
[send on channel c elements of data-bufwith bit number c of dest-mask set, while receiving incoming data on channel c in scratch-bu.f] 
for-begin (each element in scratch-bu/) 
[set bit number c of dest-mask to zero] if-begin (this element has dest-index 
equal to that of some element of data-bu/) then [combine and overwrite element of data-buf] 

else 

[insert element of scratch-bufinto data-buf, maintaining ordering by dest-mask and dest-index ] 

if end for end for-end 
[copy remaining elements of data-bufto output data buffer] proc-end 

Code 22.5 The crystal-accumulator Algorithm 
The irregular nature of the crystal-accumulator algorithm makes it difficult to give a perfonnance analysis for the general case. However, insb"uctive results can be obtained for the "random" case, in which each processor contains approximately the same number of non-identity elements in the vector V (i ), and the final decomposition of S is unifonn over the processors. In this case we denote by n (c ) the average number of elements per node, at step c of the algorithm, where c=O,l,...,d-l. On the average, at step c each pro- cessor exchanges n(c)/2 elements over channel (d-l-c). There are M(c+l) possible locations for the elements received, where M (c + 1 )=M (0)/2c+l. Thus, the probability that a particular received element can be combined with another element is 

436 

General Message Passing in a Loosely Synchronous Environment Chap. 22 

n (c )/2M (c + I), so the number of elements per processor at the next step may be written: 

n(C+l}=~+ 
['l- n(C}]~ 
2 2M(c+l} 2 

where the first term on the right-hand side is the number of "resident" elements at step c , and the second term the number of "new" elements, i.e., the number of elements which were received, but which were not combined with any of the resident elements. The recursion relationship Eq. (22-7) may be solved to give, 

n (c )= 
2c 
where 1= n/M is dIe initial average fraction of dIe V(i) not occupied by identity ele- ments, M = M (0) is dIe lengdl of dIe vector in each processor, and n = n (0) is dIe aver- age number of elements per processor not equal to dIe identity element of dIe combining function. The total communication time for dIe crystal-accumulator algorithm is, 
d-l n(c) 
T comm = tcomm L 2 (22-9) c=O 

M 

1- 

(22-8) 

so substituting from Eq. (22-3) we have, 
4-1 M Tcomm = Icomm L 2c+1 c~ 
Figure 22-4 shows T comm as a function of n for fixed M .Two limiting cases are of interest. For n < < M , the communication time is proportional to n , which is the same as for the cryslal-rouler algorithm. However, as n ~M the dependence of T comm on n disappears, and the curve in Fig. 22-4 levels off. This limiting case is the same as the fold algorithm. Thus, if the vectors V (i) are sparse the cryslal-accwnulalor behaves like the cryslal-rouler; however, if the V(i) are full it behaves like the routinefold, described in Sec. 21-3.3. Due to the high computational cost of forming the Vi(i), the hypercube implementation in [Furmanski 87a] is very efficient, with the communication dwarfed by calculation. 
In [Furmanski 87b], the use of communication algorithms for network simulation was summarized by: 

-[ I -( 1 -'Y J 2' ] 

Sparse Regular Network ~ Index 
Sparse Irregular Network ~ Crystal-router 
Dense Irregular Network ~ Crystal-accumulator Dense Regular Network ~ Fold 

(22-10) 

Sec. 22-4 The crysta/-accumu/ator Routine 

437 

0 

n~ 

M 

Figure 22.4 The dependence of T ~... on n, the average number of non-identity elements per processor, illustrating the two limiting cases. 
22-5 An Implementation of the Virtual Concurrent Processor 
In Chap. 4 we introduced the concept of the virtual concurrent processor, in which the nodes are fully interconnected and communicate via node-addressed messages. We now consider how such a communication paradigm might be implemented in software on a broad spectrum of real concurrent processors. We call this the virtual machine loosely synchronous communication system (VMLSCS). The functionality of the VMLSCS may be modeled by assuming that communication is handled by a separate process, referred to as the VM process, which runs in each node. Nodes communicate by making read and write requests to their VM process. Interaction between the VM processes of different nodes actually effects the transfer of messages between the nodes. The user interacts with the VM processes in the nodes only by making read and write requests. 
The VM process is initiated by a call to the routine vm-initproc, and is terminated bya call to vm-killproc (or the end of the program), both of which must be called with loose synchrony. The routine vm-initproc allocates buffer space and performs any necessary machine-dependent tasks to initiate the VM process. The routine vm-killproc releases the resources assigned to the VM process. Requests to the VM process to read and write messages are made using the routines vm-read and vm-write, which were introduced in Sec. 4-3. In order to increase the utility of these routines we now add two extra arguments, message-type and mode. The message-type allows processors to exchange messages of a specific type, and the mode specifies whether the communication is to be blocking or non-blocking. In Sec. 4-3 vm-read and vm-write were defined to be blocking communication routines, however this restriction can now be relaxed since these routines only make requests to the VM process, and do not directly send or receive 

438 

General Message Passing in a Loosely Synchronous Environment Chap. 22 

messages. When communicating in non-blocking mode the routine vm-write does not wait for a complementary call to vm-read in the destination node before returning, nor does vm-read wait until a call to vm-write has been executed in the source node, thus vm-write and vm-read do not have to be called in loose synchronization, and there is no possibility of deadlock. However, in blocking mode the constraint of loose synchroniza- tion still applies, and a blocking call to vm-write in a source processor must be matched by a corresponding blocking call to vmJead in the destination processor. On some con- current processors blocking communications may only be used between certain nodes. For example, on a hypercube only nodes directly connected by a communication channel may communicate in blocking mode. If portability is required all communication should be done in non-blocking mode. 
The VM process attempts to service read and write requests made in blocking mode immediately. Communication requests made in non-blocking mode are not immediately serviced, however, the routine vm-comsync ensures that all previously writ- ten messages have been delivered to their destination. The routine vm-comsync must be called in loose synchronization in all processors. An additional routine, vm-query, may be called to check whether there are any unread messages of a particular type that have been received from a specified processor. The arguments to vm-query are pointers to integers specifying the source processor and message type, either of which may have a "wild card" value to indicate that any value for these quantities is acceptable. If an unread message satisfying the source processor and message type constraints exists, then the actual source processor and message type are stored at the locations pointed to by the routine's arguments. If no such message exists then an error code is returned, otherwise the length of the message in bytes is returned. The routines vm-write, vm-read. and vm-query are defined in Code 22-3. 
Having described the functionality of the VMLSCS we now consider how to imple- ment it on different types of concurrent processor. In the case of a hypercube running with an asynchronous communication system, the virtual concurrent processor can be implemented relatively easily since such systems generally provide communication prim- itives for performing node-addressed communication. In this case a call to vm-comsync synchronizes all the nodes, and ensures that all writes have been completed. For a hyper- cube with a synchronous, channel-addressed communication system, such as crOs III, the routines cread and cwrite may be used to implement blocking communication. The crystal-router algorithm may be used to implement non-blocking communication, and we will consider this in more detail. For each communication channel there is a corresponding communication buffer, allocated in the routine vm-initproc. When a non- blocking write request is made by a call to vm-write the message is copied into the com- munication buffer of the channel on which the message must be sent first. A header con- taining the number of bytes in the message, the source and destination processors, and the message type is prepended to each message. When vm-comsync is called these mes- sages are delivered to their destination processors by means of the crystal-router algo- rithm, as follows. Communication buffers are exchanged over the first communication channel, and the header of each message received is checked to see whether it has 

Sec. 22-5 An Implementation of the Virtual Concurrent Processor 

439 

reached its destination processor or whether it must be forwarded. If a message is to be forwarded it is copied to the communication buffer of the channel on which it must next be sent If a message has reached its destination then information about it is copied to an array of data type MESS-DATA referred to as the read array. MESS-DATA is defined in Code 22-4. After this process has been repeated for all of the communication channels all messages will have reached their final destination. 

Code 22-3 VMLSCS Routines 

Code 22-4 The Data Type MESS-DATA 
Non-blocking read requests made by vm-read cause the read array to be inspected. If an unread message satisfying the source processor and message type constraints is referenced in the read array then the message is copied from the communication buffer to the storage location supplied in the read request, and is flagged for deletion from the communication buffer. Thus read requests are serviced immediately. The routine vm-query also inspects the read array, and is similar to a non-blocking read request 

440 

General Message Passing in a Loosely Synchronous Environment Chap. 22 

except that the memory-to-memory copy from the communication buffer to the user- supplied buffer is not performed. 
In addition to delivering messages to their destination processors, vm-comsync per- forms another major task. At the start of vm-comsync each of the communication buffers is examined, all messages flagged for deletion are removed, and the comrriunication buffer is compacted. 
As a further refinement. on some hypercubes with high-speed floating-point units, such as the Caltech/JPL Mark IIIfp hypercube, it is advantageous to split the routine vm-comsync into two parts. The first part initiates the exchange of communication buffers whilst the second checks for completion of the exchanges. These two stages can be implemented as distinct routines so that calculation can be performed between the two stages, thereby overlapping communication with calculation. To do this vm-write and vm Jead need to be modified so that the copying of messages in and out of communica- tion buffers is performed as part of the communication step and overlaps calculation. Thus vm-write should not copy the message to a communication buffer, but instead maintains a list of pointers to messages in an array of type MESS-DATA. After com- munication has been initiated this array is inspected, and the messages are then copied to the appropriate message buffers. The routine vm-read should be modified so that when a request is issued to read a message that has not yet arrived the request is stored in an array of type MESS-DA T A. When the message arrives it is then copied to the location stored in this array. 
A full implementation of the virtual concurrent processor should also contain col- lective communication routines, such as vm-bcast for sending messages to more than one destination node, and vm-combine for combining data from a set of nodes. Such routines can be implemented quite straightforwardly in terms of vm-read and vm-write, however we will not go into the details here. 
The virtual concurrent processor can also be implemented on shared memory con- current processors. On such machines an area of shared memory is allocated to contain the messages addressed to each processor. Calls to vm-write cause the message and header to be written to the message area of the destination processor. The routines vm-read and vm-query check through the message headers in the message area for unread messages with the appropriate source processor and message type, and, in the case of vm-read, copy any such messages to the storage location supplied in the argu- ment list. The routine vm-initproc initializes the message area, and vm-comsync syn- chronizes the processors. 
The concept of the virtual concurrent processor was first introduced in Chap. 4 to provide a framework within which to discuss concurrent algorithms. However, it is now apparent that the virtual concurrent processor can be implemented on a wide range of dif- ferent types of concurrent processor, and provides a common communication system per- mitting a high degree of software portability. 
We emphasize that the virtual concurrent processor with its service routines of Code 22-3 represents an abstract machine model suitable for the general loosely synchro- nous problem. We have been careful to define VMLSCS so that it can be implemented 

Sec. 22-6 Portable Progranuning Environments 

441 

with either synchronous or asynchronous communication systems. This allows the sys- tem implementer to choose the method that gives the desired tradeoff between func- tionality and performance. 

22-6 Portable Programming Environmen~ 
We started this book by defining a rather general virtual machine, but used a specific hypercube environment, crOS Ill, for much of the detailed algorithmic and per- formance analysis. Now we have shown how to use crOS III to build a much more gen- eral programming environment -VMLSCS -which realizes the virtual machine concept on a hypercube. The crystal-router and crystal-accumulator algorithms are the keys to a hypercube implementation of VMLSCS under crOS Ill, or more generally under any synchronous system. We have, in fact, ported crOS III to a variety of different hyper- cubes and also shared memory machines such as the BBN Butterfly and IBM's RP3. However, VMLSCS is a more appropriate system around which to build a portable environment. VMLSCS can be implemented with either an asynchronous or synchro- nous message-passing system at the lowest level. 
Currently we view crOS III as a finished product -an optimized synchronous implementation of VMLSCS for the hypercube. In the near future we expect to experi- ment with VMLSCS and use it with our future concurrent scientific algorithms. We will build VMLSCS on a variety of high performance concurrent machines of different archi- tectures. In particular, we see it as a natural environment for all coarse-grain MIMD machines with either shared or distributed memory . 

23 

23-1 Introduction 
This book has covered a large number of algorithms and problems and has shown that in every case there are conditions, i.e., particular values of parameters, under which concurrent computers can be effectively used. Can these examples be convincingly gen- eralized? What are the essential characteristics of the problems? What is the nature of the parameter space? What classes of concurrent computers are covered by our analysis? Can we meaningfully speculate on problems, parameters, or computers that are not natural extrapolations of our examples? We will address these questions in this chapter under the general theme: "When is a hypercube a supercomputer for scientific and engineering computations?" 

23-2 Hardware Issues 
The essential lessons, as they relate to hardware, have already been summarized in Sec. 3-5 and 3-6, widt Chap. 2 describing how the hypercube fits in a taxonomy of paral- lel computers. The algorithmic chapters (5-13, 16-21) of the book have expanded upon the general algoridtmic overview in Chap. 3. 
Chap. 2 describes some key choices in the architecture of concurrent computers that are reiterated in Table 23-1. 
Table 23-1 Features of Concurrent Computers 

Of these global choices in Table 23-1, the discussion of this book has leaned heavily toward the left-hand column of Table 23-1. This choice, however, leaves the topology of the node interconnection unspecified. Much applications work can be independent of the topology , but we have frequently chosen to address the hypercube specifically. Chapters 11, 18, 19,21 and 22 rely on the det!lils of the hypercube topol- ogy; the other chapters typically require only a mesh interconnect, which is contained within the hypercube. Inhomogeneous problems and load-balancing (decomposition) 

443 

444 

The Hypercube as a Supercomputer in Science and Engineering Chap. 23 

techniques rely on a general feature of the hypercube: the short (at most log~) distance between any two nodes in a hypercube network. In the context of current technology, the richness of the hypercube topology seems to justify the additional expense (over a two or three-dimensional mesh) required for its implementation. 
According to Eq. (3-22), the speedup on a concurrent machine is given by: 
N 
S = -(23-1) I+!c 
With the overhead! c taking the typical form: ! c = [a+btcomm/tcak ]/n lId (23-2) where a, b, and d are constants that we have derived for many of the examples in this 
book. The values of a, b, and system dimension d are determined by the algorithm, and the value of tcomm/tca/c by the hardware and communication software implementation. Figure 3-5 emphasizes the essential point As long as the problem is big enough (n lId -10) for typical ranges of parameters (a+btcomm/tca/c -I), one will obtain a speedup that is close to N and linearly increasing with the number of processors. In gen- eral, hypercubes with sufficient memory on each node and with good communication capability (t = tcomm/tca/c comparable in value to that for the original Caltech machines, t -3) will perform well. We should note that we have tacitly assumed in the previous chapters that communication and calculation cannot be overlapped. In more advanced designs, one can overlap communication with calculation and this leads to a straightfor- ward extension of the performance analysis given in Sec. 3-5. One finds that for typical problems the overlap allows one to relax the condition on t and find good performance as long as t = tcomm/tca/c is ~ 15 for the case of overlapped communication and calculation [Fox 87]. 
It is interesting that we have found no other limiting criteria. All the problems that we have considered have "natural" algorithms that exhibit parallelism. Only in the sort- ing problem of Chap. 18, did we find that the speedup was significantly reduced by the nonoptimal performance of the concurrent algorithm. Many of the problems discussed in this book are simulations of natural phenomena; clearly nature itself is highly "con- current" and so it is not surprising that good algorithms can be devised to model this con- current world. 
Throughout this book we have assumed that the communication system between the nodes incurred little startup or latency penalty, i.e., that tcomm is roughly independent of the message size. Current commercial hypercubes, however, exhibit the effect illus- trated in Fig. 4-2 in which tcomm is large for short messages. This effect is a consequence of both hardware and software design differences from the original Caltech hypercubes, which in fact display only a modest dependence of tcomm on message size. Some of our conclusions and analysis may require reexamination if machines that exhibit good perfor- mance for relatively short messages are not generally available. 
Our techniques can be translated straightforwardly to machines that utilize shared memory but also adhere to the "left-hand column" for the last three issues in Table 23-1 

Sec. 23-2 The Hardware Issues 

445 

(i.e., large grain size, MIMD, and general purpose node). Such machines include those designed by CRA Y, ETA, ENCORE, SEQUENT , ALLIANT , BUTTERFL Y, ELXSI, etc. In fact, if the shared-memory machine inco~tes a large cac~e on each node, then one can view the caches as the distributed memory and the shared memory as a commun- ication mechanism [Fox 87]. 
Some of our results apply to fine grain-size machines, but the mapping is not so direct or universal as the correspondence between the hypercube and a large grain-size shared-memory machine. 

23-3 Software Issues 
We have adopted a conservative approach to the software issues. We have made the minimal necessary extensions to a conventional sequential programming environ- ment. The choices and issues have been reviewed in Sec. 3-4, and here we touch upon the highlights. The software for large grain-size concurrent computers can be very simi- lar in structure to that for sequential machines. One need only add a library of basic communication calls to any standard language. We have discussed C and FORTRAN, but PASCAL, LISP, ADA, PROLOG, BASIC, and even assembly language represent equally acceptable programming languages. The CUBIX environment, described in Chaps. 6 and 15, allows the concurrent programmer access to the same input/output and system facilities of modem sequential systems. It is in many cases quite straightforward to generate concurrent code that with trivial modification may run on both sequential and concurrent machines transparently. Although we have not discussed this point in much detail, the same code may also run on a wide variety of large grain concurrent computers of both distributed and shared memory design. We expect that it will be easier to run hypercube code on a shared-memory machine than vice versa. 
The crystalline environment used throughout this book has two important limita- tions. Firstly, it only addresses the programming of a class of problems that we have termed loosely synchronous in Sec. 3-4; there exists a global synchronization mechanism typically arising from either an iteration count or an overall simulation time. This restric- tion is apparently not too serious, since it is satisfied by all the examples in this book. Loosely synchronous problems include a large fraction of typical supercomputer applica- tions. Many research groups including our own are working on more general program- ming environments that will address more extensive problem classes. In Sec. 22-5, we introduced the virtual machine loosely synchronous communication system (VMLSCS) and we believe that this is a natural programming environment for this general problem class. As explained in Sec. 22-5, one can implement VMLSCS with the crystalline sys- tem. Other low level message passing paradigms are also appropriate for VMLSCS and could be chosen on the basis of performance/functionality tradeoffs. 
The second limitation of the crystalline environment is more subtle. One way of stating this limitation is that the VMLSCS environment is an algorithmic or user com- munication system but not a concurrent operating system. Crystalline communication and CUBIX encompass the necessary message-passing and I/O functionality that a pro- gram needs when running application code. This task is accomplished with elegance and 

446 

The Hypercube as a Supercomputer in Science and Engineering Chap. 23 

high perfonnance. However, dle system is incomplete as it does not address many important areas of the programming environment. These areas include sharing dle con- current computer among many users (multi-user environment) and interactive program debugging. These capabilities require a more complete asynchronous operating system that eidler emulates a crystalline environment or more efficiently transfers control to an optimized crystalline system when dle application program is running. 

23-4 Scientific Applications on a Concurrent Supercomputer 

23-4.1 Introduction 
In Chap. 2 we described how an extrapolation of current technology should allow the future construction of large grain-size concurrent computers whose performance will be several orders of magnitude greater than that of current supercomputers. Specialized fine grain-size machines will lead to even greater performance for some problems. The examples discussed in this book have shown how a broad range of problems are capable of effectively using this potential performance. yielding speedups comparable to the number of nodes. At Caltech. we have adopted a somewhat unusual but practical approach to developing the scientific uses of concurrent machines. The research program is based not upon a general theoretical framework. but rather upon experiment. We sup- plied the necessary support to allow leading computational scientists to use hypercubes. thereby going beyond tryout algorithms and solving significant problems. This approach has had the advantage of ensuring that complete applications were developed so that the total performance could be assessed without neglecting possible hidden sequential bottlenecks that would lower the overall performance. We close this book by describing some of the research applications. This description complements the rest of the book in the sense that the discussion is science-based rather than algorithm-based. Such a compi- lation is by no means complete. but it is useful as an indicator. We restrict mention to local work with which we are familiar and we choose only to describe those Caltech applications for which the implementation issues are fairly clear-cut This restriction excludes some exciting work in progress. More details of these implementations can be found in [Fox 86£]. 

23-4.2 The Hypercube in Biology 

Neural Circuit Simulation There is growing interest in the use of simulation in biological research, and in par- ticular in the study of large systems of neurons. These can either be real neurons as dis- cussed in Chap. 1 when simulating the brain, or "applied" or "theoretical" neurons which comprise computational circuits of the type discussed in [Hopfield 82]. The concurrent decomposition issues in simulating such systems are described in [Furmanski 87b] and are very similar to those involved in the simulation of an array of electronic components such as those in a chip. The best algorithms depend upon the nature of the circuit, but in 

Sec. 23-4 Scientific Applications on a Concurrent Supercomputer 

447 

the cases looked at so far the hypercube can be an excellent circuit simulator. In the case of simulations of the brain, this conclusion is not surprising, since nature's computer, the brain, is a kind of distributed memory system. It should be expected that a general- PurPose distributed-memory concurrent computer like the hypercube can be applicable to its simulation. 
In many cases, the connectivity between neurons (circuit elements) is so high that one can use the long-range force algorithm of Chap. 9. In this case the input from each neuron is communicated to all nodes. Consider a simulation of a system with N " neurons on a hypercube with N nodes. Suppose further that on average each neuron is connected to I others. Then if I »N , independent of N " , the algorithm of Chap. 9 is efficient. In an implementation of the simulation of the piriform cortex on the hypercube, we found that the fold algorithm of Chap. 21 was appropriate [Furmanski 87a]. Connectivities with I ~ may call for the special decomposition or load-balancing techniques which were covered in Sec. 3-8 and Chap. 17. A particularly difficult case with 1=4 and random con- nectivities is discussed in [Fox 86d]. 
The hypercube is not only appropriate for the simulation of biological and applied neural networks but also in real-time applications such as the conttoller or "brain" of a robot. This work has been pioneered using a commercial NCUBE hypercube at Oak Ridge National Laboratory [Bahren 87]. 

Protein Dynamics 
An importlmt area of scientific computation in biology and chemistty involves the dynamics of large protein molecules. This is treated as a particle dynamics problem of the type discussed in Chaps. 9 and 16. Since the interatomic electrical forces are long range one can usually employ the algorithm of Chap. 9 even though we may typically ignore the screened potential of atoms that are widely separated. In fact, the implementa- tion issues are not very different from those in a circuit simulation; a protein forms a cir- cuit whose elements are the atoms and whose connection is defined by the interatomic force. This correspondence is an example of the general equivalence given by the theory of complex systems described in Chap. 3. 

23-4.3 The Hypercube in Chemistry 

Chemical Reactions 
The hypercube has been employed in a major new algorithm for the detailed simu- lation of three- and four-body chemical reactions [Kuppermann 86]. This simulation includes several components. The first step involves the solution of a finite element problem of the type discussed in Chap. 8. This step is followed by the determination of the lowest eigenfunctions of a sparse matrix using the subspace iteration method which can be performed using variants of the general methods described in Chap. 21. The major part of the calculation involves the solution of a coupled-channel SchrOdinger equation which uses the logarithmic derivative method and is dominated by the inversion 

The Hypercube as a Supercomputer in Science and Engineering Chap. 23 

of an M xM matrix where M is the number of channels. The Gauss-Jordan code described in Sec. 21-5 was developed for this application. Interesting values of M go up to 1000 and such large problems can profitably use hypercubes with several thousand nodes. 

23-4.4 The Hypercube in Engineering 

Chaos 

Two groups have used the hypercube to determine the fractal dimension of data sets; in one case this corresponded to experimental plasma data and in another to trajec- tories coming from the solutions of ordinary differential equations [Theiler 86, 87 and Lorenz 87]. We have already described the basic idea in Sec. 9-5 where we saw how the long-range force algorithm can be used to calculate the correlation function. 

Computational Fluid Dynamics In general, computational fluid dynamics uses the techniques described in Chaps. 7 and 8 for the solution of partial differential equations. The importance of turbulent flow introduces some important new issues. Investigations have examined flow at high Reynold's number using vortex methods, where the solution of the differential equations is exchanged for a study of the dynamics of independent vortices. These vortices effec- tively interact with a long-range force and so one can use the method of Chap. 9 to achieve a hypercube implementation of high efficiency [Baden 87, Leonard 80, 87]. We also note that improved sequential algorithms for long-range interactions have recently been developed [Barnes 86] and one may be able to perform this calculation in time com- plexity N IIlogN II where N II is the number of vortices. Preliminary hypercube implemen- tations of Barnes and Hut's algorithm show promising efficiency. 
The dynamic nature of the irregularities produced by turbulence poses algorithmic challenges even for sequential machines. It is probably best to use an underlying mesh that changes or adapts as the solution changes. Work is under way on such an adaptive mesh for use on the hypercube in the context of the multigrid solution method [Van de Velde 87a, b]. As discussed in Chap. 8, the multigrid method can be efficiently imple- mented on the hypercube. One ambitious goal is to combine both the mesh adaption and the hypercube decomposition into a single step, since both need similar optimization methods. Note that the need for adaptive meshes implies that even on a sequential machine, the user can be concerned only with the local problem. This feature renders the transition to the hypercube particularly natural, since domain decomposition has already been enforced by the locally adapting mesh. 
A new approach to fluid dynamics has been proposed which models the continuum problem in terms of discrete cellular automata [Wolfram 86]. This leads to algorithms similar to the neural network and statistical physics applications. These are efficiently implemented on the hypercube but the regularity and simplicity of cellular automata sug- gests that an SIMD approach with an architecture like the Connection Machine would be more cost-effective [Hayot 87]. 

Sec. 23-4 Scientific Applications on a Concurrent Supercomputer 

449 

Earthquake Engineering 
The methods of Chap. 8 have applications throughout many disciplines. At Caltech they are being used to solve finite element problems that arise in many structural analysis problems including those occurring in earthquake engineering and at the Jet Propulsion Laboratory in the analysis of spacecraft structures. [Lyzenga 85, Nour-Omid 87a, 87b] 

Convolutional Decoding 
Convolutional decoding is used in communication, for example between a space- craft and earth, to decrease the incidence of undetected errors with minimum increase in the volume of information to be transmitted. The Viterbi algorithm is a well-known method of convolutional coding whose complexity increases exponentially with the number of states. It has been shown that the structure of this algorithm is formally identi- cal to that of the FFf , and hence that the hypercube represents an excellent architecture for a parallel implementation of this algorithm [pollara 85, 86]. The performance analysis is very similar to that in Chap. 11. The algorithm is sufficiently simple that real- istic use of it could benefit from a specialized node optimized for this problem. 

Ray Tracing in Computer Graphics 
Ray tracing is a technique used to render computer graphics images of three- dimensional models. It is time consuming but leads to very realistic images. The picture is divided into a two-dimensional mesh of pixels and several rays are run through each pixel. These rays are propagated according to the laws of optics and interact with the environment by refraction and reflection. Two kinds of decompositions are relevant here. The calculation is rather easily decomposed, since each pixel is independent and each processor can run rays independently. However, one must use the scattered decom- position for the pixels to achieve load balance, because pixels near a complicated part of the picture take longer to process than those in a dull background. On the other hand, the databases describing the model for the image can be very large and in general also require decomposition which is, however, much harder to derive. This issue is related to the general load-balancing problem described in Sec. 3-8 and is a topic of current research. It is expected that the hypercube will still perform well even when the data base is decomposed; the pixel decomposition leads to negligible inefficiencies of 1-2% [Goldsmith 86, 87]. 

23-4.5 Geophysics 
The use of the hypercube in geophysics at Caltech is particularly impressive as the group led by Clayton and Hager has been able to use the hypercube on a day-to-day basis for many different applications [Clayton 87]. 

450 

The Hypercube as a Supercomputer in Science and Engineering Chap. 23 

Seismic Waves 
The example of Chap. 7 is indicative of the application of the hypercube to the study of seismic waves. These are typically solved by finite difference methods which, as described in Chap. 7, work as well on the hypercube for the fourth-order differencing as for the standard second-order approximation. New applications being explored include nonuniform media for which the optimal methods use a mixture of full numeric and partially analytic methods. This combination leads to irregularities in the computa- tional complexity per grid point and to nontrivialload-balancing issues. 

Geodynamics 

Finite element methods as discussed in Chap. 8 have been employed with a precon- ditioned conjugate gradient iterative solver. The study of the earth's mantle is reduced to one of thermal convection in an incompressible medium. Three-dimensional problems require large memory to yield good efficiencies for the reasons outlined in Chap. 3. 

Tomography and Normal Modes 
Two types of geophysical calculations use the hypercube in a different fashion where each node independently calculates part of the answer. In tomography, ray tracing is used to propagate acoustic waves through the earth. The propagation time, which is sensitive to the structure of the earth, is obtained by inversion from the observed timing data. In a normal mode analysis, a set of synthetic seismograms is compiled for a given model of the earth and a particular set of earthquake source parameters. The signal is analyzed into separate modes for each eigenfrequency of the earth, and each mode is cal- culated separately on a single processor node. These two applications are characterized by essentially 100% concurrent efficiency. 

23-4.6 Physics 

Computational Astrophysics 
One particularly interesting problem involves a study of the evolution of the large- scale structure of the universe on the hypercube [Salmon 86]. This employs the particle in a cell (PIC) algorithm, which involves both particle dynamics (galaxies evolving under Newton's laws) and a mesh-based algorithm. The galaxies are "smeared" to derive a mass density on a mesh, and then the FFT of Chap. II is used to calculate the long-range component of the gravitational potential. This reduces a problem of complexity N i to one that is N g log N g , where N g is the number of galaxies in the simulation. PIC codes involve an interesting conflict between the cell and particle decompositions. These will not be simultaneously load-balanced if the distribution of mesh points does not match the particle density. 
In many cases, this presents no serious problem as the easily load balanced FFT dominates the poorly balanced particle stage. Further investigation of a reformulation of 

Sec. 23-4 Scientific Applications on a Concurrent Supercomputer 

451 

the problem using a (galaxy) clustering algorithm to replace the FFr is under way. This approach has the same N g log N g calculational complexity and should be easier to load balance [AppeI85, Barnes 86, Greengard 87]. 

High-Energy Physics 
Lattice gauge theory calculations were described in Chap. 13 and have been a cen- tral theme of our hypercube use at Caltech. Roughly twenty separate lattice gauge calcu- lations have been performed on the hypercube, and most of these have been published [Fox 86fJ .The theory is very complex, and for this reason lattice gauge calculations make high efficiency use of the hypercube even for small volumes, such as 4x4x4x16 four-dimensional mesh in each node when the surface to volume ratio is high. The regu- larity of the current numerical formulations leads to rather straightforward concurrent decompositions. 

Condensed Matter 
The regular nearest-neighbor Monte Carlo algorithm encountered in the lattice gauge theory is neatly complemented by some of the condensed matter Monte Carlo cal- culations performed on the hypercube. In the study of the melting of a two-dimensional solid, an irregular short-range but not nearest-neighbor problem is involved, and as men- tioned in Sec. 13-7, one needs a subtle algorithm to both obtain good efficiency and satisfy the constraint of detailed balance [Johnson 86]. A Monte Carlo study of a long- range force problem in a two-dimensional gas requires a very different algorithm from that in Chap. 9 for the long-range dynamics problem. Detailed balance implies that only one particle can be updated at a time and care is required to ensure that one can efficiently decide which particle to update in a concurrent algorithm [Fucito 85]. 

Granular Physics 
An intuitively appealing application of the hypercube involves the simulation of wind-driven and gravity-driven motion of a collection of sand grains. The conventional continuum approximations are not used, but rather each grain is moved separately in accordance with Newton's laws. This method is intrinsically very time-consuming and is perhaps only worth pursuing if one believes that computer performance will increase substantially in the future. This simulation is a particle dynamics problem of the type discussed in Chap. 16. The sand grains interact by contact only, and define an irregular but pure nearest-neighbor algorithm. The time required to calculate the grain-grain force is typically so large that the node-to-node communication costs are negligible. Load imbalance represents the only serious impact on efficiency, although in practice even this is of small importance. It is amusing to note that the initial hypercube implementation had an efficiency £ of 3! One part of the calculation involves the determination of which sand grains touch, and this was implemented on the sequential machine as a search of a list of all Ng (number of grains) grains, which requires a time of order Ng2. The con- current algorithm is implemented with a spatial decomposition which means that this step 

452 

The Hypercube as a Supercomputer in Science and Engineering Chap. 23 

only needs to search the local and neighboring nodes. Such a search takes a time of order (Ng/N)2 on the hypercube and results in a an algorithmic speedup of order N4 Of course, this was a case in which the sequential algorithm was intrinsically poor and should also have used a spatial decomposition (or geometric hashing) method. When the concUlTent implementation is compared to the sequential version using this improved algorithm, the efficiency assumes a more sensible value near unity with load-imbalance as the dominant overhead [Werner 87]. 

23-5 The Last Word 
We remind readers of our experience that hypercubes exhibit high performance on most large scientific problems. Other concurrent architectures are also successful. If you are interested in cost-effective computing with very high capability (1012 flops = 1 Teraflop) in the future. we believe that it would be wise to consider the use of concurrent computers. 

References 
Note many internal Caltech reports are referred to as C3p memos. These may be obtained from the Caltech Concurrent Computation Program as explained in the Pream- ble to this book. 

Adams 82 

Adams84 

Akl 85 

Aldcroft 87 

Allakhverdiyev 81 

Aloisio 87 

Amdahl 67 

ANSI 87 

Adams, L. M., "Iterative algorithms for large sparse linear systems on parallel computers," Ph.D. Thesis, University of Virginia (1982). 

Adarns, L. M. and Voight, R. G., "Design, development, and use of the finite element machine," in Large Scale Scientific Computation, Academic Press, New York (1984), 301. 

Akl, S. G., Parallel Sorting Algorithms, Academic Press, New York (1985). 

Aldcroft, T., Cisneros, A., Fox, G. C., Furrnanski, W., and Walker, D. W., "LU decomposition of banded matrices and the solution of linear systems on hypercubes," Caltech report C3p -348, in preparation, 1987. 

Allakhverdiyev, N. M., and Sarafuliyeva, S. S., "Choice of mul- tiprocessor system configuration for digital signal processing", translated in USSR Report -Cybernetics. Computers and Automa- tion Technology, Foreign Broadcast Information Service, JPRS 83843, July 7, 1983. 

Aloisio a., Fox, a., Kim, J. S., and Veneziani, N., "A concurrent implementation of the prime factor algorithm on the hypercube," unpublished Caltech report C3p -468 (1987). 

Amdahl, G. M., "Validity of the single processor approach to achieving large-scale computing capabilities," in AFIPS Confer- ence Proceedings 1967.30. AFIPS Press, Montvale, N.J. (1967), 483. 

Draft Proposed American National Standard for Information Sys- terns -Programming Language C, 1987. Accredited Standards Committee, X3 Secretariat, 311 First St N.W., Suite 500, Wash. DC 20001. 

453 

454 

Appel 85 

Arvind 87 

Ashcroft 81 

Askew 86 

Athens 87 

ATT84 

HadeD 87 

Barhen 87 

Barkai 84 

Barnes 86 

References 

Appel, A.W., "An efficient program for many-body simulation,' SlAM J. Sci. Stat. Comput., 6, (1985), 85. 

Arvind and Nikhil, R. S., "Executing a program on the MU tagged-token dataflow architecture," PARLE Conference, in Lec- ture Notes in Computer Science. 259, edited by G. Goos and I. Hartmanis, Springer-Verlag, New York (1987), 1. 

Ashcroft, I" Eldridge, R, H" Paulson, R. W., and Wilson, G. A., Programming with Fortran 77, Published by Granada Publishing Ltd" St, Albans, Hefts., 1981. 

Askew, C. R., Carpenter, D. B., Chalker, I. T., Hey, A. I. G., Nicole, D. A., and Pritchard. D. I., "Monte carlo simulations on transputer arrays", Computer Physics Communications, 42 (1986), 21. 

Proceedings of ICS87, International Conference on Supercomput- ing, published by Springer-Verlag, New York, as A Lecture Note in Computer Science, Edited by C. Polychronoupolos. 

UN/X System V (Release 2.0) Programmer Reference Manual. sec- lions 2 and 3. 1984. 

Baden, S. B., "Run-time partitioning of scientific continuum calcu- lations running on multiprocessors," Ph.D. Dissertation, UC Berkeley,1987. 

Barhen, J., Einstein, J. R., Jorgensen, C. C., "Advances in con- current computation for machine intelligence and robotics," in the Proceedings of the Second International Conference on Supercom- puting, Published by the International Supercomputing Institute Inc., St. Petersburg, Florida, May 1987, Caltech report C3P-418. 

Barkai, D., Moriarity, K. J. M., and Rebbi C., "A highly optimized vectorized code for Monte Carlo simulations of SU(3) lattice gauge theories," Computer Physics Communications, 32 (1984), 1. 

Barnes, I. and Hut, P., "A hierarchical O(NlogN) force calculation algorithm," Nature, 324, (1986),446. 

References 

Barron 83 

Batcher 68 

Hatcher 85 

Bathe 82 

Baudet 78 

Beetem 86 

Bell 85 

BreadeD 86 

Brooks 84 

Brown 83 

Buzbee 87 

Barron, I. M., Cavill, P., May, D., and Wilson, P., transputer,"Electronics (Nov. 17, 1983), 109. 

Batcher, K. E" "Sorting networks and their applications," in AFIPS Conference Proceedings 1968, 32, AFIPS Press, Montvale, NJ. (1968), 307. 

Batcher, K. E., "MPP: A high speed image processor," in Algo- rithmically Specialized Parallel Computers, Academic Press, New York (1985). 

Bathe, K-J., Finite Element Procedures in Engineering Analysis, Prentice-Hall, Englewood Cliffs, NJ. (1982). 

Baudet. G. and Stevenson, D., "Optimal sorting algorithms for parallel computers," IEEE Transactions on Computers. C-27 , (1987), 84. 

Beetem, J., Denneau, M., and Weingarten, D., "GF 11" in Proceedings of the Conference on Frontiers of Quantum Monte Carlo, September 3-6, 1985 at Los Alamas, edited by J. E. Guber- naris, Journal of Statistical Physics 43, numbers 5/6 (June 1986). 

Bell, C. G ., "Multis: a new class of multiprocessor computers,' Science. 228, (1985) 462. 

Breaden, M., Chang, D., Chen, S., and O'Dea, I., "SURFCUBE: the development of a small hypercube for personal computers," (October 1986), Unpublished Caltech report C3p -374. 

Brooks, E. Ill, et al., "Pure gauge SU(3) lattice gauge theory on an array of computers," Phys. Rev. Lett., 52, (1984), 2324, Caltech report C3p -65. 

Brown, F. B., "Vectorized Monte Carlo methods for reactor lattice analysis." Talk given at Conference on Monte Carlo Methods and Future Computer Architectures, Brookhaven National Laboratory , (April 2-5, 1983). 

Buzbee, B., "Supercomputers: values and trends," Int. Journal of Supercomputer Applications 1, (1987) 100. 

456 

ChaD 86 

ChaD 87 

Christ 86 

Chu 87 

Cisneros 85 

Cisneros 87 

Clayton 84 

Clayton 87 

Clementi 87 

Cooley 65 

References 

Chan, A., Saad, y ., and Schultz, M., "Solving elliptic partial dif- ferential equations on dle hypercube multiprocessor", Supercom- puter,13, (1986), 35. 

Chan, T. F. and Tuminaro, R. S., "Implementation of multigrid algorithms on hypercubes," published in Hypercube Mu/tiproces- sors.1987, edited by M. T. Heath, SlAM (1987) 730. 

Christ, N. H., "Lattice gauge theory with a fast highly para1lel computer," in Proceedings of the Conference on Frontiers of Quantum Monte Carlo, September 3-6, 1985 at Los Alamos, edited by J. E. Gubematis, Journal of Statistical Physics 43, numbers 5/6 (June 1986). 

Chu, E. and George, A., "Gaussian elimination with partial pivot- ing and load balancing on a multiprocessor," Para/lei Computing, 5, (1987), 65. 

Cisneros, A., "Scalar products on the hypercube," Unpublished Caltech report C3p -199 (1985). 

Cisneros, A., " A communications system for irregular local interaction problems on a concurrent computer," Comp. Phys. Co~., 46, (1987),35, Caltech report C3p-317. 

Clayton, R. W., "Finite difference solutions of the acoustic wave equation on a concurrent processor," Unpublished Caltech report C3p -89 (1984). 

Clayton, R., Ha:ger, B. and Tanimoto, T., "Applications of con- current processors in geophysics," in Proceedings of the Second International Conference on Supercomputing, Published by the International Supercomputing Institute Inc., St. Petersburg, Florida. (May 1987), Caltech report C3p -317. 

Clementi, E. and Debich, J., "Large scale parallel computation on a loosely coupled array of processors," printed in [Dongarra 87]. 

Cooley, J. W. and Tukey, J. W., "An algorithm for the machine calculation of complex fourier series", Mathematics of Computa- tion,19 (1965),297. 

References 

Creutz 83 

Dally 86 

Dantzig 68 

DAP 79 

Dennis 74 

Dewdney 84 

Dippe 84 

Dippe 85 

Dongarra 85 

Dongarra 87 

Donath 79 

Duff 84 

457 

Creutz, M., Quarks, Lattices and Gluons, Cambridge University Press, Cambridge, Great Britain (1983). 

Dally, W" and Seitz, C" "A VLSI architecture for concurrent data structures," J, Distributed Systems 1 {1986), 187, 

Dantzig, G. B., Linear Programming and Extensions, Princeton University Press, Princeton, N.J. (1968). 

"The DAP approach," Infotech State of the Art Report: Supercom- puters. 2 edited by Jesshope, C. R. and Hackney, R. W., Infotech Inti. Ltd., Maidenhead (1979), 311-29. 

Dennis, I. B., "First version of a dataflow procedure language," in Proc. Programming Symposium, Paris 1974, edited by G. Goos and I. Hartrnanis, Springer-Verlag, New York (1974). 

Dewdney, A. K., "Computer recreations," Scientific American, (December 1984). 

Dippe, M. E. and Swensen, I. A., "An adaptive subdivision algo- rithm and parallel architecture for realistic image synthesis," SIG- GRAPH. 84 Conference Proceedings, (1984), 149. 

Dippe, M. A. Z. and Wold, E. H., "Antialiasing through stochastic sampling," Computer Graphics 19, 69. Also appeared in SIG- GRAPH' 85 Conference Proceedings, (1985). 

Dongarra, J. J. and Sorensen, D. C. "A fully parallel algorithm for the symmetric eigenvalue problem," Second SlAM Conference on Vector and Parallel Processing in Scientific Computing, Virginia, (Nov.20, 1985). 

Experimental Parallel Computing Architectures, edited by I. I. Dongarra, North-Holland, Amsterdam (1987). 

Donath, W. E., "Placement and average interconnection lengths of computer logic," IEEE Trans. Circuits and Systems 16, (1979) 272. 

Duff, S. I., "Supercomputers in Europe," Parallel Computing 1 (1984) 321. 

References 

Duff 87 

FelteD 85a 

FelteD 8Sb 

FelteD 863 

FelteD 86b 

FelteD 87 

Feynman 65 

Forty 85 

Flower 86 

Fox 843 

Update of [Duff 84] published in the Proceedings of ICS 87, Inter- national Conference on Supercomputing published by Springer- Verlag, New York, as Lecture Note in Computer Science, edited by C. Polychronoupolos. 

FelteD, E., Karlin, S., and Otto, S., "Sorting on a hypercube," to appear in the Journal of Parallel and Distributed Computing, Cal- tech report, C3p -244 (1985). 

Felten, E., Karlin, S., and Otto, S., "The b"aveling salesman prob- lem on a hypercube, MIMD Computer," Proceedings of 1985 International Conference of Parallel Processing, St Charles, ll..., 1985, Caltech report C3p -93b. 

Felten, E., Morison, R., Otto, S., Barish, K., Fiitland, R., and Ho, F., "Chess on the hypercube," published in Hypercube Multipro- cessors. 1987, edited by M. T. Heath, SlAM (1987) 327, Caltech report C3p -383. 

Felten, E., "Linear programming on a distributed memory mul- tiprocessor," unpublished Caltech report C3p -467(1987). 

Felten, E., "Parallel branch and bound algorithms," Unpublished Caltech report C3p -457 (1987). 

Feynman, R. p ., and Hibbs, A. R., Quantum Mechanics and Path Integrals, McGraw-HiII, New York (1965). 

Forty, A, J" "Future facilities for advanced research computing." Joint working party report for Advisory Board for the Research Councils, Computer Board for Universities, and Research Councils University Grants Committee, (June, 1985) Dept. of Education and Science, Elizabeth House, London. 

Flower, I., Otto, S. W ., and Salama, M., " A preprocessor for finite element problems," to appear in Proceedings, Symposium on Parallel Computations and Their Impact on Mechanics, ASME Winter Meeting, Dec. 14-16," Boston, Mass., {1987), Caltech report C3p -292. 

Fox, G. and Otto, S., " Algorithms for concurrent processors," phy- sics Today (May 1984), Caltech report C3p-71. 

References 

Fox 84b 

Fox 84c 

Fox 84d 

Fox 85a 

Fox 8Sb 

Fox 85c 

Fox 863 

Fox 86b 

Fox 86c 

Fox 86d 

459 

Fox, G., "Use of concurrent processors,in (high-energy physics) data analysis," Unpublished Caltech report, C3p -129 (1984). 

Fox, G., "On the sequential component of computation," Unpub- lished Caltech report, C3p -130 (1984). 

Fox, G., "Square mabix decomposition: symmebic, local, scat- tered," Unpublished Caltech report, C3p -97 (1984). 

Fox, G., Otto, S. W., Umland, E. A., "Monte Carlo physics on a concurrent processor" in Proceedings of the Conference on Fron- tiers of Quantum Monte Carlo, September 3-6, 1985 at Los Alamos, edited by J. E. Gubematis, Journal of Statistical Physics 43, numbers 5/6 (June 1986), Caltech report C3p -214. 

Fox, G., Hey, A. J. G, and Otto, S., "Mabix algorithms on the hypercube I: mabix multiplication," Parallel Computing, 4, (1987),17, Caltech report C3p-206. 

Fox, G., "The perfonnance of the Caltech hypercube in scientific calculations: A preliminary analysis," Supercomputers- Algorithms. Architectures. and Scientific Computation, edited by F. A. Matsen and T. Tajima, University of Texas Press {1987), Cal- tech report CJp -161. 

Fox, G. and Otto, S., "Concurrent computation and the theory of complex systems," published in Hypercube Multiprocessors, 1986, edited by M. T. Heath, SlAM (1986) 244, Caltech report C3p -255. 

Fox, G. and Furrnanski, W., "Optimal communication algorithms on the Hypercube" Unpublished Caltech report C3p -314 (1986). 

Fox, G. and Funnanski, W., "Communication algorithms for regu- lar convolutions on the hypercube," published in Hypercube Mul- tiprocessors. 1987, edited by M. T. Heath, SlAM (1987) 223, Cal- tech report C3p -329. 

Fox, G., "Load balancing and sparse mabix-vector multiplication on the hypercube," to be published in Proceedings of IMA Workshop, Minnesota (November 1986), edited by M. Schultz, Caltech report C3p -327B. 

460 

Fox 86e 

Fox 86f 

Fox 86g 

Fox 86h 

Fox 86i 

Fox 87 

Frankel 86 

Frederickson 83 

Frederickson 87 

References 

Fox, G., "Iterative full mabix-vector multiplication on the hyper- cube," Unpublished Caltech report C3p -336 (1986). 

Fox, G., " Annual report of the Caltech Concurrent Computation Program 1985-86," published in Hypercube Multiprocessors, 1987, edited by M. T. Heath, SlAM (1987) 353, Caltech report C3p-290B. 

Fox, G., " A review of automatic load balancing and decomposition methods for the hypercube," to be published in Proceedings of IMA Workshop, Minnesota (November 1986), edited by M. Schultz, Caltech report C3p -385. 

Fox, G., Kolawa, A., and Williams, R., "The implementation of a dynamic load balancer," Published in Hypercube Multiprocessors, 1987, edited by M. T. Heath, SlAM (1987) 114, Caltech report C3p-328. 

Fox, G. and Funnanski, W., "Load balancing by a neural network," Unpublished Caltech report, C3p -363 (1986). 

Fox, G., "Domain decomposition in disbibuted and shared memory environments I," to be published as Lecture Note in Com- puter Science, Springer-Verlag, New York, edited by C. Polychro- nopoulos, Caltech report C3p -392 (1987). 

Frankel, A., and Clayton, R. W ., "Finite difference simulations of seismic scattering: implications for the propagation of short- period seismic waves in the crust and models of crustal hetero- geneity," I. Geophys. Res. 91, (1986), 6465, Caltech report C3p- 203. 

Frederickson, P., Hiromoto, R., Jordan, T., Smith, B., Warnock, T., "Pseudo-random trees in Monte Carlo". proceedings, Conference on Monte Carlo Methods and Future Computer Architectures, Brookhaven National Laboratory (April 2-5, 1983). 

Frederickson P. 0. and McBryan 0. A., "Parallel superconvergent multigrid," to be published in Applied Math. Series, Marcel- Decker, (1987). 

References 

Frenkel 86 

Fucito 85 

Furmanski 86 

Furmanski 87a 

Furmanski 87b 

Gabriel 86 

Gaines 86 

Gaines 87 

Gehringer 87 

Geist 86 

461 

"Special issue on parallelism; Connection Machine and shared memory ," edited by K. A. Frenkel, Commumications of the ACM 29, (1986), pp.1168-1239. 

Fucito, F., and Solomon, S., "Monte Carlo parallel algorithm for long-range interactions," Computer Physics Communications 34, (1985), 225, Caltech report C3p -79b. 

Furmanski, W. and Fox, G., (1986), Caltech report C3p -386. 

"Matrix", paper in preparation, 

Furmanski, W., Bower, J. M., Nelson, M. E., Wilson, M. A., and Fox, G., "Pirifol1n (Olfactory) cortex model on the hypercube," (February 1987), Caltech report C3p -404. 

Furrnanski, W. and Fox, G. C., "Hypercube communication for neural network algorithms," (February 1987), Caltech report C3P-405. 

Gabriel, R. p ., "Massively parallel computers: the Connection Machine and Non-Von," Science 231, (1986) 975. 

Gaines, I., Areti, H., Atac, R., Riel, I., Cook, A., Fischler, M., Hance, R., Husby, D., Nash, T., and Zmuda, T., "The ACP mul- tiprocessor system at Fermilab," invited talk at 1987 Asilomar Conference on Computing in High Energy Physics, published in Computer Physics Communications 45, (1987) 323. 

Gaines, I. and Nash, T ., "Use of new computer technologies in ele- mentary particle physics," Ann. Rev. Nucl. Part. Sci., 37 (1987), edited by J. D. Jackson, published by Annual Reviews Inc., 4139 El Camino Real, P. 0. Box 10139, Palo Alto, CA94303-0897. 

Gehringer, E. F., Siewiorek, D. P. and Segall, Z., "Parallel process- ing: dIe Cm* experience," published by Digital Equipment COIp., Bedford, Mass. (1987). 

Geist, G. A. and Heath, M. T., "Matrix factorization on a hyper- cube multiprocessor," Hypercube Multiprocessors 1986, ed. by M. T. Heath, SlAM, Philadelphia (1986), 161. 

462 

Geist 87 

Gilbert 58 

Goddard 85 

Goldsmith 86 

Goldsmith 87 

Good 58 

Gottlieb 86 

Gottschalk 87 

Grassberger 83 

Greengard 87 

Grunwald 87 

Baynes 82 

References 

Geist, G. A. and Romine, C. H., "LU factorization algorithms on distributed-memory multiprocessor architectures," SlAM I. Sci. Stat. Comput., to appear (1987). 

Gilbert, E. N., "Gray codes and paths on the n-cube," Bell System Technical Journal. 37, (May 1958), 815. 

Goddard, W. A. III, "Theoretical chemistry comes alive: Full partner with experiment," Science 227, (1985),917. 

Goldsmith, I., and Salmon, I., "Static and dynamic database distri- bution for graphics ray tracing on the hypercube," Unpublished Caltech report C3p -360 (1986). . 

Goldsmid1, J. and Salmon, J ., II Automatic creation of object hierar - chies for ray tracing," IEEE, CG and A, 14 (1987), Caltech report C3p -295. 

Good, I. J ., "The interaction algorithm and practical Fourier analysis," I. Royal Statistical Society 208, (1958),361. 

Gottlieb, A., " An overview of die NYU ultracomputer project," printed in [Dongarra 87] . 

Gottschalk, T. D., "Multiple track initiation on a hypercube," in the Proceedings of the Second International Conference on Supercom- puting. Published by the International Supercomputing Institute Inc., St. Petersburg, Florida (May 1987), Caltech report C3p -398. 

Grassberger, P., and Procaccia, I., "Measuring dle strangeness of strange attractors," Physica 9D (1983), 189. 

Greengard, L., "The rapid evaluation of potential fields in particle systems," Yale research report Y ALEU / DCS / RR-533 (April 1987). 

Grunwald, D. C. and Reed, D. A., "Benchmarking hypercube hardware and software," Published in Hypercube Multiprocessors. 1987. Edited by M. T. Heath, SlAM (1987) 169. 

Baynes, L. S., Lau, R. L., Siewiorek, D. P. and Mizell, D. W., "A survey of highly parallel computing," Computer (Ian. 1982),9. 

References 

Hayot 87 

Heath 87 

Held 70 

Held 71 

HilUs 85 

HilIis 87 

Hipes 86 

Ho 86a 

Ho 86b 

Hoare 62 

Hoare 78 

Hockney 81a 

463 

Hayot, F., Mandal, M. and Sadayappen, P., "Implementation and performance of a binary lattice gas algorithm on parallel processor systems," Ohio State University report (1987). 

Heath, M. T., "Hypercube applications at Oak Ridge National Laboratory," in Hypercube Multiprocessors 1987, ed. by M. T. Heath, SlAM, Philadelphia (1987), 395. 

Held, M. and Karp, R. M., "The b'aveling salesman problem and minimum spanning b"ees," Oper. Res. 18, (1970) 1138. 

Held, M. and Karp, R. M., "The b"aveling salesman problem and minimum spanning b"ees: Part II," Mathematical Programming 1 (1971) 6. 

Hiltis, W. D., The Connection Machine, MIT Press, Cambridge, Mass. (1985). 

Hillis, W. D., "The Connection Machine," Scientific American, (June 1987) 108. 

Hipes, P. and Kuppermann, A., "Gauss-Jordan matrix inversion with pivoting on the hypercube," Unpublished Caltech report, C3p-347, (1986). 

Ho, C- T ., Johnsson, S. L., "Distributed routing algorithms for broadcasting and personalized communication in hypercubes," Proceedings of IEEE 1986 International Conference on Parallel Processing, (1986). 

Ho, C- T ., Johnsson, S. L., "Matrix transposition on Boolean n- cube configured ensemble architectures," Yale report Y ALEUIDCS/I'R-494 (September 1986). 

Hoare, C. A. R., "Quicksort," Computer I. 5, (October 15, 1962) 10. 

Hoare, C. A. R., "Communicating sequential processes" Communi- cations of the ACM 21, (1978) 666. 

Hackney, R. W., and Eastwood, ]. W., Chapter 8, in Computer Simulation Using Particles, McGraw-Hill, New York (1981). 

464 

Hockney 81b 

Hopfield 82 

Hopfield 86 

Hughes 87 

Ipsen 87 

Jefferson 85 

Jennings 77 

Johnson 84 

Johnson 85 

Johnson 86 

Johnsson 85 

References 

Hackney, R. W., and Jesshope, C.R., Parallel Computers. Adam Hilger, Bristol, Great Britain (1981). 

Hopfield, J. J., "Neural networks and physical systems with emer- gent collective computational abilities," Proc. NatL. Acad. Sci USA. 79 (1982) 2554. 

Hopfield, I. I. and Tank, D. W., "Computing with neural circuits: a model," Science 233 {1986),625. 

Hughes, T. J., The finite element method: linear static and dynamic finite element analysis. Prentice-Ha1I, Englewood Cliffs, N.J. (1987). 

Ipsen, I. C. F. and Jessup, E., "Two methods for solving the sym- metric tridiagonal eigenvalue problem on the hypercube," pub- lished in Hypercube Multiprocessors. 1987, edited by M. T. Heath, SlAM (1987) 627. 

Jefferson, D., and Sowizral, H., "Fast concurrent simulation using the time-warp mechanism," SCG Conference on Distributed Simu- lation. San Diego, CA. (January 1985). 

Jennings, A., Matrix Computation for Engineers and Scientists, John Wi1ey & Sons, New York (1977). 

Johnson, S., "Combining parallel and sequential sorting on a Boolean n-cube," Proceedings, IEEE 1984 International Confer- ence on Parallel Processing, (1984) 444-48. 

Johnson, M. A., "The interrupt-driven communication system,' Unpublished Caltech report C3p -137 (1985). 

Johnson, M. A., "Concurrent computation and its application to the study of melting in two dimensions," Caltech Ph.D. dissertation (1986), Caltech report C3p -268. 

Johnsson, L., "Band-matrix systems solvers on ensemble architec- tures," in Supercomputers -Algorithms, Architectures and Scientific Computation. eds. T. Tajima and F. A. Matsen, Univer- sity of Texas Press (1987). 

References 

Jobnsson 87 

Kalos 86 

Karin 87 

Karlin 85 

Karmarkar 84 

Karp 77 

Karplus 87 

Kirkpatrick 83 

Kit tel 76 

Knuth 73a 

Knuth 73b 

465 

Johnsson, L. and Ho, C-T., "Matrix multiplication on Boolean cubes using generic communication primitives," to appear in Proceedings of the ARO Workshop on Parallel Processing and Medium-Scale Multiprocessors. (1986). 

Kalos, M. H., "Monte Carlo methods and the computers of the future," in Supercomputers -Algorithms. Architectures, and Scientific Computation. edited by F. A. Matsen and T. Tajima, University of Texas Press (1987). 

Karin, S. and Smith, N. P., The Supercomputer Era, Academic Press, New York (1987). 

Karlin, S., Suggs, B., "A 68010 based concurrent processor," Cal- tech EE91 term paper (fall 1985), unpublished Caltech report C3p-246. 

Karrnarkar, N., f'A new polynomial time algorithm for linear pro- gramming," Combinatorica 4 (1984), 373. 

Karp, R. M., "Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane," Math. of Operations Res. 2,3 (1977),209. 

"Multiprocessors and array processors," edited by W .J. Karplus, Proceedings of the Third Conference on Multiprocessors and Array Processors, Simulation Series, 18, The Society for Com- puter Simulation, San Diego (1987). 

Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P., "Optimization by simulated annealing," Science 220, (May 1983), 671. 

Kittel, C., Introduction to Solid State Physics, 5d1 Ed. John Wiley & Sons, New York (1976), 76-82. 

Knuth, D. E., Sorting and Searching, The Art of Computer Pro- gramming, Vol. 3, Addison-Wesley, Reading, Mass. (1973). 

Knuth, D. E., Seminumerical Algorithms, The Art of Computer Programming, Vol. 2, Addison-Wesley, Reading, Mass. (1973). 

466 

Knuth 73c 

Kolawa 85 

Kolawa 86 

Kriimer 87 

Kung 80 

Kuck 86 

Kuppermann 86 

Landman 71 

Lazou 87 

Leonard 80 

Leonard 87 

References 

Knuth, D. E., Fundamental Algorithms. The Art of Computer Pro- gramming, Vol.l , Addison-Wes1ey, Reading, Mass. (1973). 

Kolawa, A. and Otto, S. W., "Performance of the Mark II and IN1EL hypercubes," published in Hypercube Multiprocessors. 1986, edited by M. T. Heath, SlAM (1986) 272, Caltech report C3P-254. 

Kolawa, A. and Fox, G., "Concurrent searching of a database-an application of the hypercube to symbolic quantum chromodynam- ics," unpublished Caltech report C3p -182B, (1986). 

Kriimer, 0. and Miihlenbein, H., "Mapping strategies in message based multiprocessor systems," PARLE Conference, in Lecture Notes in Computer Science. 258, edited by G. Goos and I. Hart- manis, Springer-Verlag, New York (1987), 213. 

Kung, H. T. and Leiserson, C. E., Introduction to VLSI systems, Sec. 8.3, by C. Mead and L. Conway, Addison-Wesley, Reading, Mass. (1980). 

Kuck, D. I., Davidson, E. S., Lawrie, D. H., Sameh, A. H., "Paral- lel supercomputing today and the Cedar approach," Science 231, 
(1986),967. 

Kuppermann, A., and Hipes, P. G., I. Chem Phys. 84 (1986), 55. 

Landman, B. S. and Russo, R. L., "On a pin versus block relation- ship for partitions of logic graphs," IEEE Trans. Comp. C20, (1971) 1469. 

Lazou, C., Supercomputers and Their Use, Oxford University Press, Oxford, Great Britain, (1987). 

Leonard, A. "Vortex methods for flow simulation," J. Computa- tional Physics 37 (1980), 289. 

Chua K. and Leonard, A" "Three dimensional vortex methods and the vortex reconnection problem," Bulletin of the American Physi- cal Society, to be published (1987), 

References 

Li86 

LiB 65 

LiB 73 

Lorenz 87 

Luenberger 84 

Lyzenga 85 

Mandelbrot 79 

Marinari 86 

Martin 67 

Mead 80 

Meier 84 

Messina 87 

467 

Li, P. P., "Parallel sorting on the Ametek/SI4," (Sept. 1986) avail- able from the Ametek Corporation, Arcadia, CA. 

Lin, S., "Computer solutions of the traveling salesman problem," The Bell System Technical Journal 44, (December 1965), 2245. 

Lin, S. and Kernighan, B. W .,"An effective heuristic algorithm for the traveling salesman problem," Oper. Res. 21 {1973),498. 

Lorenz, J. and Noerdlinger P. D., " Analysis of strange attractors on the hypercube," Unpublished report C3p -400 (1987). 

Luenberger, D., Linear and Nonlinear Programming, 211d Ed., Addison-Wesley, Reading, Mass. (1984). 

Lyzenga, G. A., Raefsky, A., and Hager, B. H., "Finite elements and the method of conjugate gradients on a concurrent processor," in Proceedings of the 1985 ASME International Computers in Engineering. Boston (August 4-8, 1985), Caltech report C3p -164. 

Mandelbrot, B., Fractals: Form, Chance. and Dimension, Free- man, San Francisco, Calif. (1979). 

Marinari, E., !lThe APE computer and lattice gauge theory ,!I Proceedings of the Wuppertal Workshop on Lattice Gauge Theory, edited by R. Buck, K. H. MUtter, and K. Schilling, Plenum Press, New York (1986). 

Martin, R. S., and Wilkinson, I. H., "Solution of symmetric and unsymmetric band equations and the calculation of eigenvectors of band matrices," Numerische Mathematik 9. (1967), 279. 

Mead, C. and Conway L., Introduction to VLSI Systems, Addison- Wesley, Reading, Mass. (1980). 

Meiert D.t "Two-dimensional one-fluid hydrodynamics: an astro- physical test problem for the nearest neighbor concurrent proces- sort" unpublished Caltech report C3p -90 (1984). 

Fox, G. and Messina, P., "Advanced computer architectures," Scientific American. (Oct. 1987). 

468 

Metropolis 53 

Moler 86 

Montry 87 

Morison 86 

Muller 85 

Nassimi 79 

Noerdlinger 86 

Nour-Omid 87a 

Nour-Omid 87b 

O'Neil 87 

References 

Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., Teller, E., "Equation of state calculations by fast computing machines," I. Chem Phys 21 (1953), 1087. 

Moler, C., "Mabix computation on disbibuted memory multipro- cessors," published in Hypercube Multiprocessors, 1986, edited by M. T. Heath, SlAM (1986) 181. 

Montry, G. R. and Renner, R. E., "Parallel processing on an ELXSI 6400," in the Proceedings of the Second International Conference on Supercomputing, Published by the International Supercomputing Institute Inc., St. Petersburg, Florida (May 1987). 

Morison, R. and Otto, S. W ., "The scattered decomposition for finite element problems," Journal of Scientific Computing 2, (1986), Caltech report C3p -286. 

Muller, A., "Element-by-element iterative procedures in structural finite element analysis," Ph.D. thesis, Stanford University (1985). 

Nassimi, D., and Sahni, S., "Bitonic sort on a mesh-connected parallel computer," IEEE Trans. Camp. 27, (1979),2. 

Noerdlinger, P. D. and Walker, D. W., "Discrete Fourier transforms on the Mark n Hypercube," {1986), unpublished Cal- tech report C3p-337. 

Nour-Omid, B., and Park, K. C., "Solving Sb'uctural mechanics problems on the Caltech hypercube machine," Computer Methods in Applied Mechanics and Engineering 6] , (1987) 161. 

Nour-Omid, B., Raefsky, A. and Lyzenga, G., "Solving finite ele- ment equations on concurrent computers," Proceedings of the Sym- posiwn on Parallel Computations and Their Impact on Mechanics. ASME, Boston (Dec. 13-18, 1987). 

O'Neil, E., Allik, H., Moore, S., and Tenenbaum, E., "Finite ele- ment analysis on the BBN Butterfly multiprocessor," in the Proceedings of the Secondlnternationa/ Conference on Supercom- puling. published by the International Supercomputing Institute Inc., St. Petersburg, Florida, (May 1987). 

References 

Ortega 85 

Otto 84a 

Otto 84b 

Palmer 86 

Papadimitriou 82 

Percus 87 

Peterson 85a 

Peterson 8Sb 

Pfister 85 

Pollara 85 

469 

Ortega, I. M. and Voight, R. G., "Solution of partial differential equations on vector and parallel computers," SlAM Review. 27, (1985), 149. 

Otto, S. w., and Stack, I. D., "SU(3) Heavy-quark potential with high statistics," Phys. Rev. Lett.. 52, (1984), 2328, Caltech report C3p-67. 

Otto, s., "Lattice gauge theories on a hypercube computer," Proceedings. Argonne National Laboratory Workshop, Gauge Theory on a Lattice, (1984), Caltech report C3p -91. 

Palmer, I., "The NCUBE: A VLSI parallel supercomputer," Hypercube Multiprocessors, 1986. edited by M. T. Heath, SlAM (1986) 19. 

Papadimitriou, C. H., and Steiglitz, K., Combinatorial Optimiza- tion: Algorithms and Complexity, Prentice-HalI, Englewood Cliffs, N.J. (1982). 

Percus, 0. E. and Kalos, M. H., "Random number generators for ultracomputers," Ultracomputer Note No.114 (Feb. 1987), Courant Institute, NYU. 

Peterson, J. C., et at., "The Mark III hypercube ensemble con- current computer," IEEE 1985 Conference on Parallel Processing, St. Charles, IL., (August 1985), Caltech report C3p -151. 

Peterson, V. L., "Use of supercomputers in computational aero- dynamics," Proceedings of the 1985 Science and Engineering Symposium. Cray Research Inc., Minneapolis (1985). 

Pfister, G. F., et at., "The IBM research parallel processor proto- type (RP3): introduction and architecture," IEEE 1985 Conference on Parallel Processing. St. Charles, IL., (August 1985). 

Pollam, F., "Concurrent Viterbi algorithm on a hypercube," in Proceedings of the 23rd Annual Allerton Conference on Communi- cation Control and Computing, ed. Hajek, B., Munson Jr., D. C., Univ. of illinois, (October 85), Caltech report C3p -208. 

470 

Pollara 86 

Pritchard 87 

Quintan 87 

Rader 68 

Rattner 85 

Reed 87 

Salmon 86 

Salmon 87 

Sameh 85 

References 

Pollara F., "Concurrent Viterbi algorithm with trace-back," in August 1986 Conference of International Society of Optical Engineering, Advanced Algorithms and Architectures for Signal Processing, Vol. 696 of SPIE Proceedings, 204 (1986), Caltech report C3p -462. 

Pritchard, D. J., Askew, C. R., Carpenter, D. B., Glendinning, I., Hey, A. J. G. and Nicole, D. A., "Practical parallelism using tran- sputer arrays," PARLE Conference, in Lecture Notes in Computer Science. 258, edited by G. Goos and J. Hartmanis, Springer- Verlag, New York (1987),278. 

Quinlan, J. and Siewiorek, D., "Baseline measurements of the Mark II hypercube," published in Hypercube Multiprocessors. 1987, edited by M. T. Heath, SlAM (1987) 200. 

Rader, C. M" "Discrete Fourier b"ansforrns when the number of data samples is prime," Proc. IEEE 56, (1968) 1107, 

Rattner, J., "Concurrent processing: A new direction in scientific computing," in Con.f. Proc. 1985 National Computing Conference 54, (1985), 157. 

Reed, D. A., Adams, L. M., and Patrick, M. L., "Stencils and prob- lem partitionings: their influence on the performance of multiple processor systems," IEEE Transactions on Computers. C36, (1987), 845. 

Salmon, J. and Hogan, C., "Correlation of QSO absorption lines in universes dominated by cold dark matter," Monthly Notices of the Royal Astronomical Society, 221, (1986), 93, Caltech report C3p - 211. 

Salmon, J ., "CUBIX: programming hypercubes without program- ming hosts," published in Hypercube Multiprocessors, 1987, edited by M. T. Heath, SlAM (1987), 3, Caltech report C3p -378. 

Sameh, A., "Numerical algorithms on the Cedar system," Second SlAM Conference on Vector and Parallel Processing in Scientific Computing, Virginia, (November 20, 1985). 

References 

Schemer 84 

Schilling 87 

Schmidt 87 

Schwartz 80 

Seitz 843 

Seitz 84b 

Seitz 85 

Shaw 84 

Shell 59 

Siegel79 

Solomon 84 

Theiler 86 

471 

Schemer, J. and Neches, p ., "The genesis of a database computer," IEEE Computer Magazine. (November 1984), 19. 

Schilling, K., "Lattice QCD -a challenge in large scale comput- ing," Camp. Phys. Camm. 44, (1987), 261. 

Schmidt, G. E., "The Butterfly parallel processor," in the Proceed- ings of the Second International Conference on Supercomputing , published by the International Supercomputing Institute inc., St. Petersburg, Florida, May 1987. 

Schwartz, I. T., "Ultracomputers," ACM TOPLAS. 2, (October 1980), 484. 

Seitz, C. L., and Matisoo, J ., "Engineering limits on computer per- formance,'. Physics Today, (May 1984),38. 

Seitz, C. L., "Concurrent VLSI architectures," IEEE Transactions on Computers. 33, (1984), 1247. 

Seitz, C. L., "The cosmic cube", Communications of the ACM 28, (1985), 22. 

Shaw, "SIMD and MSIMD variants of the non-von supercom- puter," Proceedings of IEEE Compcon 1984, San Francisco, IEEE Computer Society Press (1984). 

Shell, D. L., II A high-speed sorting procedure," Communications of the ACM. 2, {1959),30. 

Siegel, H. ]., "Interconnection networks for SIMD machines," Computer. (June 1979), 57. 

Solomon, I., Lee, M., and Fox, G. "Image processing and the hypercube -Analysis of initial implemenmtion," unpublished Cal- tech report C3p -132, (1984). 

Theiler, J., "Spurious dimension from correlation algorithms applied to limited time-series data," Phys. Rev. A, 34, (1986) 2427, Caltech report C3p -274a. 

472 

Theiler 87 

Thompson 77 

Tuazon 85 

Utku 86 

Van de Velde 87a 

Van de Velde 87b 

Vegdahl84 

Wagar 86 

Walker 86 

Wallace 84 

Werner 85 

References 

Theiler, J ., II An efficient algorithm for estimating correlation dimension from a set of discrete points," Phys. Rev. A. to be pub- lished, Caltech report (1987). 

Thompson, C. D: and Kung, H. T., "Sorting on a mesh-connected parallel computer," Communications oftheACM, 20,1977,263. 

Tuazon, J. et al., "Caltech/JPL hypercube concurrent processor," IEEE 1985 Conference on Parallel Processing, St Charles, Illinois, August 1985, Caltech report C3p -160. 

Utku, S., Melosh, R., and Salama, M., "Concurrent Cholesky fac- torization of positive definite banded Hennitean matrices," Int. I. Numerical Methods in Engineering, 23 (1986) 2137. 

Van de Velde, E. F. and Keller, H. B., "The design of a parallel multigrid algorithm," in the Proceedings of the Second Interna- tional Conference on Supercomputing at Santa Clara. May 1987, published by the International Supercomputing Institute, Inc., St. Petersburg, Florida (May 1987), Caltech report C3p -406. 

Van de Velde, E. F. and Keller, H. B., "The parallel solution of nonlinear elliptic equations," Caltech report C3p -447 (1987). 

Vegdah1, S. R" "A survey of proposed architectures for the execu- tion of functiona11anguages," IEEE Transactions on Computers, C-33, (1984), 1050, 

Wagar, B., "Hyperquicksort -a fast sorting algorithm for hyper- cubes," in, Hypercube Multiprocessors. 1987, edited by M. T. Heath, SlAM (1987), 292. 

Walker, D., Montry, G., Fox, G., and Ho, A., " A comparison of the performance of the Caltech Mark II hypercube and the ELXSl 6400," published in Hypercube Multiprocessors. 1987, edited by M. T. Heath, SlAM (1987),210, Caltech report C3p -356. 

Wallace, D. I., "Numerical simulation on the ICL distributed array processor," Phys. Rep 103. (1984), 191. 

Werner, B. T. and Haff, P. K., "Dynamical simulations of granular materials using concurrent processing computers," (1985), Unpub- lished Caltech report C3p -242. 

References 

Werner 87 

Whelan 85 

Wilhelmson 87 

Wilson 86 

Winograd 75 

Winograd 76 

Wolfram 86 

Zweben 83 

473 

Werner, B. T., " A physical model of wind-blown sand transport," Caltech Ph. D. dissertation (1987), unpublished Caltech report C3P-425. 

Whelan, D., " ANIMAC-a multiprocessor architecture for real-time computer animation," Caltech Ph.D. Thesis (1985). 

High-speed computing: scientific applications and algorithm design, edited by Robert Wilhelmson, University of Illinois Press (1987). 

Wilson, K. G., "The Gibbs project," in Supercomputers -Algo- rithms. Architectures. and Scientific Computation. edited by F. A. Matsen and T. Tajima, University of Texas Press (1987). 

Winograd, S., "Some bilinear forms whose multiplicative com- plexity depends on the field of constraints," IBM Yorktown Report RC 5669, (October 10,1975). 

Winograd, S., "On computing the discrete Fourier Transform," Proc. Nat. Acad. Sci. 73, (1976),1005. 

Wolfram, S., Theory and Applications of Cellular Automata, World Scientific Publishing Co. (1986). 

Zweben, S. I. and Gould, R. W., "Scaling of edge-plasma tur- bulence in the Caltech tokamak," Nuclear Fusion 23, (1983).1625. 

Adaptive Mesh 
In problems in which an approximate numerical solution is sought on a mesh of nodal points, an adaptive mesh is one in which the nodal points change dynami- cally as the numerical system evolves. 

Arndahl's Law Arndahl's Law states that the maxirnurn concurrent speedup attainable for a con- current algorithm is limited by its sequential components. Thus, if the sequential component takes a fraction, f seq , of the total run time on one node of a concurrent processor, the maximum possible speedup is 1/ f seq .This law is discussed in Sec. 3-6 and 20-4. 

Architecture 

The architecture of a computer describes the design of the hardware components of the computer system, and the ways in which these components interact to produce the complete machine. The architecture includes both topology and details of node for a concurrent processor . 

Array or Computer Array 
A rather loose term used to describe the set of nodes of a concurrent processor . This term implies but does not require that the processor has a geometric or matrix like connectivity . 

Artificial Iotelligence 
This defines a class of problems such as pattern recognition, decision making and learning in which humans are clearly very proficient compared with current com- puters. The definition of artificial intelligence is imprecise and time dependent; some include computer algebra and game playing in this class. 

Backsubstitution 
See LU decomposition 

Banded Matrices 
A banded matrix is one in which the non-zero elements are clustered around the main diagonal. If all the non-zero elements in the matrix are within m columns of the main diagonal, then 2m + 1 is termed the bandwidth of the matrix. 

475 

476 

The Glossary 

Bandwidth 

Blocking 

Cache 

This is a measure of the speed of infonnation transfer typically used to quantify the communication capability of concurrent computers. One can use bandwidth to measure both node to node and collectiv~ (bus) communication capability. Bandwidth is usually measured in megabytes of data per second. Also, see banded matrices for an entirely different use of bandwidth. 

Blocking is a tenn used to describe the action of read and write communication routines that wait until their function is complete. Blocking is usually implemented by means of polling, and is described in Chaps. 4, 14, and 22. 

A fast memory used to hold commonly used variables which are automatically fetched by hardware from the slower and larger main computer memory . 

Cellular Automaton A cellular automaton is a collection of objects, cellular automata, each of which has a state that is a function of the state of the other objects, and which is evaluated according to a certain set of rules. The system evolves in a set of discrete steps, with each object evaluating its state at each step according to its rules, which may be different for different objects. A simple example of a cellular automaton is one in which the objects are rectangular cells arranged in a two-dimensional grid so that each cell has four neighbors. The state of a cell may either be O or 1, and the rule for all cells is: set your state to O if the sum of the states of your four neighbors is odd, otherwise set your state to I. 

Cellular Computer 
A term used in Chap. 2 to describe fine grain computers including neural net- works, systolic array and SIMD machines like the Connection Machine. 

Channel Mask A channel mask is a non-negative integer specifying a set of communication channels. If the numbers of the channels to be specified are io, i I,..., iN-I, then the channel mask is the integer for which these bit numbers are set to I and all other bits are 0. For example, if the channels to be specified are numbered 0, I, and 4, the corresponding channel mask is the binary number 10011, or 19, in which bits number 0, I, and 4 are set to I.