Post-graduate theses
Current Record: 4398 of 6695
|
Identifier |
000409411 |
Title |
A Massively parallel regular expression and string matching engine for commodity hardware |
Alternative Title |
Μια παράλληλη μηχανή αναζήτησης κανονικών εκφράσεων και αλφαριθμητικών για ευρέως διαθέσιμο υπολογιστικό υλικό |
Author
|
Ντεγιάννης, Δημήτριος Α.
|
Thesis advisor
|
Μαρκάτος, Ευάγγελος
|
Thesis advisor
|
Ιωαννίδης, Σωτήρης
Τσαμαρδινός, Ιωάννης
|
Abstract |
String pattern matching is one of the most studied fields in the research community,
mainly due to the fact that it can be used and applied in various and
diverse fields, such
as
computer science, computational biology, chemistry and others. Since 1970,
researchers
aim to develop algorithms for efficient string searching and until today, the
problem of
pattern matching remains a popular area for studying.
Recently, in order to cope with the ever advancing technology, parallel computing
platforms–such as CUDA and OpenCL–offer general purpose programming using
commodity
CPUs, hardware accelerators and GPUs.
In this work, we propose a framework for string pa
ttern matching on parallel hardware
architectures. Using CUDA and OpenCL,
our
framework offers uniform execution on any
processor available in a system. The framework provides an abstraction layer to the user
–
without penalizing the performance
–
and it is
provided as either a C
-
or Java
-
like API.
Except for simple string matching,
our engine
supports the use of multiple regular
expressions that comply with the POSIX ERE standard. Specifically, we achieve the
simultaneous matching of multiple simple strings
and binary patterns against multiple
data streams as input. Finally, the framework manages to simultaneously match large sets
of regular expressions against multiple data streams.
The performance evaluation shows that our massively parallel engine
can achieve up to
21 times performance increase when processing simple strings and
up to 15 times when
processing regular expressions, compared to the CPU versions of
both matching
algorithms. Specifically, the engine can sustain
simple
string matching throughput
up to
65 Gbits/s and regular expression matching throughput up to 50 Gbits/s.
|
Language |
English |
Subject |
Framework |
|
Αλφαριθμητικό |
|
Κανονικές εκφράσεις |
|
Παράλληλα |
Issue date |
2017-03-17 |
Collection
|
School/Department--School of Sciences and Engineering--Department of Computer Science--Post-graduate theses
|
|
Type of Work--Post-graduate theses
|
Permanent Link |
https://elocus.lib.uoc.gr//dlib/c/e/0/metadata-dlib-1495522483-502375-8476.tkl
|
Views |
783 |