Parallel Optimization of the SSABS Exact String-Matching Algorithm for Shared-Memory Multicore Systems Using POSIX Threads

String matching algorithms are algorithms used to determine the most suitable arrangement by contrasting and finding the correlation between a set of patterns and a random string [1-3]. During the comparison phase, the pattern length must equal the length of the window text. Furthermore, the pattern and text window string patterns rely on the ascertainment of their fit [4]. String matching remains a major problem faced by multitudinous computer science applications like intrusion detection systems (IDS) search analysis [5], natural language processing, information retrieval [6, 7], artificial intelligence (AI), signal and image processing [8, 9], pattern recognition [10], web search engines [11], and operating systems [12]. String matching is also used in the analysis of DNA patterns [13, 14] and protein sequences [15].

The world is witnessing swift database development, which emphasizes the significance of performance enhancement of exact string-matching algorithms. The brute force algorithm is perceived as the simplest algorithm technique in comparison with alternative string-matching algorithms. This is due to its ability to scan a text pattern with a text substring via left-to-right orientation. In the presence of a match or a mismatch, precise shifts take place one position to the right; hence, the brute force algorithm operates in O(mn) time. Furthermore, the Boyer-Moore algorithm is a widely used algorithm due to its high efficiency; it initiates the comparison from right to left. In the presence of a match or mismatch between the pattern and the text window, the good suffix and the bad character functions greatly impact the shifting [16].

The analysis of the Boyer-Moore algorithm and the Aho-Corasick algorithm has resulted in the Commentz-Walter algorithm. Pre-processed phased patterns utilized for text-matching are the fundamentals for a state machine, with the application of the Boyer-Moore extraction in the searching stage. Notably, the matching window length must be equal to the minimum pattern length. For the pattern characters, scanning is conducted from right to left. In circumstances where there are unpredictable irregularities, a pre-calculated shift table is used to shift the window position to the right. The algorithm's time complexity is in the order of O(π + m) for the pre-processing phase, and O(n*m) for the searching phase [17].

The Aho-Corasick algorithm uses automata, unlike the Knuth-Morris-Pratt algorithm; the state machine pattern is founded on a tree formation. At the beginning, the tree has an empty root; the states are formed when pattern matching occurs. The state machine is traversed during the search stage in anticipation of a perfect matching state probability. The time complexity is in the order of O(nk + m) for the preprocessing phase, and O(n + m + z) for the searching phase [18].

The Fast-On-line Hybrid Matching Algorithm (FOHM) is dual-phased; the preprocessing phase involves the creation of the Quick Search Bad Character (qsBc) table, while the search phase comprises a three-step division pattern, followed by the analysis of the three steps through the pattern and text window comparison. The text window is then compared with the pattern’s first three characters, followed by the comparison of the last three characters. If a match is found, the algorithm proceeds with the comparison of the remaining characters found inside the pattern and text window. The technique shifts the window to the right by an amount derived from the qsBc table in the event of a nil match at any phase [19].

The exact string-matching algorithms are affected by the number of attempts, the number of character comparisons, and the time consumed. The downsides of one or more of these factors are influenced by the efficacy of the algorithms. The decrease in the quantity of attempts and the quantity of character comparisons in sequential performance is enabled by a preponderance of the string-matching algorithms, albeit with a weakness in consumed time. Hence, researchers have emphasized the importance of focusing on the time consumption issues by utilizing parallel processing due to its capability in reducing time consumption in exact string-matching algorithms [4]. Parallelism is dependent on the complexity and cooperation amongst the processors or computer cores to address the sequential computer issues. These parallel applications rely on a pair of approaches: data decomposition and function decomposition. Shared memory and distributed memory are the constituents of the parallel computer architecture. Therefore, the techniques used are categorized by the method they use to access memory. In the first method that uses the shared memory technique, the processors only utilize one access method to access the common memory. This shared memory technique is utilized to keep data, in addition to various functions like synchronization and communication purposes between the processors [17, 20].

The fundamental characteristics and operational behavior of the SSABS algorithm are analyzed in this section. The principal aim is to determine the computationally intensive code components via the examination of the SSABS algorithm’s sequential version that includes the preprocessing and searching stages. The overall improvement and algorithm efficiency are achieved through understanding of these crucial performance aspects, as they are the enablers of efficient parallelization using Pthreads.

3.1 Sequential SSABS algorithm

The SSABS algorithm is a string-matching algorithm that combines the Boyer-Moore and Sunday's Quick Search heuristics. Its main objective is to decrease the number of shifts and optimize the average shift distance during pattern searching. During the preprocessing stage, the SSABS formulates the qsBc table, which delegates a shift value to individual alphabet characters. The value represents the character distance from the pattern terminal, or $m+1$ if lacking in the pattern. The qsBc offers constant, favorable, and typically larger shift values, which are independent of the comparison order; this allows for faster and more predictable searching in comparison to the Boyer-Moore bad-character rule.

