MDUMPCP(3) 

577 

CNAME 
mdumpcp-dump data from nodes to control processor's memory 

c SYNOPSIS 
int mdumpcp (buffer, nbytes, bufmap) char *buffer; 
int nbytes, *bufmap; 

C DESCRIPTION mdumpcp may only be called from the control processor. mdumpcp causes a separate block of at most nbytes bytes of data to be read from each node and written into memory starting at buffer. After the call to mdumpcp , buffer contains a concatenation of all the blocks of data sent by the nodes, in proc- num order. Then, a separate map of the data is stored in bufmap in order to keep track of which data is from which node. The first integer of the array, bufmap[O] contains nproc, the total number of nodes in the cube, which is just 2 to the power of doc. Then the array elements bufmap[J] through bufmap[nproc] contain the number of bytes of data sent from each of the nodes. For example, bufmap[6] con- tains the number of bytes of data sent by node 5. 
It is guaranteed that a separate block of data will be read from each node; mdumpcp will not return until a block of data has been read from each node. A call to mdumpcp in the control processor must be complemented by a call to dumpelt in all of the nodes. Otherwise, deadlock will result 
If more than nbytes bytes are written by a node, only the first nbytes bytes are placed in buffer. The remaining bytes are then read, so the corresponding calls to dumpelt in the nodes can return, but the extra bytes are lost and -I is returned to indicate the error. The type of error is identified in the external variable errno, and the number of bytes that were transmitted is saved in the external variable errcnt. The value of errcnt is overwritten each time more than nbytes are written by a node, so if several nodes write more than nbytes bytes, errcnt will contain the value from the last node to write more than nbytes bytes of data. 

FORTRAN SYNOPSIS 
INTEGER FUNCTION KMDUMP (BUFFER, NBYlES, BUFMAP) INTEGER BUFFER (*), BUFMAP (*), NBYTES 

SEE ALSO 
dumpelt(3), fdumpcp(3), floadcp(3), mloadcp(3) 

DIAGNOSnCS If an error occurs in mdumpcp, it returns -I and sets errno accordingly. Otherwise, it returns the number of nodes that sent data. Several conditions can generate an error: communication errors, a bad buffer address, a preposterous value of nbytes, 

578 

Appendix E: The crOS m Operating System App. E 

or reading a message that is longer than nbytes. Communication errors are detected by comparing the checksum of the incoming data with the checksum appended to the data by dumpelt. 

MLOADCP(3) 

579 

CNAME 
mloadcp-load data into nodes from control processor 

c SYNOPSIS 
int mloadcp (buffer, bufmap) char *buffer; int *bufmap; 

C DESCRIPTION mloadcp may only be called from the control processor. mloadcp causes a separate block of data to be written to each node from memory starting at buffer. Before calling mloadcp, one block of data for each node in the hypercube must be placed in buffer, in procnum order. Then, a separate map of the data in buffer must be stored in bufmap with the following format: one integer, nproc, containing the total number of nodes, followed by one integer for each node, containing the number of bvtes of data for that node. 
It is guaranteed that a sepa'""lte block of data will be written to each node; mloadcp will not return until a block of data has been written to and read by each node. A call to mloadcp in the control processor must be complemented by a call to loadelt in all of the nodes. Otherwise, deadlock will result. 

FORTRAN SYNOPSIS 
INTEGER FUNCTION KMLOAD (BUFFER, BUFMAP) INTEGER BUFFER (*), BUFMAP (*) 

SEE ALSO 
loadelt(3), floadcp(3), fdumpcp(3), mdumpcp(3) 

DIAGNOSnCS If an error occurs in mloadcp, it returns -I and sets errno accordingly. Otherwise, it returns the number of nodes to which it sent data. Several conditions can gen- erate an error: a bad buffer address or invalid contents of the buffer, such as unrea- sonable values of nbytes or too few data blocks for the number of nodes. Although no communication errors can be detected by mloadcp, it appends a checksum to the data when they are written allowing loadelt to detect communication errors when the data are read. 

580 

Appendix E: The crOS ill Operating System App. E 

NAME 
intro--introduction to the utility library 

