Cluster Computing

[Link] (0123456789().,-volV)(0123456789().
,- volV)

High performance parallel KMP algorithm on a heterogeneous

architecture
Neungsoo Park1 • Soeun Park1 • Myungho Lee2

Received: 20 February 2019 / Revised: 4 August 2019 / Accepted: 14 August 2019

Ó Springer Science+Business Media, LLC, part of Springer Nature 2019

Abstract
String matching algorithm is widely used in many application areas such as bio-informatics, network intrusion detection,
computer virus scan, among many others. Knuth–Morris–Pratt (KMP) algorithm is commonly used for its fast execution
time compared with many other string matching algorithms when applied to large input texts. However, the performance of
the KMP algorithm is limited when the input text size increases significantly beyond a certain limit. In this paper, we
propose a high performance parallel KMP algorithm on the Heterogeneous High Performance Computing (HPC) archi-
tecture based on the general-purpose multicore microprocessor and the manycore graphic processing unit (GPU) using
OpenCL as the General Purpose computing using Graphic Processing Unit (GPGPU) platform. The proposed parallel KMP
algorithm mainly focuses on optimizing the CPU–GPU memory hierarchy by overlapping the data transfer between the
CPU memory and the GPU memory with the string matching operations on the GPU. It also optimizes the allocation of the
work-groups and the work-items, and places the pattern data and the failure table in the on-chip local memory of the GPU.
Exploiting multiple GPUs further the performance improvements. The experimental results show that the optimized
parallel KMP algorithm leads up to 15.25 times speedup compared with the version before our optimization techniques
were applied.

Keywords KMP algorithm
GPGPU
OpenCL
Heterogeneous computing
Computation communication overlapping

1 Introduction when it is applied to large sized input texts and reference

patterns. However, when the input text size increases sig-
String matching algorithms are commonly used in various nificantly beyond a certain limit such as in the genome
applications such as the keyword matching for the given sequence matching, the execution time also increases
input text, the intrusion detection in the network system accordingly [6]. Therefore, it is crucial to minimize the
[1, 2], the human genome sequence matching for the bio- execution time by efficiently parallelizing the KMP algo-
informatics [3], among many others [4, 5]. The Knuth– rithm [7].
Morris–Pratt (KMP) algorithm is superior to other similar Recently, a heterogeneous high performance computing
pattern matching algorithms for its fast execution time (HPC) architectures based on general-purpose multicore
microprocessors and the manycore graphic processing units
(GPUs) are becoming increasingly popular for a wide range
& Myungho Lee
myunghol@[Link] of applications. Its influence has been steadily growing in
the Top 500 list, in particular, and in other various appli-
Neungsoo Park
neungsoo@[Link] cations. The architecture of the GPU has gone through a
number of innovative design changes in the last 1.5 dec-
Soeun Park
kaipia8@[Link] ades by integrating a large number of fine-grained uniform
cores with the multithreading capability, levels of the cache
1
Department of Computer Science & Engineering, Konkuk hierarchies, enhanced bandwidths with the memory and
University, Seoul, Korea other CPU or GPU chips, and the large amount of the on-
2
Department of Computer Science & Engineering, Myongji board memory. These architectural innovations have led to
University, Yongin, Kyungkido, Korea

123
 Cluster Computing

a drastic performance improvement to surpass several stored at the corresponding index of the failure table. Then
Teraflops for the double precision arithmetic per chip. In the whole window of the pattern string is shifted by the
addition, user friendly programming environments such as number to the forward direction of the input text string.
CUDA [8, 9] from Nvidia, OpenCL [10, 11] from Khronos Figure 1 illustrates the KMP algorithm. In Fig. 1a, the
Group, OpenACC [12] from a subgroup of OpenMP pattern string and the input text string matches from index
Architecture Review Board (ARB) have been developed 0 to 4. When Input Text[5] is compared with Pattern
for the general-purpose computing using GPUs (GPGPU). String[5], a mismatch occurs. We check the Failure
There has been some previous research to speed-up the Table[4] = 2, since Failure Table[i-1] is the re-starting
KMP algorithm using the GPU or the field programmable index when the Pattern String[i] is mismatched. For the
gate array (FPGA) [13–18]. In this paper, we aim to optimize subsequent string matching operations, we slide the pattern
the performance of the KMP algorithm on the heterogeneous string window by 3 (= Table[5]) characters to the right and
architecture by optimizing the CPU–GPU memory hierarchy then continue to match from the Pattern String[2] as shown
and the efficient parallelization using the OpenCL. In order in Fig. 1b.
to minimize the memory access latencies, we place the pat- Assume that the input text length is L and the pattern
tern data and the failure table used for the string matching in string length is P. The time complexity of the KMP algo-
the local memory in OpenCL (shared-memory on Nvidia rithm is O(L ? P). Previous algorithms without the failure
GPU). We then optimize the allocation of the work-groups table result in O(LP) time complexity. Therefore, the KMP
and the work-items on the GPU to maximize the benefit of algorithm is superior to the previous algorithms [19].
the multithreading. For further performance improvement, The execution time of the KMP algorithm grows lin-
the input/output data transfers between the CPU memory and early as the input text size increases, as shown in Fig. 2.
the GPU memory are overlapped with the string matching For an application dealing with a huge input size such as in
operations on the GPU. We also exploit multiple GPUs for the human genome sequence matching, it is crucial to
the parallel KMP algorithms. The resulting optimized par- minimize the execution time by parallelizing and opti-
allel implementation leads up to 15.25 times performance mizing the KMP algorithm.
improvement compared with the previous parallel KMP on
GPU version before our optimization techniques were
applied. 3 Parallelization of KMP algorithm
The rest of the paper is organized as follows: Section 2
introduces the KMP algorithm. Section 3 explains our 3.1 Preliminaries
techniques for parallelizing and optimizing the KMP
algorithm. Section 4 shows the experimental results with In this section, we explain our parallelization and opti-
analyses. Section 5 concludes the paper with future mization strategies for the KMP algorithm on the hetero-
research directions. geneous architecture based on the multicore CPU and the
manycore GPU using OpenCL as the GPGPU platform. In
order to minimize the memory access latencies, we place
2 KMP algorithm

