Please use this identifier to cite or link to this item: http://localhost:8081/xmlui/handle/123456789/11863
Title: PERFORMANCE IMPROVEMENT OF PARALLEL PATTERN MATCHING ALGORITHM USING CEO. -BROADBAND ENGINE
Authors: Chowdhury, Rajarshi
Keywords: ELECTRONICS AND COMPUTER ENGINEERING;PARALLEL PATTERN MATCHING ALGORITHM;CEO;BROADBAND ENGINE
Issue Date: 2008
Abstract: A pattern matching algorithm is used to find the presence of the pattern in a given block of data. Pattern matching is used to test whether things have a desired structure, to find relevant structure, to retrieve the aligning parts, and to substitute the matching part with something else. Sequence (or specifically text string) patterns are often described using regular expressions (i.e. backtracking) and matched using respective algorithms. Sequences can also be seen as trees branching for each element into the respective element and the rest of the sequence, or as trees that immediately branch into all elements. Pattern matching is useful in the field of text editing, highly computation intensive works like bioinformatics (pattern matching in biological sequence databases or amino acid sequence databases), networking (high-speed intrusion detection system), syntax analysis, operating systems, internet related searches to name a few. Sequential pattern matching algorithms have almost reached their limits in terms of performance improvement. They are already linear in time complexity and the effective decrement in number of character comparisons is too less. In our work we first analyze most of the existing sequential and parallel pattern matching algorithms in terms of complexity, character comparisons and time of execution. Based on our analysis we try to parallelize the fastest sequential pattern matching algorithm — TVSBS to study the performance improvement. We use IBM Cell-Broadband Engine to implement our algorithm.
URI: http://hdl.handle.net/123456789/11863
Other Identifiers: M.Tech
Research Supervisor/ Guide: Mittal, Ankush
Niyogi, Rajdeep
metadata.dc.type: M.Tech Dessertation
Appears in Collections:MASTERS' DISSERTATIONS (E & C)

Files in This Item:
File Description SizeFormat 
ECDG13931.pdf3.21 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.