CUDASW++ 3.0: accelerating Smith-Waterman protein database search by coupling CPU and GPU SIMD instructions View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2013-12

AUTHORS

Yongchao Liu, Adrianto Wirawan, Bertil Schmidt

ABSTRACT

BACKGROUND: The maximal sensitivity for local alignments makes the Smith-Waterman algorithm a popular choice for protein sequence database search based on pairwise alignment. However, the algorithm is compute-intensive due to a quadratic time complexity. Corresponding runtimes are further compounded by the rapid growth of sequence databases. RESULTS: We present CUDASW++ 3.0, a fast Smith-Waterman protein database search algorithm, which couples CPU and GPU SIMD instructions and carries out concurrent CPU and GPU computations. For the CPU computation, this algorithm employs SSE-based vector execution units as accelerators. For the GPU computation, we have investigated for the first time a GPU SIMD parallelization, which employs CUDA PTX SIMD video instructions to gain more data parallelism beyond the SIMT execution model. Moreover, sequence alignment workloads are automatically distributed over CPUs and GPUs based on their respective compute capabilities. Evaluation on the Swiss-Prot database shows that CUDASW++ 3.0 gains a performance improvement over CUDASW++ 2.0 up to 2.9 and 3.2, with a maximum performance of 119.0 and 185.6 GCUPS, on a single-GPU GeForce GTX 680 and a dual-GPU GeForce GTX 690 graphics card, respectively. In addition, our algorithm has demonstrated significant speedups over other top-performing tools: SWIPE and BLAST+. CONCLUSIONS: CUDASW++ 3.0 is written in CUDA C++ and PTX assembly languages, targeting GPUs based on the Kepler architecture. This algorithm obtains significant speedups over its predecessor: CUDASW++ 2.0, by benefiting from the use of CPU and GPU SIMD instructions as well as the concurrent execution on CPUs and GPUs. The source code and the simulated data are available at http://cudasw.sourceforge.net. More... »

PAGES

117