KMP algorithm was developed by Knuth et al. [19]. This

algorithm uses the prefix and the suffix of the reference
pattern string in the process of the pattern matching. First, a
preprocessing step is conducted for the reference pattern
string to generate a failure table. The pattern string and its
failure fable have the same length. Starting with the
beginning of the pattern string, we count the number of
occurrences of the pattern matching with the prefix and the
suffix at the current index of the string until we reach the
end of the pattern string. We store these count values at the
corresponding indices of the failure table. Next, we con-
duct the pattern matching of the reference string with the
input text using the failure table. When a character in the
pattern string matches with the character in the input text,
the pattern match continues for the next character. When a
mismatch occurs, then we skip by the number of characters Fig. 1 Illustration of KMP algorithm

123
Cluster Computing

Wgroup / CUgpu
Wlitem / Witem=CU ð1Þ
Witem=cu  PECU
where Wgroup is the total number of work-groups, Witem/CU
is the number of work-items allocated to each CU called as
the local work items, Wlitem is the number of work-items
allocated to each CU called as the local work items, PECU
is the number of PE’s in each CU, and CUgpu is the number
of CU’s on GPU.
Fig. 2 Execution time of KMP algorithm for various input sizes To optimize the performance, we need to explore the
parameters for the work-item and the work-group by con-
the pattern data and the failure table in the local memory sidering the proposed conditions. To reduce the space for
(shared-memory on the Nvidia GPU) because their sizes the exploration, the local and the global work-item are
are rather limited and can be accommodated in the small- allocated as follows:
sized local memory. We then optimize the allocation of the Wlitem ¼ k  Witem=CU ¼ kPECU
work-groups and the work-items on the GPU to maximize ð2Þ
Wgitem ¼ a
Wlitem
Wgroup ¼ a
Wlitem
PECU
the benefit of the multithreading capability of the GPU. For
further performance improvement, we optimize the CPU– where Wgitem is the total number of work-items called as
GPU memory hierarchy by overlapping the input/output the global work item, k and a are multipliers to select the
data transfers between the CPU memory and the GPU work-items. The size of the sub-text allocated to each
memory with the string matching operations on the GPU. work-item (Lpart) is.
We also exploit multiple GPUs in the heterogeneous L P 1
architecture for the parallel KMP algorithm. In the fol- Lpart ¼
Wgitem ð3Þ
lowing subsections, we explain the work-item and the
work-group allocation, the overlapping of pattern matching Lsub ¼ Lpart þ P 1
computation with the input/output data transfers, and the where L is the input text length, P is the pattern string
exploiting of the multiple GPUs. length and Lsub is the length of subtext to be assigned to
each work-item.
3.2 Optimizing work-item and work-group The total number of characters in the input text string
allocation that needs to be scanned for the string matching is L-P?1.
Thus we need to evenly divide them amongst all work-
Assuming we place the pattern string and the failure items. For each work-item, we need to allocate extra P-1
table in the on-chip local memory of the GPU, the input characters in order to avoid the missing pattern string
text string is loaded from the global memory to the regis- matching. The range of the input text that each work-item
ters of the GPU. The input text is divided into small sub- processes is
texts. We let each sub-text to be allocated to a work-item to
be mapped to each processing element (PE) of the GPU. Wid  Lpart  i  ðWid þ 1Þ
Lpart þ ðP 1Þ
ð4Þ
Then the pattern matching is conducted between the pattern for 0  Wid  Wgitem 1
string and the work-items. A possible matching sub-text
where Wid is the id-th work-item. The overall time com-
might be separated into two consecutive sub-texts. To
plexity based on OpenCL is
avoid this, we redundantly copy (P - 1) characters of the  
subsequent sub-text. Multiple work-items are allocated to L
O þP
each work-group. Figure 3 illustrates the work-groups and PEgpu
work-items allocation to the whole input text.
where PEgpu ¼ CUgpu  PECU .
In order to optimize the SIMD and multithreaded exe-
cution of the KMP algorithm on the GPU, we need to
3.3 Optimizations considering CPU–GPU
carefully decide the input sub-text size for the work-item.
memory hierarchy
We also need to carefully decide the number of work-items
to be allocated to each work-group which will be mapped
Parallel computing on the heterogeneous architectures
to a computing unit (CU) of the GPU. The conditions of
based on the multicore CPU and the manycore GPU
work-items and work-groups are allocated as follows:
involves the data transfers between the host DRAM and the

