Parallel SIMD CPU and GPU Implementations of Berlekamp–Massey Algorithm and Its Error Correction Application View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-02

AUTHORS

Hamidreza Mohebbi

ABSTRACT

The Berlekamp–Massey algorithm finds the shortest linear feedback shift register for a binary input sequence. A wide range of applications like cryptography and digital signal processing use this algorithm. This research proposes novel parallel mechanisms offered by heterogeneous CPU and GPU hardwares in order to achieve the best possible performance for BMA. The proposed bitwise implementation of the BMA algorithm is almost 35 times faster than state of the art implementations. This further improvement is achieved by using SIMD instructions which provides data level parallelism. This new approach can be 4.6 and 35 times faster than a bitwise CPU and state of the art implementations, respectively. In order to achieve the highest possible speedup over a multi-core structure, a multi-threading implementation is introduced in this research. By leveraging on OpenMP we were able to obtain a speedup of 10 times over 12 cores server. The GPU device with thousands of processing cores can bring great speedup over the best CPU implementation. Two other parallel mechanisms offered by GPU are concurrent kernel execution and streaming. They achieve 14.5 and 2.2 times of speedup compared to CPU serial and typical CUDA implementations, respectively. Also, the performance of the openMP code with SIMD instructions is compared with GPU stream implementation. The effectiveness of the proposed method is evaluated in a real world error correction application and it achieves 6.8 times of speedup. More... »

PAGES

137-160

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10766-018-0574-x

DOI

http://dx.doi.org/10.1007/s10766-018-0574-x

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Massachusetts Boston", 
          "id": "https://www.grid.ac/institutes/grid.266685.9", 
          "name": [
            "Computer Science Department, University of Massachusetts Boston, 02125, Boston, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mohebbi", 
        "givenName": "Hamidreza", 
        "id": "sg:person.07740503523.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07740503523.42"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/s10489-016-0826-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013013575", 
          "https://doi.org/10.1007/s10489-016-0826-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10489-016-0826-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013013575", 
          "https://doi.org/10.1007/s10489-016-0826-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2788396", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034208907"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1027422805851", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042850433", 
          "https://doi.org/10.1023/a:1027422805851"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s12095-016-0189-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048890194", 
          "https://doi.org/10.1007/s12095-016-0189-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s12095-016-0189-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048890194", 
          "https://doi.org/10.1007/s12095-016-0189-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1049/iet-com.2015.0500", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1056821854"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1049/ip-i-2.1989.0028", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1056855364"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/18.243455", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061098966"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/18.681314", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061100688"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tit.1964.1053699", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061646032"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tit.1965.1053825", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061646153"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tit.1969.1054260", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061646572"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0108018", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062837710"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.5539/cis.v4n6p18", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1072944146"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/9781316661277", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1096041547"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/bibm.2017.8217962", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1099746915"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-54973-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109702532", 
          "https://doi.org/10.1007/3-540-54973-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-54973-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109702532", 
          "https://doi.org/10.1007/3-540-54973-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-54973-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109702532", 
          "https://doi.org/10.1007/3-540-54973-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-54973-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109702532", 
          "https://doi.org/10.1007/3-540-54973-0"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-02", 
    "datePublishedReg": "2019-02-01", 
    "description": "The Berlekamp\u2013Massey algorithm finds the shortest linear feedback shift register for a binary input sequence. A wide range of applications like cryptography and digital signal processing use this algorithm. This research proposes novel parallel mechanisms offered by heterogeneous CPU and GPU hardwares in order to achieve the best possible performance for BMA. The proposed bitwise implementation of the BMA algorithm is almost 35 times faster than state of the art implementations. This further improvement is achieved by using SIMD instructions which provides data level parallelism. This new approach can be 4.6 and 35 times faster than a bitwise CPU and state of the art implementations, respectively. In order to achieve the highest possible speedup over a multi-core structure, a multi-threading implementation is introduced in this research. By leveraging on OpenMP we were able to obtain a speedup of 10 times over 12 cores server. The GPU device with thousands of processing cores can bring great speedup over the best CPU implementation. Two other parallel mechanisms offered by GPU are concurrent kernel execution and streaming. They achieve 14.5 and 2.2 times of speedup compared to CPU serial and typical CUDA implementations, respectively. Also, the performance of the openMP code with SIMD instructions is compared with GPU stream implementation. The effectiveness of the proposed method is evaluated in a real world error correction application and it achieves 6.8 times of speedup.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s10766-018-0574-x", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1126246", 
        "issn": [
          "0885-7458", 
          "1573-7640"
        ], 
        "name": "International Journal of Parallel Programming", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "47"
      }
    ], 
    "name": "Parallel SIMD CPU and GPU Implementations of Berlekamp\u2013Massey Algorithm and Its Error Correction Application", 
    "pagination": "137-160", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "c2a7f351df8295f51382f0ac2938c646aac91004fc19fdb046126b66b7a4690b"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10766-018-0574-x"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1103792648"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10766-018-0574-x", 
      "https://app.dimensions.ai/details/publication/pub.1103792648"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T10:19", 
    "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/0000000348_0000000348/records_54319_00000001.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs10766-018-0574-x"
  }
]
 

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.1007/s10766-018-0574-x'

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.1007/s10766-018-0574-x'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10766-018-0574-x'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10766-018-0574-x'


 

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