References to SciGraph publications

  • 2007-12. 160-fold acceleration of the Smith-Waterman algorithm using a field programmable gate array (FPGA) in BMC BIOINFORMATICS
  • 2008-12. SWPS3 – fast multi-threaded vectorized Smith-Waterman for IBM Cell/B.E. and ×86/SSE2 in BMC RESEARCH NOTES
  • 2011-12. Protein alignment algorithms with an efficient backtracking routine on multiple GPUs in BMC BIOINFORMATICS
  • 2012-08. Unified framework for recognition, localization and mapping using wearable cameras in COGNITIVE PROCESSING
  • 2012-12. Coupling SIMD and SIMT architectures to boost performance of a phylogeny-aware alignment kernel in BMC BIOINFORMATICS
  • 2009-12. CUDASW++: optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units in BMC RESEARCH NOTES
  • 2008-12. CBESW: Sequence Alignment on the Playstation 3 in BMC BIOINFORMATICS
  • 2010-12. CUDASW++2.0: enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD abstractions in BMC RESEARCH NOTES
  • 2008-03. CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment in BMC BIOINFORMATICS
  • 2009-12. BLAST+: architecture and applications in BMC BIOINFORMATICS
  • 2010-12. Hybrid cloud and cluster computing paradigms for life science applications in BMC BIOINFORMATICS
  • 2007-12. Model based analysis of real-time PCR data from DNA binding dye protocols in BMC BIOINFORMATICS
  • 2011-12. Faster Smith-Waterman database searches with inter-sequence SIMD parallelisation in BMC BIOINFORMATICS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1186/1471-2105-14-117

    DOI

    http://dx.doi.org/10.1186/1471-2105-14-117

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1032649695

    PUBMED

    https://www.ncbi.nlm.nih.gov/pubmed/23557111


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information Systems", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
            "name": "Algorithms", 
            "type": "DefinedTerm"
          }, 
          {
            "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
            "name": "Databases, Protein", 
            "type": "DefinedTerm"
          }, 
          {
            "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
            "name": "Sequence Alignment", 
            "type": "DefinedTerm"
          }, 
          {
            "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
            "name": "Sequence Analysis, Protein", 
            "type": "DefinedTerm"
          }, 
          {
            "inDefinedTermSet": "https://www.nlm.nih.gov/mesh/", 
            "name": "Software", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Johannes Gutenberg University of Mainz", 
              "id": "https://www.grid.ac/institutes/grid.5802.f", 
              "name": [
                "Institut f\u00fcr Informatik, Johannes Gutenberg Universit\u00e4t Mainz, Mainz, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Liu", 
            "givenName": "Yongchao", 
            "id": "sg:person.01356237607.16", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01356237607.16"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Johannes Gutenberg University of Mainz", 
              "id": "https://www.grid.ac/institutes/grid.5802.f", 
              "name": [
                "Institut f\u00fcr Informatik, Johannes Gutenberg Universit\u00e4t Mainz, Mainz, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Wirawan", 
            "givenName": "Adrianto", 
            "id": "sg:person.010056145157.83", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010056145157.83"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Johannes Gutenberg University of Mainz", 
              "id": "https://www.grid.ac/institutes/grid.5802.f", 
              "name": [
                "Institut f\u00fcr Informatik, Johannes Gutenberg Universit\u00e4t Mainz, Mainz, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Schmidt", 
            "givenName": "Bertil", 
            "id": "sg:person.01165760171.33", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01165760171.33"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1093/bioinformatics/bts061", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004966652"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/bioinformatics/bts276", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007749674"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/bioinformatics/13.2.145", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008319186"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1186/1471-2105-9-377", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009826728", 
              "https://doi.org/10.1186/1471-2105-9-377"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1186/1471-2105-9-377", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009826728", 
              "https://doi.org/10.1186/1471-2105-9-377"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1186/1471-2105-8-85", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010432928", 
              "https://doi.org/10.1186/1471-2105-8-85"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1186/1471-2105-8-85", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010432928", 
              "https://doi.org/10.1186/1471-2105-8-85"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1186/1471-2105-12-221", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010513713", 
              "https://doi.org/10.1186/1471-2105-12-221"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-2836(05)80360-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013618994"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/bioinformatics/btl582", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014155557"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1186/1471-2105-12-181", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015805408", 
              "https://doi.org/10.1186/1471-2105-12-181"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1186/1756-0500-2-73", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016918082", 
              "https://doi.org/10.1186/1756-0500-2-73"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1186/1756-0500-1-107", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023265691", 
              "https://doi.org/10.1186/1756-0500-1-107"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1186/1471-2105-8-185", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024279614", 
              "https://doi.org/10.1186/1471-2105-8-185"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1186/1471-2105-8-185", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024279614", 
              "https://doi.org/10.1186/1471-2105-8-185"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-2836(81)90087-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024589839"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-2836(82)90398-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025042064"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/bioinformatics/16.8.699", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025315480"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10339-012-0496-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034768061", 
              "https://doi.org/10.1007/s10339-012-0496-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/bioinformatics/bti508", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034858023"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1073/pnas.85.8.2444", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035928070"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jcp.2010.02.009", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037434697"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1186/1471-2105-13-196", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038214039", 
              "https://doi.org/10.1186/1471-2105-13-196"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/bioinformatics/btp324", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038266369"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1186/1756-0500-3-93", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041106303", 
              "https://doi.org/10.1186/1756-0500-3-93"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/nar/22.22.4673", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042438223"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1186/1471-2105-11-s12-s3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043261293", 
              "https://doi.org/10.1186/1471-2105-11-s12-s3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/nar/25.17.3389", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047265454"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1186/1471-2105-10-421", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050579230", 
              "https://doi.org/10.1186/1471-2105-10-421"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1186/1471-2105-9-s2-s10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053056668", 
              "https://doi.org/10.1186/1471-2105-9-s2-s10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/mm.2008.31", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061408600"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tcsii.2005.853340", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061569178"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tpds.2007.1059", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061753097"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tpds.2007.1069", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061753107"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/ipdps.2011.182", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093377377"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/ipdps.2009.5160931", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094780600"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2013-12", 
        "datePublishedReg": "2013-12-01", 
        "description": "BACKGROUND: The maximal sensitivity for local alignments makes the Smith-Waterman algorithm a popular choice for protein sequence database search based on pairwise alignment. However, the algorithm is compute-intensive due to a quadratic time complexity. Corresponding runtimes are further compounded by the rapid growth of sequence databases.\nRESULTS: We present CUDASW++ 3.0, a fast Smith-Waterman protein database search algorithm, which couples CPU and GPU SIMD instructions and carries out concurrent CPU and GPU computations. For the CPU computation, this algorithm employs SSE-based vector execution units as accelerators. For the GPU computation, we have investigated for the first time a GPU SIMD parallelization, which employs CUDA PTX SIMD video instructions to gain more data parallelism beyond the SIMT execution model. Moreover, sequence alignment workloads are automatically distributed over CPUs and GPUs based on their respective compute capabilities. Evaluation on the Swiss-Prot database shows that CUDASW++ 3.0 gains a performance improvement over CUDASW++ 2.0 up to 2.9 and 3.2, with a maximum performance of 119.0 and 185.6 GCUPS, on a single-GPU GeForce GTX 680 and a dual-GPU GeForce GTX 690 graphics card, respectively. In addition, our algorithm has demonstrated significant speedups over other top-performing tools: SWIPE and BLAST+.\nCONCLUSIONS: CUDASW++ 3.0 is written in CUDA C++ and PTX assembly languages, targeting GPUs based on the Kepler architecture. This algorithm obtains significant speedups over its predecessor: CUDASW++ 2.0, by benefiting from the use of CPU and GPU SIMD instructions as well as the concurrent execution on CPUs and GPUs. The source code and the simulated data are available at http://cudasw.sourceforge.net.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1186/1471-2105-14-117", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1023786", 
            "issn": [
              "1471-2105"
            ], 
            "name": "BMC Bioinformatics", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "14"
          }
        ], 
        "name": "CUDASW++ 3.0: accelerating Smith-Waterman protein database search by coupling CPU and GPU SIMD instructions", 
        "pagination": "117", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "9b8a4d7546cd41184e353c2514e48dd44bb9a61387f7f8356fac6ad0c8c8f889"
            ]
          }, 
          {
            "name": "pubmed_id", 
            "type": "PropertyValue", 
            "value": [
              "23557111"
            ]
          }, 
          {
            "name": "nlm_unique_id", 
            "type": "PropertyValue", 
            "value": [
              "100965194"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1186/1471-2105-14-117"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1032649695"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1186/1471-2105-14-117", 
          "https://app.dimensions.ai/details/publication/pub.1032649695"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T13:14", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8659_00000506.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1186/1471-2105-14-117"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1186/1471-2105-14-117'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1186/1471-2105-14-117'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1186/1471-2105-14-117'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1186/1471-2105-14-117'


     

    This table displays all metadata directly associated to this object as RDF triples.

    214 TRIPLES      21 PREDICATES      67 URIs      26 LITERALS      14 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1186/1471-2105-14-117 schema:about N053082369e78461ebfa60ce4a63de77f
    2 N6af2fe6b3c3f42f88bb79da1ab156324
    3 N82c029ff61694341975697c328513cf4
    4 Ne1e47db760b24558ad6318eda771f4e5
    5 Ne7d9cf5867c14840ad1451b947c50737
    6 anzsrc-for:08
    7 anzsrc-for:0806
    8 schema:author N3edec932fba342e9ad332480ae97009a
    9 schema:citation sg:pub.10.1007/s10339-012-0496-2
    10 sg:pub.10.1186/1471-2105-10-421
    11 sg:pub.10.1186/1471-2105-11-s12-s3
    12 sg:pub.10.1186/1471-2105-12-181
    13 sg:pub.10.1186/1471-2105-12-221
    14 sg:pub.10.1186/1471-2105-13-196
    15 sg:pub.10.1186/1471-2105-8-185
    16 sg:pub.10.1186/1471-2105-8-85
    17 sg:pub.10.1186/1471-2105-9-377
    18 sg:pub.10.1186/1471-2105-9-s2-s10
    19 sg:pub.10.1186/1756-0500-1-107
    20 sg:pub.10.1186/1756-0500-2-73
    21 sg:pub.10.1186/1756-0500-3-93
    22 https://doi.org/10.1016/0022-2836(81)90087-5
    23 https://doi.org/10.1016/0022-2836(82)90398-9
    24 https://doi.org/10.1016/j.jcp.2010.02.009
    25 https://doi.org/10.1016/s0022-2836(05)80360-2
    26 https://doi.org/10.1073/pnas.85.8.2444
    27 https://doi.org/10.1093/bioinformatics/13.2.145
    28 https://doi.org/10.1093/bioinformatics/16.8.699
    29 https://doi.org/10.1093/bioinformatics/bti508
    30 https://doi.org/10.1093/bioinformatics/btl582
    31 https://doi.org/10.1093/bioinformatics/btp324
    32 https://doi.org/10.1093/bioinformatics/bts061
    33 https://doi.org/10.1093/bioinformatics/bts276
    34 https://doi.org/10.1093/nar/22.22.4673
    35 https://doi.org/10.1093/nar/25.17.3389
    36 https://doi.org/10.1109/ipdps.2009.5160931
    37 https://doi.org/10.1109/ipdps.2011.182
    38 https://doi.org/10.1109/mm.2008.31
    39 https://doi.org/10.1109/tcsii.2005.853340
    40 https://doi.org/10.1109/tpds.2007.1059
    41 https://doi.org/10.1109/tpds.2007.1069
    42 schema:datePublished 2013-12
    43 schema:datePublishedReg 2013-12-01
    44 schema:description BACKGROUND: The maximal sensitivity for local alignments makes the Smith-Waterman algorithm a popular choice for protein sequence database search based on pairwise alignment. However, the algorithm is compute-intensive due to a quadratic time complexity. Corresponding runtimes are further compounded by the rapid growth of sequence databases. RESULTS: We present CUDASW++ 3.0, a fast Smith-Waterman protein database search algorithm, which couples CPU and GPU SIMD instructions and carries out concurrent CPU and GPU computations. For the CPU computation, this algorithm employs SSE-based vector execution units as accelerators. For the GPU computation, we have investigated for the first time a GPU SIMD parallelization, which employs CUDA PTX SIMD video instructions to gain more data parallelism beyond the SIMT execution model. Moreover, sequence alignment workloads are automatically distributed over CPUs and GPUs based on their respective compute capabilities. Evaluation on the Swiss-Prot database shows that CUDASW++ 3.0 gains a performance improvement over CUDASW++ 2.0 up to 2.9 and 3.2, with a maximum performance of 119.0 and 185.6 GCUPS, on a single-GPU GeForce GTX 680 and a dual-GPU GeForce GTX 690 graphics card, respectively. In addition, our algorithm has demonstrated significant speedups over other top-performing tools: SWIPE and BLAST+. CONCLUSIONS: CUDASW++ 3.0 is written in CUDA C++ and PTX assembly languages, targeting GPUs based on the Kepler architecture. This algorithm obtains significant speedups over its predecessor: CUDASW++ 2.0, by benefiting from the use of CPU and GPU SIMD instructions as well as the concurrent execution on CPUs and GPUs. The source code and the simulated data are available at http://cudasw.sourceforge.net.
    45 schema:genre research_article
    46 schema:inLanguage en
    47 schema:isAccessibleForFree true
    48 schema:isPartOf Naeec535c8e8f4f649b2752e0d6ab8ec9
    49 Ne94b0b6bde154f0e963257abe40cec4e
    50 sg:journal.1023786
    51 schema:name CUDASW++ 3.0: accelerating Smith-Waterman protein database search by coupling CPU and GPU SIMD instructions
    52 schema:pagination 117
    53 schema:productId N13e956507b4541d0ab8b4202d769e613
    54 N1f8c1b21adaa4502bd4a7a480bc83b38
    55 Nce243564d10c4dcd9f061371c4278e8b
    56 Ndc89dcf607f74129a19fd16969e40426
    57 Neb28e11c4d9d4e3ca0d0bab70a186c2d
    58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032649695
    59 https://doi.org/10.1186/1471-2105-14-117
    60 schema:sdDatePublished 2019-04-10T13:14
    61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    62 schema:sdPublisher Nfbf0b4cf543a4f8a818ac063aace8266
    63 schema:url http://link.springer.com/10.1186/1471-2105-14-117
    64 sgo:license sg:explorer/license/
    65 sgo:sdDataset articles
    66 rdf:type schema:ScholarlyArticle
    67 N053082369e78461ebfa60ce4a63de77f schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
    68 schema:name Databases, Protein
    69 rdf:type schema:DefinedTerm
    70 N13a5950aaa624e58a0389297f5b358b9 rdf:first sg:person.01165760171.33
    71 rdf:rest rdf:nil
    72 N13e956507b4541d0ab8b4202d769e613 schema:name nlm_unique_id
    73 schema:value 100965194
    74 rdf:type schema:PropertyValue
    75 N1f8c1b21adaa4502bd4a7a480bc83b38 schema:name doi
    76 schema:value 10.1186/1471-2105-14-117
    77 rdf:type schema:PropertyValue
    78 N3edec932fba342e9ad332480ae97009a rdf:first sg:person.01356237607.16
    79 rdf:rest Ndb43b99898964895a4d499d41427939c
    80 N6af2fe6b3c3f42f88bb79da1ab156324 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
    81 schema:name Sequence Analysis, Protein
    82 rdf:type schema:DefinedTerm
    83 N82c029ff61694341975697c328513cf4 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
    84 schema:name Software
    85 rdf:type schema:DefinedTerm
    86 Naeec535c8e8f4f649b2752e0d6ab8ec9 schema:issueNumber 1
    87 rdf:type schema:PublicationIssue
    88 Nce243564d10c4dcd9f061371c4278e8b schema:name readcube_id
    89 schema:value 9b8a4d7546cd41184e353c2514e48dd44bb9a61387f7f8356fac6ad0c8c8f889
    90 rdf:type schema:PropertyValue
    91 Ndb43b99898964895a4d499d41427939c rdf:first sg:person.010056145157.83
    92 rdf:rest N13a5950aaa624e58a0389297f5b358b9
    93 Ndc89dcf607f74129a19fd16969e40426 schema:name pubmed_id
    94 schema:value 23557111
    95 rdf:type schema:PropertyValue
    96 Ne1e47db760b24558ad6318eda771f4e5 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
    97 schema:name Sequence Alignment
    98 rdf:type schema:DefinedTerm
    99 Ne7d9cf5867c14840ad1451b947c50737 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
    100 schema:name Algorithms
    101 rdf:type schema:DefinedTerm
    102 Ne94b0b6bde154f0e963257abe40cec4e schema:volumeNumber 14
    103 rdf:type schema:PublicationVolume
    104 Neb28e11c4d9d4e3ca0d0bab70a186c2d schema:name dimensions_id
    105 schema:value pub.1032649695
    106 rdf:type schema:PropertyValue
    107 Nfbf0b4cf543a4f8a818ac063aace8266 schema:name Springer Nature - SN SciGraph project
    108 rdf:type schema:Organization
    109 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    110 schema:name Information and Computing Sciences
    111 rdf:type schema:DefinedTerm
    112 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    113 schema:name Information Systems
    114 rdf:type schema:DefinedTerm
    115 sg:journal.1023786 schema:issn 1471-2105
    116 schema:name BMC Bioinformatics
    117 rdf:type schema:Periodical
    118 sg:person.010056145157.83 schema:affiliation https://www.grid.ac/institutes/grid.5802.f
    119 schema:familyName Wirawan
    120 schema:givenName Adrianto
    121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010056145157.83
    122 rdf:type schema:Person
    123 sg:person.01165760171.33 schema:affiliation https://www.grid.ac/institutes/grid.5802.f
    124 schema:familyName Schmidt
    125 schema:givenName Bertil
    126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01165760171.33
    127 rdf:type schema:Person
    128 sg:person.01356237607.16 schema:affiliation https://www.grid.ac/institutes/grid.5802.f
    129 schema:familyName Liu
    130 schema:givenName Yongchao
    131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01356237607.16
    132 rdf:type schema:Person
    133 sg:pub.10.1007/s10339-012-0496-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034768061
    134 https://doi.org/10.1007/s10339-012-0496-2
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1186/1471-2105-10-421 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050579230
    137 https://doi.org/10.1186/1471-2105-10-421
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1186/1471-2105-11-s12-s3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043261293
    140 https://doi.org/10.1186/1471-2105-11-s12-s3
    141 rdf:type schema:CreativeWork
    142 sg:pub.10.1186/1471-2105-12-181 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015805408
    143 https://doi.org/10.1186/1471-2105-12-181
    144 rdf:type schema:CreativeWork
    145 sg:pub.10.1186/1471-2105-12-221 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010513713
    146 https://doi.org/10.1186/1471-2105-12-221
    147 rdf:type schema:CreativeWork
    148 sg:pub.10.1186/1471-2105-13-196 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038214039
    149 https://doi.org/10.1186/1471-2105-13-196
    150 rdf:type schema:CreativeWork
    151 sg:pub.10.1186/1471-2105-8-185 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024279614
    152 https://doi.org/10.1186/1471-2105-8-185
    153 rdf:type schema:CreativeWork
    154 sg:pub.10.1186/1471-2105-8-85 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010432928
    155 https://doi.org/10.1186/1471-2105-8-85
    156 rdf:type schema:CreativeWork
    157 sg:pub.10.1186/1471-2105-9-377 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009826728
    158 https://doi.org/10.1186/1471-2105-9-377
    159 rdf:type schema:CreativeWork
    160 sg:pub.10.1186/1471-2105-9-s2-s10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053056668
    161 https://doi.org/10.1186/1471-2105-9-s2-s10
    162 rdf:type schema:CreativeWork
    163 sg:pub.10.1186/1756-0500-1-107 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023265691
    164 https://doi.org/10.1186/1756-0500-1-107
    165 rdf:type schema:CreativeWork
    166 sg:pub.10.1186/1756-0500-2-73 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016918082
    167 https://doi.org/10.1186/1756-0500-2-73
    168 rdf:type schema:CreativeWork
    169 sg:pub.10.1186/1756-0500-3-93 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041106303
    170 https://doi.org/10.1186/1756-0500-3-93
    171 rdf:type schema:CreativeWork
    172 https://doi.org/10.1016/0022-2836(81)90087-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024589839
    173 rdf:type schema:CreativeWork
    174 https://doi.org/10.1016/0022-2836(82)90398-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025042064
    175 rdf:type schema:CreativeWork
    176 https://doi.org/10.1016/j.jcp.2010.02.009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037434697
    177 rdf:type schema:CreativeWork
    178 https://doi.org/10.1016/s0022-2836(05)80360-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013618994
    179 rdf:type schema:CreativeWork
    180 https://doi.org/10.1073/pnas.85.8.2444 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035928070
    181 rdf:type schema:CreativeWork
    182 https://doi.org/10.1093/bioinformatics/13.2.145 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008319186
    183 rdf:type schema:CreativeWork
    184 https://doi.org/10.1093/bioinformatics/16.8.699 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025315480
    185 rdf:type schema:CreativeWork
    186 https://doi.org/10.1093/bioinformatics/bti508 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034858023
    187 rdf:type schema:CreativeWork
    188 https://doi.org/10.1093/bioinformatics/btl582 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014155557
    189 rdf:type schema:CreativeWork
    190 https://doi.org/10.1093/bioinformatics/btp324 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038266369
    191 rdf:type schema:CreativeWork
    192 https://doi.org/10.1093/bioinformatics/bts061 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004966652
    193 rdf:type schema:CreativeWork
    194 https://doi.org/10.1093/bioinformatics/bts276 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007749674
    195 rdf:type schema:CreativeWork
    196 https://doi.org/10.1093/nar/22.22.4673 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042438223
    197 rdf:type schema:CreativeWork
    198 https://doi.org/10.1093/nar/25.17.3389 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047265454
    199 rdf:type schema:CreativeWork
    200 https://doi.org/10.1109/ipdps.2009.5160931 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094780600
    201 rdf:type schema:CreativeWork
    202 https://doi.org/10.1109/ipdps.2011.182 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093377377
    203 rdf:type schema:CreativeWork
    204 https://doi.org/10.1109/mm.2008.31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061408600
    205 rdf:type schema:CreativeWork
    206 https://doi.org/10.1109/tcsii.2005.853340 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061569178
    207 rdf:type schema:CreativeWork
    208 https://doi.org/10.1109/tpds.2007.1059 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061753097
    209 rdf:type schema:CreativeWork
    210 https://doi.org/10.1109/tpds.2007.1069 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061753107
    211 rdf:type schema:CreativeWork
    212 https://www.grid.ac/institutes/grid.5802.f schema:alternateName Johannes Gutenberg University of Mainz
    213 schema:name Institut für Informatik, Johannes Gutenberg Universität Mainz, Mainz, Germany
    214 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...