123
 Cluster Computing

Fig. 3 Work-item and work-

group allocation

device memory. Thus we extend the memory hierarchy to string matching operations are conducted on the GPU. For
include the host side DRAM from the GPU perspective each computation of the input data chunk, the number of
(see Fig. 4). Our optimization for the KMP algorithm matching occurrences is counted and copied back to the
considers such a memory hierarchy. At the top of the host side main memory.
memory hierarchy is the local memory (or shared-memory The total execution time of the KMP algorithm is
on Nvidia GPU), followed by the global memory (a region
TEX ¼ L=sd þ Tgpu þ R=sd ð5Þ
in the device memory), and the host side main memory.
There is an order of magnitude memory latency differences where L is the input text length, sd is the data transfer rate
as we go down the hierarchy [9]. between CPU and GPU over the PCI-Express, Tgpu is the
As explained in Sect. 3.1, the frequently referenced string matching computation time on GPU and R is the
pattern string and the failure table are stored in the local length of the result data for each input chunk.
memory. However, since the input data has low reuses, we The data transfer from the host main memory to the
load the input data to the registers from the global memory. global memory takes a long time. In order to reduce or hide
The input data is usually large, and it may not fit in the the high overhead of the data transfer, we overlap the
global memory of the GPU. Thus, we assume that it is computation (string matching operation) of the current
initially placed in the host main memory. Then we divide chunk with the data transfer of the next chunk so that all
the input data into multiple chunks each of which can fit in the subsequent input data chunk is transferred while the
the global memory of the GPU. Then we copy each chunk current chunk is computed. Then the result data for the
to the global memory in turn. For each input data chunk, current chunk is transferred back to the host main memory.
This data transfer is also overlapped with the string
matching computation.
Figure 5 illustrates our optimization strategy of dividing
the input data into 4 chunks, overlapping the computations
and the data transfers for both the input and the output data.

Fig. 4 Performance optimization considering CPU–GPU memory

hierarchy Fig. 5 Overlapping data transfers with string matching computations

123
Cluster Computing

This scenario is contrasted to the non-overlapping case and speedup using the multiple GPUs is lower than the linear
shows that the execution time gets improved. The execu- speedup.
tion time using the overlapping is
L R
Toverlapping ¼ þ Ns
Tstage þ ð6Þ 4 Experimental results
N s sd Ns sd
where Ns is the number of data chunks or streams and Tstage For evaluating the performance improvement of our pro-
is the execution time of each overlapped stages. posed parallelization and optimization approach, we
The amount of data copied from the CPU host to the implemented our approach using the OpenCL on two dif-
GPU device at each stream is L=Ns . The amount of data ferent platforms as shown in the following Table 1.
copied from the GPU device to the CPU host at each For the experiments, we used a pattern string of length 8,
stream is R=Ns . The optimization of work-group and work- 16, 24, 30, 60, and 96. The length of an input text was
item allocation discussed in Sect. 3.2 is applied to each varied from 1 MB to 1 GB (1 MB, 10 MB, 100 MB,
stream computation. 250 MB, 500 MB, and 1 GB). We measured the whole
Tstage is the longest time among H2D (CPU Host-to- execution time which includes sending the input data from
GPU Device) transfer time, GPU execution time, and D2H the host main memory to the device memory, performing
(GPU Device-to-CPU Host) transfer time for each stream the pattern matching operations, and returning the result
data. Most of the execution time savings stems from the data from the device memory to the host memory. The
hidden data transfer time with the computation time. reported execution time is the average of five execution
times for each experimental set. For the performance
3.4 Exploiting multiple GPUs comparisons, we measured the time without optimization
and the time with various optimizations including work-
In order to further the performance improvements, we item and work-group allocations, local memory copy, the
exploit multiple GPUs in our heterogeneous architecture. computation and the data transfer overlapping, and
Figure 6 illustrates the execution scenario of KMP algo- exploiting multiple GPUs.
rithm using two GPUs while overlapping the string Figure 7 shows the execution times when the number of
matching computations with the data transfers. Given the global work items was varied in OpenCL. As shown in the
input data, as the number of GPU used increases, the data figure, even though the number of work-items increases,
chunk size for each data stream decreases. Thus the times the performance did not improve. Therefore, it is crucial to
for the computation and the data transfer are reduced carefully select the computation parameters considering
accordingly. However, as we increase the number of GPUs work-groups and work-items in order to optimize the per-
and the resulting number of data streams, the burden on the formance. However, the search space to explore all the
communication medium between the host memory and the possibilities or combinations is too huge to apply an
device memory increases. Also, the data transfer time does exhaustive search. In this paper, we consider the proposed
not decrease linearly in accordance with the decrease of the work-items selection strategy described in Sect. 3.2.
data chunk size, because the start-up time for the data Figure 8 shows the execution time on the GTX 1080 Ti
transfer which is a major overhead does not decrease lin- platform using the proposed work-items/work-group opti-
early with the data size decrease. Therefore, the expected mizations for pattern length = 8 and 6 different text sizes.
The work-group (Wgroup) is set to the number of CUs as
shown in Table 1. The work-item (Wlitem ) is considered as
the multiple (a) of the number of PEs in Table 1 as dis-
cussed in Sect. 3.2. We conducted experiments varying
work-item (Wlitem ) and a from 1 to 1024 in order to find the
best performance combination. As shown in Fig. 8, the best
performance for large strings was shown in the global
work-item (Wgitem ) = 14,336 when work-group = 28, work-
item (Wlitem ) = 256 or 512, and a ¼ 2 or 1. Figure 9 pre-
sents the execution time on the Tesla P100 platform for
pattern length=16 and text size = 100 MB, 500 MB and
1 GB cases. Tesla P100 consists of 56 CUs. The best
performance for large strings was achieved when the work-
group (Wgroup) = 56, the work-item (Wlitem ) = 256 or 512,
Fig. 6 Multi-streams overlapping on two GPUs

