SYSTOLIC ARRAY OF PIPELINED PROCESSING ENGINES FOR IMPLEMENTING DYNAMIC PROGRAMMING ALGORITHMS

摘要

An integrated circuit that is capable of performing sequence alignment via dynamic programming methods is provided. The integrated circuit may include a linear systolic array having series-connected processing engines, each of which has a n-stage deep pipeline. The systolic array may align first and second sequences, wherein the first sequence is divided into multiple segments equal to the internal depth of the pipeline. The systolic array may compute matrix scores for these segments in parallel until the entire sequence matrix score is computed. The internal pipeline structure and a loopback memory within the systolic array are configured to take care of any required data dependencies in the computation of the matrix scores.