Biomedical Engineering Reference
In-Depth Information
32
32
28
28
24
24
20
20
16
16
12
12
8
8
4
4
0
4
8
12
16
20
24
28
32
0
4
8
12
16
20
24
28
32
Processors
Figure 15.12
Speedup of the parameter estimation for (
a
) Rhodophyta rRNA data and
(
b
) Cadherin protein data measured on the homogeneous COW.
Processors
For the protein data, the obtained speedup is better than for the DNA data. For sets
with 32 and more sequences, it is at least 12.8 for 16 processors. Even for the small
number of 16 sequences, it is 9.8 for 16 processors. The effect of increasing speedup
for larger problem sizes on identical numbers of processors is called Amdahl effect
[37, 38]. It is caused by a lower complexity of the communication overhead compared
with the time complexity of the problem size.
15.6 DISCUSSION
The parallel performance of an implementation is limited mainly by the coverage,
that is the parallel proportion of the problem, and
granularity
, that is, the amount of
work performed until communication is necessary.
The two targets of parallelizing the parameter estimation prior to phylogenetic
analysis as delineated earlier exhibit nicely the effects of coverage as well as granu-
larity. The improved parallelization introduced in Section 15.5 aims at the increase
of the coverage, after runtime measurements have identified step (v) as consuming
most of the runtime (nonparallelized on one processor). After parallelization of step
(ii), the relative duration of step (v) became dramatically apparent (cf. Fig. 15.7), now
being the limiting time factor to the parameter estimation.
Increasing the coverage alone does not guarantee a good parallel performance.
Within the different parallel regions their granularity plays an important role, deter-
mined by the size of the independent tasks as well as the scheduling technique
assigning batches of tasks (grains) to the processors. Finding efficient ways to paralle-
lize the parameter estimation was much more difficult than in the MLStep and the
PStep of the subsequent tree reconstruction analysis, where we have to execute a
large number of independent tasks with long durations relative to the communication
overhead [39].
Search WWH ::
Custom Search