123
 Cluster Computing

Table 1 Experimental
Platforms GTX 1080 Ti Tesla P100
environment
CPU Intel Xeon CPU Intel Xeon CPU
E5-2620 E5-1650
GPU
Device 4 9 Nvidia GeForce GTX 1080 Ti 1 9 Nvidia Tesla P100
OpenCL version 1.2 1.2
Device memory size 11 GB 16 GB
Local memory size (shared memory) 48 KB 48 KB
No of CUs 28 56
No of PEs/CU 128 64

180 400
PaƩern Length: 8 PaƩern Length: 8
160 PaƩern Length: 24 350 PaƩern Length: 24
140
300
Excution TI me (msec)

Excution TI me (msec)
120
250
100
200
80
150
60
100
40

20 50

0 0

No. of Global Items No. of Global Items

(a) 250MB, No. of local items = 256 (b) 500MB, No. of local items = 512
Fig. 7 Execution times without any optimization on Nvidia GeForce GTX 1080 Ti

and a ¼ 512 or 1024. Unlike GTX 1080 Ti, the best per- Figure 12 shows the effect of overlapping the compu-
formance on the Tesla P100 was found around a large a in tation and the data transfer of the multi-stream on the
experimental results. Even though a is large, the experi- single GTX 1080 Ti. The work-group and work-item on a
mental results showed that work-item and work-group stream was allocated according to the condition for the
allocation conditions for the best performance still hold. single stream considered in Figs. 8 and 10. The number of
The best performance is found in the following condition: work-items was allocated as 64, 128, 256, 512, or 1024.
Wgitem ¼ a
Wlitem
Wlitem . For 250 MB, 500 MB, and 1 GB cases, the best perfor-
Figure 10 shows the effect of the local memory copy of mance was achieved on the 8 streams with the work-items
the pattern string and the failure table on a GTX 1080 Ti and work-groups allocated for Fig. 12. The best perfor-
platform. The best performance was found in the global mance in 100 MB case was found by overlapping the
work-items = 14,336 when work-group = 28, (work-items, computation and the data transfer of 4 streams. In 1 MB
a) = (128, 4), (256, 2), and (512, 1) pairs, similar to the and 10 MB case, the best performance was achieved when
combination of the work-items/work-group parameters. In 2 streams are overlapped, since the stream computation
the small strings, the local copy was one of the overheads overhead nullified the performance gain from the stream
for the pattern matching computation. As the string size overlapping computation in the small string. Figure 13
increases, the performance improves up to 1.45 times shows the effect of overlapping the computation and the
compared with work-group/work-item only optimization. data transfer of multi-stream on the Tesla P100 platform.
Figure 11 shows the effect of the local memory copy of the For the input text size 500 MB and 1 GB cases, the best
pattern string and the failure table on a Tesla P100 plat- performance was achieved on the 8 streams with the work-
form, also. items and work-groups allocation parameters shown in
Fig. 8. Since the input text is divided and distributed into

123
Cluster Computing

=1 =2 =4 =8 =1 =2 =4 =8 =1 =2 =4 =8
=16 =32 =64 =128 =16 =32 =64 =128
=16 =32 =64 =128 =256 =512 =1024 =256 =512 =1024
2.5 10 90
9 80
2 8 70
Excution TIme(msec)

Excution TIme(msec)

