Parallel Text Search

This project presents several text search algorithms for processing a single large text with multiple query patterns and how they can be parallelized across different hardware architectures. See doc/main.pdf for the paper.

Build Instructions

This requires CMake for building, an MPI implementation (e.g. Open MPI) and, for OpenCL, an ICD loader (e.g. ocl-icd) as well as a runtime (e.g. AMD CLR for AMD).

Get started by cloning the repository and all submodules:

git clone --recursive https://github.com/patri9ck/text-search.git
cd text-search

Then, build it using CMake:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build

This will create two executables in build/, text-search and text-search-test.

Using the Command-Line Tool

The command-line tool text-search provides the best implementations using OpenMP, MPI, OpenCL (safe or unsafe), or simply a single thread (sequential).

Example call:

build/text-search -i openmp -d data -f README.md -q text -q search

This uses the best OpenMP implementation, loads all files in the directory data/ and the file README.md to look through and searches for the words text and search. Use the --help option for a list of all options.

For MPI, simply use the MPI implementation and wrap the command using mpiexec:

mpiexec -n 8 build/text-search -i mpi -d data -f README.md -q text -q search

Running Tests

Example call:

build/text-search-test -i candidate_v3 -d data -f common-words.txt -c

This will load all books from the directory data/, all queries in the file common-words.txt, run the candidate_v3 implementation and test it against the reference implementation. Run --help for an overview of all options.

Again, to use MPI, choose an MPI implementation and wrap the command using mpiexec.

Creating Plots

To create plots and CSV files, benchmark.py exists which calls the test binary. It stores its results in doc/.

Example call:

python3 benchmark.py benchmark -i openmp -e build/text-search-test -m queries -q common-words.txt -b data

Use the --help options for an overview of all options.

Existing plots and CSV files can already be found in the doc/ directory.

To show speed-up factors, based on previous created CSV files, run:

python3 benchmark.py compare -q common-words.txt -q long-words.txt

Downloading Ebooks from Project Gutenberg

To download the top 100 ebooks from Project Gutenberg into data/, run:

python3 download-gutenberg-ebooks.py

The repository already includes the top 100 from December 2025.

Implementations Overview

• std: Uses the standard library, e.g. std::string::find(), and is used to check for correctness.

• candidate_v1: Loops through each query and then through each character of the text. If a character matches the first character of the query, its index (a candidate) is added to a vector. After all candidates for all queries are collected, each are checked character-by-character.

• candidate_v2: Same as candidate_v1 but uses a pre-allocated int array per query the size of the text.

• candidate_v3: To save storage and improve cache utilization, a bit mask is used instead of an int array.

• candidate_v4: This creates a huge bit mask for all queries together instead of creating one per query.

• hash_v1: Rabin-Karp rolling-hash implementation.

• hash_v2: Groups queries by length instead and uses an unordered map as a hash table.

• std_openmp Parallelization of std using OpenMP.

• candidate_openmp_v1: Parallelization of candidate_v3 using OpenMP.

• candidate_openmp_v2: Parallelization of candidate_v4 using OpenMP.

• hash_openmp Parallelization of hash_v2 using OpenMP by distributing independent query length groups across CPU threads.

• candidate_mpi Parallelization of candidate_v3 using MPI.

• candidate_opencl_v1 Parallelization of candidate_v4 using OpenCL which validates directly instead of selecting candidates first.

• candidate_opencl_v2 Two-phase strategy: Counts candidates to allocate a result buffer. Then validates all text positions and queries, adding matches to the buffer.

• candidate_opencl_v3 Consists of only one phase. The needed result buffer size is estimated before on the CPU using a heuristic.

License

This project is licensed under MIT.