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 N1fb064e08ac94ee19e6fa94f33740d49
    2 N5d1ff03087f0486795e36c0766964bb7
    3 N8d1dc01b851740baa8a733770566edb8
    4 Na59c9f955d3143e9948ab9a3ab5584f5
    5 Nf51de00a04f24d08b917c184a5552bea
    6 anzsrc-for:08
    7 anzsrc-for:0806
    8 schema:author N91dbca379ce64766873bcf7ff3ce87c7
    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 N3d447b8c790e4d30ba5ecc8a21909cf2
    49 Nbd0875393e7a4cba8a06616c9b24a059
    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 N4ba1d58b2b504fefa5ab77fa40fd1d73
    54 N6396b46de96841aa9325dc8b9a7a0566
    55 Nf3dc8612920b4b92901985c7cafe2596
    56 Nf82f3647b024448495f7bad323cef591
    57 Nf9130927fbd543b2a55ef5d0a31937e6
    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 N87d2ee9fbb9840d28cd93a706286a9fb
    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 N1fb064e08ac94ee19e6fa94f33740d49 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
    68 schema:name Sequence Alignment
    69 rdf:type schema:DefinedTerm
    70 N3d447b8c790e4d30ba5ecc8a21909cf2 schema:issueNumber 1
    71 rdf:type schema:PublicationIssue
    72 N4ba1d58b2b504fefa5ab77fa40fd1d73 schema:name readcube_id
    73 schema:value 9b8a4d7546cd41184e353c2514e48dd44bb9a61387f7f8356fac6ad0c8c8f889
    74 rdf:type schema:PropertyValue
    75 N5d1ff03087f0486795e36c0766964bb7 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
    76 schema:name Databases, Protein
    77 rdf:type schema:DefinedTerm
    78 N6396b46de96841aa9325dc8b9a7a0566 schema:name nlm_unique_id
    79 schema:value 100965194
    80 rdf:type schema:PropertyValue
    81 N87d2ee9fbb9840d28cd93a706286a9fb schema:name Springer Nature - SN SciGraph project
    82 rdf:type schema:Organization
    83 N8d1dc01b851740baa8a733770566edb8 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
    84 schema:name Algorithms
    85 rdf:type schema:DefinedTerm
    86 N91dbca379ce64766873bcf7ff3ce87c7 rdf:first sg:person.01356237607.16
    87 rdf:rest Naa6a5d32d5f14e52b739a13586efc88f
    88 Na59c9f955d3143e9948ab9a3ab5584f5 schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
    89 schema:name Sequence Analysis, Protein
    90 rdf:type schema:DefinedTerm
    91 Naa6a5d32d5f14e52b739a13586efc88f rdf:first sg:person.010056145157.83
    92 rdf:rest Ne8f5deb2508846b3aabd0fe8de52eae3
    93 Nbd0875393e7a4cba8a06616c9b24a059 schema:volumeNumber 14
    94 rdf:type schema:PublicationVolume
    95 Ne8f5deb2508846b3aabd0fe8de52eae3 rdf:first sg:person.01165760171.33
    96 rdf:rest rdf:nil
    97 Nf3dc8612920b4b92901985c7cafe2596 schema:name doi
    98 schema:value 10.1186/1471-2105-14-117
    99 rdf:type schema:PropertyValue
    100 Nf51de00a04f24d08b917c184a5552bea schema:inDefinedTermSet https://www.nlm.nih.gov/mesh/
    101 schema:name Software
    102 rdf:type schema:DefinedTerm
    103 Nf82f3647b024448495f7bad323cef591 schema:name pubmed_id
    104 schema:value 23557111
    105 rdf:type schema:PropertyValue
    106 Nf9130927fbd543b2a55ef5d0a31937e6 schema:name dimensions_id
    107 schema:value pub.1032649695
    108 rdf:type schema:PropertyValue
    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)


    ...