Excution TIme(msec)
7
60
1.5 6
50
5
40
1 4
30
3
0.5 2 20

1 10
0 0 0
64 128 256 512 1024 64 128 256 512 1024 64 128 256 512 1024
Work Items Work Items Work Items

(a) 1MB (b) 10MB (c) 100MB

=1 =2 =4 =8 =1 =2 =4 =8 =1 =2 =4 =8
=16 =32 =64 =128 =16 =32 =64 =128 =16 =32 =64 =128
=256 =512 =1024 =256 =512 =1024 =256 =512 =1024
200 450 800
180 400 700
160 350 600
Excution TIme(msec)

Excution TIme(msec)

Excution TIme(msec)
140
300
120 500
250
100 400
200
80 300
150
60
100 200
40
20 50 100

0 0 0
64 128 256 512 1024 64 128 256 512 1024 64 128 256 512 1024
Work Items Work Items Work Items

(d) 250MB (e) 500MB (f) 1GB

Fig. 8 Comparison of work group and work item optimization on GTX 1080Ti: pattern length = 8

120 =1 =2 =4 =8 400 =1 =2 =4 =8 600 =1 =2 =4 =8

=16 =32 =64 =128 =16 =32 =64 =128 =16 =32 =64 =128
=256 =512 =1024 350 =256 =512 =1024 =256 =512 =1024
100 500
300
Excution TIme(msec)

Excution TIme(msec)

Excution TIme(msec)

80 400
250

60 200 300

150
40 200
100
20 100
50

0 0 0
64 128 256 512 1024 64 128 256 512 1024 64 128 256 512 1024
Work Items Work Items Work Items
(a) 100MB (b) 500MB (c) 1GB

Fig. 9 Comparison of work group and work item optimization on Tesla P100: pattern length = 16

each stream, the input text size in each GPU computation multi-streams on the single GPU (MS1G). The best per-
stream is reduced. Therefore, a became smaller than the a formance was achieved when the number of streams is 16
in Fig. 8. for 1 GB and 8 for 500 MB. For 1 GB and 500 MB case,
Figure 14 shows the execution times using various MS1G achieves up to 2.16 times speedup compared with
optimizations on the single GTX 1080 Ti platform: non- WGWI ? LC and 6 times speedup compared with Non-
optimization (Non-Opt), work-group and work-item Opt. Figure 15 shows the execution times using various
(WGWI), work-group/work-item ? local memory copy optimizations on the Tesla P100 platform. The best per-
(WGWI?LC), the computation and data transfer overlap of formance was achieved when the number of streams is 8

123
 Cluster Computing

2 =1 =2 =4 =8 =16 =32 7 =1 =2 =4 =8 =16 =32 80 =1 =2 =4 =8 =16 =32

1.8 70
6
1.6
60
Excution TIme(msec)

Excution TIme(msec)

Excution TIme(msec)
1.4 5

1.2 50
4
1 40
3
0.8 30
0.6 2
20
0.4
1 10
0.2
0 0 0
64 128 256 512 1024 64 128 256 512 1024 64 128 256 512 1024
Work Items Work Items Work Items
(a) 1MB (b) 10MB (c) 100 MB
200 =1 =2 =4 =8 =16 =32 450 =1 =2 =4 =8 =16 =32 900 =1 =2 =4 =8 =16 =32
180 400 800
160 350 700
Excution TIme(msec)

Excution TIme(msec)

Excution TIme(msec)
140
300 600
120
250 500
100
200 400
80
150 300
60
40 100 200

20 50 100
0 0 0
64 128 256 512 1024 64 128 256 512 1024 64 128 256 512 1024
Work Items Work Items Work Items
(d) 250MB (e) 500MB (f) 1GB
Fig. 10 Comparison of execution times using local-memory copy optimization on GTX 1080Ti: pattern length = 8

90 =1 =2 =4 =8 400 =1 =2 =4 =8 500 =1 =2 =4 =8
=16 =32 =64 =128 =16 =32 =64 =128 =16 =32 =64 =128
80 =256 =512 =1024 350 =256 =512 =1024 450 =256 =512 =1024
70 400
300
350
Excution TIme(msec)

Excution TIme(msec)

Excution TIme(msec)

60
250 300
50
200 250
40
150 200
30
150
100
20 100
10 50 50
0 0 0
64 128 256 512 1024 64 128 256 512 1024 64 128 256 512 1024
Work Items Work Items Work Items
(a) 100MB (b) 500MB (c) 1GB
Fig. 11 Comparison of execution times using local-memory copy optimization on Tesla P100: pattern length = 16

for the input text sizes 1 GB and 500 MB. For 1 GB and through the comparisons of multi-stream on the single GPU
500 MB cases, MS1G achieves up to 3.39 times speedup (MS1G), single-stream on 2 GPUs (SS2G), multi-stream
compared with WGWI ? LC and 6 times speedup com- on 2 GPUs (MS2G), single-stream on 4 GPUs (SS4G), and
pared with Non-Opt. multi-stream on 4 GPUs (MS4G). The best performance of
Figure 16 presents the effect of multi-stream overlap- the string matching computation using the input text 1 GB
ping executions on multi-GPUs (4 9 GTX 1080 Ti) was achieved on the MS4G optimization in the case of 4

