Systolic array for solving cyclic loop dependent algorithms

Abstract

A systolic array (1) for reducing the time required to solve an algorithm having cyclic loop dependency, i.e., nested loops in which values calculated by inner loops depend upon indices of said inner loops and upon indices of outer loops. The array (1) comprises a chain of several identical serially connected and sequentially accessed cells. In the preferred embodiment, each cell, except for first and last cells in the chain, is connected to its two adjacent cells only. Multiprocessing is employed: at certain times during the algorithm solving, more than one cell is simultaneously activated to perform portions of the solving, so that the total time required to solve the algorithms is shortened to be a linear function of n.times.m. The algorithm can represent measurement of the distance between two symbolic strings, or other problems in artificial intelligence or logic. The algorithm is broken up into nm subalgorithms D(i,j); at each processing step, those subalgorithms D(i,j) are solved for which sufficient information exists for their solution. In the illustrated example, this condition is represented by diagonally time-slicing a two-dimensional matrix having as elements each of the subalgorithms D(i,j).