skip to main content
10.1145/1328554.1328565acmconferencesArticle/Chapter ViewAbstractPublication PagesscConference Proceedingsconference-collections
research-article

Implementation of the Smith-Waterman algorithm on a reconfigurable supercomputing platform

Published: 11 November 2007 Publication History

Abstract

An innovative reconfigurable supercomputing platform -- XD1000 is developed by XtremeData Inc. to exploit the rapid progress of FPGA technology and the high-performance of Hyper-Transport interconnection. In this paper, we present the implementations of the Smith-Waterman algorithm for both DNA and protein sequences on the platform. The main features include: (1) we bring forward a multistage PE (processing element) design which significantly reduces the FPGA resource usage and hence allows more parallelism to be exploited; (2) our design features a pipelined control mechanism with uneven stage latencies -- a key to minimize the overall PE pipeline cycle time; (3) we also put forward a compressed substitution matrix storage structure, resulting in substantial decrease of the on-chip SRAM usage. Finally, we implement a 384-PE systolic array running at 66.7MHz, which can achieve 25.6GCUPS peak performance. Compared with the 2.2GHz AMD Opteron host processor, the FPGA coprocessor speedups 185X and 250X respectively.

References

[1]
Altera Corporation, StratixII Device Handbook, http://www.altera.com/, 2007
[2]
CLC Bio Inc., http://www.clcbio.com/, 2007
[3]
E. Chow, T. Hunkapiller, J. Peterson, M. S. Waterman, "Biological Information Signal Processor," in Proc. Int. Conf. ASAP (M. Valero et al., eds.), Los Alamitos, CA, pp: 144~160, IEEE CS, September 1991
[4]
O. Gotoh, "An Improved Algorithm for Matching Biological Sequences", Journal of Molecular Biology, 162, pp: 705~708, 1982
[5]
J. D. Hirschberg, R. Hughey, K. Karplus, Kestrel: "A programmable array for sequence analysis", In: Proc. Int. Conf. ASAP '96, IEEE CS, pp: 25~34, Chicago, IL, 1996
[6]
D. T. Hoang, "A systolic array for the sequence alignment problem", Brown University, Providence, RI, Technical Report, pages CS-92-22, 1992
[7]
D. T. Hoang, "Searching genetic databases on splash 2", Proc. IEEE Workshop on FPGAs for Custom Computing Machines, pp: 185~192, CS Press, Los Alamitos, CA, 1993
[8]
R. Hughey, D. P. Lopresti, "B-SYS: A 470-processor programmable systolic array", Proc. Int. Conf. Parallel Processing (C.Wu, ed.), vol. 1, (Boca Raton, FL), pp: 580~583, CRC Press, August 1991
[9]
HyperTransport Consortium, http://www.hypertransport.org/, 2007
[10]
H. T. Kung, C. E. Leiserson, "Systolic Arrays for VLSI", Interim report, Department of Computer Science, Carnegie Mellon University, December 1978
[11]
H. T. Kung, C. E. Leiserson, "Algorithms for VLSI Processor Arrays", Introduction to VLSI Systems (C. A. Mead and L. A. Conway, eds.), chapter 8.3, pp: 271~292, Addison-Wesley, 1980
[12]
H. T. Kung. "Why systolic architectures?", IEEE Computer, 15(1), pp: 37~46, January 1982
[13]
Richard J. Lipton and Daniel Lopresti, "A Systolic Array for Rapid String Comparison", Proceedings of the Chapel Hill Conference on Very Large Scale Integration, pp: 363~376, 1985
[14]
D. P. Lopresti, "P-NAC: A Systolic Array for Comparing Nucleic Acid Sequences", IEEE Computer, 20 (7), pp: 98~99, 1987
[15]
National Center for Biotechnology Information, http://www.ncbi.nlm.nih.gov/, 2007
[16]
Timothy Oliver, Bertil Schmidt, "High Performance Biosequence Database Scanning on Reconfigurable Platforms", Proceedings of the 18th IPDPS, 2004
[17]
Timothy Oliver, Bertil Schmidt, Douglas Maskell, "Hyper Customized Processors for Bio-Sequence Database Scanning on FPGAs", FPGA'05, Monterey, CA, 2005
[18]
T. F. Smith, M. S. Waterman, "Identification of Common Molecular Subsequences", Journal of Molecular Biology, 147(1): pp: 195~197, 1981
[19]
TimeLogic Corp., http://www.timelogic.com/, 2005
[20]
XtremeData, Inc., XD1000 Development System, http://www.xtremedatainc.com/, 2007
[21]
C. T. White, R. K. Singh, et al. "BioSCAN: A VLSI-based System for Biosequence Analysis", IEEE International Conference on Computer Design: VLSI in Computers and Processors, pp: 504~509, IEEE Computer Society Press, Washington, DC, 1991