123
Cluster Computing

5 64 128 256 512 1024 6 64 128 256 512 1024 60 64 128 256 512 1024
5
5 50
4

Execution Time (msec)

Execution Time (msec)

Execution Time (msec)

4
4 40
3
3 3 30
2
2 20
2
1
1 10
1
0 0 0
2 4 8 16 32 2 4 8 16 32 2 4 8 16 32
No of Streams No of Streams No of Streams
(a) 1MB (b) 10MB (c) 100 MB
140 64 128 256 512 1024 300 64 128 256 512 1024 600 64 128 256 512 1024

120 250 500

Execution Time (msec)

Execution Time (msec)

Execution Time (msec)

100
200 400
80
150 300
60
100 200
40

20 50 100

0 0 0
2 4 8 16 32 2 4 8 16 32 2 4 8 16 32
No of Streams No of Streams No of Streams
(d) 250MB (e) 500MB (f) 1GB
Fig. 12 Comparison of multi-stream executions on a GTX 1080Ti: pattern length = 8

80 64 128 256 512 1024 140 64 128 256 512 1024 300 64 128 256 512 1024
70 120 250
Execution Time (msec)

Execution Time (msec)

Execution Time (msec)

60
100
200
50
80
40 150
60
30
100
40
20
20 50
10

0 0 0
2 4 8 16 32 2 4 8 16 32 2 4 8 16 32
No of Streams No of Streams No of Streams
(a) 100MB (b) 500MB (b) 1GB
Fig. 13 Comparison of multi-stream executions on a Tesla P100: pattern length = 16

streams, the global work-items = 14,336 with work-group = In Fig. 17, the execution times for the pattern length 16,
28, and (work-items, a) = (256, 2) pair. The streaming 24, 30, 60, and 96 are compared with various optimiza-
allocation for the best performance was 16 streams on the tions. The complexity of the proposed parallel KMP


single GPU and 4 streams per GPU on 4 9 GPU platforms. algorithm is O L=PEgpu þ P . Since the input text size L is
It verified that the multi-streams overlapping on multi- large enough compared with PEgpu and the pattern length
GPUs as shown in Fig. 6 improved the overall perfor- (P), the overall performance increased as the input text size
mance. The MS4G achieves up to 2.51 times speedup increased. The performance variation caused by different
compared with MS1G in 1 GB case. pattern lengths was small. In the overall performance
evaluation, our MS4G approach achieves up to 15.25 times

123
 Cluster Computing

2 5 45 42.24
4.57
1.74 4.42
1.8 4.5 40
1.6 1.52 4 32.96
Execution Time (msec)

Execution Time (msec)

Execution Time (msec)

1.41 3.52 35
1.4 3.5
30
1.2 3 23.85
25
1 2.5 2.31
20
0.8 0.69 2
15 13.60
0.6 1.5
0.4 1 10

0.2 0.5 5
0 0 0
Non-Opt WGWI WGWI+LC MS1G Non-Opt WGWI WGWI+LC MS1G Non-Opt WGWI WGWI+LC MS1G

(a) 1MB (b) 10MB (c) 100MB

180 350 700
320.98
156.11 610.60
160
300 600
Execution Time (msec)

Execution Time (msec)

Execution Time (msec)

140
250 500
120
100 200 400
78.10 159.28 307.48
80 150 300
55.01 108.88 219.41
60
100 200
40 28.99 54.16 101.95
50 100
20
0 0 0
Non-Opt WGWI WGWI+LC MS1G Non-Opt WGWI WGWI+LC MS1G Non-Opt WGWI WGWI+LC MS1G

(d) 250MB (e) 500MB (f) 1GB

Fig. 14 Execution time for various optimizations on a GTX 1080Ti: pattern length = 8

80 350 500
313.90 450.39
70 67.72 450
300
400
Execution Time (msec)

Execution Time (msec)

Execution Time (msec)

60
250 350 334.48
50 296.09
300
200
40 35.55 161.99 250
147.90
31.32 150
200 180.77
30
21.44 92.31 150
100
20
100
10 50
50
0 0 0
Non-Opt WGWI WGWI+LC MS1G Non-Opt WGWI WGWI+LC MS1G Non-Opt WGWI WGWI+LC MS1G

(a) 250MB (b) 500MB (c) 1GB

Fig. 15 Execution time for various optimizations on a Tesla P100: pattern length = 16

