An adaptive data prefetching scheme for biosequence database search on reconfigurable platforms

ABSTRACT

Searching on DNA and protein databases using sequence comparison algorithms has become one of the most powerful techniques to better understand the functionality of particular biological sequences. However, the requirements to process the biological data exceed the ability of general-purpose processor. The core of sequence alignment algorithm was implemented as fine-grained parallel architecture that was running on a commercial-off-the-shelf (COTS) FPGA board, where supercomputer performance has been achieved. However, reconfigurable computing platforms have utilized a PCI bus as the communications channel, limiting the communication speed between the host processor and the FPGA. This communication bottleneck often offsets the application speedup enabled by FPGA. In this paper we present an adaptive data prefetching scheme to avoid reconfigurable coprocessor stalls due to data unavailability through profiling techniques and quantitative analysis. Experimental results satisfied time constraints with various query sequences and show that we can effectively eliminate a major portion of data access penalty.

REFERENCES

• 1: Alpha-Data, http://www.alpha-data.com
• 2: Xiandong Meng , Vipin Chaudhary, Bio-sequence analysis with cradle's 3SoC™ software scalable system on chip, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.967941]
• 3: Xiandong Meng , Vipin Chaudhary, Exploiting Multi-level Parallelism for Homology Search using General Purpose Processors, Proceedings of the 11th International Conference on Parallel and Distributed Systems - Workshops (ICPADS'05), p.331-335, July 20-22, 2005
• 4: Oliver, T., Schmidt, B. and Maskell, D. Hyper Customized Processors for Bio-Sequence Database Scaning on FPGAs, IEEE Transactions on Circuits and Systems II, Vol. 52, No. 12, pp. 851--855, 2005
• 5: Progeniq Pte. Ltd., http://www.progeniq.com

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms, Design, Performance

Keywords:
DMA, FPGA, Smith-Waterman algorithm, data prefetching