Cited By

View all
  • (2024)Survey of Hardware Acceleration of Genomic Analysis2024 IEEE 17th International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC)10.1109/MCSoC64144.2024.00093(540-547)Online publication date: 16-Dec-2024
  • (2024)Dedicated Bioinformatics Analysis HardwareReference Module in Life Sciences10.1016/B978-0-323-95502-7.00022-1Online publication date: 2024
  • (2024)Sequence-Order Frequency Matrix–Sampling and Machine Learning with Smith–Waterman (SOFM–SMSW) for Protein Remote Homology DetectionWireless Personal Communications10.1007/s11277-024-11617-y138:4(2637-2656)Online publication date: 10-Oct-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
HPRCTA '07: Proceedings of the 1st international workshop on High-performance reconfigurable computing technology and applications: held in conjunction with SC07
November 2007
54 pages
ISBN:9781595938947
DOI:10.1145/1328554
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 November 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. FPGA
  2. Smith-Waterman algorithm
  3. coprocessor
  4. reconfigurable supercomputing

Qualifiers

  • Research-article

Conference

SC '07
Sponsor:

Upcoming Conference

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)48
  • Downloads (Last 6 weeks)3
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Survey of Hardware Acceleration of Genomic Analysis2024 IEEE 17th International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC)10.1109/MCSoC64144.2024.00093(540-547)Online publication date: 16-Dec-2024
  • (2024)Dedicated Bioinformatics Analysis HardwareReference Module in Life Sciences10.1016/B978-0-323-95502-7.00022-1Online publication date: 2024
  • (2024)Sequence-Order Frequency Matrix–Sampling and Machine Learning with Smith–Waterman (SOFM–SMSW) for Protein Remote Homology DetectionWireless Personal Communications10.1007/s11277-024-11617-y138:4(2637-2656)Online publication date: 10-Oct-2024
  • (2023)A Multi-FPGA Implementation of FM-Index Based Genomic Pattern SearchIEICE Transactions on Information and Systems10.1587/transinf.2022EDP7230E106.D:11(1783-1795)Online publication date: 1-Nov-2023
  • (2023)Mutation Tree Reconstruction of Tumor Cells on FPGAs Using a Bit-Level Matrix RepresentationProceedings of the 13th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies10.1145/3597031.3597050(27-34)Online publication date: 14-Jun-2023
  • (2023)Profile-Driven Banded Smith-Waterman acceleration for Short Read Alignment2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247740(1-6)Online publication date: 9-Jul-2023
  • (2023)WFA-FPGA: An efficient accelerator of the wavefront algorithm for short and long read genomics alignmentFuture Generation Computer Systems10.1016/j.future.2023.07.008Online publication date: Jul-2023
  • (2022)Traceback Memory Reduction for Three-Sequence Alignment Algorithm with Affine Gap Models2022 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC)10.23919/APSIPAASC55919.2022.9980113(1014-1018)Online publication date: 7-Nov-2022
  • (2022)GANDAFL: Dataflow Acceleration for Short Read Alignment on NGS DataIEEE Transactions on Computers10.1109/TC.2022.314411571:11(3018-3031)Online publication date: 1-Nov-2022
  • (2022)SALoBa: Maximizing Data Locality and Workload Balance for Fast Sequence Alignment on GPUs2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS53621.2022.00076(728-738)Online publication date: May-2022
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media