DESCRIPTION 
This section describes the utility library that supports the communication routines presented in Sec. I, 2, and 3. Although this section currently contains few routines, additional routines such as index, transpose, transfer and crystal-router, will be added as they are implemented. 

CPARAM(4) 

581 

CNAME 
cparam-obtain cube parameters 

c SYNOPSIS 
cparam (env) 
struct cubenv *env; 

C DESCRIP110N 
cparam may be called either from the nodes or the control processor. cparam copies the parameters defining the cuuent node environment into the structure env. Irrelevant values may be ignored, i.e. cpmask has no meaning in the control pro- cessor and will be set to 0. The structure declaration from <cros.h> is: 
struct cubenv { int doc; 
int procnum; int nproc; 
int cpmask; 
int cubemask; 

} ; doc contains the dimension of the hypercube currently being used. procnum con- tains the unique processor number of a node or 1024 if called in the control proces- sor. nproc contains the total number of nodes currently in use. cpmask contains the mask of the channel that connects the node to the control processor. cpmask is 0 for the control processor and for all nodes that are not directly connected to the control processor. cubemask is the channel mask that the control processor uses to talk to the cube (node 0). It is set to 0 when cparam is called in the cube. 

FORTRAN SYNOPSIS SUBROUTINE KCP ARA (ENV) INTEGER ENV (5) 

FORTRAN DESCRIPTION 
KCPARA is the direct FORTRAN quivalent of the C routine cparam. Upon return the array ENV contains the parameters defining the current node environment. 
ENV(I) = doc 
ENV(2) = procnum ENV(3) = nproc 
ENV(4) = cpmask 
ENV(5) = cubemask 

582 

Appendix E: The crOS ill Operating System App. E 

CNAME 
gridmap-map interconnection topology onto cartesian grid 

c SYNOPSIS 
int gridinit (griddim, Dum) int griddim, *Dum; 

int gridcoord (proc, coord) int proc, *coord; 

int gridproc (coord) int *coord; 

int gridchan (proc, dir, sign) int proc, dir, sign; 

C DESCRIPTION The gridmap subroutines may be called only from the nodes. gridmap collectively refers to four routines that implement the mapping of the interconnection topology of the concurrent processor onto a decomposition topol- ogy which is some type of cartesian grid. 
gridinit initializes the other routines and must be called first. The dimension of the cartesian grid is griddim, and nwn is a pointer to an array containing the number of nodes in each dimension. gridinit returns -I if it cannot perform the mapping to the indicated decomposition topology. To use the available nodes most efficiently, the number of nodes in each dimension should be a power of two, but even if it is not, the gridmap routines will work. However, periodic boundaries, which are nor- mally provided, may not be possible if the number of nodes in each dimension is not a power of two. 
gridcoord converts the processor number proc into its cartesian coordinates in the grid. gridcoord returns the coordinates by writing them into the array indicated by the pointer coord. If node proc is not part of the grid, gridcoord returns -I. 
The inverse function of gridcoord is performed by gridproc, which returns the pro- cessor number of the node whose coordinates are given in the array coord. If the coordinates given by coord lie outside the grid initialized by gridinit, gridproc returns -I. 
gridchan returns the channel mask of the channel in the direction given by dir and sign relative to processor number proc. dir labels the particular dimension of the grid and sign, which has the allowed values of + I and -I, and identifies the desired change in the coordinate given by dir. Other values of sign cause gridchan to return -I to indicate the error. 

GRIDMAP(4) 

583 

FORTRAN SYNOPSIS 
IN1EGER FUNCTION KGRDIN (GRDDIM, NUM) IN1EGER GRDDIM, NUM (*) 

INTEGER FUNCTION KGRDCO (pROC, COORD) INIEGER PROC, COORD (*) 

IN1EGER FUNCTION KGRDPR (COORD) IN1EGER COORD ( * ) 

IN1EGER FUNCTION KGRDCH (pROC, DIR, SIGN) IN1EGER PROC, DIR, SIGN 

DIAGNOSTICS 
If an error occurs in any of the gridmap routines, they return -I. Many conditions can cause an error, such as having a coordinate or processor number out of range or requesting more nodes in the grid than are available. 

