Limits...
A Systolic Array-Based FPGA Parallel Architecture for the BLAST Algorithm.

Guo X, Wang H, Devabhaktuni V - ISRN Bioinform (2012)

Bottom Line: In contrast to other designs that detect at most one hit in one-clock-cycle, our design applies a Multiple Hits Detection Module which is a pipelining systolic array to search multiple hits in a single-clock-cycle.Further, we designed a Hits Combination Block which combines overlapping hits from systolic array into one hit.These implementations completed the first and second step of BLAST architecture and achieved significant speedup comparing with previously published architectures.

View Article: PubMed Central - PubMed

Affiliation: Electrical Engineering and Computer Science Department, The University of Toledo, MS.308, 2801 W. Bancroft Street, Toledo, OH 43607, USA.

ABSTRACT
A design of systolic array-based Field Programmable Gate Array (FPGA) parallel architecture for Basic Local Alignment Search Tool (BLAST) Algorithm is proposed. BLAST is a heuristic biological sequence alignment algorithm which has been used by bioinformatics experts. In contrast to other designs that detect at most one hit in one-clock-cycle, our design applies a Multiple Hits Detection Module which is a pipelining systolic array to search multiple hits in a single-clock-cycle. Further, we designed a Hits Combination Block which combines overlapping hits from systolic array into one hit. These implementations completed the first and second step of BLAST architecture and achieved significant speedup comparing with previously published architectures.

No MeSH data available.


Architecture of processing unit of multiple hits detection module.
© Copyright Policy - open-access
Related In: Results  -  Collection


getmorefigures.php?uid=PMC4417556&req=5

fig6: Architecture of processing unit of multiple hits detection module.

Mentions: The whole architecture works as follows: first, a query sequence with 32 characters is forwarded into the systolic array so that each processing unit holds a character from the query sequence. Then the subject sequence is driven in to the systolic array by each internal clock rising edge. Meanwhile, the incoming subject character and the query character which are held by the unit are compared, if they are identity, the logic “1” would be generated; otherwise, the logic “0” would be generated. The comparison result is an input of a 3-input AND gate. Every 3 processing units maps to an AND gate. A hit is detected when the logic “1” is generated from its output. So, the systolic array with 3-input AND gates can detect multiple hits at one internal clock rising edge. The architecture of the processing unit in the systolic array is illustrated in Figure 6.


A Systolic Array-Based FPGA Parallel Architecture for the BLAST Algorithm.

Guo X, Wang H, Devabhaktuni V - ISRN Bioinform (2012)

Architecture of processing unit of multiple hits detection module.
© Copyright Policy - open-access
Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC4417556&req=5

fig6: Architecture of processing unit of multiple hits detection module.
Mentions: The whole architecture works as follows: first, a query sequence with 32 characters is forwarded into the systolic array so that each processing unit holds a character from the query sequence. Then the subject sequence is driven in to the systolic array by each internal clock rising edge. Meanwhile, the incoming subject character and the query character which are held by the unit are compared, if they are identity, the logic “1” would be generated; otherwise, the logic “0” would be generated. The comparison result is an input of a 3-input AND gate. Every 3 processing units maps to an AND gate. A hit is detected when the logic “1” is generated from its output. So, the systolic array with 3-input AND gates can detect multiple hits at one internal clock rising edge. The architecture of the processing unit in the systolic array is illustrated in Figure 6.

Bottom Line: In contrast to other designs that detect at most one hit in one-clock-cycle, our design applies a Multiple Hits Detection Module which is a pipelining systolic array to search multiple hits in a single-clock-cycle.Further, we designed a Hits Combination Block which combines overlapping hits from systolic array into one hit.These implementations completed the first and second step of BLAST architecture and achieved significant speedup comparing with previously published architectures.

View Article: PubMed Central - PubMed

Affiliation: Electrical Engineering and Computer Science Department, The University of Toledo, MS.308, 2801 W. Bancroft Street, Toledo, OH 43607, USA.

ABSTRACT
A design of systolic array-based Field Programmable Gate Array (FPGA) parallel architecture for Basic Local Alignment Search Tool (BLAST) Algorithm is proposed. BLAST is a heuristic biological sequence alignment algorithm which has been used by bioinformatics experts. In contrast to other designs that detect at most one hit in one-clock-cycle, our design applies a Multiple Hits Detection Module which is a pipelining systolic array to search multiple hits in a single-clock-cycle. Further, we designed a Hits Combination Block which combines overlapping hits from systolic array into one hit. These implementations completed the first and second step of BLAST architecture and achieved significant speedup comparing with previously published architectures.

No MeSH data available.