Inlämning av Examensarbete / Submission of Thesis

Piotr Skrzypczak , pp. 62. COM/School of Computing, 2012.

The work

Författare / Author: Piotr Skrzypczak
Titel / Title: Parallel parsing of context-free grammars
Abstrakt Abstract:

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.

Ämnesord / Subject: Datavetenskap - Computer Science\Distributed Computing
Datavetenskap - Computer Science\Computersystems
Nyckelord / Keywords: parallel parsing, CYK algorithm, CUDA

Publication info

Dokument id / Document id: houn-8uplms
Program:/ Programme Datavetenskapligt program/Computer Science
Registreringsdatum / Date of registration: 05/27/2012
Uppsatstyp / Type of thesis: Masterarbete/Master's Thesis (120 credits)


Handledare / Supervisor: Bengt Aspvall
Examinator / Examiner: Lars Lundberg
Organisation / Organisation: Blekinge Institute of Technology
Institution / School: COM/School of Computing

+46 455 38 50 00
I samarbete med / In co-operation with: WUT - Wroclaw University of Technology

Files & Access

Bifogad uppsats fil(er) / Files attached: bth2012skrzypczak.pdf (850 kB, öppnas i nytt fönster)