Index 

ADA, 48 
adaptive mesh, 448,475 
addvec, 351ff, 355,356,399,407 Aerodynamics, 18 
Amdahl's law, 57ff, 150,372,398,475 AMETEK, 31,35,500 
architecture, 6, 15, 17ff, 20, 22, 24ff, 28, 44,443,475 
array, 22,45,278,351,475 
Artificial Intelligence, 1, 17, 19,24,46, 49,63,349,475 
Astrophysics, 18, 64, 132, 450 atomic, 44 
backsubstitution, 365,367 , 387ff, 475 banded matrix, 167, 363ff, 419,475,500 bandwidth, 9, 15, 20, 24, 31, 62ff, 419, 476 
BBN Butterfly, 28,227,364,441,499 bcastcp, 254, 562 bcastelt, 254, 563 
bintogray, 263,266 Biology, 18,446 
bitonic-merge,334 
bitonic sorting, 330, 334ff blocking, 74,476 
bound-exchg,302ff 
brain, 1, 11ff, 21ff, 40,47 branch and bound, 213 
broadcast,6, 15,22,48,53,345,412-4 broadcast, 77, 81, 169ff, 244-7, 286, 552-3 

to subcube, 246, 413, 415 from control process, 254 with shared memory, 271 
bubblesort, 339 BUFSIZ, 278 

C, 73, 84, 111ff, 273, 276, 356, 500 C code, 506-20 
Cartesian grid, 82-3, 260-1 CDC, 17 Cedar , 23 
cellular automata, 307, 448, 476 cellular computer, 22ff, 476 
channel buffer, 228-30, 234, 242, 270-1 channel mask. 231, 244, 356, 358, 476, 543 
chaos,448 
checkerboard ordering, 121, 317 four-color, 131 
checksum, 231, 233 
chemical reactions, 447-48 Chemistry, 18, 447 
chess, 2, 49, 66, 108, 349 
circuit simulation, 46, 428-31 circuit,431 
cmp -ex-hi, 331 
cmp -ex-low, 332 
collective communication routines, 76- 81, 83, 240ff, 477 combcp,259, 564 combelt, 259, 565 
combine, 247-9, 259, 351ff, 361, 381, 543, 554-5 
subcube combine, 251, 381, 385 communication, 
asynchronous, 49, 269, 438 
between nodes and control process, 79-81, 252-60 
blocking, 74ff,437-38 channel-addressed, 231, 438 collective, 76-81, 83, 240ff communication channel, 24, 29, 60, 70ff, 228ff, 477 

585 

586 

communication overhead, see over- head 
errors, 231, 232, 233 expected, 73, 426 
node-addressed, 230 
overlapped with calculation, 440, 444 
polled, 48, 229, 232, 268, 293, 487 compiler, 27ff, 65 
complex system, 39ff, 477 
computational fluid dynamics, 448 computational graph, 39ff, 307, 318 compute-energy, 300, 302 computer algebra, 46 
symbolic manipulation, 349 concat, 249-251, 358, 556 
concurrent computation, Iff, 17, 20, 24, 39ff,477 
concurrent language, 27 
condensed matter physics, 222, 451 conj-grad, 145 
conjugate gradient, 139ff, 145, 477 Connection Machine, 16, 22, 30, 478 contention, 24, 307, 309ff, 478 continuum mechanics, 149 
control processor, 7, 79, Ill, 239, 273ff control process, 72, 79, 85, 101, 116, 228,239,274,279,478 convergence, 149 
correlation dimension, 163, 448 Cosmic Cube, see hypercube cparam, 114, 251, 542, 581 cpmask, 240, 252 
CRAY, 3, 9, 16, 17, 23, 25, 27, 28, 30, 32,65, 
cread, 230ff, 542, 544-5 
in shared memory environment, 271 
creat,280ff 
cros.h, 251, 280ff, 542, 581 
crOS III, 29, 49, 69, 75, 111, 227ff, 273, 309, 441, 478, 541ff 

Index 

