Ferres, LeoElejalde Sierra, Erick2021-07-062024-08-282021-07-062024-08-282014https://repositorio.udec.cl/handle/11594/6718Tesis para optar al grado de Magíster en Ciencias de la Computación.Previous attempts to parallelize string matching algorithms have focused on data decomposition; that is, splitting the text on the number of available cores. In this work, we demonstrate that it is possible to use task decomposition efficiently, using a multiprocessor model. We introduce the Task Decomposition String Matching algorithm, a new algorithm based on bit parallelism and finite automata theory. We also present a producer/consumer strategy which may be applied to the traditional algorithms as an alternative way to parallelize them. We run experiments that compare both our approaches against traditional algorithms (such as Boyer-Moore, KMP and Bitap) by varying the length of the pattern and the properties of alphabets, two critical variables that affect performance in string matching. The Domain Decomposition strategy proved to be very efficient for this problem. Although task decomposition is asymptotically optimal, it is practically affected by cache contingencies.engCreative Commoms CC BY NC ND 4.0 internacional (Atribución-NoComercial-SinDerivadas 4.0 Internacional)AlgoritmosProcesamiento de DatosAlgoritmos ComputacionalesAnálisisÁlgebraAnálisis MatemáticoAlgoritmosEstructuraTesis