113 TRIPLES      21 PREDICATES      43 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10766-018-0574-x schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nd5872e1f660a43e18651b43ad0372449
4 schema:citation sg:pub.10.1007/3-540-54973-0
5 sg:pub.10.1007/s10489-016-0826-7
6 sg:pub.10.1007/s12095-016-0189-2
7 sg:pub.10.1023/a:1027422805851
8 https://doi.org/10.1017/9781316661277
9 https://doi.org/10.1049/iet-com.2015.0500
10 https://doi.org/10.1049/ip-i-2.1989.0028
11 https://doi.org/10.1109/18.243455
12 https://doi.org/10.1109/18.681314
13 https://doi.org/10.1109/bibm.2017.8217962
14 https://doi.org/10.1109/tit.1964.1053699
15 https://doi.org/10.1109/tit.1965.1053825
16 https://doi.org/10.1109/tit.1969.1054260
17 https://doi.org/10.1137/0108018
18 https://doi.org/10.1145/2788396
19 https://doi.org/10.5539/cis.v4n6p18
20 schema:datePublished 2019-02
21 schema:datePublishedReg 2019-02-01
22 schema:description The Berlekamp–Massey algorithm finds the shortest linear feedback shift register for a binary input sequence. A wide range of applications like cryptography and digital signal processing use this algorithm. This research proposes novel parallel mechanisms offered by heterogeneous CPU and GPU hardwares in order to achieve the best possible performance for BMA. The proposed bitwise implementation of the BMA algorithm is almost 35 times faster than state of the art implementations. This further improvement is achieved by using SIMD instructions which provides data level parallelism. This new approach can be 4.6 and 35 times faster than a bitwise CPU and state of the art implementations, respectively. In order to achieve the highest possible speedup over a multi-core structure, a multi-threading implementation is introduced in this research. By leveraging on OpenMP we were able to obtain a speedup of 10 times over 12 cores server. The GPU device with thousands of processing cores can bring great speedup over the best CPU implementation. Two other parallel mechanisms offered by GPU are concurrent kernel execution and streaming. They achieve 14.5 and 2.2 times of speedup compared to CPU serial and typical CUDA implementations, respectively. Also, the performance of the openMP code with SIMD instructions is compared with GPU stream implementation. The effectiveness of the proposed method is evaluated in a real world error correction application and it achieves 6.8 times of speedup.
23 schema:genre research_article
24 schema:inLanguage en
25 schema:isAccessibleForFree false
26 schema:isPartOf N7ef04dfe94b54a379aca3daf17684483
27 Nfc250b1cdf4343c6aa95e7ebcab772a4
28 sg:journal.1126246
29 schema:name Parallel SIMD CPU and GPU Implementations of Berlekamp–Massey Algorithm and Its Error Correction Application
30 schema:pagination 137-160
31 schema:productId N53f33e37c9774b338fcd094ea074cd90
32 Nd480bc0fec7f4e6481b592d5d4772ad0
33 Nfb66134283964300886162b99c0648d6
34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1103792648
35 https://doi.org/10.1007/s10766-018-0574-x
36 schema:sdDatePublished 2019-04-11T10:19
37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
38 schema:sdPublisher Nd8b9d0e7324641ffbb17636124ee4d10
39 schema:url https://link.springer.com/10.1007%2Fs10766-018-0574-x
40 sgo:license sg:explorer/license/
41 sgo:sdDataset articles
42 rdf:type schema:ScholarlyArticle
43 N53f33e37c9774b338fcd094ea074cd90 schema:name dimensions_id
44 schema:value pub.1103792648
45 rdf:type schema:PropertyValue
46 N7ef04dfe94b54a379aca3daf17684483 schema:issueNumber 1
47 rdf:type schema:PublicationIssue
48 Nd480bc0fec7f4e6481b592d5d4772ad0 schema:name doi
49 schema:value 10.1007/s10766-018-0574-x
50 rdf:type schema:PropertyValue
51 Nd5872e1f660a43e18651b43ad0372449 rdf:first sg:person.07740503523.42
52 rdf:rest rdf:nil
53 Nd8b9d0e7324641ffbb17636124ee4d10 schema:name Springer Nature - SN SciGraph project
54 rdf:type schema:Organization
55 Nfb66134283964300886162b99c0648d6 schema:name readcube_id
56 schema:value c2a7f351df8295f51382f0ac2938c646aac91004fc19fdb046126b66b7a4690b
57 rdf:type schema:PropertyValue
58 Nfc250b1cdf4343c6aa95e7ebcab772a4 schema:volumeNumber 47
59 rdf:type schema:PublicationVolume
60 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
61 schema:name Information and Computing Sciences
62 rdf:type schema:DefinedTerm
63 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
64 schema:name Computation Theory and Mathematics
65 rdf:type schema:DefinedTerm
66 sg:journal.1126246 schema:issn 0885-7458
67 1573-7640
68 schema:name International Journal of Parallel Programming
69 rdf:type schema:Periodical
70 sg:person.07740503523.42 schema:affiliation https://www.grid.ac/institutes/grid.266685.9
71 schema:familyName Mohebbi
72 schema:givenName Hamidreza
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07740503523.42
74 rdf:type schema:Person
75 sg:pub.10.1007/3-540-54973-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109702532
76 https://doi.org/10.1007/3-540-54973-0
77 rdf:type schema:CreativeWork
78 sg:pub.10.1007/s10489-016-0826-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013013575
79 https://doi.org/10.1007/s10489-016-0826-7
80 rdf:type schema:CreativeWork
81 sg:pub.10.1007/s12095-016-0189-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048890194
82 https://doi.org/10.1007/s12095-016-0189-2
83 rdf:type schema:CreativeWork
84 sg:pub.10.1023/a:1027422805851 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042850433
85 https://doi.org/10.1023/a:1027422805851
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1017/9781316661277 schema:sameAs https://app.dimensions.ai/details/publication/pub.1096041547
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1049/iet-com.2015.0500 schema:sameAs https://app.dimensions.ai/details/publication/pub.1056821854
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1049/ip-i-2.1989.0028 schema:sameAs https://app.dimensions.ai/details/publication/pub.1056855364
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1109/18.243455 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061098966
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1109/18.681314 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061100688
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1109/bibm.2017.8217962 schema:sameAs https://app.dimensions.ai/details/publication/pub.1099746915
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1109/tit.1964.1053699 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061646032
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1109/tit.1965.1053825 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061646153
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1109/tit.1969.1054260 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061646572
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1137/0108018 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062837710
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1145/2788396 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034208907
108 rdf:type schema:CreativeWork
109 https://doi.org/10.5539/cis.v4n6p18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072944146
110 rdf:type schema:CreativeWork
111 https://www.grid.ac/institutes/grid.266685.9 schema:alternateName University of Massachusetts Boston
112 schema:name Computer Science Department, University of Massachusetts Boston, 02125, Boston, MA, USA
113 rdf:type schema:Organization
 




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


...