crystalline operating system (communi- cation system), 29, 48ff, 75, 178, 227ff, 260,445,478; see also crOS III 
in shared memory environment, 270-1 
crystal-accumulator, 433- 7 crystal-router, 75, 151, 348, 425ff, 438, 479 
cshift, 241-3,312,542,557-58 cubeld, 260, 566-68 cubeldl, 260, 566-68 cubeldle,566-68 cubeldv,566-68 
cubeldve, 279,566-68 cubemask, 252 
cubenv, 542,581 
CUBIX, 111ff, 123, 273ff, 308,313,479, 501ff 
Cuppens method, 421 
cwrite, 230ff, 542,546 
in shared memory environment, 271 

dataflow, 27ff, 42,47,479 
deadlock, 74,232,234,438,479 decomposition, 1, 42ff, 47, 54, 64, 82, 108,402 
domain, Iff, 15, 26, 44, 270, 307 , 309,480 FFT,190 
finite elements, 46, 58, 60, 64ff, 140ff 
Laplace equation, 120 local, 480 
mapping onto concurrent proces- sor, 81-3, 260-8 
matrices, 167ff,419 
scattered, 65, 142, 324ff, 369-71, 419,480,488 
square, 367, 489 
of symmetric matrices, 420 of trees, 349 
wave equation, 97ff 

Index 

degrees of freedom, 44,57,136 DEI, 587 
detailed balance, 222 diagonal passing, 132 discretization, 99, 136 
distributed memory, 2, 23ff, 26ff, 29,41, 55,479 
divide and conquer, 343,347 DMA, 230 doc,239 
domain, 97, 120, 136,479 dot-global, 147 do-steps, 104 
dumpelt, 257-8,280,569 
dumping data from nodes, 257-8 
earthquake engineering, 449 edge-exchange,303ff efficiency, 4, 55ff, 480 
ofbitonic sort, 336ff of combining, 351 
of finite elements, 148 
of long range interactions, 159 of matrix algorithms, 421 
of matrix multiplication, 176ff ofQCD,221ff 
of quicksort, 345ff 
of scalar product, 358ff of shellsort, 341ff 
of wave equation, 104ff eigenvalues,47, 167,350,419 elastostatic, 149 element,79 
elliptic partial differential equation, 117, 126, 135 
Engineering, 18,448-9 ensemble machine, 70 error handling, 227 
errcnt, 227,232-3, 542ff 
errno, 227, 232-3,274, 542ff ETA, 17,28 
exit, 115,277-8 
expand, 350,407-10,415,427 

587 

