Parallel_Programming_In_C_With_MPI_And_OpenMP_2003_Quinn.pdf

(19321 KB) Pobierz
PERFORMANCEAN4LYSIS FORMULAS
Amdahl's Law
Let
f
be the fraction of operations in a computation that must be performed
sequentially, where 0:::
f
:::
1. The maximum speedup
1/1
achievable hy a parallel
computer with
p
processors performing the computation is
I
.
l{r<-----
- f
+
(1-
fJI
p
Gustafson·Barsis's Law
Given a parallel program solving a problem of size
Il
using
p
processors, let
s
denote the fraction of total execution time spent in serial code. The maximum
speedup
1/1
achievable by this program is
1/1
::S
iJ
+
(I -
p)s
Karp·Flatt Metric
Given a parallel romputationexhibiting speedup 1/Ion
p
processors, where
p
>
I,
the experimentally determined serial fraction
e
is defined
to
be
IN-lip
e=--------
I-lip
Isoefficiency Relation
Suppose a parallel system exhibits efficiency
<{n,
p).
where
II
denotes problem
size and
p
denotes number of processors. Define C
=
E(n.
p)1
(\
[(II,
(J
i).
Let
T(n,
I) denote sequential execution time, and let
1;,(1l,
p)
denote p8rallcl over-
head (total amount of time spent by all processors performing communications
and redundant computations).
In
order
to
maintain the same level of efficiency as
the number of processors increases, problem size must be increased so that the
following inequality is satisfied:
1'(/1,
I)
~
CTu(n,
p)
Parallel Programming
in
C with
MPI
andOpenMP
Michael
J,
Quinn
Oregon Stale UniveJ:rity
II
Higher Education"
Boston Burr Ridge, IL Dubuque, 11\ Madison, WI New York San Francisco St. Louis
Bangkok Bogota Caracas Kuala Lumpur Lisbon London Madrid Mexico City
Milan Montreal New Delhi Santiago Seoul Singapore Sydney Taipei Toronto
PARALLEL PROGRAMMING IN C WITH MPI A!'lD OPENMP
International E;lition
2003
Exclusive rights by McGraw"Hili Education (Asia), for manufacture and export. This
book
cannot
be
re"exportcd from the country to which it is sold by McGraw-Hill. The
International Edition is not available in North Amenca.
Published by McGraw-Hili.
a
business unit of The McGraw·Hill Companies,
Inc., 1221
Avenue of the Americas, New York, NY
10020.
Copy light
©2004
by The McGraw·Hill
COlTllJanies,
Tnc.
All rights reserved. No pari or this publication may be reproduced
or
distributed in any form or
by
any meaRS, or stored in a database or retrieval system,
without
tlie
prior written consent or The McGt-dw"HilI Companies, Inc., including, but
nol limited to, in any network or other electronic storage or transmission, or broadcast for
distance learning.
Some ancillaries, il1tluding electronic and prinl comJJOnents, liIay not be available to
customers outside the United Stales.
10 09 08 07 06
20
09 08 07
CTP SLP
Ullrary of Congress Cataloging·in"Pllblication Data
Quinn, Michael .1. (Michael Jay)
Parallel programming in C with MPI and OpenMP
f
Michael
J.
Quinn...
·1 ,t ed.
p.
cm.
ISIlN
007-282256-2
I.
C (Computer
progrdm
language). 2. Par1lllel programming (Computer ,cience).I.1Jtle.
QA76.73.CI5Q55 2004
005.13"3-dc21
2003046371
elP
When
ordering this title,
use
ISBN 007·123265"6
Printed in Singapore
IVww.mhhe.com
W'lth gratitude lor their rove, support, and guidance,
I dedicate this book to mV parents,
Edward and Georgia
Quinn.
Preface xiv
1 Motivation and History I
2 Parallel Architectures 27
3
Parallel Algorithm
Design
63
4
Message-Pa,sing Programming 93
5 The Sieve
of Eratusthenes
It5
6 Floyd's Algorithm 137
7
Performance Analysis 159
8
Matrix-Veltor Multiplication
178
9
Document Classification 216
10 Monte C3!'lo Methods 239
11
Matrix Multiplication 273
_
12
Solving Linear Systems 290
13
Finite Difference Methods 318
14
Sorting 338
15
The Past Fourier Transform 353
16
Combinatorial Search 369
17
Shared-Memory Programming 404
18
Combining MPI and OpenMP 436
Appendix
A MPI Punctions 450
Appendix
B
Ulilily
Functions 485
Appendix C
Debugging
MPI
Programs
505
Appendix D
Review of Complex Numbers 509
Appendix E
OpenMP Functions 513
Bibliography 515
i',uthor
Index
520
Subject
Index 522
iv

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin