BACKGROUND
sequence alignment is a popular bioinformatics application that determines the degree of similarity between nucleotide or amino acid sequences which is assumed to have same ancestral relationships.
the optimal local alignment of a pair of sequences can be computed by the dynamic programming  based smith-waterman  algorithm <cit> .
however, this approach is expensive in terms of time and memory cost.
furthermore, the exponential growth of available biological data <cit>  means that the computational power needed is growing exponentially as well.
the recent emergence of accelerator technologies such as fpgas, gpus and specialized processors have made it possible to achieve an excellent improvement in execution time for many bioinformatics applications, compared to current general-purpose platforms.
however, special-purpose hardware implementations such as fpgas  <cit>  tend to be very expensive and hard-to-program.
hence, they are not suitable for many users.
recent usage of easily accessible accelerator technologies to improve the search time of the sw algorithm include intel sse <dig> <cit> , gpu <cit>  and cuda <cit> .
farrar <cit>  exploits the sse <dig> simd multimedia extension of general-purpose cpus.
his implementation utilizes vector registers, which are parallel to the query sequence and are accessed in a striped pattern.
similar to the implementation by rognes  <cit> , a query profile is calculated only once for each database search.
however, farrar's implementation allows moving the conditional calculation of the f-matrix outside the inner loop.
therefore, this implementation achieves a speed up of factor 2– <dig> over the previous simd implementations by wozniak <cit>  and rognes <cit> .
liu et al.
<cit>  first reported the implementation of the smith-waterman algorithm on graphics hardware.
the sw algorithm is implemented using the streaming architecture of gpus by reformulating it in terms of computer graphics primitives.
the implementation relies on opengl, in which a conversion of the problem to the graphical domain is needed, as well as a reverse procedure to convert back the results.
although, it achieves a high efficiency, programming in opengl requires specialized skills.
therefore, manavski <cit>  re-implemented the sw algorithm on a gpu with the recently released c-based cuda programming environment.
the implementation performs from  <dig> to  <dig> times faster than any other previous attempt available on commodity hardware.
in this paper, we demonstrate how the playstation®  <dig> , a commodity hardware powered by the cell broadband engine <cit> , can be used as a low cost computational platform to accelerate the smith-waterman algorithm.
our implementation is able to outperform both the striped method on an intel core  <dig> duo as well as the cuda-based gpu implementation on a geforce  <dig> gtx.
the smith-waterman algorithm
the smith-waterman algorithm is used to determine the optimal local alignment between two nucleotide or protein sequences.
the algorithm compares two sequences by computing the similarity score by means of dynamic programming .
two elementary operations are used: substitution and insertion/deletion .
the original algorithm was proposed by smith and waterman <cit>  with a complexity of o and was improved by gotoh <cit>  to run at o.
consider two strings s <dig> and s <dig> with length m and n, respectively.
the smith-waterman algorithm computes the similarity value m of two sequences ending at position i and j of the two sequences s <dig> and s <dig>  respectively.
for affine gap penalties, i.e.
α ≠ β, the computation of m, for  <dig> ≤ i ≤ m,  <dig> ≤ j ≤ n, is given in the following equations 1–3:
m = max{m + sbt, s <dig>  e, f, 0},
e = max{m - α, e - β},
f = max{m - α, f - β},
where sbt is a character substitution cost table, α is the cost of the initial gap; β is the cost of the following gaps.
for linear gap penalties, i.e.
α = β, the above recurrence relations can be simplified as shown in equations 4:
m = max{m + sbt, s <dig>  m - α, m - α}
initialization values are given as the following: for  <dig> ≤ i ≤ m,  <dig> ≤ j ≤ n, m = m = e = f =  <dig>  each position of the matrix m is a similarity value.
the two segments of s <dig> and s <dig> producing this value can be determined by a trace-back procedure.
cell broadband engine architecture
the cell broadband engine <cit>   is a recently introduced single-chip heterogeneous multi-core processor, which is developed by sony, toshiba and ibm.
the cell be offers a unique assembly of thread-level and data-level parallelization options.
it is operating at the upper range of existing processor frequencies  and is projected to run at more than  <dig> ghz in the near future.
several examples of bioinformatics applications that has been ported to the cell be architecture include folding@home <cit> , fasta <cit> , clustalw <cit>  and raxml <cit> .
the cell be combines an ibm powerpc processor element  and eight synergistic processor elements  <cit> .
an integrated high-bandwidth bus called the element interconnect bus  connects the processors and their ports to external memory and i/o devices.
the block diagram of the cell be architecture is shown in figure  <dig>
the ppe is a 64-bit power architecture core and contains a 64-bit general purpose register set , a 64-bit floating point register set , and a 128-bit altivec register set.
it is fully compliant with the 64-bit power architecture specification and can run 32-bit and 64-bit operating systems and applications.
each spe is able to run its own individual application programs.
each spe consists of a processor designed for streaming workloads, a local memory, and a globally coherent direct memory access  engine.
the eib is a 4-ring structure, and can transmit  <dig> bytes per cycle, for a bandwidth of  <dig>  gigabytes/second.
the eib can support more than  <dig> outstanding dma requests.
the most distinguishing feature of the cell be lies within the variety of the processors it has, i.e.
the ppe and the spes.
heterogenous multi-core systems can lead to decreased performance if both the operating system and application are unaware of the heterogeneity.
the ppe is designed to run the operating system and, in many cases, the top-level control thread of an application, while the spes is optimized for compute intensive applications, hence, providing the bulk of the application performance.
the spe can access ram through direct memory access  requests.
the dma transfers are handled by the memory flow controller .
the mfc provides the interface, by means of the eib, between the local storage of the spe and main memory.
the mfc supports dma transfers as well as mailbox and signal-notification messaging between the spe and the ppe and other devices.
data transferred between local storage and main memory must be 128-bit aligned.
the size of each dma transfer can be at most  <dig> kb.
dma-lists can be used for transferring large amounts of data .
a list can have up to  <dig>  dma requests, each for up to  <dig> kb.
the ps <dig> uses the cell broadband engine as its cpu, hence making it possible for users to create a high-powered computing environment for a fraction of the cost of a cell blade server.
the ps <dig> utilizes seven of the eight spes, in which the eighth spe is disabled to improve chip yields, i.e.
chips do not have to be discarded if one of the spes is defective.
only six of the seven spes are accessible to developers as one is reserved by the operating system.
the power requirement for the ps <dig> is  <dig> v ac,  <dig> hz and the power consumption approximately  <dig> w. generally available ps3's can be used for scientific high performance computing through installation of linux .
programs can be developed the using freely available c-based cell be sdk  <cit> .
at the time of this writing, the retail price of the playstation®  <dig> is us$  <dig> for  <dig> gb and us$ <dig> for  <dig> gb, while the retail price of the nvidia geforce 8800gtx card is us$ <dig>  and a dell optiplex  <dig> with intel core  <dig> duo  <dig>  ghz processor is us$ <dig>  a qs <dig> blade server with two cell be chips has a retail price of us$ <dig> .
thus, the ps <dig> offers a good alternative to other accelerator technologies.
methods
cell be mapping
our sequence alignment implementation  uses affine gap penalties and utilizes the 128-bit wide simd vector registers of the spes for optimization.
the vectorization strategy is based on a column-based approach <cit> .
it also employs a static load balancing strategy, which means that the work load is known at the start and distributed equally across the spes.
the code is written in c together with the cell be simd multimedia extension language intrinsics and spu intrinsics for portability.
dma transfers and mailbox functions are used for communication purposes.
a list of spu low-level specific and generic intrinsics used in our vectorized implementation, divided into categories, is shown in table  <dig>  constant formation intrinsics, arithmetic intrinsics, compare, branch and halt intrinsics, bits and mask intrinsics, logical intrinsics, shift and rotate intrinsics and scalar intrinsics have been employed to access hardware features, which are not easily accessible from a high level language in order to obtain the best performance from the cell be.
spu_and
spu_nor
spu_rlmaskqwbyte
list of spu low-level specific and generic intrinsics used in the implementation are listed and sorted into categories, as shown below.
more details about the syntax and semantics of these intrinsics can be found in  <cit> .
due to the fact that the spes only have  <dig> kbytes of local memory, which have to store program code and data, memory allocation is crucial for the spe.
the current longest sequence in the swiss-prot database is  <dig>  amino acids .
in order to accommodate for longer protein sequence in the future, we allocate dynamic memory for the database sequences of up to  <dig>  amino acids per sequence.
due to these limitations, the maximum query sequence length allowed for our implementation is limited to  <dig>
query profile
in order to calculate m in the sw dp matrix, the value sbt needs to be added to m. to avoid performing this table lookup for each element in the dp matrix, rognes <cit>  and farrar  <cit>  suggested calculating a query profile parallel to the query sequence beforehand.
assuming that s <dig>  s <dig> ∈ Σ* and s <dig> is the query sequence, the query profile is defined as a set p = {px | x∈Σ} consisting of |Σ| numerical strings of length l <dig> each, where l <dig> = |s1|.
each string px ∈ p consists of all substitution table values that are needed to compute a complete column j of the dp matrix for which s <dig> = x. pre-computing the query profile greatly reduces the amount of substitution table lookup in the sw dp matrix computation, since |Σ| is usually much smaller than |s2|.
the query profile can be calculated in a straightforward sequential layout  <cit>  or in a more complex striped layout  <cit> , as shown in figure  <dig>  the values in the query profile for sequential and striped layout are defined in equation  <dig> and  <dig>  respectively:
px = sbt, for all  <dig> ≤ i ≤ l <dig>
px=sbt%p)t)+⌊i−1p⌋+1],x)for all 1≤i≤l <dig>
where p is the number of segments and t is the segment length.
in the striped layout, p corresponds to the number of elements that can be processed in a simd vector register .
the length of each segment, t is defined in equation  <dig>
t = ⌈/p⌉
both approaches allow efficient vectorization on sse2-compatible processors using the corresponding simd instruction set.
using the pre-calculated query profile, the computation of the dp matrix can be performed in column-wise order.
due to the simplified dependency relationship and parallel loading of the vector scores from memory, fast dp matrix calculations can be achieved.
the advantage of the striped layout compared to the sequential layout is that data dependencies between vector registers are moved outside the inner loop.
for instance, when calculating vectors for the dp matrices h or f with the sequential layout, the last element in the previous vector has to be moved to the first element in the current vector.
when using the striped query layout, this needs to be done just once in the outer loop when processing the next subject sequence character.
saturation arithmetic
the inner loop of the algorithm requires saturation arithmetic, namely saturated additions and saturated subtractions.
the cell be lacks the saturation arithmetic support, leaving the tasks to be handled by software instead of direct hardware support.
in order to tackle this problem, we introduced two new functions, namely spu_adds and spu_subs to handle saturated additions and saturated subtractions, respectively.
RESULTS
in this section, we analyze the performance of our parallel algorithm for various query sequence lengths using sequences from swiss-prot database.
searches for  <dig> query sequences with various lengths between  <dig> to  <dig> amino acids were performed.
the accession numbers of the query sequences used are o <dig>  p <dig>  p <dig>  p <dig>  p <dig>  p <dig>  p <dig>  q8zgb <dig>  p <dig>  p <dig>  p <dig>  p <dig>  p <dig>  p <dig>  p <dig>  p <dig>  q <dig> and o <dig>  respectively.
all queries were run against swiss-prot release  <dig>  comprising  <dig> , <dig> amino acids in  <dig>  sequence entries.
the gap-open penalty used was  <dig> and the gap-extension penalty used was  <dig>  the scoring matrix used in the testing was blosum <dig>  all experiments were carried out on a standalone playstation®  <dig> machine, with yellow dog linux  <dig>  operating system and the cell software development kit   <dig> .
the performance statistics measured are then converted to the following measurements, i.e.
computational time and mega cell updates per second .
given a query sequence of size q and a database of size d, the mcups rating  is calculated by equation  <dig>
|q|×|d|×106t
where
|q| = size of query sequence in amino acids
|d| = size of database sequences in amino acids
t = run time
performance evaluation of our implementation, in terms of computational time and mcups.
all queries were run against swiss-prot release  <dig>  comprising  <dig> , <dig> amino acids in  <dig>  sequence entries.
eighteen query sequences of length  <dig> to  <dig> amino acids were used.
the gap-open penalty used is  <dig> and the gap-extension penalty used was  <dig>  the blosum <dig> scoring matrix was used.
we have compared the performance of our cbesw implementation with other publicly available implementations of sw-based protein database scanning, namely ssearch <cit> , striped smith-waterman <cit>  and cuda <cit> .
the query sequences, as well as their respective swiss prot accession numbers, used in the different performance comparisons are shown in table  <dig>
list of query sequences, as well as their respective accession number, used in different performance comparisons with other publicly available implementations of sw-based protein database scanning, namely ssearch, striped smith-waterman and cuda.
ssearch <cit>  is a sw implementation which is part of the fasta <cit>  package.
the ssearch performance is benchmarked on an intel core  <dig> duo  <dig>  ghz cpu with  <dig> gb ram.
both execution cores were used in the experiment.
as shown in figure  <dig>  for a query sequence of length  <dig> , ssearch achieves a performance of  <dig>  mcups.
thus, our implementation is over  <dig> times faster.
the performance comparison between the ps <dig> implementation and cuda-sw on one nvidia geforce 8800gtx is shown in figure  <dig>  the cuda implementation experiment was conducted with a geforce 8800gtx  <dig> mb installed in a pc with a dual-core amd opteron  <dig>  <dig>  ghz cpu,  <dig> gb ram running fedora  <dig>  the substitution matrix used is blosum <dig>  as can be seen from the figure, our implementation achieves a better mcups performance.
the ps <dig> peak performance is  <dig> times faster compared to the peak performance cuda implementation on a single nvidia geforce 8800gtx.
CONCLUSIONS
in this paper, we have demonstrated that the playstation®  <dig>  powered by the cell broadband engine, can be effectively used to accelerate a biological sequence alignment application.
in order to derive an efficient mapping onto this type of heterogeneous multi-core architecture, we have utilized simd vectorization and parallel data partitioning and communication techniques.
our implementation achieves a peak performance of  <dig> .
<dig> mcups for a query sequence of length  <dig>  hence, the peak performance of our implementation is  <dig>  times and  <dig>  times faster than ssearch and striped sw, on an intel core  <dig> duo  <dig>  ghz.
the ps <dig> peak performance is also  <dig> times faster compared to the peak performance cuda implementation on a single nvidia geforce 8800gtx.
the very rapid growth of biological sequence databases demands even more powerful high-performance solutions in the near future.
hence, our results are especially encouraging since high performance computer architectures are developing towards heterogeneous multi-core systems.
due to the  <dig> kb memory limitation of the spe local store, the maximum query sequence length in our current implementation is  <dig>  one of the limiting factors is that the size of the query profile grows with the length of the query sequence.
part of our future work is therefore to tackle this limitation.
a promising approach is to align subject sequences against separate chunks of the query profile.
the complete query profile only needs to be stored once in the main memory instead of the local store of the spe.
this frees up more memory space for the spes and thus allows longer query sequences.
given a query sequence of length l, the query profile can be divided into n chunks in which each chunks contains a query profile of size l/n.
the respective spes can then align a part of the chunk of the query profile it has and get the next chunk from outside memory via concurrent dma transfer.
availability and requirements
▪ project name: cbesw
▪ project homepage:
▪ operating system: only tested with playstation®  <dig> with yellow dog linux  <dig>
▪ programming language: c
▪ other requirements: cell sdk  <dig>
▪ license: none
▪ any restrictions to use by non-academics: none
abbreviations
cpu: central processing unit; cuda: compute unified device architecture; cups: cells updates per seconds; dp: dynamic programming; dma: direct memory access; fpga: field-programmable gate arrays; gpu: graphics processing unit; mfc: memory flow controller; ppe: powerpc processor element; simd: single instructions multiple data; spe: synergetic processor element; sse: streaming simd extensions; sw: smith-waterman
competing interests
the authors declare that they have no competing interests.
authors' contributions
aw conceived the study, participated in its design, implementation and coordination, performed benchmark test cases and drafted the manuscript.
tnh participated in the design and implementation of the source code.
kck participated in the creation of the manuscript.
bs conceived the study, participated in the analysis and interpretation of data.
all authors have read and approve the final manuscript.
supplementary material
additional file 1
the file is the compressed source code for the cbesw.
click here for file
additional file 2
the file is the executable file for cbesw.
the command to run it is ./cbesw.
click here for file
additional file 3
readme file for cbesw file.
click here for file
acknowledgements
aw is supported by the phd program of nanyang technological university.

 sequence alignment is a popular bioinformatics application that determines the degree of similarity between nucleotide or amino acid sequences which is assumed to have same ancestral relationships. the optimal local alignment of a pair of sequences can be computed by the dynamic programming based smith-waterman algorithm. however, this approach is expensive in terms of time and memory cost. furthermore, the exponential growth of available biological data means that the computational power needed is growing exponentially as well. the recent emergence of accelerator technologies such as fpgas, gpus and specialized processors have made it possible to achieve an excellent improvement in execution time for many bioinformatics applications, compared to current general-purpose platforms. however, special-purpose hardware implementations such as fpgas tend to be very expensive and hard-to-program. hence, they are not suitable for many users. recent usage of easily accessible accelerator technologies to improve the search time of the sw algorithm include intel sse, gpu and cuda. farrar exploits the sse simd multimedia extension of general-purpose cpus. his implementation utilizes vector registers, which are parallel to the query sequence and are accessed in a striped pattern. similar to the implementation by rognes, a query profile is calculated only once for each database search. however, farrar's implementation allows moving the conditional calculation of the f-matrix outside the inner loop. therefore, this implementation achieves a speed up of factor 2– over the previous simd implementations by wozniak and rognes. liu et al. first reported the implementation of the smith-waterman algorithm on graphics hardware. the sw algorithm is implemented using the streaming architecture of gpus by reformulating it in terms of computer graphics primitives. the implementation relies on opengl, in which a conversion of the problem to the graphical domain is needed, as well as a reverse procedure to convert back the results. although, it achieves a high efficiency, programming in opengl requires specialized skills. therefore, manavski re-implemented the sw algorithm on a gpu with the recently released c-based cuda programming environment. the implementation performs from to times faster than any other previous attempt available on commodity hardware. in this paper, we demonstrate how the playstation®, a commodity hardware powered by the cell broadband engine, can be used as a low cost computational platform to accelerate the smith-waterman algorithm. our implementation is able to outperform both the striped method on an intel core duo as well as the cuda-based gpu implementation on a geforce gtx. the smith-waterman algorithm the smith-waterman algorithm is used to determine the optimal local alignment between two nucleotide or protein sequences. the algorithm compares two sequences by computing the similarity score by means of dynamic programming. two elementary operations are used: substitution and insertion/deletion. the original algorithm was proposed by smith and waterman with a complexity of o and was improved by gotoh to run at o. consider two strings s and s with length m and n, respectively. the smith-waterman algorithm computes the similarity value m of two sequences ending at position i and j of the two sequences s and s respectively. for affine gap penalties, i.e. α ≠ β, the computation of m, for ≤ i ≤ m, ≤ j ≤ n, is given in the following equations 1–3: m = max{m + sbt, s e, f, 0}, e = max{m - α, e - β}, f = max{m - α, f - β}, where sbt is a character substitution cost table, α is the cost of the initial gap; β is the cost of the following gaps. for linear gap penalties, i.e. α = β, the above recurrence relations can be simplified as shown in equations 4: m = max{m + sbt, s m - α, m - α} initialization values are given as the following: for ≤ i ≤ m, ≤ j ≤ n, m = m = e = f = each position of the matrix m is a similarity value. the two segments of s and s producing this value can be determined by a trace-back procedure. cell broadband engine architecture the cell broadband engine is a recently introduced single-chip heterogeneous multi-core processor, which is developed by sony, toshiba and ibm. the cell be offers a unique assembly of thread-level and data-level parallelization options. it is operating at the upper range of existing processor frequencies and is projected to run at more than ghz in the near future. several examples of bioinformatics applications that has been ported to the cell be architecture include folding@home, fasta, clustalw and raxml. the cell be combines an ibm powerpc processor element and eight synergistic processor elements. an integrated high-bandwidth bus called the element interconnect bus connects the processors and their ports to external memory and i/o devices. the block diagram of the cell be architecture is shown in figure the ppe is a 64-bit power architecture core and contains a 64-bit general purpose register set, a 64-bit floating point register set, and a 128-bit altivec register set. it is fully compliant with the 64-bit power architecture specification and can run 32-bit and 64-bit operating systems and applications. each spe is able to run its own individual application programs. each spe consists of a processor designed for streaming workloads, a local memory, and a globally coherent direct memory access engine. the eib is a 4-ring structure, and can transmit bytes per cycle, for a bandwidth of gigabytes/second. the eib can support more than outstanding dma requests. the most distinguishing feature of the cell be lies within the variety of the processors it has, i.e. the ppe and the spes. heterogenous multi-core systems can lead to decreased performance if both the operating system and application are unaware of the heterogeneity. the ppe is designed to run the operating system and, in many cases, the top-level control thread of an application, while the spes is optimized for compute intensive applications, hence, providing the bulk of the application performance. the spe can access ram through direct memory access requests. the dma transfers are handled by the memory flow controller. the mfc provides the interface, by means of the eib, between the local storage of the spe and main memory. the mfc supports dma transfers as well as mailbox and signal-notification messaging between the spe and the ppe and other devices. data transferred between local storage and main memory must be 128-bit aligned. the size of each dma transfer can be at most kb. dma-lists can be used for transferring large amounts of data. a list can have up to dma requests, each for up to kb. the ps uses the cell broadband engine as its cpu, hence making it possible for users to create a high-powered computing environment for a fraction of the cost of a cell blade server. the ps utilizes seven of the eight spes, in which the eighth spe is disabled to improve chip yields, i.e. chips do not have to be discarded if one of the spes is defective. only six of the seven spes are accessible to developers as one is reserved by the operating system. the power requirement for the ps is v ac, hz and the power consumption approximately w. generally available ps3's can be used for scientific high performance computing through installation of linux. programs can be developed the using freely available c-based cell be sdk. at the time of this writing, the retail price of the playstation® is us$ for gb and us$ for gb, while the retail price of the nvidia geforce 8800gtx card is us$ and a dell optiplex with intel core duo ghz processor is us$ a qs blade server with two cell be chips has a retail price of us$. thus, the ps offers a good alternative to other accelerator technologies. methods cell be mapping our sequence alignment implementation uses affine gap penalties and utilizes the 128-bit wide simd vector registers of the spes for optimization. the vectorization strategy is based on a column-based approach. it also employs a static load balancing strategy, which means that the work load is known at the start and distributed equally across the spes. the code is written in c together with the cell be simd multimedia extension language intrinsics and spu intrinsics for portability. dma transfers and mailbox functions are used for communication purposes. a list of spu low-level specific and generic intrinsics used in our vectorized implementation, divided into categories, is shown in table constant formation intrinsics, arithmetic intrinsics, compare, branch and halt intrinsics, bits and mask intrinsics, logical intrinsics, shift and rotate intrinsics and scalar intrinsics have been employed to access hardware features, which are not easily accessible from a high level language in order to obtain the best performance from the cell be. spu_and spu_nor spu_rlmaskqwbyte list of spu low-level specific and generic intrinsics used in the implementation are listed and sorted into categories, as shown below. more details about the syntax and semantics of these intrinsics can be found in. due to the fact that the spes only have kbytes of local memory, which have to store program code and data, memory allocation is crucial for the spe. the current longest sequence in the swiss-prot database is amino acids. in order to accommodate for longer protein sequence in the future, we allocate dynamic memory for the database sequences of up to amino acids per sequence. due to these limitations, the maximum query sequence length allowed for our implementation is limited to query profile in order to calculate m in the sw dp matrix, the value sbt needs to be added to m. to avoid performing this table lookup for each element in the dp matrix, rognes and farrar suggested calculating a query profile parallel to the query sequence beforehand. assuming that s s ∈ Σ* and s is the query sequence, the query profile is defined as a set p = {px | x∈Σ} consisting of |Σ| numerical strings of length l each, where l = |s1|. each string px ∈ p consists of all substitution table values that are needed to compute a complete column j of the dp matrix for which s = x. pre-computing the query profile greatly reduces the amount of substitution table lookup in the sw dp matrix computation, since |Σ| is usually much smaller than |s2|. the query profile can be calculated in a straightforward sequential layout or in a more complex striped layout, as shown in figure the values in the query profile for sequential and striped layout are defined in equation and respectively: px = sbt, for all ≤ i ≤ l px=sbt%p)t)+⌊i−1p⌋+1],x)for all 1≤i≤l where p is the number of segments and t is the segment length. in the striped layout, p corresponds to the number of elements that can be processed in a simd vector register. the length of each segment, t is defined in equation t = ⌈/p⌉ both approaches allow efficient vectorization on sse2-compatible processors using the corresponding simd instruction set. using the pre-calculated query profile, the computation of the dp matrix can be performed in column-wise order. due to the simplified dependency relationship and parallel loading of the vector scores from memory, fast dp matrix calculations can be achieved. the advantage of the striped layout compared to the sequential layout is that data dependencies between vector registers are moved outside the inner loop. for instance, when calculating vectors for the dp matrices h or f with the sequential layout, the last element in the previous vector has to be moved to the first element in the current vector. when using the striped query layout, this needs to be done just once in the outer loop when processing the next subject sequence character. saturation arithmetic the inner loop of the algorithm requires saturation arithmetic, namely saturated additions and saturated subtractions. the cell be lacks the saturation arithmetic support, leaving the tasks to be handled by software instead of direct hardware support. in order to tackle this problem, we introduced two new functions, namely spu_adds and spu_subs to handle saturated additions and saturated subtractions, respectively.  in this section, we analyze the performance of our parallel algorithm for various query sequence lengths using sequences from swiss-prot database. searches for query sequences with various lengths between to amino acids were performed. the accession numbers of the query sequences used are o p p p p p p q8zgb p p p p p p p p q and o respectively. all queries were run against swiss-prot release comprising, amino acids in sequence entries. the gap-open penalty used was and the gap-extension penalty used was the scoring matrix used in the testing was blosum all experiments were carried out on a standalone playstation® machine, with yellow dog linux operating system and the cell software development kit. the performance statistics measured are then converted to the following measurements, i.e. computational time and mega cell updates per second. given a query sequence of size q and a database of size d, the mcups rating is calculated by equation |q|×|d|×106t where |q| = size of query sequence in amino acids |d| = size of database sequences in amino acids t = run time performance evaluation of our implementation, in terms of computational time and mcups. all queries were run against swiss-prot release comprising, amino acids in sequence entries. eighteen query sequences of length to amino acids were used. the gap-open penalty used is and the gap-extension penalty used was the blosum scoring matrix was used. we have compared the performance of our cbesw implementation with other publicly available implementations of sw-based protein database scanning, namely ssearch, striped smith-waterman and cuda. the query sequences, as well as their respective swiss prot accession numbers, used in the different performance comparisons are shown in table list of query sequences, as well as their respective accession number, used in different performance comparisons with other publicly available implementations of sw-based protein database scanning, namely ssearch, striped smith-waterman and cuda. ssearch is a sw implementation which is part of the fasta package. the ssearch performance is benchmarked on an intel core duo ghz cpu with gb ram. both execution cores were used in the experiment. as shown in figure for a query sequence of length, ssearch achieves a performance of mcups. thus, our implementation is over times faster. the performance comparison between the ps implementation and cuda-sw on one nvidia geforce 8800gtx is shown in figure the cuda implementation experiment was conducted with a geforce 8800gtx mb installed in a pc with a dual-core amd opteron ghz cpu, gb ram running fedora the substitution matrix used is blosum as can be seen from the figure, our implementation achieves a better mcups performance. the ps peak performance is times faster compared to the peak performance cuda implementation on a single nvidia geforce 8800gtx.  in this paper, we have demonstrated that the playstation® powered by the cell broadband engine, can be effectively used to accelerate a biological sequence alignment application. in order to derive an efficient mapping onto this type of heterogeneous multi-core architecture, we have utilized simd vectorization and parallel data partitioning and communication techniques. our implementation achieves a peak performance of. mcups for a query sequence of length hence, the peak performance of our implementation is times and times faster than ssearch and striped sw, on an intel core duo ghz. the ps peak performance is also times faster compared to the peak performance cuda implementation on a single nvidia geforce 8800gtx. the very rapid growth of biological sequence databases demands even more powerful high-performance solutions in the near future. hence, our results are especially encouraging since high performance computer architectures are developing towards heterogeneous multi-core systems. due to the kb memory limitation of the spe local store, the maximum query sequence length in our current implementation is one of the limiting factors is that the size of the query profile grows with the length of the query sequence. part of our future work is therefore to tackle this limitation. a promising approach is to align subject sequences against separate chunks of the query profile. the complete query profile only needs to be stored once in the main memory instead of the local store of the spe. this frees up more memory space for the spes and thus allows longer query sequences. given a query sequence of length l, the query profile can be divided into n chunks in which each chunks contains a query profile of size l/n. the respective spes can then align a part of the chunk of the query profile it has and get the next chunk from outside memory via concurrent dma transfer. availability and requirements ▪ project name: cbesw ▪ project homepage: ▪ operating system: only tested with playstation® with yellow dog linux ▪ programming language: c ▪ other requirements: cell sdk ▪ license: none ▪ any restrictions to use by non-academics: none abbreviations cpu: central processing unit; cuda: compute unified device architecture; cups: cells updates per seconds; dp: dynamic programming; dma: direct memory access; fpga: field-programmable gate arrays; gpu: graphics processing unit; mfc: memory flow controller; ppe: powerpc processor element; simd: single instructions multiple data; spe: synergetic processor element; sse: streaming simd extensions; sw: smith-waterman competing interests the authors declare that they have no competing interests. authors' contributions aw conceived the study, participated in its design, implementation and coordination, performed benchmark test cases and drafted the manuscript. tnh participated in the design and implementation of the source code. kck participated in the creation of the manuscript. bs conceived the study, participated in the analysis and interpretation of data. all authors have read and approve the final manuscript. supplementary material additional file 1 the file is the compressed source code for the cbesw. click here for file additional file 2 the file is the executable file for cbesw. the command to run it is./cbesw. click here for file additional file 3 readme file for cbesw file. click here for file acknowledgements aw is supported by the phd program of nanyang technological university.