Throughout the searching stage, the SSABS performs pattern arrangements and matching with a text segment; it conducts comparisons mainly from the right-to-left positions. Firstly, the terminal pattern character and the window are compared; if there is a match, the first pattern character and the corresponding window character are contrasted to ascertain the main similarities between the pattern and the window. But if there is no match in the characters, the residual characters are contrasted successively. The algorithm uses the qsBc table to calculate the needed extent to move the pattern; this extent is based on the character immediately following the current text window once there is a match or mismatch. This procedure is repeated until the text is scanned [30].

3.2 Parallel Implementation of Sheik-Sumit-Anindya-Balakrishnan-Sekar algorithm using Pthreads

The threads are implemented autonomously using available implementation components that function inside a shared memory space; hence, it is an effective method for addressing simultaneous functions. These threads are widely used in shared-memory multiprocessor and multi-core systems to achieve true parallelism performance. The Pthreads library provides a harmonized and limited C program thread management interface on UNIX-based platforms following the IEEE POSIX 1003.1c standard. This library enables multiple-thread generation and coordination within an individual procedure, supporting the realization of an effective parallel computation. The attainment of parallelism in UNIX environments is enabled through the fork system call, which generates a new process that operates autonomously from its parent. Nevertheless, experimental studies have demonstrated that Pthreads provide outstanding performance in comparison to fork-based parallelism. The value-added edge stems from the substantially reduced operating system overhead that is linked to the generation of threads and context switching due to the sharing of the same address space; this is contrary to autonomous processes produced by fork.

The implementation of the parallel SSABS algorithm is achieved via a succession of explicit stages that align thread performance and data processing. The initial step involves the formation and management of threads, and the preparation for parallelism. A determined peak quantity of threads is specified, with individual threads assigned a specific exclusive identifier from 0 to P – 1, where P signifies the total number of active threads. This was followed by the creation of threads and the initiation of dedicated thread tasks. Before the implementation, mutex mechanisms are activated using a predetermined static initializer to regulate access to shared variables. Mutex lock and unlock operations are employed to guarantee that only one thread can access shared data at any instance, thus averting race conditions. Furthermore, control functions are employed for execution synchronicity by awaiting the completion of a designated thread or all threads before advancing further.

In the second stage, the first step is setting up important basic input parameters and their assignment to several threads. Global access is provided to the core SSABS algorithm variables involving text length (n), text array (y), pattern length (m), and pattern array (x). The algorithm's preprocessing function is conducted simultaneously, producing heuristic structures such as the qsBc table; this enables effective search window changes throughout the pattern matching process.

In the third stage, the input text is split into smaller sections to achieve parallel processing. A designated thread is allocated to each section of the text. Each segment's size is expanded to incorporate an overlap based on the pattern length determined as n/p + m – 1; this is aimed at preventing missing pattern matches at the segment edges. If synchronized access to shared data is required, mutex lock and unlock procedures are employed, and threads process their allotted segments concurrently. Each thread individually conducts the SSABS search on the text segment assigned to it in the final stage using the identical pattern and shift rules adopted in the Quick Search method. This enables the threads to find precise pattern matches effectively. Each thread tracks local performance metrics during the query, such as the number of character comparisons, the overall matching attempts, and the segments’ processing time. The final stage combines the outcomes from the search trajectory of each thread. The partial outputs from each thread, including execution times and performance metrics, are merged using a reduction mutex; this merging creates a global number(s) that signify the general performance of the parallel SSABS algorithm. The mutex is released after the aggregation to guarantee appropriate synchronization and to preserve data integrity. This phase, as depicted in Figure 1, offers an extensive assessment of the algorithm's scalability and efficiency.

image003.png

Figure 1. Flowchart of the parallel execution of the Sheik-Sumit-Anindya-Balakrishnan-Sekar (SSABS) algorithm using Pthreads

3.3 Parallel implementation of the proposed algorithm

A personal computer with an Intel® Core™ i7-6600U CPU, 8 GB of RAM, and a 256 GB SSD, running Ubuntu 18.04.6 LTS under Windows 10 through WSL2, was used to assess the parallel SSABS algorithm. GCC 7.5.0 was used to compile the Source code with optimization flags for native Pthreads. The WSL2 environment functions through a lightweight Type-1 hypervisor virtual machine, but has a structurally insignificant effect on multi-threaded performance. WSL2 differs from virtualization by running a native Linux kernel wherein execution streams can be mapped by the Pthreads library directly onto physical host CPU cores. The execution paths avoided virtualization translation overhead since the parallel SSABS implementation is strictly CPU-bound and functions wholly inside pre-allocated RAM buffers and bypasses virtual disk I/O bottlenecks. Thus, the virtualization layer introduced negligible noise latency, which ensures that the trends for empirical speedup and efficiency continuously reflect the performance of the native hardware.

