Index
Absence of deadlock, 73, 95
Absence of livelock, 77, 95
Absence of unnecessary delay, 95
accept statement, 399
Action. See Atomic action
Active monitor, 302-8
Active-X system, 414
Ada language, 397-406, 615-16
history and references, 413-14
Adaptive grid (mesh), 549
Adaptive quadrature problem, 18
bag-of-tasks program, 134-36
manager/workers program, 428-30
recursive program, 18
Administrator/workers. See
Manager/workers paradigm
Aging, technique of, 180
Allocation patterns, 540, 557
Amdahl's Law, 529-30
Angle brackets notation, 54
Anti-dependence, 604
Array copy problem, 57, 70
Assertion, 44, 60
in comments in programs, 31
Assertional reasoning, 44
Assignment action, 64
Assignment statement axiom, 60
Asynchronous execution, 3
Asynchronous message passing, 296-98
duality with monitors, 308
implementation of, 488-96
At-most-once property, 52
Atomic action, 42
Fine-grained, 51
Coarse-grained, 54
Atomic broadcast problem, 195, 257
Atomic transaction, 412
Avoiding interference, 65
await statement, 54-55
implementation of, 101-3
Axiom, 58. See also Inference rule
assignment axiom, 60
Background processes, 15, 363
Backward substitution, 574
Bag-of-tasks paradigm, 132-35, 139, 337, 424.
See also Manager/workers paradigm
Bakery algorithm, 111-14, 137
Barber problem. See Sleeping barber problem
Barnes Hut algorithm, 570-72
Barrier synchronization, 115
kinds of barriers
butterfly, 121-22
combining tree, 119-20
coordinator, 119
counter, 116
dissemination, 122
symmetric, 121
programmed using
Ada language, 402
Linda primitives, 336
monitors, 248
MPI library, 343
Pthreads library, 248
semaphores, 158
Bear and honeybees problem, 202
Beowulf machine, 9
Binary semaphore, 155, 159
Blocking primitive, 297
Blocks, allocation by, 540, 557
Bounded buffer problem, 161
programmed using
monitors, 213-15
multiple primitives, 385-86
rendezvous, 376-77
semaphores, 161-64
synchronous message passing, 325
Broadcast algorithm, 423, 451
disseminating information, 444-47
distributed semaphores, 454-57
Broadcast message, 444, 454
Broadcast signal, 213
BSP model, 615, 627-28, 640
Busy waiting, 57, 94. See also
Spin lock; Spin loop
Butterfly barrier, 121-22
C* language, 615, 620-21
Cache, 4
characteristics of, 5
consistency problem, 7
distributed file system, in a, 367-70
false sharing, 8
multiprocessor, in a, 7
call statement, 363. See also
Remote procedure call; Rendezvous
Capability variable, 371
Caretaker process, 292
Cellular automata, 435-37
Channel, for message passing, 291
declaration of, 296
dynamic naming, 301
implementation of, 488-90
Cigarette smokers problem, 199
Cilk language, 615-18, 639
Circular pipeline, 23, 437-38
Clearing house process, 499
Clients and servers, 12, 21-22. See also
Server process
Closed monitor call, 235
Closed pipeline, 437-38
Cluster of workstations, 9
co, syntax of, 29-30
Coarse-grained atomic action, 54
Coarse grid correction, 549
Combining tree barrier, 119-20
Comments, syntax of, 31
Common Object Request Broker (CORBA),
414, 638
Communicating sequential processes.
See CSP language
Communication event, 452
Complete graph, 463
Completeness, of a logic, 58
Computational load. See Load balancing
Computational modeling, 533
Concurrent C language, 412
Concurrent Euclid language, 251, 286
Concurrent ML language, 623, 640
Concurrent Pascal language, 250-51
Concurrent program, definition of, 2
Conditional atomic action, 55
Conditional critical regions, 78
Condition synchronization, 2, 51
Condition variable, 203, 207
Java, in, 240-41
operations on, 212
Pthreads, in, 246-47
signaling disciplines, 208-9
Connection Machine, 32, 131, 138-39
Consumer process, 19. See also
Producer/consumer interaction
Context, of a process, 267
Context switch, 52, 268
Conversational continuity, 312
Coordination language, 619
Coordinator/worker interaction, for
barrier synchronization, 117-19
matrix multiplication, 23-25
CORBA, 414, 638
Co-scheduling on multiprocessors, 276
co statement, 29-30
implementation of, 266-67
Counter barrier, 116
Covering condition, 219
Critical assertion, 64
Critical section of code, 3, 43
Critical section problem, 95
bakery algorithm, 111-14
Dekker's algorithm, 141
distributed semaphores solution, 454-57
semaphore solutions, 157-60
server process solution, 409-11
spin lock solution, 98
test-and-set solution, 99
test-and-test-and-set solution, 101
ticket algorithm, 108-11
tie-breaker algorithm, 104-8
token passing solution, 457-60
CSP language, 320-29, 615-16
history and references, 349-50
implementation of, 496-503
modern version, 331-33
Occam version, 329-31
Cyclic allocation, 557
Data dependence, 604
Data parallel algorithm, 93, 124-32.
See also Barrier synchronization;
SIMD multiprocessor
Data parallel language, 620
Data parallel program, 11
DCOM, 414
Deadlock, 73-74, 165
Decentralized dining philosophers, 467
Decentralized program structure, 389, 466
Declarative program, 3
Dekker's algorithm, 141
Dependence analysis, 603
Dependence testing, 605-6
Diffusing computation, 485
Dining philosophers problem, 164-65
centralized, 376-78
decentralized, 467-71
distributed, 466-67
programmed using
Ada, 403-6
rendezvous, 376-78
semaphores, 164-66
multiple primitives, 466-71
Dining savages problem, 258
Direct naming, 322
Disjoint variables, 65
Disk scheduling problem, 224-28
programmed using
monitors, 228-37
message passing, 308-11
relation to sleeping barber, 228, 232
scheduling algorithms, 227
Dispatcher routine, in a
single processor kernel, 268-71
multiprocessor kernel, 270-75
Dissemination barrier, 122
Distributed bag of tasks, 424
Distributed Component Object Model, 414
Distributed dining philosophers, 466-67
Distributed file system. See File system
Distributed kernel, 491-96
Distributed memory architecture, 8, 291
Distributed mutual exclusion, 457
Distributed pairing problem, 357
Distributed Processes language, 411
Distributed program, definition of, 291
Distributed program structures
client/server, 309
interacting peers, 317
network of filters, 301
pipelines, 437
replicated files, 389
replicated servers, 466
Distributed semaphores, 454-57
Distributed shared memory, 9, 294,
487, 515
false sharing with, 519
implementation of, 515-19
page consistency protocols, 518-19
Distributed termination detection, 460
Double checking, technique of, 50, 273
Doubling, technique of, 125, 127
Drinking philosophers problem, 485
DSM. See Distributed shared memory
Duality of monitors and message passing, 308
Dynamic naming, 301
Echo message, 444
Efficiency of a parallel computation, 529
Eight queens problem, 90, 478
Elevator algorithm, 227
Eligible action, 74
Embarrassingly parallel application, 13
Emerald language, 251-52, 412
empty function, with
monitors, 207
message passing, 298
Event, in a distributed program, 452
Event counts and sequencers, 189
Eventual entry property, 95
Exclusion of configurations, 74
Exit protocols, in spin-lock solutions, 100
Failures, 460, 472-74
Fairness, 74-77
False sharing, 8, 532
Fast multipole method, 570, 572
Fault-tolerant programming, 472, 474
Fetch-and-Add instruction, 116
Fetch-and-\(*F instructions, 138
File buffer allocation problem, 259-60
File server, 22. See also Server process;
Replicated files
Filter process, 12, 298
examples
characters to lines, 297
merge sorted streams, 300, 372, 380
prime number generation, 326-28
programmed using
message passing, 298-302
CSP language, 326-28
remote procedure call, 370-72
rendezvous, 379-81
Finding patterns in a file, 48
Fine-grained atomic action, 51
Flag synchronization principles, 118
Flag variable, 118
Flow dependence, 604
FMM. See Fast multipole method
fork primitive, 266, 271, 284
Formal logical system, 58
for statement, syntax of, 28-29
Fortran language, 598-99
Fortran D language, 629
Fortran M language, 615, 618-19, 639
Forward elimination, 574
Full multigrid method, 553
Fully acknowledged message, 455
Functional language, 623
Function inlining, 540
Game of Life problem, 435-37
Gaussian elimination, 573-75
Gauss-Seidel method, 546
General semaphore, 155
Global invariant, 68
Globus toolkit, 633, 636-38
Gravitational N-body problem. See
N-body problem
Grid computation, 534-53
See also Data parallel algorithm;
Heartbeat algorithm
Guarded communication, 320, 323-26
Guarded operation, 374
Happens before relation, 452
Haskell language, 623, 640
Heartbeat algorithm, 423, 430-37
Game of Life, 435-37
Jacobi iteration, 541-45
LU decomposition, 581-83
N-body problem, 563, 565-66
region labeling, 432-35
High Performance Fortran (HPF)
language, 592, 615, 629-33
references for, 641
History, of program execution, 42-43
Hungry birds problem, 201
Hypercube, 9, 32, 441
Idle process, in a multiprocessor, 273
Image processing, 432-35
Imperative language, 614
Imperative program, 3
Implementation of
asynchronous message passing, 488-96
await statement, 101-3
distributed shared memory, 515-19
monitors, 279-86
processes, 266-71
remote procedure call, 504-6
rendezvous, 504, 507-9
semaphores, 276-79
synchronous message passing, 496-503
in, syntax of, 374-75
Independent statements, 13, 45
Indivisible action. See Atomic action
Inference rule, 58
await statement rule, 63
co statement rule, 63
sequential statement rules, 61
Inlining a function, 540
Input command (?), 321
implementation of, 496-503
Input statement (in), 374-76. See also
Multiple primitives; SR language
implementation of, 507-15
Interacting peers, 12, 25, 292. See also
Heartbeat algorithm; Pipeline algorithm;
Replicated files; Replicated servers
communication structures, 317
exchanging values using
asynchronous message passing, 314-18
remote procedure call, 371-73
rendezvous, 381
Interconnection network, 6, 8
Interference, 63
techniques for avoiding, 65-70
Interpolation, with multigrid method, 550-51
Interpretation of a
logic, 58
triple, 59
Interval timer, 218-19
in a kernel, 269
programmed using
covering condition, 220
priority wait, 221
remote procedure call, 365-67
rendezvous, 378
Invariant
global, 68
loop, 62
Inverse, of a matrix, 589
Iterative parallelism, 11, 13-17
Jacobi iteration problem, 129-30, 535-45
High Performance Fortran program, 632
message passing program, 544-45
MPI program, 596-97
OpenMP program, 602
Pthreads program, 594-95
sequential program, 539
shared variable program, 542
Java language, 237, 344, 393, 615-16
references, 252, 351, 413
remote methods, 393-97
sockets, 344-48
synchronized methods, 239-41
threads, 238-39
join primitive, 266, 271, 284
Kernel, 265
distributed, 491-96
multiprocessor, 270-76
single processor, 266-70
structure of, 268
Laplace's equation, 129, 534
Legion system, 636, 641
Lightweight thread, 362
Linda language, 334-40, 615-16
history and references, 350
Linked lists, operations on, 127-29
Livelock, 77, 95
Liveness property, 43, 72, 74-77
Load balancing, 133, 276, 430, 531
Locality of reference, 5
Lock-free synchronization, 138
Lock-step execution, 131
Lock variable, 98
Logic. See Formal logical system
Logical clock, 453
LogP model, 615, 628, 640
Loop transformations
blocking (tiling), 611
distribution, 609
fusion, 610
interchange, 14, 607
skewing, 612
strip mining, 611
unroll and jam, 610
unrolling, 538, 610
Loop invariant, 62
Loosely coupled machine, 9
LU decomposition, 575-76
message passing program, 582
sequential program, 577
shared variable program, 579
Lynx language, 412
Mailbox, 297. See also Channel
Manager/workers paradigm, 424-30.
See also Bag-of-tasks paradigm
adaptive quadrature, 428-430
N-body problem, 561-64
prime number generation, 337-40
sparse matrix multiplication, 424-28
Marshaling, of arguments, 394
Massively parallel processors (MPP), 3
Matching communication statements, 321
Matrix computations, 573-83
Matrix inversion, 589
Matrix multiplication, 13
bag of tasks, 133-34
blocks, 441-44
message passing, 23-26, 437-44
pipeline algorithm, 25, 438-41
shared variables, 13-16
sparse matrices, 424-28
Memory allocation problem, 201, 258
Memory cache, 4. See also Cache
Memory consistency, 7
Memory contention, 100
Merge process, 300, 372, 380
Merge network, 301
Mesa language, 251
Mesh computation. See Grid computation
Message Passing Interface. See MPI library
Message-passing, 291, 293, 295.
See also Asynchronous message passing;
Synchronous message passing
duality with monitors, 308
Message-passing structures. See
Distributed program structures
Metacomputer, 635
Metacomputing, 592, 635
Middleware, 414
MIMD (multiple instruction, multiple data),
multiprocessor, 3, 151
minrank function, 212
ML language, 623, 640
Modern CSP, 331-33, 350
Modula language, 251, 286
Module declaration, syntax of, 363
Monitor invariant, 205
Monitors, 40, 265
condition variables, 207
duality with message passing, 308
implementation of, 279-83
languages using, 250-52
relation to rendezvous and
RPC, 293, 361
relation to semaphores, 203, 283-84
signaling disciplines, 208
syntax, 204-5
Moving-head disk, 226
MPI library, 340, 435, 593
basic functions 341-42
global communication functions, 343
Jacobi iteration program, 596-97
references, 350-51
Multicomputer, 9
Multigrid method, 549-53
Multilisp language, 623, 640
Multiple primitives notation, 382-86.
See also SR language
implementation of, 509-15
Multiprocessor
asynchronous (MIMD), 3, 151
caches, 6-8
locking principle, 272
kernel, 270-76
synchronous (SIMD), 4, 131-32
Multithreaded program, definition of, 10
Mutual exclusion, 2, 51, 93, 95, 475. See
also Critical section problem
Mutex locks, in Pthreads, 246-47
N-body problem, 554-55
allocation patterns, 557
approximate methods, 569-72
heartbeat algorithm, 565
manager/workers algorithm, 564
pipeline algorithm, 567
sequential program, 556
shared variable program, 560-61
tree codes, 569-72
NESL language, 615, 624, 640
Nested monitor call, 235-36
Network architecture, 9
Network interface routines, 491-96
Network of workstations, 9
Network topology problem, 448
Nonblocking primitive, 296
Nondeterministic execution, 30
Noninterference, 64
Nonpreemptive signal, 208
Nonuniform memory access time, 6
notify statement, 240-41
Nucleus. See Kernel
NUMA multiprocessor, 6
Occam language, 329-31, 349, 615-16
Odd/even exchange sort, 148
One-lane bridge problem, 200, 256, 355
Open monitor call, 236
OpenMP library, 592, 595, 598-603
Open pipeline, 437
Operational reasoning, 43
Orca language, 615, 619-20, 639
Output command (!), 321
implementation of, 496-503
Output dependence, 604
Overhead, in parallel computations, 531
P operation, 154-55. See also Semaphore
meaning of name, 188
Pablo system, 633-34, 641
Padding, of memory, 8
Page consistency protocol, 518-19
Paradigms
programming style, 11
process interaction, 423
Paradyn system, 634, 641
Parallelizing a program, 45, 530, 532
Parallelizing compilers, 603-14
program transformations, 608
Parallel prefix computation, 124
Parallel program, definition of, 527
Parallel Virtual Machine. See PVM library
Partial correctness, 43, 59
Partial pivoting, 575
Partial sums of an array problem, 126
Particle computations, 553-72
Pascal Plus language, 251
Passing the baton, 170, 172, 175
readers/writers problem, 171-78
SJN allocation problem, 180-84
Passing the condition, 210
Path expressions, 252, 262
Patterns for process interaction. See
Distributed program structures
Peer process. See Interacting peers
Performance, of a parallel computation, 528
Performance measurement tools, 633
Peterson's algorithm. See Tie-breaker
algorithm
Pipe, in Unix, 20
Pipeline algorithm, 12, 437
matrix multiplication, 23-26, 438-44
N-body problem, 566-67
prime number generation, 328
types of pipelines, 437
PL (Programming Logic), 59
Polling, technique of, 310
Port, 298. See also Channel
POSIX threads, 40, 184. See also
Pthreads library
Postcondition, 60
PRAM model, 615, 626-27, 640
Precondition, 60
Preemptive signal, 208
Prime number generation, using
bag of tasks, 150
manager/workers, 337-40
Sieve of Eratosthenes, 326-28
Primitive operation, 265
Priority wait statement, 212
Private semaphore, 182, 284
Privatization transformation, 608
Probe/echo algorithm, 423, 444
broadcast in a network, 444-47
network topology, 448-51
Probe message, 444
Procedure declaration, syntax of, 31
Process declaration, syntax of, 30
Process descriptor, 267
Processor scheduler. See Dispatcher routine
Producer/consumer interaction, 12, 19-21.
See also Bounded buffer problem
copying an array, 57
finding patterns in a file, 48
Pthreads library, using 186-88
semaphores, using, 158-64
Producer process, 19
Program transformations, in parallelizing
compilers, 608
Programming logic (PL), 57, 59
Proof, in a formal logic, 58
Proof outline, 64, 71
Property, of a program, 43
Protected types, in Ada, 401-3
Pruning, technique of, 19
Pthreads library, 40, 184, 246, 593
condition variables, 246-47
Jacobi iteration program, 594-95
mutex locks, 246-47
semaphores, 186
threads, 185-85
PVM library, 340, 351, 592
Quadrature problem, 17
Quadtree, 570
Quantifier, in a for statement, 28
Quicksort algorithm, 17
quit primitive, 266, 271, 284
Race condition, 113, 653
Read set, 45, 65
Readers' preference, 168
Readers/writers problem, 166-67
programmed using
Java, 241-46
monitors, 215-17
multiple primitives, 386-93
semaphores, 167-78, 196
scheduling policies
alternating (fair), 177
readers' preference, 168
writers' preference, 177
with encapsulated database, 387-89
with replicated files, 389-93
Ready list, 269
receive statement, 296-97
implementation of, 489-90
Recursive parallelism, 12, 17-19
Red/black method, 546-49
Reference set, 65
Region labeling problem, 435
Registry service, 394
Relative completeness, 59
Remote evaluation, 412
Remote files, 345-48
Remote method invocation, 393-97
Remote operations, 293
Remote procedure call, 293, 361-73.
See also Java language; SR language
implementation of, 504-6
Rendezvous, 293, 361, 373-81. See also
Ada language; SR language
implementation of, 507-15
in the sleeping barber problem, 222
Replicated files, 389
using locks, 390-92
using weighted voting, 392-93
Replicated servers, 423, 465-71
decentralized, 467-71
distributed, 466-67
structures for, 465-66
Replicated workers, 139 . See also
Bag-of-tasks paradigm;
Manager/workers paradigm
Resource allocation problem, 178-80. See also
Shortest-job-next allocation problem
Resource counter semaphores, 162
Restriction, with multigrid method, 550-51
Reverse stripes, allocation by, 557
RMI. See Remote method invocation
Roller coaster problem, 202, 259, 355, 419
RPC. See Remote procedure call
Safety property, 43, 72-74
Savings account problem, 256, 354, 419
Scalable parallel computation, 132, 529
Scalar expansion transformation, 608
Scheduler. See Dispatcher routine
Scheduling policy, 75
Schooner system, 636, 641
Search/insert/delete problem, 200, 258
select statement, 400
Self-scheduling disk driver, 308
Semaphore, 153-54
binary, 155
distributed, 454
general, 155
implementation of, 276-79
monitors, relation to, 283-84
private, 182
signaling, 157
split binary, 159
Semi-synchronous send statement, 522
send statement, 296
implementation of, 488-90, 494, 496
Sentinel value, 299
Server process, 21
applications
active monitors, 302-8
barrier synchronization, 402
bounded buffer, 376-77
dining philosophers, 376-77
disk driver, self-scheduling, 308-11
distributed files, 311-14, 367-70
readers/writers, 386-89
remote database, 395-97
remote file reader, 345-48
replicated files, 389-93
resource allocation, 307
shortest-job-next allocator, 378-79
time server, 378
programmed using
Ada language, 401-6
Java language, 393-97
message passing, 302-14
multiple primitives, 384-93
remote procedure call, 365-70
rendezvous, 376-79
Server skeleton, 394
Server stub, 394
Shared-memory multiprocessor, 6-8
Shortest-job-next allocation, 180
using monitors, 217-18
using rendezvous, 378-79
using semaphores, 181-84
Shortest-seek-time disk scheduling, 227, 310
Sieve of Eratosthenes, 326-28
signal_all statement, 212-13
Signal and continue discipline, 208
Signal and wait discipline, 208
Signaling semaphore, 157
signal statement, 207-9
implementation of, 281, 285
SIMD (single instruction, multiple data),
multiprocessor, 4, 131-32
Single processor kernel, 266-70
Sisal language, 615, 625-26, 640
SJN allocation. See Shortest-job-next
allocation
Sleeping barber problem, 221-22
relation to disk-scheduling problem, 228, 232
SMP (symmetric multiprocessor), 6
SOR. See Successive over relaxation
Sorting algorithms
exchange sort, 148
merge network, 300-1
quicksort, 17
Soundness, of a logic, 58
Spanning tree, 445
Sparse matrix multiplication, 424-28
Spatial locality, 5
Speedup, of a parallel computation, 528
Spin lock, 99
Spin loop, 55
Spinning process, 57
Split binary semaphore, 159
SPMD (single program multiple data), 316,
340, 541
SR language, 406-11, 615-16
history and references, 414
SST disk scheduling, 227, 310
Stable marriage problem, 90, 356, 420
Stable prefix, of a message queue, 455
StarMod language, 412
Starvation, absence of. See Fairness
State, of a
process, 267
program, 42
Strength reduction transformation, 536
Strip mining, of loops, 611
Stripes, allocation by, 557
Strips, allocation by, 557
Strongly fair scheduling policy, 76
Structure of distributed programs. See
Distributed program structures
Successive over relaxation, 546-49
Symmetric barrier, 121
Symmetric multiprocessor (SMP), 6
Synchronization, 2. See also Condition
synchronization; Mutual exclusion
specified using await, 54-55
used for avoiding interference, 69-70
Synchronizing Resources. See SR language
Synchronous execution, 131
Synchronous message passing, 318-20.
See also CSP language
implementation of, 496-503
Synchronous multiprocessor, 131
Synchronous send statement, 318
Task parallel program, 11
Temporal locality, 5
Temporal logic, 80
Termination detection problem, 460-65
Test-and-test-and-set protocol, 101
Test-and-Set instruction, 99
Textual substitution, 60
Thread of control, 2, 184
Ticket algorithm, 108-11, 137
Tie-breaker algorithm, 104-8, 136
Tightly coupled machine, 9
Tiling, of loops, 612
Time server. See also Interval timer
using remote procedure call, 365-67
using rendezvous, 378
Timestamp, 453
Token-passing algorithm, 423, 457-65
decentralized dining philosophers, 467-71
distributed mutual exclusion, 457-60
termination detection, 460-65
Topology of a network problem, 448
Total correctness, 43, 59
Tournament barrier, 146
Transformations, in parallelizing
compilers, 608
Transputer machine, 329
Traveling salesman problem, 479-80
Tree code, 570
Tree-structured barrier, 118-20
Triangular matrix, 574
Triple, in a programming logic, 59
Tuple space, 334. See also Linda language
Turing Plus language, 251
UMA multiprocessor, 6
Unconditional atomic action, 55
Unconditionally fair scheduling policy, 75
Uniform memory access time, 6
Unisex bathroom problem, 200
Unix pipes, 20
Unroll and jam transformation, 610
V cycle, 552
V operation, 154-55. See also Semaphore
meaning of name, 188
Visualization tools, 634
W cycle, 552
Wait-free synchronization, 138
wait statement, 207-9
implementation of, 281, 285
Water molecule problem, 198, 257
Wave front synchronization, 580, 612
Weakened assertions, 66-68
Weakly fair scheduling policy, 75
Weighted voting, 392-93, 413
Work farm model, 139. See also Bag-of-tasks
paradigm; Manager/workers paradigm
Writers' preference, 177
Write set, 45, 65
ZPL language, 615, 621-23, 640