speedup over the non-optimized parallel implementation we divide the input data into multiple chunks, transfer the
(Non-Opt). data from the host memory to the device memory while the
pattern matching operations are performed for the previous
chunk of the input data. The output data is also transferred
5 Conclusion and future research direction while the computations are being performed on the GPU.
Through the computation and the data transfer overlapping,
In this paper, we introduced a parallelization and opti- most of the data transfers are hidden by the computations.
mization approach for the KMP algorithm on a heteroge- Our approach also optimizes the work-item and work-
neous architecture based on a multicore CPU and group allocations, and also places the pattern data and the
manycore multi-GPUs. In order to optimize the KMP failure table in the local memory. Furthermore, by
algorithm from the input data transfer from the host main exploiting multiple GPUs in the heterogeneous architec-
memory to the device memory and to the result data ture, we further improve the performance. Our approach
transfer from the device memory to the host memory after results in up to 15.25 times speedup over the parallel
the pattern matching operations are performed on the GPU, implementation before applying our optimizations.

123
Cluster Computing

6 16
5
4.60 14.21
4.5 5.03 14 13.60
5
4 12.25
4.37

Execution Time (msec)

12

Execution Time (msec)

Execution Time (msec)

3.5 4
3.52 9.73
10
3 8.62
2.5 3 8
2.31 2.38
1.90
2 6
2
1.5
4
1 0.69 1
0.51 2
0.5 0.34

0 0 0
MS1G SS2G MS2G SS4G MS4G MS1G SS2G MS2G SS4G MS4G MS1G SS2G MS2G SS4G MS4G

(a) 1MB (b) 10MB (c) 100 M

35 60 56.18 120
54.16 109.20
28.99 101.95
30 28.66
50 100
Execution Time (msec)

Execution Time (msec)

Execution Time (msec)

25
40 80
33.82
20 18.73 18.40 31.07
16.97 57.75 58.06
30 26.75 60
15
40.22
20 40
10

5 10 20

0 0 0
MS1G SS2G MS2G SS4G MS4G MS1G SS2G MS2G SS4G MS4G MS1G SS2G MS2G SS4G MS4G

(d) 250MB (e) 500MB (f) 1GB

Fig. 16 Effect of multi-stream overlapping executions on 4 x GTX 1080Ti: pattern length = 8

5 8 50
paƩen length = 16 paƩen length = 16 paƩen length = 16
4.5 paƩen length = 24 7
paƩen length = 24 45 paƩen length = 24
paƩen length = 30 paƩen length = 30 paƩen length = 30
4 40
paƩen length = 60 6 paƩen length = 60 paƩen length = 60
Execution Time (msec)

Execution Time (msec)

Execution Time (msec)

3.5 paƩen length = 96 paƩen length = 96 35 paƩen length = 96

5
3 30

2.5 4 25

2 20
3
1.5 15
2
1 10
1
0.5 5

0 0 0

(a) 1MB (b) 10MB (c) 100 MB

180 400 700
paƩen length = 16 paƩen length = 16 paƩen length = 16
160 paƩen length = 24 350
paƩen length = 24 paƩen length = 24
600
paƩen length = 30 paƩen length = 30 paƩen length = 30
140 paƩen length = 60 paƩen length = 60 paƩen length = 60
300
Execution Time (msec)

Execution Time (msec)

Execution Time (msec)

paƩen length = 96 paƩen length = 96 500 paƩen length = 96

120
250
100 400
200
80 300
150
60
200
100
40

50 100
20

0 0 0

(d) 250MB (e) 500MB (f) 1GB

Fig. 17 Execution time comparison for various pattern length on 4 9 Nvidia GTX 1080ti

123
 Cluster Computing

For further performance improvements, we are working 11. Nvidia: OpenCL Programming Guide for the CUDA Architec-
on copying the input data chunk to the local memory ture. Nvidia. [Link]
load/opencl/nvidia_opencl_programmingguide.pdf (2009)
instead of loading from the global memory directly while 12. [Link]: The OpenACC Application Program-
the pattern matching computations are performed on the ming Interface 2.5. [Link] Doc., pp. 1–118 (2015)
GPU in a multithreaded fashion. A naı̈ve implementation 13. Sidhu, R.P.S., Mei, A., Prasanna, V.K.: String matching on
resulted in the performance loss. For an optimal imple- multicontext FPGAs using self-reconfiguration. In: Proceedings
of 1999 ACM/SIGDA Seventh International Symposium on Field
mentation, we are working on coalescing the multiple Programmable Gate Arrays, pp. 217–226 (1999)
global memory accesses. We also work on avoiding the 14. Rasool, A., Khare, N.: Parallelization of KMP string matching
shared memory bank conflicts. These optimizations will algorithm on different SIMD architectures: multi-core and
lead to further improvement in the computation time. GPGPU’s. Int. J. Comput. Appl. 49(11), 26–28 (2012)
15. Aygun, S., Gunes, E.O., Kouhalvandi, L.: Python based parallel
Together with more aggressive input data partitioning to application of Knuth-Morris-Pratt algorithm. In: Proceedings of
increase the degree of the computation and the communi- 2016 IEEE 4th Workshop on Advances in Information, Elec-
cation overlapping, we expect to boost the overall tronic and Electrical Engineering (AIEEE 2016) (2017)
performance. 16. Alzoabi, U.S., Alosaimi, N.M., Bedaiwi, A.S., Alabdullatif,
A.M.: Parallelization of KMP string matching algorithm. In:
Proceeedings of 2013 World Congress on Computer and Infor-
Acknowledgements This research was supported in part by Basic mation Technology (WCCIT 2013) (2013)
Science Research Program through the National Research Foundation 17. Lei, S., Wang, C., Fang, H., Li, X., Zhou, X.: SCADIS: a scalable
of Korea (NRF) funded by the Ministry of Education (No. accelerator for data-intensive string set matching on FPGAs. In:
2017R1D1A1B03033128). This research was supported in part by Proceeedings of 2016 IEEE Trustcom/BigDataSE/ISPA,
Next-Generation Information Computing Development Program pp. 1190–1197 (2016)
through the National Research Foundation of Korea (NRF) funded by 18. Kouzinopoulos, C.S., Margaritis, K.G.: String matching on a
the Ministry of Education, Science, and Technology (NRF- multicore GPU using CUDA. In: Proceeedings of 2009 13th
2015M3C4A7065662). Panhellenic Conference on Informatics (PCI 2009), pp. 14–18
(2009)
19. Knuth, D.E., Morris Jr., J.H., Pratt, V.R.: Fast pattern matching in
References strings. SIAM J. Comput. 6(2), 323–350 (1977)

