|
Distributed and Parallel Computing Hesham El-Rewini and Ted G. Lewis 1997 | 469 pages ISBN: 1884777511 |
|||
| $60.00 | Softbound print book | Out of print (?) | |
Index
Aaccess mode 378
active positions 267
Akl, S.G. 122, 143
Algorithm
A_Elect_Leader_Simple 167-168
A_Spanning_Tree 172
A_Template 155
AllSums_EREW 128
Broadcast_EREW 122
MatMult_CREW 130
MST_EREW 143-144
ParMerge_CREW 139-140
ParSearch_CREW 135-136
S_Elect_Leader_Improved 164, 166
S_Elect_Leader_Simple 160
S_Spanning_Tree 170
S_Sum_Hypercube 152-153
S_Template 152
Sort_CRCW 133
Sum_EREW 127
algorithms
heuristic 239-246
optimal 225, 234, 248, 250
Alliant
Graphics Performance Characterization Group 70
Amdahl, Gene xvii, 50
Amdahl's Law 43, 50-52
American Airlines 28
Angluin, D. 158, 159
Apple 5
applets 387
arrays 401-402
declaring the array 401
initializing the array 401
asynchronous transfer mode (ATM) 31
AT&T
SPECmark 71
TP monitors 35
B
Baase, S. 143
barriers 27, 307-308
Barsis, Ed 43, 53
BASIC 4
batched 2-5
BBN Butterfly 102
behavior 389
Bell, Gordon 52, 75
benchmarks 44, 70
Dhrystone 72
Fermi 73
Ghrafstone 70
Gilbreath 72
JRR 73
Linpack 70, 72-73
Livermore Loops 70, 73
Mendez 73
NAS Kernel 73
PERFECT Club 70, 73
Picture Level 70
Sieve of Eratosthenes 72
SLALOM 75
SPECmark 71
Stones 73
synthetic 70
TP1 70
UNIX Today! 70
WebSTONE 76-77
Whetstone 70, 71
Bento 111
Bhuyan, L. N. 90
blocking 102
Bokhari, S. H. 251
Bräunl, Thomas 54, 257
buffer 301
Bull: SPECmark 71
Burroughs Corporation xvii
byte code 388
Byzantine failures 175-178
C
C 4, 290
C++ 4, 10, 290
cache coherency 92-93
write-update policy 92
Canon: CORBA 28
Carnegie Mellon University 21
Cm* 102
CDC: SPECmark 71
Center for Supercomputer Research Laboratory (CSRL) 73
certification 184
Chen, S. 253
CILab
OpenDoc/SOM 107, 114
system object model (SOM) 112
libraries 403
client/server (CS) 27-28, 31-35, 370-372, 409, 412
COBOL 4
coding and unit testing 183
Coffman, E. G. 228
collective operations 345-352
Commodore personal computers 5
common gateway interface (CGI) 105
Common Object Request Broker Architecture (CORBA) 28, 107, 110-112, 114
communication 225, 232, 336
delay 230, 239
general 271, 276-279
graph 149
models 230-232
nonblocking 338-340
one-sided 372-377
parallel 271
regular 271-275
rendezvous 343
buffered send 337
ready send 338
synchronous send 337
communicators 329-332
intracommunicators 329
MPI_COMM 329
MPI_COMM_NULL 331
MPI_COMM_SELF 329
MPI_COMM_WORLD 329-331
MPI_UNDEFINED 331
SPECmark 71
component object model (COM) 36, 108
components 27
compound document 36, 83
Computer Society 75
configuration 259
CONFIGURATION (keyword) 259
connection 260
compound 262
parameterized 261
uni-directional 260
context switching 404
control flow statements 392
for 392-393
if/else 392
switch 392-393
while 392
coordinates 334
copy-back update policy 93
Cosnard, M. 122
cost of the parallel algorithm 123
cost optimal 124
coupled 11, 21-27
crash failures 175-176
Cray
CS6400 78
Origin2000 78
T3E 78
vector Cray 11
Y-MP 45
creating objects 390-391
creating threads 404-406
critical path 228, 243
Curnow, J. P. 70
cutset 248
D
data distribution 15
Data General
minicomputers 5
SPECmark 71
data packing 302-303
data partitioning 19
data types 392
dataflow parallelism 26
DataInputStream class 411
DataOutputStream class 411
data-parallel 55
programming 19
Digital Equipment Corporation 79
CORBA 28
DECstation 257
Graphics Performance Characterization Group 70
minicomputers 5
ObjectBroker 111
SPECmark 71
Delphi 36
Desurvire, E. 6
detailed design 183
Dhall, S. 129
diameter 99
dirty bit 92
displacement 379
distributed compound documents 83
distributed computing 2-3
distributed computing environment (DCE) 35
distributed object technology 107
distributed objects 83
distributed processing 7
distributed program 6, 7
distributed memory 26
multiple instruction, multiple data (MIMD) 24
divide-and-conquer 43
dominant sequence 243
Dubois, M. 92, 93
Dupont: SPECmark 71
Dupont Pixel Systems: Graphics Performance Characterization Group 70
duty cycle 89
dynamic data exchange/dynamic link library (DDE/DLL) 108
dynamic model 362
dynamic networks 100-103
multistage 100
random 100
single-stage 100
E
elapsed time 59
El-Rewini, H. 232, 234, 238, 239, 242, 251
Encina 11
end-user programming 27
ensured desktop 2-3, 5, 11
etype 379
Evans & Sutherland: Graphics Performance Characterization Group 71
exceptions 400-401
execution time 225, 230
extension 390
F
fan 195, 197-198, 213
Feng, T-Y. 86, 102
Fermi National Accelerator Lab 73
fields 389, 394-395
filetype 379
fine-grained 11, 17-18, 21-24, 31
Fischer, M. 176
FORTRAN 4, 290
Fortune and Wyllie 119
Freund, R. 253
front-end computer 257
Fujii, M. 228
Fujitsu
VPP 300 78
MPI_Allreduce() 347
MPI_Barrier() 343
MPI_Bcast() 349
MPI_Bsend_init() 340
MPI_Cart_coords() 334
MPI_Cart_create() 332
MPI_Cart_rank() 334
MPI_Close_port() 369
MPI_Comm_accept() 368, 370-371
MPI_Comm_connect() 369, 370-371
MPI_Comm_create() 331
MPI_Comm_dup() 331
MPI_Comm_get_parent() 366
MPI_Comm_group() 330, 363
MPI_Comm_rank() 329
MPI_Comm_remote_group() 363
MPI_Comm_remote_size() 363
MPI_Comm_size( 363
MPI_Comm_size() 330
MPI_Comm_spawn() 363-365, 370
MPI_Comm_spawn_multiple() 364, 366
MPI_Comm_split() 331
MPI_File_close() 377
MPI_File_get_view() 380
MPI_File_iread() 382
MPI_File_iread_at() 382
MPI_File_iread_shared() 382
MPI_File_iwrite() 383
MPI_File_iwrite_at() 383
MPI_File_iwrite_shared() 383
MPI_File_open() 377
MPI_File_read() 382
MPI_File_read_all() 382
MPI_File_read_at() 382
MPI_File_read_at_all() 382
MPI_File_read_orderd() 382
MPI_File_read_shared() 382
MPI_File_set_view() 379, 380
MPI_File_write() 383
MPI_File_write_all() 383
MPI_File_write_at() 383
MPI_File_write_at_all() 383
MPI_File_write_orderd() 383
MPI_File_write_shared() 383
MPI_Finalize() 325
MPI_Gather() 350
MPI_Get() 374
MPI_Graph_create() 334
MPI_Group_ range_incl() 328
MPI_Group_difference() 328
MPI_Group_excl() 326, 327
MPI_Group_incl() 327, 328
MPI_Group_intresection() 328
MPI_Group_range_excl() 326, 327
MPI_Group_range_incl() 327
MPI_Group_union() 328
MPI_Ibsend() 339
MPI_Init() 325, 329, 363
MPI_Initialize() 325
MPI_Intercomm_create() 363
MPI_Irecv() 338
MPI_Irsend() 339
MPI_Isend() 338, 339
MPI_Issend() 339
MPI_Lookup_name() 369
MPI_Open_port() 368
MPI_Publish_name() 368
MPI_Put() 374
MPI_Recv() 337, 343
MPI_Recv_init() 340
MPI_Reduce() 346
MPI_Rsend() 338
MPI_Rsend_init() 340
MPI_Scan() 348
MPI_Scatter() 350
MPI_Send() 337
MPI_Send_init() 340
MPI_Ssend() 337
MPI_Ssend_init() 340
MPI_Start() 340
MPI_startall() 340
MPI_Test() 339
MPI_Testall() 340
MPI_Testany() 340
MPI_Type_struct() 342
MPI_Unpublish_name() 369
MPI_Wait() 339
MPI_Waitall() 340
MPI_Waitany() 340
MPI_Win_complete() 375, 376
MPI_Win_fence() 376
MPI_Win_create() 372, 373, 374
MPI_Win_lock() 377
MPI_Win_post() 375, 376
MPI_Win_start() 375, 376
MPI_Win_unlock() 377
MPI_Win_wait() 375, 376
pvm_barrier() 307, 308
pvm_bcast() 304
pvm_getinst() 299
pvm_getrbuf() 302
pvm_getsbuf() 302
pvm_gettid() 299
pvm_gsize() 299
pvm_initsend() 301, 302
pvm_joingroup() 298
pvm_lvgroup() 298
pvm_mcast() 303, 304
pvm_mkbuf() 301, 302
pvm_myid() 296
pvm_nrecv() 305
pvm_packf() 302, 306
pvm_parent() 296
pvm_pkbyte() 302
pvm_pkcplx() 302
pvm_pkdcplx() 302
pvm_pkdouble() 302
pvm_pkfloat() 302
pvm_pkint() 302
pvm_pklong() 302
pvm_pkshort() 302
pvm_pkstr() 302, 306
pvm_pkuint() 302
pvm_pkulong() 302
pvm_pkushort() 302
pvm_precv() 306
pvm_psend() 304, 306
pvm_recv( ) 307
pvm_recv() 304
pvm_reduce() 309
pvm_send() 303
pvm_setrbuf() 302
pvm_setsbuf() 302
pvm_spawn() 293, 296, 297, 298
pvm_tidtohost(id) 296
pvm_trecv() 305
pvm_unpackf() 306
pvm_upk*() 306
pvm_upkbyte() 306
pvm_upkcplx() 306
pvm_upkdcplx() 306
pvm_upkdouble() 306
pvm_upkfloat() 306
pvm_upkint( ) 306
pvm_upklong() 306
pvm_upkshort() 306
pvm_upkstr() 306
pvm_upkuint() 306
pvm_upkulong() 306
pvm_upkushort() 306
Gabow, H. 228
Gantt chart 192, 224, 231
Garay, J. 177
gather 350
Gaussian Blur 30
Gerasoulis, A. 243
get 374
gigaflop barrier 45
global computers 28
Gold Hill: CORBA 28
Goodman, J. R. 93
Gordon Bell Prize 21, 52, 75
grain 6
grain size 2, 6-8, 11, 241
graph topology 334-335
graphical user interface (GUI) 32
Graphics Performance Characterization Group 70
gray code 96
grid 260
Grosch, Herb 44
Grosch's Law 43, 44-45
Gustafson, John 43, 53, 76
Gustafson-Barsis formula 55
Gustafson-Barsis Law 43, 52-57
H
Hamming code 98
Hamming distance 98
heavyweight process 404
heterogeneous computers 290
heterogeneous environments 252
heuristics 193
Hewlett-Packard 79
Convex SPP 1200 78
Convex SPP 1600 78
CORBA 28
Graphics Performance Characterization Group 71
SPECmark 71
TP monitors 35
Hirschberg, D. 161
hit rate 89
hop 87
Hu, T. C. 226
hypercubes 95
SIMD 99
hypertext markup language (HTML) 29, 104-105
I
I/O automata 153
IBM 79
Graphics Performance Characterization Group 71
IBM-PC 257
personal computers 5
RP3 102
RS/6000 Powerparallel 78
RS6000 257
SOMObjectMgr 111
SPECmark 71
System/360 4
T. J. Watson Research Center 102
TP monitors 35
Illiac V xvii
incremental development 181
indexing 263-267
Informix 12
inheritance 390
initiating task 291
input streams 411
instance variables 389
instantiation 390
Intel Corporation 45, 79
massively parallel machine 45
P6 6
P7 50
P8 50
Paragon 12, 26, 257
Paragon XP 76MP 78
Pentium 6
SPECmark 71
Teraflops Pentium Pro 78
interconnection network 47
topology 86
interface definition language (IDL) 28, 113
interfaces 399-400
Intergraph
SPECmark 71
megacomputer 103-106
interval ordered tasks 227-228
iPSC/2 85
isoefficiency metric 60
J
JaJa, J. 135, 143
Java xix, 104, 387
JavaBeans 107, 115
packages 403
virtual machine 388
kernels 70, 72
Kronsjo, L. 122
Kumar, V. 129, 135, 143
Kung, H. T. 21
L
Lakshmivara, S. 129
Lamport, L. 176
large grained 11, 21, 25-27, 29, 35-37
lazy parallelism xviii
Le Lann, G. 159
leader election problem 157-159
Lee, C. 250
Lewis, T. 242
lightweight process 404
Lo, V. 251
LOAD (statement) 280
load balancing 14
loading factor 61
locks 16, 24, 376
lockstep synchronization 258
loop-carried dependency 9
loosely coupled 11, 29-30, 35, 102
Lotus Notes 12
Lundell, S. 303
Lynch, N. 150, 153, 159, 175
M
main method 402-403
MasPar 257
massively parallel 85
master-slaves structure 291
matrix multiplication 283-284, 313-317, 353-355
using threads 415
Megatek: Graphics Performance Characterization Group 71
Meiko 21
Mendez, Raul 73
mesh 266
message complexity 157
message passing 26, 84, 300
Message-Passing Interface (MPI) 31, 324, 362
data types, basic 341
data types, derived 340
Forum 362
tasks 324
message-passing system 83-85, 119, 149
synchronous 150
methods 389, 395-396
DDE/DLL 108
OLE 36
OLE/COM 107, 108, 114
Open Database Connectivity (ODBC) 33
Windows 3.x 108
Windows 95 108
Windows NT 108
million floating-point operations per second (MFLOPS) 43
million instructions per second (MIPS) 6, 43
MIPS: SPECmark 71
miss rate 89
Modula-2 257, 281
Montry, Gary 76
Moore, Gordon 45
Moore's Law 6, 45-46
Moses, Y. 177
Motorola: SPECmark 71
MP-1 257
MP-2 257
MPI_BYTE 341
MPI_CHAR 341
MPI_COMM_WORLD 363, 364
MPI_DOUBLE 341
MPI_FLOAT 341
MPI_Group 326
MPI_Info 365
MPI_INT 341
MPI_LONG 341
MPI_LONG_DOUBLE 341
MPI_MODE_APPEND 378
MPI_MODE_CREATE 378
MPI_MODE_DELETE_ON_CLOSE 378
MPI_MODE_EXCL 378
MPI_MODE_RDONLY 378
MPI_MODE_RDWR 378
MPI_MODE_SEQUENTIAL 378
MPI_MODE_UNIQUE_OPEN 378
MPI_MODE_WRONLY 378
MPI_PACKED 341
MPI_UNIVERSE_SIZE 363
MPI_UNSIGNED 341
MPI_UNSIGNED_CHAR 341
MPI_UNSIGNED_LONG 341
MPI_UNSIGNED_SHORT 341
Multimedia Extensions (MMX) xix, 50
multiple instruction, multiple data (MIMD) 24, 26, 30
models 24
multistage interconnection network (MIN) 100
nonblocking network 102
omega 100
multithreading 404-409
mutual exclusion 24, 406-408
mutual exclusion lock 24
N
NAS (NASA/Ames Suite) 74
NASA Ames Research Center 74
NASA/Ames 73
National Institute for Standards and Technology (NIST) 71
n-body problem 184-189
NC-class 124-125
NCR
SPECmark 71
network graph, two-terminal 248
network paradigm 6
node 86
nonblocking send/receive 338
non-uniform memory access (NUMA) 86, 102
North Star personal computers 5
Novell Tuxedo 35
NP-completeness 193, 223, 237-238, 251
NP-complete problems 125, 236
number of hops 87
O
Object Data Base Management Standard (ODBMS) 114
Object Database Management Group (ODMG) 114
ODMG-93 115
object linking and embedding (OLE) 108
Object Management Group (OMG) 28, 107, 112
object orientation 387
object references 390
object request broker (ORB) 28, 111
ObjectDesign: CORBA 28
object-oriented paradigm 389
objects 389, 393-394
on-line transaction processor (OLTP) 12, 37
Open Systems Foundation: RPC mechanisms 111
ORACLE 11, 12
output streams 411
override 390
P
Papadimitriou, C. H. 227
par 195, 201-202
paradigms of computing 4
Parallaxis 257, 259
parallel applications 412
parallel computing 2, 48
parallel I/O 377-383
parallel operations 267-269
parallel processing 7
parallel random access machine (PRAM) 119-120
CREW PRAM 121
ERCW PRAM 121
EREW PRAM 121-122
environment 300
partitioning 7-10, 253
Pascal 4
P-complete problems 125
P-completeness 124-125
PERFECT (PERFormance Evaluation for Cost-effective Transformations) 73
Phillips: CORBA 28
pipe 195, 203-205
pipeline 17-18, 21, 49
polylogarithmic 125
PowerBuilder 11, 12, 36
precedence constraints 307
precedence synchronization 343
preliminary design 183
Prim 143
Prime 28
minicomputers 5
procedural oriented 389
processor
efficiency 60
speed 60
utilization 59
put 374
Q
Quinn, M. 143
R
race conditions 24
rank 324, 334
rate of arrival 61
read lock 25
receive 300
nonblocking 305
timeout 305
MPI_BOR 347
MPI_BXOR 347
MPI_LAND 347
MPI_LOR 347
MPI_LXOR 347
MPI_MAX 347
MPI_MIN 347
MPI_PROD 347
MPI_SUM 347
reliability xviii
remote memory access (RMA) 372
remote memory access synchronization 375-377
remote procedure call (RPC) 34, 114
nonblocking 34
response time xviii, 60
reverse-engineering 181, 205
Rice, John 73
run time 123
Runnable interface 406
run-time environment 362-363
S
Sake, Mark 76
Sandia National Laboratories 76
scalability 64, 85
scan 348
scatter 350
scheduling 191-194
dynamic 223
heuristic 194
homogeneous environments 253
nondeterministic 223, 241-242
list scheduling algorithms 225
model 223-225
precedence constrained scheduling (PCS) 224
priority-based 242-243
problem 222, 222-223
static 223
two processor 228-229
Sequent Computer
MIMD systems 12
S27 90
S81 90
shared-memory MIMD machines 88
Symmetry 26, 90, 91
Sethi, R. 228
setting the context 267
SGI 79
Origin2000 85
SGI/Cray Origin2000 78
shared-memory MIMD machines 88
shared memory
multiple instruction, multiple data (MIMD) 24-25
single instruction, multiple data (SM SIMD) machine 120
virtual 102
shared database 35-38
shared memory system 83-84, 119
switch-based 83
Siemens: SPECmark 71
Silicon Graphics, Inc. 76
MIMD systems 12
multiprocessor servers 84
SPECmark 71
Sinclair, J. 161
single instruction, multiple data (SIMD) 11, 18-21
SLALOM Benchmark (Scalable, Language-independent, Ames Laboratory, One-minute Measurement) 75
SmallTalk 4
snoopy cache protocol 93
Socket class 410
sockets xix, 34, 409-411
active 410
passive 409
software agent 105
Solbourne: SPECmark 71
Sollin 143
space complexity 123
speedup 51, 66
SPMD Meiko 12
SQL 11
standalone applications 387
standard generalized markup language (SGML) 29
standard graphical markup language (SGML) 29
Standard PL/I 4
star graph 291
star network 96
Stardent: SPECmark 71
state machine 151
static networks 94-100
Stenstrom 93
Stone, Harold 248
STORE (statement) 280
Strecker, W. D. 90
String class 402
subclass 390
subclassing 398
subscalar processors 89
Sun Microsystems
Java 29
JavaBeans 28
MIMD systems 12
multiprocessor servers 84
shared-memory MIMD machines 88
SPARCstation 257
SPECmark 71
TP monitors 35
RPC mechanisms 111
supercomputer 45
super-linear speedup 67
superscalar parallelism 48-49
superscalar processors 89
supervisor-workers structure 197, 291, 291-293, 352, 370-371
Sybase 12
symmetric multiple processors (SMP) 35, 86
systems 83
synchronization 16, 342-345
mechanism 24
synchronous message-passing model 150-153
system architecture 11
system object model (SOM) 36, 112
system testing and tuning 183
systolic arrays 21-23, 96
T
Tandy personal computers 5
task 195, 195-197
task allocation 246-252
optimal 248
problem 223
task graphs 192, 224-225
clustering of 243
in-forest 225-227, 232
interval order 225
out-forest 225-226, 232
task identifier (TID) 296
task rank 329-330
Tektronix: Graphics Performance Characterization Group 71
TeraKIPS 6
Tesler, Lawrence 3
Thakkar, S. 92, 93
Thinking Machines Corporation CM-1 21
thread 404
3COM: CORBA 28
throughput xviii, 44, 60
throw statement 400
tightly coupled 11, 17-21, 102
time complexity 123, 157
time sharing 2, 3, 5
torodial mesh 96
TP monitors 35
Transaction Processing Consortium (TPC) 58
Transarc Encina 35
transmission control protocol/internet protocol (TCP/IP) 29
tree 195, 198-201
trivially parallel 14, 43
Trystram, D. 122
try-catch-finally clause 401
Tuxedo 11
U
Ullman, J. 236
uniform memory access (UMA) 102
Unisys
SPECmark 71
V
validation 184
variables
vector 262
very long instruction word (VLIW) 50
virtual connections 259
virtual machines 258
virtual processors 258, 259, 265
virtual topologies 332-335
VisiCalc 5
Visual BASIC 11, 12, 36
von Neumann computer 257, 258
von Neumann machine 46, 47
von Neumann, John xvii, 27, 46
von Neumann's bottleneck 43
W
Weicker, R. P. 72
Wichmann, B. A. 70
window fence 376
Workstation Laboratories: Ghrafstone benchmark 70
World Wide Web (WWW) 12, 29, 83, 85, 104-105, 107, 115
write lock 25
write-once protocol 93
write-through 92
X
XDR 301
Y
Yang, T. 243
Yannakakis, M. 227
DESCRIPTION
Distributed and Parallel Computing is a comprehensive survey of the state-of-the-art in concurrent computing. It covers four major aspects:
- Architecture and performance
- Theory and complexity analysis of parallel algorithms
- Programming languages and systems for writing parallel and distributed programs
- Scheduling of parallel and distributed tasks
Many books on parallel computing have been published during the last 10 years or so. Most are already outdated since the themes and technologies in this area are changing very rapidly. Particularly, the notion that parallel and distributed computing are two separate fields is now beginning to fade away; technological advances have been bridging the gap. Distributed and Parallel Computing is unique in recognizing how distributed systems are utlized for parallel computations. The coverage and the contents represent the state of the art.
Distributed and Parallel Computing is designed for computer science and engineering students as well as professionals in the field (programmers, managers, technologists).