Essay --

The acceleration of string pattern matching problems in hardware has started as early as 1980 [1] with the special purpose VLSI chip used by Foster and Kung to compute an algorithm for the string pattern matching problem using systolic array architecture. The term systolic array was coined by Kung and Leiserson in 1978 at the Carnegie-Mellon University [2]. This one-dimensional array enables the acceleration of Dynamic Programming (DP) algorithms by means of computing the recursive equation in anti-diagonal flow instead of sequential flow as in a standard microprocessor. Another early study which implemented the DP algorithm on special-purpose VLSI chip was reported by Lipton and Lopresti in 1985. The sequence edit distance algorithm was implemented in the processing element and a total of 30 systolic processors were used for the acceleration of the pattern matching problem. Following that, the Princeton Nucleic Acid Comparator (P-NAC) was reported by Lopresti in 1987 [3]. This VLSI core performed DNA sequence comparisons and achieved speeds 125 times faster than a minicomputer (DEC VAX 11/785). In the early 1990s, Field Programmable Gate Arrays (FPGAs) were used to accelerate the algorithm using a linear systolic array. SPLASH was among the first off-the-shelf FPGA-based sequence edit distance accelerators, and was reported by Hoang and Lopresti [4]. It comprised of 24 PEs where each implemented the sequence edit distance algorithm. However, at that time FPGAs were not as competitive as they are today. Thus, other parallel architectures were developed, including the single instruction multiple data (SIMD) architectures such as micro grain array processor (MGAP) [4] in 1994, Kestrel [5] in 1996 and Fuzion [6] in 2002. These parall... ...poses a new processor array architecture for the Smith-Waterman with affine gap penalty alignment algorithm that are more efficient in speed and area than the processor array architecture of [23] specially for short query sequences. This is achieved by applying a nonlinear mapping methodology to the Smith-Waterman with affine gap penalty alignment algorithm after expressing it as Regular Iterative Algorithm (RIA). This methodology uses a data scheduling and node projection techniques to explore the systolic array architecture of the algorithm. Also, we present the hardware implementation of the processing element (PE) of the proposed systolic array structure and apply a scheduling strategy to the PE architecture in order to re-use the systolic array for the multiple pass processing of such biological sequences without requiring additional time for PE configuration.