E-Locus - Institutional Repository of the University of Crete - A Massively parallel regular expression and string matching engine for commodity hardware

Home A Massively parallel regular expression and string matching engine for commodity hardware

Results - Details

[Add to Basket]

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

Views

730

Digital Documents
	Download document View document Views : 135