Key Takeaways & Executive Findings
- •• Introduces CUSMART, a CUDA-based parallel implementation of the SMART library, integrating 64 string matching algorithms for GPGPU acceleration. • Demonstrates significant performance improvements and scalability of string matching algorithms on NVIDIA GPUs through systematic parallelization and optimization. • Provides a comprehensive comparative analysis of parallelized algorithms across multiple scenarios, identifying strengths and weaknesses for specific use cases. • Establishes practical optimization techniques for GPGPU-based string matching, contributing to high-performance text processing in big data and related fields.
Abstract
This study presents a parallel version of the string matching algorithms research tool (SMART) library, implemented on NVIDIA’s compute unified device architecture (CUDA) platform, and uses general-purpose computing on graphics processing unit (GPGPU) programming concepts to enhance performance and gain insight into the parallel versions of these algorithms. We have developed the CUDA-enhanced SMART (CUSMART) library, which incorporates parallelized iterations of 64 string matching algorithms, leveraging the CUDA application programming interface. The performance of these algorithms has been assessed across various scenarios to ensure a comprehensive and impartial comparison, allowing for the identification of their strengths and weaknesses in specific application contexts. We have explored and established optimization techniques to gauge their influence on the performance of these algorithms. The results of this study highlight the potential of GPGPU computing in string matching applications through the scalability of algorithms, suggesting significant performance improvements. Furthermore, we have identified the best and worst performing algorithms in various scenarios.
1. Introduction
String matching holds significant importance within the realm of text processing. It serves as an essential component used by operating systems’ functional software. Despite data being shared and stored in numerous formats, text remains the predominant form of information handling. This is particularly evident in the literature, where data consists of extensive corpora. Similarly, in the realm of computer science, large quantities of data are stored in linear data files. Molecular biology presents another instance, where biological molecules are approximated as sequences of more fundamental building blocks such as amino acids or nucleotides, treated as strings. The programming methodologies emphasized in string matching serve as foundational paradigms in various other fields of information technology, including computer security (Lu and Fu, 1978), bio-informatics (Crochemore and Rytter, 1994; Han et al., 2007), social media content processing (Tian et al., 2012), data mining (Sellis, 1998), data compression (Ziv and Lempel, 1977), coding theory (Petrakis, 1993; Lin CY and Och, 2004), and numerous other fields.
In computer-centric domains, the utilization and accumulation of data are growing continually. Correspondingly, the processing and computational requirements for these data have been escalating. Particularly, within the domains of high-performance computing and big data, this concern has gained heightened importance in recent years. The extension of calculation time resulting from the expansion of data volume not only leads to notably prolonged response time in string matching applications but also intensifies the performance demands on string matching algorithms. As a result, the reduction of calculation time becomes crucial to ensure system availability. This leads to the need for new solutions and hardware support to effectively manage the escalating demands.
Parallel processing serves as the primary solution to reduce calculation time in high-performance computing, with the central processing unit (CPU) historically underpinning the foundation for parallel calculations (Ceruzzi, 2003). The processing of string matching algorithms in parallel systems has been previously investigated, with a focus on tackling individual algorithms and aiming to achieve higher performance against CPUs specifically for those particular algorithms (Ashkiani et al., 2016). However, due to limitations such as the finite number of cores in CPUs, the concept of general-purpose GPU (GPGPU) has gained prominence as an alternative that offers significant computational power. Therefore, parallel computing with GPGPU can be used for string matching. In this paper, we present a compute unified device architecture (CUDA)-enhanced string matching algorithms research tool (CUSMART), applied for a study on parallelization in general-purpose computing on graphics processing units (GPGPUs). Parallelization is achieved by implementing classic serial string matching algorithms on GPUs and applying several optimization techniques.
Loading authentic research manuscript (Pages 1–5)...
Adnan OZSOY, Mengu NAZLI, Onur CANKUR, Cagri SAHIN (2025). CUSMART: effective parallelization of string matching algorithms using GPGPU accelerators. Frontiers of Information Technology & Electronic Engineering. https://doi.org/10.1631/FITEE_2400091
Research & Educational Purpose Only:The translations, structured abstracts, analytical annotations, and data reports provided by SinoTechIntel are intended exclusively for academic research, internal corporate R&D, and educational benchmarking. They do not constitute formal engineering, chemical safety, legal, or professional advice.
Copyright & Intellectual Property Notice: Original copyright of the underlying source articles and experimental data remains with the respective authors, institutions, and original publishing journals. SinoTechIntel claims intellectual property only over its proprietary translations, analytical syntheses, and AEO structured enhancements in accordance with international fair use and academic citation principles.
Frequently Asked Questions
What is CUSMART?
CUSMART (CUDA-enhanced String Matching Algorithms Research Tool) is a parallel implementation of the SMART library that runs on NVIDIA's CUDA platform. It integrates 64 string matching algorithms using GPGPU programming to improve performance.
How does CUSMART enhance string matching performance?
CUSMART leverages general-purpose computing on graphics processing units (GPGPU) to parallelize classic serial string matching algorithms. It applies several optimization techniques and demonstrates significant scalability and performance improvements across various scenarios.
What optimization techniques were explored in the study?
The authors investigated and established various optimization techniques for GPU-based string matching. These include efficient parallelization strategies, memory access patterns, and workload distribution methods to maximize throughput on CUDA-enabled GPUs.
What are the main findings of the CUSMART study?
The study highlights the potential of GPGPU computing in string matching applications, showing significant performance gains. It also identifies the best and worst performing algorithms across different contexts, providing insights for algorithm selection.
Why is GPGPU computing suitable for string matching?
GPGPU computing offers massive parallelism, which is ideal for string matching tasks that can be partitioned into independent subproblems. This allows for substantial reductions in calculation time compared to traditional CPU-based implementations, especially for large datasets.
Related Technical Papers & Translations
Design and optimization of a high-efficiency distillation process for cellulosic fuel ethanol integrated with thermal coupling and molecular sieve adsorption
To address the challenges of high energy consumption and prominent costs in the traditional three-columns distillation process for cellulosic fuel ethanol, a distillation—molecular sieve coupling separation process is proposed. This process integrates a three-column (crude distillation column, first distillation column, second distillation column) system with a 3A molecular sieve adsorption deep dehydration unit. A thermal coupling network is constructed via differential pressure design (steam from medium/high-pressure columns as mutual heat sources, reboiler liquid waste heat for feed preheating), and molecular sieve adsorption conditions are optimized. The study first performs a thermodynamic consistency test on the ethanol—water system, determines optimal non-random two-liquid (NRTL) model binary interaction parameters via experimental data regression for Aspen Plus simulation. Aiming at minimum total annual cost (TAC), Aspen Plus is used to optimize process parameters (theoretical tray number, feed location, reflux ratio, side-draw position, etc.). Economic analysis shows this process reduces CO2 emission costs by 27.56%, TAC by 15.58% (to 5.123 × 106 USD·a-1), and increases ethanol purity to ＞99.6%, providing an effective solution for green, efficient separation.
A cohesion loss model for determining residual strength of deep bedded sandstone
Rock residual strength, as an important input parameter, plays an indispensable role in proposing the reasonable and scientific scheme about stope design, underground tunnel excavation and stability evaluation of deep chambers. Therefore, previous residual strength models of rocks established were reviewed. And corresponding related problems were stated. Subsequently, starting from the effects of bedding and whole life-cycle evolution process, series of triaxial mechanical tests of deep bedded s
Federated model with contrastive learning and adaptive control variates for human activity recognition
Recent attention to privacy issues demands a communication-safe method for training human activity recognition (HAR) models on client activity data. Federated learning (FL) has become a compelling technique to facilitate model training between the server and clients while preserving data privacy. However, classical FL methods often assume independent and identically distributed (IID) data among clients. This assumption does not hold true in practical scenarios. Human activity in real-world scena