Information Technology Reference
In-Depth Information
coupled problem, because many numerical methods involve solving the ODE part
for every spatial grid point. In this case, when the number of spatial grid points is
large, the task of solving all these ODEs is again embarrassingly parallel.
Even when parallelism exists, work division can still be a challenge. Our pre-
vious examples are simple, because the work division there is essentially a one-
dimensional partitioning applied to structured data entities. In the case of two- or
three-dimensional unstructured computational meshes, partitioning not only has to
make sure that each processor has approximately the same amount of work, but also
has to keep the amount of resulting communication as low as possible. In the case
of time-dependent problems that have a dynamically changing work load, dynamic
load balancing can be another challenge.
10.2.6
Performance Analysis
The prominent reason for adopting parallel computing, time saving is also the main
measure for evaluating the quality of a parallelized code. If we denote by
T.P/
the computing time for solving a problem using
P
processors, the very important
concept of
speedup
is thus defined as
T.1/
T.P/
;
S.P/ D
(10.15)
where
T.1/
should be the computing time used by a serial code, and not a paralleli-
zed code run on one processor. This is because a parallel implementation typically
has some additional operations that are not needed in a serial implementation.
An ideal result of parallelization is that the entire serial code is parallelizable with
a perfect work division and that the parallelization-induced communication cost is
negligible. In such an ideal situation, we can expect that
T.P/
is exactly one
P
th of
T.1/
, thus
S.P/ D P
. The ideal situation is rarely achievable, so we understand-
ably would like the value of
S.P/
to be close to
P
; the larger the better quality of
the parallelization. An equivalent quality measure, called
parallel efficiency
, can be
defined as
S.P/
P
T.1/
PT.P/
;
.P / D
D
(10.16)
which will have a normalized value between 0 and 1.
Amdahl's Law
The first obstacle to perfect parallelization is that there can exist some bits of a serial
code that are inherently sequential. Suppose a serial code has a fraction of size
˛
