Change search
ReferencesLink to record
Permanent link

Direct link
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. , 62 p.
Keyword [en]
parallel parsing, CYK algorithm, CUDA
National Category
Computer Science
URN: urn:nbn:se:bth-2958Local ID: diva2:830253
Available from: 2015-04-22 Created: 2012-05-27 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

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

By organisation
School of Computing
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 55 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

Total: 27 hits
ReferencesLink to record
Permanent link

Direct link