the recent emergence of accelerator technologies has made it possible to achieve an excellent improvement in execution time for many bioinformatics applications, compared to current general-purpose platforms. in this paper, we demonstrate how the playstation® powered by the cell broadband engine, can be used as a computational platform to accelerate the smith-waterman algorithm. as a result, the computational power needed by bioinformatics applications is growing exponentially as well. the results from our experiments demonstrate that the playstation® console can be used as an efficient low cost computational platform for high performance sequence alignment applications. the exponential growth of available biological data has caused bioinformatics to be rapidly moving towards a data-intensive, computational science. our implementation achieves a peak performance of up to mcups.
 the exponential growth of available biological data has caused bioinformatics to be rapidly moving towards a data-intensive, computational science. as a result, the computational power needed by bioinformatics applications is growing exponentially as well. the recent emergence of accelerator technologies has made it possible to achieve an excellent improvement in execution time for many bioinformatics applications, compared to current general-purpose platforms. in this paper, we demonstrate how the playstation® powered by the cell broadband engine, can be used as a computational platform to accelerate the smith-waterman algorithm.  for large datasets, our implementation on the playstation® provides a significant improvement in running time compared to other implementations such as ssearch, striped smith-waterman and cuda. our implementation achieves a peak performance of up to mcups.  the results from our experiments demonstrate that the playstation® console can be used as an efficient low cost computational platform for high performance sequence alignment applications. 