Biomedical Engineering Reference
In-Depth Information
most effective on large SMPs. Database partitioning, thread creation and manage-
ment, memory contention, and collecting search results can result in large overheads,
which prevent BLAST from achieving good scalability. However, according to exper-
imental studies [13], multithreaded BLAST appears to achieve good performance in
practice.
9.4.3 Replicated Databases
Replicating sequence databases on distributed memory systems (replicated BLAST)
is one of the most popular methods for providing high performance BLAST searches.
The implementations usually adopt a master
/
worker paradigm to maintain load bal-
ance. When the database size is relatively small, a full copy of the sequence database
may be stored in memory on each node. Batched queries can be split up evenly and
assigned to each node. The computing nodes then perform local BLAST searches and
send the results back to the master node. Although this method will not reduce the
search time for individual queries, the total search time can be reduced when there
are a large number of number batched queries. Figure 9.3 shows the algorithm used
by BLAST searches using replicated sequence databases.
One obvious advantage of replicated BLAST is that the only parallelization over-
head is distributing the queries and collecting the final results. It is thus fairly easy
to achieve near-linear speedups for large numbers of BLAST queries, as long as the
database is not too large. The disadvantages of replicated BLAST are that it needs
sufficient memory and disk space to store the database on each node and requires a
large number of queries (at least equal to the number of computing nodes) to exploit
Query1
Query2
Query3
1. Replicate database on
cluster of PCs
DB
2. Run multiple BLASTs in
parallel
Master
•
1. Assign query sequences
to workers
2. Collect search results
from workers
Query1
DB
•
Workers
Query2
1.BLAST assigned queries
on database
2. Send results back to
master
DB
Query3
DB
Figure 9.3
Replicated BLAST algorithm.
Search WWH ::
Custom Search