Biomedical Engineering Reference
In-Depth Information
Such parallelism can be exploited using fine-grain vector instructions found in com-
mon microprocessors, such as Altivec (for the PowerPC) and MMX
/
SSE (for the
Pentium).
A version of BLAST called AGBLAST developed by researchers at Apple and
Genentech exploited the Altivec instructions in the PowerPC family of CPUs to
improve BLAST performance. Experimental results showed performance improve-
ments up to a factor of five for BLAST queries with long sequences, which required
more time for calculating local alignments. Improvements were more limited for short
sequences such as ESTs.
9.4.2 Multithreading
A second approach for improving BLAST performance for individual searches is to
exploit thread-level parallelism in comparing queries to different parts of a sequence
database. As a BLAST search is usually performed against sequence databases con-
sisting of multiple sequences, searches can easily be performed in parallel using
multiple threads. A threaded BLAST search simply slices the given databases into
equal sized chunks according to the number of available processors. Each database
chunk is then distributed to a predefined processor using memory mapping. Each pro-
cessor is responsible for a thread scanning, a different database fragment. The sorted
results are stored in a global structure, which is shared by all the processors and then
combined to produce the final BLAST search result. Figure 9.2 shows the algorithm
used by multithreaded BLAST searches.
The current release of both NCBI BLAST [11] and WU BLAST [12] can be
run in multithreaded mode on shared-memory multiprocessor (SMP) machines. As
BLAST search needs to scan each database sequence at least once for each query
sequence, threaded BLAST searches are both memory and I
/
O intensive and are
•
Run individual BLAST
query in parallel
Query1
Query2
Query3
DB
•
Main thread
1.Partition database
2.Spawn worker threads
DB
3.Merge partial search
results from workers
Query1
Query2
Query3
Query1
Query2
Query3
Workers
•
DB
D
B
1.Process queries on
database fragments
Query1
Query2
Query3
2.Store results in global
data structure
DB
Query1
Query2
Query3
Figure 9.2
Multithreaded BLAST algorithm.
Search WWH ::
Custom Search