farm, 1, IOff, 46, 54 
fast Fourier transform, 46, 52, 62ff, 187ff, 238, 404-6, 450, 480, 500 [close, 115, 277-8 [cread, 252, 570-1 [cwrite, 252, 572 
[dumpcp, 257-8, 573-4 
FFI' , See fast Fourier transform file system, 
access to, 252 
loading data from, 254-5 
finite differences, 26, 46, 99, 107, 118ff, 480,500 
higher-order, 129, 131, 224 
finite elements, 26, 27, 46, 109, 135ff, 481,500 
higher-order, 151 
Finite Element Machine, 136 [jlush, 115, 277-8, 285 filbu[, 282, 285ff 
jloadcp, 254, 280, 543, 575 [multi, 114, 116, 276, 282 [old, 350, 407-102, 436 [orceyar,163 [orest,412-4 
FORTRAN , 27, 73, 84, 112ff, 187, 500 CUB IX, 501ff 
FORTRAN code, 521-40 
forward reduction, 365, 367, 387ff, 370, 375 
Fourier transform, see fast Fourier transform, non-binary Fourier transform [print}; 277 
FPS, 28, 31, 35 [scan[, 285ff 
[singl, 114, 276, 282 Fujitsu, 17 
full-duplex, 229, 242 
full matrix 167, 419, 481 fwrite,277 GaAs, 2Off 
Gauss-Jordan method, 419, 448 

588 

Gauss-Seidel iteration, 119, 481 Gaussian elimination, 481 geodesics, 399-401 
geometric hashing, 297 
Geophysics, 18, 46, 449-51 getc,285 
get-edge, 125 globalize, 147 
global-reverse, 198, 406- 7 
grain, 5, 12, 22ff, 29, 41ff, 47, 97, 100, 176,477,479,480,482 
grain size, 5, 16, 22ff, 37, 51, 54, 58ff, 342,482 
granular physics, 296, 451 granule, 44, 322, 479, 482 Gray code, 260-2, 482 graytobin, 262-3, 266 
gridmap, 82, 260-8, 582-3 gridchan, 266-7, 582-3 gridcoord, 265, 582-3 
gridinit, 116, 264, 582-3 gridproc, 266, 582-3 
ground state, 66, 215, 318ff 
guard ring, 300, 302, 310, 483 
Hadrian's Wall, 2ff, 44, 47, 53 half-duplex, 229, 242 
Hamiltonian, see objective function High Energy Physics, 18, 451 Hitachi, 17 
Householder's method, 419 hydrodynamic flow, 132 
hypercube, 3, 6, 9, 11, 19, 23ff, 28, 29, 31-37, 40ff, 48ff, 60, 84, 483 
AMETEK, see AMETEK Cosmic Cube, 31, 33 FPS, see FPS 
INTEL iPSC, see INTEL 
Mark n, 7, 9, 29, 31, 33, 56, 58, 60, 63, 84ff, 106, 111, 127, 147, 173, 195, 360ff, 376, 413, 420, 500 
Mark ill, 29, 31, 34, 230, 440, 500 NCUBE, see NCUBE 
numbering of nodes in, 239 

Index 

simulator, 500 
subcube, 199,244 
topology , see Topology, hypercube trees mapped onto, 349ff 
hyperswap, 216ff 
1/0, see input / output 
image processing, 5,22,47,62,187 index, 403-7,415,427 
inhomogeneous, 3,8,41,44,64,307, 483 
INMOS, 29,38,487,490 inner product, 139, 144 
input / output, 9ff, 62ff, 111ff, 169, 273ff, 483 
INTEL, 19,31-7 
8087 processor, 84 
iPSC hypercube, 31, 34, 49, 84ff, 183,364,413,500 
interact,301 
interrupt-driven, 151,269,305,478,483 interrupt line, 228-9,232-3,268 
irregular, 3, 7, 26, 44, 49, 53, 56, 64, 291ff, 307,483 
ismulti, 276, 282 
iterative improvement, 215 
iterative solution, 118ff; see also Gauss- Seidel, Jacobi iteration and (successive over) relaxation 

Jacobi iteration, 118,484 

Laplace equation, 117ff, 135ff, 484 latency, 50, 85, 173ff, 183, 444, 484 lattice gauge theory, 24, 219, 451 Lennard-Jones potential, 294 linear equations, 363ff 
linked list, 297ff, 307, 309ff 
load balance, 8, 28, 41, 49, 56, 64ff, 75, 269, 307ff, 327, 330, 484 
of circuit simulation, 428 
of finite elements, 140, 322 
of LU decomposition, 369, 372, 395,415 

Index 

of matrix algorithms, 419-22 
of matrix multiplication, 182ff 
of non-binary Fourier transform, 432-3 
of PIC algorithm, 450 of quicksort, 345 
of scalar products, 349ff, 359ff of wave equation, 100, 105 loadelt, 254, 282, 576 loading, 
data into nodes, 254-5 
programs into nodes, 260 log2, 264 
long range force, 129, 155ff, 500 
loose synchronization, 29, 43ff, 48, 73ff, 113, 115, 123, 252, 268, 274ff, 426, 438, 445,484 
LU decomposition, 167, 363ff, 419, 481, 484 
Mark II (III), see hypercube Material Science, 18 mat-mult, 172 
matrix algorithms, 22, 26ff, 46, 48, 54, 349ff, 399ff, 500 
matrix inversion, 419, 448 
matrix multiplication, 167ff, 379, 421 matrix-vector multiplication, 167, 350, 408-12, 419 
mdumpcp, 257-8, 577-8 MEIKO, 29, 38 
members, 3, 5, 8, 44, 46, 97, 479, 485 memory, 18, 19, 22ff, 38, 55ff merge, 329ff 
Meteorology , 18 
Metropolis method, 321 
mesh, 23, 44ff, 49, 142, 168ff, 175, 443, 485 
message passing, 16, 24, 27, 43, 70, 445, 485 

general, 425££, 500 
microprocessor, 8,12, 19££,28 
MIMD, see multiple-instruction multiple-data 

589 

mloadcp, 254,282, 543, 579 molecular dynamics, 155 
Monte Carlo, 18, 46, 201ff, 213ff, 307, 486 

detailed balance, 222 for integrals, 206 
calculation of 1t, 208 
event tracing, 201,206 
matching of parallel and sequential, 210 
simulated annealing, 67, 214ff, 318ff 
Quantum Chromodynamics, 219ff moveJlsh,313 mread,274ff 
multigrid method, 150-51,448,486 multiple, see multiplicity multiple-instruction multiple-data, 1, 22ff, 30, 41, 60, 70, 324, 339, 348, 443, 485 
mwrite, 274ff, 283ff multiplicity, 
singular, 113,115,276 multiple, 114, 276 
N-body problem, 64, 65, 155ff, 164, 291ff 
NCUBE, 29,31,36,49,60,500 NEC, 17 
need-predictable, 291,426,486 Neumann boundary, 138 
neural networks, 13ff, 18, 22, 53, 67, 434-5,446-7, 486 
as applied to optimization, 213 neuron, 12ff, 22ff, 41,46,67 next-dir, 295 
nodal point, 60, 97, 117, 486 
non-binary Fourier transform, 431-3 nonsimultaneous correction, 121 NP-complete, 66, 213,487 nproc, 70, 239 
n-squaredyroblem,l64 Nuclear Physics, 18 

590 

objective function, 66,215,318 object orientated, 27 OCCAM, 49,487 
operating system, 48ff, 61, 69, 227ff, 273ff, 292, 425ff, 445 
optimization,64ff, 120,213 
ordered cube geodesics, 399,426 overhead, 487; see also efficiency 
due to communications, 49ff, 61, 63, l04ff, 126, 151, 159, 174ff, 193ff,322 
general form, 55ff, 444 
software overhead, 56, 178, 180-1, 376,396 
in backsubstitution, 394 
in forward reduction, 387 in LU decomposition, 375 
in running load balancer, 321-2 in transpose, 410 
packet size, 229-30,234 
particle dynamics, 108, 291ff, 500 particle-in-cell (PIC) algorithm, 450 particle-particle particle-mesh (pPPM) method, 297 
partial differential equations, 18, 52; see also elliptic 
pattern recognition, 13, 15,45,64 periodic boundary conditions, 267 pipe, 86, 173ff, 246,413,418,487 dual geodesic pipe, 418 
splityipe, 374,377,418 pipeline,4, 157 
pivoting, 379ff, 487 Plasma Physics, 18 Plato, 2 
polled, see communication portable programs, 441 pot-2arr, 156 potyar, 159 pot-seq, 156 
pot-symyar2, 161 pot-sym-2arr, 161 

Index 

prand,206 
prand-set,206 
preconditioner, 149ff,488 
prime factor algorithm, 431-3 printf, 112, 115, 277 
procnum,70, 115,239,276,288,356 protein dynamics, 447 pseudocode, 493ff 
pseudo-random number, 201ff, 500 correlations of, 202 
linear congruential, 203ff linear shift register, 211 putc, 277,282 putchar, 277 
Quantum Chromodynamics, 219ff; see also High Energy Physics Quicksort, 46, 329, 343ff QR algorithm, 418-20 
rand,205 
rand-set,205 
random number, see pseudo-random number 
ray tracing, 65,455 rdstat, 236,547 recombine,163 
recursive bisection, 428-30 
red / black ordering, see checkerboard ordering 
refill, 286ff 
relaxation, 488 release,285ff 
rendezvous, 48,74 ring-setup, 158 
robotics, 19,447 
rollback, 307, 314ff rotate, 158 
RP3, 6,28,441 
samplesort, see quicksort 
scalar product, 57, 350ff, 500 scanf, 112, 286 scatter, 415-6 

Index 

scattered decomposition, see decomposi- tion 
SchrOOinger equation, 447 seismic waves, 450 
sequential bottleneck, 173, 370, 488; see also Amdahl's Law serve-request, 280 setbuf, setvbuf, 278 setbuffer, 278 setup,253 
shape function, 137 
shared memory, 6,24, 26ff, 43, 55ff, 71, 270-1,440,445,488 shell-merge,341 Shellsort, 339ff 
should-self -interact, 162 
SIMD, see single-instruction multiple- data 
simplex algorithm, 422 
simulated annealing, 66ff, 214ff, 318ff, 489 
simulation, 307 
single-instruction multiple-data, 22ff, 30, 60,324,334,339,348,443,489 singular, see multiplicity 
society,2, 16,21, 39ff, 53 
Software Supplement, 86, 499 
SOR, see successive over-relaxation sorting, 46, 327ff, 500; see also bitonic, Shellsort, quicksort, bubblesort sparse matrix, 167,422,489 sparsity, 118 
speedup, 3, 8, 16, 55ff, 67, 159,444,480, 489; see also efficiency splityipe, see pipe 
spreadsheet. 46, 167, 183ff 
standard 1/0, 112, 116, 275ff startup, see latency stderr, 276,277 
stdin, 112, 114,276 
stdout, 112, 114, 276 stiffness, 137ff 

591 

Structural Analysis, 46 
successive over-relaxation, 119, 122, 125,490 
supercomputer, 17ff, 25, 27ff, 30, 446, 490 
SUPRENUM, 29 
synchronization, 44ff, 75, 234, 323; see also loose synchronization, 
system dimension, 53, 379,444,479 systolic array, 22, 26, 490 
tcalc (tcomm ), 31, 50, 444,490 
of Mark II hypercube, 31, 84 of INTEL iPSC, 31,84 
see also speedup and efficiency temperature, 41,66, 215ff, 322 template, 322 
test-export, 296 token, 321 
tomography,450 
topology, 3, 6, 22, 24ff, 29, 41ff, 50ff, 443,490 
fully interconnected, 26, 71, 237 for matrix multiplication, 168 hypercube, 71, 193, 237ff 
ring, 157,214,237-8,261,328 trees on hypercubes, 349ff two-dimensional grid, 71,238, 262 
transfer,416-9 
transpose,408-12 
transputer, 29,38,487,490 
Traveling salesman problem, 213ff trees mapped onto hypercube, 349ff turbulence, 448 ungetc,277 
UNIX,49, 1 I Iff, 273ff, 499-500 unpredictable communications, 305ff update order, 119,121 
update yarticles, 292, 294ff update-SOR,125 
variational equation, 136 vectorization. 27 

592 

Index 

VHSIC, 20 
virtual concurrent processor (machine), 69ff, 230, 271, 437-41, 445, 490, 500 Viterbi algorithm, 449 VLSI, 17 VMLSCS,269,425,437-41,445,491 Von Neumann, 477, 491 VMS, 500 
vm-bcast, 77, 81, 440 vm-bcastcp, 81 vm-bcastelt, 81 vm-combcp, 81 vm-combelt, 81 
vm-combine, 78, 81, 85, 159, 351, 440 vm-comsync, 438 
vm-dumpcp,80,85-6 vm-dumpelt, 80, 85-6 vm-gridinit, 82, 86 
vm-gridcoord, 83, 86 vm-gridproc, 83 vm-initproc, 437 vmJillproc,437 
vm-loadcp, 79, 86 vm-loadelt, 79, 86 vm-query, 438 
vm -,ead, 73ff, 86, 437ff 
vm-shift, 76, 124, 158, 192, 241 vm-write, 73ff, 86, 437ff vortex method, 448 vread, 234-5, 548-9 
vshift, 234-5, 309, 356, 358, 378, 559-60 vwrite, 234-5, 550 
wait, 285ff 
walking program, 
for loops, 222ff 
for finite differences, 224 WaTor, 307ff, 500 
wave equation, 98ff, 500, 505ff C code, 506-20 
FORTRAN code, 521-40 

~ 

Gregory A. Lyzenga 

Steve w. Otto 

John K. Salmon 

David W. Walker 

~ 

I-, , . 
~ ~ 

r- ISBN 0-13-823022-6