Phylogenetic Parameter Estimation on COWs - Parallel Computing for Bioinformatics and Computational Biology - page 358

Figure 15.5 Gantt charts of a single execution of the pairwise distance computation step for
Cadherin protein data using GSS on a heterogeneous COW. Assignment order under ( a ) worst
case scenario: The slowest processor receives the largest available batch; ( b ) best case: starting
with the fastest CPU. Each row corresponds to one processor sorted by speed according to
the above assignments. The first row represents the master process distributing tasks to the
processors from top to bottom sending new task batches whenever a processor has finished its
last batch. Light gray areas depict work and dark gray areas depict idle time and communication
or, in case of the master process (first line), coordinating and scheduling the tasks. Vertical
arrows represent communication events.
there is no significant difference among the runtimes of the GSS in the best case and
SGSS under both scenarios (about 9 s), GSS shows a significant increase of about
60% of its runtime to about 15 s for the worst case scenario (compared with the other
cases) and keeping more than 50% of the workers waiting for the tasks to be finished.
Although the impact might not be as harsh on average, one can clearly see that there
will be a severe increase of running time whenever one of the slower machines gets
one of the larger task packages. This effect has been eliminated efficiently by the
SGSS algorithm.