3.4 The performance metrics

The parallel version of the suggested algorithm was achieved using Pthreads. Several evaluation metrics, such as execution time, speedup, and efficiency, were used to benchmark the performance of the parallel implementation with the sequential counterpart [31]. The overall time needed to complete a task is termed the execution time. It represents the time span needed for a single processor to run the algorithm from the beginning (initialization) to its termination (completion), represented as T_s. The execution time (T_p) for the parallel version is the time span from the start of the first thread to the end of the final thread's execution.

The enhanced performance derived from parallel execution is quantified using speedup; it is defined as the ratio of the sequential execution time to the parallel execution time (where S is the calculated speedup, T_s is the time spent in the sequential version, and T_p is the time spent in the parallel version). Eq. (1) is used for time calculation (measured in milliseconds).

$\operatorname{Speedup}(S)=\frac{T_s}{T_p}$   (1)

Efficiency refers to the effective utilization of available processing cores during parallelism; it is calculated as the ratio of the speedup attained to the total number of cores in totality used. Improved resource use with less thread idle time demonstrates higher efficiency. Efficiency is calculated using Eq. (2), where P is the number of processing cores, and S is the speedup.

$\operatorname{Efficiency}(E)=\frac{S}{P}$   (2)

3.5 Theoretical performance and complexity analysis

The scalability constraints of the multi-core SSABS application were clarified by modelling its execution profile using formal parallel complexity theory.

3.5.1 Parallel time complexity

The SSABS algorithm requires a preprocessing step to build the qsBc shift table; this requires $O(m$ $+\Sigma)$ time, where $m$ is the pattern length, and the alphabet size is indicated by $\Sigma$. The parallel model executed this phase sequentially by the master thread to circumvent redundant table allocations. For the searching phase, the length of the text $n$ was split among $p$ processing cores. Given overlaps of pattern boundaries, the chunk size processed by each core was exactly $\frac{n}{p}+m-1$ characters. Assuming that the load was equally distributed across all threads, the parallel execution time complexity per thread is bounded as follows:

$\mathrm{O}\left(\left(\frac{n}{p}+m-1\right) \cdot m\right)$   (3)

In the best-case shifting scenario (large alphabet sizes, such as the Source dataset), the inner pattern matching cost is decreased, and the search bounds per core are reduced to $O\left(\frac{n}{p . m}\right)$.

3.5.2 Theoretical speedup bounds (‘Amdahl's Law')

Amdahl’s Law controls the maximum achievable speedup (S) of the parallel framework in this study as follows:

$S(p)=\frac{1}{f+\frac{1-f}{p}}$    (4)

where, f is the strictly sequential fraction of the application, and p is the number of cores.

In this implementation, f consisted of the following:

1. The sequential initialization and pre-processing of the qsBc table;
2. The latency of the operating system needed to spawn and context-switch the Pthreads.

As f > 0, the speedup scaling curve naturally flattened as p transitioned from four to eight cores, which clarified the sub-linear scaling curves observed empirically (see Section 4).

3.5.3 Synchronization and scalability costs

The text searching phase ended with the introduction of the synchronization overhead. The total match positions across chunks were aggregated into a global shared vector by applying a mutual exclusion lock (pthread_mutex_t) or an explicit barrier synchronization. A serialization overhead restricted by $O(p . k)$ was introduced by this important section, where the match hits frequency is denoted by $k$. The overhead of this synchronization barrier management began to compete with the decreasing computational chunk size $\left(\frac{n}{p}\right)$ when $p$ increased to 8 , which indicated the scalability of the algorithm.

3.6 Experiment design

The experiment data for this study was sourced from the Pizza & Chili Corpus repository. Four distinct dataset categories were chosen (Extensible Markup Language (XML), Source, DNA, and Protein), each having a 200 MB file size. Statistical reliability was ensured, and anomalies were eliminated from background thread noise by performing each experiment five times and averaging the results. These iterations yielded negligible variance, which confirmed the high stability and environmental consistency of the profiles of execution.

Configurations with 2, 4, and 8 processing cores were employed for parallel studies. The execution times were indicated as follows: Sequential implementation is denoted as seq, whilst executions utilizing 2, 4, and 8 processor cores were denoted by C2, C4, and C8, respectively. Improvement was assessed through a performance comparison between the sequential version and the parallel version. The averaged values were analyzed to enable a fair comparison of datasets and algorithm performance. Throughout the trials, the pattern length ranged from 10 to 100 characters. The performance data indicated the impact of different pattern sizes on execution time, speedup, and efficiency using varying colors.