1. Bellekens, X., Atkinson, R.C., Renfrew, C., Kirkham, T.: Publisher’s Note Springer Nature remains neutral with regard to
Investigation of GPU-based pattern matching. In: Proceeedings of jurisdictional claims in published maps and institutional affiliations.
the 14th Annual Post Graduate Symposium on the Convergence
of Telecommunications, Networking and Broadcasting
(PGNet2013) (2013) Neungsoo Park has a B.S. in
2. Jiang, W., Yang, Y.H.E., Prasanna, V.K.: Scalable multi-pipeline Electrical Engineering, from
architecture for high performance multi-pattern string matching. Yonsei University, Korea, 1991.
In: Proceedings of the 2010 IEEE International Symposium on He has an M.S. in Electrical
Parallel and Distributed Processing (IPDPS 2010) (2010) Engineering, from Yonsei
3. Rajesh, S., Prathima, S., Reddy, D.L.S.S.: Unusual pattern University, Korea, 1993. He has
detection in DNA database using KMP algorithm. Int. J. Comput. a Ph.D. in Electrical Engineer-
Appl. 1(22), 1–7 (2010) ing-Systems, from University of
4. Kalubandi, V.K.P., Varalakshmi, M.: Accelerated spam filtering Southern California, Los Ange-
with enhanced KMP algorithm on GPU. In: 2017 National les, CA, USA, 2002. He was a
Conference on Parallel Computing Technologies (PARCOMP- Research Staff in Samsung
TECH) (2017) Electronics, 2002–2003. Cur-
5. Al-Ssulami, A.M.: Hybrid string matching algorithm with a pivot. rently, he is a Professor in the
J. Inf. Sci. 41(1), 82–88 (2014) Department of Computer Sci-
6. Kim, J.W., Kim, E., Park, K.: Fast Matching method for DNA ence & Engineering, Konkuk
sequences. In: Combinatorics, Algorithms, Probabilistic and University, Korea, from 2003. His research interests include Com-
Experimental Methodologies (2007) puter Architecture, Embedded Systems, High Performance & Parallel
7. Sitaridi, E.A., Ross, K.A.: GPU-accelerated string matching for Computing, GPGPU, Big Data Computing, Multimedia Computing.
database applications. In: VLDB J (2016)
8. NVIDIA: Cuda C Programming Guide. [Link]
[Link]/compute/DevZone/docs/html/C/doc/CUDA_C_
Programming_Guide.pdf (2012)
9. Manavski, S.A.: Cuda compatible GPU as an efficient hardware.
No. November, pp. 24–27 (2007)
10. AMD: AMD accelerated parallel processing OpenCL program-
ming guide. AMD Document. [Link]
[Link]/wordpress/media/2013/07/AMD_Accelerated_Parallel_
Processing_OpenCL_Programming_Guide-[Link] (2013)

123
Cluster Computing

Soeun Park has a B.S. and an Myongji University, Korea, from 2004. His research interests include
M.S. in Computer Science & Computer Architecture, High Performance Computing, GPGPU,
Engineering, from Konkuk Optimizing Compiler.
University, Korea, 2016 and
2019, respectively.

Myungho Lee has a B.S. in

Computer Science & Statistics
from Seoul National University,
1986. He has an M.S. in Com-
puter Science from University
of Southern California, Los
Angeles, CA, USA, 1988. He
has a Ph.D. in Electrical Engi-
neering-Systems, from the
University of Southern Califor-
nia, Los Angeles, CA, USA,
1999. He was a Staff Engineer
in Sun Microsystems Inc, Sun-
nyvale, CA, USA, from
1999–2005. Currently, he is a
Professor in the Department of Computer Science & Engineering,

123