Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Parallel parsing of context-free grammars
Blekinge Institute of Technology, School of Computing.
2012 (English)Independent thesis Advanced level (degree of Master (Two Years))Student thesis
Abstract [en]

During the last decade increasing interest in parallel programming can be observed. It is caused by a tendency of developing microprocessors as a multicore units, that can perform instructions simultaneously. Popular and widely used example of such platform is a graphic processing unit (GPU). Its ability to perform calculations simultaneously is being investigated as a way for improving performance of the complex algorithms. Therefore, GPU’s are now having the architectures that allows to use its computional power by programmers and software developers in the same way as CPU. One of these architectures is CUDA platform, developed by nVidia. Aim of this thesis is to implement the parallel CYK algorithm, which is one of the most popular parsing algorithms, for CUDA platform, that will gain a significant speed-up in comparison with the sequential CYK algorithm. The thesis presents review of existing parallelisations of CYK algorithm, descriptions of implemented algorithms (basic version and few modifications), and experimental stage, that includes testing these versions for various inputs in order to justify which version of algorithm is giving the best performance. There are three versions of algorithm presented, from which one was selected as the best (giving about 10 times better performance for the longest instances of inputs). Also, a limited version of algorithm, that gives best performance (even 100 times better in comparison with non-limited sequential version), but requires some conditions to be fulfilled by grammar, is presented. The motivation for the thesis is to use the developed algorithm in GCS.

Place, publisher, year, edition, pages
2012. , p. 62
Keywords [en]
parallel parsing, CYK algorithm, CUDA
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:bth-2958Local ID: oai:bth.se:arkivex43E2C3B240A398E3C1257A0B005744CBOAI: oai:DiVA.org:bth-2958DiVA, id: diva2:830253
Uppsok
Technology
Supervisors
Available from: 2015-04-22 Created: 2012-05-27 Last updated: 2018-01-11Bibliographically approved

Open Access in DiVA

fulltext(831 kB)1308 downloads
File information
File name FULLTEXT01.pdfFile size 831 kBChecksum SHA-512
2af6549454241b505014d9081427684045d862e36546ac2787fdb989510881fa3568706bce07e11dd3c58ad6a0751d100f4b79e4b08edc31baf737268638acc8
Type fulltextMimetype application/pdf

By organisation
School of Computing
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 1308 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 195 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf