Parallelizing the Smith-Waterman Algorithm

using OpenSHMEM and MPI-3 One-Sided

Interfaces

Matthew Baker, Aaron Welch, Manjunath Gorentla Venkata

Oak Ridge National Laboratory

Abstract. The Smith-Waterman algorithm is used for determining the

similarity between two very long data streams. A popular application
of the Smith-Waterman algorithm is for sequence alignment in DNA
sequences. Like many computational algorithms, the Smith-Waterman
algorithm is constrained by the memory resources and the computa-
tional capacity of the system. As such, it can be accelerated and run at
larger scales by parallelizing the implementation, allowing the work to
be distributed to exploit HPC systems. A central part of the algorithm
is computing the similarity matrix which is the mechanism that evalu-
ates the quality of the matching sequences. This access pattern to the
matrix to compute the similarity is non-uniform; as such, it better suits
the Partioned Global Address Space (PGAS) programming model. In
this paper, we explore parallelizing the Smith-Waterman algorithm us-
ing the OpenSHMEM model and interfaces in OpenSHMEM 1.2 as well
as the one-sided communication interfaces in MPI-3 . Further, we also
explore the advantages of using non-blocking communication interfaces,
which are proposed as extensions for a future OpenSHMEM specification.
We evaluate the parallel implementation on Titan, a Cray XK7 system
at the Oak Ridge Leadership Computing Facility (OLCF). Our results
demonstrate good weak and strong scaling characteristics for both of the
OpenSHMEM and MPI-3 implementations.

Keywords: OpenSHMEM, MPI-3, Smith-Waterman

Notice of Copyright
This manuscript has been authored by UT-Battelle, LLC under Contract No.
DE-AC05-00OR22725 with the U.S. Department of Energy. The United States
Government retains and the publisher, by accepting the article for publication,
acknowledges that the United States Government retains a non-exclusive, paid-
up, irrevocable, world-wide license to publish or reproduce the published form
of this manuscript, or allow others to do so, for United States Government pur-
poses. The Department of Energy will provide public access to these results of
federally sponsored research in accordance with the DOE Public Access Plan
([Link]
2 Parallelizing the Smith-Waterman Algorithm with OpenSHMEM and MPI-3

1 Introduction
The sequence alignment is the central functionality of genetic analysis and many
other Bioinformatics applications. It infers the structural and functional rela-
tionship between the DNA/RNA or protein sequences, and finds similarity be-
tween the query and reference sequences. The sequence matching functionality,
essentially a pattern matching function, has wider applications besides Bioin-
formatics. One of the most popular algorithms for sequence matching is the
Smith-Waterman algorithm, which employs a dynamic programming approach
to find local alignment, which finds local regions with high levels of similarity.
Given the importance of this algorithm and its wider application, it is included
in many benchmark suites including Scalable Synthetic Compact Applications
1 (SSCA1) [1] and BioParallel [2], and is used in tools for analyzing next gener-
ation sequencing data such as SNPTools [3].
Like many scientific simulations and workloads, the Smith-Waterman algo-
rithm execution is constrained by the availability of resources. The algorithm
complexity is bounded by O(mn), where m and n are the lengths of the se-
quences. Given the importance of the algorithm and the asymptotic runtime of
the algorithm, there are various parallelization and optimization strategies to ad-
dress the resource problem. Researchers have parallelized the Smith-Waterman
algorithm by implementing the algorithm using parallel programming models
such as MPI and BSP models and use distributed memory systems for execution
[4][5]. For multicore systems, it has been optimized using hybrid programming
paradigms such as MPI+OpenMP [6]. With GPUs providing more performance
per watt, the GPU based distributed memory systems have become ubiquitous.
To take advantage of this computing architecture, researchers have developed a
parallelized implementation of the Smith-Waterman algorithm for many thread
systems such as GPUs [7].
A typical implementation of the Smith-Waterman algorithm involves gener-
ating a similarity matrix, tracing back the sequences for a suitable alignment,
and finding the optimal alignment. Parallelizing this algorithm results in com-
munication that is not uniform. Further, the pattern to find the optimal sequence
or tracing back the sequence is rather irregular, i.e. one cannot predict where
the beginning of an optimal sequence is. Using a two-sided model such as MPI
for parallelizing this algorithm means that one has to predict the sequence and
post the receives appropriately. If the prediction is wrong, the receives have to be
cancelled, which is awkward and can give unpredictable performance behavior.
To overcome this programming drawback, we explore the advantages of using
one-sided communication interfaces provided by OpenSHMEM [8] and MPI-3 [9]
for parallelizing the Smith-Waterman algorithm. In the one-sided communica-
tion model, the sender of data is aware of not just a source buffer address but
also the destination buffer address. As a consequence, only the sender of data
actively participates in the execution of basic communication operations, while
the receiving side stays passive. While implementing using these models, we
explore two approaches. First, using blocking one-sided communication inter-
faces, and second using non-blocking one-sided communication interfaces. The
Parallelizing the Smith-Waterman Algorithm with OpenSHMEM and MPI-3 3

non-blocking communication interfaces enables asynchronous progress of com-

munication, enabling the ability to overlap communication and computation.
The rest of the paper is organized as follows: section 2 provides background
details of the Smith-Waterman algorithm, OpenSHMEM and MPI-3 interfaces,
and extensions to OpenSHMEM interfaces. Section 3 provides details of the
OpenSHMEM and MPI-3 implementations of the Smith-Waterman algorithm.
Section 4 provides details of the evaluation of the implementation on Titan, a
Cray XK7 system. Finally, section 5 provides a summary of the paper’s findings.

2 Background

OpenSHMEM is an API for programming in the PGAS model, and provides

low level interfaces for communication and synchronization between the many
processing elements (PEs) in the system. OpenSHMEM is primarily focused on
one-sided communication, and one of its distinguishing factors is its memory
model. The OpenSHMEM memory model uses the concept of symmetric data
objects, which are variables that are allocated with the same type, size, and offset
on all PEs for easy access to and simple partitioning of memory. OpenSHMEM
includes a set of interfaces for Remote Memory Access (RMA) operations, atomic
memory operations, synchronization operations, collective communication oper-
ations, distributed lock operations, and operations for querying process and data
availability, and is available for C and Fortran.

2.1 Smith-Waterman Algorithm

The Smith-Waterman algorithm looks for sequence subsets that best match in
two large sequences. This algorithm will execute in O(mn) time where m is the
length of the main sequence while n is the length of the match sequence. We fix
the length of the main and match sequences to be the same, so the algorithm
effectively runs in O(n2 ) time.
The first step is to generate a similarity matrix. This similarity matrix decides
if a pair of codons, a triplet of adjacent DNA nucleotides that code for proteins,
are either exact matches, similar matches that are distinct but serve the same
function, or dissimilar matches. This can be generalized as a function sim(a, b)
that will return an exact match score, a similar score, or a no match score.
This algorithm works with a dynamic programming matrix A. This matrix
is formed for each element Aij by comparing element i in the main sequence
and j in the match sequence using the sim(a, b) function to derive a score that
is added to element A(i−1)(j−1) of the score matrix representing the score if
the current sequence were matched. A score is derived for a gap in the main
sequence by subtracting a gap penalty from element Ai(j−1) in the score matrix.
A score for a gap in the match sequence is also derived by taking element A(i−1)j
and subtracting the gap penalty. These scores, for the gap in main, the gap in
match, and a similarity value between main and a match, are all compared and
4 Parallelizing the Smith-Waterman Algorithm with OpenSHMEM and MPI-3

the highest score is the score used for element Aij in the matrix to a minimum
score of 0.
Additionally, our implementation used the Gotoh improvements [10], which
keeps a pair of additional arrays to map a changing gap penalty to penalize
small gaps over large gaps. This is done using an additional array where the
previous match against the main sequence is penalized with a gap start penalty,
while the previous gap penalty, represented by E(i−1) is penalized with a gap
extension value. Match has a similar array where previous gap penalties in the
match sequence are located in F(j−1) . These gap values are compared against the
matching value rather than a fixed gap penalty. This is done on the observation
that in nature a genome usually sees larger gaps rather than smaller gaps.

2.2 OpenSHMEM Non-blocking Extensions

The proposed OpenSHMEM non-blocking extensions include four core compo-

nents: data transfer operations (put/get), atomic operations, collectives, and
functions to test for completion. The new operations for non-blocking remote
memory access highlight one of the important differences with the proposed
API, particularly concerning put operations. Put operations have often been
considered as non-blocking already, since the calls return before remote com-
pletion is guaranteed. However, the key consideration concerns how completion
itself is defined, which can have many different levels ranging from virtually no
completion to remote completion. These differing definitions of completion se-
mantics include, in progressive order from early to late in the operation: when
local buffers can be reused, local completion, and finally remote completion.
The old put operations returned after local buffers could be reused, but did
not necessarily guarantee local completion, and guaranteeing remote completion
required the use of a quiet operation. The newly proposed non-blocking put in-
stead returns even earlier, before local buffers can safely be reused, and requires
an extra operation to either test or wait for the completion equivalent to the
older blocking form. This same change in semantics carries over to all the other
non-blocking operations, including get, atomic, and collective operations.
In order to properly take advantage of these new functions and test for com-
pletion, all non-blocking calls return an opaque request handle shmemx request handle t
that can later be used with either of two new functions to query completion sta-
tus. The first of these functions is shmemx wait req(), which simply blocks until
the non-blocking call is complete (as according to the appropriate blocking call’s
original semantics). The second of these is shmemx test req(), which checks and
immediately returns the current status of the operation so that further work
may be done in the event that it is not yet complete.
The current proposal makes no mention of how these non-blocking operations
interact with synchronization functions such as shmem fence() and shmem quiet().
Instead, the proposal explicitly says that a conformant OpenSHMEM implemen-
tation can progress non-blocking operations however it sees fit.
Parallelizing the Smith-Waterman Algorithm with OpenSHMEM and MPI-3 5

2.3 Cray Non-blocking Extensions

The Cray non-blocking extensions are incomplete with respect to the OpenSH-
MEM proposed extensions. In particular, rather then implement shmemx wait req()
and shmemx test req(), the Cray SHMEM library requires the use of shmem quiet()
to ensure the completion of non-blocking routines. This can produce unneces-
sary overhead if the algorithm in use does updates with shmem put() and does
prefetching with non-blocking shmem get() operations as in the case of this pa-
per’s implementation of the Smith-Waterman algorithm. The Cray API still has
request handles as parameters, but they are both of a different type and are
currently unused in the implementation, and may be passed in as NULL [11].

3 Smith-Waterman Implementation

Among all kernels in the SSCA1 benchmark suite [12], the Smith-Waterman
algorithm is the most difficult to parallelize and runs in O(n2 ) time. The only
input provided to the algorithm is a SCALE number. The size of the score matrix
is determined by SCALE, with each increment roughly doubling the number of
elements in the score matrix, effectively doubling the length of the computation.
Pseudo code is shown in listing 1.1.
To make the Smith-Waterman algorithm parallel, this implementation is set
up to be data parallel on the score matrix’s anti-diagonal. This is based on the
observation that a particular entry in the score matrix is only dependent on the
values at A(i−1)(j−1) , Ai(j−1) , and A(i−1)j as seen in figure 1. This will require 2n
iterations to complete, forming the outer loop started on line 10. The algorithm
as a whole is still O(n2 ) since in addition to the outer iterations there will be,
at most, n values to compute in the inner loop started on line 26.

Ai-1j-1 Ai-1j

Aij-1 Aij

Fig. 1. Computing a dynamic programming matrix entry using two immediate neigh-
bors at i − 1,j and i,j − 1 and the diagonal element, i − 1,j − 1.

In a naive implementation the benchmark will allocate a matrix of n2 ele-

ments and compute all of the values. The benchmark can compute values for
6 Parallelizing the Smith-Waterman Algorithm with OpenSHMEM and MPI-3

each Aij on an anti-diagonal independently. The data will only depend on the
previous two anti-diagonals. This naive implementation would fill in the entire
dynamic programming matrix A before scanning for potential good matches.
Additionally, there are two arrays for the current gap penalty. The gap
penalty is based on the previous iteration of the benchmark and whether the
penalty for continuing a previous gap is larger then the penalty for starting a
new gap. These arrays require an additional 2n amount of memory, since each
array must be n values long and an array must be made for the main sequence
and the match sequence.

Fig. 2. Computation of the Score Matrix: the black anti-diagonal is calculated using
two light shaded anti-diagonals

A key observation is that each anti-diagonal is only dependent on the previous

two anti-diagonals; the previous ones are unneeded to compute a particular Aij .
This can be seen in figure 2. This means that the score matrix can be reduced to
a three row matrix of n elements with each row representing an anti-diagonal.
The memory requirement for the diagonal can thus be reduced from n2 to 3n
and caching behavior is improved because writes are done in adjacent localities
independent of the reads. as can be seen in figure 3. It is important to note that
each row in figure 3 corresponds to the same colored row in figure 3.
Discarding previous diagonals means that you cannot wait until the end to
scan for good matches. During the compute portion a score is evaluated based
on a minimum score, the adjacency of other stored ends, and if the next match
will produce a better score to decide if it should store a pair of well scoring end
points.
Parallelizing the Smith-Waterman Algorithm with OpenSHMEM and MPI-3 7

In total, with all of the gap arrays, the score matrix, and sequence data,
the Smith-Waterman algorithm will require, at most, 5j + 2k space in memory,
where j is the size of an entry in the score matrix and k is the size of a codon.

Fig. 3. In this implementation of the Smith-Waterman algorithm, the entire score

matrix is transformed into three rows. Each row of the same color is equal to the same
color anti-diagonal in figure 2.

Using the anti-diagonals as matrix rows, the indices for the elements to com-
pare are no longer the same as described in the basic Smith-Waterman algorithm.
The main gap is still at A(i−1)j , but now the match gap is at A(i−1)(j−1) while
the match is at index A(i−2)(j−1) . Figure 4 shows the new dependency layout,
where the colored arrows as the same as in figure 1
This implementation allows for dense memory access and use, but requires
inline analysis of the score results. Either each row is scanned for the highest score
to find only the best match, or a list of scores must be retained for comparison
if multiple sub sequences are to be analyzed.

Ai-2j-1

Ai-1j-1 Ai-1j

Aij

Fig. 4. The score matrix after transformation and the entries involved in computing a
score matrix entry
8 Parallelizing the Smith-Waterman Algorithm with OpenSHMEM and MPI-3

Once the gap arrays and the score matrix are arranged in a loop independent
way, distributing the elements across PEs becomes straightforward. Each PE
gets an equal number of codons and since the gap and score matrices are based
on codon length, these matrices can be distributed in the same manner. This
locality will also minimize distributed memory access. This layout is illustrated
in figure 5.

PE 0 PE 1
main seq
match seq

main gap

match gap

score matrix

Fig. 5. Symmetric Heap with a ten codon main sequence and ten codon match sequence

The end result of these changes is that the benchmark runs in 2n iterations
that can be parallelized within each iteration. This is most helpful in the middle
iterations where there can be as many as n elements to be processed.
 Parallelizing the Smith-Waterman Algorithm with OpenSHMEM and MPI-3 9

1 local_align ( main_codon_seq , ma tc h _c od on _ se q ) {
2 /* A is the score Matrix */
3 A [ len ( main_codon ) ][ len ( match_codon ) ];
4 /* E is the main gap matrix */
5 E [ len ( main_codon ) ][ len ( match_codon ) ];
6 /* F is the match gap matrix */
7 F [ len ( main_codon ) ][ len ( match_codon ) ];

9 /* outer loop */
10 for ( outer =0; outer < 2 * length ( main _codon_ seq ) ) {
11 wait_for_puts () ;
12 barrier_all () ;
13 start = c o m p u t e _ l o c a l _ s t a r t _ i n d e x ( outer ) ;
14 end = c o m p u t e _ l o c a l _ e n d _ i n d e x ( outer ) ;

16 /* prestage non - blocking operations */

17 if ( n o n _ b l o c k i n g _ e n a b l e d ) {
18 n b _ p r e v i o u s _ m a t c h = get_nb (A , i -1 , j -1)
19 nb_main_codon = get_nb ( main_codon_seq , i ) ;
20 nb_m atch_cod on = get_nb ( match_codon_seq , j ) ;
21 nb_gap_main = get_nb (E ,i -1 , j ) ;
22 nb_gap_match = get_nb (F ,i ,j -1) ;
23 }

25 /* inner loop */
26 for ( inner = start ; inner < end ) {
27 i = c o m p u t e _ m a i n _ i n d e x ( outer , inner ) ;
28 j = c o m p u t e _ m a t c h _ i n d e x ( outer , inner ) ;

30 if ( n o n _ b l o c k i n g _ e n a b l e d ) { /* non - blocking gets */

31 nb_i = c o m p u t e _ n e x t _ m a i n _ i n d e x ( outer , inner ) ;
32 nb_j = c o m p u t e _ n e x t _ m a t c h _ i n d e x ( outer , inner ) ;

34 w a i t _ f o r _ p r e v i o u s _ g e t s () ;
35 previ ous_mat ch = n b _ p r e v i o u s _ m a t c h ;
36 main_codon = nb_main_codon ;
37 match_codon = n b_match _codon ;
38 gap_main = nb_gap_main ;
39 gap_match = nb_gap_match ;

41 n b _ p r e v i o u s _ m a t ch = get_nb (A , nb_i -1 , nb_j -1) ;

42 nb_main_codon = get_nb ( main_codon_seq , nb_i ) ;
43 nb_ma tch_cod on = get_nb ( match_codon_seq , nb_j ) ;
44 nb_gap_main = get_nb (E , nb_i -1 , nb_j ) ;
45 nb_gap_match = get_nb (F , nb_i , nb_j -1) ;
46 } else { /* blocking gets */
47 previ ous_mat ch = get (A , i -1 , j -1) ;
48 main_codon = get ( main_codon_seq , i ) ;
49 match_codon = get ( match_codon_seq , j ) ;
50 gap_main = get (E ,i -1 , j ) ;
51 gap_match = get (F ,i ,j -1) ;
52 }

54 new_match = sim ( main , codon ) ;

55 new_score = max ( new_match , gap_main , gap_match , 0) ;

57 if ( is_score_good ( new_score ) ) {
58 add_new_pair ( new_score , i , j ) ;
59 }

61 new_gap_score = new_match - n ew _ ga p_ p en al ty ;
62 e xt en d_ m ai n_ g ap = gap_main - e x t e n d _ g a p _ p e n a l t y ;
63 e x t e n d _ m a t c h _ g a p = gap_match - e x t e n d _ g a p _ p e n a l t y ;

65 put (A ,i ,j , new_score ) ;
66 put (E ,i ,j , max ( new_gap_score , e xt en d _m ai n_ g ap ) ;
67 put (F ,i ,j , max ( new_gap_score , e x t e n d _ m a t c h _ g a p ) ;
68 }
10 Parallelizing the Smith-Waterman Algorithm with OpenSHMEM and MPI-3

69 }
70 }

Listing 1.1. Pseudo code for the implementation of the main loops for the Smith-
Waterman algorithm

3.1 Smith-Waterman Implementation Using Blocking and

Non-blocking OpenSHMEM Operations

In the OpenSHMEM version of the Smith-Waterman algorithm, the sequence of

length n is split up across the p PEs, where each PE gets n/p codons. Each PE
will fill out the matrix A for each element it has in the main sequence, ensuring
that access for the score matrix, the main gap matrix, and main sequence are all
local, leaving remote access for the match sequence and the match gap array.
An additional optimization to the OpenSHMEM version of Smith-Waterman
algorithm is the option for prefetching data. On a particular PE it is easy to
compute which codons will be needed next and which element of the score matrix
will be needed next. Therefore, it is easy to issue the fetches for the next loop
iteration at the beginning of the current inner loop using the code path at line
30 in listing 1.1.
The communications in the inner loop are completed by shmem quiet(). At
the very end of the inner loop, at line 65, the algorithm will issue blocking put
operations to write the new results for scores and gaps. The algorithm does not
need these values until the next iteration of the outermost loop. This means that
each inner loop will wait on the put operations as well as the non-blocking get
operations on line 34.
In the future, we will extend the implementation to include non-blocking bulk
get operations to process indices that are expected to be local to the calling PE.
This may help get additional overlap by reducing the network overhead. It should
be easy to compute which indices will be needed on the next iteration and do a
non-blocking bulk get on the entire index range.

3.2 Smith-Waterman Implementation Using MPI-3 One-sided

Operations

In the Smith-Waterman version that uses MPI-3 one-sided interfaces, the se-
quence length is split evenly across the Message Passing Interface (MPI) pro-
cesses. A single block of memory on each process was allocated to store all the
necessary information, and it was associated with a window. The window was
synchronized with the MPI Win lock all() and MPI Win unlock all() interfaces.
For communication, we used one-sided put and get interfaces, and we ex-
plored both blocking and non-blocking communication operations. The commu-
nication interfaces were mostly used for retrieving and setting data for the parts
of the sequence that were located on other ranks. This was done using two ap-
proaches, with one version that simply retreived remote data as it was needed,
Parallelizing the Smith-Waterman Algorithm with OpenSHMEM and MPI-3 11

and another that was optimized to prefetch data for future iterations by ex-
ploiting non-blocking operations. In this way, the two versions can be directly
compared to the blocking and non-blocking OpenSHMEM versions, respectively.
Since these operations are always non-blocking in nature (to the extent that lo-
cal buffers can’t be reused), MPI Rget() was used in place of blocking routines,
so that the associated request handle could be waited on for completion before
the results are needed without having to flush out all other pending operations
as well. When prefetching future data in the optimized version, MPI Get() was
simply used instead, and a flush was performed on a future iteration before the
results were needed.
The performance of both MPI-3 implementations was worse than the Open-
SHMEM implementation as you can observe from Figure 6. When trying to
improve upon them, all the MPI Rget() calls were replaced with MPI Get(),
and instead of waiting on a request handle, additional flushes had to be issued
for each time the result was about to be used. This inevitably caused a lot of
unnecessary flushing and noticeably negated the potential improvement for the
“non-blocking” prefetch version since those operations still had to be flushed
out early due to future “blocking” calls. However, this actually resulted in a
significant performance boost, though it was still noticeably slower than the
OpenSHMEM runs, which may be attributed to the excessive flushing. Why
the use of MPI Rget() resulted in such a large drop in performance is unclear,
though may simply be an implementation quirk due to the relatively young age
of the new one-sided API.

4 Evaluation
This section presents the evaluation and performance characteristics of the Smith-
Waterman OpenSHMEM and MPI-3 implementations.

4.1 Testbed
The experiments were conducted on Titan, housed at OLCF. It contains 18,688
compute nodes, each of which includes one 16-core 2.2GHz AMD Opteron 6274
(Interlagos) processor with 32 GB of RAM and an NVIDIA Kepler GPU with 6
GB of DDR5 memory. It uses a 3D torus network built from Gemini application-
specific integrated circuits (ASICs).
For our experiments, the OpenSHMEM implementation of the benchmark
uses Cray SHMEM, and the MPI-3 implementation uses Cray MPI.

4.2 Performance of Strongly Scaling Smith-Waterman

Implementation - OpenSHMEM and MPI-3
Figure 6 shows the completion time in seconds for the OpenSHMEM imple-
mentation and MPI-3 while keeping the matrix size sequence size constant at
sequence size 65536 for a score matrix size 655362 (SCALE=32), and increasing
12 Parallelizing the Smith-Waterman Algorithm with OpenSHMEM and MPI-3

10000
MPI-3 blocking
MPI-3 non-blocking
OSH blocking
OSH non-blocking
(log) Seconds

1000

100
16 nodes 32 nodes 64 nodes 128 nodes

Fig. 6. The completion times of the OpenSHMEM and MPI-3 Smith-Waterman im-
plementations, while the problem size is kept constant and the number of nodes is
increased

the number of the nodes. For this experiment, the problem was launched with one
PE per node. The benchmark was run for two iterations and we are presenting
the average runtime. The green bar is the completion time of the OpenSHMEM
implementation when using blocking put and get interfaces, while the yellow
bar is the completion time of the OpenSHMEM implementation when using
non-blocking get interfaces. The red bar is the completion time of the MPI-3
implementation when using blocking put and get interfaces, while the blue bar
is the completion time of the MPI-3 implementation when using non-blocking
get interfaces.

OpenSHMEM Strong Scaling: From figure 6, we can observe that the im-
plementation has good strong scaling, i.e. as we increase the resources (nodes) to
the solve the problem, the completion time decreases. For 16 PEs and nodes, the
completion time is 2877.5 seconds, and for 128 PEs and nodes, the completion
time decreases to 770 seconds.
The results also show that the Smith-Waterman algorithm implementation
with non-blocking operations performs better than the implementation with
blocking operations. It is 34% better when using 16 PEs, and 41% better when
using 128 PEs. This makes sense as we can achieve an overlap of communication
and computation when using non-blocking operations. The innermost loop can
Parallelizing the Smith-Waterman Algorithm with OpenSHMEM and MPI-3 13

issue a non-blocking get at the top of its loop for the next iteration. The loop
then waits for the completion of the non-blocking get before starting the next
iteration of the inner loop.

Performance Comparision of MPI-3 and OpenSHMEM Implemen-

tations: Figure 6 clearly shows that the OpenSHMEM implementation runs
considerably faster than the MPI-3 implementation. At 128 nodes the OpenSH-
MEM implementation completes in 546.5 seconds while the MPI-3 implemen-
tation completes in 1220 seconds, a 123% improvement.
At 16 nodes the MPI-3 implementation completes in 5318 seconds while the
OpenSHMEM implementation completes in 2142 seconds, a 148% improvement.
At 64 nodes the OpenSHMEM implementation was 129% faster and at 32 nodes
it was 138% faster then the MPI-3 implementation. In all cases the OpenSHMEM
implementation was over 100% faster.
There is an interesting performance anomaly at 64 nodes, where going from
32 nodes to 64 nodes in the blocking implementations of both MPI-3 and Open-
SHMEM did not get the expected speed ups. There was only a 22% speed up
instead of the 67% speed up seen in the non-blocking implementations and the
61% speed up seen going from 16 nodes to 32 nodes in the blocking implemen-
tation. This anomaly seems to be Titan specific, since it is not reproducible on
other test systems at similar scales.

4.3 Performance of Weakly Scaling Smith-Waterman -

OpenSHMEM Implementation
Figure 7 shows the completion time in seconds for OpenSHMEM , while the
problem is scaled logarithmically and the number of nodes is doubled. For 16
nodes, the completion time is 263 seconds, and the problem size is 29 in the
non-blocking version.
The OpenSHMEM implementation using non-blocking interfaces performs
better than the implementation using blocking interfaces. This is similar to the
results that we observed for the strong scaling case. For 128 nodes, the non-
blocking version performs 39% better than the blocking version.

5 Conclusion
This paper presented two approaches to parallelize the Smith-Waterman al-
gorithm for distributed memory systems using one-sided semantics provided by
OpenSHMEM and MPI-3 . The results show the advantages of parallelization for
both strong and weak scaling experiments. Our experience and results show that
though both programming models provide interfaces and semantics to implement
the algorithm, the performance characteristics of the OpenSHMEM implementa-
tion were better than the MPI-3 implementation. Due to the preliminary nature
of the comparison analysis, these performance advantages may be more of a con-
sequence of implementation rather than semantics. The code is available on the
14 Parallelizing the Smith-Waterman Algorithm with OpenSHMEM and MPI-3

1000
blocking
non-blocking
(Log) Seconds

100
16 nodes 32 nodes 64 nodes 128 nodes
SCALE 29 SCALE 30 SCALE 31 SCALE 32
Fig. 7. The completion times of the OpenSHMEM and MPI-3 Smith-Waterman im-
plementations, while the problem size and the number of nodes is increased

web site gitlab, and we plan to open source the implementation and make it
available publicly.

Acknowledgments. This work is supported by the United States Department

of Defense and used the resources of the Extreme Scale Systems Center (ESSC)
located at the Oak Ridge National Laboratory (ORNL).

References

1. Smith, T.F., Waterman, M.S.: Identification of common molecular subsequences.

Journal of molecular biology 147 (1981) 195–197
2. Jaleel, A., Mattina, M., Jacob, B.: Last level cache (llc) performance of data
mining workloads on a cmp - a case study of parallel bioinformatics workloads. 2014
IEEE 20th International Symposium on High Performance Computer Architecture
(HPCA) 0 (2006) 88–98
3. Wang, Y., Lu, J., Yu, J., Gibbs, R.A., Yu, F.: An integrative variant analy-
sis pipeline for accurate genotype/haplotype inference in population NGS data.
Genome Research 23 (2013) 833–842
4. El-Saghir, Z., Kelash, H., Elnazly, S., Faheem, H.: Parallel implementation of
smith-waterman algorithm using mpi, openmp and hybrid model. International
Journal of Innovative Technology and Exploring Engineering 4 (2014)
Parallelizing the Smith-Waterman Algorithm with OpenSHMEM and MPI-3 15

5. Hamidouche, K., Mendonca, F., Falcou, J., de Melo, A., Etiemble, D.: Parallel
smith-waterman comparison on multicore and manycore computing platforms with
bsp++. International Journal of Parallel Programming 41 (2013) 111–136
6. Noorian, M., Pooshfam, H., Noorian, Z., Abdullah, R.: Performance enhancement
of smith-waterman algorithm using hybrid model: Comparing the mpi and hybrid
programming paradigm on smp clusters. In: Systems, Man and Cybernetics, 2009.
SMC 2009. IEEE International Conference on. (2009) 492–497
7. Khajeh-Saeed, A., Poole, S., Perot, J.B.: Acceleration of the smith–waterman
algorithm using single and multiple graphics processors. Journal of Computational
Physics 229 (2010) 4247–4258
8. OpenSHMEM Org.: OpenSHMEM Specification. [Link] (2015)
9. The MPI Forum: MPI: A Message Passing Interface. . Technical report (Version
3.0., 2012)
10. Gotoh, O.: An improved algorithm for matching biological sequences. Journal of
molecular biology 162 (1982) 705–708
11. ten Bruggencate, M.: Cray shmem update (2014) Presentation regarding extensions
to OpenSHMEM by Cray [Accessed: 2015 06 23].
12. Bader, D., Madduri, K., Gilbert, J., Shah, V., Kepner, J., Meuse, T., Krishna-
murthy, A.: Designing scalable synthetic compact applications for benchmarking
high productivity computing systems. Cyberinfrastructure Technology Watch 2
(2006) 1–10