STRING-PROCESSING ON THE HYPERCUBE

We give parallel algorithms for solving some string comparison problems on the hypercube. These algorithms are widely applicable to the problems of speech and signal processing. For strings x and y with length(jr) = m, length(y) = n, and assuming n ≥ m, we show the following: the substring problem (where typically m is much smaller than n) can be solved in O(m + log(n/m)) time using O(m) space per processing element (PE) on an MIMD hypercube of O(n/m) PE's. We note that this algorithm has an optimal processor-time product if m is bounded below by log(n/m). The results of implementing this algorithm on the NCUBE/7 hypercube machine are presented. We also show that the longest common substring problem can be solved in O(log n) time using O(1) space per PE on an SIMD hypercube of O(n2) PE's. Finally, we show that the string edit problem, the longest common subsequence problem, the minimum-length time-warping problem, and many other speech recognition problems can be solved in 0(log2 n) time using O(1) space per PE on an SIMD hypercube of O(n3/log2 n) PE's. © 1990 IEEE