Comparing Long Strings on a Short Systolic Array

Abstract:

In this paper we demonstrate two techniques for comparing strings of arbitrary length on a systolic array we have proposed and implemented. The first is an application of algorithm partitioning, the second an implementation of a string matching heuristic for which we prove performance bounds. We analyze the
time and number of processors required in each case and determine the processor utilizations.