Title :
A systolic array for sequence comparison based on two-logic-levels processing element
Author :
Hireche, Nasreddine ; Langlois, J. M Pierre ; Nicolescu, Gabriela
Author_Institution :
Dept. de Genie Inf., Ecole Polytech. de Montreal, Montreal, QC
Abstract :
In this work, we implement a dynamic programming (DP) algorithm for sequence comparison (SC) purposes. We aimed at obtaining a better compromise between the processing acceleration optimization and the hardware cost. A simplified edit distance (ED) calculation formula is used, where we introduce two new simplified logical equations based on this last formula. A systolic array (SA) based on our simplified processing element (PE) can compare sequences with a great length and a high processing frequency. Our system speed-up shows a gain varying between 13% and 142% compared to other systems, according to the considered FPGA family.
Keywords :
dynamic programming; field programmable gate arrays; systolic arrays; FPGA; dynamic programming algorithm; edit distance calculation formula; sequence comparison; systolic array; two-logic-levels processing element; Acceleration; Biology computing; Dynamic programming; Equations; Field programmable gate arrays; Genetics; Hardware; Heuristic algorithms; Sequences; Systolic arrays; Dynamic Programming; FPGA; Parallel Hardware Acceleration; Sequence Comparison; Systolic Array;
Conference_Titel :
Circuits and Systems, 2007. NEWCAS 2007. IEEE Northeast Workshop on
Conference_Location :
Montreal, Que
Print_ISBN :
978-1-4244-1163-4
Electronic_ISBN :
978-1-4244-1164-1
DOI :
10.1109/NEWCAS.2007.4487953
